Deterministic black-box noncommutative singularity testing for rational linear matrices (Garg-Gurvits-Oliveira-Wigderson question)
A linear matrix with matrix coefficients is noncommutatively singular if it is not invertible over the free skew field, equivalently if is singular for every tuple of matrices of every dimension. Garg, Gurvits, Oliveira and Wigderson gave a deterministic polynomial-time algorithm for this problem that reads the coefficients (white box). In Section 6 of their Operator Scaling paper they asked for a black-box construction: a deterministic, polynomial-size list of matrix tuples, depending only on the sizes, on which every noncommutatively nonsingular pencil becomes invertible. Can such a list be constructed in deterministic polynomial time?
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Algebraic complexity; noncommutative rank; operator scaling
- Posed by
- Ankit Garg, Leonid Gurvits, Rafael Oliveira and Avi Wigderson, Operator scaling: theory and applications, Found. Comput. Math. 20 (2020), Section 6, p. 280
- Year posed
- 2020
- Years open
- 6y
- Solved
- 2026-09-24
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Unreviewed
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 34 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Claims a deterministic polynomial-time, polynomial-size list of rational matrix tuples on which every noncommutatively nonsingular rational affine pencil of bounded order becomes invertible, and a list recovering the noncommutative rank of rectangular rational pencils from ordinary ranks. It does NOT treat pencils with coefficients from other fields; the GGOW question for general fields remains.
What the AI did
The release README says all results were produced by an unreleased internal OpenAI model, the vast majority by one fixed procedure using on average about three hours of ChatGPT Pro thinking compute per result. Its named exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region, whose write-up was human edited for readability) do not concern this family. The manuscripts are credited to OpenAI with no human author named. The answer is a corollary in Section 5 (the pencil-hitting corollary) of the rational-formula hitting-list manuscript, which also gives a rank-detecting list for rectangular rational pencils.
Verification
No independent mathematician has checked this yet. The pencil-hitting corollary of the principal manuscript was read: every rational affine pencil of order at most a bound that is invertible somewhere over an extension of becomes invertible at some tuple of the same polynomial-size list. The paper calls this the rational-coefficient version of the GGOW question, so coefficients outside are not covered. The Lean statement RationalHitting concerns formulas, not pencils, so it does not cover this entry. Not rebuilt here.