Toric Certificates for Effective Skolem Tails and Subspace Orbit Reachability

1 Introduction

Let \(K\) be a number field. A scalar linear recurrence sequence over \(K\) is a sequence \(u=(u_n)_{n\ge0}\) satisfying

for some \(a_0,\ldots,a_{d-1}\in K\). The Skolem Problem asks whether there exists \(n\ge0\) such that

The strong computational form asks to compute the entire zero set

The Skolem--Mahler--Lech theorem asserts that \(Z(u)\) is a finite union of arithmetic progressions together with a finite exceptional set. Its known proofs do not provide a general algorithm for computing the finite exceptional set. The computational heart of Skolem is therefore the construction of an effective zero-free tail.

This paper studies such tails through toric certificates. The scalar case is included, but the natural level of generality is vectorial. Let

be a vector of algebraic linear recurrence sequences. The simultaneous zero set is

This formulation covers the Simultaneous Skolem Problem. It also covers affine subspace orbit reachability: if \(A\in K^{d\times d}\), \(x_0\in K^d\), and

then

The central idea is to separate the dominant vector from zero. On each branch, after standard spectral reductions, we obtain

where \(z(k)\) is a toric orbit on a compact toric coset, \(\mathbf D\) is the normalized dominant vector, and \(\mathbf E\) is exponentially smaller. If one can certify that

outside a computable prefix, then the exponentially small error cannot cancel the dominant vector outside that prefix. The rest is an exact finite computation.

The vector viewpoint is essential. A scalar coordinate may contain a factor such as

which is outside the automatic one-character Baker class. But a system such as

has no common zero on \(\T^2\), and the norm of the vector is bounded away from zero by a semialgebraic certificate. Thus the vector method proves effective tails in cases not visible to scalar coordinatewise methods.

The contributions are:

1. a global vector dominant-shell normal form with torsion saturation;

2. a verifier theorem for toric lower-bound certificates;

3. joint semialgebraic and Positivstellensatz/SOS certificates;

4. Bezout--toric certificates converting scalar lower bounds into vector lower bounds;

5. a scalar Baker--Matveev lemma for expressions \(F(k,\delta^k)\);

6. quotient-character reduction, producing scalar atoms automatically from Laurent factors whose exponent supports become one-dimensional modulo the toric relation lattice;

7. binomial-stratified certificates combining semialgebraic Lojasiewicz bounds, Baker separation from exact binomial hits, and recursive restriction;

8. automatic extraction of binomial strata from dominant elimination ideals in the binomial subclass;

9. a partial Factor--Reduce--Certify compiler and an automatic binomial-stratified certificate-tree compiler;

10. applications to Simultaneous Skolem, Subspace Orbit, affine linear-loop reachability, algebraic target hitting, and eventual cone membership.

The framework isolates certified toric dominant shells: once a dominant lower-bound mechanism is verified, the zero-free tail and the exact finite prefix become effective. Non-binomial toric approximation remains the boundary where additional Diophantine lower bounds would be needed.

2 Effective input and certificate model

An input consists of:

1. a number field \(K\), represented effectively;

2. either a scalar or vector linear recurrence sequence over \(K\), or a linear dynamical system \((A,x_0,B,b)\);

3. a complex embedding \(\sigma:K\hookrightarrow \C\).

All computations take place in finite extensions of \(K\). We use standard exact algorithms in number fields: arithmetic, factorization, construction of splitting fields, root-of-unity testing, exact zero testing, comparison of algebraic absolute values under \(\sigma\), and computation of multiplicative relation lattices [12]. These algorithms are not claimed to be efficient in general; they are used as exact symbolic subroutines.

A certificate is extended input. The algorithms in this paper are sound: if the certificate verifies, then the output zero set is correct. They are not complete: failure to certify means ``not certified'', not ``no zero'' and not ``undecidable''.

We separate three layers.

• The verifier theorem: a valid certificate implies an effective zero-free tail.

• Automatic certificate generation: for certain structural classes, the certificate is constructed by the compiler.

• Positive search: for some certificates, such as Bezout--toric identities of bounded degree, one may search positively, but failure of the search has no mathematical consequence.

