pith. sign in

arxiv: 2606.24624 · v1 · pith:2LIGJ7LInew · submitted 2026-06-23 · 🧮 math.CO · cs.IT· math.IT

An eigenvalue proof of Heged\"{u}s's bound for codes with a single Hamming distance

Scott Duke Kominers This is my paper

Pith reviewed 2026-06-25 23:04 UTC · model grok-4.3

classification 🧮 math.CO cs.ITmath.IT
keywords Hamming distanceconstant-distance codesGram matrixeigenvaluessubset familieslinear algebra boundbinary codesq-ary codes
0
0 comments X

The pith

If all pairwise Hamming distances equal a fixed λ not equal to (n+1)/2, a family of subsets of an n-set has size at most n.

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

The paper supplies a short linear-algebra proof of the bound that any collection of subsets of {1,…,n} with all pairwise Hamming distances equal to the same λ ≠ (n+1)/2 has at most n members. It forms the Gram matrix from the characteristic vectors of the subsets and extracts its eigenvalues directly from the single observation that those vectors share a common norm and common pairwise inner products. The resulting spectral information forces linear dependence once more than n vectors are present. The same fact immediately yields the corrected q-ary bound of n(q−1) when the distance avoids the analogous midpoint. A reader would care because the argument replaces an explicit determinant computation with a transparent eigenvalue reading that works verbatim over larger alphabets.

Core claim

When the characteristic vectors of the subsets all have equal norm and equal pairwise inner products (corresponding to constant Hamming distance λ ≠ (n+1)/2), the Gram matrix they generate has eigenvalues that are completely determined by those two equalities; the multiplicity of the zero eigenvalue then implies that the vectors become linearly dependent as soon as their number exceeds n, so the family cannot contain more than n subsets.

What carries the argument

The Gram matrix of the characteristic vectors, whose eigenvalues are fixed solely by the common norm and common pairwise inner products of the vectors.

If this is right

  • Any such constant-distance family is linearly dependent once its size exceeds n.
  • The same eigenvalue extraction yields the bound n(q−1) for constant-distance codes over an alphabet of size q when λ avoids ((q−1)n+1)/q.
  • The argument requires no determinant calculation and applies verbatim once the equal-norm and equal-inner-product condition is verified.
  • When λ equals the excluded midpoint value, the spectral obstruction disappears and larger families become possible.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same spectral shortcut may shorten other proofs in extremal set theory that currently compute determinants of Gram matrices arising from constant inner-product conditions.
  • Problems involving nearly constant distances could be tested for whether a small perturbation still pins the eigenvalues tightly enough to enforce a linear-dependence bound.
  • The method separates the algebraic fact about equal-norm equal-inner-product vectors from the combinatorial details of the ground set, suggesting it can be reused for other distance-regular settings.

Load-bearing premise

The eigenvalues of the Gram matrix are completely determined by the vectors having equal norms and equal pairwise inner products.

What would settle it

An explicit collection of n+1 subsets of {1,…,n} whose pairwise Hamming distances are all equal to some fixed λ not equal to (n+1)/2.

read the original abstract

We give a short, self-contained linear-algebra proof of a bound of Heged\"{u}s [Australasian Journal of Combinatorics, 2026; arXiv:2409.07877]: if all pairwise Hamming distances in a family of subsets of $\{1,\ldots,n\}$ equal a fixed value $\lambda\ne(n+1)/2$, then the family has at most $n$ members. Our proof uses the same Gram matrix as in Heged\"{u}s's argument, but reads its eigenvalues in place of its determinant, and keys off of a single fact about vectors of equal norm and equal pairwise inner product. That fact applies verbatim over an alphabet of size $q$, where it yields the bound $n(q-1)$ for $\lambda\ne\bigl((q-1)n+1\bigr)/q$ -- the corrected form of a conjecture of Heged\"{u}s, recently established by Hu, Huang, and Yu [arXiv:2504.07036].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to provide a short, self-contained linear-algebra proof of Hegedüs's bound: if all pairwise Hamming distances in a family of subsets of {1,…,n} equal a fixed λ ≠ (n+1)/2, then the family has size at most n. The proof reuses the Gram matrix of characteristic vectors from Hegedüs's argument but extracts its eigenvalues (rather than the determinant) from the single fact that equal-norm, equal-inner-product vectors yield a Gram matrix with explicitly known eigenvalues; the same approach is said to yield the bound n(q−1) over an alphabet of size q when λ ≠ ((q−1)n + 1)/q.

Significance. If the argument is complete, the eigenvalue reading supplies a noticeably shorter and more transparent derivation than the original determinant computation while simultaneously correcting and extending a conjecture to the q-ary setting. The approach relies only on standard facts about Gram matrices and therefore strengthens the linear-algebra toolkit available for constant-distance problems.

