Eigenvalues and eigenfunctions of a Hamming ball

Alex Samorodnitsky; Amit Avni

REVIEW 3 major objections 4 minor 18 references

Eigenvalues and eigenfunctions of a Hamming ball

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The eigenvalues of a Hamming ball's adjacency matrix are exactly the shifted and scaled roots of Krawtchouk polynomials, with explicit multiplicities.

desk verdict A solid, genuinely new spectral theorem for Hamming balls; the headline extremal application is compressed but the core result deserves refereeing. read the letter →

arxiv 2411.14597 v1 pith:AJE2SBJ5 submitted 2024-11-21 math.CO

Amit Avni , Alex Samorodnitsky This is my paper · ORCID

classification math.CO MSC 05C5005E3033C45

keywords HammingballadjacencyspectrumKrawtchoukpolynomialscubefractionaledgeboundarysemi-symmetricfunctionsJohnsonschemespectralradius

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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)$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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)}$.

Load-bearing premise

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.

Editorial extensions

If this is right

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))$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

Now 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.

One 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|

Verdict: 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.

Referee Report

3 major / 4 minor

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].

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 (3)

[1.1.1 (Theorem 1.10)] 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.
[2.4 (Corollary 1.15, second claim)] 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.
[2.1 (Proposition 1.6)] 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.

minor comments (4)

[2.2] The paragraph beginning "Next, let t1 < t2 with λ ∈ Λ_{t1} and λ ∈ Λ_{t2}" appears twice almost verbatim; one occurrence should be deleted.
[2.4] 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.
[2.1] 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.
[2.4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the spectral description is derived from an explicit tridiagonal reduction, not from a fitted or self-referential input.

full rationale

The derivation chain is self-contained relative to standard external facts. Theorem 1.7 is proved by constructing A-invariant spaces W_y (Definition 2.2 and Corollary 2.4) and showing that the restriction A_y is a symmetric tridiagonal matrix whose characteristic polynomial is, after a diagonal similarity, exactly the Krawtchouk recurrence (Lemma 2.5). This is a genuine reduction: the sets Lambda_t are not defined as eigenvalues of A; the Krawtchouk roots enter only through the standard three-term recurrence. Proposition 1.6 uses the Johnson-scheme decomposition U_j and the spanning property of {g_y}_{|y|=j} as a known association-scheme fact from Section 1.0.1, following [11]; this is an external ingredient, not an assumption of the theorem being proved. The prior observation [16], by one of the authors, that (n-lambda)/2 lies among Krawtchouk roots is used only as motivation; Corollary 1.8 proves the sharper first-root statement and identifies the positive spherical eigenfunction. The other self-citations ([15], [17]) supply context, bounds, or a conjecture to be disproved, not load-bearing premises. There are no fitted parameters, no self-referential normalizations, and no prediction that is a renamed input. The only concern one might raise is that the spanning/full-rank fact underlying U_j = span{g_y : |y|=j} could be stated with an explicit citation, but omitting that proof is a completeness/correctness gap, not circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters are fitted; this is pure mathematics with no data. The axioms are standard external theory, with the sole exception of the Levenshtein root bounds, which enter as unproved imported estimates.

assumptions (7)

standard math Hamming sphere S(n,i) has eigenspaces V_j = U_j intersect U_{j-1}^perp spanned by restrictions of {g_z}, with dim V_j = C(n,j) - C(n,j-1)
Cited from [11] (van Lint-Wilson, Example 30.7) and used in Section 1.0.1 and in the proof of Proposition 1.6.
standard math Krawtchouk polynomials are orthogonal with respect to the binomial measure, all roots are real, distinct, in (0,n), and symmetric about n/2
Cited from [18] (Szego); used in Theorem 1.7 and Corollary 1.8.
standard math Krawtchouk recurrence k K_k(x) = (N-2x) K_{k-1}(x) - (N-k+2) K_{k-2}(x), with monic normalization P_k = k! / (-2)^k times K_k
Cited from [13]; used in Lemma 2.5 to identify spectra of the tridiagonal matrices.
standard math Eigenvalues of a symmetric tridiagonal matrix with recurrence coefficients are the roots of the m-th orthogonal polynomial (Chihara, Ex. 5.7)
Cited from [3]; used in Lemma 2.5.
standard math Perron-Frobenius theorem: the adjacency matrix of a connected graph has a unique maximal eigenvalue with a strictly positive eigenvector
Used in the proof of Corollary 1.8; standard result.
domain assumption Levenshtein's bounds (5.36) and (5.44) on the first root of Krawtchouk polynomials
Imported from [9]; unproved in this paper, drives Corollary 1.15.
standard math Root interlacing and integer-point property of Krawtchouk roots, and reciprocity (n choose j) K_i(j) = (n choose i) K_j(i)
Cited from [18,13]; used in the proof of the second claim of Corollary 1.15.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Eigenvalues and eigenfunctions of a Hamming ball." pith.science (2026). https://pith.science/paper/AJE2SBJ5

@misc{pith2026241114597,
  author       = {Pith},
  title        = {Pith review of: Eigenvalues and eigenfunctions of a Hamming ball},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AJE2SBJ5}},
  note         = {Machine review of arXiv:2411.14597}
}

read the original abstract

