Erdős problem #183 — wave 5m report

Access date: 2026-07-26 (UTC).

Claim labels used throughout:

• (a) elementary-rigorous — proved here from definitions.
• (b) rigorous-modulo-named-theorem — the precise external theorem is named

and linked.

• (c) plausible/structural-unverified — heuristic interpretation or cost

estimate only.

• (d) computational-only — exactly reproducible finite computation, but not

promoted to a theorem independent of that computation.

0. Mandatory live-page gate

(d: direct live-page observation) I loaded the rendered live page

<https://www.erdosproblems.com/183> through the Bright Data browser path, not

from the stale YAML. It displayed:

• status OPEN - $250;
• 0 claimed proofs for this problem;
• Currently working on this problem: None;
• Interested in collaborating: None;
• This problem looks difficult: None;
• This problem looks tractable: None;
• The results on this problem could be formalisable: None;
• I am working on formalising the results on this problem: None;
• one like, by LawrenceHollom;
• five comments; and
• “This page was last edited 10 April 2026.”

Thus neither of the mandatory stop conditions applied.

Verbatim live statement

> Let \(R(3;k)\) be the minimal \(n\) such that if the edges of \(K_n\) are

> coloured with \(k\) colours then there must exist a monochromatic triangle.

> Determine

> \[ > \lim_{k\to\infty}R(3;k)^{1/k}. > \]

Results listed on the live page

(b: live page, with primary-source checks below) The page says that Erdős

offered $100 for proving the limit finite. It records

hence \(R(3;k)\le \lceil e\,k!\rceil\), and gives the best listed upper

bound

for \(k\ge4\), attributed to Xu, Xie and Chen (2002). It gives the best

listed lower bound

from Ageron, Casteras, Pellerin, Portella, Rimmel and Tomasik (2021/2022).

It also points to problem #483.

All five live comments

**(d: direct live-thread observations; comments are explicitly unverified by

the site)** I also opened the linked discussion thread

<https://www.erdosproblems.com/forum/discuss/183>. In chronological order:

1. On 2025-09-26 Wouter Cames van Batenburg noted the Fredericksen--Sweet

improvement \(1073^{1/6}\), then the Ageron et al. preprint and its claimed

\(380^{1/5}\) lower bound. The page says it was updated in response.

2. On 2025-12-02 the same commenter described the auxiliary invariant

\(\chi_2(n)\), the least number of sum-free classes partitioning

\(\mathbb F_2^n\setminus\{0\}\), and the implication

\[ \lim_kR(3;k)^{1/k}\ge 2^{(n-1)/(\chi_2(n)-1)}. \]

The comment singled out \(\chi_2(8)\le5\) and

\(\chi_2(13)\le8\) as concrete targets.

3. On 2026-01-09 robiscounting observed that the cited 1961 Erdős source

states the Schur-number version and asked for the earliest Ramsey-number

formulation.

4. Thomas Bloom replied that the Erdős attribution and the two prizes had

been taken from Chung’s site, which supplied no further reference.

5. On 2026-07-22 onetwothreefour reported a broken [El19] reference and

supplied <https://arxiv.org/abs/1912.05353>.

There was no claimed proof, current worker, or collaborator hidden in the

thread.

1. Literature verification and present state

(b: Chung’s theorem, also restated in Fox--Pach--Suk) Chung’s 1973 paper is

F. R. K. Chung, On the Ramsey numbers \(N(3,3,\ldots,3;2)\),

Discrete Mathematics 5 (1973), 317--321,

<https://doi.org/10.1016/0012-365X(73)90125-8>. Fox, Pach and Suk explicitly

state both that Chung proved supermultiplicativity and that the limit exists:

J. Fox, J. Pach, A. Suk, *Bounded VC-dimension implies the Schur--Erdős

conjecture*, <https://arxiv.org/abs/1912.02342>, lines corresponding to

Problems 1.1--1.2 in the paper.

(a) The existence of the extended-real limit can also be checked directly.

Put \(s_k=R(3;k)-1\). Take triangle-free \(a\)- and \(b\)-colourings on

\(s_a\) and \(s_b\) vertices, using disjoint palettes. On ordered pairs of

vertices, colour an edge from the first coordinate when those coordinates

differ and from the second coordinate otherwise. A triangle with three,

