frontiers / frontier

Additive combinatorics: Sidon sets and N(h,k) bounds

id: vfr_496956067dc5ad79
license: CC-BY-4.0
findings: 22
accepted core: 1
contested: 1
links: 0
sources: 22
evidence: 22
avg conf: 0.83

used by 1 · replayed by 1 producer · second seat open

e33/33 · finding.asserted · reviewer:will · 2026-06-03 · null→e123

State

by type

theoretical22

by review state

unreviewed21
needs_revision1

bundle anatomy

finding statement

For h>=3 the analog of N(h,k) admits a polynomial in k upper bound via h-squared-dissociated sets, replacing the prior exponential construction.

theoretical

evidence

theoretical · manual state transition

22 atoms

provenance

Nathanson, 2024 (open problem)

review state

The example finding is unreviewed. Frontier changes still pass through reviewable changes and accepted events.

26 accepted events

derived signals

Links, candidate gaps, bridges, citation stance, nearby papers, and generated summaries route review. They do not rewrite the record by themselves.

0 linked findings39 reviewable changes

22 findings · 0 machine-sealed

verifiedreplayedsupersededbankedleasedcontesteddeprecated

Additive combinatorics: Sidon sets and N(h,k) bounds

State

bundle anatomy

For h>=3 the analog of N(h,k) admits a polynomial in k upper bound via h-squared-dissociated sets, replacing the prior exponential construction.

Behrend's construction yields subsets of {1,...,N} of size N * exp(-c * sqrt(log N)) containing no nontrivial 3-term arithmetic progression, the densest such known until 2020.

Singer's perfect-difference-set construction in projective planes yields Sidon sets in {1,...,N} of size sqrt(N) + O(N^{1/4}), matching the elementary upper bound up to lower-order terms.

Gowers gave the first quantitative proof of Szemeredi's theorem with effective bounds, introducing higher-order Fourier analysis (Gowers norms U^k) as the central tool.

B_h sets, the h-fold generalization of Sidon sets, have maximum density satisfying |A| <= (h! * N)^{1/h} + O(N^{1/(2h)}) in {1,...,N}.

The h-squared-dissociated set construction needed for the polynomial bound has diameter polynomial in k, replacing geometric components in the original construction.

Roth's theorem: any subset of {1,...,N} of density alpha > C / log log N contains a nontrivial 3-term arithmetic progression.

Freiman's theorem: a finite set A of integers with |A+A| <= K|A| is contained in a generalized arithmetic progression of dimension at most d(K) and size at most f(K) * |A|.

A Sidon set in {1,...,N} of size O(sqrt(N)) exists, attaining the elementary upper bound for h=2 sumsets up to a multiplicative constant.

A Bohr neighborhood B(Lambda, rho) is the set of x in Z/NZ where |gamma * x / N| < rho for all gamma in Lambda; its dimension d = |Lambda| controls density |B| / N >= rho^d, enabling Fourier-analytic density-increment iterations.

The polynomial method bounds 3-AP-free subsets of (Z/4Z)^n by 4^{0.926n}, far below the 4^n total, breaking the previous logarithmic-style bounds for cap-set-style problems.

Plunnecke-Ruzsa inequality: if |A+A| <= K|A|, then |kA - lA| <= K^{k+l} * |A| for all nonnegative integers k, l.

Schoen-Shkredov: density alpha > exp(-c * (log N)^{1/4}) suffices for 3-APs via combined Fourier and Bohr-set decomposition methods.

Szemeredi's theorem: any subset of the natural numbers with positive upper density contains arbitrarily long arithmetic progressions.

Functions with large Gowers U^{s+1}-norm correlate with nilsequences of step s; this inverse theorem is the analytic engine behind quantitative Szemeredi for arbitrary k.

Bourgain's Fourier-analytic increment argument lowers the density threshold for 3-AP existence in {1,...,N} to alpha > C * (log log N)^2 / sqrt(log N).

Sanders' bound: density alpha > C * (log log N)^4 / log N is sufficient to guarantee a 3-term AP in any subset of {1,...,N}.

Ruzsa covering lemma: if |A+B| <= K|A|, then B is contained in the sumset A - A translated by at most K elements; the engine of small-doubling structure theorems.

