Browse › Theoretical computer science › 116 Uniform black-box noncommutative identity testing across characteristics
Polynomial Hitting Lists for Noncommutative Rational Formulas
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 construct, in deterministic polynomial bit time, a polynomial-size list of rational matrix tuples for noncommutative rational formulas over ℚ of bounded tree size. Every nonzero admissible formula has a defined, invertible value at one tuple, with no separate bounds on inverse nesting or rational constant heights. Matrix dimensions, entry bit lengths, and total output length are polynomially bounded.
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.
Formalization
- OpenAI math release, Uniform black-box noncommutative identity testing across characteristics: Lean scope notes (release Lean development, October 2026). The release's Lean formalization states the polynomial-size hitting-list theorem for rational formulas over $\mathbb Q$ (invertible value at some listed tuple, with polynomial dimension, output length and running time; comparator statement
RationalHitting.lean); the scope note does not list the pencil-hitting or noncommutative-rank corollaries. [family-level]
Related prior literature mentioned by others
- V. Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay, Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time (arXiv:2309.15647, revised 2025-07-11). Identified in VibeMathed's family entry as the predecessor posing the polynomial-dimension question; it constructs quasipolynomial-size hitting sets for rational formulas with unrestricted inverse nesting.
- Michael A. Forbes and Amir Shpilka, Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs (FOCS 2013; arXiv:1209.2408, revised 2013-09-22). VibeMathed's family entry identifies this quasipolynomial black-box hitting-set construction for noncommutative branching programs and division-free formulas as background to the family's claimed polynomial constructions. [family-level]
Possibly relevant literature (found by the agent, not checked)
- V. Arvind, A. Chatterjee, U. Ghosal, P. Mukhopadhyay, C. Ramya, On Identity Testing and Noncommutative Rank Computation over the Free Skew Field (arXiv:2209.04797, 2022). Studies black-box rational identity testing and deterministic noncommutative-rank computation for matrices with small linear-pencil entries, related to the paper's rank-detecting list for rectangular affine pencils.
Elsewhere
- VibeMathed: Problem record
- VibeMathed: Problem record
- Emergent Mind: family 116
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Polynomial-Hitting-Lists-for-Noncommutative-Rational-Formulas-September-24-2026,
author = {{OpenAI}},
title = {{Polynomial Hitting Lists for Noncommutative Rational Formulas}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Polynomial-Hitting-Lists-for-Noncommutative-Rational-Formulas-September-24-2026/Polynomial-Hitting-Lists-for-Noncommutative-Rational-Formulas-September-24-2026.pdf}{OAI:Polynomial-Hitting-Lists-for-Noncommutative-Rational-Formulas-September-24-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/116.md. The Lean statements have not been checked by people against the paper's claims.
Family 116: Uniform black-box noncommutative identity testing across characteristics
For each characteristic, constructs in deterministic polynomial bit time a polynomial-dimensional matrix tuple detecting every nonzero division-free noncommutative formula of bounded size over any field of that characteristic. Rational formulas over ℚ also admit polynomial-size hitting lists whenever they have a defined rational-matrix evaluation.
Other papers in this family:
- Uniform Matrix Hitting Points in Every Positive Characteristic · October 4, 2026
- One Rational Matrix Hitting Point for Noncommutative Formulas · September 24, 2026