two, or one distinct first coordinates cannot be monochromatic. Therefore

Fekete’s lemma applied to \(\log s_k\) gives

\(\lim s_k^{1/k}=\sup_k s_k^{1/k}\), possibly \(+\infty\); replacing \(s_k\)

by \(R(3;k)\) does not change the limit. Thus “determine” includes the still

open first question of whether this already-existing extended-real limit is

finite.

(b: Eliahou, Corollary 2.8 and references) The comment’s arXiv identifier

is valid. S. Eliahou, *An adaptive upper bound on the Ramsey numbers

\(R(3,\ldots,3)\)*, <https://arxiv.org/abs/1912.05353>, was published in

Integers 20 (2020), A54. Its Corollary 2.8 proves

from \(R(3;4)\le62\), and its bibliography identifies the 2002 source as

X. Xu, Z. Xie and Z. Chen, *Upper bounds for Ramsey numbers \(R_n(3)\) and

Schur numbers*, Mathematics in Economics 19 (2002), 81--84. Eliahou also

states explicitly that it is unknown whether the limit is finite or infinite.

(b: Ageron et al., Corollary 2.9) The lower-bound preprint exists:

R. Ageron et al., New lower bounds for Schur and weak Schur numbers,

<https://arxiv.org/abs/2112.03175> (v2, 2022). It proves the recurrence

and Corollary 2.9 deduces growth rate \(\ge380^{1/5}\) for Schur numbers and

multicolour triangle Ramsey numbers using \(S(n)\le R(3;n)-2\). This is the

claim actually made by the cited source, not an inference from its title.

(b: Bishnoi--Cames van Batenburg--Ravi, v3) The live comment’s auxiliary

result is now in a primary source: A. Bishnoi, W. Cames van Batenburg and

A. Ravi, The chromatic number of finite projective spaces,

<https://arxiv.org/abs/2512.01760v3>, revised 2026-05-24. Its small-value

table gives

Corollary 4 proves

and Problem 1 explicitly asks whether \(\chi_2(8)=5\) or

\(\chi_2(13)=8\). Hence a certified five-colouring at \(d=8\) would give

(b: Bishnoi--Kucheriya) I also checked the very recent preprint

A. Bishnoi and G. Kucheriya, *Multicolor vector space Ramsey numbers over the

binary field*, <https://arxiv.org/abs/2607.17263> (2026-07-19). Its new

theorem concerns higher-dimensional vector-space configurations; for \(t=2\)

it recovers the known connection with classical multicolour triangle Ramsey

numbers. It does not claim a solution of #183 or of \(\chi_2(8)\).

(c: search report, not a completeness theorem) Exact-title, formula and

author searches on arXiv and the web found no later primary source claiming to

determine the limit or \(\chi_2(8)\). Search has false negatives, so this is

reported only as a literature-search result; the live page remains the

authoritative status source.

2. The finite auxiliary problem

(a) Identify the points of \(\mathrm{PG}(7,2)\) with the integers

\(1,\ldots,255\), interpreted as nonzero eight-bit vectors. Addition is XOR.

Its projective lines are

there are

of them, and every point lies on 127 lines. A colour class is sum-free

exactly when it contains no such line.

(a) If these 255 points have a proper \(q\)-colouring \(c\), colour the

edge \(\{u,v\}\) of the complete graph on \(\mathbb F_2^8\) by

\(c(u+v)\). A monochromatic triangle would give three same-coloured

nonzero vectors \(x,y,x+y\), a contradiction. Thus a proper five-colouring

would already give \(R(3;5)>256\); the stronger asymptotic conclusion

\(2^{7/4}\) uses the named recursion in Corollary 4 of the projective-space

paper.

Complete SAT reduction used

(a) A direct CNF has variables \(X_{v,c}\) for 255 points and five

colours. “Exactly one” contributes

clauses. Forbidding one colour on all three points of every line contributes

\(5\cdot10\,795=53\,975\) clauses. The unsymmetrised instance therefore has

1,275 variables and 56,780 clauses.

(a) The following symmetry reduction loses no possible solution. Some

class \(A\) has at least \(\lceil255/5\rceil=51\) points. If its span has

dimension \(r\) and \(a\in A\), then \(A\) and \(a+A\) are disjoint, so

