Linear Algebraic Method and the Erd\H{o}s-Heilbronn Conjecture

Guanzhong Yang

arxiv: 2605.19542 · v1 · pith:66IAQ6ZSnew · submitted 2026-05-19 · 🧮 math.CO · math.RA

Linear Algebraic Method and the ErdH{o}s-Heilbronn Conjecture

Guanzhong Yang This is my paper

Pith reviewed 2026-05-20 04:04 UTC · model grok-4.3

classification 🧮 math.CO math.RA

keywords restricted sumsetsErdős-Heilbronn conjectureAlon-Nathanson-Ruzsa theoremlinear algebrafinite fieldsVandermonde matricesadditive combinatorics

0 comments

The pith

A linear algebraic method using Vandermonde matrices gives an elementary proof of the Alon-Nathanson-Ruzsa theorem for restricted sumsets, which implies the Erdős-Heilbronn conjecture.

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

The paper develops Das's linear algebraic method to establish lower bounds on the sizes of restricted sumsets over finite fields. It constructs linear systems tied to these sumsets and proves they are solvable precisely when the sets meet the size threshold predicted by the Alon-Nathanson-Ruzsa theorem. This yields a new proof that relies only on basic linear algebra, including the ranks of Vandermonde-like matrices, rather than polynomial methods. Because the theorem implies the Erdős-Heilbronn conjecture, the work supplies an elementary route to one of the central results in additive combinatorics over finite fields.

Core claim

By building linear systems from the elements of a restricted sumset and showing that these systems admit solutions exactly when the sumset reaches the minimal size given by the theorem, the author proves the Alon-Nathanson-Ruzsa result for restricted sums in prime fields. The solvability hinges on the full rank of certain Vandermonde-like matrices over the finite field. This argument directly implies the Erdős-Heilbronn conjecture as a corollary.

What carries the argument

Das's linear algebraic method, which encodes the restricted sumset as a linear system over a finite field and determines solvability from the rank of the associated Vandermonde-like matrix.

If this is right

The Erdős-Heilbronn conjecture holds for restricted sumsets in finite fields of prime order.
The Alon-Nathanson-Ruzsa lower bound on restricted sumset size follows from the solvability of the constructed linear systems.
Proofs of similar sumset results can be carried out with only elementary linear algebra over finite fields instead of the Combinatorial Nullstellensatz.
The rank properties of Vandermonde-like matrices determine the minimal size of restricted sums in this setting.

Where Pith is reading between the lines

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

The same linear-system construction might adapt to prove analogous bounds for sumsets with other restrictions, such as arithmetic-progression-free sums.
Matrix-rank arguments could replace polynomial techniques in additional problems from additive combinatorics where explicit bases are available.
Direct computation of the relevant matrix ranks for small fields would give explicit constants and tightness examples beyond the asymptotic statements.

Load-bearing premise

The linear systems built from the restricted sumset have solutions if and only if the sumset meets the size lower bound claimed by the theorem.

What would settle it

For a small prime field and explicit sets A and B, compute the restricted sumset size and check whether the corresponding linear system has a solution precisely when the size meets the Alon-Nathanson-Ruzsa bound; a mismatch would refute the central argument.

read the original abstract

Additive combinatorics asks for lower bounds on sumsets and restricted sumsets over finite fields. Central examples are the Cauchy-Davenport theorem and the Erd\H{o}s-Heilbronn conjecture. In this note, we develop Das's linear algebraic method and give a new elementary proof of the Alon-Nathanson-Ruzsa theorem for restricted sumsets, which implies the Erd\H{o}s-Heilbronn conjecture. Compared with the classical polynomial method via Combinatorial Nullstellensatz, our proof uses only basic linear algebra over finite fields, including Vandermonde matrices and solvability of linear systems.

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.

Desk Editor's Note private letter to a colleague

Yang has produced a linear algebraic proof of the Alon-Nathanson-Ruzsa theorem that sidesteps the usual polynomial approach.

read the letter

Colleague, The main point to know is that this paper supplies a linear-algebraic proof of the Alon-Nathanson-Ruzsa theorem for restricted sumsets, which is already known but here derived without the Combinatorial Nullstellensatz. It uses Das's method with Vandermonde-like matrices and checks solvability of linear systems over finite fields to get the size lower bound, implying the Erdős-Heilbronn conjecture. What it does well is stick to basic linear algebra. The approach is direct, with no invented entities or free parameters, and the argument flows from the rank properties matching the combinatorial bounds. This is a clean alternative technique in the program of sumset estimates, and the outline looks coherent. The soft spots are limited. The central assumption about the linear systems being solvable precisely when the bound holds is standard, but one would want to see the explicit rank calculations in the full text to confirm they hold for all finite fields and set sizes. From the summary and stress-test, though, there is no sign of circularity or unsupported steps. It's proportionate to call this a solid but not deep advance. This kind of paper is for people in additive combinatorics who follow proofs of these classical results and might appreciate seeing the linear algebra method extended. A reader interested in elementary methods or teaching these theorems could get value from the different perspective. It deserves serious referee time because the work is formally grounded in standard tools and engages honestly with the existing literature on the conjecture. Best regards,

Referee Report

0 major / 2 minor

Summary. The manuscript develops Das's linear algebraic method to give a new elementary proof of the Alon-Nathanson-Ruzsa theorem on restricted sumsets over finite fields. The argument constructs a linear system whose solvability is tied to the size of the restricted sumset, using rank properties of Vandermonde-like matrices, and deduces the Erdős-Heilbronn conjecture as a corollary. The approach relies only on basic linear algebra over finite fields and avoids the Combinatorial Nullstellensatz.

