Scalar recurrence sequences with finitely repairable power subsequences
September 8, 2026
Abstract
We give a finite algebraic criterion for an integral linear recurrence sequence sampled at to admit a fixed multiplier satisfying the Dold congruences. The criterion permits repeated characteristic roots, root-of-unity quotients, and finite transients. It consists of polynomial identities indexed by the Galois group and the power residues modulo a root-of-unity modulus. For a nonzero nondegenerate recurrence without a transient, finite repair is equivalent to simplicity and divisibility of by the exponent of the Galois group of its Binet coefficient field. We also give a sufficient multiplier in terms of coefficient denominators and ramification, a terminating procedure for the least multiplier when , and an effectively ultimately periodic description of the admissible sampling exponents. The necessity argument combines Frobenius congruences with Chebotarev and Skolem–Mahler–Lech; sufficiency treats ramified primes directly.
1. Introduction
For an integer sequence , the Dold congruences are
We say that has finite repair if some positive integer makes satisfy (1). Its least such multiplier is denoted . Only divisibility is considered: nonnegativity of the resulting orbit numbers is a separate question.
For unsampled recurrence sequences, Minton’s trace classification characterizes finite repair [5]; a precise restatement is [1, Theorem 2.4]. Luca and Ward [3, Theorem 1] give a sufficient splitting-field exponent condition for power subsequences of simple recurrences, with further size hypotheses on the sampling exponent. Rajs [6, Theorems 8 and 9] treats unsampled scalar sequences and gives additional sufficient sampled bounds. These results motivate the question considered here: for a fixed scalar sequence and a fixed positive integer , exactly when is finitely repairable?
The question is formulated here as a classification problem; we do not attribute this exact formulation to a numbered published conjecture. A sufficient condition using the entire root splitting field can miss scalar cancellations. For example, a trace sequence can be repairable without sampling even when its roots generate a nontrivial extension. Degenerate recurrences present an additional issue: polynomially weighted components may vanish at all sampled indices without vanishing identically.
Our finite criterion handles both phenomena. In the nondegenerate case, the answer is controlled by the field generated by the Binet coefficients. In the general case, polynomial identities on the power residues replace coefficientwise invariance. The displayed multiplier is sufficient and need not be sharp. For every sampling exponent greater than one, a further finite procedure determines the least multiplier, though it need not do so efficiently.
2. The finite criterion
An integral linear recurrence means an integer sequence satisfying a monic constant-coefficient recurrence over from index one. Its standard generalized Binet decomposition has the form
where the are distinct nonzero algebraic integers, the nonzero polynomials have coefficients in the splitting field of the nonzero characteristic roots, and has finite support. The root set and polynomial weights are Galois equivariant:
One obtains this decomposition by the generalized eigenspace decomposition of a rational companion matrix. Its nilpotent part gives the finite transient; its other Jordan blocks give the polynomial weights. Uniqueness of distinct exponential-polynomial components gives (3) and the rationality of . A sequence with nonzero constant term in its minimal recurrence has . The empty root set is allowed, with .
Put . Partition into equivalence classes by declaring when is a root of unity. Choose a representative root in each class and write
Let be the least common multiple of the orders of all root-of-unity quotients among the roots; set if there are none. Thus every . For , define
For , and a class , define
The phase is independent of the representative of modulo . Changing multiplies this polynomial by a nonzero root of unity and does not change its vanishing.
Theorem 1 (Finite scalar criterion).
Let be as in (2) and fix . The sequence has finite repair if and only if both of the following hold:
for every positive integer ;
as a polynomial for every , every and every class .
These are finitely many algebraic tests, since the transient has finite support. If they hold, choose a positive integer such that all are algebraic integers. If is the ramification index at in , then a sufficient multiplier is
For an empty root set take and the empty product to be one.
The field is Galois, so is independent of the prime above . No discriminant coprimality assumption is imposed in the sufficiency direction. All equations in condition (2) are exact identities in a number field, not congruences sampled at finitely many integers.
Corollary 2 (Coefficient-field classification).
Suppose is nonzero, has no transient, and is nondegenerate: no quotient of distinct roots is a root of unity. Then finite repair of is possible exactly when every is constant and
Here is Galois. Thus a simple nondegenerate sequence has a least admissible sampling exponent, namely ; a nonsimple nondegenerate sequence has none.
In particular, the root field supplies a sufficient exponent, but the exact exponent in this scalar setting is a quotient-group invariant. At , the coefficients in the nondegenerate case must be rational, in agreement with Minton’s established trace classification.
This proves necessity. Conversely, pairing divisors gives
so the stated congruences imply divisibility by each full prime power in an arbitrary index.
Lemma 4 (Power-index identity test).
Let , , and be as above, and let . Put . The following are equivalent:
for every sufficiently large positive integer ;
for every and class , the polynomial is zero;
for every positive integer .
Proof.
Condition (2) implies (3) by grouping terms according to their classes, and (3) implies (1). For the remaining implication, fix a power residue and choose an integer with . The sequence , for nonnegative sufficiently large , equals
The quotients of distinct bases are not roots of unity: otherwise the corresponding quotient of representative roots would itself be a root of unity. This is a nondegenerate exponential polynomial unless all its polynomial coefficients vanish. There are infinitely many distinct integers with , so (1) supplies infinitely many zero terms on this progression. By the Skolem–Mahler–Lech theorem, a nonzero nondegenerate recurrence over a characteristic-zero field has only finitely many zeros; see [2, Theorem 1.8]. Hence all polynomial coefficients vanish. Substitution is injective on , proving (2).
This use of Skolem–Mahler–Lech requires no effective bound for isolated zeros. The test determines whether an entire prescribed family of indices vanishes; it does not decide whether a general recurrence has an isolated zero.
4. Necessity: from prime congruences to identities
Assume that repairs . Fix a positive integer and an element . Chebotarev supplies infinitely many unramified rational primes with Frobenius conjugacy class equal to that of [4, Theorem 8.31]. For each, choose a prime ideal of whose arithmetic Frobenius is exactly ; conjugating a prime above makes this choice possible.
Discard the finitely many primes dividing , coefficient denominators, and any primes too small for to lie beyond the support of the transient. The first-level local congruence gives
Since and , it follows that
The algebraic number on the left is fixed once and are fixed. A nonzero algebraic number is divisible at only finitely many prime ideals after its denominators are cleared. Thus (7) is an exact equality:
The order of quantifiers matters: Chebotarev is used with each fixed, rather than with a single prime required to work uniformly for infinitely many .
For large the transient vanishes. Lemma 4 applied to the remaining exponential polynomial proves precisely the identities in condition (2) of Theorem 1. The same lemma then shows that the exponential sum in (9) vanishes for every. Therefore for every , proving condition (1). This argument also covers an empty root set directly.
5. Sufficiency, including ramified primes
The following deliberately coarse bound keeps the treatment of ramification elementary.
Lemma 5 (Ramified power lifting).
Let be a finite extension of ramification index , with valuation normalized by . If lie in its valuation ring and , then
Also, for every integer .
Proof.
The last assertion follows by factoring . If , expansion of gives the lower bound
As long as , this is at least , since . After iterations the valuation is therefore at least one. Each subsequent iteration increases it by at least one. For this gives . For , the claimed right side is nonpositive, so integrality suffices. If a difference is zero the inequalities are immediate.
Now suppose the two conditions in Theorem 1 hold. Lemma 4 and the vanishing transient give (8). In particular, the identity element yields
Choose as in the theorem and put , which are algebraic integers.
Fix a rational prime and a prime of above it. The decomposition group surjects onto the Galois group of the residue field; choose a lift of arithmetic residue Frobenius [4, Section 8]. In the completion , with and ramification index , every algebraic integer satisfies
For and , apply Lemma 5 with and then raise to the power . We obtain
Multiplication by each integral and summation preserve this lower bound. Equations (11) and (8), the latter used with and index , identify the sum as
This number is a rational integer. Its normalized valuation in is its ordinary -adic valuation, so
The multiplier (5) consequently supplies the modulus at every prime; unramified primes have and need no extra factor. Lemma 3 completes the proof of Theorem 1. Notice that no individual equality was assumed: the exact sampled sum identity is what handles degeneracy.
6. The coefficient field and the exponent spectrum
In the nondegenerate case all classes are singletons and . The identity in (4) for says , so simplicity is necessary. The remaining identities are
By equivariance they mean exactly that every fixes every . The set of coefficients is stable under , so its generated field is stable under and hence Galois over . Restriction maps onto . Therefore the preceding identities hold if and only if every element of that quotient group has -th power equal to one, which is (6). Sufficiency follows from Theorem 1.
is effectively ultimately periodic, given exact algebraic data for its Binet decomposition. More precisely, let bound the support of its transient, put
where is the Carmichael exponent and . Choose an integer with . For all , membership in depends only on .
Proof.
For , condition (1) of Theorem 1 reduces to , since for . The group element depends only on .
It remains to consider the set of power residues. Work modulo a prime power exactly dividing . For any integer divisible by , once . For , the value is periodic in with period . The Chinese remainder theorem shows that, for , the entire map , and therefore its image , depends only on . Thus every identity in Theorem 1 repeats after .
All tests involve finitely many coefficients in a fixed number field, finitely many group permutations and residues, and the finite transient. Testing determines the whole spectrum. The use of Skolem–Mahler–Lech in proving the criterion introduces no search for its ineffective zero bound.
Remark 7.
The theorem asserts a finite decision procedure, not an efficient one. Splitting-field calculations and root-of-unity grouping may be large. Exact algebraic representations are essential; numerical approximations to roots are not sufficient certificates for these identities.
7. An exact finite procedure for the least multiplier
Theorem 8 (Finite local search for ).
Suppose the criterion in Theorem 1 holds and . With and as there, put and
The least repair multiplier is computable by testing only primes dividing and levels . At each such prime its exponent is
where a zero difference contributes no positive deficit. The apparent infinite range in can be replaced by a finite range obtained from the recurrence modulo .
Proof.
The proof of sufficiency actually gives
For the right side is at least , so no multiplier is needed at those levels. If divides neither nor the field discriminant, then , and , leaving no levels to check.
Fix one remaining pair . The state vector of an integral recurrence modulo lies in a finite set and has a deterministic transition. It is therefore eventually periodic, with computable preperiod endpoint and positive period , obtained by recording states until one repeats. For every the two sampled indices are at least , and their residues modulo depend only on . The condition depends only on . Consequently it suffices to test
Computations modulo determine every positive deficit in (13): if the difference is zero modulo , its deficit is nonpositive. Taking the maximum yields exactly the local multiplier required by Lemma 3. Combining the finitely many primes proves the assertion.
The state spaces in this procedure may be very large. The result proves computability and gives a rigorous stopping rule; it is not a polynomial-time claim or a short closed formula. It also does not claim a new exact algorithm for the unsampled case , where the level-bound argument has zero denominator.
8. Examples and boundary cases
Example 9 (The same roots, different admissible exponents).
Let and . Their quotient is not a root of unity, since its real absolute value is different from one. The Lucas sequence has coefficient field and admits every positive sampling exponent. The Fibonacci sequence has coefficient field and admits exactly the positive even exponents. These conclusions recover known behavior [3]; they illustrate that the root field alone is insufficient to distinguish the two scalar sequences. We make no new priority claim for these examples.
Example 10 (Strictly smaller required exponent).
Let be the splitting field of . This cubic has no rational root and has discriminant , a positive nonsquare. Its Galois group is , and all its roots are real. Hence is a totally real Galois extension with group exponent six. Its quadratic subfield is .
Choose an integral primitive element of , and then an integer sufficiently large that every conjugate of is positive. Define
This is an integer sequence: its terms are traces of algebraic integers. Its six roots are distinct positive numbers, so it is nondegenerate; its coefficients are the nonzero numbers . Its minimal characteristic roots generate , whereas its coefficient field is . Corollary 2 gives exactly the even admissible exponents. In particular, sampling at squares works although six does not divide two. This separates the scalar condition from the full root-group exponent condition.
Example 11 (Repeated roots can disappear on squares).
Let be the integer periodic sequence of period four with values
The sequence is annihilated by , where is the shift operator, so is an integral recurrence with repeated nonzero roots. Squares are congruent to zero or one modulo four; hence . This sampled sequence satisfies Dold congruences with multiplier one, by elementary commuting-power lifting (or Theorem 1 applied to its single integral root). Thus simplicity of the original scalar recurrence is not necessary in the degenerate case.
For contrast, is nondegenerate and nonsimple, and no power subsequence has finite repair. Directly, for every odd prime and every , .
Example 12 (Finite transients are not harmless).
Let , where and all other . This is an integral recurrence with a nilpotent component. Theorem 1 shows that all positive sampling exponents except and are admissible: precisely these two exponents sample the transient position . An arbitrary finite change of a repairable sequence need not preserve finite repair. If instead , no sampling exponent is admissible.
9. Scope and further questions
The main result is a complete scalar finite-repair criterion, supplemented for by a terminating computation of the least multiplier. In contrast to simultaneous entrywise or recurrence-module criteria, it accounts for observed cancellations, degenerate components, and transients. The coefficient-field corollary and the ultimately periodic exponent spectrum are consequences of the same classification and are presented together as one contribution.
Three concrete questions remain. First, can the exact local repair exponents be obtained efficiently from the finite identities, without traversing large modular recurrence state spaces? Second, how efficiently can the eventually periodic spectrum be represented without enumerating the full splitting-field group? Third, under useful hypotheses on growth and signs, when does finite Dold repair imply realizability after scaling? No answer to these questions is asserted here.
The proof uses standard Chebotarev and Skolem–Mahler–Lech inputs, which are explicitly cited. The claimed new contribution is their combination with the sampled identity criterion and ramified sufficiency, rather than either external theorem. The source comparison accompanying this manuscript records the texts checked and access limits. Computational examples are consistency checks and are not premises of the infinite statements.
Preparation.
This manuscript was developed with OpenAI Codex assistance in problem formulation, proof construction, source comparison and exposition. Internal checking is not external peer review.
References
[1] J. Byszewski, G. Graff and T. Ward, Dold sequences, periodic points, and dynamics, Bull. London Math. Soc. 53 (2021), 1263–1298. doi:10.1112/blms.12531.
[2] Y. Bilu, F. Luca, J. Nieuwveld, J. Ouaknine and J. Worrell, Twisted rational zeros of linear recurrence sequences, J. London Math. Soc. 111 (2025), article e70126. doi:10.1112/jlms.70126.
[5] G. T. Minton, Linear recurrence sequences satisfying congruence conditions, Proc. Amer. Math. Soc. 142 (2014), 2337–2352. doi:10.1090/S0002-9939-2014-12168-X.
[6] M. Rajs, On Dold condition and fail factor of linear recurrent sequences, arXiv:2509.09847v1 (2025). https://arxiv.org/abs/2509.09847.