\(2|A|\le2^r\). Since \(51>32\), \(r\ge7\). Choose seven independent

members of \(A\), map them linearly to \(1,2,4,8,16,32,64\), and call their

colour 0. Their sum \(1\mathbin{\mathtt{xor}}2=3\) has another colour, which

can be called 1. If \(A\) spans dimension 8, choose the eighth basis point in

\(A\); otherwise choose it outside the 7-space. Residual colour permutation

then permits the colour of 128 to be restricted to \(0,1,\) or \(2\).

These eight unit clauses and one three-literal clause give the complete

normalised instance with 56,789 clauses.

(d) CaDiCaL 1.9.5 did not decide that complete normalised instance in a

bounded 180-second run. This is a timeout, not evidence of satisfiability or

unsatisfiability.

3. Verified near-colouring

(c: discovery only) Five multiplicative cyclotomic classes in

\(\mathbb F_{256}^{\times}\) give a useful heuristic seed: each initially has

17 bad lines. The C++ tabu search in runs/erdos183_search.cpp repeatedly

reduced the total defect from 85 to 7, but not to zero. No mathematical claim

depends on the heuristic or its internal objective bookkeeping.

(d: independently checked certificate) The following five sets partition

\(\mathbb F_2^8\setminus\{0\}\). Classes 0--3 are sum-free. Class 4 has

exactly seven lines, all inside one Fano plane.

0: 2 9 15 16 27 29 32 33 36 39 50 51 53 54 64 76 77 82 89 94 95 98 99
   101 102 110 112 113 116 131 136 145 151 154 166 171 173 174 180 184
   188 191 193 198 199 211 212 213 216 228 232 236 239 246 250 254
1: 3 4 6 13 17 20 22 31 34 37 42 45 48 55 63 67 68 70 72 79 84 86 93
   96 103 111 114 117 122 125 135 137 140 142 149 153 155 156 158 160
   167 168 181 186 197 203 204 206 215 217 219 220 222 226 229 240 248
2: 10 12 24 25 38 40 41 43 47 52 57 58 59 61 73 78 85 91 92 105 107
   109 118 121 123 127 128 129 134 146 147 148 161 162 163 165 172 177
   179 183 190 192 194 195 196 209 210 225 231 238 241 242 243 245 252
3: 1 5 7 8 14 19 21 26 28 30 35 44 46 49 56 60 62 65 71 74 81 83 87
   88 90 97 104 106 108 115 119 120 124 126 130 132 139 141 143 150 157
   159 164 169 175 178 182 185 187 189 205 207 208 221 223 224 233 237
   244 249 251 253 255
4: 11 18 23 66 69 75 80 100 133 138 144 152 170 176 200 201 202 214
   218 227 230 234 235 247

(d) The class sizes are \((56,57,55,63,24)\). Exhaustive line

enumeration gives precisely

as the monochromatic lines. Their point set is

so these are exactly all seven lines of a Fano plane.

This is a near-colouring, not a five-colouring and not an improvement

to the published Ramsey lower bound.

4. Exact isolation of the defect

(a, conditional on the checked finite data) Fix a point \(v\in P\), and

suppose it is changed from colour 4 to \(c\in\{0,1,2,3\}\). Every outside

pair

whose two endpoints currently have colour \(c\) must have at least one

endpoint changed; otherwise it and \(v\) form a new monochromatic line.

For fixed \(v\), these pairs are disjoint.

(d) Recomputed matching counts, with columns \(c=0,1,2,3\), are

so no point of \(P\) can even be recoloured while all outside points stay

fixed.

(d: exact exhaustive proposition) With the five colour labels fixed,

every proper five-colouring of these 255 points has Hamming distance at least

37 from the displayed near-colouring.

Here is the finite proof checked by the standalone script.

1. A hypothetical repair restricts to one of \(5^7\) colourings of \(P\).

Exactly 58,380 of these have no monochromatic line within \(P\).

2. For each such restriction, let \(T\) be the points that changed from

colour 4. For every \(v\in T\), take all the outside pairs described

above for the new colour of \(v\).

3. The set of changed outside points must be a vertex cover of the union of

those pairs. Every matching in that union is therefore a lower bound on

the number of changed outside points.

4. For each of all 58,380 restrictions, the checker constructs a

deterministic greedy matching. The minimum of

