Browse › Theoretical computer science › 141 Existential–universal real sentences in the counting hierarchy
Existential–universal real sentences in the counting hierarchy
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We prove that the existential theory of the reals lies in the counting hierarchy. More generally, we show that the truth of existential–universal sentences over the reals can be decided in a fixed level of the counting hierarchy, even when the integer polynomials are given by arithmetic circuits.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Alex Meiburg, ∃ℝ ⊆ CH (arXiv:2610.10514, 2026-10-07; also as Zenodo working paper, doi:10.5281/zenodo.23221364). This concurrent manuscript claims ∃ℝ ⊆ BPP^C₃ ⊆ C₄P, plus counting-hierarchy bounds for every fixed number of alternating real quantifier blocks. Its author's note compares this with OpenAI's "very similar proof" giving the weaker bound C₂₆P. [AI-generated per source]
Comments and discussion
- Peter Bürgisser, Intractability of Hilbert's Nullstellensatz implies algebraic hardness of permanent (arXiv:2606.25121v2, revised 2026-10-19). Question 6.1 asks whether the existential theory of the reals is in the counting hierarchy; version 2 notes that "several ChatGPT generated papers have appeared, claiming an affirmative solution" and that none has been humanly verified, citing this preprint and Meiburg's.
Digests and expositions
- AI Proved What?, Real solutions at level 26? (Episode 141, October 2026). This AI-assisted video and written exposition describe the paper's claimed containments and outline its quartic reduction, penalty minimization, implicit counting computations, and treatment of the universal block. [AI-generated per source]
Elsewhere
- Emergent Mind: family 141
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Existential-universal-real-sentences-in-the-counting-hierarchy-October-4-2026,
author = {{OpenAI}},
title = {{Existential--universal real sentences in the counting hierarchy}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Existential-universal-real-sentences-in-the-counting-hierarchy-October-4-2026/etr-counting-hierarchy.pdf}{OAI:Existential-universal-real-sentences-in-the-counting-hierarchy-October-4-2026}},
year = {2026}
}Family 141: Existential–universal real sentences in the counting hierarchy
Proves that the existential theory of the reals lies in the counting hierarchy. More generally, truth of existential–universal real sentences can be decided at one fixed level of that hierarchy, even when their integer polynomials are specified by arithmetic circuits.
This is the only paper in this family.