{"id":"70356b36-4826-4214-b7ea-3771ecdd042d","arxiv_id":"2411.14597","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every eigenvalue of a Hamming ball subgraph equals 2x minus (n minus 2t) for a root x of a Krawtchouk polynomial, with explicit eigenspaces; this yields the maximal eigenvalue as n minus 2 times the first root of K_{r+1}^{(n)} and extends spectral extremality of Hamming balls to subconstant…","lead":"This paper gives the complete list of eigenvalues and eigenspaces of the adjacency matrix of a Hamming ball, a natural subset of the Boolean cube, in terms of roots of Krawtchouk polynomials. It then uses this to show that Hamming balls are essentially the extremal subsets of the cube for maximal eigenvalue over a much wider range of sizes than previously known.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1.6's proof assumes the top-level span {g_y : |y|=j} = U_j, a nontrivial full-rank fact for the inclusion matrix; without it the W_y decomposition is unsupported.","rationale":"The core spectral theorem appears mathematically sound: the tridiagonal reduction in Corollary 2.4 is consistent, the Krawtchouk recurrence in Lemma 2.5 checks out, and the final dimension count is coherent. The single place where the written proof is unsupported is the spanning assertion inside Proposition 1.6. The definitions in §1.0.1 define U_j using all subsets of size at most j, so the claim that the top layer {g_y}_{|y|=j} alone spans U_j is not a tautology; it is equivalent to full rank of the inclusion matrix N_{j,i}. This fact is true under the standing hypothesis i≤n/2 and can be supplied from Gottlieb's theorem, but omitting it leaves a hole in the proof of Proposition 1.6. Since Lemma 2.3 and Corollary 2.4 explicitly invoke Proposition 1.6 to identify W_{y,i}=V_{y,i} and to construct the zonal basis f_{y,i}, the theorem's W_y machinery depends on this step. The proposed test verifies the rank fact; if it holds, the gap is fillable and the verdict should remain conditional rather than become a rejection.","tokens_in":18447,"tokens_out":37852,"duration_ms":342135,"concrete_test":"Check the omitted rank fact directly: for all 1≤j≤i≤n/2, prove that the C(n,j)×C(n,i) inclusion matrix N_{j,i} with entries 1_{z⊆x} has rank C(n,j), e.g., via Gottlieb's theorem or by a triangularization in the Johnson scheme. A minimal concrete instance: for n=5, i=3, j=2, verify that the 10×10 matrix (1_{z⊆x}) is nonsingular. If the rank is full, add the missing argument to §2.1; if deficient, Proposition 1.6's spanning claim and the W_y construction fail.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.1, proof of Proposition 1.6, contains the line 'the functions {g_y}_{|y|=j} span a subspace U_j, which contains V_j' after defining U_j in §1.0.1 as the span of all g_z with |z|≤j. For j<i, {g_y: |y|=j} spans U_j only if the C(n,j)×C(n,i) inclusion matrix N_{j,i} (rows j-subsets, columns i-subsets, entry 1_{z⊆x}) has full row rank. This holds for j≤i≤n/2 (Gottlieb), but it is neither proved nor cited at this point. The subsequent identity V_j=E_j⟨g_y⟩_{|y|=j} and hence the spanning part of Proposition 1.6 depend on it. Proposition 1.6 is the stated basis for Lemma 2.3 and Corollary 2.4, which give W_{y,i}=V_{y,i} and the 1-dimensional zonal spaces used to build W_t(λ). If the rank fact failed, the dimension and multiplicity accounting in Theorem 1.7 would not be justified. The gap is fixable, but it is a real omitted step in the core proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the adjacency matrix of the subgraph of the Hamming cube induced by a Hamming ball, and more generally by a union of adjacent concentric Hamming spheres. The main result (Theorem 1.7) states that every eigenvalue is of the form 2x - (n-2t), where x is a root of a Krawtchouk polynomial of degree r-t+1 on a cube of dimension n-2t, and the multiplicity is the sum of binomial differences (C(n,t)-C(n,t-1)) over all t for which the eigenvalue appears. It also describes the eigenspaces via restrictions to Hamming spheres: a vector in the eigenspace vanishes on inner spheres and its restriction to each outer sphere lies in the t-th eigenspace of that sphere. Corollary 1.8 identifies the maximal eigenvalue as n - 2x, with x the first root of K_{r+1}^{(n)}, and shows the corresponding eigenfunction is positive and spherical. A generalization to unions of concentric spheres is stated as Theorem 1.10. Applications in Section 1.2.2 concern the largest maximal eigenvalue and the smallest fractional edge boundary size among subsets of a fixed cardinality; Corollary 1.15 claims an improved lower bound for all cardinalities and an upper bound for sets of size 2^{n-o(n)} that disproves a conjecture of [17].","tokens_in":18690,"tokens_out":20938,"duration_ms":175023,"significance":"If fully established, the spectral description of Hamming balls is a clean and useful contribution: it links the eigenvalues to Krawtchouk roots in varying dimensions, verifies multiplicities by a dimension count, and gives a concrete description of eigenfunctions in terms of the Johnson scheme. The connection with extremal eigenvalues of large subsets is interesting and would extend prior work of Friedman-Tillich and Bollobas-Lee-Letzter. The paper provides detailed proofs for the core Theorem 1.7, and the main claims are concrete and falsifiable. However, the unproved generalization (Theorem 1.10) and the incomplete proof of the second part of Corollary 1.15 currently reduce confidence in the advertised scope of the results.","major_comments":[{"comment":"Theorem 1.10, which extends the main result to unions of adjacent concentric Hamming spheres, is stated without proof. The sentence \"we present without proof, since the proof of Theorem 1.7 extends essentially verbatim to this setting\" is not a substitute for a proof, particularly because the new matrix family M_t and the parameter t* = max(t, r1) require verification. Since Corollary 1.11 and the incidence-matrix application depend on this theorem, this is a load-bearing omission. The authors should either provide the proof or explicitly mark the result as conjectural and qualify the corollaries that rely on it.","section":"1.1.1 (Theorem 1.10)"},{"comment":"The proof of the second part of Corollary 1.15 is incomplete. It relies on an unspecified function ε(s,n) with the property that if i ≥ (1+ε(s,n))·ln(2^n/s)/2 then x_i ≤ t+1, and states \"it is easy to see\" that such a function exists, without giving the required construction or calculation. Furthermore, the logical step from this threshold to the bound Δ(s) ≤ ln(2^n/s)(1+o(1)) needs a careful monotonicity argument that is not provided. Since this is the basis for the claimed disproof of the conjecture from [17], the proof must be completed.","section":"2.4 (Corollary 1.15, second claim)"},{"comment":"The proof of Proposition 1.6 contains the statement that the functions {g_y}_{|y|=j} span the subspace U_j. This is inaccurate because, by the definition in Section 1.0.1, U_j is the span of all g_z with |z|≤j, so {g_y : |y|=j} spans only a subspace of U_j. The subsequent identity V_j = E_j U_j = E_j ⟨{g_y}⟩_{|y|=j} is nonetheless valid, but only because U_j = U_{j-1} + span{g_y : |y|=j} and E_j annihilates U_{j-1}. The proof should state these facts explicitly; as written, it appears to appeal to an unproved full-rank fact for the inclusion matrix, which is not actually needed. The argument is repairable, but the current wording is misleading.","section":"2.1 (Proposition 1.6)"}],"minor_comments":[{"comment":"The paragraph beginning \"Next, let t1 < t2 with λ ∈ Λ_{t1} and λ ∈ Λ_{t2}\" appears twice almost verbatim; one occurrence should be deleted.","section":"2.2"},{"comment":"The error term from the Levenshtein bounds is written both as O(t^{-1/6}√n) and later as O(√n); clarify which bound is being used at each point and provide the exact equation numbers.","section":"2.4"},{"comment":"The notation for the space U_{y,j} is occasionally written U_{y,i} (e.g., \"Uy,i = Sy,i ∩ ⟨G0, ..., Gj−1⟩⊥\"); the subscripts should be made consistent.","section":"2.1"},{"comment":"The notation O_{r→∞}(r^{-1/6}·√n) is confusing because r is a function of n; consider writing the limit as n→∞ or explicitly stating that r ~ n.","section":"2.4"}],"recommendation":"major_revision","confidential_remarks":"The core Theorem 1.7 appears sound and the approach is promising. However, the manuscript currently states a central generalization without proof and gives an incomplete proof for a headline application. I recommend major revision; the authors should either prove Theorem 1.10 or substantially qualify its status, and they should complete the argument for the second part of Corollary 1.15. The paper should be reconsidered after these points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on Avni–Samorodnitsky (2411.14597). The main result, Theorem 1.7, is the real thing: a complete description of the eigenvalues and eigenspaces of the Hamming ball adjacency matrix in terms of Krawtchouk roots, with a clean multiplicity formula. Corollary 1.8, identifying the maximal eigenvalue as n−2x with x the first root of K_{r+1}^{(n)}, is a sharp and useful statement. The technique of zonal semi-symmetric functions is a good idea, and the proof is worked out in enough detail that I could follow the dimension count.\n\nThe novelty is genuine. [16] only noted that (n−λ)/2 is some Krawtchouk root; nobody had the full spectrum. The extension to unions of concentric spheres (Theorem 1.10) is a nice bonus, though it is stated without proof. The authors say the proof goes over verbatim; a referee should ask them to either include it or spell out the modifications.\n\nNow the soft spots. The second claim of Corollary 1.15, which disproves the [17] conjecture, is the weakest part. The argument uses an unstated ε(s,n) and a bound from [9] with O(t^{−1/6}√n) error, and the step \"there exists ε… so that if i ≥ … then x_i ≤ t+1\" is too compressed. It may be fixable, but as written it is not fully rigorous. The first claim of Corollary 1.15 is fine. Also, the derivation of the bound from [9] is imported; that's acceptable, but the error terms should be tracked carefully.\n\nOne concern that was flagged to me: the proof of Proposition 1.6 supposedly needs a Gottlieb full-rank theorem to show {g_y}_{|y|=j} spans U_j. That worry does not hold up. For |z|<j, g_z on S(n,i) is a constant multiple of the sum of g_y over y⊇z, |y|=j, so the span of the weight-j functions already contains all lower-weight g_z. No full-rank input is needed. So the core proof is cleaner than the stress-test suggests.\n\nVerdict: this deserves a serious referee. The spectral theorem is likely correct and is a meaningful contribution. The application section needs tightening, not reworking. I'd suggest sending to a good combinatorics journal and asking for the proof of Theorem 1.10 and an explicit error analysis in Corollary 1.15.","headline":"A solid, genuinely new spectral theorem for Hamming balls; the headline extremal application is compressed but the core result deserves refereeing.","tokens_in":19260,"tokens_out":6760,"would_cite":true,"duration_ms":57522,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05E30","33C45"],"pacs":[],"model":"deepseek-v4-flash","headline":"The eigenvalues of a Hamming ball's adjacency matrix are exactly the shifted and scaled roots of Krawtchouk polynomials, with explicit multiplicities.","keywords":["Hamming ball","adjacency spectrum","Krawtchouk polynomials","Hamming cube","fractional edge boundary","semi-symmetric functions","Johnson scheme","spectral radius"],"falsifier":"For $n=6$ and $r=2$, diagonalize the $22\\times22$ adjacency matrix of the Hamming ball $B(6,2)$ and compare its eigenvalues and multiplicities with the claimed union of $2R(6,3)-6$, $2R(4,2)-4$, and $2R(2,1)-2$; one mismatched eigenvalue or multiplicity would refute Theorem 1.7.","tokens_in":18230,"feed_emoji":"🧮","tokens_out":14985,"duration_ms":116293,"temperature":0.7,"pith_summary":"The paper establishes a complete spectral theorem for the adjacency matrix of a Hamming ball, and for subgraphs induced by unions of adjacent concentric Hamming spheres. For a ball of radius $r$ in the $n$-cube, every eigenvalue is a shifted and scaled root of a Krawtchouk polynomial: the spectrum is the union over $t=0,\\ldots,r$ of the sets $2\\,R(n-2t,\\,r-t+1)-(n-2t)$, where $R(m,k)$ is the set of roots of the $k$-th Krawtchouk polynomial on $\\{0,1\\}^m$, and the multiplicity of an eigenvalue is the sum of binomial differences over the $t$'s whose sets contain it. The maximal eigenvalue is exactly $n$ minus twice the first root of $K_{r+1}^{(n)}$, with a positive spherical eigenfunction. This sharpens the known comparison between Hamming balls and arbitrary subsets of the cube of the same cardinality, showing that balls keep essentially the largest maximal eigenvalue even for sets of size $2^{n-o(n)}$, and it disproves a conjecture about fractional edge boundary of large sets.","feed_headline":"Hamming-ball spectra pinned to Krawtchouk roots","feed_subtitle":"Every eigenvalue is a shifted Krawtchouk root, settling the spectral-radius question for large subsets of the cube.","key_machinery":"The workhorse is the space $W_y=S_y^{(B)}\\cap\\langle\\{S_z^{(B)}:|z|<|y|\\}\\rangle^{\\perp}$ of semi-symmetric functions on the ball around $y$, together with its one-dimensional layers $V_{y,i}$, the zonal semi-symmetric functions in the $i$-th eigenspace of $S(n,i)$. For fixed $|y|=t$, the adjacency matrix restricted to $W_y$ becomes a $(r-t+1)\\times(r-t+1)$ tridiagonal matrix with explicit off-diagonal entries; a diagonal similarity transform puts it in symmetric Jacobi form, and the resulting characteristic polynomial is a Krawtchouk polynomial $K_{r-t+1}^{(n-2t)}$. Proposition 1.6, which says the zonal semi-symmetric functions around points $y$ of weight $j$ span the sphere eigenspace $V_j$, is what allows the dimension count and the identification of $W_t(\\lambda)$ with $V_t$ of $S(n,t)$.","core_discovery":"The central claim is Theorem 1.7: a real number $\\lambda$ is an eigenvalue of the adjacency matrix $A(n,r)$ of the Hamming ball $B(n,r)$ if and only if $\\lambda$ belongs to the union of $\\Lambda_t=2\\,R(n-2t,\\,r-t+1)-(n-2t)$ over $t=0,\\ldots,r$, with multiplicity $m(\\lambda)=\\sum_{t:\\lambda\\in\\Lambda_t}\\left(\\binom{n}{t}-\\binom{n}{t-1}\\right)$; for each $t$ and each $\\lambda\\in\\Lambda_t$ there is an eigenspace $W_t(\\lambda)$ of dimension $\\binom{n}{t}-\\binom{n}{t-1}$. The eigenspace $W_t(\\lambda)$ vanishes on $B(n,t-1)$, its restriction to each sphere $S(n,i)$ for $t\\le i\\le r$ lies in the $t$-th eigenspace of that sphere, and a function in $W_t(\\lambda)$ is determined by its restriction to $S(n,t)$. Corollary 1.8 identifies the maximal eigenvalue as $\\lambda=n-2x$, where $x$ is the first root of $K_{r+1}^{(n)}$, with multiplicity one and a positive spherical eigenfunction. The same decomposition, via a family of tridiagonal matrices $M_t$, describes the eigenvalues and eigenfunctions of a union of concentric spheres; for two adjacent spheres this yields the full spectrum of the incidence matrix between layers $r-1$ and $r$, with eigenvalues $\\pm\\sqrt{(r-t)(n-r-t+1)}$.","pith_inferences":["The tridiagonal realization of $A$ on $W_y$ looks transferable: any vertex-transitive layered graph whose layers have the same zonal-semi-symmetric spanning property should admit an analogous 'ball spectrum = shifted polynomial roots' statement.","The disproof of the fractional-edge-boundary conjecture suggests that for sets of size $2^{n-o(n)}$ the true minimizer is not a subcube but a Hamming ball of radius about $n/2 - \\sqrt{\\ln(2^n/s)/2}\\,n$; checking this numerically for $n=20,\\ldots,40$ would be a direct test.","The statement that a $W_t(\\lambda)$ eigenfunction is determined by its restriction to $S(n,t)$ gives a canonical coding of ball eigenfunctions by sphere data; this could be useful for quantum walks or mixing times on truncated cubes, where explicit eigenbases are rare."],"forward_implications":["The spectrum and spectral gap of any Hamming-ball subgraph can be read off from Krawtchouk roots, so no numerical matrix diagonalization is needed for these graphs.","The maximal eigenvalue of $B(n,r)$ is $n$ minus twice the first root of $K_{r+1}^{(n)}$; this pins down the value used in linear-programming bounds for binary codes.","For a union of two adjacent Hamming spheres, all nonzero eigenvalues are $\\pm\\sqrt{(r-t)(n-r-t+1)}$ with multiplicity $\\binom{n}{t}-\\binom{n}{t-1}$, plus a zero eigenvalue of multiplicity $\\binom{n}{r}-\\binom{n}{r-1}$; this fully describes the incidence matrix between layers $r-1$ and $r$.","Hamming balls have essentially the largest maximal eigenvalue among all subsets of the cube of the same size even when the size is $2^{n-o(n)}$, so the lower bound on fractional edge boundary of large sets is tight up to a factor tending to 1.","The conjecture that the fractional edge boundary of every set of size $s$ between $2^n/n$ and $2^{n-1}$ is at least $(1-o(1))\\log_2(2^n/s)$ is false; the paper shows $\\Delta(s)\\le \\ln(2^n/s)(1+o(1))$."],"supporting_citations":[{"why":"Supplies the eigenspace decomposition $V_j=U_j\\cap U_{j-1}^\\perp$ of the Hamming sphere and the zonal spherical function facts used in Proposition 1.6.","marker":"[11]"},{"why":"Provides the Krawtchouk polynomials, their recurrence, and the reciprocity relation used to identify eigenvalues and to bound the first root in Corollary 1.15.","marker":"[13]"},{"why":"Gives the standard theorem that the eigenvalues of a symmetric tridiagonal matrix with positive off-diagonal entries are the zeroes of the associated monic orthogonal polynomials, used in Lemma 2.5.","marker":"[3]"},{"why":"Supplies the estimates on the first root of Krawtchouk polynomials that Corollary 1.15 uses to sharpen the spectral bounds.","marker":"[9]"},{"why":"Establishes reality, distinctness, symmetry, and root separation of Krawtchouk roots, used in Theorem 1.7 and Corollary 1.8.","marker":"[18]"},{"why":"Formulates the conjecture about fractional edge boundary of large subsets that Corollary 1.15 disproves.","marker":"[17]"},{"why":"Shows the incidence matrix between layers $r-1$ and $r$ has full rank, the baseline for the complete description in Corollary 1.11.","marker":"[5]"},{"why":"Gives the entropy bound on the size of a Hamming ball used to compare with cardinality $s$ in Corollary 1.15.","marker":"[10]"}],"fun_headline_variants":["Hamming ball spectra: every eigenvalue is a Krawtchouk shift","Exact eigenvalues and eigenspaces for Hamming balls","Krawtchouk roots describe all Hamming ball adjacency spectra","Hamming balls' largest eigenvalue is a Krawtchouk root","Complete spectral picture for Hamming balls and concentric spheres"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof leans on a known decomposition of the Hamming sphere into eigenspaces $V_j=U_j\\cap U_{j-1}^\\perp$ and on Proposition 1.6, which asserts that the semi-symmetric functions around a point $y$ span $V_j$; without that sphere decomposition the invariant subspaces $W_y$ and the entire spectral description do not go through, and the extension in Theorem 1.10 is stated without proof.","fun_headline_variants_meta":{"raw":{"variants":["Hamming ball spectra: every eigenvalue is a Krawtchouk shift","Exact eigenvalues and eigenspaces for Hamming balls","Krawtchouk roots describe all Hamming ball adjacency spectra","Hamming balls' largest eigenvalue is a Krawtchouk root","Complete spectral picture for Hamming balls and concentric spheres"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000704,"raw_usage":{"total_tokens":3187,"prompt_tokens":967,"completion_tokens":2220,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":2133}},"tokens_in":583,"tokens_out":2220,"duration_ms":15745,"temperature":1.0,"reasoning_tokens":2133,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:07:20.443143+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $n=6$ and $r=2$, diagonalize the $22\\times22$ adjacency matrix of the Hamming ball $B(6,2)$ and compare its eigenvalues and multiplicities with the claimed union of $2R(6,3)-6$, $2R(4,2)-4$, and $2R(2,1)-2$; one mismatched eigenvalue or multiplicity would refute Theorem 1.7.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the eigenspace decomposition $V_j=U_j\\cap U_{j-1}^\\perp$ of the Hamming sphere and the zonal spherical function facts used in Proposition 1.6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Krawtchouk polynomials, their recurrence, and the reciprocity relation used to identify eigenvalues and to bound the first root in Corollary 1.15."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the standard theorem that the eigenvalues of a symmetric tridiagonal matrix with positive off-diagonal entries are the zeroes of the associated monic orthogonal polynomials, used in Lemma 2.5."},{"cited_title":"Handbook of Coding The- ory","cited_arxiv_id":null,"evidence_quote":"Supplies the estimates on the first root of Krawtchouk polynomials that Corollary 1.15 uses to sharpen the spectral bounds."},{"cited_title":"Szego, Orthogonal Polynomials , Amer","cited_arxiv_id":null,"evidence_quote":"Establishes reality, distinctness, symmetry, and root separation of Krawtchouk roots, used in Theorem 1.7 and Corollary 1.8."},{"cited_title":"Samorodnitsky, Faber-Krahn for large subsets of the boolean cube , preprint (2017)","cited_arxiv_id":null,"evidence_quote":"Formulates the conjecture about fractional edge boundary of large subsets that Corollary 1.15 disproves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows the incidence matrix between layers $r-1$ and $r$ has full rank, the baseline for the complete description in Corollary 1.11."},{"cited_title":"van Lint, Introduction to Coding Theory , third edition, Graduate Texts in Math- ematics, vol","cited_arxiv_id":null,"evidence_quote":"Gives the entropy bound on the size of a Hamming ball used to compare with cardinality $s$ in Corollary 1.15."}],"review_version":1}