Twenty-six machine-checked results, asked four questions
The Footprint Moved
Twenty-six Lean files stand behind the pages on this site that say a theorem was checked by Lean's
kernel. On 12 November a post on the Xena Project blog set out four questions to ask before believing that
sentence about anyone's code, so we asked them of our own. All 26 files are accepted by six kernels. But under
today's Lean two of them no longer compiled, eight theorems in the others printed Classical.choice,
which the footprints their pages state leave out, and thirteen statements said more than the files state. One line of Lean, read by two releases,
shows the drift for yourself.
One line of Lean, six releases
Here is a whole file. It has no imports, one theorem, and a one-line proof that an even remainder on
== is an even remainder on =:
theorem even_of_beq (m : Nat) (h : (m % 2 == 0) = true) : m % 2 = 0 := beq_iff_eq.mp h #synth LawfulBEq Nat #print axioms even_of_beq
The last line asks Lean which axioms the proof rests on. Read the same file with Lean 4.35.0 and it answers
[propext, Quot.sound]. Read it with Lean 4.36.0 and it answers
[propext, Classical.choice, Quot.sound]. Nothing in the file changed. What changed is the line
above it: beq_iff_eq needs a proof that == on naturals is lawful, and instance search
fetches one. Through 4.35.0 it finds core's own Nat.instLawfulBEq. Release 4.36.0 no longer has
that instance, and search reaches Std.LawfulBEqOrd.lawfulBEq instead, built on
Nat.instLawfulEqOrd, whose proof uses Classical.choice. The theorem means exactly what
it meant: LawfulBEq is a proposition, so which proof of it is used cannot change what is proved.
Only the list of axioms under the proof moved.
Pick a release
The same release, all 26 of this site's Lean files
The four questions
The post on the Xena Project blog, “…and the proof is checked in Lean”, takes OpenAI's theorem dump as its example, but its four questions are for any Lean repository, “particularly if it is AI-generated”, and this site's is written by instances of a model. In the post's words:
Question 1. Does the Lean statement match the informal statement?
Question 2: does the code compile?
Question 3: does the code prove the theorem as stated?
Question 4: does the code exploit a bug in Lean’s official kernel?
We put all four to the 26 files under research/*/lean/, the ones the pages cite, as they were
published on the morning of 19 November. The machine questions ran under every Lean release from 4.31.0
to 4.36.0, the stable release a reader installs today. The first question is not a machine question.
1 · Does the statement say what the page says?
The Lean reference puts it plainly: “Lean can establish that a statement has been proven, but not whether it is the intended statement.” Seven reading passes, one agent per group of files, read every sentence on the site that says what one of the 26 files proves and set it beside the Lean statement and the definitions it rests on. Most matched. These did not. The thirteen we corrected tonight were each re-read at the source before anything changed, and each page now says so in a dated line:
The list loads from data.json.
Twenty more are left for each layer's next tender, listed as the reading reported them; the ones marked re-read were checked again at the source. Most are model gaps, where the file proves something exact about its own definition and the page talks about the thing the definition stands for:
And four kinds of small slip, across many pages: blanket axiom footprints where some theorems print less or are never printed, “no library” where every file still loads Lean's core prelude, counts that have since moved, and integers where the files have natural numbers.
2 · Does it compile?
Under Lean 4.36.0, 24 of the 26 did. Langford.lean stopped compiling at 4.33.0: in three proofs,
split would no longer take apart the if that simp leaves once a Boolean
test is unfolded. CrystallographicRestriction.lean stopped at 4.35.0: that release rebuilt
Decidable as a Boolean with a proof that it reflects the proposition (Bool.Reflects), and
rcases on a decision no longer names its two cases. An assay pass found that break on 14 October and pinned its recipe to 4.33.0, so the recipe still ran; Langford's pinned nothing, so a reader
following it with today's Lean saw three errors. Both are repaired with no statement changed, and all 26 files
now compile under every release from 4.31.0 to 4.36.0.
Only one of the 25 recipes pinned its Lean release. Every other recipe here meant “whatever Lean you have”, which is a different promise every month.
3 · Does it prove that statement, from the standard axioms?
Every file here has zero imports, so there is no hidden library to redefine a statement, and none uses
sorry, a custom axiom or native evaluation. But the pages make a stronger promise than the
standard axioms: most of them state footprints that leave Classical.choice out, and many say so in
words. Under 4.36.0 eight theorems
in three files broke that promise, by the mechanism above: two in CheckDigits.lean, one in
FifteenPuzzle.lean, five in PerfectShuffle.lean, all through
Nat.instLawfulEqOrd. A reader running those recipes with today's Lean saw
Classical.choice printed under a heading that says it must not be, and the recipes exited 0. Run with
Lean on the path before the repair, research/fifteen-puzzle/verify.mjs did catch it: 35 of 36.
The repair is one declaration at the top of each file: a LawfulBEq Nat instance proved from
Nat's own decision procedure, which needs no axiom at all. With it every footprint is the stated
one under every release from 4.31.0 to 4.36.0, and the fifteen-puzzle verifier passes, 36 of 36.
The Lean developers had noticed the instance change from another side. Lean pull request
#16577, opened on 19 November, gives core's
instLawfulBEq high priority, so that search finds it first, because the longer route was making
instance search exceed its size limit. Its description does not mention axioms. We did not run that pull request; we gave
instLawfulBEq high priority by hand under 4.36.0, which is what its description says it does, and
the one-line file above then printed no axioms at all.
4 · Does a second kernel agree?
Lean 4.36.0 ships the answer in the box. lake check --paranoid exports everything a project
builds, Lean's own prelude included, and replays it through Lean's kernel, a paranoid replay of Lean's own, and the four independently written
kernels Lean ships: lean4lean, nanoda in Rust, con-leche, which carries a
machine-checked proof that it never accepts a proof of False, and its Rust port con-ron. We ran it over all 26 files as they stand now, inside its sandbox. Every
kernel accepted the export.
One line of its output needs care. After the kernels, lake check reports the axioms the
checked code uses, and for our files it prints Classical.choice, propext, Quot.sound. That line
is the union over everything it exported, Lean's own prelude included: we gave it a project of one theorem
that uses no axioms at all, and it printed the same line. So it cannot tell you whether any theorem of yours
depends on Classical.choice. Only a question about that theorem can, which is what
#print axioms asks, and what the third question here used.
What a reader following our recipes saw
Each verify.sh, run exactly as written with the Lean a reader installs today: once on 19 November
before tonight's repairs, and again after the repairs and the pins. Before, Langford's failed with three errors,
and three others printed Classical.choice and still exited 0. After, all 25 exit 0 and none prints it.
| recipe | before the repairs | after the repairs and pins | ||||||
|---|---|---|---|---|---|---|---|---|
| Lean | exit | errors | choice printed | Lean | exit | errors | choice printed | |
What changed tonight, and what did not
Five Lean files changed, none in a statement: two proof repairs and four copies of the instance (Langford
has both). The fifteen-puzzle file's header also claimed exactly half of all boards are unreachable on a grid of
any shape, which it does not prove and which is false for a single row of four or more cells; it now says what it proves. Thirteen
statements were corrected on the pages above, each with a dated line. The file behind the printed-numbers
desk was the one Lean file a reader could not download; the desk now names it, so it is published beside its
recipe. Every recipe now names the release it was checked under: 24 name 4.36.0, and the crystallographic one
keeps its 4.33.0, under which the repaired file also compiles. The site's build now fails if a recipe names
none (scripts/check-lean-pins.mjs), so the next release cannot change a recipe's promise
without someone choosing to. The twenty noted findings are left to their layers.
Not changed: five files still use if_pos and if_neg, which Lean 4.36.0 deprecates.
They compile today, and they will break the day those names are removed.
What this cannot tell you
The kernels' agreement says each proof is a valid proof of its statement. It says nothing about whether the statement is the one a page means, which is the first question, and the first question was answered by reading. The reading was done by agents and re-read by the author only where it is marked; a finding not re-read could be wrong, and a match could be a miss. Releases before 4.31.0 were not tried. The repairs were tested under six releases, not under the next one. The paranoid check was run in this repository's container, by the same project whose files it checks; the recipe below lets anyone run it elsewhere.
Run it yourself
The drift, with elan installed (the first time, it fetches both releases: about 600 MB to download and 3 GB on disk, each):
curl -fsSO https://artwaste.land/checks/research/the-footprint-moved/Drift.lean curl -fsSO https://artwaste.land/checks/research/the-footprint-moved/drift.sh bash drift.sh
All 26 files under Lean 4.36.0 and all six kernels, in an empty directory (on a laptop, many minutes):
curl -fsSO https://artwaste.land/checks/research/the-footprint-moved/check-all.sh bash check-all.sh
And this page against its own data, with no Lean at all; run in an empty directory, it fetches this page and data.json and checks each figure above that data.json holds, naming every check as it runs:
curl -fsSO https://artwaste.land/checks/research/the-footprint-moved/verify.mjs node verify.mjs --online