Fabian Arevalo

Computational research note · Ramsey theory on the integers

Seven certified van der Waerden numbers, and a new bound past w(2;5,7)

First machine-checked proofs for a row of the mixed van der Waerden table, through w(2;4,7) = 109 and w(2;5,5) = 178, plus the first recorded bound on the open cell above them: w(2;5,8) > 295.
August 16, 2026 · produced in a Claude Code research session · code, data and certificates in the companion repository.

Start here: no maths required

Write the whole numbers from 1 to 295 in a row, and color every one of them either red or blue.

Now try to avoid two things at once: five red numbers that are evenly spaced (like 3, 10, 17, 24, 31, each one 7 more than the last), and eight blue numbers that are evenly spaced. You choose the spacing separately each time someone challenges you, and you choose the colors however you like. Red only has to dodge runs of five; blue has the harder job of dodging runs of eight.

It turns out you can do it, the whole way to 295. Below is one specific coloring that works, drawn as a grid. It is not 295 separate decisions: it is a single 74-number pattern, repeated four times end to end. Nobody had published a coloring like this before, or any bound at all on this exact question, because the largest case anyone had solved before this stopped at a smaller number, in 2013.

Hover or tap a cell to see its position and color; click a column to check that all copies agree there.
An explicit coloring of 1 through 295 with no five evenly-spaced reds and no eight evenly-spaced blues. A filled square is color 1 (the side that must dodge 8-term progressions); an open square is color 0 (the side that must dodge 5-term progressions). Read left to right, top to bottom: all four rows are copies of the same 74-number pattern. Row four stops ten cells early only because 295 isn't a multiple of 74. This is the actual committed data (data/witness_5_8_n295_perdef_p74k0.txt), independently re-checked for this page: a freshly compiled copy of the repository's from-definition C checker and a separately re-imported Python enumerator both confirm no 5-term run of one color and no 8-term run of the other, over every arithmetic progression in range.

What this note adds