3 Vector Binet form and global shells

Let

be a vector of algebraic linear recurrence sequences. Passing to a common splitting field \(L/K\), we may write

where \(\mathcal R\subset L^\times\) is finite and

Zero characteristic roots contribute only to a finite initial segment. That segment is checked exactly, and the sequence is shifted. Hence all roots in the remaining Binet representation are nonzero.

Fix an embedding

A global vector shell is a set

The shell contribution is

The shell is vectorially cancelled if

as a vector-valued exponential-polynomial function. This means every coordinate is identically zero.

After torsion splitting, distinct bases with no root-of-unity quotient give linearly independent exponential-polynomial functions. Therefore vectorial cancellation is decidable exactly.

4 Torsion splitting and torsion saturation

If \(\lambda/\mu\) is a root of unity, let \(o(\lambda,\mu)\) be its order. Let

For each residue class \(r\pmod{M_0}\), define

Equal bases in the resulting Binet representation are combined exactly.

A second torsion issue remains. A shell with relative multiplicative rank \(\rho\) modulo torsion need not be an exact toric coset. Its roots have the form

where \(\xi_\lambda\) is a root of unity and

Let

Passing to subbranches

makes

constant. The polynomial coefficients are transformed by

and the bases by

All new data are computable. We call this step torsion saturation.

5 Vector toric normal form

After torsion splitting and torsion saturation, peel globally cancelled shells until the first non-cancelled global shell is reached. Let \(S\) be that shell. Choose \(\Lambda\in S\). The roots in \(S\) can be written as

Since all roots in \(S\) have the same \(\sigma\)-absolute value, the toric parameters satisfy

Define

Then the contribution of \(S\) has the form

where

All lower shells have strictly smaller \(\sigma\)-absolute value. Hence the branch has normal form

with

Here

6 Toric cosets

After reindexing, it is convenient to write

with

Define the exact relation lattice

where

This lattice is computable.

Let

The orbit closure of \(z(k)=c\eta^k\) is the compact toric coset

Equivalently,

We do not assume \(T_\eta\) is connected. If finite torsion remains in \(\eta\), \(T_\eta\) may have finitely many components. The equations above describe the full compact coset.

For effective real-algebraic verification, write

The torus is defined by

and the coset equations are the real and imaginary parts of

for a basis of \(\mathcal L_\eta\).

7 The certified-tail theorem

Theorem 7.1 (Certified-tail soundness).

Let a saturated branch have vector toric normal form

\[ \mathbf v_k=\Lambda^k\bigl(\mathbf D(k,z(k))+\mathbf E(k)\bigr), \]

where

\[ |\mathbf E(k)|\le C_E(k+1)^s\theta^k, \qquad 0<\theta<1. \]

Assume there are computable constants \(A,C,N_0\) such that, for every \(k\ge N_0\),

\[ \mathbf D(k,z(k))\ne0 \quad\Longrightarrow\quad |\mathbf D(k,z(k))| \ge \exp(-C(\log(k+2))^A). \]

Assume also that exact zeros of

\[ \mathbf D(k,z(k)) \]

are either contained in a computable prefix or occur only on subbranches where the global dominant vector is identically cancelled and hence peeled.

Then the branch has a computable zero-free tail. Consequently the zeros on the branch are computable exactly as a finite set plus any identically zero subprogressions.

8 Joint semialgebraic certificates

Definition 8.1 (Joint semialgebraic certificate).

Let

\[ \mathbf D(T,X)=(D_1(T,X),\ldots,D_m(T,X)). \]

A joint semialgebraic certificate, or joint S-certificate, on a toric coset \(C=cT_\eta\) consists of explicit data

\[ B_0\in\mathbb N,\qquad L_0\in\mathbb N,\qquad q\in\Q_{>0} \]

such that

\[ \sum_{i=1}^m|\sigma(D_i(t,x))|^2 \ge q(t+1)^{-L_0} \]

for every

\[ t\ge B_0, \qquad x\in C. \]

The assertion is a universal formula over a real closed field. Laurent monomials are represented on the torus by