Ellenberg-Gijswijt extend Croot-Lev-Pach to prove a 3-AP-free subset of F_3^n has size at most 2.756^n, settling the cap-set problem up to a constant in the exponent.

Bloom-Sisask break the 'log barrier' for Roth: density alpha > 1 / (log N)^{1+c} for an absolute c > 0 suffices for a 3-AP, the first sub-1/log N bound.

Lindstrom's upper bound for Sidon-set size in {1,...,N} is sqrt(N) + N^{1/4} + 1, tightening the Erdos-Turan bound by a factor of sqrt(2).

For h>=3 the analog of N(h,k) admits a polynomial in k upper bound via h-squared-dissociated sets, replacing the prior exponential construction.

Behrend's construction yields subsets of {1,...,N} of size N * exp(-c * sqrt(log N)) containing no nontrivial 3-term arithmetic progression, the densest such known until 2020.

Singer's perfect-difference-set construction in projective planes yields Sidon sets in {1,...,N} of size sqrt(N) + O(N^{1/4}), matching the elementary upper bound up to lower-order terms.

Gowers gave the first quantitative proof of Szemeredi's theorem with effective bounds, introducing higher-order Fourier analysis (Gowers norms U^k) as the central tool.

B_h sets, the h-fold generalization of Sidon sets, have maximum density satisfying |A| <= (h! * N)^{1/h} + O(N^{1/(2h)}) in {1,...,N}.

The h-squared-dissociated set construction needed for the polynomial bound has diameter polynomial in k, replacing geometric components in the original construction.

Roth's theorem: any subset of {1,...,N} of density alpha > C / log log N contains a nontrivial 3-term arithmetic progression.

Freiman's theorem: a finite set A of integers with |A+A| <= K|A| is contained in a generalized arithmetic progression of dimension at most d(K) and size at most f(K) * |A|.

A Sidon set in {1,...,N} of size O(sqrt(N)) exists, attaining the elementary upper bound for h=2 sumsets up to a multiplicative constant.

A Bohr neighborhood B(Lambda, rho) is the set of x in Z/NZ where |gamma * x / N| < rho for all gamma in Lambda; its dimension d = |Lambda| controls density |B| / N >= rho^d, enabling Fourier-analytic density-increment iterations.

The polynomial method bounds 3-AP-free subsets of (Z/4Z)^n by 4^{0.926n}, far below the 4^n total, breaking the previous logarithmic-style bounds for cap-set-style problems.

Plunnecke-Ruzsa inequality: if |A+A| <= K|A|, then |kA - lA| <= K^{k+l} * |A| for all nonnegative integers k, l.

Schoen-Shkredov: density alpha > exp(-c * (log N)^{1/4}) suffices for 3-APs via combined Fourier and Bohr-set decomposition methods.

Szemeredi's theorem: any subset of the natural numbers with positive upper density contains arbitrarily long arithmetic progressions.

Functions with large Gowers U^{s+1}-norm correlate with nilsequences of step s; this inverse theorem is the analytic engine behind quantitative Szemeredi for arbitrary k.

Bourgain's Fourier-analytic increment argument lowers the density threshold for 3-AP existence in {1,...,N} to alpha > C * (log log N)^2 / sqrt(log N).

Sanders' bound: density alpha > C * (log log N)^4 / log N is sufficient to guarantee a 3-term AP in any subset of {1,...,N}.

Ruzsa covering lemma: if |A+B| <= K|A|, then B is contained in the sumset A - A translated by at most K elements; the engine of small-doubling structure theorems.

Ellenberg-Gijswijt extend Croot-Lev-Pach to prove a 3-AP-free subset of F_3^n has size at most 2.756^n, settling the cap-set problem up to a constant in the exponent.

Bloom-Sisask break the 'log barrier' for Roth: density alpha > 1 / (log N)^{1+c} for an absolute c > 0 suffices for a 3-AP, the first sub-1/log N bound.

Lindstrom's upper bound for Sidon-set size in {1,...,N} is sqrt(N) + N^{1/4} + 1, tightening the Erdos-Turan bound by a factor of sqrt(2).

Search Vela