Quasipolynomial Bounds for Arithmetic Progressions

Introduction

Erdős asked whether every set $A$ of positive integers for which $\sum_{a\in A} 1/a$ diverges contains arithmetic progressions of every finite length [14]. We prove a quantitative density bound that implies this assertion. For integers $k \ge3$ and $N \ge1$, let $r_k(N)$ be the largest cardinality of a subset of $[N] = \{1,\ldots,N\}$ containing no nonconstant $k$-term arithmetic progression $a,a+d,\ldots,a+(k-1)d$, with $d>0$. All logarithms are natural.

Theorem 1.1. For each fixed integer $k \ge3$ there are constants $C_k,c_k,\varepsilon_k>0$ such that, for every $N \ge2$,

Equivalently, there is $A_k \ge1$ such that an $\alpha$-dense subset of $[N]$ contains a nonconstant $k$-term progression whenever

The constants may depend on the fixed length $k$; the exponent is not optimized. The reciprocal-sum consequence follows immediately from summing the density bound over dyadic intervals.

Corollary 1.2 (Divergent reciprocal sums). Every set $A\subseteq\mathbb{N}$ with $\sum_{a\in A}a^{-1}=\infty$ contains nonconstant arithmetic progressions of every finite length.

Proof. Fix $k\ge3$, and suppose that $A$ contains no nonconstant $k$-term progression. For $m\ge0$, translation identifies $[2^m,2^{m+1})\cap\mathbb{Z}$ with an interval of length $2^m$. Thus $|A\cap[2^m,2^{m+1})|\le r_k(2^m)$. Theorem 1.1 implies, for $m\ge1$,

For every $d,\varepsilon>0$, the sequence $e^{-dm^\varepsilon}$ is summable: since $m^\varepsilon/\log m\to\infty$, its terms are at most $m^{-2}$ for all sufficiently large $m$. The $m=0$ interval contributes at most one. The reciprocal sum of $A$ is therefore finite, a contradiction. Divergence also implies that $A$ is infinite, which supplies lengths one and two. ▫

Density thresholds and summability

The threshold in (1.2) is quasipolynomial in $1/\alpha$: the logarithm of a sufficient interval length is a fixed power of $2+\log(1/\alpha)$. The inversion between the two forms of Theorem 1.1, including the endpoints, is proved in Section 10.

The infinite-set consequence depends on more than a density tending to zero. Divergence of a reciprocal sum allows zero-density sets, and the qualitative estimate $r_k(N)=o(N)$ does not by itself settle Erdős’s question. The proof of Corollary 1.2 uses the stronger condition

Our bound also gives a stronger divergence criterion: for every fixed $B\ge0$, a set $A\subseteq\mathbb{N}$ satisfying

contains progressions of every finite length. Section 11 proves this criterion, uniform harmonic bounds and tails, and estimates for larger weights whose parameters depend on $k$. It also recovers the theorem of Green and Tao that every subset of the primes of positive relative upper density contains infinitely many progressions of every finite length [21].

Prior density bounds

Van der Waerden’s theorem concerns a partition: every finite coloring of the positive integers has a monochromatic arithmetic progression of each finite length [47]. The density problem asks for a condition on a prescribed set. Erdős and Turán began the study of the corresponding extremal functions in 1936 and explicitly conjectured that $r_3(N)=o(N)$ [15]. The all-length positive-density conjecture appears explicitly in Erdős’s later account [13]. Roth proved the three-term case by Fourier-analytic methods [39]; Szemerédi proved the four-term case in 1969 and the general theorem in 1975 [44, 45]. Furstenberg’s subsequent proof recast the assertion as multiple recurrence in a measure-preserving system [16]. The reciprocal-sum conjecture extends this density problem to sparser sets, including the primes [14].

For three terms, successive quantitative advances sharpened Roth’s density-increment method: a shortage of progressions forces a density increase on a smaller structured set. Roth obtained $r_3(N)\ll N/\log\log N$. Heath-Brown and Szemerédi replaced the double logarithm by a positive power of $\log N$ [26, 46], and Bourgain developed density increments on regular Bohr sets [9, 10]. Sanders reached $r_3(N)\ll N/(\log N)^{1-o(1)}$, and Bloom improved the remaining logarithmic factors [41, 4].

Bloom and Sisask gave an almost-periodicity approach to this near-logarithmic range [5]. Their later bound $r_3(N)\ll N/(\log N)^{1+c}$, for an absolute $c>0$, crossed the dyadic summability threshold and established the three-term reciprocal-sum conjecture [6].

Kelley and Meka obtained the stronger bound

