A noncommutative rational formula in the variables is a rooted tree whose leaves are variables or rational constants, whose binary gates are additions or ordered multiplications, and whose unary gates are inversions. Its size is its number of vertices, leaves and inverse gates included. At a tuple of rational matrices, the formula is evaluated with each rational constant read as . It is defined there when every inverse gate of its tree, including gates in branches whose contribution later cancels, receives an invertible matrix. A formula is admissible when it is defined at some tuple of rational matrices of positive dimension. An admissible formula is nonzero when one of its defined values is nonzero. Identity testing asks whether an admissible formula vanishes at every tuple where it is defined. A matrix hitting list for a class of formulas is a fixed finite list of matrix tuples such that every nonzero formula of the class has a defined nonzero value at one of them. The question is whether a deterministic machine can write, for the formulas in variables of size at most , a matrix hitting list, from and alone and in time polynomial in .
Hrubeš and Wigderson developed this model of rational formulas and its reduction to testing whether a matrix of linear forms is singular. Deterministic polynomial-time identity testing with access to the formula followed from the operator scaling of Garg, Gurvits, Oliveira and Wigderson and the constructive noncommutative rank computation of Ivanyos, Qiao and Subrahmanyam. Derksen and Makam established polynomial bounds on the dimension of the matrices at which an admissible formula has a defined evaluation. From these bounds they derived randomized polynomial-time identity testing. Arvind, Chatterjee and Mukhopadhyay constructed deterministic quasipolynomial-size hitting sets for rational formulas whose inverse gates nest to depth at most two. Arvind, Chatterjee and Mukhopadhyay then obtained quasipolynomial-size rational matrix hitting sets with no bound on the nesting of inverse gates. In the conclusion of that work they ask for polynomial matrix dimension.
The preprint proves that there are a deterministic Turing machine and positive integers such that, for all , the machine on input writes, within bit operations and in at most bits, a list of -tuples of rational square matrices such that every nonzero admissible formula in variables of size at most , whatever its rational constants and the nesting of its inverse gates, has a defined invertible value at some tuple of . The preprint’s corollaries on rational affine linear pencils, among them a list that recovers the noncommutative rank of every rectangular such pencil of given shape, are not in the Lean library.
The results on these pages are those of the Lean library RationalHitting, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library, so the Lean library is the reference: where the preprint states a result differently, the statement on the page is the Lean library’s, with the preprint’s given beside it. The preprint is a guide only, giving the results their order and their names. The Lean library proves the theorem above with no hypothesis, for one deterministic Turing machine with four tape symbols. Started on the word , this machine halts within steps with the list encoded in binary on its tape. For its list, the Lean library bounds the dimension by and the length of the encoding by a fixed constant times . OpenAI’s catalog entry also lists Uniform Matrix Hitting Points in Every Positive Characteristic, which the Lean library does not cover, and One Rational Matrix Hitting Point for Noncommutative Formulas, of which the Lean library contains only the Wronskian lemma, its Lemma 4.1. The main theorem of that preprint, for given and one tuple of rational matrices at which every nonzero division-free formula in variables with at most gates evaluates to a nonzero matrix, is formalized in another Lean library, which these pages do not present.
RationalHitting is a Lean library: 22 items, in six groups. Each has a page written by OctoInform, listed below.
No item matches.