OctoInform Beta

OpenAI preprint, September 2026 · §5. A rational hitting list and its bit complexity · §5

Proposition 5.3 [Bit complexity and output length]: A stack program compiled to a Turing machine writes ℋn,s\mathcal{H}_{n,s} from 1n01s1^n01^s in polynomial time, and the list’s encoding has polynomial length

One Turing machine writes the hitting list in polynomial time.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Fix n,s≥1n, s \ge 1. The hitting list ℋn,s\mathcal{H}_{n,s} for noncommutative rational formulas of size at most ss in nn variables is a finite list of tuples of square rational matrices, all of one size, given by an explicit construction over a cyclotomic field. Proposition 5.3 measures the cost of writing it down. The input is nn and ss in unary, as the word 1n01s1^n01^s, and the output is every entry of every matrix of the list, in binary: how many steps does one Turing machine need, and how long is what it writes?

Formulas and Hitting Lists

A rational formula ff in nn variables is a finite tree built from the variables x1,…,xnx_1, \dots, x_n and rational constants by addition, multiplication in a fixed order and inversion✦; its size |f||f| is its number of vertices.✦

Let RR be a ring with a ring homomorphism ℚ→R\mathbb{Q} \to R, and let X∈RnX \in R^n. The evaluation of rational formulas at XX is the least relation between formulas and elements of RR in which xix_i has the value XiX_i, a constant has its image in RR, f+gf+g and fgfg have the values a+ba+b and abab when ff and gg have the values aa and bb, and f−1f^{-1} has the value bb when ff has a value aa with ab=ba=1ab = ba = 1.✦

At a tuple X∈Matd(ℚ)nX \in \mathrm{Mat}_d(\mathbb{Q})^n of d×dd \times d rational matrices, evaluation takes place in the ring Matd(ℚ)\mathrm{Mat}_d(\mathbb{Q}), a constant qq being the scalar matrix qIdqI_d.✦ A rational formula ff in nn variables is admissible if it has a value at some tuple in Matd(ℚ)n\mathrm{Mat}_d(\mathbb{Q})^n with d≥1d \ge 1✦, and nonzero if it has a nonzero value at some such tuple.✦

A list of tuples ℒ\mathcal{L} in nn variables consists of a positive integer dim⁡ℒ\dim\mathcal{L}, its dimension, and a finite sequence of tuples in Matdim⁡ℒ(ℚ)n\mathrm{Mat}_{\dim\mathcal{L}}(\mathbb{Q})^n; its length |ℒ||\mathcal{L}| is the number of these tuples.✦ A list of tuples ℒ\mathcal{L} in nn variables is a hitting list for size ss if every admissible nonzero rational formula ff in nn variables with |f|≤s|f| \le s has a value that is an invertible matrix at some tuple of ℒ\mathcal{L}.✦

The Hitting List

The construction uses the parameters w=n+1,B=2s+1,Δ=2w3B,e=⌊log⁡2(BΔ)⌋,M=2e+1,ℓ=2e,N=M−Δ,D=Mℓ,H=1+3(s+2)BM3,\begin{gathered} w = n+1, \qquad B = 2s+1, \qquad \Delta = 2w^3B, \qquad e = \lfloor \log_2(B\Delta) \rfloor,\\ M = 2^{e+1}, \qquad \ell = 2^e, \qquad N = M - \Delta, \qquad D = M\ell, \qquad H = 1 + 3(s+2)BM^3, \end{gathered}(1) Here NN is the truncation and HH the grid size.

The cyclotomic field ℛ\mathcal{R} is the quotient ℚ[ξ]/(ξℓ+1)\mathbb{Q}[\xi]/(\xi^\ell+1) of ℚ[ξ]\mathbb{Q}[\xi] by the monic polynomial ξℓ+1\xi^\ell+1 of degree ℓ\ell✦; in it ξ\xi is a primitive MM-th root of unity, and 1,ξ,…,ξℓ−11, \xi, \dots, \xi^{\ell-1} is its power basis over ℚ\mathbb{Q}.✦ The regular representation ρ:ℛ→Matℓ(ℚ)\rho\colon \mathcal{R} \to \mathrm{Mat}_\ell(\mathbb{Q}) is the ℚ\mathbb{Q}-algebra homomorphism sending yy to the matrix of multiplication by yy in the power basis.✦