by combining positivity, dependent-random-choice sifting and almost-periodicity to control the loss in a density increment [30]. Bloom and Sisask simplified the argument and then improved the exponent to $1/9$ [8, 7]. Raghavan subsequently obtained $r_3(N)\le N\exp\left(-(\log N)^{1/6-o(1)}\right)$ [38]. These refinements concern three terms. On the lower-bound side, Behrend’s construction already gives $r_3(N) \ge N\exp(-C\sqrt{\log N})$, so a fixed power saving in $N$ is impossible even in this case [1].

Gowers’s approach to longer progressions detects higher-order structure. He introduced the uniformity norms that control progression counts and extended density increments beyond linear Fourier analysis [17, 18]. His general theorem gives $r_k(N) \ll_k N/(\log\log N)^{c_k}$ for every fixed $k$, with $c_k > 0$. Green and Tao obtained $r_4(N) \ll N/(\log N)^{1/11}$ [24]. Leng, Sah and Sawhney first treated five terms and then proved, for every fixed $k \ge5$,

[33, 34]. Their general argument combines a quasipolynomial inverse theorem with density increments. The inverse theorem controls the structured correlation obtained from a large uniformity norm; the cost of localizing and iterating that correlation remains a separate issue. The resulting saving in $\log\log N$ does not give the dyadic summability above.

Theorem 1.1 gives a stretched-exponential saving in $\log N$ for every fixed length. Its contribution to Erdős’s conjecture is this all-length, summable bound; no improvement of the three-term exponent is claimed. We next explain the quantitative constraint on the density-increment regions that allows the argument to be iterated at this scale.

Preserving structure through density increments

A fixed multiplicative density gain can be applied only $O_k(1+\log(1/\alpha))$ times before the density exceeds one. To obtain Theorem 1.1, the total logarithmic loss of interval length over these increments must be polynomial in $2+\log(1/\alpha)$. We therefore need to control both the number of coordinates describing each new region and the precision of the constraints inherited from previous regions.

The regions are triangular polynomial cells. A spatial integer variable $u$ determines integer blocks $b_1,\ldots,b_D$ successively through constraints of the form

Here $D$ depends only on $k$, each $l_h$ is a fixed center, and $C_h$ is a polynomial. The spatial variable has weight one, the block $b_h$ has weight $h$, and $C_h$ has weighted degree at most $h$. The narrow widths make each integer block unique when it exists. Keeping these integer blocks, and substituting them exactly into all later polynomials, preserves the equations defining the old region when a new constraint is added. No bound on the coefficients of the $C_h$ is imposed.

Write $Q_h=\log(2/w_h)$ for the precision at weight $h$. The main increment theorem bounds the additional precision at weight $h$ by a polynomial in the dimension data, the logarithmic density parameter, and the precisions at strictly higher weights. In particular, this bound does not use the current $Q_h$ or the lower precisions. The dimensions obey an analogous descending recurrence. Since the number $D$ of weights is fixed, descending induction bounds all dimensions and precisions by polynomials through the required number of increments. Section 2 states these recurrences precisely; Section 10 proves that the construction satisfies them.

Two different arguments supply these bounds. The first produces an absolute increment for a $[0,1]$-valued function on an integer box with sufficiently long sides. The function must have positive mean and contain no nonconstant $k$-term progression in its support. The increment adds only a number of determining coordinates polynomial in the logarithmic inverse mean, independently of the dimension of that box. The second returns such an increment from a sampled box to the original cell, preserving the old determining equations and the descending dependence of their width losses.

An absolute increment with uncontrolled dependence on the old widths would not suffice for this second task.

The absolute increment. The higher-order inverse theorem converts a large uniformity norm into correlation with a nilsequence, a Lipschitz function evaluated along a polynomial orbit on a compact nilmanifold. This description of structured correlations has both ergodic and additive-combinatorial origins. Host and Kra developed seminorms and nilsystem characteristic factors, Ziegler proved the universal-factor theorem, and Bergelson, Host and Kra isolated nilsequences in multiple correlations [27, 48, 2]. Green and Tao obtained locally quadratic structure for the $U^{3}$ norm [20]; Green, Tao and Ziegler then proved the all-degree interval inverse theorem [25]. Manners gave explicit quantitative inverse bounds on prime cyclic groups [36]. The stronger quasipolynomial bounds of Leng, Sah and Sawhney are the interval input used here [35], Theorem 1.2; the appendices prove the box and product-cyclic reductions needed in the argument.

