Proved theorem Lean Unrefereed

The last exception for two-colour Rado numbers

No dated manuscript catalogued; standalone verification archive linked above. On this site since · last revised · Verify & co-author
Kind
Theorem, a written proof with no computer search
Status
Proved and Lean-verified for every k≥3k \ge 3 (both upper and lower halves in core Lean 4); unrefereed
Prior work
Not found in the searches logged; answers Kim, Song and Hwang (2023); the lower half is Martinelli and Schaal's Lemma 3
On this page
  1. The statement
  2. Check it yourself
  3. Worked examples
  4. Status and who checked it
  5. Prior work
  6. Further reading

The statement

Colour each number from 1 to nn red or blue. A solution is three numbers x,y,zx,\allowbreak y,\allowbreak z from 1 to nn, repeats allowed, with x+y+c=kzx + y + c = kz. The Rado number R(c,k)R(c,\allowbreak k) is the least nn for which every colouring of 1..n1..n has a solution all of one colour. It exists exactly when cc is valid (kk odd or cc even). Martinelli and Schaal (2007) proved the lower bound

R(c,k)≥LB(c,k)=⌈2⌈(c+2)/k⌉+ck⌉.R(c, k) \ge LB(c, k) = \left\lceil \frac{2\lceil (c+2)/k \rceil + c}{k} \right\rceil .

An exception is a valid cc with R(c,k)>LB(c,k)R(c,\allowbreak k) > LB(c,\allowbreak k). Kim, Song and Hwang (Discrete Mathematics, 2023) proved there are none once c≥2k3+2k2−kc \ge 2k^3 + 2k^2 - k (for k≥5k \ge 5), defined ν(k)\nu(k) as the least cc from which R(c,k)=LB(c,k)R(c,\allowbreak k) = LB(c,\allowbreak k) for every valid cc, and wrote:

"It would also be interesting to determine ν(k) for all k. ... We conjecture that ν(5) = 66."

Theorem. For every k≥3k \ge 3 the last exception is

c∗(k)=k(k2+k−4)2 (k odd),c∗(k)=k(k2−2)2 (k even):c^*(k) = \frac{k(k^2 + k - 4)}{2} \ (k \text{ odd}), \qquad c^*(k) = \frac{k(k^2 - 2)}{2} \ (k \text{ even}):

