We prove
L265
in the notation of its statement. For a set Y let C(Y) be the set of
colors occurring on D(Y). The proof is author-recorded by Plasma AI.
Lemma 1 (refinement). If a coloring of [1,N] has property (B), every
Bohr cell Y in {0,…,N} satisfies ∣Y∣≤q∣C(Y)∣.
Proof. Start from Y0=Y. Given a cell Yj with ∣Yj∣≥2, take the
color ij∈C(Yj) and the frequency θj that property (B)
supplies. Of the q half-open arcs of length 1/q covering
R/Z, one arc J has
∣Yj∩{y:{θjy}∈J}∣≥∣Yj∣/q; let Yj+1 be that set.
It is a Bohr cell, since 1/q≤ρ. Its differences satisfy
∥θjx∥<1/q≤ρ, so they avoid color ij, and
C(Yj+1)⊆C(Yj)∖{ij}. Every element of D(Yj)
is colored, so a cell with at least two points has C(Yj) nonempty.
Hence the process stops at some T≤∣C(Y)∣ with ∣YT∣≤1, and
∣Y∣≤qT∣YT∣≤q∣C(Y)∣. □
Proof of (1). Take a coloring of [1,S(k)] by at most k colors with no
monochromatic x+y=z. By hypothesis it has property (B). The set
{0,…,S(k)} is a Bohr cell (the case r=0), and its differences
carry at most k colors, so Lemma 1 gives S(k)+1≤qk. □
Lemma 2 (digit cubes). Let b≥4 and
ιb(v)=∑i=1rvibi−1 for v∈{−1,0,1}r.
- ιb is injective, ιb(v)>0 exactly when v∈Qr+, and
ιb(Qr+)⊆[1,br−1].
- For v,w,u∈Qr+, ιb(v)+ιb(w)=ιb(u) if and only if
v+w=u.
- If b=q+1, the digit cube Yr={ιb(δ):δ∈{0,1}r}
equals ${y\in{0,\ldots,b^r-1}:{y/b^l}\in[0,1/q)\text{ for }
l=1,\ldots,r}$, and D(Yr)=ιb(Qr+).
Proof. A relation ∑icibi−1=0 with ∣ci∣≤3<b forces every
ci=0, because the lowest nonzero ci would be divisible by b. This
gives injectivity, and part 2, since v+w−u has entries in [−3,3]. The
last nonzero term of ιb(v) dominates the others, because
bj−1>∑i<jbi−1; this gives the sign and the range. For part 3
let d0,d1,… be the base-b digits of y. Then
{y/bl}=(dl−1+{y/bl−1})/b, which is below 1/q exactly when
dl−1+{y/bl−1}<b/q=1+1/q. Since 1+1/q<2, induction on l shows
that all r conditions hold exactly when every digit is 0 or 1; a
finite sum of distinct powers b−j stays below 1/(b−1)=1/q.
Differences of vectors in {0,1}r are exactly the vectors in
{−1,0,1}r, and part 1 identifies the positive ones. □
Proof of (2). Fix r≥1 and a coloring γ of Qr+ by
χr colors with no monochromatic triple. Put b=q+1≥4 and
N=br−1. Color x=ιb(v) by γ(v) for v∈Qr+, and color
every other x∈[1,N] by the restriction of a coloring of [1,N] with no
monochromatic x+y=z, using a disjoint palette. A monochromatic solution
of x+y=z in the first palette has all three terms in ιb(Qr+),
so by Lemma 2(2) it is a monochromatic triple of γ, which does not
exist; in the second palette it would be monochromatic for the restricted
coloring. So the coloring has no monochromatic x+y=z, and by hypothesis
it has property (B). By Lemma 2(3), Yr is a Bohr cell with arcs of
length 1/q≤ρ, ∣Yr∣=2r, and D(Yr)=ιb(Qr+) carries at
most χr colors. Lemma 1 gives 2r≤qχr, that is,
χr≥rlog2/logq. □
The same argument with property (B) required only for cells with
∣Y∣≥A∣C(Y)∣, for some A≥1, gives S(k)+1≤max(q,A)k and
χr≥rlog2/logmax(q,A): run the refinement only while
∣Yj∣≥max(2,A∣C(Yj)∣), and at the stopping time
∣Y∣≤qTmax(1,A∣C(Y)∣−T)≤max(q,A)∣C(Y)∣.