1 · The essentials
These manuscripts study expressions in which changing the order of multiplication can change the answer. The goal is to choose small square arrays of numbers that reveal whether an expression is genuinely nonzero. For expressions built without division, the manuscripts describe a single choice of arrays that works for every expression within a prescribed size bound. That choice depends on the number of inputs, the size bound, and the arithmetic being used—not on the particular expression. Separate constructions cover arithmetic in positive characteristic and in characteristic zero. For expressions over the rational numbers that also allow inverses, the result instead supplies a short list of choices, provided the expression has at least one rational-matrix evaluation where all its operations are defined. This last result has a Lean formalization; the supplied source does not identify formalizations for the other two manuscripts.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine preparing one test tray that makes every nonempty recipe in a size-limited collection leave a visible mark. When recipes include operations that cannot always be performed, the guarantee changes: a short collection of trays contains at least one on which each eligible nonempty recipe both works and leaves a mark.
Why it matters
The constructions turn nonzeroness into something detectable by fixed matrix substitutions, without tailoring the substitution to each individual formula. In positive characteristic, one deterministic procedure handles any promised prime supplied as input, and its output also works with coefficients in extension fields. The rational-formula result extends the approach to inverses while explicitly accounting for whether evaluations are defined.
2 · Going further
The problem is noncommutative identity testing: detect whether a formula represents a nonzero expression when multiplication order matters. For division-free formulas, a matrix hitting point is a tuple of matrices at which every nonzero formula in the specified bounded class evaluates to a nonzero matrix. The positive-characteristic manuscript describes one deterministic machine taking a promised prime in binary and in unary. In polynomial bit time it constructs matrices over of dimension that detect every nonzero size- division-free formula in variables over every field of characteristic .
The same positive-characteristic tuple works with arbitrary extension-field coefficients, including in characteristic two. The manuscript also states applicability to its specified acyclic algebraic path programs. The characteristic-zero companion describes a single tuple of rational matrices of dimension , again constructed in deterministic polynomial bit time, that works over every field of characteristic zero.
The construction-level idea supplied by the abstracts is to replace formula-specific tests with a universally detecting matrix substitution for a bounded class. They do not describe the internal argument that produces these substitutions. The rational-formula companion changes the target from one hitting point to a polynomial-size hitting list: for every nonzero admissible rational formula over of bounded tree size, some tuple gives a defined, invertible value. Here admissibility requires a defined rational-matrix evaluation. Matrix dimensions, entry bit lengths, and total output length are polynomially bounded, with no separate bounds on inverse nesting or rational constant heights. This rational-formula manuscript is the one identified as Lean-formalized.
Useful notions
- Matrix substitution into an expression
- Multiplication where order matters
- Fields and their characteristic
- Formula size and tree size
- Polynomial bit-time computation
What was known before / what is new
Before
The source presents the distinction between division-free formulas and rational formulas, whose inverses can make evaluations undefined. It also separates positive-characteristic arithmetic from characteristic-zero arithmetic. It supplies no account of earlier bounds or historical milestones, so no comparison with prior results is asserted here.
New
The positive-characteristic manuscript shows a uniform construction of one matrix tuple for each promised prime, with dimension and validity over all fields of that characteristic. The characteristic-zero manuscript shows a rational matrix tuple of dimension that works over every characteristic-zero field. The Lean-formalized companion supplies polynomial-size hitting lists for admissible noncommutative rational formulas over , with a defined, invertible evaluation guaranteed for every nonzero formula in the bounded class.
Limits and assumptions
The single-point guarantees concern bounded-size division-free formulas; the positive-characteristic extension to path programs is only for the class stated in that manuscript. Its algorithm assumes a promised prime in binary and size parameters in unary. The rational-formula guarantee concerns bounded tree size over and requires at least one defined rational-matrix evaluation; it supplies a list, not a single universal tuple. The source explicitly identifies the rational-formula result as Lean-formalized, but does not identify formalizations for the two single-point constructions or specify finer formalization coverage. It states no remaining open problems.
Mini glossary
- Noncommutative formula —
- An expression in which the order of multiplication matters.
- Division-free formula —
- A formula that uses no division or inverse operations.
- Matrix hitting point —
- A fixed tuple of matrices that gives a nonzero evaluation for every nonzero formula in a specified class.
- Characteristic —
- The characteristic of a field records whether repeatedly adding one first gives zero after a positive number of additions, or never does, in which case the characteristic is zero.
- Admissible rational formula —
- In the stated rational-formula setting, this is a formula that has at least one rational-matrix evaluation at which all operations are defined.
- Hitting list —
- A collection of matrix tuples containing, for each target nonzero formula, at least one tuple that detects it.
Keywords : Noncommutative identity testing · Matrix hitting points · Rational formulas
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Uniform Matrix Hitting Points in Every Positive Characteristic
04/10/2026We 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 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.
One Rational Matrix Hitting Point for Noncommutative Formulas
24/09/2026We construct, in deterministic polynomial bit time, one tuple of rational matrices that detects every nonzero polynomial computed by a noncommutative division-free formula of a prescribed size. The matrices have dimension for n variables and formula size s, and the same tuple works over every field of characteristic zero.
Polynomial Hitting Lists for Noncommutative Rational Formulas
24/09/2026We 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.