Degree conjecture for general rank sequences

Hilbert-polynomial proof of the degree conjecture for general rank sequences

In Complexity of powers of a constant-recursive sequence, Eric Rowland and Jesús Sistos Barrón formulate Conjecture 6.2 for a recurrence whose characteristic roots are distinct and have no multiplicity. They predict that its general rank sequence is eventually polynomial of degree one less than the free rank of its group of homogeneous root relations. We prove this assertion, including torsion in the relation quotient, and then give the sharp extension that explains exactly what changes when characteristic roots are repeated.

Let the distinct characteristic roots be

$$\rho_1,\ldots,\rho_k\in\mathbb C^{\times}. \tag{1}$$

These roots are nonzero because the source assumes that the constant coefficient of the minimal recurrence is nonzero. The relevant relation lattice consists only of relations between products containing the same total number of roots:

$$N= \left\{a\in\mathbb Z^k: \sum_{i=1}^ka_i=0, \quad \prod_{i=1}^k\rho_i^{a_i}=1 \right\}. \tag{2}$$

Put

$$G=\mathbb Z^k/N, \qquad d=\operatorname{rank}_{\mathbb Z}(G), \qquad g_i=e_i+N\in G. \tag{3}$$

Because every element of $N$ has coordinate sum zero, the total-degree homomorphism descends to

$$\deg:G\longrightarrow\mathbb Z, \qquad \deg(g_i)=1. \tag{4}$$

In particular, $d\geq1$. The homogeneity requirement in (2) is essential: root products from different powers must not be identified.

Suppose first that every characteristic root is simple. Introduce algebraically independent nonzero coefficients $u_1,\ldots,u_k$ over a characteristic-zero field containing the roots, and write the general exponential expression as

$$s(n)=\sum_{i=1}^ku_i\rho_i^n. \tag{5}$$

Any finite initial segment preceding the eventual recurrence does not affect its rank. The multinomial expansion of the $M$th power is

$$s(n)^M= \sum_{\substack{a\in\mathbb N^k\\|a|=M}} \binom{M}{a_1,\ldots,a_k} u_1^{a_1}\cdots u_k^{a_k} \left(\prod_{i=1}^k\rho_i^{a_i}\right)^n. \tag{6}$$

For vectors $a,b\in\mathbb N^k$ with $|a|=|b|=M$, their exponential roots coincide exactly when

$$\prod_{i=1}^k\rho_i^{a_i} =\prod_{i=1}^k\rho_i^{b_i} \quad\Longleftrightarrow\quad a-b\in N \quad\Longleftrightarrow\quad \sum_{i=1}^ka_ig_i=\sum_{i=1}^kb_ig_i. \tag{7}$$

For each such equivalence class, the coefficient in (6) is a sum of distinct monomials in the algebraically independent $u_i$, with positive multinomial coefficients. It cannot vanish. Thus the source's general, no-cancellation rank is exactly

$$R(M)= \left| \left\{ \sum_{i=1}^ka_ig_i: a\in\mathbb N^k,\quad |a|=M \right\} \right|. \tag{8}$$

Indeed, distinct nonzero exponential roots are linearly independent, so the minimal characteristic polynomial of (6) has exactly one simple factor for each class in (8).

Let

$$S=\mathbb Ng_1+\cdots+\mathbb Ng_k\subseteq G, \qquad A=\mathbb C[S]. \tag{9}$$

The semigroup algebra has one formal basis element $X^g$ for each $g\in S$, with multiplication $X^gX^h=X^{g+h}$. By (4), it is a finitely generated standard graded algebra, generated by the degree-one elements $X^{g_i}$. Its degree-$M$ component therefore satisfies

$$\dim_{\mathbb C}A_M=R(M). \tag{10}$$

We next compute its dimension without assuming that $G$ is torsion-free. Write

$$G\cong\mathbb Z^d\oplus T, \qquad h=|T|, \tag{11}$$

where $T$ is finite and $h=1$ when $T$ is trivial. Consider the subalgebra

$$B=\mathbb C[hS] =\mathbb C[X^{hg_1},\ldots,X^{hg_k}] \subseteq A. \tag{12}$$

