OAI.NCHitting.universal_hitting

The theorem states that, for natural numbers n,s ≥ 1 and any field F of characteristic zero, every noncommutative arithmetic formula f over F in n variables x₀,…,xₙ₋₁ (built from scalars of F, single variables, binary addition and binary multiplication, with size counting each scalar or variable leaf as 1 and each addition or multiplication node as the sizes of its two parts plus 1) satisfies the following. If f.size ≤ s and f is not the zero series, meaning its noncommutative coefficient series has some nonzero coefficient on a word w in the variables, then evaluating f at an explicit tuple of rational matrices gives a nonzero matrix. Here scalars a of F are sent to the scalar matrix a times the identity of size D, where D = dimension(n,s) equals 1 if n = s = 1 and 2ns² otherwise, and the variable xᵢ is sent to the D×D matrix generator(i), viewed over F via the rational cast. For n = s = 1 this matrix is the 1×1 matrix with entry 1. Otherwise its entry in row r and column q (indexed from zero) is (−1)^(r−q−1) / (r·(i+1)^(r−q)) when q < r, and 0 when q ≥ r. The coefficient series of a formula is defined by letting scalars give a constant series, a variable give the indicator of its one-letter word, addition add series termwise, and multiplication give the noncommutative convolution (Cauchy product over word concatenation).