Quantitative Superexponential Bounds for van der Waerden Numbers

Proof. Each factor in Equation (2.2) is at most 2M, and there are at most h_0 factors. If \ell^a\mid h\le2M, with \ell\le h_0, then a\le\floor{\log(2M)/\log\ell}. Thus the full \ell-primary part of h divides \lambda, and hence also \gcd(h,\lambda t). All prime divisors of s therefore exceed h_0. This proves the assertions, including the case t=0, for which s=1.□

Proof. Put n=k^2. For a prime \ell, write v_\ell(a) for the exponent of \ell in a positive integer a. Counting multiples of each power of \ell in the factorials gives

because each summand is 0 or 1 and vanishes for \ell^a>2n. If every prime factor of \binom{2n}{n} were at most k, its value would consequently be at most (2n)^k. On the other hand, the central binomial coefficient is the largest of the 2n+1 coefficients in (1+1)^{2n}, so

For n=k^2, the logarithm of this lower bound is k^2\log4-\log(2k^2+1), whereas that of (2n)^k is k\log(2k^2). The former is larger for all sufficiently large k. There is therefore a prime divisor P>k; it is at most 2n because it divides (2n)!.□

Proof. For large k we have \alpha\le1/4 and R\ge1. If \theta=R/m, the bounds k^2R\le m\le k^2R+1\le2k^2R give H/2\le\theta\le H. On either interval indexed by \ell in Equation (2.11), the quantity \rho(Y)+\alpha ranges, on the closure, between b=\alpha e^{\ell\theta} and be^\theta, while |I|=b(e^\theta-1). Hence

For 0\le\theta\le1, the outside expressions are bounded below by \theta/2 and above by 2\theta, respectively. This proves the first two inequalities in Equation (2.13); the last follows from \rho(Y)+\alpha\le3/4<1. Finally,

by Equation (2.4), so 2m\le2k^2R+2=O(k^3\log k).□

Proof. Fix Y_0\in\overline I and put r_0=\rho(Y_0)+\alpha. Every Y\in N(I) has circle distance at most 2w from Y_0. By Lemma 2.3 and the Lipschitz property of \rho,

where the last inequality holds for H\le1/8. Apply the lower width bound at a point of \overline J\cap N(I) to obtain

The arc N(I) has length 3w<1. In its linear ordering, successive mesh endpoints enclose a full mesh interval, of length at least w/16 by the assertion just proved. If there are b such endpoints, then (b-1)w/16\le3w, so b\le49.□

Proof. The portion of the arc on which \rho\ge\eta has at most two components. Within one component, successive mesh endpoints have spacing at least H\eta/4, by Lemma 2.3 applied at either endpoint of the intervening mesh interval. The number of mesh endpoints in these components is therefore at most 4H/(H\eta/4)+2=16/\eta+2. Add the at most two threshold points \rho=\eta. Inside \{\rho<\eta\} the output is constant, so no other endpoints are needed. This gives at most 16/\eta+4=16000D+4\le16004D breakpoints. At each breakpoint use the half-open convention for V and the weak inequality in Equation (2.14); this includes coincident mesh and threshold points.□

Proof. First count strict sign vectors. The complement of an arrangement has at most \sum_{j=0}^e\binom{s}{j} regions. Indeed, when a new hyperplane is added, every region it splits meets that hyperplane in a different region of the induced arrangement, whose dimension is at most e-1. Induction on s and e, followed by Pascal’s identity, gives the stated bound. Repeated hyperplanes create no additional regions. A strict sign set is convex, and therefore connected when nonempty, so each strict sign vector corresponds to one region.

Now consider a realized sign vector with zero entries, and let A be the affine intersection of its zero hyperplanes. If A has codimension d, then d of those equations with linearly independent normals already define A: consistency at a point of A makes every remaining zero equation a consequence of the selected equations. There are at most \binom{s}{d} ways to select them. On A, every hyperplane containing A has forced zero sign; the remaining hyperplanes impose strict signs in dimension e-d. The strict-region bound on A, and a sum over d, prove the first inequality in Equation (3.1). For each summand, \binom{s}{d}\binom{s}{j}\le(s+1)^{d+j}\le(s+1)^e; there are at most (e+1)^2 summands. Restricting the parameter space can only remove sign vectors.□