We describe the eigenvalues and the eigenspaces of the adjacency matrices of subgraphs of the Hamming cube induced by Hamming balls, and more generally, by a union of adjacent concentric Hamming spheres. As a corollary, we extend the range of cardinalities of subsets of the Hamming cube for which Hamming balls have essentially the largest maximal eigenvalue (among all subsets of the same size). We show that this holds even when the sets in question are large, with cardinality which is an arbitrary subconstant fraction of the whole cube.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[16]

One more proof of the first linear programming bound for binary codes and two conjectures

A. Samorodnitsky, One more proof of the ﬁrst linear programming bound for binar y codes and two conjectures , arXiv:2104.14587, 2021

work page Pith review arXiv 2021
[17]

Samorodnitsky, Faber-Krahn for large subsets of the boolean cube , preprint (2017)

A. Samorodnitsky, Faber-Krahn for large subsets of the boolean cube , preprint (2017)

work page 2017
[9]

Handbook of Coding The- ory

V. I. Levenshtein, Universal bounds for codes and designs , in “Handbook of Coding The- ory” (V. S. Pless and W. C. Huﬀman, Eds.), Elsevier, Amsterdam , 1998

work page 1998
[1]

Brouwer, Cohen, Neumaier, Distance-Regular graphs

work page
[2]

Bollobas, J

B. Bollobas, J. Lee, and S. Letzter, Eigenvalues of subgraphs of the cube , European J. of Combinatorics, 70, 2018, pp. 125-148

work page 2018
[3]

T. S. Chihara, An introduction to orthogonal polynomials

work page
[4]

Friedman and J-P

J. Friedman and J-P. Tillich, Generalized Alon-Boppana theorems and error-correcting codes, SIAM J. Discrete Math., 19(3) (electronic), 2005, pp. 700- 718

work page 2005
[5]

D. H. Gottlieb, A Certain Class of Incidence Matrices , Proceedings of the American Math- ematical Society, 17(6), 1966, pp. 1233–1237

work page 1966

Show all 18 references

[6]

Gross, Logarithmic Sobolev inequalities , Amer

L. Gross, Logarithmic Sobolev inequalities , Amer. J. of Math., 97, 1975, pp. 1061-1083

1975
[7]

L. H. Harper, Optimal numberings and isoperimetric problems on graphs , J. Combin. Theory, 1, 1966, pp. 385-393

1966
[8]

Hart, A note on the edges of the n-cube , Discr

S. Hart, A note on the edges of the n-cube , Discr. Math., 14, 1976, pp. 157-163

1976
[10]

van Lint, Introduction to Coding Theory , third edition, Graduate Texts in Math- ematics, vol

J.H. van Lint, Introduction to Coding Theory , third edition, Graduate Texts in Math- ematics, vol. 86, Springer-Verlag, Berlin, 1999

1999
[11]

J. H. van Lint, R. M. Wilson, A course in Combinatorics , second edition
[12]

W. J. Martin, H. Tanaka, Commutative association schemes , European J. of Combina- torics, 30, 6, 2009, pp. 1497-1525

2009
[13]

R. J. McEliece, E. R. Rodemich, H. Rumsey, Jr., and L. R. W elch, New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitie s, IEEE Trans. Inform. Theory, vol. 23, 1977, pp. 157-166

1977
[14]

O’Donnel, Analysis of Boolean functions , Cambridge University Press, 2014

R. O’Donnel, Analysis of Boolean functions , Cambridge University Press, 2014

2014
[15]

Samorodnitsky, A modiﬁed logarithmic Sobolev inequality for the Hamming cu be and some applications , arXiv:0807.1679 (2008)

A. Samorodnitsky, A modiﬁed logarithmic Sobolev inequality for the Hamming cu be and some applications , arXiv:0807.1679 (2008)

2008 arXiv
[18]

Szego, Orthogonal Polynomials , Amer

G. Szego, Orthogonal Polynomials , Amer. Math. Soc., Providence, 1939. 20

1939

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [16]

One more proof of the first linear programming bound for binary codes and two conjectures

A. Samorodnitsky, One more proof of the ﬁrst linear programming bound for binar y codes and two conjectures , arXiv:2104.14587, 2021

work page Pith review arXiv 2021

[2] [17]

Samorodnitsky, Faber-Krahn for large subsets of the boolean cube , preprint (2017)

A. Samorodnitsky, Faber-Krahn for large subsets of the boolean cube , preprint (2017)

work page 2017

[3] [9]

Handbook of Coding The- ory

V. I. Levenshtein, Universal bounds for codes and designs , in “Handbook of Coding The- ory” (V. S. Pless and W. C. Huﬀman, Eds.), Elsevier, Amsterdam , 1998

work page 1998

[4] [1]

Brouwer, Cohen, Neumaier, Distance-Regular graphs

work page

[5] [2]

Bollobas, J

B. Bollobas, J. Lee, and S. Letzter, Eigenvalues of subgraphs of the cube , European J. of Combinatorics, 70, 2018, pp. 125-148

work page 2018

[6] [3]

T. S. Chihara, An introduction to orthogonal polynomials

work page

[7] [4]

Friedman and J-P

J. Friedman and J-P. Tillich, Generalized Alon-Boppana theorems and error-correcting codes, SIAM J. Discrete Math., 19(3) (electronic), 2005, pp. 700- 718

work page 2005

[8] [5]

D. H. Gottlieb, A Certain Class of Incidence Matrices , Proceedings of the American Math- ematical Society, 17(6), 1966, pp. 1233–1237

work page 1966