Explicit restricted isometries beyond the square-root barrier (Tao's deterministic UUP question)
A restricted isometry quantifies how well a measurement matrix preserves the Euclidean geometry of sparse vectors in compressed sensing. For an matrix , the restricted isometry constant is the smallest with whenever . Random matrices give with and . In 2007 Tao asked for deterministic constructions of comparable strength. Coherence arguments stop at , and the best unconditional explicit constructions before this work (Bourgain, Dilworth, Ford, Konyagin and Kutzarova, 2011, and later refinements) reached with at most about . What is the largest exponent for which an explicit family has , , and , and can it reach the random exponent ?
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Compressed sensing; frame theory; incidence geometry
- Posed by
- Terence Tao, Open question: deterministic UUP matrices (blog post, 2 July 2007)
- Year posed
- 2007
- Years open
- 19y
- Solved
- 2026-11-10
- Model
- GPT-6 Astra; ChatGPT (GPT-6 Pro); Claude Opus 5.5; GPT-6.1 Sol
- Vendor
- OpenAI; Anthropic
- Collaborators
- Christian Kümmerle, Dustin G. Mixon
- Verification
- Lean-checked, statement unaudited
- Publication
- Preprint
- Significance
- 38 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1: there is an explicit family of real matrices with unit-norm columns such that , , and . The unconditional exponent thus rises from barely above to . The matrices are subframes of a two-distance tight frame built from the strongly regular graph , , with columns selected using Zahl's sphere-tangency bound over finite fields; the proof uses only the absolute values of the Gram entries, with no phase cancellation. Theorem 4 shows that is a barrier for every argument of that kind, and Proposition 10 shows that this construction itself cannot pass . Exponents in remain open (Problem 9 of the paper), so Tao's question is answered only in part.
What the AI did
Per the paper's disclosure, Theorem 1 was proved in one shot using GPT-6 Astra. While digesting the proof, the authors distilled the Gershgorin and flat-RIP hybrid estimate, identified the 2/3 barrier and explored subframes of two-distance tight frames, over several long conversations with ChatGPT. ChatGPT generated an initial draft; the authors then rewrote the paper completely and used ChatGPT and Claude Opus 5.5 for rounds of feedback. The authors state that they checked all mathematical claims, citations and computations and take full responsibility. The Lean formalization was created by a Claude Opus 5.5 orchestrator with GPT-6.1 Sol and GPT-6 Astra subagents.
Verification
No independent mathematician has checked this yet. Lean-checked on this site's ladder. Checked here on 19 November 2026: the arXiv paper 2611.14475v1 (introduction, Theorem 1, Section 5, acknowledgments and AI disclosure) and Tao's 2007 post that poses the problem. The Lean repository ckuemmerle/ExplicitRIPTwoThirds was read at commit fba9242 (379 Lean files, about 34,000 lines, Lean 4.35.0 with Mathlib). The frozen headline ExplicitRIP.main_theorem and the definition ripConstant were read: is the supremum, over column sets of size at most , of the operator norm of the Gram submatrix minus the identity, and the theorem states, along the primes (proved infinite), unit-norm columns, , , , and for the concrete Cholesky-factor matrices of the paper. That matches Theorem 1 except for explicitness: no running-time bound is formalized, as the paper and the README both say. A grep found no sorry outside the four deliberate stubs of Challenge.lean, and no axiom, admit, native_decide, implemented_by, extern or unsafe. comparator.json permits only propext, Quot.sound and Classical.choice. Not rebuilt here; the repository has no CI runs, and a search of the Palomar registry found no entry for it. The Lean statements were drafted and audited by AI agents for one of the authors, so the statement is not independently anchored.
Sources
- PaperarXivBourgain, Dilworth, Ford, Konyagin, Kutzarova: Explicit constructions of RIP matrices (previous record)Zahl, Sphere tangencies, line incidences, and Lie's line-sphere correspondence (key input)
- Lean proofLean formalization (ckuemmerle/ExplicitRIPTwoThirds, commit fba9242)
- Lean statementLean headline: ExplicitRIP.main_theorem (Frozen/MainTheorem.lean)
- OtherTao, Open question: deterministic UUP matrices (2007), where the problem is posed
Submitted by MellowGander562 on