certified
There is a permutation of the natural numbers containing no four-term arithmetic progression in increasing or decreasing order. This disproves the conjecture that every permutation must contain one.
Submitted by JenW1N
The PDF is a working mathematical exposition. Lean verification applies to the formal source, not the prose.
Certified 14 Sept 2026, published by conjectures.io.
Review decision
Approved in reviewREVIEW_APPROVED
Approved under policy v2: REVIEW_APPROVED, for the full locked conjecture bounty. The submission constructs a bijection of all natural numbers avoiding four-term arithmetic progressions in both increasing and decreasing value order along increasing indices, refuting the exact Erdős 196 target. The reviewed predicate includes both orientations; changing from positive integers to zero-based naturals is immaterial under translation. A finite saturation argument and extension lemma yield nested finite stages that eventually contain every natural number. The proof establishes injectivity and surjectivity separately and proves unrestricted progression avoidance before constructing the final equivalence. No unproved extension assumption remains. The inspected [SamuelSchlesinger research record](https://github.com/SamuelSchlesinger/erdos-problems/blob/9f18b1d6bb2c144761e47d304282f0ce3fec5631/research/permutation-monotone-ap/RESULTS.md) leaves its full permutation construction conditional on missing finite-feasibility or merge obligations. Its restricted results do not establish this target. [Geneson's introduction](https://arxiv.org/html/2608.12604v1) distinguishes its density results from an enumeration of all naturals avoiding four-term progressions; [LeSaulnier–Vijay](https://www.sciencedirect.com/science/article/pii/S0012365X10003936) impose an odd-difference restriction absent here. The retained comparison did not establish distinctive copied proof blocks. The exact accepted proof and task passed production verification and a fresh isolated replay on 10 September 2026, including statement, dependency, permitted-axiom, and Lean-kernel checks. No material formalization defect or published disqualification reason was established by the recorded review. Under v2, unresolved provenance questions alone do not justify denying the reward. This is an eligibility decision, not a guarantee of originality. The verification replays used the Lean default kernel; an independent-kernel check was not performed.
Approved · decided 11 Sept 2026
Formal statement
True ↔ ∀ (f : ℕ ≃ ℕ), HasMonotoneAP (⇑f) 4Verification report
Every box below had to hold before the proof counted. They are grouped in the order the verifier reaches them.
Manifest valid — Passed
The task bundle held together: the exact file set, a strict manifest, and every trusted hash matching the bytes on disk.
Task commitment matches — Passed
The bundle digest the submission committed to is the digest of the bundle that was actually verified.
Production task — Passed
The task came from the production pool rather than a test fixture.
Trusted file hashes match — Passed
The pinned dependencies agree across the manifest, the lockfile and the checkout, down to the same Formal Conjectures commit.
Submission policy respected — Passed
The submitted source passed the static scan: no imports, no axiom declarations, no sorry, no native_decide, no unsafe options.
Production sandbox — Passed
The run happened under real isolation, Landrun with seccomp, and the sandbox passed its own live self-test before the proof was touched.
Challenge built — Passed
The trusted Challenge.lean, which contains no miner code, compiled on its own.
Source type hash matches — Passed
The source theorem in the compiled environment still hashes to the type recorded in the task, so the statement has not drifted upstream.
Solution built — Passed
The submitted Solution.lean compiled.
Statement unchanged — Passed
The theorem the proof establishes has exactly the same canonical type as the task's target - it was not weakened or restated.
Only permitted axioms — Passed
The transitive axiom closure of the proof stays inside the axioms this task permits.
Lean kernel accepted — Passed
The Lean kernel replayed the proof and accepted it.
Nanoda accepted — Not run
A second kernel, written independently of Lean's, also accepted the proof.
One kernel, not two
This task does not require a second, independent kernel, so Nanoda was not run. The verdict rests on a single kernel implementation.
Theorems established
Stage COMPLETED · Axioms permitted: propext, Quot.sound, Classical.choice