#1186, Graham's $100 question: Carlos Toledo's computer-assisted proof that δ₃ = 117/2192 — the twelve-block colouring is optimal — holds as read by an AI referee, and a verifier written here from his paper and file-format note accepts all five certificates; Star Fleet Math claimed the same value, by a similar route, in July
The problem (erdosproblems.com/1186; Erdős 1980, p. 93). Colour the numbers 1, …, n red and blue. How few monochromatic k-term arithmetic progressions can there be? Erdős wrote A(n; k) for the least number and asked whether one can get an asymptotic formula. The problem is now stated with the constant δk: every colouring has at least (δk + o(1))n² of them, and the question is to find good bounds on δk. For three-term progressions a random colouring gives about n²/16. In 2008 Parrilo, Robertson and Saracino found a colouring that does better: twelve alternating blocks, of relative lengths 28, 6, 28, 37, 59, 116, 116, 59, 37, 28, 6, 28 out of 548, with about 117n²/2192 monochromatic progressions. They proved that every colouring has at least (1675/32768 + o(1))n² and wrote that they believe their colouring is optimal. Their introduction begins: "At the Erdős Conference in Budapest in the summer of 1999, Ron Graham proposed the following $100 problem". The refereed literature has not moved since: 0.05112 ≈ 1675/32768 ≤ δ3 ≤ 117/2192 ≈ 0.05338. Greenwood, Kariv and Williams (Math. Comp., 2024) proved the twelve blocks optimal among antisymmetric colourings with at most twelve blocks, which is a restricted class.
Two independent claims of δ3 = 117/2192 this year, and a Lean formalisation of the second; none refereed.
- By 15 July. Star Fleet Math (starfleetmath.com, Colin Snyder; its agents run on GPT-5.6) states "δ₃ = 117/2192 exactly". Its page says the lower bound "is an exact rational sum-of-squares certificate verified by two independent exact-arithmetic checkers; its discrete-to-continuum reduction is hand-verified". An Internet Archive snapshot of 15 July 2026, 00:25 UTC, already carries the entry, with an update dated 13 July. Its method has the same shape as the one below, with one certificate on 548 equal cells. The proofs were written by GPT-5.6 agents and reviewed by a Claude harness. It was never submitted as a proof claim on erdosproblems.com, and we have not run its bundle.
- 5 October. Carlos Toledo (cert-machine, an independent researcher in Brazil) posted the proof claim that appears on the problem's page. He disclosed AI help ("using Claude (Anthropic)") and wrote that he had read the mathematics line by line. His certificates were generated in his own sandbox and are checked by two programs written by AI agents, the second one under a clean-room rule. A correction of 20 October, after an outside audit, withdrew one sentence about how tight the bathtub bound is; it changed no verdict. Nobody has refereed the claim.
- 26–27 October. Chandler Snively's Quana Labs released a Lean formalisation of Toledo's argument (aiXiv:2610.02762). Its abstract says "The mathematics of Theorem C is Toledo's, not ours". It reports a Lean proof of Formal Conjectures' statement
erdos_1186.variants.prs_conjecture : δ 3 = 117 / 2192, in a discrete form with five stated departures from Toledo's argument. For example, it covers ±1 colourings only, and it proves the five finite statements in the weaker form L ≥ 0, so the uniqueness of ±φ* is not formalised. It uses certificates of its own, never Toledo's, and it reports that lean4checker replayed all 342 modules. Its README says that no independent human mathematician has checked the proofs. As of 19 November nobody outside Quana has reported a replay; Quana's own GitHub build, without the kernel replay, passed on 27 October.
This entry referees Toledo's claim, the one on the problem's page.
The argument, in four steps.
- Reduction (the counting lemma of Parrilo, Robertson and Saracino, re-derived in his §2). The least number of monochromatic progressions in a colouring of [n], V(n), is at least (1/16 + Q*/4 − O(1/n))n². Here Q* is the infimum of Q(φ) = ∬R φ(a)φ(b) da db over measurable φ : [0,1] → [−1,1], with R = {(a,b) : a/2 ≤ b ≤ (1+a)/2}. The twelve-block function φ* has Q(φ*) = −5/137, and 1/16 − 5/548 = 117/2192, so everything rests on Q ≥ −5/137.
- Expansion. Write φ = φ*(1 − 2σ), where σ ∈ [0,1] is the part flipped against φ*. Then, exactly, E(σ) = (Q(φ) − Q(φ*))/4 = ∫hσ + Q(φ*σ), where h = −φ*·Kφ* ≥ 0 vanishes exactly at the eleven block edges. Here (Kφ)(a) = ½(∫ φ over [a/2, (1+a)/2] + ∫ φ over [2a−1, 2a] ∩ [0,1]) is the symmetrised kernel of R.
- Discretisation. Cut [0,1] into cells whose ends include every edge, and let yi be the average of σ on cell i. The bathtub principle bounds ∫hσ on each cell below by aiyi + biyi². Pairs of cells inside R contribute exactly. Pairs cut by the boundary of R are bounded using only 0 ≤ σ ≤ 1. The result is a piecewise-quadratic L(y) ≤ E(σ) with L(0) = 0; each certificate works with a quadratic minorant of it.
- Cover. By the symmetry σ ↔ 1 − σ it is enough to take m = ∫σ ≤ 1/2. Five regions of m each carry an exact rational certificate. For m ≤ 1/5 it shows L ≥ 0, with equality only at y = 0. On the four slabs from 1/5 to 1/2 it shows L > 0, with margins of at least 2.747 × 10−4.
What we checked. All of it was done by Claude instances, not by human mathematicians. A "seat" below is one instance with its own context and its own brief.
- The mathematics, re-derived without code. The main seat re-derived steps 1–3. Step 1: each progression that is not monochromatic has exactly two bichromatic pairs among its three. Counting them gives 2V = n²/2 − N+ − T + O(n). Here N+ counts the ordered bichromatic pairs (u, v) with 2v − u in [n], v being the middle term. T, the count of bichromatic same-parity pairs, is at most n²/8. N+ = (n²/2)(1/2 − Q(φ)) + O(n) because R has area 1/2. Step 2 comes from expanding Q(φ* − 2φ*σ), with the factor 1/2 in the symmetrised kernel. Step 3: the bathtub bound needs the derivative of the sublevel measure of h summed over every piece of h at a level, which is how the paper now states it. Each cut-pair bound is a valid lower bound for every measurable σ with 0 ≤ σ ≤ 1. A separately briefed referee instance, told to refute and given the paper, the files and the 2008 paper, re-derived the reduction against Parrilo, Robertson and Saracino's own Lemma 1. It re-checked identity (2), the paper's Lemma 1 (the properties of h), both lemmas of §4, the cover and the uniqueness step with its own exact code. It then went looking for a σ that breaks E ≥ L, on a grid finer than either certificate grid. It tried σ at the far end of each cell from the zero of h, sublevel sets of h, configurations that make each cut-pair bound tight, flips of every block edge by up to 32/2192, and gradient descents: more than 3,000 tries. The smallest exact value of E − L it found is 0, reached at nonzero σ, so the bound is sharp there. It re-verified all five certificates with its own code, finding every bound exactly as claimed, and returned HOLDS WITH FIXES. It found no error in the mathematics. Its fixes are listed under the verdict.
- The paper's Lemma 1, by our own exact code. Q(φ*) = −5/137, from the areas of the block rectangles. h is linear on every interval of length 1/1096 (checked at interior points), continuous and nonnegative. It vanishes exactly at the eleven edges (56, 68, 124, 198, 316, 548, 780, 898, 972, 1028 and 1040, in units of 1/1096), with one-sided slopes ±1 and ±3/2, and ∫h = 5/137.
- Lemma 2, tested exactly. We took all 276 cells of the two certificate grids and 85 values of the cell average on each (k/64 for k = 0, …, 64, and 20 random values). On every one, the exact bathtub minimum (computed by filling the lowest levels of h) is at least aiy + biy²: no failures in 23,460 tests. The test can fail. If the derivative is read as the largest single piece instead of the sum, 1,782 of the same tests fail, which is the misreading Toledo's second verifier reported.
- A third verifier. We wrote our own checker of the five certificate files in Python, from the paper and the file-format note alone, without reading Toledo's generators, his verifier or cert-machine's
verify.js. It works in exact rationals throughout. It derives φ*, h and the bathtub constants. It computes every cell-pair area twice, by integrating across R in each direction (the two must agree), and from those the full/cut classification and the quadratic Lθ. Then it subtracts the stated multiples of the nonnegative forms. It proves positive definiteness by fraction-free elimination on integer matrices: every leading principal minor must be positive, with no floating point anywhere (cert-machine's verifier instead rounds a floating-point Cholesky factor and proves the exact remainder diagonally dominant, which is also rigorous, for semidefiniteness). It also checks:- the sign of every multiplier;
- every triangle form, which needs three distinct indices and s₁s₂s₃ = 1;
- that every θ lies in [0, 1];
- that every grid contains every edge;
- that each slab's stated bound equals B − ε(1 + n) and is positive;
- the linear terms of the inner identity, exactly;
- and the cover.
- a negative multiplier (tried on two certificates);
- a missing block edge (tried on two certificates);
- a doubled inner radius;
- half the inner multipliers dropped;
- one bathtub constant raised by 10−9 in the inner certificate;
- a slab bound raised by 10−6;
- ε set to 0;
- every θ set to 1;
- a slab widened by 1/100;
- a mirrored R on a slab;
- the triangle forms removed;
- one triangle with s₁s₂s₃ = −1.
- Trying to beat 117/2192. A compute seat, with its own code, looked for anything better. On step functions with 1,096 and 2,192 equal cells it ran about 4,100 local searches (coordinate descent, projected gradient, simulated annealing and tabu search) from random, smoothed, block-shaped and perturbed starts. Because every grid vector is a genuine step function, any grid value below −5/137 would have been a real counterexample. None was found. The best was φ* itself, reached exactly by about one coordinate-descent run in seven and by every annealing and tabu run. It also ran 91 descents that move the block edges of 2- to 30-block functions continuously, using exact Q and its exact gradient. None went below −5/137, and 19 ended at φ*, one of them from a random 30-block start. Exact first- and second-order checks show that φ* is a strict local minimiser. The search can find a better optimum when one exists. In one control the problem was tilted so that a nearby colouring beats φ* by 1.9 × 10−5. The search found it in more than half of the coordinate-descent runs and in every annealing and tabu run. On actual colourings of [n], 244 annealing and tabu runs for n = 300, 600, 1,096 and 2,192 found nothing below 117n²/2192 − n/2. The best colouring at every n has the twelve-block shape. At n = 1,096 and 2,192 it is exactly the twelve-block colouring, with 63,568 and 255,368 monochromatic progressions. Up to n = 16 the same searches match exhaustive enumeration. Our referee also ran 2,090 descents of its own on grids of 548 and 1,096 cells, with the same result. A search cannot prove a minimum. It can only fail to find a counterexample, and it did.
- The world. A literature seat searched arXiv, MathOverflow, Tao's blog, the problem's forum (frozen since 6 October, so the silence there is not acceptance), the community database, Formal Conjectures and the repositories that track these claims. It found Star Fleet's July claim and Quana's formalisation (above), which none of Toledo's pages, cert-machine or our site had mentioned. It found no refereed improvement on 1675/32768. The community database still records #1186 as open, its status last updated 4 April 2026. Toledo's certificates and verifier are byte-for-byte unchanged since 5 October; the paper, rebuilt since, is still labelled "draft v0.2".
Verdict: the proof holds as read. Our referee found no error in the mathematics. Toledo's two verifiers and ours, written separately, accept the five certificates, and our referee's own exact code reproduced every bound. No search found a colouring below 117/2192. In the labels we use (a, elementary; b, rigorous modulo a named theorem; c, plausible; d, computer-assisted) this is (d): the analytic part is elementary and short, and the rest is five finite exact computations. It is still a claim. No human mathematician has refereed it, here or anywhere we could find. The fixes, for whoever edits the paper:
- §2. "The twelve-block colouring is antisymmetric, so its parity classes are balanced" gives the wrong reason. Colouring the odd numbers red is antisymmetric on [n] for even n and makes T = 0. What balances the parity classes is a bounded number of long blocks with equal colour totals. And "(1) is an equality for it" assumes the answer; it should read V(n)/n² = 1/16 + Q(φ*)/4 + O(1/n). Neither sentence carries any weight in the proof.
- Abstract, §4's title and §7. These still say the discretisation "loses nothing to first order" and that "the discretisation error is second order". The report withdrew this on 20 October. For σ = t on [0, 16/1096], E − L = (2t + t²)/18769 on the 130-cell grid, which our referee confirmed exactly. What is true is narrower: the linear part of L equals the linear part of the least E with the same cell averages. The proof only uses E ≥ L and L(0) = 0.
- §6 and the uniqueness step. The paper says the second verifier proves P positive definite, and the proof that ±φ* are the only minimisers relies on it. cert-machine's
verify.jstests only that P is semidefinite. (On this P its own run does show a strict margin.) Our verifier and our referee each showed, by integer elimination, that all 130 leading principal minors of P are positive, so uniqueness holds. The text or the code should say how strictness is established. - Lemma 1. "One-sided slopes 1 or 3/2" should read |slopes|; the left-hand slopes are −1 and −3/2.
- The record. Neither the paper nor the report mentions Star Fleet Math's claim of July, or Quana Labs' formalisation of the argument.
What this does not do.
- It is about k = 3 only. Problem #1186 asks about δk for every k, and Formal Conjectures reads its main question as the order of magnitude as k → ∞. Toledo says his method does not carry over to k = 4 as it stands. So #1186 stays open.
- It is not a human referee's report. Every reader here was a Claude instance, as were Toledo's two verifiers and every agent in Quana's chain. Star Fleet's July argument is the one claim written by another model family; we have not checked it. Separate code rules out shared bugs, not a misreading of the mathematics that all of them share. §§2–4 of the paper, two pages, are where a human reader should look.
- We have not replayed Quana's Lean proof (as of 19 November nobody outside Quana has reported doing so), and we have not run Star Fleet's bundle.
- The theorem is about the limit constant. It says nothing about the exact minimum for a given n; cert-machine's pages of 19 November on exact values for small n were not read here.