Questions of this shape (how far can you push a coloring before evenly-spaced monochromatic runs become unavoidable) are called van der Waerden numbers, and small cases have been computed since the 1970s. The row that matters here is w(2;5,t): red must always dodge a run of five, blue must dodge a run of t. The last new value published in this row was in 2013, at t = 7. This note adds:

  1. The next cell, opened for the first time. 1 through 295 can be colored to dodge both patterns at (5,8); no bound on this cell had been published before. Whether 296 can also be done is still open.
  2. Seven older answers, given a real proof for the first time. Values for seven smaller cells, from 22 up to 178, have been known since as far back as the 1970s, but none of those publications shipped a way to check the computation independently. This note recomputes all seven from the bare definition and attaches a machine-checkable proof to each.
  3. A pattern in what the winning colorings look like. Every winning coloring found this session is either exactly repeating or just one cell away from it, except at one harder cell, (5,6), where a complete search ruled out every short repeating pattern outright and the real answer is still unsettled.
  4. A tool for splitting one huge proof into many small, checkable pieces. One of the seven proofs below is a single file 1.14 gigabytes long. A separate, resumable "divide and conquer" driver was built, tested, and is ready to point at the next open cell: instead of one proof, it breaks the work into thousands of small, individually checked pieces (421, in this session's validation run).

Everything below is the technical version. Section 2 has the certified table; section 4 has the repeating-pattern figure that section 3 is trying to explain.

AbstractSummary of results

The mixed van der Waerden number w(2;s,t) is the least n such that every red/blue coloring of {1,…,n} contains a red s-term or a blue t-term arithmetic progression. The exact values published for 4 ≤ s ≤ t ≤ 7 (Landman–Robertson's tables; Ahmed, 2009–2013 (secondary)) predate certificate-producing SAT practice: none of them ship a machine-checkable proof. This note (i) re-derives seven cells of the table from the raw definition, through w(2;4,7) = 109 and w(2;5,5) = 178, each with a witness independently re-verified by two from-definition checkers and an UNSAT proof validated by a from-definition RUP checker; (ii) proves the first recorded bound on the open cell above the row's 2013 frontier, w(2;5,8) > 295, via an exactly-74-periodic coloring; (iii) records that extremal witnesses are near-periodic with a defect count that grows along the ladder, including a complete negative result at (5,6); and (iv) validates a resumable cube-and-conquer campaign driver toward deciding w(2;5,8). The eighth rung of the ladder, w(2;5,6) = 206, is not among the certified cells here: both certification legs were still running when the session that produced this note closed, and no commit since has completed them. This repository currently has seven certified cells, not eight.

Section 1Definitions and certification protocol

A good partition of [1,n] for (s,t) is a 2-coloring with no monochromatic s-term arithmetic progression in color 0 and no monochromatic t-term arithmetic progression in color 1. By definition, w(2;s,t) is the least n admitting no good partition; good partitions of [1,n] exist exactly for n ≤ w(2;s,t) − 1.

Lemma 1: restriction monotonicity

If [1,n] admits a good partition, so does [1,m] for every m < n.

Proof. Restrict the coloring to [1,m]. Every arithmetic progression contained in [1,m] is also contained in [1,n], so no forbidden monochromatic progression can appear that was not already excluded. ∎

Certification protocol. A value w(2;s,t) = w is CERTIFIED when both legs exist: (a) a good partition of [1,w−1], re-verified by an enumeration routine independent of the CNF encoder; (b) an UNSAT proof for the CNF encoding of "a good partition of [1,w] exists", validated by rup_check, a forward reverse-unit-propagation checker written from the definition of a DRUP proof, sharing no code with any SAT solver. By Lemma 1, these two legs pin the value exactly.

Encoding. One Boolean variable per integer in [1,n]; for every s-term progression, a clause forbidding all-color-0; for every t-term progression, a clause forbidding all-color-1. The encoder self-checks against the closed-form count of k-term progressions in [1,n], and reproduces the tiny brute-force cases w(2;3,3) = 9 and w(2;3,4) = 18. (Re-derived independently for this page: for all seven certified cells, the variable and clause counts in the committed .cnf files match the encoder's own formula exactly. See section 2.)

Section 2Certified values

Seven cells carry both certification legs. An eighth cell, w(2;5,6) = 206, was attempted but not finished by session close, and the frontier cell, w(2;5,8), currently has only a lower-bound leg. All three states are shown below rather than only the seven successes, because a table that silently dropped the incomplete row would misrepresent how far the session actually got.

cellvaluewitness legUNSAT / bound legstatus
(3,5)22good partition of [1,21]242-line DRUP, RUP-VERIFIEDCertified
(3,6)32good partition of [1,31]582-line DRUP, RUP-VERIFIEDCertified
(4,4)35good partition of [1,34]573-line DRUP, RUP-VERIFIEDCertified
(4,5)55good partition of [1,54], exactly 22-periodic7,636-line DRUP, RUP-VERIFIEDCertified
(4,6)73good partition of [1,72]253,728-line DRUP, RUP-VERIFIED (as logged); independently, 421/421 cube-and-conquer leaves RUP-checked, 0 failuresCertified
(4,7)109good partition of [1,108]18,434,058-line DRUP, 1.14 GB, RUP-VERIFIED (sha256 in MANIFEST)Certified
(5,5)178good partition of [1,177], 44-periodic, 1 defect1,561,916-line DRUP, ≈103 MB, RUP-VERIFIED (sha256 in MANIFEST)Certified
(5,6)206not completed by session closenot completed (Glucose UNSAT running > 2 h at close)In progress
(5,8)> 295good partition of [1,295], exactly 74-periodicno UNSAT attempt yet at any n > 295Certified Lower bound
Hover or tap a bar for exactly what was re-checked for this page and what is carried as reported.
Every one of these seven values has a checked proof, and the proof's length grows by five orders of magnitude along the ladder. It is not even monotonic in n. w(2;4,7) = 109 needed a longer proof (18.4M lines) than w(2;5,5) = 178 (1.6M lines), despite the smaller n: proof difficulty tracks the shape of (s,t), not just the size of n. The hatched bar, w(2;4,6), is the one value in this chart not independently re-checked for this page.

What was actually re-checked for this page, and what was carried as reported. The four smallest proofs, for (3,5), (3,6), (4,4), and (4,5), are committed files; wc -l on each matches the line counts above exactly, and re-running the repository's rup_check against all four (recompiled fresh from source for this page) returns VERIFIED on every one. The two largest proofs, for (4,7) and (5,5), exceed the repository's 10 MB commit threshold and are not present as files; certs/MANIFEST.csv, read directly for this page, independently confirms their byte sizes (1,141,611,800 and 103,399,908) and sha256 hashes with a RUP-VERIFIED verdict, but does not itself record a line count for the second one, so both line counts above are the certifying session's own figures, not something this page recounted. The (4,6) proof is different in kind: this repository has neither the proof file nor a certs/MANIFEST.csv row for it, so the 253,728-line figure could not be independently checked at all here. What is independently checkable is a separate route to the same cell: data/cnc_4_6_n73.csv records a cube-and-conquer campaign with 421 leaf cubes, every one individually RUP-checked at production time (the driver's own source enforces this: a leaf is logged UNSAT only if rup_check agrees), zero CHECKFAIL rows, closing the full search space by a case-split argument. That figure, 421, is also the one independently confirmed here for the cube-and-conquer route; the source note separately cites a "64/64 leaves" control for this same cell, and no data under that description could be found in this repository to check it against, so it is not repeated on this page.

Section 3The bound at w(2;5,8)

Theorem 2: CERTIFIED

w(2;5,8) > 295.

Certificate. An exactly-74-periodic coloring of [1,295] (data/witness_5_8_n295_perdef_p74k0.txt), found by a complete defect-tolerant search over periodic-with-≤8-defects colorings at period 74 (the solver returned a 0-defect solution) and verified good by two independent from-definition checkers. By Lemma 1 this also certifies every smaller n. ∎

Walk history. Earlier steps toward this bound are committed alongside it: exactly-74-periodic witnesses were found at n = 280, then 290, then 292, then 295. The blocks are not all the same block: the 74-cell pattern good through n = 290 turns out to fail by n = 292, while a different 74-cell pattern is good all the way through 295. A block dying is not the same as the period dying, and the period dying is not the same as the row dying: larger-period and defect-tolerant searches above 295 were still running when the session closed.

Context (all secondary). The row reads 178, 206, 260 at t = 5, 6, 7 in the literature this session could reach, though only 178 is independently certified in this repository; 206 is not yet certified here (section 2), and 260 was not attempted this session. The first differences of that three-point sequence are +28 and then +54. A naive continuation of that pattern would put w(2;5,8) somewhere in the low-to-mid 300s: this is not a bound of any kind, just a two-point extrapolation, stated because it is the only orientation available, not because it carries any evidential weight. No UNSAT attempt has yet been made at any n > 295, so the true gap between 295 and w(2;5,8) is completely unknown; it could be zero cells or hundreds.

Section 4Periodicity and defects along the ladder

A pattern shows up in every extremal witness found this session: each one is either exactly periodic, or periodic up to a small, exactly-located defect. Representing a coloring as "a p-cell block, plus a short list of exceptions" turns a search over 2n colorings into a search over 2p·C(n,≤k) restricted ones, complete rather than heuristic and small enough to finish. This is the mechanism that made every lower-bound leg in section 2 computable.

Hover or tap a row for the period, the repeat count, and any defect.
The winning colorings are almost, but not quite, periodic. How far "almost" has to stretch grows along the ladder. Each row shows one copy of the repeating block a complete search found, then whatever is left over after tiling that block as many whole times as fits; a crossed cell is a position where the leftover breaks the pattern. The (5,6) row is hatched because there is nothing to draw: a complete search ruled out every period from 30 to 49 outright.

The four data points, re-derived independently for this page by tiling each witness's own first block across its full length and comparing to the actual committed bits:

  1. (4,5) at n = 54: exactly 22-periodic. Tiling the first 22 bits across all 54 positions reproduces the witness exactly: 0 defects.
  2. (5,5) at n = 177: 44-periodic with exactly one defect. Tiling the first 44 bits four times covers positions 1–176 exactly; the single leftover bit, position 177, is the only disagreement in the entire string: the tiling predicts color 1 there, the witness has color 0.
  3. (5,6) at n = 205: no exactly-periodic witness exists for any period p ∈ [30,49] (a complete per-period result, not a failed search), and none with p = 41 at ≤ 6 defects either. This is a negative computational claim carried from the certifying session; re-running a full period sweep was outside the scope of what this page re-verifies, so it is reported, not independently reproduced here.
  4. (5,8) at n = 295: exactly 74-periodic, as in section 3, but not from one universal block. The 74-cell pattern good through n = 290 stops being good by n = 292; a different 74-cell pattern is what reaches 295.

Whether this defect count is monotone along the whole (s,t) ladder is open; the four points above are 0, 1, "no small period at all," and 0-at-a-larger-period: suggestive, not a proved trend.

Section 5Methodology and infrastructure

Environment. 4-core cloud sandbox, 15 GB RAM, Python 3.11.15, python-sat 1.9.dev15 (CaDiCaL 1.9.5 as the fast satisfiability path, Glucose 4.2 with proof logging as the certificate path), gcc -O2 for the C checkers. Search seeds fixed at random.Random(20260816) for the incomplete searchers; the complete per-period and per-defect SAT searches are deterministic given the solver version.

Independence legs. Four separate channels, sharing no code with each other: the CNF encoder self-checks against a closed-form progression-count identity; tiny cells are cross-checked against zero-cleverness brute force; every witness is re-verified by an enumeration routine written independently of the encoder (this page re-ran that check, plus a second, freshly-compiled C version, against the (5,8) witness directly; see "in plain terms" above); every UNSAT proof is checked by tools/satcert/rup_check, a from-definition forward-RUP checker sharing no code with any SAT solver.

Certificate hygiene. Proofs at or below the repository's size threshold are committed directly; larger ones are excluded by certs/.gitignore and recorded instead in certs/MANIFEST.csv (sha256, byte size, solver, and checker verdict), with the generating script left in place so the proof is re-derivable, not merely asserted.

The cube-and-conquer driver. A resumable campaign tool for UNSAT legs too large for a single proof-logged run: it splits on the most arithmetic-progression-covered variables, recurses into deeper splits whenever a cube exhausts its conflict budget, and checks each resulting leaf's own DRUP proof with rup_check at the moment it is produced: a leaf is only ever logged UNSAT once the checker has already agreed. Because a case split on fixed-variable sign patterns is a tautology, "every leaf UNSAT" implies the whole instance is UNSAT without needing a merged proof. Directly confirmed for this page from data/cnc_4_6_n73.csv: one campaign on w(2;4,6) = 73, starting from 16 cubes, adaptively deepening 14 of them once and 13 of their children again, ending at 421 UNSAT leaves (2 resolved at the first depth, 211 at the second, 208 at the third) with zero CHECKFAIL rows. The source note additionally describes two other controls for this same driver (a direct 64-cube run and a satisfiability-detection run at n = 72) that this repository does not carry separate campaign data for, so they are reported as described rather than independently re-checked here.

Section 6Open questions

  1. Decide w(2;5,8). The campaign infrastructure exists; the UNSAT leg at the (unknown) boundary is the hard half. The measured growth of proof-logged UNSAT cost down this row (seconds at (5,5)@178, more than two hours and still unfinished at (5,6)@206) prices this as a multi-session cube-and-conquer campaign, not a single run.
  2. Finish w(2;5,6) = 206 itself: the witness leg at 205 and the UNSAT leg at 206 were both still running at session close.
  3. Is the defect count of extremal witnesses monotone along the (s,t) ladder? The four points measured so far (0, 1, "no short period at all," 0-at-a-larger-period) do not yet settle it.

Section 7Caveats and honesty notes