Formally verified AI-led

Lean-checked proof of the Aaronson-Ambainis conjecture on influential variables of bounded polynomials

A research system at Physical Superintelligence running a non-public Anthropic model produced a proof, checked in Lean by two independent kernels, that every low-degree polynomial bounded on the Boolean cube with non-trivial variance has a variable of polynomially large influence, the conjecture Aaronson and Ambainis showed implies that quantum query algorithms can be simulated classically on most inputs with polynomially more queries.

Model
Non-public Anthropic model, run in a research harness built at PSI
Field
Computer science
Date
2026-11-06
Human collaborators
David Turturean
Problem posed
2009 · open 17 yrs

What was found

The main theorem says that every f:{−1,1}n→[−1,1]f : \{-1, 1\}^n \to [-1, 1] of degree at most dd has a coordinate jj with Infj(f)≥15500π4Var(f)5/2/d6\mathrm{Inf}_j(f) \ge \frac{\sqrt{15}}{500\pi^4}\mathrm{Var}(f)^{5/2}/d^6, which in the conjecture's own normalisation gives an influence of at least (ε/d)7(\varepsilon/d)^7, where Aaronson and Ambainis asked only for (ε/d)O(1)(\varepsilon/d)^{O(1)}. The proof follows a plan of Lovett and Zhang through level sets and fractional certificates and replaces the inequality their plan left as a conjecture with a new all-pairs inequality, obtained from a bijection produced by the lowest-degree terms of a determinant and related to Reimer's butterfly lemma; a row bound by the method of Agarwal and Ben-David supplies the degree dependence. The Lean statement of record, PrintedConjecture, sits in a file that imports only Mathlib and uses no definition of the project. For each of the four final theorems the repository records an axiom print of exactly propext, Classical.choice and Quot.sound, a kernel replay with leanchecker from an empty environment, the same replays with the independent lean4lean checker, and a sandboxed Comparator run that also rechecks the proofs with nanoda.

Novelty check

arXiv, 2026-11-16, abs:"Aaronson-Ambainis" AND abs:conjecture returned 15 records. Everything before November 2026 is partial: the conjecture for random restrictions (2402.13952), for completely bounded polynomials (2609.05201), distributional variants (2609.35327), and the August 2026 Stanford result for algorithms with a fixed number of parallel query rounds that PSI cites. The two November records are an exposition of this proof and a shorter proof that uses part of it, both recorded under independent checks. No entry in this registry covered the conjecture, and the proof is not among the entries in Palomar's recent feed read on 2026-11-16.

Caveats and known objections

Graded formal on the machine check, on the same footing as 2026-10-26-eth-refuted-claude: a sorry-free Lean development with only the standard axioms, re-checked by a second independent kernel, whose statement file is short enough for a person to compare with the conjecture. That comparison is the load-bearing step a kernel cannot make, and the only published one is vibemathed's, which records reading PrintedConjecture line by line against Conjecture 6 of arXiv:0911.0996v3 and finding that it matches. The checks are PSI's own records, run in its GitHub workflows; the proof is not registered on Palomar and the build was not rerun for this entry. The fourth Lean theorem assumes Theorem 1.7 of Agarwal and Ben-David, which is not formalized, but it only improves the constant by a factor of four; the theorem that proves the printed conjecture has no hypothesis. The paper itself is not machine-checked, and the repository lists the passages with no Lean counterpart. There is no peer review. The Stanford group's praise quoted in PSI's post is first-party framing, though its own exposition on arXiv stands as an outside reading. Jim Halverson, who audited the proof, is an adviser to PSI and so not independent. Autonomy is ai-led on the strictest defensible reading: PSI says the mathematical statements, the first draft and the Lean formalization were produced by AI models in a harness David Turturean built, that he scoped the problem and ran the system, and that he reviewed the paper and takes responsibility for it. The model is non-public, so the run cannot be reproduced, and PSI is a company announcing its own system.

Independent checks

Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan (Stanford University): Wrote a 30-page exposition of the proof after working to understand it, organised around four steps with weaker exponents than the original; the authors note they received no compensation from Anthropic or PSI and used Anthropic's public models in preparing it. · link ↗

Thomas Huffstutler, David Miloschewsky and Supartha Podder: Gave a seven-page proof of the conjecture through the completion framework that uses only a special case of Turturean's certificate inequality, for which they supply their own self-contained proof. · link ↗

Also recorded at

vibemathedthe-aaronson-ambainis-conjecture

Nothing mechanically. It is a parallel listing of the same result, carrying its own verification label rather than an independent check.

Labels it Lean-checked with the statement unaudited, while recording that its own check on 15 November 2026 read PrintedConjecture line by line against Conjecture 6 of arXiv:0911.0996v3 and found that it matches.

Disagree with these grades?

Bring a citation: a grade moves on evidence, not on argument.

Or on GitHub: submit a check challenge the grade send a correction or send a pull request

Entry history (1 event)
  1. AddedEntered the registry graded Formally verified and AI-led.

Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.

Graded formally verified for verification and ai-led for autonomy. What these mean.

Cite this entry

Plain text
whataifound.org. (2026). Lean-checked proof of the Aaronson-Ambainis conjecture on influential variables of bounded polynomials. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-11-06-aaronson-ambainis-conjecture
BibTeX
@misc{whataifound-physicalsuperintelligence-2026-conjecture,
  title        = {Lean-checked proof of the Aaronson-Ambainis conjecture on influential variables of bounded polynomials},
  author       = {{whataifound.org}},
  year         = {2026},
  howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
  note         = {Result by Physical Superintelligence (PSI). Verification: Formally verified. Autonomy: AI-led.},
  url          = {https://whataifound.org/finding/2026-11-06-aaronson-ambainis-conjecture}
}

Related findings

← All computer science findings in the registry