The coset \(C\) is represented by polynomial equations

and the real and imaginary parts of

for a basis of \(\mathcal L_\eta\).

The certificate condition becomes

This formula is effectively decidable by quantifier elimination over real closed fields.

Proposition 8.2.

A joint S-certificate implies the hypothesis of the certified-tail theorem with a polynomial lower bound:

\[ |\mathbf D(k,z(k))|\ge q^{1/2}(k+1)^{-L_0/2}. \]

9 Binomial-stratified certificates

Uniform separation on the whole compact toric coset is a useful certificate, but many natural dominant vectors vanish on structured subtori. The certificate can still be effective when the entire dominant zero locus is forced into finitely many binomial strata.

Definition 9.1 (Binomial stratum).

Let \(C\subseteq\T^\rho\) be an effective compact toric coset. A binomial stratum in \(C\) is a subset

\[ H= \{x\in C: \chi_{a_1}(x)=\zeta_1,\ldots,\chi_{a_\ell}(x)=\zeta_\ell\}, \]

where

\[ a_j\in\Z^\rho, \qquad \chi_{a_j}(X)=X^{a_j}, \]

and each \(\zeta_j\) is algebraic of complex absolute value \(1\). The stratum is proper if \(H\ne C\).

For such a stratum set

Then

For a finite family

define

Thus

Definition 9.2 (Binomial stratification certificate).

Let

\[ \mathbf D(T,X)\in L[T][X_1^{\pm1},\ldots,X_\rho^{\pm1}]^m \]

be a dominant vector on \(C\). A binomial stratification certificate consists of

\[ B\in\mathbb N \]

and a finite family \(\mathcal H\) of proper effective binomial strata in \(C\) such that

\[ \mathbf D(t,x)=0 \quad\Longrightarrow\quad x\in\bigcup_{H\in\mathcal H}H \]

for all real \(t\ge B\) and all \(x\in C\).

Once the candidate strata are supplied, the implication is a universal formula over a real closed field after writing the torus and the coset in real coordinates. Hence it is effectively checkable by quantifier elimination.

Lemma 9.3 (Effective semialgebraic Lojasiewicz inequality).

Let \(K_0\) be a compact effective semialgebraic set, and let

\[ f,g:K_0\to\R_{\ge0} \]

be effective continuous semialgebraic functions. If

\[ Z(f)\subseteq Z(g), \]

then there exist effectively searchable constants

\[ N\in\mathbb N, \qquad c>0, \]

with \(c\) algebraic, such that

\[ f(y)\ge c\,g(y)^N \]

for every \(y\in K_0\).

Theorem 9.4 (Stratified semialgebraic lower bound).

Assume that \(\mathbf D\) admits a binomial stratification certificate \((B,\mathcal H)\) on \(C\). Put

\[ P(t,x)=\sum_{i=1}^m |D_i(t,x)|^2, \qquad \Delta(x)=\Delta_{\mathcal H}(x). \]

Then there exist effectively computable constants

