oai-math-revised beta

Browse › Theoretical computer science › 116 Uniform black-box noncommutative identity testing across characteristics

Uniform Matrix Hitting Points in Every Positive Characteristic

OpenAI · October 4, 2026

Lean

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 a single matrix substitution that detects every nonzero size-s division-free noncommutative formula in n variables over every field of a given positive characteristic. One deterministic machine, given a promised prime p in binary and n, s in unary, outputs matrices over 𝔽p of dimension $O(n^3s^6)$ in polynomial bit time. The same tuple works with arbitrary extension-field coefficients, including in characteristic two. The construction also applies to the stated acyclic algebraic path programs.

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.

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic-October-4-2026,
  author = {{OpenAI}},
  title = {{Uniform Matrix Hitting Points in Every Positive Characteristic}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic-October-4-2026/uniform-matrix-hitting-points-positive-characteristic.pdf}{OAI:Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic-October-4-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: