Linear equations and chromatic thresholds in $B_h$ sets

Nathan Tung

arxiv: 2606.30767 · v2 · pith:TTJT425Cnew · submitted 2026-06-29 · 🧮 math.CO · math.NT

Linear equations and chromatic thresholds in B_h sets

Nathan Tung This is my paper

Pith reviewed 2026-07-03 22:22 UTC · model grok-4.3

classification 🧮 math.CO math.NT

keywords B_h setsSidon setslinear equationschromatic numberFourier pseudorandomnessRoth theoremadditive combinatorics

0 comments

The pith

A B_h set without pairwise distinct solutions to a linear equation with more than 2h variables must be smaller by a constant factor than the largest known B_h sets.

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

The paper establishes that B_h sets of near-maximum size must contain solutions to linear equations with more than 2h variables, extending Roth-type theorems to this sparse setting. A key step shows that the largest B_h sets are Fourier pseudorandom, which transfers dense results to the sparse case. For Sidon sets, avoiding non-translation-invariant equations with zero-sum subcollections of five or more coefficients forces either a very small set or a Cayley graph of bounded chromatic number. Constructions demonstrate large Sidon sets that avoid equations with four-coefficient zero-sums yet produce graphs of unbounded chromatic number.

Core claim

If a B_h set is free of pairwise distinct solutions to a linear equation with more than 2h variables then it must be a constant factor smaller than the best-known upper bound on the size of any B_h set. Extremal B_h sets are Fourier pseudorandom. If the forbidden equation has a certain subdivision structure, an asymptotic saving is obtained. For Sidon sets, forbidding a non-translation-invariant equation with a zero-sum subcollection of at least five coefficients implies the set is either very small or generates a Cayley graph with bounded chromatic number.

What carries the argument

Fourier pseudorandomness of extremal B_h sets, which serves as the input that transfers dense Roth-type results into the sparse B_h setting.

If this is right

Large B_h sets must contain solutions to many linear equations with more than 2h variables.
When the equation has a subdivision structure, the size bound improves to an asymptotic saving.
Sidon sets avoiding equations with zero-sum subcollections of five or more coefficients are either small or generate bounded-chromatic-number Cayley graphs.
Sidon sets avoiding only equations with four-coefficient zero-sums can still be large and generate unbounded-chromatic-number Cayley graphs.

Where Pith is reading between the lines

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

The pseudorandomness property may allow similar transfers for other additive-combinatorial statements beyond linear equations.
Chromatic-threshold characterizations could extend from Sidon sets to general B_h sets.

Load-bearing premise

Extremal B_h sets are Fourier pseudorandom.

What would settle it

An explicit construction of a B_h set that reaches within a constant factor of the maximum size while avoiding all pairwise distinct solutions to some linear equation with more than 2h variables.

read the original abstract

We derive sparse analogs of several Roth-type results, showing that they hold in $B_h$ sets of near-maximum size. It is shown that if a $B_h$ set is free of pairwise distinct solutions to a linear equation with more than $2h$ variables then it must be a constant factor smaller than the best-known upper bound on the size of any $B_h$ set. As a key input, it is established that extremal $B_h$ sets are Fourier pseudorandom. If the forbidden equation has a certain subdivision structure, an asymptotic saving is obtained. The case of Sidon sets ($h=2$) was previously studied by Conlon, Fox, Sudakov, and Zhao as well as Prendiville. When forbidding a non-translation-invariant equation $E$ from a Sidon set, it is shown that if $E$ has a zero-sum subcollection of at least five coefficients then the Sidon set must either be very small or generate a Cayley graph with bounded chromatic number. On the other hand, large Sidon sets are constructed that generate Cayley graphs with unbounded chromatic number and are also free of multiple equations with zero-sum subcollections of four coefficients. This can be viewed as a sparse analog of a result of Liu, Wu, Yang, and Zhang characterizing linear equations with vanishing chromatic threshold.

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

Extends the Sidon-set Roth analogs to general B_h sets by proving extremal ones are Fourier pseudorandom, plus some new chromatic constructions for non-invariant equations.

read the letter