\[ B'\in\mathbb N, \qquad q>0, \qquad L_0\in\mathbb N, \qquad R\in\mathbb N \]

such that

\[ P(t,x)\ge q(t+1)^{-L_0}\Delta(x)^R \]

for every \(t\ge B'\) and every \(x\in C\).

10 SOS and Positivstellensatz certificates

Quantifier elimination proves decidability, but one may also use algebraic certificates that are easier to verify.

Let \(C\) be represented by equalities

and inequalities

These include the torus equations, the coset equations, and the tail condition \(t-B_0\ge0\). A Positivstellensatz/SOS certificate for the joint lower bound consists of an identity

where the \(\sigma_j\) are sums of squares and the \(h_\ell\) are arbitrary polynomials, all with algebraic coefficients.

Such an identity is checked by exact polynomial arithmetic and by verifying the supplied sum-of-squares decompositions. When present, it gives a joint S-certificate.

This SOS formulation is not required for decidability, but it gives a more explicit certificate format than quantifier elimination.

11 Automatic joint certificates from leading vectors

Write

with \(\mathbf D_d\ne0\).

Proposition 11.1 (Leading-vector criterion).

If

\[ \mathbf D_d(x)\ne0 \qquad\text{for every }x\in C, \]

then a joint S-certificate exists and can be effectively found.

12 Scalar character-polynomial atoms

A scalar atom is an expression

where

and

is a toric character. Along the branch

we have

Absorbing the constant \(\chi(c)\) into \(F\), one reduces to

13 The Baker--Matveev lemma

We use the following standard consequence of effective lower bounds for linear forms in logarithms.

Lemma 13.1 (Scalar character lower bound).

Let

\[ F(T,Y)\in L[T,Y]\setminus\{0\}, \]

let

\[ \delta\in L^\times, \qquad |\sigma(\delta)|=1, \]

and suppose \(\delta\) is not a root of unity. Then there exist computable constants

\[ C>0, \qquad N_0\in\mathbb N \]

such that, for every \(k\ge N_0\),

\[ F(k,\delta^k)\ne0 \quad\Longrightarrow\quad |\sigma(F(k,\delta^k))| \ge \exp(-C(\log(k+2))^2). \]

Moreover, exact zeros of \(F(k,\delta^k)\) are contained in a computable finite prefix.

14 Baker separation from binomial strata

The preceding scalar lemma controls one-character atoms. Binomial strata reduce to finitely many such one-character conditions along the toric orbit.

Lemma 14.1 (One-character separation).

Let

\[ \alpha,\zeta\in\overline{\Q}^{\times}, \qquad |\sigma(\alpha)|=|\sigma(\zeta)|=1. \]

Then the solution set

\[ S(\alpha,\zeta)=\{k\ge0:\alpha^k=\zeta\} \]

is effectively computable as a finite union of arithmetic progressions and a finite set. Moreover, there exist effective constants

\[ c>0, \qquad A\in\mathbb N, \]

such that

\[ |\sigma(\alpha^k-\zeta)|\ge c(k+1)^{-A} \]

for every \(k\notin S(\alpha,\zeta)\).

Lemma 14.2 (Separation from one binomial stratum).

Let \(z(k)=c\eta^k\in C\), and let

\[ H= \{x\in C:\chi_{a_1}(x)=\zeta_1,\ldots,\chi_{a_\ell}(x)=\zeta_\ell\} \]

be an effective binomial stratum. Set

\[ S_H=\{k\ge0:z(k)\in H\}. \]

Then \(S_H\) is effectively computable as a finite union of arithmetic progressions and a finite set. Moreover, there exist effective constants

\[ c_H>0, \qquad A_H\in\mathbb N, \]

such that

\[ \Delta_H(z(k))\ge c_H(k+1)^{-A_H} \]

for every \(k\notin S_H\).

Lemma 14.3 (Separation from a finite family of binomial strata).

Let \(\mathcal H=\{H_1,\ldots,H_N\}\) be a finite family of effective binomial strata and set

\[ S_{\mathcal H}=\bigcup_{\nu=1}^N S_{H_\nu}. \]

Then \(S_{\mathcal H}\) is effectively computable as a finite union of arithmetic progressions and a finite set. Moreover, there exist effective constants

\[ c>0, \qquad A\in\mathbb N, \]

such that

\[ \Delta_{\mathcal H}(z(k))\ge c(k+1)^{-A} \]

for every \(k\notin S_{\mathcal H}\).

Theorem 14.4 (Stratified zero-free tail outside exact hits).

Let a saturated branch have normal form

\[ \mathbf v_k=\Lambda^k(\mathbf D(k,z(k))+\mathbf E(k)), \qquad z(k)=c\eta^k, \]

with

\[ |\mathbf E(k)|\le C_E(k+1)^s\theta^k, \qquad 0<\theta<1. \]

Assume that \(\mathbf D\) admits a binomial stratification certificate \(\mathcal H\) on \(C\), and let

\[ S_{\mathcal H}=\{k\ge0:z(k)\in\bigcup_{H\in\mathcal H}H\}. \]

Then there is an effectively computable \(B\) such that

\[ \mathbf v_k\ne0 \]

for every \(k\ge B\) with \(k\notin S_{\mathcal H}\).

15 Torsion scalar atoms

If \(\delta\) is a root of unity of order \(Q\), pass to subbranches

Then

where \(G_s\in L[h]\).

If \(G_s\not\equiv0\), its integer zeros are finite and computable, and Liouville gives a polynomial lower bound for nonzero values.

If \(G_s\equiv0\), the scalar atom vanishes identically on that subbranch. In a scalar product certificate this may force the dominant scalar to vanish. In a vector or Bezout certificate it means only that the particular scalar test has failed. The algorithm either peels the branch if the full dominant vector is identically zero, or requires a new certificate on that subbranch.

Termination follows because every peeling removes one global shell and all splitting operations are finite.

16 Bezout--toric certificates

Let

Let

be a basis of \(\mathcal L_\eta\), and define the coset binomials

Then

Definition 16.1 (Bezout--toric certificate).

A Bezout--toric certificate consists of Laurent polynomials

\[ A_i(T,X),\quad B_j(T,X),\quad M(T,X) \]

such that

\[ M(T,X)=\sum_{i=1}^m A_i(T,X)D_i(T,X)+\sum_{j=1}^\ell B_j(T,X)G_j(X), \]

together with a scalar certificate for \(M(k,z(k))\) giving

\[ |M(k,z(k))|\ge \exp(-C(\log(k+2))^A) \]

outside a computable prefix.

The identity is verified exactly in the Laurent polynomial ring.

Lemma 16.2.

There exist computable constants \(C_A,R\) such that

\[ \left(\sum_i|A_i(k,z(k))|^2\right)^{1/2} \le C_A(k+1)^R. \]

Proposition 16.3.

A Bezout--toric certificate implies the lower-bound hypothesis of the certified-tail theorem.

One may search for Bezout--toric certificates by fixing degree bounds for the unknown \(A_i,B_j,M\), imposing the identity as a finite linear system over \(L\), and checking whether \(M\) admits a scalar S/B/T certificate. If the search succeeds, the certificate is valid. If it fails at a chosen bound, no conclusion follows. Thus this is a positive semidecision procedure, not a complete algorithm.

17 Quotient-character reduction

Let

be a Laurent factor. Consider the image of \(A\) in

We say that \(H\) has quotient affine rank at most one if the differences

span a vector space of dimension at most one in

Proposition 17.1.

If \(H\) has quotient affine rank at most one, then after finite torsion splitting,

\[ H(k,z(k))=\alpha_0^k F(k,\delta^k) \]

for some algebraic \(\alpha_0,\delta\) of \(\sigma\)-absolute value \(1\) and some

\[ F(T,Y)\in L[T,Y]. \]

Corollary 17.2.

A quotient-affine-rank-one factor is automatically converted into a scalar Baker or torsion atom.

18 Automatic binomial extraction

The binomial-stratified theorem is a verifier: it proves a tail once the strata are known. In an important subclass the strata can be extracted from the dominant equations.

18.1 Dominant elimination ideals

Let \(C\subseteq\T^\rho\) be the compact toric coset attached to a branch, and let

be its Laurent ideal, generated by the binomials

For

define

and

The variety \(V(J_D)\cap C\) contains every point \(x\in C\) for which there exists a complex value \(T=t\) with

It is therefore an algebraic over-approximation of the eventual real projection

The over-approximation is useful: if it is already covered by proper binomial strata, then it gives a valid certificate without guessing the strata.

Definition 18.1 (Automatically binomial branch).

A dominant branch is automatically binomial if the computed set

\[ V(J_D)\cap C \]

is effectively verified to be contained in a finite union of proper binomial strata

\[ H_1\cup\cdots\cup H_N \]

inside \(C\). In the strict binomial case, these strata are obtained from binomial radical and decomposition algorithms [11], followed by lattice basis reduction and Smith normal form.

Theorem 18.2 (Automatic binomial certificate extraction).

Let a nonzero dominant branch be automatically binomial. Then one can effectively compute a finite family of proper binomial strata

\[ \mathcal H=\{H_1,\ldots,H_N\} \]

such that

\[ \mathbf D(t,x)=0 \quad\Longrightarrow\quad x\in\bigcup_{\nu=1}^N H_\nu \]

for every \(t\) and every \(x\in C\). Hence the branch admits a binomial stratification certificate with \(B=0\).

19 Binomial-stratified certificate trees

Exact hits of binomial strata are not exceptional failures. They are arithmetic progressions on which the recurrence can be restricted and renormalized.

Definition 19.1 (Binomial-stratified toric certificate tree).

A binomial-stratified toric certificate tree for a vector recurrence is a finite rooted tree whose nodes carry restricted branches

\[ \mathbf v_k=\mathbf u_{ak+b} \]

with saturated dominant normal forms

\[ \mathbf v_k=\Lambda^k(\mathbf D(k,z(k))+\mathbf E(k)). \]

A terminal node is one of the following:

1. an identically zero branch;

2. a branch with a joint S-certificate, an SOS/Positivstellensatz certificate, a Bezout--toric certificate, or scalar atoms proving a dominant lower bound;

3. a closure-avoiding branch for which the leading-vector or semialgebraic compactness test gives a lower bound.

A nonterminal node carries a binomial stratification certificate \(\mathcal H\). Its children are the infinite arithmetic progressions contained in

\[ S_{\mathcal H}= \{k\ge0:z(k)\in\bigcup_{H\in\mathcal H}H\}. \]

On each child, the recurrence is restricted to that progression and the dominant normal form is recomputed. Along every edge, either a dominant spectral shell is peeled or the dimension of the compact toric orbit closure strictly decreases.

Definition 19.2 (Automatic binomial-stratified tree).

A binomial-stratified toric certificate tree is automatic if every nonterminal node obtains its binomial stratification certificate from automatic binomial extraction.

Theorem 19.3 (Exact zero set from a certificate tree).

If a vector recurrence admits a finite binomial-stratified toric certificate tree, then its zero set is computable exactly as a finite union of arithmetic progressions and a finite set. If the tree is automatic, the binomial strata at all nonterminal nodes are computed from the dominant branch equations.

20 The Factor--Reduce--Certify compiler

The partial compiler operates branchwise.

1. Compute the vector toric normal form.

2. Compute the toric coset \(C=cT_\eta\).

3. Attempt the leading-vector criterion.

4. If it fails, attempt to construct a Bezout--toric certificate by bounded-degree linear algebra.

5. For scalar factors or scalar tests, factor in the Laurent polynomial ring.

6. For each irreducible factor, compute its quotient affine rank modulo \(\mathcal L_\eta\).

7. If the rank is at most one, reduce it to a scalar atom.

8. Verify remaining S-certificates by quantifier elimination, SOS identities, or Positivstellensatz identities.

9. If the branch is not terminally certified, attempt automatic binomial extraction from \(J_D\).

10. If binomial extraction succeeds, compute the exact-hit progressions, restrict to the infinite progressions, and recompute the dominant normal form on each child.

11. Accept the recursive step only when it peels a dominant shell or strictly lowers the toric dimension.

12. If every terminal branch is certified and every recursive branch belongs to a finite certificate tree, compute the zero-free tails and exact prefixes.

13. If some branch is not certified, return ``not certified''.

Theorem 20.1 (Compiler soundness).

If Factor--Reduce--Certify succeeds on all branches of a vector recurrence \(\mathbf u\), then it computes

\[ Z(\mathbf u)=\{n\ge0:\mathbf u_n=0\} \]

exactly as a finite union of arithmetic progressions and a finite set.

21 Certified and automatic binomial-stratified classes

Definition 21.1.

A vector recurrence belongs to the certified binomial-stratified toric class if its dominant branch decomposition admits a finite binomial-stratified toric certificate tree.

It belongs to the automatic binomial-stratified toric class if it admits such a tree and every nonterminal stratum is produced by automatic binomial extraction.

Corollary 21.2 (Certified binomial-stratified Skolem).

For every algebraic vector recurrence \(\mathbf u\) in the certified binomial-stratified toric class, the set

\[ Z(\mathbf u)=\{n\ge0:\mathbf u_n=0\} \]

is computable exactly.

Corollary 21.3 (Automatic binomial-stratified Skolem).

For every algebraic vector recurrence \(\mathbf u\) in the automatic binomial-stratified toric class, the zero set \(Z(\mathbf u)\) is computable exactly. In this class the binomial strata required at nonterminal nodes are computed from the dominant elimination ideals.

Remark 21.4.

The restriction is geometric rather than dimensional. There is no a priori bound here on recurrence order, root multiplicity, number of dominant roots, toric rank, vector dimension, ambient matrix dimension, or target dimension. The required structure is that the dominant toric zero loci are either terminally separated from zero or recursively controlled by binomial strata.

22 Applications

Theorem 22.1 (Simultaneous Skolem).

Let

\[ u^{(1)},\ldots,u^{(m)} \]

be algebraic linear recurrence sequences and set

\[ \mathbf u_n=(u^{(1)}_n,\ldots,u^{(m)}_n). \]

If Factor--Reduce--Certify succeeds on \(\mathbf u\), then

\[ \{n\ge0:u^{(1)}_n=\cdots=u^{(m)}_n=0\} \]

is computable exactly.

This is stronger than separately solving the scalar Skolem instances and intersecting their zero sets, because a joint vector certificate may exist even when a scalar coordinate is outside the automatic scalar certificate class.

Theorem 22.2 (Subspace Orbit and affine linear loops).

Let

\[ A\in K^{d\times d}, \qquad x_0\in K^d, \]

and let

\[ V=\{y\in K^d:By=b\} \]

be an affine subspace. Define

\[ \mathbf u_n=BA^nx_0-b. \]

If Factor--Reduce--Certify succeeds on \(\mathbf u_n=BA^nx_0-b\), then the hitting-time set

\[ \{n\ge0:A^nx_0\in V\} \]

is computable exactly.

Corollary 22.3 (Binomial-stratified Subspace Orbit).

With notation as above, suppose

\[ \mathbf u_n=BA^nx_0-b \]

belongs to the certified binomial-stratified toric class. Then

\[ \Hit(A,x_0,V)=\{n\ge0:A^nx_0\in V\} \]

is computable exactly. If \(\mathbf u_n\) belongs to the automatic binomial-stratified toric class, the required binomial strata are computed from the dominant branch equations.

This gives a certified reachability theorem for affine linear loops

with target condition \(Bx=b\).

Corollary 22.4 (Algebraic target hitting).

Let

\[ W=\{y:P_1(y)=\cdots=P_m(y)=0\} \]

be an affine algebraic set over \(K\). Since coordinates of \(A^nx_0\) are linear recurrence sequences and such sequences are closed under addition and pointwise multiplication, each sequence

\[ P_i(A^nx_0) \]

is a linear recurrence sequence. If Factor--Reduce--Certify succeeds on

\[ \bigl(P_1(A^nx_0),\ldots,P_m(A^nx_0)\bigr), \]

then

\[ \{n\ge0:A^nx_0\in W\} \]

is computable exactly.

23 Eventual cone membership and ultimate positivity

Let \(C\subseteq\R^m\) be a semialgebraic cone or a closed semialgebraic set. Suppose a real vector recurrence has normal form

with \(\Lambda>0\), and suppose a certificate proves that \(\mathbf D(k,z(k))\) has distance at least

from the boundary of \(C\) for \(k\ge B\), with a fixed side of the boundary. Then \(\mathbf u_k\in C\) eventually if and only if the dominant vector lies on that side. The finite prefix is checked exactly.

For \(m=1\) and \(C=[0,\infty)\), this gives certified ultimate positivity.

24 A high-rank vector family

Let \(\rho\ge2\), and let

satisfy

and be multiplicatively independent modulo torsion.

Define

Proposition 24.1.

The vector \(\mathbf D_\rho\) has no zero on \(\T^\rho\).

Therefore

has a strictly positive minimum on \(\T^\rho\), and a joint S-certificate can be verified.

Let

where

Then Factor--Reduce--Certify succeeds and computes the simultaneous zero set.

The scalar coordinate

has exponent support of affine rank \(\rho\), so it is not an automatic quotient-character scalar factor. The vector system is nevertheless certified by joint separation. This demonstrates the genuine advantage of the vector method.

25 Realization as Subspace Orbit

Let

Then

Let \(V_\rho\subseteq K^\rho\) be the affine subspace defined by

and

Then

By the preceding proposition, the pure dominant model has no hitting time. With exponentially smaller subdominant perturbations, the subspace-orbit certificate theorem gives a computable zero-free tail and exact prefix check.

This gives a high-rank family of certified Subspace Orbit instances in which one scalar equation contains high-rank toric support, but the vector system is jointly separated.

26 Relation to previous work

The Skolem Problem is open in general. The Skolem--Mahler--Lech theorem gives the eventual structure of the zero set but is not a general algorithm for computing the finite exceptional set.

Low-order and few-dominant-root results decide important special cases. The present framework is different: it is not based on low order or few dominant roots, but on a verifiable toric separation certificate.

Modern algorithms for broader recurrence classes often produce correct certificates when they terminate, with termination proved under strong Diophantine conjectures. The present method is unconditional inside the certified class.

The Evertse--Schlickewei--Schmidt theory gives explicit upper bounds for the number of nondegenerate solutions of linear equations in variables from a finite-rank multiplicative group [10]. Such results are close in spirit, but a bound on the number of solutions does not by itself give a computable bound on the positions of the indices \(n\). The present method produces an explicit zero-free tail once a certificate is verified.

Bacik and Varonka study Subspace Orbit and Simultaneous Skolem from a dimension-theoretic perspective [5]. Their results are orthogonal to the present work. They prove decidability in certain target-dimension regimes and hardness in others. The present framework imposes no a priori target-dimension threshold; it requires a toric separation certificate for the dominant vector.

The vector feature is essential. The family above shows that scalar coordinatewise certification can fail while joint vector certification succeeds.

27 Boundary of the certified class

The certified class is governed by the available lower-bound mechanisms. Joint semialgebraic certificates handle dominant vectors that avoid zero on the compact toric closure. Binomial-stratified certificates handle dominant zero loci contained in finitely many character strata, because exact character hits are computable and Baker separation gives polynomial distance from the strata away from those hits.

A scalar expression such as

on a genuinely rank-two orbit is different. Its zero locus is not a finite union of binomial strata. Along

one would need effective lower bounds for

outside exact zeros. Such non-binomial toric approximation is not supplied by the binomial-stratified layer.

Thus the compiler is sound and incomplete: success produces a verified exact zero set, while failure means that the available certificate mechanisms did not certify the instance.

28 Conclusion

We have developed a certificate framework for effective zero-free tails in scalar and vector linear recurrence sequences. The main novelty is the vector toric viewpoint: for Simultaneous Skolem and Subspace Orbit, it is enough to separate the dominant vector from zero. This can succeed even when scalar coordinatewise methods fail.

The framework includes:

1. global vector dominant-shell normal form;

2. torsion saturation and toric coset closures;

3. certified-tail soundness;

4. joint semialgebraic and SOS certificates;

5. Bezout--toric certificates;

6. scalar Baker character-polynomial atoms;

7. quotient-character reduction;

8. binomial-stratified lower bounds;

9. Baker separation from exact binomial hits;

10. automatic binomial extraction from dominant elimination ideals;

11. finite certificate trees;

12. a partial Factor--Reduce--Certify compiler with a recursive binomial-stratified mode;

13. applications to Simultaneous Skolem, Subspace Orbit, linear-loop reachability, algebraic target hitting, and ultimate positivity;

14. a high-rank vector family showing genuine advantage over scalar methods.

The resulting framework gives a rigorous, checkable, and partially automatic mechanism for proving effective Skolem tails in high-rank, high-order families. Its strongest automatic layer is the binomial-stratified class: semialgebraic Lojasiewicz inequalities control vanishing near the strata, Baker separation controls the actual toric orbit away from exact hits, and recursive restriction handles the exact-hit progressions.