\[ |T|+\lvert\text{greedy matching}\rvert \]

is 37. At the first minimizing restriction, in the point order

\((18,66,80,138,152,200,218)\), the colours are

\((4,2,4,2,4,3,4)\): three Fano points change and the explicitly

constructed outside matching has 34 edges.

The argument uses only that a vertex cover contains an endpoint of every

edge in a matching. “Greedy” need not find a maximum matching; any matching

gives a valid lower bound. The exhaustive minimum is computational-only,

but it is reproduced without SAT, ILP, randomness, or third-party packages.

Core verification logic (the full certificate and assertions are in the

standalone file):

for assignment in product(range(5), repeat=7):
    if any(assignment[i] == assignment[j] == assignment[k]
           for i, j, k in fano_line_indices):
        continue
    changed_fano = sum(c != 4 for c in assignment)
    forced_edges = set()
    for v, c in zip(FANO, assignment):
        if c != 4:
            forced_edges.update(matchings[v, c])

    used, greedy_matching = set(), []
    for x, y in sorted(forced_edges):
        if x not in used and y not in used:
            used.update((x, y))
            greedy_matching.append((x, y))
    lower_bound = changed_fano + len(greedy_matching)

5. Reproduction

The standalone verifier is

erdos183_wave5m_reverify.py. From the

repository root:

python runs/erdos183_wave5m_reverify.py

It uses only the Python standard library. A successful run prints:

partition sizes: (56, 57, 55, 63, 24)
projective lines checked: 10795
monochromatic lines: 7 [(18, 66, 80), (18, 138, 152), (18, 200, 218),
 (66, 138, 200), (66, 152, 218), (80, 138, 218), (80, 152, 200)]
admissible Fano restrictions exhausted: 58380
minimum certified Hamming-distance lower bound: 37
matching size at minimizer: 34
ALL CHECKS PASSED

(d) The clean run on this VM took approximately 2.4 seconds.

The heuristic search source is

erdos183_search.cpp. It is not part of the proof;

it only explains how the finite certificate was found.

6. What this establishes, and the precise wall

(d) The concrete progress is a fully checkable partition into four

sum-free classes and a fifth class whose entire defect is one Fano plane,

together with an exact proof that this near-colouring is isolated by Hamming

radius 36. This is stronger information than a raw “best objective = 7”

heuristic log.

(a) The Hamming result does not imply \(\chi_2(8)=6\): a proper

five-colouring could lie at distance 37 or more. Conversely, the near-

colouring does not imply \(\chi_2(8)=5\). Neither implication is being

claimed.

(b: projective-space Corollary 4) Even a successful proof

\(\chi_2(8)=5\) would improve only the lower bound on the requested limit

to \(2^{7/4}\). It would not prove finiteness and therefore would not close

Erdős #183.

(a) The ordinary neighbourhood/pigeonhole recurrence loses a factor

comparable to \(k\) at each step and therefore gives factorial rather than

uniform exponential growth. The exact missing global advance is a uniform

bound

for some absolute \(C\), or an argument of equivalent strength. The

bounded-VC-dimension theorem does not supply it for arbitrary colourings, and

the vector-space constructions control a special translation-invariant

subclass rather than all edge-colourings.

(d) For the finite auxiliary target, the exact remaining computation is

the complete normalised 1,275-variable, 56,789-clause SAT instance. A SAT

witness would settle \(\chi_2(8)=5\); an UNSAT result is publishable only with

a checkable proof trace (for example DRAT/LRAT), not a solver status line.

The three-minute CaDiCaL timeout supplies neither.

(c: low-confidence resource estimate) A serious solver portfolio with

proof logging should be budgeted at roughly \(10^2\)–\(10^3\) core-hours

(about $3–$100 at $0.03–$0.10 per core-hour), with no assurance that this is

enough; proof-trace storage and checking may dominate an UNSAT run. That

estimate is deliberately broad because one short timeout does not support a

credible runtime extrapolation. I did not launch such a job on this VM.

PARTIAL: verified a five-class near-colouring of PG(7,2) with exactly one monochromatic Fano plane and proved by a standalone exhaustive checker that every proper five-colouring is at fixed-label Hamming distance at least 37; the global existence of a five-colouring, and Erdős #183 itself, remain open.