The main advance is carrying the Conlon-Fox-Sudakov-Zhao and Prendiville results on Sidon sets over to B_h sets for general h. They show that a near-maximal B_h set without distinct solutions to a linear equation with more than 2h variables must be smaller than the known upper bound by a constant factor. The key step is establishing that those extremal B_h sets are Fourier pseudorandom, which then feeds the counting argument. For the chromatic side they give both a saving when the equation has a certain subdivision structure and explicit constructions of large Sidon sets whose Cayley graphs have unbounded chromatic number while avoiding equations with zero-sum subcollections of four coefficients.

The pseudorandomness claim is the technical heart and appears to be handled directly rather than assumed. The constructions for the chromatic thresholds look like the right sparse analog of the Liu-Wu-Yang-Zhang work. Citations track the relevant prior results without padding.

The main soft spot is that the pseudorandomness proof for general h is the load-bearing piece; if it has any gap the size-reduction claim weakens. The abstract is clear on the statements but the full argument needs checking for how the h=2 case lifts. No sign of circularity or invented parameters.

This is for people already working in additive combinatorics on sparse Roth theorems or on chromatic numbers of Cayley graphs. A reader in that subfield gets concrete extensions and constructions worth knowing. It deserves a serious referee because the generalization is substantive and the methods sit on established ground.

Referee Report

0 major / 3 minor

Summary. The paper derives sparse analogs of Roth-type results in near-maximal B_h sets. It shows that a B_h set without pairwise distinct solutions to a linear equation with more than 2h variables must be smaller by a constant factor than the best-known upper bound on |B_h| sets. A key input is the proof that extremal B_h sets are Fourier pseudorandom. For Sidon sets (h=2), it further shows that forbidding a non-translation-invariant equation E with a zero-sum subcollection of at least five coefficients forces either small size or bounded chromatic number in the generated Cayley graph, while constructing large Sidon sets free of equations with four-coefficient zero-sums that generate graphs of unbounded chromatic number. This extends prior Sidon-set work of Conlon-Fox-Sudakov-Zhao and Prendiville, and provides a sparse analog of Liu-Wu-Yang-Zhang on chromatic thresholds.

Significance. If the Fourier pseudorandomness of extremal B_h sets holds, the results give a structural dichotomy for equation-free subsets of near-maximal B_h sets and supply new examples of sparse sets with controlled chromatic thresholds. The pseudorandomness input is a reusable tool that strengthens the sparse additive combinatorics toolkit, and the constructions for Sidon sets separate the behavior of different zero-sum lengths in a manner parallel to the dense case.

minor comments (3)

The abstract and introduction should explicitly state the precise definition of 'pairwise distinct solutions' used in the main theorem (likely in §2 or §3) to avoid ambiguity with the standard B_h definition.
Notation for the linear equation E and its subdivision structure (mentioned for the asymptotic saving case) should be introduced with a numbered display equation early in the paper.
The reference list should include the full citation details for Conlon-Fox-Sudakov-Zhao and Prendiville to facilitate comparison with the dense analogs.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our manuscript, for highlighting the significance of the Fourier pseudorandomness result as a reusable tool, and for recommending minor revision. The report correctly identifies the extensions of prior work by Conlon-Fox-Sudakov-Zhao, Prendiville, and Liu-Wu-Yang-Zhang.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation establishes Fourier pseudorandomness of extremal B_h sets as an explicit key input and then derives constant-factor size reductions for subsets free of certain linear equations, extending prior results on Sidon sets by other authors (Conlon-Fox-Sudakov-Zhao, Prendiville, Liu-Wu-Yang-Zhang). No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; all supporting results are external, and the argument is presented as a direct sparse analog without internal reduction to its own inputs. The paper is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard mathematical foundations and domain-specific assumptions in additive combinatorics and Fourier analysis; no free parameters, invented entities, or ad-hoc axioms are indicated in the abstract.

axioms (2)

standard math Standard axioms of set theory and arithmetic
Background for all combinatorial arguments.
domain assumption Fourier analysis on abelian groups applies to pseudorandomness of extremal B_h sets
Explicitly invoked as key input in the abstract.

pith-pipeline@v0.9.1-grok · 5766 in / 1222 out tokens · 33911 ms · 2026-07-03T22:22:51.007677+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 3 canonical work pages · 2 internal anchors

[1]

Sheng Chen,On the size of finite Sidon sequences, Proc. Amer. Math. Soc.121(1994), no. 2, 353–356. MR1196162

