Quasipolynomial Bounds for Arithmetic Progressions

1. Fix the iteration horizon first

For a progression-free set of density $\alpha>0$, start with $f=1_A$, no cell constraints, and $a_0=\alpha/2$. Fix one resource parameter $p=C(2+\log(1/\alpha))$ and reserve

Each increment multiplies the target by at least $1+\eta_k$ and adds at most $d_0=(2+p)^{C_k}$ fresh absolute coordinates. Discounted intermediate targets remain above a fixed positive multiple of $a_0$, so the same $p$ ensures $a\ge e^{-p}$ throughout. Temporary higher-dimensional path boxes do not replace the root spatial dimension in the next round: the root remains an integer-affine slice of the original interval.

Proposition 10.4 · p. 81

2. Triangular recurrences control the loss of length

The weight depth $D=D_k$ is fixed. The increase in the dimension at weight $i$ is bounded by $d_0$ and a polynomial in strictly higher-weight dimensions. Within a preparation round, set $H_D=d_D$ and $H_i=d_i+H_{i+1}^2$; then $d_i^{\rm out}\le d_i+d_0+H_{i+1}^2$, with $H_{D+1}=0$. Descending induction bounds dimensions and cut counts across all $T$ rounds by one polynomial forecast $d_*(p)$, fixed before numerical precisions.

For widths $w_i$, write $Q_i=\log(2/w_i)$. The decisive estimate is

Neither the current $Q_i$ nor lower-weight widths enter the right-hand side. Define downward envelopes

Then $Q_i(t)\le V_i=\operatorname{poly}_k(p)$. Fixed $D$ means fixed polynomial-composition depth. The sum of logarithmic root-slice losses, remaining logarithmic side requirements, and endpoint-rounding costs is also $\operatorname{poly}_k(p)$. Actual length losses occur at the exponential of this scale; a polynomial loss in the side lengths themselves is not asserted. An initial $\log N$ exceeding the total sustains every round.

Propositions 10.2–10.3; §§10.2–10.3 · pp. 77–80

3. The stopping contradiction and equivalence of the two forms

An earlier impossibility alternative already contradicts the initial assumptions. Otherwise $a_T\ge(\alpha/2)(1+\eta_k)^T\ge1$. The certificate $\mathbb E fB^->a_T\mathbb EB^+$ contradicts the pointwise inequality $fB^-\le B^+$. Thus a progression-free set cannot satisfy $\log N\ge C_k(2+\log(1/\alpha))^{A_k}$.

Substituting $\alpha=r_k(N)/N>0$ and inverting gives

which yields the density bound after renaming constants. Conversely, put $\overline C_k=\max(1,C_k)$. The bound implies $r_k(N)\le\alpha N/2<\alpha N$ whenever

This slack covers equality in “density at least $\alpha$.” Enlarging $A_k$ gives the stated threshold throughout $0<\alpha\le1$. The density bound is immediate when $\alpha=0$.

Proof of Theorem 1.1 · pp. 81–82

1. Do not charge the inverse of a small certificate surplus

A preparation rank cut uses a relation at a failing degree, lowers the rational value-space dimension, and, when needed, copies a higher block down one weight. Every higher determining polynomial is transformed exactly on its integer arguments. Since coefficients are unrestricted, continuity in an approximate integer slot cannot replace this operation.

Constrained paths along integer-affine maps carry the prepared cell to terminal boxes. Stopped paths retain zero mass; survivors are not renormalized. Proposition 6.2 gives a terminal mean $Y$ with $\mathbb EY\ge(1-\delta)a$, and at least a $\delta a$ fraction of paths have $Y\ge(1-2\delta)a$. This avoids paying the inverse of the original strict surplus $\mathbb EfB^--a\mathbb EB^+$. Injective integer-affine pullback and removal of points preserve progression-freeness.

Proposition 4.1; Lemma 4.3 · pp. 25–26 Proposition 6.2 · pp. 42–44

2. Obtain a fresh-coordinate count independent of dimension

Lemma 2.2 supplies a fixed multiplicative gain and a degree-$s$ polynomial patch with at most $(2+p)^{C_k}$ fresh coordinates on a terminal box of density $a\ge e^{-p}$. The fresh count is independent of its dimension $n$, although logarithmic side requirements, slice costs, Lipschitz bounds, and inverse surplus may depend on $p+n$.

