D.9 Recurrence packets and a common integral spine
On this page · Permalink · Source line 2773
Linear recurrences provide a setting where residue subsequences, local completions, and a common global source can all be described exactly. Background on recurrence sequences may be found in [EverestVanDerPoortenShparlinskiWard2003], [Stanley2012].
D.9.1 Companion jumps
On this page · Permalink · Source line 2777
Let \(R\) be a commutative ring. Let
For a positive integer \(N\) and an address \(j\in\{0,\ldots,N-1\}\), define the residue state packet
Historical theorem D.96: Companion jump recurrence
Every residue state packet satisfies
More explicitly,
Proof
The state relation gives \(v_n=C^nv_0\). Substitute \(n=Nk+j\).
We use the resultant convention
when \(f\) is monic, with roots counted with multiplicity.
Historical theorem D.97: Characteristic polynomial of the jump
Let
Then
The identity holds over the coefficient ring after interpreting the resultant universally.
Proof
After passage to an algebraic closure, let \(\alpha_1,\ldots,\alpha_d\) be the eigenvalues of \(C\), counted with algebraic multiplicity. The resultant is
which is the characteristic polynomial of \(C^N\). Both sides are polynomial expressions with integer coefficients in the entries of \(C\), so the identity descends to every commutative coefficient ring.
D.9.2 Second order recurrences
On this page · Permalink · Source line 2853
Historical theorem D.98: Residue subsequences of a second order recurrence
Suppose
over a commutative ring. Define \(V_0=2\), \(V_1=P\), and
For every positive integer \(N\) and every address \(j\), the subsequence
satisfies
Proof
The companion matrix
has trace \(P\) and determinant \(Q\). The trace of \(C^N\) is \(V_N\), while its determinant is \(Q^N\). Cayley Hamilton applied to \(C^N\) gives
Apply this identity to the residue state packet and take its scalar coordinate.
Historical corollary D.99: Fibonacci residue packets
Let \(F_0=0\), \(F_1=1\), and \(F_{n+2}=F_{n+1}+F_n\). Let \(L_N\) denote the Lucas number. For every \(N\geq1\) and every address \(j\),
Proof
Apply Historical theorem D.98 with \(P=1\) and \(Q=-1\). Then \(V_N=L_N\).
D.9.3 Finite and local periodicity
On this page · Permalink · Source line 2907
Historical theorem D.100: Periodicity of an invertible recurrence modulo a prime power
Let
For every \(L\geq1\), every state orbit modulo \(p^L\) is purely periodic. Its period divides the order of \(C\) in
If \(p\mid\det C\), every orbit is still eventually periodic.
Proof
When \(p\nmid\det C\), multiplication by \(C\) is a permutation of the finite state set \(({\mathbb Z}/p^L{\mathbb Z})^d\). Every orbit of a permutation is periodic, and applying the group order relation for \(C\) gives the divisibility statement. Without invertibility, repeated application of a map on a finite set eventually repeats a state, after which the orbit is periodic.
Historical corollary D.101: Residue packet periods
Under the invertibility hypothesis of Historical theorem D.100, every residue packet with jump \(N\) has period dividing the order of \(C^N\) modulo \(p^L\).
Proof
Use the jump matrix from Historical theorem D.96.
D.9.4 The common integral spine
On this page · Permalink · Source line 2935
Historical theorem D.102: Base change of an integral recurrence
Let
The integral orbit
determines, by base change, compatible orbits in every ring \(R\) equipped with a homomorphism \({\mathbb Z}\to R\). In particular, the reductions modulo every positive integer and the orbits in every \({\mathbb Z_p}^d\) share the same companion matrix, characteristic polynomial, and integer recurrence relations.
Proof
Every coordinate of \(C^nv_0\) is an integer polynomial in the entries of \(C\) and \(v_0\). Applying a ring homomorphism commutes with matrix multiplication and preserves every polynomial relation with integer coefficients.
Historical corollary D.103: Prime independent recurrence spine
An integral companion system gives a canonical common source for all of its local realizations. No choice of coefficient prime is required to define the recurrence or its residue packets.
Proof
Apply Historical theorem D.102 to the companion matrix and its initial state.
Historical remark D.104
This theorem supplies a prime independent spine for integral linear recurrences. It does not prove that every unrelated family of local arithmetic packets arises from one global object.