1994
[2]

5, 497–511

Javier Cilleruelo,Combinatorial problems in finite fields and Sidon sets, Combinatorica32(2012), no. 5, 497–511. MR3004806

2012
[3]

David Conlon, Jacob Fox, Benny Sudakov, and Yufei Zhao,The regularity method for graphs with few 4-cycles, J. Lond. Math. Soc. (2)104(2021), no. 5, 2376–2401. MR4368679

2021
[4]

Sean Eberhard and Freddie Manners,The apparent structure of dense Sidon sets, Electron. J. Combin. 30(2023), no. 1, Paper No. 1.33, 19. MR4557743

2023
[5]

Erdős and M

P. Erdős and M. Simonovits,On a valence problem in extremal graph theory, Discrete Math.5(1973), 323–334. MR342429

1973
[6]

Erdős and P

P. Erdős and P. Turán,On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc.16(1941), 212–215. MR6197

1941
[7]

W. T. Gowers,What are dense Sidon subsets of {1,2,...,n} like?, blog post gowers.wordpress.com (2012)

2012
[8]

84, Springer-Verlag, New York, (1990)

Kenneth Ireland and Michael Rosen,A classical introduction to modern number theory, Second, Grad- uate Texts in Mathematics, vol. 84, Springer-Verlag, New York, (1990). MR1070716

1990
[9]

Number Theory44(1993), no

Xing De Jia,On finite Sidon sequences, J. Number Theory44(1993), no. 1, 84–92. MR1219489

1993
[10]

arXiv:2601.18738

Yifan Jing, Cosmin Pohoata, and Max Wenqiang Xu,Roth-type theorems inK s,t-free sets, (2026). arXiv:2601.18738

work page arXiv 2026
[11]

Tomasz Kościuszko,Invariant equations in many variables, Electron. J. Combin.32(2025), no. 3, Paper No. 3.24, 24. MR4946368

2025
[12]

Felix Lazebnik and Jacques Verstraëte,On hypergraphs of girth five, Electron. J. Combin.10(2003), Research Paper 25, 15. MR2014512

2003
[13]

Chromatic thresholds for linear equations and recurrence

Hong Liu, Zhuo Wu, Ningyuan Yang, and Shengtong Zhang,Chromatic thresholds for linear equations and recurrence, (2026). arXiv:2603.05490

work page internal anchor Pith review Pith/arXiv arXiv 2026
[14]

Miquel Ortega and Sean Prendiville,Extremal Sidon sets are Fourier uniform, with applications to partition regularity, J. Théor. Nombres Bordeaux35(2023), no. 1, 115–134. MR4596525

2023
[15]

Alexandru Pascadi,The sparse regularity method with Schatten norms and entropy, Electron. J. Combin. 33(2026), no. 1, Paper No. 1.26, 64. MR5037336

2026
[16]

Sean Prendiville,Solving equations in dense Sidon sets, Math. Proc. Cambridge Philos. Soc.173(2022), no. 1, 25–34. MR4438329

2022
[17]

K. F. Roth,On certain sets of integers, J. London Math. Soc.28(1953), 104–109. MR51853

1953
[18]

Ruzsa,Solving a linear equation in a set of integers

Imre Z. Ruzsa,Solving a linear equation in a set of integers. I, Acta Arith.65(1993), no. 3, 259–282. MR1254961

1993
[19]

James Singer,A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc.43(1938), no. 3, 377–385. MR1501951

1938
[20]

Coloring sparse random Cayley graphs

Nathan Tung,Coloring sparse random Cayley graphs, (2026). arXiv:2606.23762

work page internal anchor Pith review Pith/arXiv arXiv 2026
[21]

Varnavides,On certain sets of positive density, J

P. Varnavides,On certain sets of positive density, J. London Math. Soc.34(1959), 358–360. MR106865

1959
[22]

Combin.32(2011), no

Le Anh Vinh,The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields, Euro- pean J. Combin.32(2011), no. 8, 1177–1181. MR2838005 Stanford University, CA 94305, USA Email address:ntung@stanford.edu 22

2011

[1] [1]

Sheng Chen,On the size of finite Sidon sequences, Proc. Amer. Math. Soc.121(1994), no. 2, 353–356. MR1196162

