OctoInform Beta

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

§5 (setting): the parameters (5.1), the rational representation and the generator: Tuples (Z0−1Zi)i=1n(Z_0^{-1}Z_i)_{i=1}^{n} at the points of {1,…,H}3\{1,\dots,H\}^3 where Z0Z_0 is invertible, each ZiZ_i a cyclotomic lift made rational by ρM\rho_M

The rational hitting list and its cyclotomic generator.

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 a number nn of variables and a size bound ss. Write Matd(ℚ)\mathrm{Mat}_d(\mathbb{Q}) for the ring of rational d×dd\times d matrices, with rows and columns indexed by 0,…,d−10,\dots,d-1.✦ A point (X1,…,Xn)(X_1,\dots,X_n) of Matd(ℚ)n\mathrm{Mat}_d(\mathbb{Q})^n with d>0d>0 hits a noncommutative rational formula, built from x1,…,xnx_1,\dots,x_n and rational constants by addition, multiplication and inversion, when the value of the formula at that point is defined and invertible. A hitting list for a class of nonzero formulas is a positive integer dd with a finite list of points of Matd(ℚ)n\mathrm{Mat}_d(\mathbb{Q})^n that contains, for every formula of the class, a point hitting it.

A matrix of polynomials is lifted to three parameters over the MM-th cyclotomic field, for a power of two MM fixed by nn and ss, and at each integer point of a cube the lift becomes a tuple of rational matrices through the regular representation of the field.

The Cyclotomic Field

Let ee be a natural number, let ℓ=2e\ell = 2^e(1)✦ be the degree, and let M=2e+1=2ℓM = 2^{e+1} = 2\ell✦. The modulus is the polynomial xℓ+1x^\ell+1 of ℚ[x]\mathbb{Q}[x]✦, the MM-th cyclotomic polynomial: xℓ+1=ΦM(x).x^{\ell}+1 = \Phi_M(x).(2)✦

