Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


We prove L265 in the notation of its statement. For a set YY let C(Y)C(Y) be the set of colors occurring on D(Y)D(Y). The proof is author-recorded by Plasma AI.

Lemma 1 (refinement). If a coloring of [1,N][1,N] has property (B), every Bohr cell YY in {0,…,N}\{0,\ldots,N\} satisfies ∣Y∣≤q∣C(Y)∣|Y|\le q^{|C(Y)|}.

Proof. Start from Y0=YY_0=Y. Given a cell YjY_j with ∣Yj∣≥2|Y_j|\ge2, take the color ij∈C(Yj)i_j\in C(Y_j) and the frequency θj\theta_j that property (B) supplies. Of the qq half-open arcs of length 1/q1/q covering R/Z\mathbb R/\mathbb Z, one arc JJ has ∣Yj∩{y:{θjy}∈J}∣≥∣Yj∣/q|Y_j\cap\{y:\{\theta_jy\}\in J\}|\ge|Y_j|/q; let Yj+1Y_{j+1} be that set. It is a Bohr cell, since 1/q≤ρ1/q\le\rho. Its differences satisfy ∥θjx∥<1/q≤ρ\|\theta_jx\|<1/q\le\rho, so they avoid color iji_j, and C(Yj+1)⊆C(Yj)∖{ij}C(Y_{j+1})\subseteq C(Y_j)\setminus\{i_j\}. Every element of D(Yj)D(Y_j) is colored, so a cell with at least two points has C(Yj)C(Y_j) nonempty. Hence the process stops at some T≤∣C(Y)∣T\le|C(Y)| with ∣YT∣≤1|Y_T|\le1, and ∣Y∣≤qT∣YT∣≤q∣C(Y)∣|Y|\le q^T|Y_T|\le q^{|C(Y)|}. □\square

Proof of (1). Take a coloring of [1,S(k)][1,S(k)] by at most kk colors with no monochromatic x+y=zx+y=z. By hypothesis it has property (B). The set {0,…,S(k)}\{0,\ldots,S(k)\} is a Bohr cell (the case r=0r=0), and its differences carry at most kk colors, so Lemma 1 gives S(k)+1≤qkS(k)+1\le q^k. □\square

Lemma 2 (digit cubes). Let b≥4b\ge4 and ιb(v)=∑i=1rvibi−1\iota_b(v)=\sum_{i=1}^rv_ib^{i-1} for v∈{−1,0,1}rv\in\{-1,0,1\}^r.

  1. ιb\iota_b is injective, ιb(v)>0\iota_b(v)>0 exactly when v∈Qr+v\in Q_r^+, and ιb(Qr+)⊆[1,br−1]\iota_b(Q_r^+)\subseteq[1,b^r-1].
  2. For v,w,u∈Qr+v,w,u\in Q_r^+, ιb(v)+ιb(w)=ιb(u)\iota_b(v)+\iota_b(w)=\iota_b(u) if and only if v+w=uv+w=u.
  3. If b=q+1b=q+1, the digit cube Yr={ιb(δ):δ∈{0,1}r}Y_r=\{\iota_b(\delta):\delta\in\{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+)D(Y_r)=\iota_b(Q_r^+).

Proof. A relation ∑icibi−1=0\sum_ic_ib^{i-1}=0 with ∣ci∣≤3<b|c_i|\le3<b forces every ci=0c_i=0, because the lowest nonzero cic_i would be divisible by bb. This gives injectivity, and part 2, since v+w−uv+w-u has entries in [−3,3][-3,3]. The last nonzero term of ιb(v)\iota_b(v) dominates the others, because bj−1>∑i<jbi−1b^{j-1}>\sum_{i<j}b^{i-1}; this gives the sign and the range. For part 3 let d0,d1,…d_0,d_1,\ldots be the base-bb digits of yy. Then {y/bl}=(dl−1+{y/bl−1})/b\{y/b^l\}=(d_{l-1}+\{y/b^{l-1}\})/b, which is below 1/q1/q exactly when dl−1+{y/bl−1}<b/q=1+1/qd_{l-1}+\{y/b^{l-1}\}<b/q=1+1/q. Since 1+1/q<21+1/q<2, induction on ll shows that all rr conditions hold exactly when every digit is 00 or 11; a finite sum of distinct powers b−jb^{-j} stays below 1/(b−1)=1/q1/(b-1)=1/q. Differences of vectors in {0,1}r\{0,1\}^r are exactly the vectors in {−1,0,1}r\{-1,0,1\}^r, and part 1 identifies the positive ones. □\square

Proof of (2). Fix r≥1r\ge1 and a coloring γ\gamma of Qr+Q_r^+ by χr\chi_r colors with no monochromatic triple. Put b=q+1≥4b=q+1\ge4 and N=br−1N=b^r-1. Color x=ιb(v)x=\iota_b(v) by γ(v)\gamma(v) for v∈Qr+v\in Q_r^+, and color every other x∈[1,N]x\in[1,N] by the restriction of a coloring of [1,N][1,N] with no monochromatic x+y=zx+y=z, using a disjoint palette. A monochromatic solution of x+y=zx+y=z in the first palette has all three terms in ιb(Qr+)\iota_b(Q_r^+), so by Lemma 2(2) it is a monochromatic triple of γ\gamma, which does not exist; in the second palette it would be monochromatic for the restricted coloring. So the coloring has no monochromatic x+y=zx+y=z, and by hypothesis it has property (B). By Lemma 2(3), YrY_r is a Bohr cell with arcs of length 1/q≤ρ1/q\le\rho, ∣Yr∣=2r|Y_r|=2^r, and D(Yr)=ιb(Qr+)D(Y_r)=\iota_b(Q_r^+) carries at most χr\chi_r colors. Lemma 1 gives 2r≤qχr2^r\le q^{\chi_r}, that is, χr≥rlog⁡2/log⁡q\chi_r\ge r\log2/\log q. □\square

The same argument with property (B) required only for cells with ∣Y∣≥A∣C(Y)∣|Y|\ge A^{|C(Y)|}, for some A≥1A\ge1, gives S(k)+1≤max⁡(q,A)kS(k)+1\le\max(q,A)^k and χr≥rlog⁡2/log⁡max⁡(q,A)\chi_r\ge r\log2/\log\max(q,A): run the refinement only while ∣Yj∣≥max⁡(2,A∣C(Yj)∣)|Y_j|\ge\max(2,A^{|C(Y_j)|}), and at the stopping time ∣Y∣≤qTmax⁡(1,A∣C(Y)∣−T)≤max⁡(q,A)∣C(Y)∣|Y|\le q^T\max(1,A^{|C(Y)|-T})\le\max(q,A)^{|C(Y)|}.