Superpolynomial lower bound for the bit pigeonhole principle in unrestricted resolution over parities
Resolution over parities, , extends resolution to disjunctions of affine equations over . Exponential lower bounds are known for tree-like, regular and bounded-depth fragments, but no superpolynomial lower bound for unrestricted DAG-like is known for any formula. Does the bit pigeonhole principle with pigeons and holes require superpolynomially many nodes in unrestricted DAG-like ?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Proof complexity; resolution over parities
- Posed by
- Itsykson and Sokolov (2014), who introduced the system; named as the open benchmark by Efremenko-Garlik-Itsykson (2024) and Itsykson-Podolskii-Shekhovtsov (2026) among others
- Year posed
- 2014
- Years open
- 12y
- Solved
- 2026-09-15
- Model
- GPT-6 Astra; Claude Sonnet 5; Claude Fable 5.1; Claude Opus 5
- Vendor
- OpenAI; Anthropic
- Collaborators
- Kamil Braun
- Verification
- Lean-verified
- Publication
- Announced
- Significance
- 35 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Claimed: for every K there is L such that for every l >= L, any dag-like Res(+) refutation of the bit pigeonhole principle with 2^l + 1 pigeons and 2^l holes has more than (2^l)^K nodes; superpolynomial in the number of holes, for a proof system with no regularity or depth restriction. The whitepaper's route is a transfer to degree-O(log n) polynomial calculus. Candidate: kernel-checked and statement audited, read by no specialist.
What the AI did
GPT-6 Astra was the principal contributor to the mathematical development, manuscript drafting, and Lean formalization. Earlier exploration involved Claude Sonnet 5, Fable 5.1, and Opus 5. Kamil Braun designed and directed the Noemesis research framework, supplied goals and steering, and organized the verification and publication effort. Section 8.3 of the manuscript describes the contributions and development history.
Verification
Held on 15 September 2026 for one reason: nothing outside the author's machine had compiled the proof. Lifted on 22 September. GitHub Actions run 34953139115 (15 September, commit 3979e0c, a fresh ubuntu-24.04 runner, mathlib cache fetched for dependencies only and .lake/build deleted before the build) ran `lake --wfail build claims.BitPHPSuperpolynomial`, completed 2,484 jobs, printed MathResearch.bitPHP_superpolynomial with axioms propext, Classical.choice and Quot.sound, and then replayed the final module in a fresh leanchecker kernel; a second dispatch run on 17 September also succeeded. The claim file at 3979e0c is byte-identical to the one audited here at 54f0937 on 15 September: the final theorem quantifies over every AffineDAG over the standard bit-PHP initial clauses with a node deriving the empty clause and bounds the node count below by (2^l)^K; AffineDAGStep allows initial clauses, semantic weakening, resolution on a parity literal against its complement and any sound two-premise rule, with nodes referencing any earlier node and no regularity or depth constraint, a superset of dag-like Res(+); usualCNFClause is the standard bit-PHP axiom over all pairs and all 2^l labels; no sorry, no custom axiom, no native_decide in 81 files; the chessboard homology is proved, not assumed. Kernel-checked on a machine other than the author's and statement audited: Lean-verified. No specialist has read the argument.
Sources
Submitted by FrostyWalrus278 on