Proof. Consider any circle partition with F endpoints, including its representative cut, and freely choose a scalar start and step a,b\in[0,1). For 0\le j<k, the unreduced value a+jb belongs to [0,k). Represent the partition endpoints by numbers \tau\in[0,1). The interval containing (a+jb)\bmod1 is determined by its comparisons with all \tau+z for -1\le z\le k. The comparisons for all j use at most 3k^2F lines in the two parameters a,b. Equality signs give precisely the assigned half-open labels, so Lemma 3.1 bounds the number of scalar words by 9(3k^2F+1)^2.

Apply this bound separately in all 2D scalar coordinates, allowing their starts and steps to vary independently. This enlarges the collection of possible words, and is therefore an upper bound for the actual coordinate homomorphisms. We can take

Since \lambda\ge1, we have \log F=O(\log k+\log\lambda), and thus

This proves the first bound in Equation (3.2) with an absolute constant. The remaining bounds follow from Equation (2.6) and M\ge k^{1/2}.□

Proof. Fix t and a position z_0 at which the recorded pattern equals \beta. That position is regular. In each scalar coordinate, re-anchor the path at z_0: let a be the real representative of that coordinate at z_0, in the interval specified by \beta, and let b be its drift variable, either u_i or v_i. At a target position z, an unreduced representative is

as appropriate. The translation \tau_z is fixed once t,z_0,z,i are fixed. We retain only the restrictions on a,b implied at the anchor, since discarding other restrictions can only increase the number of outputs. The following three cases bound this number.

First-system coordinates. Here a ranges over an interval of length H_x and |b|\le H_x. Since |z-z_0|/h<1, the target range is contained in a fixed real interval of length at most 3H_x. The real lifts of U-endpoints form a lattice of spacing H_x, so at most four endpoints meet this range.

Stationary second-system coordinates. Write I=V(Y_{z_0,i}). The retained drift bound is |b|\le |I|, by the restriction at the regular anchor. Also \lambda t_i/h is integral, so the translation \tau_z is integral. Modulo one every target belongs to N(I) from Lemma 2.4, and at most 49 mesh endpoints are relevant. The unreduced target range lies in an interval of length at most 3|I|<1, so each relevant circle endpoint has at most one lift in that range.

Rotating second-system coordinates. The anchor interval has width at most 2H and the retained drift bound is |b|\le H. The target range has length at most 4H<1. Apply Lemma 2.5 to its image on the circle: at most 16004D breakpoints determine the truncated output V_\eta. Again each circle breakpoint has at most one lift in the real target range.

In each case, the enclosing target interval and the finite list of breakpoint lifts are fixed before a,b are varied. In particular, the magnitude of the fixed translation \tau_z introduces no factor in the count. Each comparison with a breakpoint lift is an affine line in (a,b). Taken over 0\le z<h, there are at most 16004Dh such lines per scalar coordinate. On the allowed parameter rectangle, their signs determine the scalar output at every target. They determine values at breakpoints as well as on open intervals; this accounts for half-open endpoints and for exact equalities \rho=\eta.

By Lemma 3.1 with e=2, the number of possible scalar output sequences is at most

for an absolute C_0. Take the product of these bounds for all 2D coordinates, truncating only rotating second-system coordinates. Those scalar outputs determine the complete recorded pattern: a position is dummy exactly when at least one rotating output is *; at all other positions the outputs specify the full label. No additional choice of a regular-position mask is needed.

There are h^D choices of t and at most h choices of the anchor z_0. Therefore the required number is at most

where the last inequality holds for an absolute C, since D\ge1. All eligible patterns containing \beta have at least one such anchor and are included in this count.□

Proof. For T\subseteq\mathcal E, write A_T=\bigcap_{F\in T}F^c. We prove simultaneously, by induction on |T|, that