For an M×MM \times M matrix YY over ℛ\mathcal{R} with rows and columns indexed by ℤ/M\mathbb{Z}/M, the matrix ρM(Y)∈MatD(ℚ)\rho_M(Y) \in \mathrm{Mat}_D(\mathbb{Q}) has in row μℓ+α\mu\ell + \alpha and column νℓ+β\nu\ell + \beta the entry (α,β)(\alpha, \beta) of ρ(Yμν)\rho(Y_{\mu\nu}), with μ\mu and ν\nu read in {0,…,M−1}\{0, \dots, M-1\}.✦ The signed entries εc(α,β)\varepsilon_c(\alpha, \beta), for c∈ℤ/Mc \in \mathbb{Z}/M read in {0,…,M−1}\{0, \dots, M-1\} and 0≤α,β<ℓ0 \le \alpha, \beta < \ell, are the integers εc(α,β)={(−1)⌊(c+β)/ℓ⌋if c+β≡α(mod⁡ℓ),0otherwise,\varepsilon_c(\alpha, \beta) = \begin{cases} (-1)^{\lfloor (c+\beta)/\ell \rfloor} & \text{if } c + \beta \equiv \alpha \pmod{\ell},\\ 0 & \text{otherwise,} \end{cases}(2)✦ the entries of ρ(ξc)\rho(\xi^c).

For a point λ\lambda of a field KK, the padded test matrix Rλ(t)R_\lambda(t) of order MM at λ\lambda is the M×MM \times M matrix over K[t]K[t], with rows and columns indexed by ℤ/M\mathbb{Z}/M and read in {0,…,M−1}\{0, \dots, M-1\}, whose first NN columns are given below and whose other columns are zero; its entry in row α\alpha and column β\beta is, binomial coefficients out of range being zero, Rλ(t)αβ={∑γ=0M−1(M−1−γα)(−λ)M−1−γ−α(βγ)λβ−γtγif β<N,0if β≥N.R_\lambda(t)_{\alpha\beta} = \begin{cases} \displaystyle\sum_{\gamma=0}^{M-1} \binom{M-1-\gamma}{\alpha}(-\lambda)^{M-1-\gamma-\alpha} \binom{\beta}{\gamma}\lambda^{\beta-\gamma}\, t^\gamma & \text{if } \beta < N,\\[1ex] 0 & \text{if } \beta \ge N. \end{cases}(3) The test matrices are Ri(t)R_i(t), at the points i=0,…,ni = 0, \dots, n, and at integers λ\lambda and tt the same formula defines integer matrices Rλ(t)∈MatM(ℤ)R_\lambda(t) \in \mathrm{Mat}_M(\mathbb{Z}).

Let χ\chi be an additive character of ℤ/M\mathbb{Z}/M with values in a field KK. The Weyl monomial DaSbD^aS^b, for a,b∈ℤ/Ma, b \in \mathbb{Z}/M, is the M×MM \times M matrix over KK with entry χ(aα)\chi(a\alpha) in row α\alpha and column β\beta when α=β+b\alpha = \beta + b, and 00 otherwise.✦ The three-parameter lift of an M×MM \times M matrix R(t)R(t) over K[t]K[t], indexed by ℤ/M\mathbb{Z}/M, is the matrix over K[t,p,r]K[t, p, r] R*(t,p,r)=∑a,b∈ℤ/Mcab(t)parbDaSb,cab(t)=1M∑j∈ℤ/Mχ(−aj)R(t)j,j−b,R^*(t, p, r) = \sum_{a, b \in \mathbb{Z}/M} c_{ab}(t)\, p^a r^b\, D^aS^b, \qquad c_{ab}(t) = \frac{1}{M} \sum_{j \in \mathbb{Z}/M} \chi(-aj)\, R(t)_{j,\, j-b},(4)✦ with exponents the least nonnegative representatives of aa and bb; the cab(t)c_{ab}(t) are its Fourier coefficient polynomials.

The pencil lifts R0*,…,Rn*R_0^*, \dots, R_n^* are the lifts of the test matrices R0(t),…,Rn(t)R_0(t), \dots, R_n(t) over ℛ\mathcal{R} along the character χ(k)=ξk\chi(k) = \xi^k of ℤ/M\mathbb{Z}/M.✦ At a point x=(x0,x1,x2)∈ℕ3x = (x_0, x_1, x_2) \in \mathbb{N}^3 the regular matrices are Zi(x)=ρM(Ri*(x0,x1,x2))∈MatD(ℚ),i=0,…,n.Z_i(x) = \rho_M\bigl(R_i^*(x_0, x_1, x_2)\bigr) \in \mathrm{Mat}_D(\mathbb{Q}), \qquad i = 0, \dots, n.(5)✦ The list ℋn,s\mathcal{H}_{n,s} is the list of tuples of dimension DD whose tuples are (Z0(x)−1Z1(x),…,Z0(x)−1Zn(x)),x∈{1,…,H}3,det⁡Z0(x)≠0,\bigl(Z_0(x)^{-1}Z_1(x), \dots, Z_0(x)^{-1}Z_n(x)\bigr), \qquad x \in \{1, \dots, H\}^3,\ \det Z_0(x) \ne 0,(6) taken in the lexicographic order of xx.

Exact Arithmetic

For x∈ℕ3x \in \mathbb{N}^3 and i=0,…,ni = 0, \dots, n, the integer matrix Ui(x)∈MatD(ℤ)U_i(x) \in \mathrm{Mat}_D(\mathbb{Z}) has in row μℓ+α\mu\ell + \alpha and column νℓ+β\nu\ell + \beta, for μ,ν∈ℤ/M\mu, \nu \in \mathbb{Z}/M and 0≤α,β<ℓ0 \le \alpha, \beta < \ell, the integral lift entry ∑a,j∈ℤ/MRi(x0)j,j−bεa(μ−j)(α,β)x1ax2b,b=μ−ν,\sum_{a, j \in \mathbb{Z}/M} R_i(x_0)_{j,\, j-b}\; \varepsilon_{a(\mu - j)}(\alpha, \beta)\; x_1^a x_2^b, \qquad b = \mu - \nu,(7)✦ where Ri(x0)R_i(x_0) is the integer padded test matrix at the point ii with t=x0t = x_0, and the exponents are least nonnegative representatives.

The division-free determinant det⁡′A\operatorname{det}'A of an integer matrix AA of order mm is 11 if m=0m = 0 and otherwise (−1)m−1(-1)^{m-1} times the top-left entry of stage m−1m-1 of AA✦, where stage 00 is AA and each further stage comes from the one before by an elimination step relative to AA that uses only additions, subtractions and multiplications of integers.✦

Write A[α←A*β′]A[\alpha \leftarrow A'_{*\beta}] for the matrix AA with its column α\alpha replaced by column β\beta of A′A'. The executable list ℋn,s′\mathcal{H}'_{n,s} is the list of tuples of dimension DD that has, for each x∈{1,…,H}3x \in \{1, \dots, H\}^3 in lexicographic order with δ(x)=det⁡′U0(x)≠0\delta(x) = \operatorname{det}'U_0(x) \ne 0, the tuple whose ii-th matrix, for i=1,…,ni = 1, \dots, n, has in row α\alpha and column β\beta the Cramer quotient det′(U0(x)[α←Ui(x)*β])δ(x).\frac{\operatorname{det}'\bigl(U_0(x)[\alpha \leftarrow U_i(x)_{*\beta}]\bigr)}{\delta(x)}.(8)

Binary Encoding

For a bit word yy, |y||y| is its length and yRy^R its reversal. A natural number mm with binary digits m0,…,mL−1m_0, \dots, m_{L-1}, least significant first, is encoded as ⟨m⟩=1L0m0⋯mL−1\langle m \rangle = 1^L\,0\,m_0 \cdots m_{L-1}, and ⟨0⟩=0\langle 0 \rangle = 0.✦ A rational number a/ba/b in lowest terms with b>0b > 0 is encoded as ⟨a/b⟩=σ⟨|a|⟩⟨b⟩\langle a/b \rangle = \sigma\,\langle |a| \rangle\,\langle b \rangle, with the sign bit σ\sigma equal to 11 exactly when a<0a < 0✦, and a tuple of matrices as the concatenation of the encodings of its entries, matrix by matrix and row by row.✦ A list of tuples ℒ\mathcal{L} with tuples X(1),…,X(|ℒ|)X^{(1)}, \dots, X^{(|\mathcal{L}|)} is encoded as ⟨ℒ⟩=⟨dim⁡ℒ⟩⟨|ℒ|⟩⟨X(1)⟩⋯⟨X(|ℒ|)⟩.\langle \mathcal{L} \rangle = \langle \dim\mathcal{L} \rangle\, \langle |\mathcal{L}| \rangle\, \langle X^{(1)} \rangle \cdots \langle X^{(|\mathcal{L}|)} \rangle.(9)✦

The output constant coutc_{\mathrm{out}}, the constant in the bound on the length of ⟨ℋn,s⟩\langle \mathcal{H}_{n,s} \rangle in the claim below, is the positive integer cout=(2⋅256+3)+(2⋅245773+3)+245773⋅2562⋅cbit,c_{\mathrm{out}} = (2 \cdot 256 + 3) + (2 \cdot 24577^3 + 3) + 24577^3 \cdot 256^2 \cdot c_{\mathrm{bit}},(10)✦ where clog=64+64+3⋅16⋅24577=1179824c_{\log} = 64 + 64 + 3 \cdot 16 \cdot 24577 = 1179824 is the log constant✦ and cbit=4(2562+256clog+1)+3c_{\mathrm{bit}} = 4(256^2 + 256\,c_{\log} + 1) + 3 the bit constant.✦

Programs and Machines

A stack program over a set of registers, each register holding a stack of bits, is built from the instructions that do nothing, push a bit onto a register, pop the top bit of a register and move the top bit of one register onto another, the last two doing nothing on an empty register, by sequencing, by a branch that runs one of three programs depending on whether a register is empty or has top bit 00 or 11, and by a loop that runs a program while a register is nonempty.✦ The running time of a run of a program, from one assignment of stacks to the registers to another, is the number τ\tau of steps: one for an instruction, one more than the runs it is made of for a sequence, a branch or a pass of a loop, and one for a loop that finds its register empty.✦

A register holds a bit word yy when yy reads from the top of its stack down. For a program PP with an input register and an output register, P(v)→τyP(v) \to_\tau y means that PP, run from the input register holding vv and every other register empty, ends after τ\tau steps with the output register holding yy and every other register empty.

Let 𝒳\mathcal{X} and 𝒴\mathcal{Y} be sets, and let κ\kappa and κ′\kappa' be bit encodings of them, that is, maps from 𝒳\mathcal{X} and 𝒴\mathcal{Y} to bit words. A map f:𝒳→𝒴f\colon \mathcal{X} \to \mathcal{Y} is feasible if it has a stack procedure✦: a stack program PP over finitely many registers, with an input and an output register, and a polynomial QQ with natural coefficients such that every a∈𝒳a \in \mathcal{X} has P(κ(a))→τκ′(f(a))P(\kappa(a)) \to_\tau \kappa'(f(a)) for some τ≤Q(|κ(a)|+1)\tau \le Q(|\kappa(a)| + 1) and |κ′(f(a))|≤Q(|κ(a)|+1)|\kappa'(f(a))| \le Q(|\kappa(a)| + 1).✦

A Turing machine is deterministic, with finitely many states and one tape over the alphabet {0,1,2,3}\{0, 1, 2, 3\}, in which 00 is the blank, the digit symbols 11 and 22 stand for the bits 00 and 11, and 33 is work space; given the state and the scanned symbol, its transition function either halts or gives a new state with a head move or a symbol to write.✦ A configuration is a state, a tape and the head position✦, and time is the number of transitions. For bit words vv and yy, G(v)⊢uyG(v) \vdash_u y means that the machine GG, started in its initial configuration on vv written in the digit symbols, makes uu transitions and reaches a configuration with no transition, whose tape holds yy in the digit symbols from the head rightwards, followed by blanks.

The Claim

Theorem 1. For all natural numbers nn and ss, dim⁡ℋn,s≤256(n+s+1)10,\dim\mathcal{H}_{n,s} \le 256\,(n+s+1)^{10},(11)✦ and for n≥1n \ge 1 and every ss, |ℋn,s|≤245773(n+s+1)51,|\mathcal{H}_{n,s}| \le 24577^3\,(n+s+1)^{51},(12)✦ |⟨ℋn,s⟩|≤cout(n+s+1)104.|\langle \mathcal{H}_{n,s} \rangle| \le c_{\mathrm{out}}\,(n+s+1)^{104}.(13)✦ For all nn and ss, ℋn,s′=ℋn,s,\mathcal{H}'_{n,s} = \mathcal{H}_{n,s},(14)✦ and for n,s≥1n, s \ge 1, dim⁡ℋn,s′≤256(n+s+1)10,|⟨ℋn,s′⟩|≤cout(n+s+1)104,ℋn,s′ is a hitting list for size s.\dim\mathcal{H}'_{n,s} \le 256\,(n+s+1)^{10}, \quad |\langle \mathcal{H}'_{n,s} \rangle| \le c_{\mathrm{out}}\,(n+s+1)^{104}, \quad \mathcal{H}'_{n,s} \text{ is a hitting list for size } s.(15)✦ The map sending (n,s)(n, s), encoded as 1n01s1^n01^s, to the bit word ⟨ℋn,s′⟩R\langle \mathcal{H}'_{n,s} \rangle^R is feasible, with a stack program PP and a polynomial QQ for which, for all nn and ss, P(1n01s)→τ⟨ℋn,s′⟩R for some τ≤Q(n+s+2),|⟨ℋn,s′⟩|≤Q(n+s+2).P(1^n01^s) \to_\tau \langle \mathcal{H}'_{n,s} \rangle^R \text{ for some } \tau \le Q(n+s+2), \qquad |\langle \mathcal{H}'_{n,s} \rangle| \le Q(n+s+2).(16)✦ There are a stack program PP over finitely many registers and positive integers CC and kk such that, for all n,s≥1n, s \ge 1, P(1n01s)→τ⟨ℋn,s′⟩R for some τ≤C(n+s+1)k.P(1^n01^s) \to_\tau \langle \mathcal{H}'_{n,s} \rangle^R \text{ for some } \tau \le C\,(n+s+1)^k.(17)✦ For every stack program PP over finitely many registers, with an input and an output register, there are a Turing machine GG and a positive integer CC such that, whenever P(v)→τyRP(v) \to_\tau y^R for a nonempty bit word vv, a bit word yy and a number τ\tau, G(v)⊢uy for some u≤C(|v|+τ+|y|+3)2,G(v) \vdash_u y \text{ for some } u \le C\,(|v| + \tau + |y| + 3)^2,(18)✦ with only blanks to the left of the head at the end. There are a Turing machine GG and positive integers CC and kk such that, for all n,s≥1n, s \ge 1, G(1n01s)⊢u⟨ℋn,s′⟩ for some u≤C(n+s+1)k,G(1^n01^s) \vdash_u \langle \mathcal{H}'_{n,s} \rangle \text{ for some } u \le C\,(n+s+1)^k,(19)✦ and for every stack program PP over finitely many registers and all positive integers CC and kk satisfying (17), there are a Turing machine GG and positive integers C′C' and k′k' such that, for all n,s≥1n, s \ge 1, G(1n01s)⊢u⟨ℋn,s′⟩ for some u≤C′(n+s+1)k′.G(1^n01^s) \vdash_u \langle \mathcal{H}'_{n,s} \rangle \text{ for some } u \le C'\,(n+s+1)^{k'}.(20)✦

In the paper, the result reads: the list ℋn,s\mathcal{H}_{n,s} can be constructed and written by one deterministic Turing machine in a number of bit operations bounded by a fixed polynomial in n+s+1n+s+1, and its entire binary encoding has length bounded by a fixed polynomial in the same quantity.

What Is Checked

The claim is stated over rational formulas and their evaluation at rational matrices, with admissible and nonzero formulas and hitting lists; the lists ℋn,s\mathcal{H}_{n,s} and ℋn,s′\mathcal{H}'_{n,s} built from the parameters (1); the encoding (9) and the constant coutc_{\mathrm{out}}; stack programs with their running time and feasible maps; and Turing machines over {0,1,2,3}\{0, 1, 2, 3\} timed by their transitions.

For all nn and ss, M≤16(n+s+1)5,M \le 16\,(n+s+1)^5,(21)✦ and for n≥1n \ge 1 and every ss, H≤24577(n+s+1)17.H \le 24577\,(n+s+1)^{17}.(22)✦ For every x∈ℕ3x \in \mathbb{N}^3 and i=0,…,ni = 0, \dots, n, Ui(x)=MZi(x),U_i(x) = M\,Z_i(x),(23)✦ and if every coordinate of xx is at most an integer h≥1h \ge 1, every entry zz of Ui(x)U_i(x) satisfies |z|≤M4(2w)2Mh3M.|z| \le M^4\,(2w)^{2M}\,h^{3M}.(24)✦ If det⁡Z0(x)≠0\det Z_0(x) \ne 0, then for i=1,…,ni = 1, \dots, n, Z0(x)−1Zi(x)=U0(x)−1Ui(x).Z_0(x)^{-1}Z_i(x) = U_0(x)^{-1}U_i(x).(25)✦ For integer matrices AA and A′A' of order dd with det⁡A≠0\det A \ne 0, Cramer’s rule reads (A−1A′)αβ=det⁡(A[α←A*β′])det⁡A,(A^{-1}A')_{\alpha\beta} = \frac{\det\bigl(A[\alpha \leftarrow A'_{*\beta}]\bigr)}{\det A},(26)✦ and for every integer square matrix AA, det′A=det⁡A.\operatorname{det}'A = \det A.(27)✦