{"id":"606ef695-fb41-42f7-b8f5-acca74c85c09","arxiv_id":"2505.14641","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For H(2,q), the paper gives tight size thresholds for forcing VC-dimension 2 or 3, but some higher-dimensional sharpness constructions are incorrect.","lead":"Tight extremal bounds are proven for the size a subset of a Hamming graph must have before its neighborhood system can shatter two or three points. The results sharpen earlier work, but several supporting constructions contain mathematical errors, so the full set of claims does not hold as written.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.2's no-rectangle proof fails for q=6: four explicit points in U''_3(6) form a rectangle, so the sharpness of Corollary 1.4 (Proposition 1.7) is unproven.","rationale":"The reader's weakest assumption is exactly the modular arithmetic step in Lemma 4.2, and I agree that this is the load-bearing fault. The paper's advertised central accomplishment includes a complete size-based characterization of VC-dimension 3 in H(d,q): Corollary 1.4 gives a sufficient size threshold and Proposition 1.7 claims a matching construction. Proposition 1.7 depends entirely on Lemma 4.2 establishing a set with no 4-point lines and no rectangles. The q=6, d=3 counterexample shows the no-rectangle conclusion is false, so the sharpness claim is unproven. This is not a cosmetic typo: the paper explicitly states 'we have completely characterized which subsets ... have VC-dimension 3 in terms of size.' The main H(2,q) theorems may be correct, but the higher-dimensional characterization is a central advertised result. Proposition 1.6 is also false under the paper's own range convention, but it is less load-bearing than Lemma 4.2. Therefore the reader's rejection is justified, and I recommend no change to the verdict.","tokens_in":15429,"tokens_out":16209,"duration_ms":134740,"concrete_test":"For q=6 and d=3, list the points of U''_3(6) in the plane x2=0 and check whether (0,0,2), (0,0,5), (3,0,5), (3,0,2) are all present and form a rectangle. If they are, Lemma 4.2's no-rectangle proof is invalid; this check settles whether Proposition 1.7's construction actually avoids rectangles.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 4.2, after assuming ϵx=ϵz, the proof derives ϵw−ϵy = 2(y1−w1) in Z_q and concludes that if ϵw=ϵy then y1=w1. This is false for even q: the congruence 2(y1−w1)≡0 mod q has the nonzero solution y1−w1=q/2. For q=6 and d=3, fix the middle coordinate x2=0 and take the four points (0,0,2), (0,0,5), (3,0,5), (3,0,2). Each satisfies x3 ∈ {x1+x2−1, x1+x2, x1+x2+2} mod 6, so all four lie in U''_3(6), and they form an axis-parallel rectangle. Thus the claimed 'no rectangle' property, which is the basis for applying Lemma 4.1 to conclude VC-dim ≤2, is false. Consequently Proposition 1.7—the sharpness of Corollary 1.4—is not proven, and the paper's advertised complete characterization of VC-dimension 3 in H(d,q) in terms of size rests on a false lemma. Separately, Proposition 1.6 asserts a q^{d-1}-point independent set has VC-dimension 1, but under the paper's own convention used in Lemma 2.2, where ranges are intersections with n(v) for v∈U, an independent set has every range empty and VC-dimension 0, not 1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the VC-dimension of the set system induced by open neighborhood ranges on subsets of Hamming graphs H(d,q). Its main results are: (i) for H(2,q), any U with |U| ≥ 2q for odd q has VC-dimension at least 2, and any U with |U| ≥ 3q+1 for q ≥ 4 has VC-dimension 3, with matching constructions; (ii) a pigeonhole corollary transferring the H(2,q) bound to H(d,q) and giving VC-dimension 3 for |U| ≥ 3q^{d-1}; (iii) constructions intended to show sharpness of this corollary and to bound VC-dimension from above (Propositions 1.5, 1.6, 1.7); and (iv) analogous results for H(2,q,2). The H(2,q) portion is elementary and mostly sound, but the higher-dimensional sharpness construction in Proposition 1.7 has a genuine modular-arithmetic gap, and Proposition 1.6 is false under the paper's stated convention.","tokens_in":15749,"tokens_out":17798,"duration_ms":176271,"significance":"If corrected, the paper would provide clean, tight size thresholds for VC-dimension 2 and 3 in H(2,q), a useful pigeonhole transfer to higher dimensions, and several explicit constructions with no parameter fitting. The H(2,q) arguments and the 'fist' and 'row-pluck' lemmas are genuine contributions. However, the advertised complete characterization of VC-dimension 3 in H(d,q) depends on Proposition 1.7, whose proof is invalid for even q, and Proposition 1.6 is false as stated. These are load-bearing gaps, so the manuscript cannot be accepted in its current form, but the H(2,q) core appears salvageable in a major revision.","major_comments":[{"comment":"The no-rectangle proof fails for even q. From the congruence εw − εy = 2(y1 − w1) in Z_q, the proof concludes that εw = εy forces y1 = w1. For even q this is false: 2(y1 − w1) ≡ 0 mod q has the nonzero solution y1 − w1 = q/2. Concretely, for q = 6 and d = 3, the four points (0,0,2), (0,0,5), (3,0,5), (3,0,2) all lie in U''_3(6) and form an axis-parallel rectangle in the plane x2 = 0. Thus the asserted rectangle-free property is false, and Lemma 4.1 cannot be applied. This leaves Proposition 1.7, the claimed sharpness of Corollary 1.4, unproved, so the paper's advertised complete characterization of VC-dimension 3 in H(d,q) is not established.","section":"§4.3.2, Lemma 4.2 and Proposition 1.7"},{"comment":"Under the convention used throughout the paper, where ranges are the intersections n(u) ∩ U for u ∈ U (see Lemma 2.2 and Lemma 5.3), the set U'_d(q) is an independent set. Every range in (U'_d(q), n(U'_d(q))) is therefore empty, so the VC-dimension is 0, not 1: no neighborhood in U contains a given vertex. Proposition 1.6 is false as stated; at most it shows the existence of a set of size q^{d-1} with VC-dimension at most 1.","section":"§4.2, Proposition 1.6"},{"comment":"Proposition 1.7 is internally inconsistent as printed: it refers to H(3,q) but uses the dimension parameter d and the size 3q^{d-1}. Moreover, the proof via Lemma 4.2 requires d ≥ 3 and q ≥ 6, whereas Proposition 1.7 claims d,q ≥ 2. These parameter ranges and the notational mismatch must be fixed, and any revised version must address the even-q counterexample described in the first major comment.","section":"§4, Proposition 1.7 statement"}],"minor_comments":[{"comment":"The displayed union for U1(q) runs i = 0 to q/2, which gives q/2 + 1 translates modulo q with the term i = q/2 coinciding with i = 0; the intended construction should run i = 0 to q/2 − 1.","section":"§2.2.1, Lemma 2.2"},{"comment":"The definition of U'_d(q) says 'U'_d(q) ⊂ H(q,d)' but should say H(d,q), and the phrase 'H(q,d)' appears again in the proof of Lemma 4.2.","section":"§4.2, definitions"},{"comment":"The displayed checks after equation (3) contain transcription errors, such as '2 + 2 ≠ −1 = (−1) + 0εy + εw' and the expression '2εy + εw'; the intended sums are εy + εw throughout.","section":"§4.3.2, Lemma 4.2 final case check"},{"comment":"The description of a rectangle as points 'each point adjacent to the points it was listed next to' is slightly ambiguous because adjacency in Hamming graphs means differing in exactly one coordinate; a figure or a coordinate-based definition would improve clarity.","section":"§4.3.2, rectangle definition"}],"recommendation":"major_revision","confidential_remarks":"The H(2,q) results appear sound and are worth publishing after repair. The main obstruction is the unproved sharpness claim for H(d,q) (Proposition 1.7) and the false statement of Proposition 1.6. I would invite a revision in which the authors either provide a correct higher-dimensional construction or explicitly restrict the sharpness claim to the range where the proof works, and correct Proposition 1.6."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper has two genuinely good results about VC-dimension in H(2,q), and a bunch of higher-dimensional claims that don't hold up. The good part is Theorems 1.2 and 1.3. The proofs are elementary and, as far as I can tell, correct: for odd q, 2q points force a shattered pair, and the 3q+1 threshold for VC-dimension 3 is tight via the diagonal-3-points-per-line construction. Those are real improvements over [11], and worth keeping.\n\nThe trouble starts in Section 4. Proposition 1.6 asserts that the hyperplane x_d = Σ_{j=1}^{d-1} x_j has VC-dimension 1. But that set is an independent set in H(d,q), so every neighborhood restricted to U is empty. Under the paper's own range convention, that gives VC-dimension 0, not 1. You can't fix this by reading the neighborhoods in the ambient graph, because the shattered set is inside U and the intersection with U is still empty.\n\nLemma 4.2 has a modular arithmetic gap. The proof concludes that if ε_w = ε_y then 2(y_1 - w_1) = 0 forces y_1 = w_1. Over Z_q that's only true for odd q. For even q, y_1 - w_1 = q/2 is a nonzero solution. The stress-test gives an explicit rectangle for q=6: (0,0,2), (0,0,5), (3,0,5), (3,0,2) all lie in U''_3(6). So the no-rectangle argument fails exactly when q is even, which is most of the parameter range. Proposition 1.7, the claimed sharpness of Corollary 1.4, depends on that lemma and is therefore unproven. There's also a typo in the statement of Proposition 1.7 – it says H(3,q) but the construction is in H(d,q).\n\nNone of this casts doubt on the H(2,q) core. The d=2 results are the main event, and they're probably right. But the abstract's promise of 'many of these being tight as well' oversells the paper, because the advertised complete characterization of VC-dimension 3 in higher dimensions rests on a false lemma.\n\nWho should read this? Anyone interested in VC-dimension of pseudorandom or Hamming graphs. The H(2,q) theorems are a useful benchmark. But the paper needs major revision before it's publishable: fix or drop Proposition 1.6, repair Lemma 4.2 (or restrict it to odd q and state the even-q case as open), and correct the Proposition 1.7 statement. I'd send it to a referee, but with the expectation that the higher-dimensional sections need substantial rework.","headline":"The H(2,q) threshold theorems look solid and new, but the higher-dimensional sharpness claims are broken (Proposition 1.6 is false, Lemma 4.2 fails for even q), so the advertised complete characterization does not hold as written.","tokens_in":16290,"tokens_out":5080,"would_cite":true,"duration_ms":43946,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C99","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper pins down the exact subset sizes of Hamming graphs that force VC-dimension 2 or 3, and proves each threshold is tight.","keywords":["VC-dimension","Hamming graphs","neighborhood systems","shattering sets","tight bounds","point configurations","pigeonhole principle","pseudorandom graphs"],"falsifier":"For $q=6$, inspect the set defined by $x_d \\in \\{-1,0,2\\} + \\sum_{j=1}^{d-1} x_j$ and look for four points forming a rectangle; the congruence $\\epsilon_w-\\epsilon_y = 2(y_1-w_1)$ admits the nonzero solution $y_1-w_1=3$ modulo 6, so if those four points are present, the no-rectangle claim fails and the sharpness construction is invalid for even $q$.","tokens_in":15245,"feed_emoji":"📐","tokens_out":8789,"duration_ms":82867,"temperature":0.7,"pith_summary":"The paper asks how many vertices of a Hamming graph $H(d,q)$ a set $U$ must contain before the neighborhood system $n(U)$ can shatter a pair or a triple of points. The main answer is a pair of tight thresholds in the two-dimensional case: for $q\\ge 4$, every $U\\subset H(2,q)$ with $|U|\\ge 3q+1$ has VC-dimension exactly 3, and a construction with $3q$ vertices shows that no smaller size guarantees this. For odd $q$, $2q$ vertices guarantee VC-dimension at least 2, with a matching counterexample. The paper also gives pigeonhole corollaries for higher dimensions and a sharp threshold for the distance-two Hamming graph $H(2,q,2)$. These thresholds matter because they are exact, elementary size conditions for a quantity that earlier pseudorandom-graph methods could only bound loosely.","feed_headline":"3q+1 vertices of a Hamming graph force VC-dimension 3","feed_subtitle":"For Hamming grids, neighborhood systems shatter triples exactly at this size threshold.","key_machinery":"The load-bearing object is the 'fist': a line $L$ containing four points $x,y,z,u_3$, with $x,y,z$ each having an additional point $u_x,u_y,u_z$ on the perpendicular line through it. A fist plus one extra point $u_0$ gives all eight intersections of neighborhoods with $\\{x,y,z\\}$, hence a shattered triple. The matching upper bound runs through the contrapositive: Lemma 3.1 shows that a subset of $H(2,q)$ with VC-dimension 3 must have a line with four points, so any set with at most three points on every line has VC-dimension below 3. The same 'four points on a line or a rectangle' dichotomy (Lemma 4.1) is the mechanism for the higher-dimensional constructions.","core_discovery":"The paper's central claim is that in $H(2,q)$ the VC-dimension of a subset against its neighborhood system is controlled by how many points lie on a single row or column. Theorem 1.3 proves that $|U|\\ge 3q+1$ forces $\\mathrm{VCdim}((U,n(U)))=3$: the size condition puts four points on one line, and the resulting 'fist' configuration shatters a triple. Lemma 3.2 shows the bound is tight by building $3q$ points with exactly three points on every row and column, and Lemma 3.1 shows that no such set can shatter a triple. Theorem 1.2 proves the analogous sharp threshold $2q$ for VC-dimension at least 2 when $q$ is odd. The remaining results extend the same line-counting principle to higher dimensions by pigeonholing and to $H(2,q,2)$.","pith_inferences":["If the rectangle-free construction in Lemma 4.2 can be repaired for even $q$, the likely consequence is that the $3q^{d-1}+1$ threshold in Corollary 1.4 is sharp for all $q$, fully settling the VC-dimension 3 size threshold in all dimensions.","The dichotomy behind Lemma 4.1 suggests a general heuristic: in Hamming graphs, VC-dimension 3 arises either from four collinear points or from a rectangle; one could test whether this dichotomy extends to other Cartesian product graphs built from grids.","A natural next question the paper leaves open is the exact threshold for VC-dimension 2 in $H(d,q)$ for $d\\ge 3$; the constructions here show the exponent is $q^{d-1}$, but the constant may depend on the parity of $q$, mirroring the two-dimensional case.","For $H(d,q,t)$ with $t>2$, the row-pluck and column-pluck configurations used for $t=2$ may give tight thresholds for larger $t$ as well, especially when a parity obstruction like the one in Lemma 4.2 is absent."],"forward_implications":["For $H(2,q)$, the paper completes the size classification: VC-dimension 3 is guaranteed exactly at $3q+1$ vertices for $q\\ge 4$, and VC-dimension at least 2 is guaranteed at $2q$ vertices when $q$ is odd, with tight counterexamples at $3q$ and $2q-1$.","For higher ambient dimensions, any subset of $H(d,q)$ with $q\\ge 4$ and size at least $3q^{d-1}+1$ has VC-dimension 3, and the constructions give sets of size on the order of $3q^{d-1}$ with VC-dimension at most 2, showing the exponent is correct.","For the distance-two graph $H(2,q,2)$, $2q$ vertices force VC-dimension at least 2, while $2q-1$ vertices can keep VC-dimension below 2; pigeonholing then gives a nontrivial threshold in $H(d,q,2)$ for $d\\ge 3$.","Because the proofs are elementary counts of points on rows and columns, the bounds hold for every subset of the Hamming graph, with no pseudorandomness or spectral assumption on the subset."],"supporting_citations":[{"why":"Supplies the earlier suite of VC-dimension results for pseudorandom graphs and the initial Hamming-graph bounds that this paper improves and generalizes.","marker":"[11]"},{"why":"Gives prior VC-dimension results for Johnson and Hamming graphs that motivate the size-threshold questions addressed here.","marker":"[1]"},{"why":"Introduces VC-dimension, the quantity whose thresholds the paper establishes.","marker":"[12]"},{"why":"Exemplifies the point-configuration method for VC-dimension in discrete planes that the line-counting arguments extend.","marker":"[7]"},{"why":"Records the pseudorandom and eigenvalue properties of Hamming graphs that the paper says standard techniques rely on.","marker":"[6]"}],"fun_headline_variants":[],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sharpness of the higher-dimensional threshold rests on the claim that the constructed set $U''_d(q)$ contains no rectangle; that claim depends on an arithmetic congruence modulo $q$ having only the trivial integer solution, which can fail when $q$ is even.","fun_headline_variants_meta":{"error":"Client error '402 Payment Required' for url 'https://api.deepseek.com/chat/completions'\nFor more information check: https://developer.mozilla.org/en-US/docs/Web/HTTP/Status/402"},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:34:21.996431+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $q=6$, inspect the set defined by $x_d \\in \\{-1,0,2\\} + \\sum_{j=1}^{d-1} x_j$ and look for four points forming a rectangle; the congruence $\\epsilon_w-\\epsilon_y = 2(y_1-w_1)$ admits the nonzero solution $y_1-w_1=3$ modulo 6, so if those four points are present, the no-rectangle claim fails and the sharpness construction is invalid for even $q$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the earlier suite of VC-dimension results for pseudorandom graphs and the initial Hamming-graph bounds that this paper improves and generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives prior VC-dimension results for Johnson and Hamming graphs that motivate the size-threshold questions addressed here."},{"cited_title":"Chervonenkis and V","cited_arxiv_id":null,"evidence_quote":"Introduces VC-dimension, the quantity whose thresholds the paper establishes."},{"cited_title":"Discrete and Computational Geometry 71 (2024), no","cited_arxiv_id":null,"evidence_quote":"Exemplifies the point-configuration method for VC-dimension in discrete planes that the line-counting arguments extend."},{"cited_title":"Brouwer, S","cited_arxiv_id":null,"evidence_quote":"Records the pseudorandom and eigenvalue properties of Hamming graphs that the paper says standard techniques rely on."}],"review_version":1}