For T=\varnothing, positivity is immediate and the conditional bound follows from Equation (4.1). Suppose the assertions are known for smaller sets. Removing any F\in T and applying the conditional bound gives

To prove the conditional bound for E\notin T, put T_1=T\cap\Gamma(E) and T_2=T\setminus T_1. If T_1=\varnothing, independence gives \Pp(E\mid A_T)=\Pp(E)\le z_E directly. Otherwise, order the members of T_1 and condition successively on their complements, starting with A_{T_2}. Each conditioning set has size at most |T|-1, so the induction hypothesis yields

Using independence from T_2 in the numerator, we obtain

The last inequality uses Equation (4.1) and T_1\subseteq\Gamma(E). This completes the induction; take T=\mathcal E for the conclusion.□

Proof. Assign to every \beta\in\cL an independent uniform random bit \xi_\beta. We introduce two finite families of bad events.

For the first family, take each distinct full-label word of a cyclic progression with L_0\ge\delta k light positions. Let w_{\max} be the largest multiplicity of a light label. Order the light positions by grouping equal labels together, with all choices fixed as functions of the word. Distribute the resulting list cyclically among w_{\max} rows. A group has at most w_{\max} positions, so a label occurs at most once in each row. Every row has at least

positions, because w_{\max}\le k/M. For each row let its bad event be that some bit occurs on strictly fewer than one quarter of its positions. There are at most kT_{\mathrm{glob}} such events in total, where T_{\mathrm{glob}} is the number in Lemma 3.2.

For the second family, take one event for each eligible recorded pattern and its discrete parameters h,t, where h_0<h\le2M. Its bad event is that some bit occurs on strictly fewer than one quarter of the regular positions. The tested labels are pairwise distinct by eligibility, and their number is at least h/2. Dummy positions use no variables. Although the realizations of the patterns have real parameters, these event families are finite: \cL, the word lengths, and the choices of h,t are all finite.

Each event E thus tests l(E) distinct independent label variables. If X is the number of ones among l=l(E) such variables, then

Indeed, (2j)!\ge2^j j! gives \cosh t\le e^{t^2/2} by termwise comparison of the power series. Markov’s inequality for the two deviations from l/2 consequently gives

The weak tail inequalities also cover the strict inequalities defining the bad events, regardless of divisibility of l by four.

Give E the weight z_E=e^{-l(E)/32}. By Lemma 3.2 and Equation (4.3), the total weight of all first-family events is at most

For a fixed label \beta, Lemma 3.4 bounds the second-family weight of events using \xi_\beta by

To see the last estimate uniformly, take C\ge1. The function \log(CDh)/h is decreasing for h\ge D^2 once D is large, and hence

For all sufficiently large k, each summand in the infinite sum in Equation (4.6) is therefore at most e^{-h/128}. Its tail tends to zero as D\to\infty.

It follows from Equations (4.5) and (4.6) that, uniformly over all labels \beta,

for all sufficiently large k. Join two distinct events whenever their supports share a label variable. Since all label bits are independent, this is a dependency graph of the kind required in Lemma 4.1; independence holds from the joint sigma-algebra of all nonneighbors. By summing Equation (4.7) over the l(E) labels used by E, we have

The lower bounds l(E)\ge\delta M-1 in the first family and l(E)\ge h/2>D^2/2 in the second ensure that l(E)\ge100 eventually. In particular z_E<1/2. Since \log(1-z)\ge-2z for 0\le z\le1/2, we obtain

For the second inequality, the positive difference 1/8-1/32-2/500 multiplied by 100 exceeds \log2. Thus Lemma 4.1 gives a choice of all label bits avoiding every bad event. Fix that choice as c_*. Summing the balanced row counts over the partition of the light positions proves part (i); the second event family gives part (ii). All estimates used absolute constants and depended only on k, so the threshold is absolute.□

Proof. For any j_1<j_2<j_3 in J, affinity modulo one implies that

In each coordinate its absolute value is at most 2H(j_3-j_1)\le2kH<1, so it is zero. Thus every triple has the same affine interpolation. If |J|\ge2, interpolate between its smallest and largest indices to obtain A,B; the triple identity places every remaining point on that interpolation. For at most two indices the conclusion follows directly, including the empty case.□

Proof. For large k, the inequality m_*>k/M gives m_*-1\ge k/(2M). Write j_-=\min J and j_+=\max J. The smallest of the m_*-1 consecutive gaps in J satisfies

All vectors (\hat x(n_j),\tilde y(n_j)), j\in J, lie in one full-label box, whose coordinate widths are at most 2H by Lemma 2.3. By Lemma 5.1, their differences are proportional to differences of indices. In particular the difference at the chosen gap h is h/(j_+-j_-) times the difference between the two extreme visits. The latter has first-coordinate absolute differences at most H_x and second-coordinate absolute differences at most 2H. This proves Equation (5.1).

The identity y=\lambda x on the torus implies v-\lambda u\in\Z^D. Since \lambda H_x=H,

for large k. Every coordinate of this integer vector is therefore zero.□

Proof. Since h x(d)=u modulo \Z^D, the vector t'=h\hat x(d)-u is integral. Reduce it coordinatewise modulo h to obtain t. The first equality in Equation (5.2) follows; multiplication by \lambda and the real identity v=\lambda u give the second.

Suppose an integer e>1 divides h and every t_i. It also divides every t'_i, because t'-t\in h\Z^D. Hence the torus displacements from index j' to index j'+h/e are u/e and v/e in the first and second systems. The vector

is a convex combination of the representatives at j' and j'+h. Their common full-label box is a product of half-open real intervals and is convex. This vector therefore lies in that same box and is the chosen representative of the sample at j'+h/e. It gives an additional visit to the label at a strictly smaller positive gap h/e, a contradiction. This proves the gcd assertion.

The torus vector t/h has order exactly h: if h divides all a t_i, the gcd assertion and Bézout’s identity imply h\mid a. Take any j_1,j_2\in\{0,\ldots,k-1\} incongruent modulo h. In at least one coordinate the rational displacement (j_1-j_2)t_i/h has circle distance at least 1/h from zero. The drift in that coordinate has absolute value at most

By the triangle inequality on the circle the actual displacement has distance at least

for sufficiently large k. Two samples in the same U interval have circle distance at most H_x, so these samples cannot have the same full label.□

Proof. Let the full label at j_* have multiplicity m'>k/M, and let j_- and j_+ be its extreme occurrence indices. By Lemma 5.3, j_+-j_-=a h for an integer m'-1\le a<k/h. Set L_i=|V(y_i(n_{j_*}))|. The real representative difference

has |\Delta_i|\le L_i\le2H. From Equation (5.2), it is congruent to a v_i modulo one. On the other hand,

for large k. The integer \Delta_i-a v_i is zero. Therefore

as claimed. This argument uses only the two endpoint representatives; it requires no assertion about the intervening path across a cut.□

Proof. If the progression has at least \delta k light positions, Proposition 4.2(i) supplies at least \delta k/4\ge\gamma k occurrences of each bit. We may therefore assume that fewer than \delta k positions are light. There is a heavy label, and Lemmas 5.2, 5.3 and 5.4 provide h,t,u,v with all the properties proved above.

Short periods. Suppose h\le h_0. The definition of the dilation gives h\mid\lambda. Thus the second path in Equation (5.2) has real step w=v/h modulo one, because \lambda t/h is integral. Its total coordinate motion satisfies

for large k. The congruence w_i=y_i(d) modulo one also gives w_i\in q^{-i}\Z: a representative of y_i(d) is an integral multiple of q^{-i}, and adding an integer preserves this lattice. In particular,

Consider the real segment \tilde y_i(n_0)+\tau w_i, 0\le\tau\le k-1. If the sampled centered representatives fail to equal \tilde y(n_0)+jw, some coordinate has w_i\ne0 and this closed segment meets a cut point in 1/2+\Z. The word closed includes a cut met at the initial or final sample, so both directions of motion and exact cut hits are covered. Each sampled point is then within real distance k|w_i| of such a cut point, giving \rho(y_i(n_j))\le k|w_i| for every j. By Lemma 2.3 and Equation (5.5),

