gpt pro 5.2 attempt on Math-710

Erdős problem 187

1) FORMAL RESTATEMENT

Let $c:\mathbb{Z}\to\{\text{red},\text{blue}\}$ be a 2-colouring. For each $d\in\mathbb{N}$, define \[ L_c(d):=\sup\left\{\ell\ge 2:\exists a\in\mathbb{Z}\ \text{such that } a,a+d,\dots,a+(\ell-1)d\ \text{are all the same colour}\right\}. \] We seek the largest function $f:\mathbb{N}\to\mathbb{N}$ such that for every colouring $c$, \[ L_c(d)\ge f(d)\quad\text{for infinitely many }d. \]

2) QUICK LITERATURE/CONTEXT CHECK

Only what appears in the problem text: van der Waerden implies $f(d)\to\infty$ is necessary, Beck gives an upper bound $f(d)\le (1+o(1))\log_2 d$ via an explicit colouring, and Erdős gave a weaker linear-type obstruction using an irrational rotation colouring.

3) ATTACK PLAN

Give two rigorous components: $1$ a universal trivial lower bound ($f(d)=2$ works), $2$ a fully verified irrational-rotation upper bound of the form $L_c(d)\ll 1/\|d\alpha\|$ and specialize to $\alpha=\sqrt2$ giving $L_c(d)\le 2d+1$.

4) WORK

Lemma 4.1 (Infinitely many monochromatic pairs).

For every 2-colouring $c$, the set $\{d\ge 1:\ L_c(d)\ge 2\}$ is infinite. In particular $f(d)=2$ is always admissible. Proof. At least one colour class is infinite; call it $A\subset\mathbb{Z}$. The difference set $A-A=\{a-a':a,a'\in A\}$ is infinite (because for any fixed $D$ there are only finitely many pairs with $|a-a'|\le D$, while $A$ has infinitely many pairs). Every $d\in (A-A)\cap\mathbb{N}$ yields a monochromatic 2-term progression $\{a,a+d\}\subset A$, so $L_c(d)\ge 2$ for infinitely many $d$. $\square$

Lemma 4.2 (Rotation colouring bound).

Fix irrational $\alpha$ and colour $n\in\mathbb{Z}$ red iff $\{\alpha n\}\in [0,1/2)$, blue otherwise. Let $\|x\|:=\min_{m\in\mathbb{Z}}|x-m|$. Then for every $d\ge 1$, \[ L_c(d)\ \le\ \left\lfloor \frac{1}{2\|\alpha d\|}\right\rfloor+1. \] Proof. Let $\delta=\|\alpha d\|\in(0,1/2]$ (irrationality gives $\delta>0$). Suppose $a,a+d,\dots,a+(\ell-1)d$ are all red. Consider the points \[ x_t:=\{\alpha(a+td)\}=\{\alpha a+t\alpha d\}\in [0,1/2)\quad (t=0,\dots,\ell-1). \] On the circle $\mathbb{R}/\mathbb{Z}$, adding $\alpha d$ each time moves by either $+\delta$ or $-\delta$ (choose direction giving the shorter step). Thus the set $\{x_t\}$ contains $\ell$ points spaced at least $\delta$ apart along that direction. If all $\ell$ points lie in an interval of length $1/2$, we must have $(\ell-1)\delta\le 1/2$, hence $\ell\le 1/(2\delta)+1$. The same argument holds for blue. Therefore $L_c(d)\le \lfloor 1/(2\|\alpha d\|)\rfloor+1$. $\square$

Lemma 4.3 (Diophantine bound for $\sqrt2$).

For every integer $q\ge 1$, \[ \|q\sqrt2\|\ \ge\ \frac{1}{(2\sqrt2+1)q}\ \ge\ \frac{1}{4q}. \] Proof. Let $p$ be the nearest integer to $q\sqrt2$, so $\|q\sqrt2\|=|q\sqrt2-p|\le 1/2$. Then $p/q$ lies within $1/(2q)$ of $\sqrt2$, in particular $p/q\le \sqrt2+1$. Compute \[ \left|\sqrt2-\frac{p}{q}\right|=\frac{|2q^2-p^2|}{q^2\left(\sqrt2+\frac{p}{q}\right)}. \] Since $2q^2-p^2$ is a nonzero integer (no integer solutions to $p^2=2q^2$ for $q\ge 1$), $|2q^2-p^2|\ge 1$. Also $\sqrt2+p/q\le \sqrt2+(\sqrt2+1)=2\sqrt2+1$. Hence \[ \left|\sqrt2-\frac{p}{q}\right|\ge \frac{1}{(2\sqrt2+1)q^2}, \] and multiplying by $q$ gives $\|q\sqrt2\|\ge 1/((2\sqrt2+1)q)\ge 1/(4q)$. $\square$

FAST REALITY CHECK (computed)

For the colouring $c(n)=\mathbf{1}_{\{\sqrt2 n\}\ge 1/2}$, brute checks on $[1,2000]$ gave: $d=1: L(d)=2$ (bound $3$), $d=2: L(d)=3$ (bound $5$), $d=5: L(d)=8$ (bound $11$), consistent with Lemmas 4.2--4.3.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: $f(d)=2$ always works (Lemma 4.1) and there exists an explicit colouring with $L(d)\le 2d+1$ for all $d$ (Lemmas 4.2--4.3).

(ii) First gap: prove any nontrivial lower bound $f(d)\to\infty$ quantitatively (e.g. $f(d)\ge c\log d$ infinitely often) without citing deep theorems.

(iii) Top 3 next moves: 1. Translate the problem into density/recurrence properties of the difference sets of colour classes. 2. Attempt entropy or energy estimates for the distribution of monochromatic runs along residue classes mod $d$. 3. Try to re-derive Beck’s logarithmic upper bound via a self-contained random construction.

(iv) Minimal counterexample structure: a colouring for which $L_c(d)$ stays bounded or grows slower than any target function along all but finitely many $d$; such a colouring must impose strong pseudorandomness simultaneously across many arithmetic progressions.