Proof. Each factor in [setup:dilation-definition] 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\left\lfloor\log(2M)/\log\ell\right\rfloor\). 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 \[v_\ell\binom{2n}{n} =\sum_{a\ge1}\left(\left\lfloor\frac{2n}{\ell^a}\right\rfloor -2\left\lfloor\frac n{\ell^a}\right\rfloor\right) \le\left\lfloor\log_\ell(2n)\right\rfloor,\] 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 \[\binom{2n}{n}\ge\frac{4^n}{2n+1}.\] 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 [mesh:intervals], 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 \[1-e^{-\theta}\le\frac{|I|}{\rho(Y)+\alpha}\le e^\theta-1.\] 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 [mesh:width-bounds]; the last follows from \(\rho(Y)+\alpha\le3/4<1\). Finally, \[R\le(D+1)\log q=O(k\log k)\] by [setup:q-bounds], 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 4 and the Lipschitz property of \(\rho\), \[\rho(Y)+\alpha\ge r_0-2w\ge(1-4H)r_0\ge r_0/2,\] 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 \[|J|\ge\frac18Hr_0\ge\frac{w}{16}.\] 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 4 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 [mesh:truncation-definition]; 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 [count:arrangement-bound]. 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 7 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 \[F=|U|+|V|=k^2\lambda+O(k^3\log k).\] Since \(\lambda\ge1\), we have \(\log F=O(\log k+\log\lambda)\), and thus \[T_{\mathrm{glob}}\le\bigl[9(3k^2F+1)^2\bigr]^{2D}.\] This proves the first bound in [count:global-bound] with an absolute constant. The remaining bounds follow from [setup:orders] 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 \[ a+\tau_z+\frac{z-z_0}{h}b, \qquad \tau_z=\frac{(z-z_0)t_i}{h} \quad\hbox{or}\quad \tau_z=\frac{(z-z_0)\lambda t_i}{h}, \tag{20}\] 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 5, 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 6 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 7 with \(e=2\), the number of possible scalar output sequences is at most \[9(16004Dh+1)^2\le C_0(Dh)^2\] 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 \[h^{D+1}\bigl[C_0(Dh)^2\bigr]^{2D} =C_0^{2D}D^{4D}h^{5D+1} \le(CDh)^{6D},\] 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 \[ \mathbb P(A_T)>0, \qquad \mathbb P(E\mid A_T)\le z_E\quad\text{for every }E\notin T. \tag{22}\] For \(T=\varnothing\), positivity is immediate and the conditional bound follows from [outer:lll-condition]. Suppose the assertions are known for smaller sets. Removing any \(F\in T\) and applying the conditional bound gives \[\mathbb P(A_T)=\mathbb P(A_{T\setminus\{F\}}) \bigl(1-\mathbb P(F\mid A_{T\setminus\{F\}})\bigr)>0.\] 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 \(\mathbb P(E\mid A_T)=\mathbb P(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 \[\mathbb P(A_{T_1}\mid A_{T_2}) \ge\prod_{F\in T_1}(1-z_F).\] Using independence from \(T_2\) in the numerator, we obtain \[\mathbb P(E\mid A_T) \le\frac{\mathbb P(E\mid A_{T_2})} {\mathbb P(A_{T_1}\mid A_{T_2})} \le\frac{\mathbb P(E)}{\prod_{F\in T_1}(1-z_F)} \le z_E.\] The last inequality uses [outer:lll-condition] and \(T_1\subseteq\Gamma(E)\). This completes the induction; take \(T=\mathcal E\) for the conclusion. ◻

Proof. Assign to every \(\beta\in\mathcal L\) 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 \[ \left\lfloor\frac{L_0}{w_{\max}}\right\rfloor \ge\delta M-1 \tag{23}\] 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 8.

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: \(\mathcal L\), 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 \[\mathbb Ee^{\pm(X-l/2)}=(\cosh(1/2))^l\le e^{l/8}.\] 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 \[ \mathbb P(E) \le\mathbb P(X-l/2\le-l/4)+\mathbb P(X-l/2\ge l/4) \le2e^{-l(E)/8}. \tag{24}\] 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 [count:global,outer:row-size], the total weight of all first-family events is at most \[ kT_{\mathrm{glob}}e^{-(\delta M-1)/32}=o(1). \tag{25}\] For a fixed label \(\beta\), 10 bounds the second-family weight of events using \(\xi_\beta\) by \[ \sum_{h_0<h\le2M}(CDh)^{6D}e^{-h/64} \le\sum_{h>D^2}(CDh)^{6D}e^{-h/64}=o(1). \tag{26}\] 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 \[\sup_{h>D^2}\frac{6D\log(CDh)}{h} \le\frac{6\log(CD^3)}{D}=o(1).\] For all sufficiently large \(k\), each summand in the infinite sum in [outer:second-weight] is therefore at most \(e^{-h/128}\). Its tail tends to zero as \(D\to\infty\).

It follows from [outer:first-weight,outer:second-weight] that, uniformly over all labels \(\beta\), \[ \sum_{E:\,\xi_\beta\text{ is used by }E}z_E\le\frac1{500} \tag{27}\] 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 11; independence holds from the joint sigma-algebra of all nonneighbors. By summing [outer:incident-weight] over the \(l(E)\) labels used by \(E\), we have \[\sum_{F\in\Gamma(E)}z_F\le\frac{l(E)}{500}.\] 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 \[\begin{align*} z_E\prod_{F\in\Gamma(E)}(1-z_F) &\ge\exp\!\left[-\left(\frac1{32}+\frac2{500}\right)l(E)\right] \\ &\ge2e^{-l(E)/8}\ge\mathbb P(E). \tag{28}\end{align*}\] For the second inequality, the positive difference \(1/8-1/32-2/500\) multiplied by \(100\) exceeds \(\log2\). Thus 11 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 \[(j_3-j_2)(Z_{j_2}-Z_{j_1}) -(j_2-j_1)(Z_{j_3}-Z_{j_2})\in\mathbb Z^e.\] 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 \[h\le\frac{j_+-j_-}{m_*-1}\le\frac{k-1}{m_*-1}\le2M.\] 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 4. By 13, 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 [dichotomy:drift-bounds].

The identity \(y=\lambda x\) on the torus implies \(v-\lambda u\in\mathbb Z^D\). Since \(\lambda H_x=H\), \[|v_i-\lambda u_i|\le\frac{6MH}{k}<1\] for large \(k\). Every coordinate of this integer vector is therefore zero. ◻

Proof. Since \(h x(d)=u\) modulo \(\mathbb Z^D\), the vector \(t'=h\hat x(d)-u\) is integral. Reduce it coordinatewise modulo \(h\) to obtain \(t\). The first equality in [dichotomy:path-equations] 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\mathbb 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 \[(\hat x(n_{j'}),\tilde y(n_{j'}))+\frac1e(u,v)\] 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 \[\frac{k|u_i|}{h}\le\frac{2MH_x}{h}\le\frac{2MH}{h}.\] By the triangle inequality on the circle the actual displacement has distance at least \[\frac{1-2MH}{h}\ge\frac{1-2MH}{2M}>H\ge H_x\] 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 15, \(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 \[\Delta_i=\tilde y_i(n_{j_+})-\tilde y_i(n_{j_-})\] has \(|\Delta_i|\le L_i\le2H\). From [dichotomy:path-equations], it is congruent to \(a v_i\) modulo one. On the other hand, \[|a v_i|\le\frac{4MH}{h},\qquad |\Delta_i-a v_i|\le2H+\frac{4MH}{h}<1\] for large \(k\). The integer \(\Delta_i-a v_i\) is zero. Therefore \[|v_i|\le\frac{L_i}{a}\le\frac{L_i}{m'-1} \le\frac{2M}{k}L_i,\] 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, 12(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 [dichotomy:drift,dichotomy:path,dichotomy:heavy-width] provide \(h,t,u,v\) with all the properties proved above.

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 13 gives \[\tilde y(n_j)=A+jB\qquad(j\in J)\] for suitable \(A,B\in\mathbb 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 [setup:cyclic], 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 \[y_{a+1}(n_j)-y_{a+1}(n_{j'})=\frac{u}{q}\pmod1.\] 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 \[ \left\lVert q\tilde y(n_j)-q\tilde y(n_{j'})\right\rVert_2\ge1 \qquad(j\ne j'). \tag{37}\]

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\mathbb R\), gives \[\left\lVert z_0+te\right\rVert_2^2=t^2+C',\qquad C'=\left\lVert z_0\right\rVert_2^2\ge0,\] because \(z_0\) is orthogonal to \(e\). For a fixed integer \(m\ge0\), the band of the key is \[m\le t^2+C'<m+1.\] 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 \[\sqrt{\max\{0,m-C'\}},\qquad \sqrt{m+1-C'}.\] 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 [perturb:separation], 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 \[f(n_j)=q^2\left\lVert A+jB\right\rVert_2^2 =\theta_0+\theta_1j+\theta_2j^2,\] where \(\theta_0=q^2\left\lVert A\right\rVert_2^2\), \(\theta_1=2q^2\langle A,B\rangle\), and \(\theta_2=q^2\left\lVert B\right\rVert_2^2\). Moreover, since every coordinate of \(\tilde y(n_j)\) belongs to \([-1/2,1/2)\), \[0\le f(n_j)\le Dq^2/4\qquad(0\le j<k).\] Put \(B_*=\left\lfloor Dq^2/4\right\rfloor+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 \((\left\lfloor f(n_j)\right\rfloor)_{j<k}\) for all realized progressions. 7, 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 [perturb:signature]. Multiplying the two counts proves [perturb:signature-count]; no independence between the two words is asserted or needed.

For the logarithmic estimate, 8 bounds \(\log T_{\mathrm{glob}}\) by \(O(k^{3/10}\log k)\). Also \(Dq^2+2\le3Dq^2\), so the remaining logarithm in [perturb:signature-count] is at most \(6\log q+3\log k+3\log D+O(1)\). [setup:parameters,setup:q-bounds] give \[\log q\le \frac{ck}{D}\log k+\log(2k^2) =O(k^{9/10}\log k), \qquad pk=k^{19/20}.\] Since \(k^{9/10}\log k/k^{19/20}=k^{-1/20}\log k\to0\), [perturb:entropy] follows. The arrangement constant comes from dimension three, so it is independent of the growing dimension \(D\). ◻

Proof. For each key \(\kappa\in\mathcal K\), take an independent Bernoulli bit \(E_\kappa\) with \(\mathbb P(E_\kappa=1)=p=k^{-1/20}\), and define \[ C(n)=c_0(n)+E_{\kappa(n)}\pmod2. \tag{41}\] 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 18, 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 \[\mathbb P\bigl(C(n_j)=b\text{ for all }j<k\bigr) \le p^{\gamma k/4}.\] 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 \[ \begin{aligned} R_k&\le 2q^{2D}p^{\gamma k/4}\\ &\le\exp\!\left( \left(2c-\frac{\gamma}{80}\right)k\log k +2D\log(2k^2)+\log2\right). \end{aligned} \tag{42}\] Here the coefficient is explicitly \[ 2c-\frac{\gamma}{80} =\frac{1}{50000}-\frac{1}{8000} =-\frac{21}{200000}<0. \tag{43}\] 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 \[E_{\kappa_j}=b-c_j\pmod2.\] 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 18, \(s\ge k/4\), and since \(p\le1-p\) this is at most \[(1-p)^s\le(1-p)^{k/4}.\] 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 \[ \begin{aligned} A_k&\le2T_{\mathrm{aff}}(1-p)^{k/4}\\ &\le2\max\{1,T_{\mathrm{aff}}\}\exp(-pk/4) =\exp\bigl(-pk/4+o(pk)\bigr)=o(1), \end{aligned} \tag{44}\] using 19 and \(1-p\le e^{-p}\). Neither union bound requires independence between different progressions or signatures.

By 17, 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 [setup:q-bounds] is uniform over every prime \(P\) allowed by 3. 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 \[n=\sum_{i=0}^{m-1}n_iN^i,\qquad 0\le n_i<N,\] and assign the color \[\bigl(C(n_0),\ldots,C(n_{m-1})\bigr)\in\{0,1\}^m.\] 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 \[ \left\lfloor\frac{a+jd}{N^i}\right\rfloor =\left\lfloor\frac a{N^i}\right\rfloor+je \tag{45}\] holds because \(je\) is an integer. Reducing Equation (45) modulo \(N\) shows that the \(i\)th 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. Theorem 20 supplies, for every integer \(k\) above an absolute threshold, such a cyclic coloring with \[N=q^D\ge k^{ck},\qquad c=10^{-5}.\] Proposition 21 gives, simultaneously for every integer \(r\ge2\), \[W_r(k)>N^{\lfloor\log_2r\rfloor} \ge k^{ck\lfloor\log_2r\rfloor}.\] The threshold on \(k\) was fixed before \(r\) was introduced, so it is absolute and uniform in the number of colors. ◻

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 (49) 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 \[f-sd_i,\qquad 1\le s\le k-1,\quad 1\le i\le t,\] 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 \[m=m_t,\qquad B=F(r^m,k-1),\qquad m_{t+1}=2mB.\] 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 \[w_j=\bigl(\chi((j-1)m+1),\ldots,\chi(jm)\bigr).\] 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 \[ w_b=w_{b+\Delta}=\cdots=w_{b+(k-2)\Delta},\qquad b+(k-2)\Delta\le B. \tag{50}\] Since \(k-2\ge1\), we have \(\Delta\le B-1\). Thus the next index \[ q=b+(k-1)\Delta \le B+\Delta\le2B-1<2B \tag{51}\] is still one of the allocated blocks. Its word need not agree with the preceding words.

The common word in Equation (50), 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 \[f'=(q-1)m+f.\] For each \(i\in\{1,\ldots,t\}\) and \(s\in\{1,\ldots,k-1\}\), \[\begin{align*} f'-s(m\Delta+d_i) &=\bigl(b+(k-1-s)\Delta-1\bigr)m+(f-sd_i). \end{align*}\] 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: \[f'-sm\Delta =\bigl(b+(k-1-s)\Delta-1\bigr)m+f, \qquad 1\le s\le k-1,\] 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 (51), 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)\). ◻