ERDŐS/DAILY ▸

← back to the ledger

ERDőS #187 · PARTIAL

Erdős problem #187 — wave 5m report

Date: 2026-07-26 (UTC)

Claim labels used throughout:

0. Mandatory live-page gate

I fetched the rendered live page through the Bright Data browser path on 2026-07-26; this was not a cached tracker-YAML or search-snippet check. The page title was 187 | Erdős Problems, and the page said it was last edited 04 April 2026. (b: live-page datum)

The live-page statement, verbatim, is:

> Find the best function \(f(d)\) such that, in any 2-colouring of the integers, at least one colour class contains an arithmetic progression with common difference \(d\) of length \(f(d)\) for infinitely many \(d\).

The gate data shown on the rendered page were:

Thus the requested stop condition did not fire.

The live page lists these known results:

1. Cohen originally asked the problem. (b: live-page/source datum)

2. Erdős's rotation colouring, according as \(\{\sqrt2 n\}<1/2\), gives the upper bound \(f(d)\ll d\), using \(\|\sqrt2 q\|\gg 1/q\). (b: live-page result)

3. Erdős reports an unpublished Petruska–Szemerédi improvement \(f(d)\ll d^{1/2}\), and the expectation \(f(d)\le d^{o(1)}\). (b: source report; not treated as a published proof independently checked here)

4. Beck constructed a colouring giving

\[ f(d)\le (1+o(1))\log_2 d. \]

