Read-back: Erdos142.leng_sah_sawhney

The statement

Let $k$ be a natural number, and assume $5 \le k$. The theorem asserts that

$$\exists\, c \in \mathbb{R},\quad c > 0 \ \ \text{ and } \ \ \big(\text{for all sufficiently large } N \in \mathbb{N}\big)\quad r(k,N) \ \le\ N \cdot \exp\!\Big(-\big(\log(\log N)\big)^{c}\Big).$$

Everything below spells out each ingredient of this assertion.

The quantifier structure

The statement is: for every natural number $k$ satisfying $5 \le k$ (both $k$ and the hypothesis $5 \le k$ are explicit arguments of the theorem), there exists a real number $c$ such that both $0 < c$ and the displayed inequality holds eventually in $N$.

The order of the binders is: $k$ first, then $c$, then $N$. Hence $c$ is allowed to depend on $k$, but a single $c$ must work for all the large $N$; $c$ may not vary with $N$.

The phrase "for all sufficiently large $N$" is the eventuality filter $\mathcal{F}_{\text{atTop}}$ on $\mathbb{N}$; unfolded, it says:

$$\exists\, N_0 \in \mathbb{N},\ \forall N \in \mathbb{N},\ N \ge N_0 \implies r(k,N) \le N \cdot \exp\!\big(-(\log\log N)^{c}\big).$$

The threshold $N_0$ is existentially quantified inside the scope of $c$ and $k$, so it may depend on both. Nothing constrains $c$ beyond $c > 0$: there is no upper bound on $c$, and $c$ is not required to be less than $1$, greater than $1$, or related to $k$ in any way. No claim is made about any particular $N$; every finite set of values of $N$ may fail the inequality.

The left-hand side: the quantity $r(k,N)$

$r(k,N)$ is a natural number, defined in the accompanying bundle as a supremum of a set of natural numbers:

$$r(k,N) \;=\; \sup\ \Big\{\, |S| \ :\ S \subseteq \{1,2,\dots,N\} \text{ a finite set, } S \text{ is } \text{“}k\text{-AP-free”} \,\Big\},$$

where $\{1,\dots,N\}$ is the integer interval from $1$ to $N$ inclusive (empty when $N = 0$), $|S|$ is the number of elements of $S$, and the supremum is taken in $\mathbb{N}$ (a conditionally complete lattice; the supremum of an empty or unbounded set of naturals would be $0$ by convention, but here the set always contains $0$, witnessed by $S = \emptyset$, and is bounded above by $N$).

In the inequality, $r(k,N)$ is coerced from $\mathbb{N}$ into $\mathbb{R}$.

What "$k$-AP-free" means here

The bundle's notion of progression-freeness used in the definition of $r$ is the following, stated for a set $s$ of naturals and a "length" $\ell$ taken in the extended naturals $\mathbb{N} \cup \{\infty\}$ (here $\ell$ is the image of $k$ in $\mathbb{N} \cup \{\infty\}$):

$s$ is AP-of-length-$\ell$-free iff for every subset $t \subseteq s$: if $t$ is an arithmetic progression of length $\ell$, then $\ell \le 1$.

And "$t$ is an arithmetic progression of length $\ell$" means: there exist $a, d \in \mathbb{N}$ such that

1. the cardinality of $t$, measured in $\mathbb{N} \cup \{\infty\}$, is exactly $\ell$; and
2. $t$ is exactly the set $\{\, a + n\cdot d \ :\ n \in \mathbb{N},\ n < \ell \,\}$.

Since $k \ge 5$, the conclusion "$\ell \le 1$" is false, so for the sets $S$ counted by $r(k,N)$ the condition reduces to: no subset $t \subseteq S$ is an arithmetic progression of length $k$ in the above sense — i.e. no subset of $S$ can be written as $\{a, a+d, a+2d, \dots, a+(k-1)d\}$ while simultaneously having exactly $k$ elements.