Yet Equation (5.4) implies that any two distinct sampled points in this coordinate have circle distance |j-j'|\,|w_i|\ge|w_i|: the entire real displacement is less than one half. They cannot belong to a common V interval of width less than |w_i|. All full labels would therefore be distinct, contradicting the heavy label. Hence every sampled representative equals \tilde y(n_0)+jw, proving alternative (ii).

Longer periods. Suppose h_0<h\le2M. Partition the first h\floor{k/h} indices into consecutive full blocks of length h; the remaining block has fewer than h indices. A full block starting at j_0 has exactly the form in Definition 3.3, with starting points x(n_{j_0}),y(n_{j_0}) and the same h,t,u,v. We verify its regularity and, when it contains a heavy index, every condition of eligibility.

For a rotating coordinate i, let s_i=h/\gcd(h,\lambda t_i)>h_0. Without the drift, the h values

run through an equally spaced grid of s_i circle points, each exactly h/s_i times. The actual value at z is within |v_i|\le4MH/k<\eta of this grid value. If the actual position is nonregular in this coordinate, its grid value is within 2\eta of the cut. An arc of length 4\eta contains at most 4\eta s_i+1 points of an s_i-point grid. This bound remains valid when endpoints are included. Consequently the fraction of positions excluded by this coordinate is at most 4\eta+1/s_i. A union bound over rotating coordinates shows that the fraction of nonregular positions is at most

Thus each full block has at least h/2 regular positions. All labels within the block are distinct by Lemma 5.3, since its indices have distinct residues modulo h. Also |u_i|\le H_x and |v_i|\le H for all i by Equation (5.1), for sufficiently large k.

Now use any full block containing a heavy index j_*. Fix a stationary coordinate i and write I_*=V(y_i(n_{j_*})), L_*=|I_*|. Its rational step \lambda t_i/h is integral, so for every index j in the block,

For large k this places y_i(n_j) in the circular L_*-neighborhood of \overline{I_*}. Applying Lemma 2.4 with I=I_* and J=V(y_i(n_j)) gives

where the final inequality uses 2M/k\le1/16 and Equation (5.3). This holds at every block position, in particular at each regular position as eligibility requires. The heavy index j_* need not itself be regular: it serves only to provide the interval I_* and the relative drift estimate. The neighborhood statement uses closures, so a cut crossing or an endpoint equality causes no change in this verification.

Every full block containing a heavy index is therefore eligible. By Proposition 4.2(ii) and Equation (5.6), it contributes at least h/8 occurrences of each bit. A full block not used in this way consists entirely of light positions. Since fewer than \delta k positions are light in the entire progression, and fewer than h positions lie in the remainder, the used full blocks cover at least

positions for sufficiently large k, using h\le2M=o(k). Each bit consequently occurs at least k/10\ge\gamma k times. This proves alternative (i) and completes the dichotomy. All inequalities imposed only absolute lower bounds on k.□

Proof. First fix a second-system box, and let J be the indices whose centered representatives lie in that box. Every coordinate interval has width at most 2H, so Lemma 5.1 gives

for suitable A,B\in\R^D. The indices in J need not be consecutive. In particular, the points q\tilde y(n_j) lie on an affine line when |J|\ge2; when |J|\le1 the claimed multiplicity bound is immediate.