Positive counting in fixed dimension alone does not give this distinction. The manuscript obtains Proposition D.3's absolute increment from Theorem C.1's shift comparison, then converts the niltest into a patch by Lemma D.5. The relative lifting theorem, Theorem I.15, bounds the output rank by $d+d_0$ for an old patch of rank $d$. Applying it to the constant old patch $1$, with $d=0$, gives the dimension-independent $d_0$. We follow the statements and their combination in Lemma 2.2; the complete proofs in Appendices C–I have not been independently verified.

Lemma 2.2 · pp. 11–12 Proposition D.3 · pp. 118–119 Proof of Theorem I.15 · pp. 194–195

3. Keep integer boxes and finite groups distinct

For the interval-to-box inverse-theorem extension, embed $Q=\prod_i\{0,\ldots,T_i-1\}$ in an interval by a mixed-radix affine map with bases $4T_i$, and extend by zero. Two-face additive identities are reflected without carries, giving equality of unnormalized cube sums. Group embeddings retain the cube-count normalization ratio. To pass from a product of cyclic groups back to boxes, divide each coordinate into at most four intervals of diameter less than one-third of the period, eliminating wraparound. Factors of $\exp(O_s(n))$ enter the logarithmic resource budget.

Positive counting for the absolute increment uses a separate passage. A box with distinct prime side lengths $P_j$ is identified by the Chinese remainder theorem with $\mathbb Z/(\prod_jP_j)\mathbb Z$; $P_j>k-1$ ensures invertibility of the small slope differences. Proposition D.3 inserts a smooth nonnegative weight supported on $x_j/P_j\in(1/4,1/3)$ and $d_j/P_j\in(1/(20k),1/(10k))$. On this support every progression lifts to the integer box without wraparound and has $d\ne0$. Positive group counting contradicts the zero count forced by integer progression-freeness. Arbitrary cyclic progressions are not read unconditionally as integer progressions.

Theorem A.7; Lemma A.9 · pp. 90–93 Proposition D.3 · pp. 118–119

4. Return the positive score and close the width dependencies

The return transports the positive and negative payoffs together, retaining positivity of their difference. At passive layers $j>s$, Proposition 7.8 and Corollary 7.9 give an ordinary ambient orbit and a retained modulus with small logarithmic cost. At active layers $j\le s$, Theorem 8.2 retains the determining projection as an exact identity. Auxiliary subdivisions in short variables or moduli could feed a current-width cost back into the scoring slice; instead these variables remain in labeled polynomial families.

Proposition 9.1 solves the inactive integer equations, real constraints, and congruence conditions in turn, restoring the old determining equations exactly. Selected affine planes solve the active layer's large full-modulus congruences identically, avoiding subdivision at that modulus. Rather than control the returned polynomial's coefficients, extraction localizes its normalized domain, bounding $\log(w_j/r_j')$ by higher-layer data independent of the current width. Finally Lemma 10.1 uses coverage averaging to compress to simultaneous residual boxes, with no new slots. Section 10.3 orders dimension forecasts, gaps, descending numerical forecasts, and the final accuracy, rank, and side choices; total discounts remain below the absolute gain, leaving $\eta_k>0$.

Proposition 7.8; Corollary 7.9; Theorem 8.2 · pp. 57–62 Proposition 9.1; §9 · pp. 69–70 Lemma 10.1 · pp. 76–77 Propositions 10.2–10.3; §§10.2–10.3 · pp. 77–80

1. Fix one length and sum

Fix $k\ge3$ and suppose $A\subseteq\mathbb N$ contains no nonconstant $k$-term progression. Each half-open dyadic interval $[2^m,2^{m+1})\cap\mathbb Z$ translates to an integer interval of length $2^m$, so

For every $d,\varepsilon>0$, $m^{\varepsilon}/\log m\to\infty$, hence $e^{-dm^{\varepsilon}}\le m^{-2}$ for all sufficiently large $m$. Thus the right-hand side is summable. The interval $m=0$ contributes at most one, and $\sum_{a\in A}1/a<\infty$, contradicting divergence. The qualitative bound $r_k(N)=o(N)$ alone would not give this summability.

Corollary 1.2 · p. 4 Proposition 11.1; Corollary 11.2 · p. 82

2. Recover every finite length

The contradiction applies to every fixed $k\ge3$, so a divergent-sum set contains a nonconstant progression of each such length. Constants and progressions may differ with $k$; no single uniform threshold is required. Divergence also makes the set infinite, supplying lengths one and two. This covers all quantifiers in Corollary 1.2. Section 11.1 extends the same dyadic partition to nonnegative weights $w$, but the subsequent weighted consequences are not all presented as main results here.

Corollary 1.2 · p. 4