Two consequences of clause 1 are worth making explicit. First, the difference $d = 0$ is automatically excluded when $k \ge 2$: with $d = 0$ the set $\{a + n\cdot 0 : n < k\}$ is the singleton $\{a\}$, whose cardinality is $1 \ne k$. So the cardinality clause, not a separate positivity hypothesis, is what rules out constant (trivial) progressions. Second, clause 1 forces the $k$ listed terms to be pairwise distinct.

The condition ranges over all subsets $t$ of $S$, not only $k$-element ones; but clause 1 means only $k$-element subsets can ever satisfy the premise.

The bundle also contains a second, elementary pair of definitions — "$A$ contains a $k$-term progression" ($\exists a, d$ with $d > 0$ and $a + i\,d \in A$ for all $i < k$) and its negation — but neither of these is used in the statement of this theorem or in the definition of $r$. The bundle's auxiliary lemmas (that the empty set is progression-free, that every progression-free $S \subseteq \{1,\dots,N\}$ has $|S| \le r(k,N)$, and that $r(k,N) \le N$) are likewise not part of this theorem's claim.

The right-hand side: the bound

The right-hand side is the real number

$$N \cdot \exp\!\Big(-\big(\log(\log N)\big)^{c}\Big),$$

with $N$ coerced from $\mathbb{N}$ to $\mathbb{R}$ and $\exp$ the real exponential function. Three points of literal reading:

The nesting of the logarithms. The inner expression is $\log$ applied to $N$, and then $\log$ applied to that. So it is the iterated logarithm $\log\log N$ — not $\log N$ raised to something, and not $(\log N)\cdot(\log N)$.

The placement of the minus sign. The exponentiation binds more tightly than the unary minus, so the argument of $\exp$ is

$$-\big((\log\log N)^{c}\big),$$

the negative of the $c$-th power of $\log\log N$ — not $\big(-\log\log N\big)^{c}$, the $c$-th power of the negated iterated logarithm. Consequently, for those $N$ with $\log\log N > 1$ the factor $\exp(-(\log\log N)^c)$ lies strictly between $0$ and $1$, and it tends to $0$ as $N \to \infty$ for any fixed $c > 0$.

The meaning of the power. Both the base $\log\log N$ and the exponent $c$ are real numbers, so $(\log\log N)^{c}$ is the real power function (real exponent), not iterated multiplication by a natural-number exponent. Under the total-function conventions in force, this power is defined for every real base, including non-positive ones: for a positive base $x$ it is $\exp(c\log x)$ as usual; for $x = 0$ and $c \ne 0$ it is $0$; and for a negative base $x$ it takes the value $\exp(c\log|x|)\cos(c\pi)$ rather than being undefined. The statement does not assume $\log\log N > 0$ anywhere.

Degenerate and edge cases

• The eventuality filter means the small-$N$ behaviour is unconstrained. In particular the theorem says nothing about $N = 0$ (where $\{1,\dots,N\}$ is empty, so $r(k,0)=0$), about $N = 1$ (where $\log 1 = 0$ and, by the convention $\log 0 = 0$, $\log\log 1 = 0$, so the bound reads $r(k,1) \le 1\cdot\exp(-0^{c}) = 1\cdot e^{0} = 1$), or about $N = 2, 3, 4$ (where $\log\log N < 0$ and the real power of a negative base takes the cosine-corrected value above). All such $N$ may simply lie below the threshold $N_0$.
• The hypothesis $5 \le k$ is satisfiable (e.g. $k = 5$), so the theorem is not vacuous on that count; the hypothesis appears nowhere in the conclusion except through the parameter $k$ of $r(k,N)$.
• The inequality is non-strict ($\le$), and $r(k,N)$ is compared to the bound after coercion into $\mathbb{R}$; no rounding or floor is applied to the right-hand side.
• The claim is an upper bound only. No lower bound on $r(k,N)$, no uniformity in $k$, and no explicit or effective value for $c$ or for the threshold $N_0$ is asserted.