Any two distinct terms of the progression give points separated by Euclidean distance at least one after this scaling. To see this, the terms are distinct by Equation (2.7), and \lambda is a unit modulo q^D. Hence \lambda(n_j-n_{j'}) is a nonzero residue modulo q^D. Choose an integer representative z of this residue, and let a\in\{0,\ldots,D-1\} be the largest integer for which q^a\mid z. Divisibility by q^b, for b\le D, is unchanged upon adding a multiple of q^D, so this choice is intrinsic to the residue. Write z=q^a u; then q\nmid u. In coordinate a+1 the circle displacement is

The residue of u modulo q is one of 1,\ldots,q-1, whose distance from 0 on the circle after division by q is at least 1/q. This argument requires only q\nmid u; it does not require u to be a unit or q to be prime. The difference between any two real representatives has absolute value at least their circle distance. Consequently

If |J|\ge2, these separated points determine a nonconstant affine line \ell. Let z_0 be the point of \ell closest to the origin, and choose a unit vector e along \ell. Writing its points as z_0+te, with t\in\R, gives

because z_0 is orthogonal to e. For a fixed integer m\ge0, the band of the key is

If it is nonempty, then m+1-C'>0, and on the half-line t\ge0 it is contained in the closed interval with endpoints

The difference of the quantities under these square roots is at most one. For 0\le u\le v, the inequality (\sqrt v-\sqrt u)^2\le v-u therefore shows that this interval has length at most one. Reflection gives the same bound on t\le0. By Equation (6.2), each of these intervals contains at most two sampled points: three points in an interval of length at most one would have total separation at least two. Thus the key occurs at most four times. If the band reaches the nearest point z_0, counting t=0 in both halves only enlarges this upper bound. Replacing the half-open band by closed intervals also covers equality at either boundary, and the case of exactly two points needs no additional argument.□

Proof. On an affine progression write \tilde y(n_j)=A+jB. Then

where \theta_0=q^2\norm A_2^2, \theta_1=2q^2\langle A,B\rangle, and \theta_2=q^2\norm B_2^2. Moreover, since every coordinate of \tilde y(n_j) belongs to [-1/2,1/2),

Put B_*=\floor{Dq^2/4}+1. For each j\in\{0,\ldots,k-1\} and b\in\{0,\ldots,B_*\}, compare \theta_0+\theta_1j+\theta_2j^2 with b. These comparisons use at most k(B_*+1)\le k(Dq^2+2) affine hyperplanes in the three variables (\theta_0,\theta_1,\theta_2). Their joint signs, including equality, determine the complete word (\floor{f(n_j)})_{j<k} for all realized progressions. Lemma 3.1, in the fixed dimension three, therefore gives at most C\bigl(k(Dq^2+2)\bigr)^3 such words. Allowing all triples of coefficients, without imposing their geometric relations, can only increase this count.

A full-label word (L(n_j))_{j<k} determines the specific second-system boxes and, because c_* is fixed, every outer bit c_0(n_j). Together with the integer-part word just counted, it determines every entry of Equation (6.3). Multiplying the two counts proves Equation (6.4); no independence between the two words is asserted or needed.

For the logarithmic estimate, Lemma 3.2 bounds \log T_{\mathrm{glob}} by O(k^{3/10}\log k). Also Dq^2+2\le3Dq^2, so the remaining logarithm in Equation (6.4) is at most 6\log q+3\log k+3\log D+O(1). Equations (2.1) and (2.4) give

Since k^{9/10}\log k/k^{19/20}=k^{-1/20}\log k\to0, Equation (6.5) follows. The arrangement constant comes from dimension three, so it is independent of the growing dimension D.□

Proof. For each key \kappa\in\cK, take an independent Bernoulli bit E_\kappa with \Pp(E_\kappa=1)=p=k^{-1/20}, and define

Only this finite family of bits is random. In particular, positions with a common key use the very same bit, even if they have different outer colors. We may take k sufficiently large that p<1/2.

First consider a progression containing at least \gamma k of each outer color, where \gamma=1/100. Fix a target color b\in\{0,1\}. Every position with c_0(n_j)=1-b must have E_{\kappa(n_j)}=1 for the whole progression to receive color b. By Lemma 6.1, these positions specify at least \gamma k/4 distinct keys. This set of keys is determined before the bits are sampled. Thus independence between distinct keys gives

If some key also occurs at a position with outer color b, the prescriptions for that key conflict and this probability is zero, which obeys the same bound. There is no choice of a subset of keys to count: all keys requiring a flip are already specified by the progression and the target color.

There are fewer than |G|^2=q^{2D} choices of (n_0,d) with d\ne0. A union bound over these choices and the two target colors bounds the probability R_k that any such progression becomes monochromatic by

Here the coefficient is explicitly

As D=O(k^{1/10}), the other terms in the exponent are O(k^{1/10}\log k)=o(k\log k). Hence R_k=o(1).

Next fix a signature realized by an affine progression, and again fix the target color b. For each entry (c_j,\kappa_j) of this signature, monochromaticity prescribes

Inconsistent prescriptions give an empty event. Otherwise, if there are s distinct keys and u of them are prescribed the value one, independence gives its probability exactly p^u(1-p)^{s-u}. By Lemma 6.1, s\ge k/4, and since p\le1-p this is at most

Two progressions with the same literal signature impose precisely the same prescriptions on the same random variables. They therefore define the same event for this target color and need be counted only once. Consequently the probability A_k of a monochromatic affine progression satisfies

using Lemma 6.2 and 1-p\le e^{-p}. Neither union bound requires independence between different progressions or signatures.

By Theorem 5.5, every nonzero-step cyclic progression is covered by the first case or the affine case. The cases may overlap, which only enlarges their combined bound. Thus the probability that any such progression is monochromatic is at most R_k+A_k=o(1). For all sufficiently large k this sum is less than one, so a choice of the bits gives the asserted coloring. All preceding thresholds and constants depend only on the fixed numerical parameters, and the bound in Equation (2.4) is uniform over every prime P allowed by Lemma 2.2. A single absolute K_0 therefore works for every integer k\ge K_0. Finally, q\ge k^{ck/D} gives N=q^D\ge k^{ck}.□

Proof. For 0\le n<N^m, write its base-N expansion as

and assign the color

Here and below a digit is identified with its residue modulo the base. Suppose that a,a+d,\ldots,a+(k-1)d is a monochromatic progression in this interval, with d>0. Since k\ge2, we have d<N^m. There is therefore a largest integer i\in\{0,\ldots,m-1\} for which N^i\mid d. Put e=d/N^i, so that N\nmid e. For every j\in\{0,\ldots,k-1\}, the exact identity

holds because je is an integer. Reducing Equation (7.1) modulo N shows that the ith digits form a cyclic progression with nonzero step e\pmod N. Monochromaticity of the color tuples would make C constant on that progression, a contradiction.

Translation by one now gives a coloring of [N^m] with 2^m colors and no monochromatic k-term progression. This proves the first assertion. For the second, take m=\lfloor\log_2r\rfloor\ge1 and embed the at most 2^m\le r color tuples into [r].□

Proof of Theorem 1.1. Theorem 6.3 supplies, for every integer k above an absolute threshold, such a cyclic coloring with

Proposition 7.1 gives, simultaneously for every integer r\ge2,

The threshold on k was fixed before r was introduced, so it is absolute and uniform in the number of colors.□

Proof. Set

Both are positive, and b\ge2. Partition the digit set \{0,\ldots,b-1\} into

and let h(u)\in\{0,1\} record the half containing u. An integer 0\le n<b^s has a unique digit vector x=(x_0,\ldots,x_{s-1}) with n=\sum_{i=0}^{s-1}x_i b^i. Give it the color

There are at most 2^s(1+s(b-1)^2)\le2^s(1+sb^2) such colors. For every integer s\ge1 we have s+1\le2^s, while 2^s\le r^{1/4} and b^2\le r^{1/2}. Hence

We show that this coloring contains no nonconstant monochromatic three-term progression. Suppose that three equally spaced integers have digit vectors x,y,z and the same color. Their midpoint relation is

For each i, the three digits x_i,y_i,z_i lie in one half H_0 or H_1. Each half has diameter at most \lceil b/2\rceil-1, so

In particular this absolute value is strictly less than b. Reducing Equation (7.4) modulo b forces its zeroth coefficient to be zero: it is divisible by b and has absolute value less than b. Dividing by b and repeating proves x_i-2y_i+z_i=0 for every i. Thus x+z=2y in \R^s. Equality of the final entries in Equation (7.2) also gives \norm{x}_2^2=\norm{y}_2^2=\norm{z}_2^2, and therefore

It follows that x=y=z, so the original three integers were equal. This excludes every progression with positive difference and length k\ge3, since its first three terms would already give a forbidden triple. After translating the interval by one and using Equation (7.3), we obtain W_r(k)>b^s.

Finally let L=\log r\ge8\log2. Since \lfloor u\rfloor\ge u/2 for u\ge1, the parameter choices give

Consequently \log(b^s)\ge L^2/(64\log2), proving the stated bound for every r\ge256, independently of k\ge3.□

Proof. For r\ge2, the inequality \lfloor\log_2r\rfloor\ge(\log r)/(2\log2) and Theorem 1.1 give, for all k\ge K_0,

Theorem 7.2 gives, for all r\ge256,

The right-hand sides tend to infinity. For fixed r\ge2, Theorem 1.1 also gives W_r(k)^{1/k}>k^{c\lfloor\log_2r\rfloor}\to\infty. For fixed A>0, Theorem 7.2 gives

uniformly for integers k\ge3.□

Proof. The recursion is well founded: construct all F(r,k) at a given length k after constructing them for every number of colors at length k-1. Each of the r steps in Equation (A.1) then uses finite positive integers.

A one-term progression is a singleton, so W_r(1)=1. Any r-coloring of [r+1] has two positions of the same color, and those positions form a two-term progression with positive difference. An injective coloring of [r] shows that W_r(2)=r+1. Also, in one color [k] contains a k-term progression and [k-1] does not, proving W_1(k)=k.

It remains to prove the asserted upper bound for k\ge3. We induct on k, simultaneously for all r, with the induction statement that every r-coloring of an interval of F(r,k) consecutive integers contains a monochromatic k-term progression. The preceding paragraph proves the cases k=1,2. Fix k\ge3, assume the statement at length k-1 for every color count, and fix r\ge1.

For the inner induction, a focus with t colors in a colored interval consists of a point f of that interval and positive integers d_1,\ldots,d_t such that all the points

belong to the interval, and, for each i, the k-1 points indexed by i have a common color a_i, with a_1,\ldots,a_t pairwise distinct. In an interval containing no monochromatic k-term progression, the focus itself must have a color different from each a_i: otherwise the corresponding points, in increasing order, together with f form such a progression of difference d_i>0.

We claim, by induction on t\in\{0,\ldots,r\}, that every r-coloring of an interval of length m_t containing no monochromatic k-term progression has a focus with t colors. For t=0 this just means choosing the single point in an interval of length m_0=1.

Assume the claim for t<r, and put

By translating, we may work with an avoiding coloring \chi of [2mB]. Partition it into 2B consecutive blocks of length m, and associate to block j the word

There are at most r^m different words. Apply the outer induction hypothesis at length k-1 and color count r^m to the word coloring of the first B block indices. We obtain integers b,\Delta\ge1 such that

Since k-2\ge1, we have \Delta\le B-1. Thus the next index

is still one of the allocated blocks. Its word need not agree with the preceding words.

The common word in Equation (A.2), regarded as a coloring of [m], contains no monochromatic k-term progression, since such a progression would also occur inside block b. Apply the inner induction hypothesis to this word. Let f\in[m] be its focus, with differences d_1,\ldots,d_t and distinct arm colors a_1,\ldots,a_t. Let a_0 be the color at its position f; as observed above, a_0 is distinct from all a_i.

Take position f in block q as the new focus, namely

For each i\in\{1,\ldots,t\} and s\in\{1,\ldots,k-1\},

The block on the right is one of the matching blocks, and the within-block position f-sd_i belongs to [m]. Consequently these points all have color a_i for fixed i. There is one more arm:

whose points all have color a_0. All t+1 arm differences are positive, all arm points are in the interval, and their colors are pairwise distinct. Together with Equation (A.3), this proves that f' is a focus with t+1 colors, completing the inner induction.

At t=r, an avoiding coloring of [m_r] would have a focus whose arms use r distinct colors. Its own color would have to avoid all of them, which is impossible in an r-coloring. Hence every such coloring contains a monochromatic k-term progression, completing the outer induction. In particular W_r(k) exists and is at most F(r,k).□