Every generator $X^{g_i}$ of $A$ is integral over $B$, since

$$(X^{g_i})^h-X^{hg_i}=0. \tag{13}$$

Consequently, $A$ is a finite integral extension of $B$ and

$$\dim A=\dim B. \tag{14}$$

The group generated by $hS$ is $hG\cong\mathbb Z^d$. Hence $B$ is an affine domain whose monomial localization is the Laurent polynomial algebra of this free group:

$$\mathbb C[hG] \cong\mathbb C[z_1^{\pm1},\ldots,z_d^{\pm1}]. \tag{15}$$

Therefore the fraction field of $B$ has transcendence degree $d$. The dimension theorem for finitely generated domains now gives

$$\dim A=\dim B=d. \tag{16}$$

Hilbert's theorem for standard graded algebras states that the Hilbert function of a nonzero algebra of dimension $d$ agrees, for all sufficiently large $M$, with a polynomial of degree exactly $d-1$. Applying this to (10) and (16) proves

$$\boxed{\displaystyle R(M)=P(M)\quad(M\gg0), \qquad \deg P=d-1.} \tag{17}$$

This is precisely Conjecture 6.2 for all distinct simple characteristic roots, all homogeneous relation lattices, and arbitrary torsion in $G$.

Sharp repeated-root extension. The source explicitly notes that its symbolic lattice does not record multiplicities. Suppose more generally that $\rho_i$ has multiplicity $m_i\geq1$, and put

$$w_i=m_i-1. \tag{18}$$

The corresponding term in the general exponential expression is $P_i(n)\rho_i^n$, where $\deg P_i=w_i$. For algebraically independent polynomial coefficients, the degree of the coefficient belonging to a product class $g$ in the $M$th power is exactly

$$W_M(g)= \max\left\{ \sum_{i=1}^ka_iw_i: a\in\mathbb N^k, \quad |a|=M, \quad\sum_{i=1}^ka_ig_i=g \right\}. \tag{19}$$

There is no cancellation of the top-degree coefficient because the contributions from distinct exponent vectors contain distinct monomials in the independent leading coefficients. Since a polynomial coefficient of degree $W$ gives a characteristic root of multiplicity $W+1$, the general rank becomes

$$R_{\boldsymbol m}(M) =\sum_{\substack{g\in S\\deg(g)=M}} \bigl(W_M(g)+1\bigr). \tag{20}$$

Introduce the standard graded semigroup

$$S^{\sharp} =\left\langle (g_i,j):1\leq i\leq k,\quad 0\leq j\leq w_i \right\rangle \subseteq G\oplus\mathbb Z, \qquad \deg(g_i,j)=1. \tag{21}$$

For a fixed exponent vector $a$, sums of the allowed second coordinates attain every integer from $0$ through $\sum_i a_iw_i$. Taking the union over all vectors representing $g$ gives precisely $0,1,\ldots,W_M(g)$. Therefore

$$R_{\boldsymbol m}(M) =\dim_{\mathbb C}\mathbb C[S^{\sharp}]_M. \tag{22}$$

If all $w_i=0$, the generated group is $G\oplus\{0\}$. If some $w_i>0$, then both $(g_i,0)$ and $(g_i,1)$ are generators, so their difference supplies $(0,1)$ and the generated group is all of $G\oplus\mathbb Z$. The same finite-integral-extension argument consequently yields the exact corrected degree law

$$\boxed{\displaystyle \deg P_{\boldsymbol m}= \begin{cases} d-1,&m_1=\cdots=m_k=1,\\ d,&\text{at least one }m_i>1. \end{cases}} \tag{23}$$

This also explains the source's Example 4.4: for characteristic polynomial $(x-1)^3(x-2)$, one has $N=0$, $d=2$, and

$$R_{(3,1)}(M) =\sum_{b=0}^M\bigl(2(M-b)+1\bigr) =(M+1)^2. \tag{24}$$

Its degree is $2=d$, not $d-1$, because the simple-root hypothesis does not hold. The repeated-root extension also proves the general-sequence half of Conjecture 5.3, but only under the source's general, no-cancellation convention. Its separate assertion about particular sequences with exceptional coefficient cancellations remains unresolved.