(b: Beck's named theorem)

5. Van der Waerden's theorem forces some admissible \(f(d)\to\infty\). (a), using van der Waerden as the named input

Live page: <https://www.erdosproblems.com/187>.

1. Primary-source and literature audit

The following sources were opened, and the relevant assertion was checked in the source rather than inferred from a title:

I also queried the exact-title citation trail for Beck's paper in OpenAlex and Semantic Scholar (18 and 17 indexed citing records, respectively, on the access date) and inspected the arithmetically relevant available papers. I found later papers which cite or restate Beck, and papers on finite difference sets, “large” difference sets, or discrepancy parameters, but no source claiming an asymptotic lower-bound improvement for this exact Cohen problem. I likewise found no published table for the particular consecutive-difference constants computed below, but make no novelty claim from that search miss. This is not a claim of bibliographic completeness. (d: database search)

2. A precise finite invariant

For a colouring \(c:\mathbb Z\to\{0,1\}\), put

\[ L_c(d)=\sup\{k:\ \exists a\in\mathbb Z,\ c(a)=c(a+d)=\cdots=c(a+(k-1)d)\}. \]

The live statement is equivalent to asking for the largest asymptotic \(f\) such that every \(c\) has \(L_c(d)\ge f(d)\) for infinitely many \(d\). If the colour of the witnessing progression varies with \(d\), the infinite pigeonhole principle selects one colour on an infinite subset, so this formulation preserves “at least one colour class.” (a)

Define the scale-local forcing constant

\[ \Delta_k=\min\left\{D\ge1:\ \text{every }c:\mathbb Z\to\{0,1\}\text{ has }L_c(d)\ge k \text{ for some }1\le d\le D\right\}. \]

It exists by van der Waerden's theorem: restrict a colouring to

\([1,W(2,k)]\). Any \(k\)-term progression there has

\[ d\le \left\lfloor\frac{W(2,k)-1}{k-1}\right\rfloor, \]

so

\[ \boxed{\Delta_k\le \left\lfloor\frac{W(2,k)-1}{k-1}\right\rfloor.} \tag{1} \]

This deduction is elementary modulo van der Waerden's theorem. (b)

Scaling lemma

For every \(m\ge1\), every \(k\ge2\), and every two-colouring \(c\), there is a \(j\in\{1,\ldots,\Delta_k\}\) such that

\[ L_c(mj)\ge k. \tag{2} \]

Proof: apply the definition of \(\Delta_k\) to the derived colouring

\(\widetilde c(n)=c(mn)\). A \(k\)-term \(\widetilde c\)-monochromatic

progression of difference \(j\) becomes a \(c\)-monochromatic progression

of difference \(mj\). (a)

The constant in (2) is sharp: taking \(m=1\), any smaller universal

multiplier would contradict the minimality of \(\Delta_k\). Thus, if

\[ \mathcal D_k(c)=\{d:L_c(d)\ge k\}, \]

then \(\mathcal D_k(c)\) meets

\(\{m,2m,\ldots,\Delta_km\}\) for every \(m\), with the best possible

uniform constant. (a)

3. Exact scale-local table through \(k=6\)

The result is

\[ \boxed{(\Delta_2,\Delta_3,\Delta_4,\Delta_5,\Delta_6) =(2,4,11,44,226).} \tag{3} \]

The upper bounds come from (1) and the exact values

\[ W(2,2)=3,\quad W(2,3)=9,\quad W(2,4)=35,\quad W(2,5)=178,\quad W(2,6)=1132. \]

The checker freshly reconstructs the SAT/UNSAT boundary for \(k=2,3,4,5\); the \(k=6\) equality is used only as the explicitly named Kouril–Paul theorem because a generic solver did not finish that UNSAT instance under the two-minute cap. (b) for the exact \(W\)-values; (d) for the fresh \(k\le5\) corroboration

| \(k\) | exact \(W(2,k)\) | \(\lfloor(W-1)/(k-1)\rfloor\) | explicit avoiding period | conclusion |

|---:|---:|---:|---:|---:|

| 2 | 3 | 2 | 2 | \(\Delta_2=2\) |

| 3 | 9 | 4 | 4 | \(\Delta_3=4\) |

| 4 | 35 | 11 | 11 | \(\Delta_4=11\) |

| 5 | 178 | 44 | 44 | \(\Delta_5=44\) |

| 6 | 1132 | 226 | 226 | \(\Delta_6=226\) |

For the lower bounds, extend each word periodically by \(c(n)=w_{n\bmod p}\):

k=2, p=2:
01

k=3, p=4:
1100

k=4, p=11:
11101101000

k=5, p=44:
11110111101111000101110000100001000011101000

k=6, p=226 (concatenate the wrapped lines):
0000100100010111000101101011001100101001011100010111011011111001
1101111010000010011110101111001000001011110111001111101101110100
0111010010100110011010110100011101000100100000110001000010111110
1100001010000110111110100001000110

For each word of period \(p\), the checker exhausts all \(p(p-1)\) pairs

\((a,d)\) with \(a\bmod p\) and \(1\le d \[ w_a,w_{a+d},\ldots,w_{a+(k-1)d}\pmod p \]

are not all equal. Hence there is an infinite colouring avoiding every

\(k\)-term monochromatic progression of each difference

\(1,\ldots,p-1\), proving \(\Delta_k\ge p\). (d), with the finite implication itself (a)

In particular, (2) now gives the following sharp concrete statement:

> For every \(m\ge1\) and every two-colouring of \(\mathbb Z\), some

> multiple \(d=jm\) supports a monochromatic \(k\)-term progression, with

> \(j\le2,4,11,44,226\) for \(k=2,3,4,5,6\), respectively; none of these

> five multiplier constants can be reduced.

This is (b)+(d) as quantified in the table, and is a genuine exact

finite-regime result attached directly to #187.

4. How the finite constants produce admissible lower functions

More generally, choose increasing target lengths \(k_r\to\infty\), put

\(M_1=1\), and recursively set

\[ M_{r+1}=\Delta_{k_r}M_r+1. \tag{4} \]

Define the staircase \(g(d)=k_r\) on

\([M_r,M_{r+1})\). Applying (2) with \(m=M_r\) gives a difference

\[ M_r\le d_r\le\Delta_{k_r}M_rwith \(L_c(d_r)\ge k_r=g(d_r)\). The bands are disjoint, so the \(d_r\)

are distinct; therefore \(g\) is an admissible function for the live

problem. This is the precise compactness/uniformity content behind the

page's statement that van der Waerden implies an \(f(d)\to\infty\).

(a), modulo existence of \(\Delta_k\) from van der Waerden

Taking consecutive targets \(2,3,4,5,6\) and the exact constants (3)

recomputes these first bands obtained from the sharp local multipliers:

| required length | guaranteed band containing a good difference |

|---:|---:|

| 2 | \(1\le d\le2\) |

| 3 | \(3\le d\le12\) |

| 4 | \(13\le d\le143\) |

| 5 | \(144\le d\le6336\) |

| 6 | \(6337\le d\le1,432,162\) |

These finite bands do not solve the asymptotic problem; they are a

checked initial segment of (4). (a)

5. Clean reduction to the missing uniform lemma

Set

\[ \alpha=\liminf_{k\to\infty}\frac{\log_2\Delta_k}{k}. \tag{5} \]

There is a direct implication from this finite invariant back to #187:

Proposition

If \(\alpha<\infty\), then for every \(\varepsilon>0\) and every

two-colouring \(c\), there are infinitely many \(d\) such that

\[ L_c(d)\ge\frac{1}{\alpha+\varepsilon}\log_2 d. \tag{6} \]

Proof: choose, adaptively, an unbounded subsequence \(k_r\) on which

\(\log_2\Delta_{k_r}\le(\alpha+\varepsilon/2)k_r\), and choose it so

lacunary that the already determined \(M_r\) in (4) satisfies

\(\log_2M_r\le(\varepsilon/2)k_r\). The scale lemma supplies distinct

\(d_r\in[M_r,M_{r+1})\) with \(L_c(d_r)\ge k_r\), while

\[ \log_2d_r \le\log_2M_r+\log_2\Delta_{k_r} \le(\alpha+\varepsilon)k_r. \]

This proves (6). (a)

Beck's pointwise colouring bound implies

\[ \alpha\ge1. \tag{7} \]

Indeed, apply the definition of \(\Delta_k\) to Beck's colouring. Its

witnessing differences must tend to infinity with \(k\), and

\(k\le(1+o(1))\log_2d\le(1+o(1))\log_2\Delta_k\). **(b: modulo Beck's

published colouring theorem)**

Consequently, either of the following would be decisive:

  • proving \(\Delta_k\le2^{O(k)}\) even along an unbounded subsequence

would give the first \(\Omega(\log d)\) lower bound and match Beck's

logarithmic order; (a)

  • proving

\[ \liminf_{k\to\infty}\frac{\log_2\Delta_k}{k}=1 \tag{8} \]

would give the lower leading constant \(1-o(1)\), matching Beck's

\((1+o(1))\log_2d\) upper construction. (a)+(b)

This is the exact missing uniform lemma isolated by the run. Known van

der Waerden estimates only provide

\(\Delta_k\le(W(2,k)-1)/(k-1)\); their available general upper bounds do

not yield \(\alpha<\infty\). A finite list of \(\Delta_k\)'s cannot supply

the required uniformity. (b)

No claim is made that (8) is true; it is the sharply identified target.

(c)

6. Reproducible computation

Standalone checker:

runs/erdos187_wave5m_verify.py

Run the full check with:

python runs/erdos187_wave5m_verify.py

The dependency-free witness-only pass is:

python runs/erdos187_wave5m_verify.py --skip-sat

The essential checks are constructed from the definitions:

# Periodic lower witness.
for d in range(1, p):
    for a in range(p):
        colours = {word[(a + j*d) % p] for j in range(k)}
        assert len(colours) > 1

# Finite van der Waerden CNF.
for d in range(1, (n-1)//(k-1) + 1):
    for a in range(n-(k-1)*d):
        edge = [a + j*d + 1 for j in range(k)]
        clauses.append(edge)             # not all colour 0
        clauses.append([-x for x in edge])  # not all colour 1

For each \(k\le5\), the checker builds both instances from scratch,

checks \(N=W(2,k)-1\) is SAT, directly scans the returned colouring for

all \(k\)-APs, and checks \(N=W(2,k)\) is UNSAT. It does not load a

stored CNF, model, or claimed table. (d)

The periodic checks cover respectively \(2,12,110,1892,50850\)

start/difference pairs for \(k=2,\ldots,6\). The period lengths, balance,

SHA-256 prefixes, recurrence arithmetic, and scale-band endpoints are

also recomputed. (d)

The final full run completed successfully in 18.13 wall-seconds

(18.07 CPU-seconds, 37,140 KB peak RSS). Its independently generated

SAT boundaries were:

k=2: N=2 SAT;   N=3 UNSAT
k=3: N=8 SAT;   N=9 UNSAT
k=4: N=34 SAT;  N=35 UNSAT
k=5: N=177 SAT; N=178 UNSAT
ALL REQUESTED CHECKS PASSED

The \(N=178,k=5\) UNSAT instance accounted for 17.954 seconds, 589,181

conflicts, 678,356 decisions, and 9,662,743 propagations. (d)

7. Computation wall and honest scope

A fresh generic CaDiCaL instance for \(W(2,6)=1132\) has 1,132 Boolean

variables, 127,577 progression edges, and 255,155 clauses after one

colour-symmetry unit clause. It did not finish in 120 CPU-seconds and was

terminated as required. Kouril–Paul's primary paper explains why their

proof required special preprocessing, multiple Beowulf clusters, and

FPGAs. Therefore this report cites their theorem rather than pretending

to have independently repeated it. (d)

As a bounded probe beyond the table, a cyclic \(k=7,p=500\) SAT instance

had 123,475 distinct modular edges and 246,951 clauses and did not resolve

within 45 CPU-seconds. It yields no positive or negative claim. Merely

scanning 500 candidates at that last-instance cost would already exceed

6 core-hours, and would still test only periodic witnesses, not prove

the infinite-colouring upper side. (d)

A direct finite-state treatment of \(\Delta_7\) at a candidate \(D\)

tracks a memory window of length \(6D\), hence has up to \(2^{6D}\)

states (for \(D=500\), \(2^{3000}\)); this naive computation is

infeasible. More importantly, no amount of checking finitely many \(k\)

establishes the uniform exponential lemma (8). **(a) for the state count;

(c) for any expectation about better algorithms**

The output therefore does not claim to solve #187. It supplies (i) a

sharp exact scale-local table through \(k=6\), (ii) explicit reproducible

periodic constructions, and (iii) a reduction identifying the precise

uniform finite Ramsey estimate that would deliver the missing

logarithmic lower bound. (a)+(b)+(d), as itemised above

PARTIAL: The sharp scale-local constants are \(\Delta_2,\ldots,\Delta_6=2,4,11,44,226\), with explicit checked periodic witnesses; a logarithmic lower bound for #187 would follow from the still-missing uniform estimate \(\Delta_k\le2^{O(k)}\), and the leading constant would follow from \(\liminf \log_2\Delta_k/k=1\).

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger