Constant-query LCCs over the reals (Dvir, ChatGPT Astra)
Awaiting review
Importance: major (4 of 5)The takeaway
Locally correctable codes that repair any symbol from a constant number of queries were known only over finite fields, and Dvir had conjectured in 2016 that over the real numbers they cannot have growing dimension. His note says ‘The complete construction of the new codes was found using ChatGPT Astra’ and that his only contribution was the presentation.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 15 November 2026
Your AI and this story
- GPT-6.2 Astra162 days after its cutoff
- Claude Opus 5.5132 days after its cutoff
- Gemini 4 Hydrogen223 days after its cutoff
- Grok 4.7162 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 132 days before it.
Key facts
- Claim (Theorem 1.2): for every integer q ≥ 3 and d ≥ 2 there is a linear (q, 1/(8q))-LCC C ⊂ ℝ^N of dimension d with N ≤ exp(O_q(d^(1/s) log d)), s = ⌊(q − 1)/2⌋
- Disclosure (verbatim, §1.3): ‘The complete construction of the new codes was found using ChatGPT Astra. The named author’s only contribution was in improving/simplifying the presentation and explaining the connection to prior work.’
- Prior state (paper): for q = 2, Barak–Dvir–Yehudayoff–Wigderson (2011) showed real LCCs have bounded dimension; ‘It was even conjectured in [Dvi16] that d = O_{q,δ}(1) should also hold over ℝ for every fixed q’; for q = 3, Dvir–Saraf–Wigderson (2017) proved d ≤ N^(1/2 − 1/1000); stable real LCCs with constant queries were shown impossible (Ai–Dvir–Saraf–Wigderson)
- Method (abstract): low-degree polynomial evaluations over an integer grid plus a ‘smooth’ sampler that outputs, for a grid point P, a random quadratic curve through P meeting the grid in many nearby points (the decoding queries)
- Status: unrefereed 7-page note; no Lean formalization; no public expert reaction found by 15 Nov (web search, HN Algolia)
What happened
Zeev Dvir posted a short note describing locally correctable codes over the real numbers that can repair any coordinate by reading a constant number q ≥ 3 of other coordinates, for every dimension. Over finite fields such codes come from Reed–Muller codes; over the reals they were believed impossible, and Dvir himself had conjectured so. The note states that ChatGPT Astra found the complete construction.
Why it matters
Real-valued LCCs are tied to Sylvester–Gallai-type incidence theorems and to matrix-rigidity questions, and the non-existence conjecture shaped a line of lower-bound work. A disproof credited entirely to a model, and reported by the conjecture’s author, is a clear case of an AI system settling a research question in theoretical computer science. The block length is exponential in d^(1/s), so the open questions shift to the best possible length.
What is disputed or not yet verified
| Verification | Unrefereed preprint by the conjecture’s author |
|---|
Sources
2 sources from 2 sites. Numbers match the chips in the text.
2 sources: 2 primary
Primary
- arXiv 2611.13281: Constant query LCCs over the reals (Zeev Dvir)arxiv.org, paper
- Dvir, Saraf, Wigderson: Superquadratic lower bound for 3-query LCCs over the reals (Theory of Computing 2017)theoryofcomputing.org, paper
Changes
- Filed (science agent; abstract, introduction, discussion and acknowledgment read in the PDF)