VibeMathedMath problems solved with AI

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 m×nm \times n matrix Φ\Phi, the restricted isometry constant δk\delta_k is the smallest δ\delta with (1−δ)∥z∥22≤∥Φz∥22≤(1+δ)∥z∥22(1-\delta)\|z\|_2^2 \le \|\Phi z\|_2^2 \le (1+\delta)\|z\|_2^2 whenever ∣supp⁡(z)∣≤k|\operatorname{supp}(z)| \le k. Random matrices give δk→0\delta_k \to 0 with m/n→0m/n \to 0 and k=m1−o(1)k = m^{1-o(1)}. In 2007 Tao asked for deterministic constructions of comparable strength. Coherence arguments stop at k≈m1/2k \approx m^{1/2}, and the best unconditional explicit constructions before this work (Bourgain, Dilworth, Ford, Konyagin and Kutzarova, 2011, and later refinements) reached k=m1/2+ε0−o(1)k = m^{1/2+\varepsilon_0-o(1)} with ε0\varepsilon_0 at most about 8⋅10−88\cdot 10^{-8}. What is the largest exponent α\alpha for which an explicit family has m→∞m \to \infty, m/n→0m/n \to 0, δk→0\delta_k \to 0 and k=mα−o(1)k = m^{\alpha-o(1)}, and can it reach the random exponent α=1\alpha = 1?

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 m×nm \times n matrices with unit-norm columns such that m→∞m \to \infty, m/n→0m/n \to 0, δk→0\delta_k \to 0 and k=m2/3−o(1)k = m^{2/3-o(1)}. The unconditional exponent thus rises from barely above 1/21/2 to 2/32/3. The matrices are subframes of a two-distance tight frame built from the strongly regular graph VO4−(p)VO_4^-(p), p≡3(mod4)p \equiv 3 \pmod 4, 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 2/32/3 is a barrier for every argument of that kind, and Proposition 10 shows that this construction itself cannot pass 2/32/3. Exponents in (2/3,1](2/3,1] 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: δk\delta_k is the supremum, over column sets of size at most kk, of the operator norm of the Gram submatrix minus the identity, and the theorem states, along the primes p≡3(mod4)p \equiv 3 \pmod 4 (proved infinite), unit-norm columns, m,n→∞m, n \to \infty, m/n→0m/n \to 0, δk→0\delta_k \to 0, k≤m2/3k \le m^{2/3} and log⁡k/log⁡m→2/3\log k/\log m \to 2/3 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

Submitted by MellowGander562 on

Changelog2 changes

Discussion