Wiki
Wiki

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

Updated


We refute L266. The argument is author-recorded by Plasma AI. Its only external premise is the statement of the accepted claim on Problem 183, Rk(3)1/k→∞R_k(3)^{1/k}\to\infty. No property of that source's particular coloring construction is required.

A Bohr cell consisting of powers

Fix ρ∈(0,1/3]\rho\in(0,1/3], an integer n≥2n\ge2, and an integer b≥max⁡(4,n+2,⌈1/ρ⌉+1)b\ge\max(4,n+2,\lceil1/\rho\rceil+1). Put N=bn−1N=b^n-1 and X={1,b,…,bn−1}X=\{1,b,\ldots,b^{n-1}\}. Then XX is the following Bohr cell:

{y∈[0,N]:{ybl}∈[0,1b−1) (1≤l≤n),{yb−1}∈[1b−1,2b−1)}.\left\{y\in[0,N]: \left\{\frac{y}{b^l}\right\}\in\left[0,\frac1{b-1}\right) \ (1\le l\le n),\quad \left\{\frac{y}{b-1}\right\}\in \left[\frac1{b-1},\frac2{b-1}\right) \right\}.

All arcs have length 1/(b−1)≤ρ1/(b-1)\le\rho. To verify the identity, write y=∑j=0n−1djbjy=\sum_{j=0}^{n-1}d_jb^j, with 0≤dj<b0\le d_j<b. If every digit is 00 or 11, then for every ll the fractional part {y/bl}\{y/b^l\} is at most ∑j=1lb−j<1/(b−1)\sum_{j=1}^lb^{-j}<1/(b-1). Conversely, if dj≥2d_j\ge2, then {y/bj+1}≥2/b>1/(b−1)\{y/b^{j+1}\}\ge2/b>1/(b-1), so the first nn conditions fail. They therefore select exactly the 0/10/1 digit cube. For its points, y≡∑jdj(modb−1)y\equiv\sum_jd_j\pmod{b-1} and 0≤∑jdj≤n<b−10\le\sum_jd_j\le n<b-1. The last condition is exactly ∑jdj=1\sum_jd_j=1, which selects XX.

Even requiring every defining arc to have length exactly ρ\rho would not exclude this cell. An arc [a,a+w)[a,a+w) with 0<w≤ρ≤1/30<w\le\rho\le1/3 is the intersection, on the circle, of [a,a+ρ)[a,a+\rho) and [a+w−ρ,a+w)[a+w-\rho,a+w). Repeating its frequency with those two constraints replaces it by two arcs of length ρ\rho and leaves the cell unchanged.

Its differences carry exactly endpoint triangles

The map (u,v)↦bu−bv(u,v)\mapsto b^u-b^v on u>vu>v is injective. Indeed, bu+bv′=bu′+bvb^u+b^{v'}=b^{u'}+b^v identifies the multisets of exponents, since their multiplicities are at most two and b≥4b\ge4; the inequalities u>vu>v and u′>v′u'>v' then identify the ordered pairs.

Suppose

(bu−bv)+(bw−bz)=bt−bs,u>v,w>z,t>s.(b^u-b^v)+(b^w-b^z)=b^t-b^s, \qquad u>v,\quad w>z,\quad t>s.

Uniqueness of base-bb digits in a sum of three powers gives {u,w,s}={t,v,z}\{u,w,s\}=\{t,v,z\} as multisets, since all multiplicities are below bb. As t>st>s, after exchanging the summands we have t=ut=u. Then {w,s}={v,z}\{w,s\}=\{v,z\} and w>zw>z force w=vw=v and s=zs=z. The relation is thus the endpoint triangle z<v<uz<v<u. In particular no equal-summand relation occurs. This is the base-bb form of the digit argument in the refutation of L261, proved here directly.

Ramsey colorings make every color recurrent

Let nk=Rk(3)−1n_k=R_k(3)-1, so n1=2n_1=2 and nk1/k→∞n_k^{1/k}\to\infty by the accepted statement. For every fixed qq the ratios nk/nk−1n_k/n_{k-1} exceed qq for arbitrarily large kk: otherwise they would eventually be at most qq, giving nk≤Cqkn_k\le Cq^k and contradicting the divergent roots.

Given ρ\rho, A≥1A\ge1 and k0k_0, put q=⌈1/ρ⌉q=\lceil1/\rho\rceil. Choose k≥max⁡(2,k0)k\ge\max(2,k_0) so large that

nk>qnk−1,nk≥Ak.n_k>q n_{k-1},\qquad n_k\ge A^k.

This is possible because the first inequality holds for arbitrarily large kk and the second for all sufficiently large kk. Take a triangle-free kk-coloring of the edges of KnkK_{n_k}, which exists by the definition of nkn_k. It uses every color, since nk>nk−1n_k>n_{k-1}. Apply the cell construction with n=nkn=n_k, and give bu−bvb^u-b^v the color of the edge uvuv. The preceding section shows that this is a Schur-free coloring of D(X)D(X).

For any color ii and real θ\theta, partition XX into qq sets according to which of the half-open arcs [j/q,(j+1)/q)[j/q,(j+1)/q) contains {θx}\{\theta x\}. Some part ZZ has

∣Z∣≥nkq>nk−1.|Z|\ge\frac{n_k}{q}>n_{k-1}.

If no difference in D(Z)D(Z) had color ii, the corresponding vertices would have a triangle-free coloring by at most k−1k-1 colors, contradicting the definition of nk−1n_{k-1}. Thus some x∈D(Z)x\in D(Z) has color ii, and the two endpoints' fractional parts give ∥θx∥<1/q≤ρ\|\theta x\|<1/q\le\rho. Every color on D(X)D(X) therefore meets every rank-one Bohr neighborhood of radius ρ\rho.

Finally extend the coloring to [1,N][1,N] by giving each integer outside D(X)D(X) its own new color, distinct from all colors on D(X)D(X). Each new class is a singleton and is sum-free; a monochromatic relation cannot mix palettes. This is a Schur-free coloring of the whole interval. On its cell XX we still have ∣C(X)∣=k≥k0|C(X)|=k\ge k_0 and ∣X∣=nk≥max⁡(2,A∣C(X)∣)|X|=n_k\ge\max(2,A^{|C(X)|}), while the claimed avoidance fails for every color and every frequency. This refutes the statement for every (ρ,A,k0)(\rho,A,k_0).

The extension uses many extra colors. It proves no superexponential lower bound for Schur numbers and imposes no obstruction on the initial cell [0,N][0,N] of a suitably chosen adaptive recursion.

A finite instance

For ρ=1/3\rho=1/3, take the three-coloring on sixteen vertices identified with F24\mathbb F_2^4 in which the color of uvuv is the cubic-residue class of u+vu+v in GF(16)\mathrm{GF}(16). The retained exact checker constructs this field as F2[t]/(t4+t+1)\mathbb F_2[t]/(t^4+t+1), checks all triangles, and checks that each of the (166)=8008\binom{16}{6}=8008 six-vertex subsets has an edge of every color. Therefore every color graph has independence number at most five. Transfer this coloring to differences of {180,…,1815}\{18^0,\ldots,18^{15}\}, a cell by the first section. At every frequency three boxes have a part of at least six vertices, which contains each color. Every color is thus 1/31/3-recurrent. This finite instance illustrates the threshold-free failure at that radius; the arbitrary-radius and arbitrary-threshold conclusions use the Ramsey argument above.