Tokareva’s bent-function conjecture disproved by LLM agents
Awaiting review
The takeaway
Every Boolean function of degree ≤ n/2 is a sum of two bent functions: that conjecture of Natalia Tokareva, listed among Carlet’s open problems, fails in every even dimension n ≥ 8. The counterexample x₁x₂(x₃x₄+x₅x₆+x₇x₈) was found by 19 rounds of up to 100 MiniMax M3.1-Flash-Preview agents (1,889 reports) with separate audit rounds. Two key equations are checked in Lean.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 26 October 2026
Your AI and this story
- GPT-6 Astra176 days after its cutoff
- Claude Opus 5.5115 days after its cutoff
- Gemini 4 Argon206 days after its cutoff
- Grok 4.7145 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 115 days before it.
Key facts
- Conjecture (Tokareva; Carlet’s ‘Open Problem 2’): for even n, every Boolean function on F₂ⁿ of algebraic degree ≤ n/2 is a sum of two bent functions. Previously verified for even n ≤ 6 and some special classes. A positive answer would have closed the gap in asymptotic order between bounds on the number of bent functions
- Result: f₈ = x₁x₂(x₃x₄+x₅x₆+x₇x₈) ∉ B₈+B₈; counterexamples in every even dimension n ≥ 8; explicit counterexamples to the derivative conjecture for even n ≥ 10
- AI statement (verbatim): ‘The counterexamples and proofs in this paper were obtained through large-scale automated reasoning with LLM agents while solving Problem 10 in NSUCRYPTO 2026 (MiniMax M3.1-Flash-Preview, 19 rounds of up to 100 independent agents between 12 and 18 October 2026, 1889 reports in all), paired with 8 rounds of independent audits (227 reports).’
- Audit caught an error (verbatim): ‘an early attempt to prove that f8 ∉ B8+B8 was discarded during the audit phase because it mistakenly treated the Walsh transform as additive. Another agent then established Equation (3.1) and confirmed that f8 is indeed a counterexample’
- In the first 10 rounds the agents decomposed every cubic on F₂⁸ and the first quartic candidate into two bent functions, which narrowed the search
- Verification: ‘Every statement in this paper was subsequently checked by the authors. We also provide a formal verification for Equation (4.2) and Equation (4.7) in Lean 4.’
- Context: NSUCRYPTO is the international cryptography olympiad of Novosibirsk State University; its ‘unsolved problems’ track poses open research problems. A small, fast model from MiniMax (a Chinese lab) did the search, not a frontier model
What happened
Bent functions are Boolean functions that are as far from linear as possible, which makes them useful in cryptography. Rothaus showed that they have degree at most n/2, so a sum of two of them does too. Natalia Tokareva asked whether every function of degree at most n/2 arises this way. Claude Carlet recorded the question as an open problem.
A team of five posted a no answer on 23 Oct. They worked on it as Problem 10 of the 2026 NSUCRYPTO olympiad with a swarm of MiniMax M3.1-Flash-Preview agents. Over a week, the agents ran 19 rounds with up to 100 independent instances each, and eight further rounds audited their output. One early “proof” was thrown out because it treated the Walsh transform as additive. A later agent proved the needed identity, and the authors generalised the example to all even dimensions.
Why it matters
This is a disproof of a named conjecture in cryptographic Boolean-function theory, made by many runs of a cheap model with a separate audit stage rather than by one frontier model. The record notes that the audit stage caught a false proof.
What is disputed or not yet verified
| Verification | Unrefereed arXiv preprint; partial Lean 4 formalization (Eq. 4.2, 4.7) |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed (arXiv PDF read)