Significance. If the verification of the matrix ranks and system solvability holds for arbitrary finite fields and set sizes, the paper supplies an accessible alternative proof of a known result in additive combinatorics. This strengthens the case for linear-algebraic techniques in the area and may facilitate extensions to other sumset problems.

minor comments (2)

[Abstract and §1] The abstract and introduction could include a short explicit statement of the precise bound obtained by the Alon-Nathanson-Ruzsa theorem to help readers compare it immediately with the classical Cauchy-Davenport bound.
[§2] Notation for the restricted sumset A ⊕ A should be defined once at the beginning of the main argument and used consistently thereafter.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and the recommendation to accept. The provided summary accurately reflects our development of Das's linear algebraic method and its application to the Alon-Nathanson-Ruzsa theorem.

Circularity Check

0 steps flagged

No significant circularity in the linear algebraic proof

full rationale

The paper develops Das's linear algebraic method to give a new elementary proof of the known Alon-Nathanson-Ruzsa theorem on restricted sumsets (which implies the Erdős-Heilbronn conjecture) using only basic linear algebra over finite fields, Vandermonde matrices, and solvability of linear systems. The derivation constructs linear systems from the restricted sumset and appeals to rank properties of associated matrices; these steps are standard, internally consistent, and do not reduce by definition or self-citation to the target bound. No fitted parameters are renamed as predictions, no uniqueness is imported via self-citation chains, and the central claim retains independent content from the linear-algebraic construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on standard facts about finite fields and linear algebra; no new entities or fitted constants are introduced.

axioms (2)

standard math Vandermonde matrices over finite fields have full rank when the points are distinct.
Invoked to guarantee solvability of the constructed linear systems.
standard math Linear systems over finite fields are solvable when the coefficient matrix has full column rank.
Central to showing the existence of the required polynomials or functions.

pith-pipeline@v0.9.0 · 5624 in / 1219 out tokens · 41008 ms · 2026-05-20T04:04:22.980544+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We develop Das's linear algebraic method... Vandermonde matrices and solvability of linear systems
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

eA(w) ≤ |A|−1 via contradiction on det(M) ≠ 0

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[1]

Alon,Combinatorial Nullstellensatz, Combin

N. Alon,Combinatorial Nullstellensatz, Combin. Probab. Comput.8(1999), 7–29

work page 1999
[2]

N. Alon, M. B. Nathanson, and I. Z. Ruzsa,Adding Distinct Congruence Classes Modulo a Prime, Amer. Math. Monthly102(1995), 250–255

work page 1995
[3]

Das,Value Sets of Polynomials and the Cauchy-Davenport Theorem, Finite Fields Appl.10(2004), 113–122

P. Das,Value Sets of Polynomials and the Cauchy-Davenport Theorem, Finite Fields Appl.10(2004), 113–122

work page 2004
[4]

J. A. Dias da Silva and Y. O. Hamidoune,Cyclic Spaces for Grassmann Deriva- tives and Additive Theory, Bull. Lond. Math. Soc.26(1994), 140–146

work page 1994
[5]

Erd˝ os and H

P. Erd˝ os and H. Heilbronn,On the Addition of Residue Classes Modulop, Acta Arith.9(1964), 149–159. 10 GUANZHONG YANG

work page 1964
[6]

Tao,An Uncertainty Principle for Cyclic Groups of Prime Order, Math

T. Tao,An Uncertainty Principle for Cyclic Groups of Prime Order, Math. Res. Lett.12(2005), 121–127

work page 2005
[7]

Tao and V

T. Tao and V. H. Vu,Additive Combinatorics, Cambridge Univ. Press, Cam- bridge, 2006. Department of Mathematics, Imperial College London, UK Email address:gy625@ic.ac.uk

work page 2006

[1] [1]

Alon,Combinatorial Nullstellensatz, Combin

N. Alon,Combinatorial Nullstellensatz, Combin. Probab. Comput.8(1999), 7–29

work page 1999

[2] [2]

N. Alon, M. B. Nathanson, and I. Z. Ruzsa,Adding Distinct Congruence Classes Modulo a Prime, Amer. Math. Monthly102(1995), 250–255

work page 1995

[3] [3]

Das,Value Sets of Polynomials and the Cauchy-Davenport Theorem, Finite Fields Appl.10(2004), 113–122

P. Das,Value Sets of Polynomials and the Cauchy-Davenport Theorem, Finite Fields Appl.10(2004), 113–122

work page 2004

[4] [4]

J. A. Dias da Silva and Y. O. Hamidoune,Cyclic Spaces for Grassmann Deriva- tives and Additive Theory, Bull. Lond. Math. Soc.26(1994), 140–146

work page 1994

[5] [5]

Erd˝ os and H

P. Erd˝ os and H. Heilbronn,On the Addition of Residue Classes Modulop, Acta Arith.9(1964), 149–159. 10 GUANZHONG YANG

work page 1964

[6] [6]

Tao,An Uncertainty Principle for Cyclic Groups of Prime Order, Math

T. Tao,An Uncertainty Principle for Cyclic Groups of Prime Order, Math. Res. Lett.12(2005), 121–127

work page 2005

[7] [7]

Tao and V

T. Tao and V. H. Vu,Additive Combinatorics, Cambridge Univ. Press, Cam- bridge, 2006. Department of Mathematics, Imperial College London, UK Email address:gy625@ic.ac.uk

work page 2006