major comments (1)
  1. [Abstract, paragraph 2] Abstract, paragraph 2: the eigenvalue fact is stated to apply verbatim to vectors of equal norm and equal pairwise inner products. From the Hamming-distance hypothesis d(v_i,v_j)=λ one obtains ⟨v_i,v_j⟩=(‖v_i‖² + ‖v_j‖² − λ)/2, which is constant for i≠j only when all ‖v_i‖² are identical. The manuscript gives no indication of a preliminary argument establishing that all sets have the same cardinality, so the off-diagonal entries of the Gram matrix need not be constant and the cited eigenvalue fact does not apply directly. This step is load-bearing for the central claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying this important point. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract, paragraph 2] Abstract, paragraph 2: the eigenvalue fact is stated to apply verbatim to vectors of equal norm and equal pairwise inner products. From the Hamming-distance hypothesis d(v_i,v_j)=λ one obtains ⟨v_i,v_j⟩=(‖v_i‖² + ‖v_j‖² − λ)/2, which is constant for i≠j only when all ‖v_i‖² are identical. The manuscript gives no indication of a preliminary argument establishing that all sets have the same cardinality, so the off-diagonal entries of the Gram matrix need not be constant and the cited eigenvalue fact does not apply directly. This step is load-bearing for the central claim.

    Authors: We agree that the eigenvalue fact requires the characteristic vectors to have equal norms in order for the off-diagonal Gram entries to be constant. The manuscript does not explicitly supply a preliminary argument establishing equal cardinalities. We will revise the manuscript to include a short preliminary lemma proving that any family with constant pairwise Hamming distance λ must have all sets of equal cardinality whenever λ ≠ (n+1)/2. With this addition the cited eigenvalue fact applies directly and the remainder of the argument is unchanged. revision: yes

Circularity Check

0 steps flagged

No circularity; self-contained linear-algebra argument on standard Gram-matrix facts

full rationale

The derivation uses the Gram matrix of characteristic vectors of the subsets and invokes only the standard eigenvalue fact for equal-norm, equal-inner-product vectors (a basic result from linear algebra, independent of the target bound). The abstract and setup explicitly frame the argument as self-contained and reading eigenvalues in place of the determinant from the cited prior work; no parameter is fitted to data and then renamed a prediction, no self-citation chain justifies the central uniqueness or eigenvalue claim, and the single-distance hypothesis is converted into the equal-norm/equal-inner-product premise via the paper's own equations rather than by definition or smuggling. The result is therefore not equivalent to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The argument rests on one standard linear-algebra fact about vectors of equal norm and equal pairwise inner products; no free parameters or new entities are introduced.

axioms (1)
  • standard math Vectors of equal norm and equal pairwise inner products satisfy a fixed linear dependence relation that determines the eigenvalues of their Gram matrix.
    Invoked to read eigenvalues directly instead of computing the determinant (abstract, paragraph 2).

pith-pipeline@v0.9.1-grok · 5716 in / 1178 out tokens · 26591 ms · 2026-06-25T23:04:48.434958+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. An Explication of Optimal Equidistant Codes

    math.CO 2026-06 unverdicted novelty 3.0

    An expository paper that unifies prior results on equidistant binary codes and identifies a missed subcase in published characterizations for n ≡ 2 mod 4.

Reference graph

Works this paper leans on

7 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    2.2.1, 2024

    László Babai and Péter Frankl,Linear Algebra Methods in Combinatorics, manuscript, v. 2.2.1, 2024

    2024

  2. [2]

    Wilson,A new proof of several inequal- ities on codes and sets, J

    László Babai, Hunter Snevily, and Richard M. Wilson,A new proof of several inequal- ities on codes and sets, J. Combin. Theory Ser. A71(1995), no. 1, 146–153

    1995

  3. [3]

    Delsarte,An algebraic approach to the association schemes of coding theory, Philips Res

    P. Delsarte,An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl.10(1973), 1–97

    1973

  4. [4]

    Gábor Hegedüs,A new upper bound for codes with a single Hamming distance, Aus- tralas. J. Combin.94(2026), no. 2, 300–304

    2026

  5. [5]

    Sihuang Hu, Hexiang Huang, and Wei-Hsuan Yu,Hegedüs’ conjecture and tighter upper bounds for equidistant codes in Hamming spaces, preprint, arXiv:2504.07036, 2025

    work page arXiv 2025

  6. [6]

    Stasys Jukna,Extremal Combinatorics: With Applications in Computer Science, 2nd ed., Texts in Theoretical Computer Science, Springer, Berlin, 2011

    2011

  7. [7]

    Mag.34(1867), no

    J.J.Sylvester,Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers, Phil. Mag.34(1867), no. 232, 461– 475. Har v ard Business School; Department of Economics and Center of Math- ematical Sciences and Appl...