OctoInform Beta

Polynomial Hitting Lists for Noncommutative Rational Formulas

A noncommutative rational formula in the variables x1,…,xnx_1,\ldots,x_n 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 d×dd\times d rational matrices, the formula is evaluated with each rational constant cc read as cIdcI_d. 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 nn variables of size at most ss, a matrix hitting list, from 1n1^n and 1s1^s alone and in time polynomial in n+sn+s.

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 GG and positive integers C,kC,k such that, for all n,s≥1n,s\geq 1, the machine GG on input 1n,1s1^n,1^s writes, within C(n+s+1)kC(n+s+1)^k bit operations and in at most C(n+s+1)kC(n+s+1)^k bits, a list ℋn,s\mathcal{H}_{n,s} of nn-tuples of rational square matrices such that every nonzero admissible formula in nn variables of size at most ss, whatever its rational constants and the nesting of its inverse gates, has a defined invertible value at some tuple of ℋn,s\mathcal{H}_{n,s}. 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 1n01s1^n01^s, this machine halts within C(n+s+1)kC(n+s+1)^k steps with the list encoded in binary on its tape. For its list, the Lean library bounds the dimension by 256(n+s+1)10256(n+s+1)^{10} and the length of the encoding by a fixed constant times (n+s+1)104(n+s+1)^{104}. 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 nn and ss one tuple of rational matrices at which every nonzero division-free formula in nn variables with at most ss gates evaluates to a nonzero matrix, is formalized in another Lean library, which these pages do not present.

The Lean library: RationalHitting

RationalHitting is a Lean library: 22 items, in six groups. Each has a page written by OctoInform, listed below.

§1. Introduction 3 items
  1. §1 (setting): rational formulas, size, evaluation, admissible and nonzero Rational formulas and their values at tuples of matrices. §1
  2. Theorem 1.1 [Polynomial hitting lists for rational formulas] Noncommutative rational formulas have polynomial-time hitting lists. §1
  3. §1.2 (setting): affine linear pencils and feasibility Matrix evaluations of affine pencils are Kronecker sums. §1.2
§2. Rectangular tests from subspace expansion 8 items
  1. §2 (setting): the parameters (2.1) and the tests Tᵢ, Rᵢ(t) (2.2), (2.3) Parameters and reversed Taylor tests of the hitting list. §2
  2. Proposition 2.1 [Rectangular rank bound] Injective evaluations make rectangular tests injective in low degree. §2
  3. §2 (displayed): the vanishing filtration (2.5) Bounded-degree polynomial spaces have bases of distinct vanishing orders. §2
  4. Lemma 2.2 [Wronskian order bound] The root multiplicities of a polynomial space are bounded. §2
  5. §2 (setting): the reduction of a Laurent-series subspace The reduction modulo tt of a subspace over K((t))K((t)). §2
  6. Lemma 2.3 [Integral bases of Laurent-series subspaces] Laurent-series subspaces have integral frames. §2
  7. Lemma 2.4 [Small-subspace expansion] Small subspaces expand under reverse Taylor tests. §2
  8. §2 (proof of Proposition 2.1): the shrunk-subspace obstruction (2.10) An invertible pencil makes an expanding test injective. §2
§3. Deformation inside a division algebra 4 items
  1. Lemma 3.1 [A matrix lift into a division algebra] Lifting matrices into a division ring, and a rank gap. §3
  2. Proposition 3.2 [Full-rank deformed pencils] Lifting the tests keeps a pencil nonsingular. §3
  3. §3 (displayed): left normalization (3.5) Left normalization turns a homogeneous pencil into an affine one. §3
  4. Lemma 3.3 [An invertible witness for a nonzero formula] A nonzero formula takes an invertible value over Hahn series. §3
§4. Encoding a formula and its evaluation domain 3 items
  1. Lemma 4.1 [Affine realization of a subtree] Every rational formula is realized by an affine pencil. §4
  2. §4 (setting): the root augmentation (4.4) The root augmentation detects whether a formula’s value is invertible. §4
  3. Proposition 4.2 [Pencil certificates for the original formula tree] Inverse-gate pencils certify where a formula is defined. §4
§5. A rational hitting list and its bit complexity 3 items
  1. §5 (setting): the parameters (5.1), the rational representation and the generator The rational hitting list and its cyclotomic generator. §5
  2. Proposition 5.1 [The hitting property] A rational hitting list for formulas of bounded size. §5
  3. Proposition 5.3 [Bit complexity and output length] One Turing machine writes the hitting list in polynomial time. §5
The second preprint: One Rational Matrix Hitting Point for Noncommutative Formulas 1 item
  1. Lemma 4.1 [Wronskian], One Rational Matrix Hitting Point Distinct vanishing orders fix the Wronskian’s order in characteristic zero. §4 of the second preprint

No item matches.