R(c∗,k)>LB(c∗,k)R(c^*,\allowbreak k) > LB(c^*,\allowbreak k), and R(c,k)=LB(c,k)R(c,\allowbreak k) = LB(c,\allowbreak k) for every valid c>c∗(k)c > c^*(k). So ν(k)=c∗(k)+1\nu(k) = c^*(k) + 1 for odd kk and c∗(k)+2c^*(k) + 2 for even kk (in the paper's reading of ν(4)\nu(4)).

kk 3 4 5 6 7 8 9 10 11 12
c∗(k)c^*(k) 12 28 65 102 182 248 387 490 704 852
ν(k)\nu(k) 13 30 66 104 183 250 388 492 705 854
printed bound 295 498 777 1144 1611 2190 2893 3732

ν(5)=66\nu(5) = 66, the printed conjecture, is the case k=5k = 5. The printed bound 2k3+2k2−k2k^3 + 2k^2 - k is too large by a factor that tends to 4.

Check it yourself

  • k=3k = 3, c=13c = 13: R(13,3)=8=LBR(13,\allowbreak 3) = 8 = LB. Colouring 1–4 blue and 5–7 red is good on 1..71..7. On 1..81..8, say 1 is blue; then every colour is forced: (1,1,5)(1,\allowbreak 1,\allowbreak 5) makes 5 red, (1,7,7)(1,\allowbreak 7,\allowbreak 7) makes 7 red, (3,5,7)(3,\allowbreak 5,\allowbreak 7) makes 3 blue, (4,4,7)(4,\allowbreak 4,\allowbreak 7) makes 4 blue, (1,4,6)(1,\allowbreak 4,\allowbreak 6) makes 6 red, (2,6,7)(2,\allowbreak 6,\allowbreak 7) makes 2 blue, (5,6,8)(5,\allowbreak 6,\allowbreak 8) makes 8 blue, and then 3+8+13=3×83 + 8 + 13 = 3 \times 8 is all blue.
  • k=3k = 3, c=12=c∗(3)c = 12 = c^*(3): the last exception. The colouring blue, red, red, blue, red, blue, blue, red of 1..81..8 has no one-colour solution among its 11 solutions (figure 1), so R(12,3)=9R(12,\allowbreak 3) = 9, one more than LB=8LB = 8.
  • k=5k = 5: c∗(5)=65c^*(5) = 65. Kim, Song and Hwang's own Example is a good colouring of 1..191..19 for c=65c = 65, so R(65,5)=20>19=LB(65,5)R(65,\allowbreak 5) = 20 > 19 = LB(65,\allowbreak 5); from c=66c = 66 on, R=LBR = LB.

Worked examples

Figure 1. x+y+12=3zx + y + 12 = 3z on 1..81..8: the colouring at the top, then each of the 11 solutions on its own row in its colours. None is all blue or all red.Full size
Figure 2. The exact R(c,5)R(c,\allowbreak 5) for c=0c = 0 to 85 by exhaustive search, beside the lower bound (the step line). Hollow dots are exceptions; the last is c=65c = 65. From c=66c = 66 every dot sits on the line, and nothing in the scan warns that the end is near.Full size

How the proof goes. Replacing every xx in 1..N1..N by N+1−xN + 1 - x turns the constant cc into c′=(k−2)(N+1)−cc' = (k-2)(N+1) - c; at N=LB(c,k)N = LB(c,\allowbreak k) and c>c∗c > c^* the equation becomes x+y=kz+bx + y = kz + b with b≥1b \ge 1. This reflection is the system's own: a reviewer agent gave it in an earlier round of the same system's work. The proof then follows forced colours, as in the hand case, through four lemmas to a one-colour solution on the needed stretch. An arithmetic lemma shows the stretch is long enough for every valid c>c∗(k)c > c^*(k), and fails by exactly one at c∗(k)c^*(k).

Status and who checked it

  • Lean-verified for every k≥3k \ge 3 (both halves). Both the upper half (no exception above c∗(k)c^*(k)) and the lower half (c∗(k)c^*(k) is an exception) are proved unconditionally in the core Lean 4 archive (lean/RadoNu/RadoNu.lean, zero sorry, standard axioms only). Before formalization, the written proof of the upper half was re-derived line by line by a falsifier agent ("No gap found") and a reviewer agent; no human referee has read it. It does not use the 2023 paper's threshold theorem.
  • Computer checks, not the proof: programs replay every step of the proof's chains for kk up to 64 with 0 gaps; SAT searches find no exception just above c∗c^* for k=3k = 3 to 18 and 31 to 60; a second exhaustive solver settles ν(k)\nu(k) for k=3k = 3 to 16 by a third route, up to the printed threshold.
  • Open: most values R(c,k)R(c,\allowbreak k) below c∗(k)c^*(k), which follow no single formula.
  • Unrefereed.

What is known, and not credited here. The lower bound LBLB and, in their Lemma 3, the lower half for every kk are Martinelli and Schaal's (2007); ν(3)=13\nu(3) = 13 is Kézdy, Snevily and White's (2009) and ν(4)=30\nu(4) = 30 follows from Guo (2010) and the 2023 Remark. Jones and Schaal's Lemma 1 (2004) is the translation step, which shifts every number of a colouring by jj; the written proof uses it for a companion result on smaller cc, not for the reflection. The claim here is the upper half for every kk.

Prior work

Searches run. A falsifier agent and a reviewer agent logged 33 and 26 searches and read 22 and 20 candidates, with hand searches of DataCite, Zenodo, HAL, OSF, GitHub, citing works and the web. Two expository surveys of 2026 state only the 2023 threshold theorem. A keyed CORE run on 2026-11-20 (7 requests answered, 71 records) found two records on the same equation with other claims: Kim, Hwang and Song (2022), on small odd cc, and an Indonesian thesis of 2025 (Fikri Rahman D.) on 4≤k≤124 \le k \le 12 and 1≤c≤91 \le c \le 9, below every last exception there. No record determines ν(k)\nu(k) or gives the last exception for any kk. The result was not found in the searches logged. On 2026-11-22, a Google Scholar sweep (5 queries) found no prior work stating this claim.

Still owed: full text of K. J. Myers (2015, Rutgers PhD dissertation, gated on RUcore/ProQuest) and paywalled Kim, Song and Hwang (2026, Springer), both surfaced in the 2026-11-22 Google Scholar sweep, plus direct cited-by traversal of Kim, Song and Hwang (2023); the full texts of Jones and Schaal (2004), Kim, Hwang and Song (2022), Bergjord's 2023 thesis and the 2025 Indonesian thesis; Landman and Robertson's Ramsey Theory on the Integers; MathSciNet.

Further reading