Squarefree repair factors and optimal exponents for linear recurrences
Henry Zweiman
September 8, 2026
Abstract
An integer sequence satisfies the Dold congruences if its Möbius transform at every positive integer is divisible by . We determine the least multiplier that makes all entries of a power-indexed integer matrix sequence satisfy these congruences: under a finite-field exponent condition, it is the product of the primes at which the matrix has nonsemisimple reduction. Consequently, for a fixed separable integral recurrence polynomial of degree with nonzero constant term, the exact multiplier that works uniformly for every integral initialization indexed from is when sampling at , where is a positive multiple of . For the fundamental Lucas sequence of nonzero discriminant , we obtain the exact scalar repair factor along every positive even power. We also show that the multiples of are exactly the exponents admitting finite repair for every separable recurrence of order at most with nonzero constant term. The sufficiency proofs use Jordan decomposition over finite fields and lifting of congruences between commuting matrices; exponent necessity uses cyclic number fields and Chebotarev. These statements concern Dold divisibility; nonnegativity of orbit counts is a separate condition.
1. Introduction and principal results
For a sequence of integers, define
The Dold congruences require for every . Write for the least positive integer such that satisfies these congruences, with if no such integer exists. We use this notation for signed sequences as well. It is a divisibility invariant: the condition , required to interpret as fixed-point counts of a map, is not part of its definition.
The repair phenomenon for power subsequences is exemplified by the Fibonacci sequence. Moss and Ward [4] established realizability after multiplication by along positive even powers and proposed a corresponding discriminant-scaled Lucas congruence. Luca and Ward [2], Theorem 5, proved that conjecture. Rajs [5] investigated repair factors for general linear recurrences and their power subsequences. Here we work with integral matrices directly, avoiding the denominators of a Binet representation.
Set . For a nonzero integer , is the product of its distinct positive prime divisors, with .
Theorem 1 (Uniform repair for a fixed recurrence).
Let
be monic, with , , and . Let be a positive multiple of . Among positive integers , the least one with the following property is
for every choice , the recurrence
has satisfying the Dold congruences.
The conclusion is uniform over initial data. A particular sequence may admit a smaller multiplier. A fundamental quadratic recurrence permits an exact scalar answer.
Theorem 2 (Exact Lucas repair).
Let , and define
If , then for every ,
If , this failure invariant is infinite for every .
Theorem 3 (Optimal universal exponents).
Fix and . The following are equivalent:
;
for every integer sequence admitting a monic separable integral recurrence polynomial of degree at most with nonzero constant term, its subsequence has finite Dold repair factor.
The repairing integer in the second condition may depend on the sequence.
These theorems do not assume that the terms are nonnegative. In particular, the conclusion applies to negative recurrence parameters and to periodic or degenerate Lucas sequences, subject to the stated discriminant distinction.
2. The matrix repair theorem
A sequence of integer matrices satisfies the Dold congruences if every matrix entry does so. A matrix over is called semisimple here if it is diagonalizable over an algebraic closure of .
Theorem 4 (Exact entrywise matrix repair).
Let be annihilated by a monic polynomial of degree with . Suppose satisfies:
for every prime , the degree of every irreducible factor of modulo divides ;
.
Let be the set of primes at which has nonsemisimple reduction. Then is finite, and
is the least positive integer for which satisfies the Dold congruences entrywise. In particular,
Both hypotheses on hold if is a positive multiple of .
The exact factor depends on the integral matrix, not merely on a chosen annihilating polynomial. For example, a diagonal integer matrix has semisimple reduction at every prime, even if two of its eigenvalues become equal modulo some prime.
We give the local argument in detail, including the small-prime and noninvertible cases.
Lemma 5 (Local Dold criterion).
Let be a free abelian group and let . Then
if and only if, for every prime , every , and every with ,
Proof.
Put . Möbius inversion gives . Thus
which proves necessity. Conversely, pairing divisors gives
The local hypothesis therefore makes divisible by the full power of every prime dividing . Since is free abelian, it follows that .
Lemma 6 (Commuting-power lifting).
Let be commuting integer matrices, and let be prime. If for , then
Proof.
Write . The commutativity of and implies that and commute. In the binomial expansion of , the terms with powers for are divisible by , and the last term is divisible by . All are divisible by , including when and . Induction proves the assertion.
Fix a prime , and put , with if . Reduce modulo and pass to an algebraic closure. Since , every Jordan block has size at most . Every eigenvalue belongs to for an irreducible factor degree of modulo . Hence .
If is a Jordan block, then , and in characteristic ,
It follows that
The size hypothesis gives . At a semisimple prime the same congruence holds with .
For , set . Applying Lemma 6 to the commuting matrices in (1), and then raising both sides to , gives
Since
one additional factor of suffices at every nonsemisimple prime. The case at such a prime is automatic after multiplication by .
At a semisimple prime take . The same argument, now also for , gives a modulus , which is at least . Therefore no multiplier is needed there. If , the polynomial modulo is squarefree and its annihilation of implies semisimplicity. Thus is finite and supported on the prime divisors of . Lemma 5 proves sufficiency of .
For necessity consider the Dold congruence at . Over , the identity holds if and only if is semisimple: the forward direction follows because has derivative , and the reverse direction follows from the eigenvalue condition. Thus at every prime at least one entry of is nonzero. Every integer repairing all entries must be divisible by . This proves exactness.
Finally, if , every irreducible factor degree divides , and implies .
where is the integer companion matrix with ones immediately above the main diagonal and last row . In particular .
For a fixed initial vector , define an integer matrix on by
Then for , so is a fixed entry of . The polynomial annihilates . It is separable because is separable and , and
Every irreducible factor of modulo any prime has degree at most , since the new factor has degree one. The exponent is divisible by all these degrees. Also , including the case . Theorem 4 therefore implies that
satisfies the Dold congruences for every initial vector.
To prove universal sharpness, fix a prime and reduce modulo . Its minimal polynomial remains modulo , because a companion matrix is cyclic over every field. Put
This is zero if and only if modulo divides . Every root of modulo lies in . The roots of are exactly the nonzero elements of this field, each with multiplicity one. It follows that if and only if modulo is squarefree with nonzero constant term, equivalently if and only if . Thus .
The first row of is nonzero. Otherwise, using and
all rows of would be zero. Choose an integral vector whose reduction has . Its recurrence sequence satisfies
Thus every multiplier working for all initial values must be divisible by . This holds for each prime in the proposed radical and proves minimality.
Example 7 (The constant term cannot be omitted).
Let for . The recurrence polynomial is
and . For every positive integer , is odd while , so the prime is required in every repair. Likewise, , so is required. For every even , Theorem 1 gives the factor , which is therefore exact for this particular sequence.
Remark 8 (Comparison with the printed general statement of Luca–Ward).
In [2], Theorem 1(i), the stated sufficient multiplier is a multiple of , with the recurrence initialized at , and the exponent required to be at least and divisible by the Galois-group exponent. Example 7 has and both discriminants equal to . Thus the printed statement allows multiplier , contradicted by its prime- Dold congruence. This is a counterexample to that statement with its printed indexing conventions; we do not assert an official erratum or any conclusion about the other theorems of the article. The initialization argument above accounts explicitly for the extra prime support from .
If , then for every . Theorem 1 therefore gives a finite repair for every sequence in the stated class.
Conversely, suppose . There is an integer , with , such that . Choose a prime , whose existence follows from Dirichlet’s theorem; see [3, Example 8.34]. The Galois group of is cyclic of order by the standard cyclotomic description [3, Section 6]. Taking the fixed field of its subgroup of index produces a cyclic extension of degree .
Choose a nonzero integral primitive element of , and let be its monic minimal polynomial. Then is separable of degree and . Let be the integer matrix of multiplication by on the order , in its basis . Thus .
Fix a generator of . Chebotarev’s theorem [3, Theorem 8.31], applied to the conjugacy class in this finite Galois extension, gives infinitely many unramified rational primes with Frobenius . Each is inert, since its residue degree is the order of its Frobenius. Exclude also the finitely many prime divisors of . At every remaining prime ,
and the reduction generates this field over . Consequently
Indeed the Frobenius orbit of a field generator has length . Since , the multiplication matrix is nonzero modulo each of these infinitely many primes.
There are only entries. Hence some fixed pair satisfies
for infinitely many such . Put . This is an integer sequence annihilated by , so it belongs to the specified class. The Dold congruence for a repaired subsequence at would require
Each of infinitely many distinct primes must therefore divide , which is impossible for a positive integer . This proves necessity.
Remark 9.
The nonzero-constant-term restriction in Theorem 3 is essential with initialization at . The sequence and for is annihilated by the separable polynomial but has infinite repair factor along every positive power.
Since and the lower-left entries of are , respectively, one has for all .
If , the polynomial is separable. Every positive even exponent meets the hypotheses of Theorem 4. That theorem proves sufficiency of .
To prove necessity, fix a prime . The characteristic polynomial of modulo has a repeated root : if is odd, ; if , is even and modulo . Write modulo . The Cayley–Hamilton identity gives , and . Hence
so . The difference from forces to divide every repair multiplier.
If , the same argument applies to every prime, precluding any positive finite repair multiplier. It also covers directly.
Example 10.
For the discriminant is and
Every positive even-power subsequence has exact Dold repair factor . Thus repeated prime powers in the polynomial discriminant do not require repeated prime powers in the repair factor.
Remark 11 (A stronger quadratic congruence).
For any , any prime , any , and , the same Jordan-and-lifting argument with a degree-two annihilator gives
Here the exponent furnished by (2) is , since one may take . This statement does not require a nonzero discriminant. At discriminant primes the scalar obstruction is consequently already visible at the first local level.
6. Relation to previous bounds and verification
Theorem 2 sharpens the sufficient Lucas discriminant factor in [4,2] to an exact radical. The matrix theorem explains this through nonsemisimple reduction. Rajs [5], Theorem 4 and its proof, retains a denominator-clearing factor in addition to a radical for quadratic square subsequences. His Theorem 9 supplies a factor for exponents divisible by the splitting-field degree. The bounds here remove higher prime powers and determine the uniform recurrence factor without constructing a splitting field.
The companion and initialization constructions give a uniform statement about integral recurrence modules. No assertion is made that every individual scalar repair factor is determined by the prime-index congruence alone in arbitrary order.
The accompanying script check.py uses exact modular integer arithmetic. It checks local instances across , eight primes from through , local levels through , and five multiplicative indices. It checks both the congruences and the Lucas minimality witnesses. These computations support the proof and do not replace its infinite-family argument. An independent implementation using arithmetic in the quadratic quotient ring additionally checks composite-index Dold congruences.
References
[1] J. Byszewski, G. Graff, and T. Ward, Dold sequences, periodic points, and dynamics, Bulletin of the London Mathematical Society (2021). doi:10.1112/blms.12531.