1994

[2] [2]

5, 497–511

Javier Cilleruelo,Combinatorial problems in finite fields and Sidon sets, Combinatorica32(2012), no. 5, 497–511. MR3004806

2012

[3] [3]

David Conlon, Jacob Fox, Benny Sudakov, and Yufei Zhao,The regularity method for graphs with few 4-cycles, J. Lond. Math. Soc. (2)104(2021), no. 5, 2376–2401. MR4368679

2021

[4] [4]

Sean Eberhard and Freddie Manners,The apparent structure of dense Sidon sets, Electron. J. Combin. 30(2023), no. 1, Paper No. 1.33, 19. MR4557743

2023

[5] [5]

Erdős and M

P. Erdős and M. Simonovits,On a valence problem in extremal graph theory, Discrete Math.5(1973), 323–334. MR342429

1973

[6] [6]

Erdős and P

P. Erdős and P. Turán,On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc.16(1941), 212–215. MR6197

1941

[7] [7]

W. T. Gowers,What are dense Sidon subsets of {1,2,...,n} like?, blog post gowers.wordpress.com (2012)

2012

[8] [8]

84, Springer-Verlag, New York, (1990)

Kenneth Ireland and Michael Rosen,A classical introduction to modern number theory, Second, Grad- uate Texts in Mathematics, vol. 84, Springer-Verlag, New York, (1990). MR1070716

1990

[9] [9]

Number Theory44(1993), no

Xing De Jia,On finite Sidon sequences, J. Number Theory44(1993), no. 1, 84–92. MR1219489

1993

[10] [10]

arXiv:2601.18738

Yifan Jing, Cosmin Pohoata, and Max Wenqiang Xu,Roth-type theorems inK s,t-free sets, (2026). arXiv:2601.18738

work page arXiv 2026

[11] [11]

Tomasz Kościuszko,Invariant equations in many variables, Electron. J. Combin.32(2025), no. 3, Paper No. 3.24, 24. MR4946368

2025

[12] [12]

Felix Lazebnik and Jacques Verstraëte,On hypergraphs of girth five, Electron. J. Combin.10(2003), Research Paper 25, 15. MR2014512

2003

[13] [13]

Chromatic thresholds for linear equations and recurrence

Hong Liu, Zhuo Wu, Ningyuan Yang, and Shengtong Zhang,Chromatic thresholds for linear equations and recurrence, (2026). arXiv:2603.05490

work page internal anchor Pith review Pith/arXiv arXiv 2026

[14] [14]

Miquel Ortega and Sean Prendiville,Extremal Sidon sets are Fourier uniform, with applications to partition regularity, J. Théor. Nombres Bordeaux35(2023), no. 1, 115–134. MR4596525

2023

[15] [15]

Alexandru Pascadi,The sparse regularity method with Schatten norms and entropy, Electron. J. Combin. 33(2026), no. 1, Paper No. 1.26, 64. MR5037336

2026

[16] [16]

Sean Prendiville,Solving equations in dense Sidon sets, Math. Proc. Cambridge Philos. Soc.173(2022), no. 1, 25–34. MR4438329

2022

[17] [17]

K. F. Roth,On certain sets of integers, J. London Math. Soc.28(1953), 104–109. MR51853

1953

[18] [18]

Ruzsa,Solving a linear equation in a set of integers

Imre Z. Ruzsa,Solving a linear equation in a set of integers. I, Acta Arith.65(1993), no. 3, 259–282. MR1254961

1993

[19] [19]

James Singer,A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc.43(1938), no. 3, 377–385. MR1501951

1938

[20] [20]

Coloring sparse random Cayley graphs

Nathan Tung,Coloring sparse random Cayley graphs, (2026). arXiv:2606.23762

work page internal anchor Pith review Pith/arXiv arXiv 2026

[21] [21]

Varnavides,On certain sets of positive density, J

P. Varnavides,On certain sets of positive density, J. London Math. Soc.34(1959), 358–360. MR106865

1959

[22] [22]

Combin.32(2011), no

Le Anh Vinh,The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields, Euro- pean J. Combin.32(2011), no. 8, 1177–1181. MR2838005 Stanford University, CA 94305, USA Email address:ntung@stanford.edu 22

2011