To pass from structured tests to positive progression counting, we prove a shift-comparison theorem: lowering the testing degree permits multiplication by a translated nonnegative function outside a small exceptional set of shifts. Its degree-one argument adapts Kelley–Meka unbalancing and sifting, as developed on Bohr sets by Bloom and Sisask [30, 8]. The almost-periodicity input is Schoen–Sisask’s Theorem 5.4 [43]. It combines the probabilistic method of Croot and Sisask with Sanders’s local control of large spectra [12, 40]; see also Sanders’s Bogolyubov–Ruzsa theorem [42]. The Schoen–Sisask radius bound retains the incoming radius as a multiplicative factor, which is essential for the shift comparison.

Higher-degree comparison requires control of polynomial orbits. Leibman established a qualitative distribution theorem [31]. Green and Tao made this theory quantitative and factored polynomial orbits into smooth, equidistributed and rational components [23]. Leng’s efficient estimates reduce the nilpotency step rather than repeatedly reducing the dimension [32]. We use this mechanism, together with the inverse theorem, to remove top-degree frequencies in the comparison argument. The appendices prove the required forms with explicit dependence on all growing dimensions and parameter counts.

The comparison and counting arguments first give the absolute rule in a fixed dimension. A relative lifting theorem extends it with only an additive number of new determining coordinates. Applied with the constant old region, this yields the dimension-independent fresh-coordinate bound in Lemma 2.2. This foundational lifting argument supplies the absolute rule; preservation of the old width budgets requires the separate return argument.

Returning to the original cell. A density increment found on a sampled parameter box must be expressed again in the original variables. The cell can have very small mass, and an error in one of its determining integers would enter every later polynomial that uses that integer. The return therefore keeps the old equations exact.

For tests of degree below the current layer weight, we use a cube version of Conlon–Fox–Zhao densification to replace sparse factors by bounded ones before applying inverse theory [11]. The comparison proved here has bounds independent of that layer’s chart mass. At layers where the testing degree is at least the layer weight, polynomial families retain the old equations through an exact projection while allowing the newly added region to have higher degree. Preparation, ascent and extraction then control the relative loss of each width by structural data and higher-weight precision budgets. The general route from inverse theory to density increments is classical [22]; retaining this dependence through the return is the quantitative issue addressed here.

Coloring thresholds

Let $W_r(k)$ be the least integer $N$ such that every coloring of $[N]$ with $r$ colors contains a monochromatic nonconstant $k$-term arithmetic progression. A largest color class has density at least $1/r$, so Theorem 1.1 gives

after increasing $A_k$. Thus, for fixed $k$, the sufficient length is quasipolynomial in the number of colors. The companion paper [37], Theorem 7.2 gives the complementary lower bound $W_r(k) > \exp((\log r)^2/(64\log2))$ for all integers $r \ge256$ and $k \ge3$. Together these estimates show that for each fixed $k \ge3$, growth in the number of colors is superpolynomial but at most quasipolynomial. The upper constant and exponent may depend on $k$.

How to read the proof

Section 2 defines the cells and precision budgets, states the triangular increment theorem, and explains the dimension-independent absolute rule. Figure 3 gives the main route, and Table 1 identifies the analytic statements and their full proofs. Section 3 constructs the constrained path law and states its sampling guarantees. Section 4 prepares the cell by rank cuts, and Section 5 proves the detection bound independent of the current width. Section 6 transfers the certificate to terminal boxes and obtains an absolute increment. Section 7 sets up its return, develops the comparison estimates, and handles the passive layers. Section 8 treats the active layers. Section 9 extracts the next cell, and Section 10 closes the recurrences and proves Theorem 1.1. Section 11 establishes the weighted consequences.

The appendices contain the rational and symbol calculus, shift comparison, progression counting, constrained sampling, cube comparison and relative lifting arguments. The two principal external analytic inputs to the increment proof are the interval inverse theorem of Leng, Sah and Sawhney and the radius-sensitive almost-periodicity theorem of Schoen and Sisask [35, 43]. Their precise hypotheses are stated at the points of application.

Polynomial cells and the increment theorem

Fix $k \ge3$ and put $s = k - 2$. We seek density increments on regions that retain every polynomial constraint introduced by an earlier increment. The regions will be triangular polynomial cells. Their integer coordinates are determined successively, and their residual widths are indexed by weight. The central estimate will bound the relative width loss at each weight using only higher-weight widths.

Every degree and descent depth below is fixed in terms of $s$; dimensions may grow. A degree bound may be replaced by any fixed larger one. We work on rectangular integer boxes, with uniform probability averages and max norms, allowing dimension factors in norm comparisons. A slice is an integer-affinely reindexed residue subbox. Different coordinate strides are permitted. Its logarithmic cost includes their logarithms and the logarithms of inverse relative side lengths. Sufficient lower bounds on the original sides absorb all endpoint rounding errors. A function is progression-free when its support contains no nonconstant integer-vector $k$-term progression.

Precision conventions