Ceiling-aware bounds and a carry-free density Hales-Jewett construction

Definitions and mathematical statement

Fix a real number $0<\alpha<1$ and an integer $k\ge3$. A nontrivial $\ell$-term arithmetic progression in the integers is $\{a,a+d,\ldots,a+(\ell-1)d\}$ with integer $d>0$. Seek a finite nonempty set $S\subseteq\mathbb Z$ with the following two properties: every subset $X\subseteq S$ of size at least $\alpha|S|$ contains a $k$-term progression, while $S$ itself contains no $(k+1)$-term progression. Define the least possible cardinality by \[ m(\alpha,k)=\min\left\{|S|: \begin{array}{l} S\subseteq\mathbb Z\text{ finite and nonempty},\\ S\text{ has no }(k+1)\text{-term progression},\\ |X|\ge\alpha|S|\Rightarrow X\text{ has a }k\text{-term progression} \text{ for every }X\subseteq S \end{array}\right\}. \] If the eligible family were empty, interpret the minimum as infinity. The problem asks for effective and sharp estimates on this function in terms of both parameters.

The density threshold is an integer condition $|X|\ge\lceil\alpha|S|\rceil$. If $r_k(S)$ denotes the largest cardinality of a $k$-progression-free subset of $S$, the first condition is exactly $r_k(S)<\alpha|S|$; the inequality is strict. The progression-free requirement on $S$ concerns the longer length $k+1$, and all progressions are tested at arbitrary positive integer differences. No diameter bound is imposed. Thus the target measures how few integers can support unavoidable shorter progressions in every dense subset while still avoiding the next longer length.

Short English statement

How small can a set be if it avoids progressions of length k+1 but every subset of relative size at least alpha contains one of length k?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001092 (AIM-COMBINATORICS-0217), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Recent trends in additive combinatorics, item 1.11. Original workshop question underlying AIM-COMBINATORICS-0217. https://aimath.org/WWN/additivecomb/additivecomb.pdf.