The cyclotomic field ℛ=ℚ[x]/(xℓ+1)\mathcal{R} = \mathbb{Q}[x]/(x^\ell+1) is the quotient of ℚ[x]\mathbb{Q}[x] by the ideal generated by the modulus.✦ The class ξ\xi of xx is a primitive MM-th root of unity, and ℛ\mathcal{R} has over ℚ\mathbb{Q} the power basis 1,ξ,…,ξℓ−11,\xi,\dots,\xi^{\ell-1}, indexed by 0,…,ℓ−10,\dots,\ell-1: ℛ=⨁k=0ℓ−1ℚξk.\mathcal{R} = \bigoplus_{k=0}^{\ell-1} \mathbb{Q}\,\xi^k.(3)✦

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 this basis: yξk′=∑k=0ℓ−1ρ(y)kk′ξk(y∈ℛ,0≤k′<ℓ).y\,\xi^{k'} = \sum_{k=0}^{\ell-1} \rho(y)_{kk'}\,\xi^k \qquad (y\in\mathcal{R},\ 0\le k'<\ell).(4)✦

The additive character χ\chi of ℤ/Mℤ\mathbb{Z}/M\mathbb{Z} with values in ℛ\mathcal{R} is built on ξ\xi✦, and it is primitive: χ(k)=ξk,χ(a⋅)≠1(a∈ℤ/Mℤ,a≠0).\chi(k) = \xi^k, \qquad \chi(a\,\cdot\,) \ne 1 \quad (a\in\mathbb{Z}/M\mathbb{Z},\ a\ne 0).(5)✦

Write MatM(ℛ)\mathrm{Mat}_M(\mathcal{R}) for the ring of M×MM\times M matrices over ℛ\mathcal{R}, with rows and columns indexed by ℤ/Mℤ\mathbb{Z}/M\mathbb{Z}, read as 0,…,M−10,\dots,M-1. With the block dimension D=Mℓ=22e+1,D = M\ell = 2^{2e+1},(6)✦ the regular representation extends entrywise to the ring homomorphism ρM:MatM(ℛ)→MatD(ℚ)\rho_M\colon \mathrm{Mat}_M(\mathcal{R})\to\mathrm{Mat}_D(\mathbb{Q}) that sends a matrix A=(Auv)A=(A_{uv}) of MatM(ℛ)\mathrm{Mat}_M(\mathcal{R}) to the matrix placing the block ρ(Auv)\rho(A_{uv}) in block row uu and block column vv: ρM(A)uℓ+k,vℓ+k′=ρ(Auv)kk′(0≤u,v<M,0≤k,k′<ℓ).\rho_M(A)_{u\ell+k,\; v\ell+k'} = \rho(A_{uv})_{kk'} \qquad (0\le u,v<M,\ 0\le k,k'<\ell).(7)✦

The Parameters

The list depends on nn and ss through the width ww, the bound BB, the gap Δ\Delta, the exponent ee and the truncation NN, w=n+1,B=2s+1,Δ=2w3B,e=⌊log⁡2(BΔ)⌋,N=M−Δ,w = n+1,\quad B = 2s+1,\quad \Delta = 2w^3B,\quad e = \lfloor \log_2(B\Delta)\rfloor,\quad N = M-\Delta,(8) where M=2e+1M = 2^{e+1} is then the least power of two greater than BΔB\Delta✦, and through the grid size H=1+3(s+2)BM3.H = 1 + 3(s+2)BM^3.(9)✦

The Lift

Let KK be a field, χ\chi an additive character of ℤ/Mℤ\mathbb{Z}/M\mathbb{Z} with values in KK, and NN a natural number, and write [xu]f[x^u]f for the coefficient of xux^u in a polynomial ff. The Taylor test matrix of order MM at a point α∈K\alpha\in K is the M×MM\times M matrix over K[t]K[t] whose column vv takes the Taylor coefficients of xvx^v at α\alpha, multiplies the one of order kk by tkt^k and makes it the coefficient of (x−α)M−1−k(x-\alpha)^{M-1-k}.✦ The padded Taylor test matrix Rα(t)R_\alpha(t) has entries Rα(t)uv={∑k=0M−1tk[xu](x−α)M−1−k[xk](x+α)v,v<N,0,v≥N.R_\alpha(t)_{uv} = \begin{cases} \sum_{k=0}^{M-1} t^k\,[x^u](x-\alpha)^{M-1-k}\,[x^k](x+\alpha)^v, & v<N,\\ 0, & v\ge N. \end{cases}(10)✦ For i=0,…,ni=0,\dots,n, Ri(t)R_i(t) is the padded Taylor test matrix Rα(t)R_\alpha(t) at the point α=i\alpha=i.

The Weyl monomial DaSbD^aS^b, for a,b∈ℤ/Mℤa,b\in\mathbb{Z}/M\mathbb{Z}, is the product of the clock matrix Da=diag(χ(au))uD^a = \mathrm{diag}(\chi(au))_u and the power SbS^b of the cyclic shift.✦ The Fourier coefficients of an M×MM\times M matrix R(t)R(t) over K[t]K[t] along these monomials are the polynomials cab(t)c_{ab}(t): (DaSb)uv={χ(au),u=v+b,0,otherwise,cab(t)=1M∑j∈ℤ/Mℤχ(−aj)R(t)j,j−b.(D^aS^b)_{uv} = \begin{cases} \chi(au), & u = v+b,\\ 0, & \text{otherwise}, \end{cases} \qquad c_{ab}(t) = \frac{1}{M}\sum_{j\in\mathbb{Z}/M\mathbb{Z}} \chi(-aj)\,R(t)_{j,\,j-b}.(11)✦

The three-parameter lift R*R^* of R(t)R(t) is the M×MM\times M matrix over K[t,p,r]K[t,p,r] with R*(t,p,r)uv=∑a,b∈ℤ/Mℤcab(t)(DaSb)uvparb,R^*(t,p,r)_{uv} = \sum_{a,b\in\mathbb{Z}/M\mathbb{Z}} c_{ab}(t)\,(D^aS^b)_{uv}\,p^a r^b,(12)✦ the exponents aa and bb read in 0,…,M−10,\dots,M-1. The pencil lifts are the lifts (12) of the padded test matrices (10) at the points 0,…,n0,\dots,n: R̃i=Ri*(i=0,…,n).\tilde R_i = R_i^* \qquad (i=0,\dots,n).(13)✦

The Claim

Definition 1. Let nn, NN, ee and HH be natural numbers, with ℛ\mathcal{R}, ℓ\ell, MM, DD and ρM\rho_M those of ee, and let R̃0,…,R̃n\tilde R_0,\dots,\tilde R_n be the pencil lifts (13) over K=ℛK=\mathcal{R}, with the character χ\chi of (5) and the truncation NN. At a point (t0,p0,r0)(t_0,p_0,r_0) of ℕ3\mathbb{N}^3 and for i=0,…,ni=0,\dots,n, the cyclotomic lift matrix and the regular matrix are Z̃i(t0,p0,r0)=R̃i(t0,p0,r0)∈MatM(ℛ),\tilde Z_i(t_0,p_0,r_0) = \tilde R_i(t_0,p_0,r_0) \in \mathrm{Mat}_M(\mathcal{R}),(14)✦ Zi(t0,p0,r0)=ρM(Z̃i(t0,p0,r0))∈MatD(ℚ).Z_i(t_0,p_0,r_0) = \rho_M\bigl(\tilde Z_i(t_0,p_0,r_0)\bigr) \in \mathrm{Mat}_D(\mathbb{Q}).(15)✦ When Z0Z_0 is invertible, writing ZiZ_i for Zi(t0,p0,r0)Z_i(t_0,p_0,r_0), the tuple at the point is τ(t0,p0,r0)=(Z0−1Z1,…,Z0−1Zn)∈MatD(ℚ)n,\tau(t_0,p_0,r_0) = \bigl(Z_0^{-1}Z_1,\dots,Z_0^{-1}Z_n\bigr) \in \mathrm{Mat}_D(\mathbb{Q})^n,(16)✦ and the point yields ϕ(t0,p0,r0)={no tuple,det⁡Z0=0,τ(t0,p0,r0),det⁡Z0≠0.\phi(t_0,p_0,r_0) = \begin{cases} \text{no tuple}, & \det Z_0 = 0,\\ \tau(t_0,p_0,r_0), & \det Z_0 \ne 0. \end{cases}(17)✦ The grid of side HH is the list of the triples of natural numbers below HH in lexicographic order, GH=((0,0,0),(0,0,1),…,(0,0,H−1),(0,1,0),…,(H−1,H−1,H−1)),G_H = \bigl((0,0,0),(0,0,1),\dots,(0,0,H-1),(0,1,0),\dots,(H-1,H-1,H-1)\bigr),(18)✦ and the generator output 𝒢n(N,e,H)\mathcal{G}_n(N,e,H) is the list, of common dimension DD, of the tuples yielded in this order at the points of {1,…,H}3\{1,\dots,H\}^3, a point that yields no tuple contributing nothing: 𝒢n(N,e,H)=[ϕ(t0+1,p0+1,r0+1):(t0,p0,r0)∈GH].\mathcal{G}_n(N,e,H) = \bigl[\,\phi(t_0+1,\,p_0+1,\,r_0+1) : (t_0,p_0,r_0)\in G_H\,\bigr].(19)✦ For natural numbers nn and ss, the rational hitting list is the output at the parameters (8) and (9): ℒn,s=𝒢n(N,e,H).\mathcal{L}_{n,s} = \mathcal{G}_n(N,e,H).(20)✦

In the paper, the result reads: with ℓ=M/2\ell = M/2, D=MℓD = M\ell, H=1+3(s+2)BM3H = 1+3(s+2)BM^3 and ℛ=ℚ[ξ]/(ξℓ+1)\mathcal{R} = \mathbb{Q}[\xi]/(\xi^\ell+1), where ρ(a)∈Matℓ(ℚ)\rho(a)\in\mathrm{Mat}_\ell(\mathbb{Q}) is multiplication by aa in the power basis and ρd\rho_d applies ρ\rho entrywise, the lift R̃i(t,p,r)\tilde R_i(t,p,r) of Ri(t)R_i(t) is formed over ℛ\mathcal{R}, and for each (t0,p0,r0)∈{1,…,H}3(t_0,p_0,r_0)\in\{1,\dots,H\}^3 the generator computes Zi=ρM(R̃i(t0,p0,r0))∈MatD(ℚ)Z_i = \rho_M(\tilde R_i(t_0,p_0,r_0))\in\mathrm{Mat}_D(\mathbb{Q}), emits nothing if Z0Z_0 is singular, and otherwise emits (Z0−1Z1,…,Z0−1Zn)(Z_0^{-1}Z_1,\dots,Z_0^{-1}Z_n).

What Is Checked

The generator (19) and the list (20) are stated over the cyclotomic field ℛ\mathcal{R} with its power basis, the regular representation ρ\rho and its extension ρM\rho_M, the character χ\chi, the pencil lifts R̃i\tilde R_i of the padded Taylor test matrices, and the parameters (8) and (9).

Of these constructions the library proves that the modulus xℓ+1x^\ell+1 is monic✦ of degree ℓ\ell✦ and equal to ΦM\Phi_M, as in (2)✦, and that χ\chi is primitive, as in (5)✦.