Number Theory · Research Note
Prescribing the Zeros of a Linear Recurrence
A construction over one fixed field resolves Derksen’s inverse conjecture: every p-normal set occurs as the exact zero set of a linear recurrence, with a companion Lean 4 proof.
A linear recurrence generates each new term as a fixed linear combination of finitely many earlier terms. Even such a finite rule can vanish exactly at \(1,2,4,8,16,\ldots\).
Take the classical sequence
Here \(t\) is a formal variable, and arithmetic takes place in characteristic two, where \(1+1=0\). Each summand is a geometric progression, so their difference satisfies a linear recurrence. Repeated squaring gives \((t+1)^{2^k}=t^{2^k}+1\), and the powers of two are precisely the zero times.
From a classification to a construction
Harm Derksen classified recurrence zero sets in positive characteristic using a class called \(p\)-normal sets. In 2005, he asked whether every set in this class could actually occur. The question appeared as Conjecture 3.6 in his 2007 paper.
These sets combine arithmetic progressions with sums and differences of powers of \(q=p^e\). For example, take all nonnegative values of \(q^a-q^b\), with the exponents varying independently. Rational coefficients are allowed under the integrality conditions in the definition, as are finite unions and changes at finitely many times.
We construct a finite-order linear recurrence over \(\mathbb F_p(t)\) for every prime \(p\) and every \(p\)-normal set \(S\subseteq\mathbb N_0\), with
The coefficient field is fixed before choosing the pattern. The recurrence’s coefficients and order can vary with \(S\), but equality holds at every nonnegative time, including any prescribed finite changes.
Why one variable is enough
Over a finite field, a recurrence has only finitely many consecutive-term states. Those states eventually repeat, making its zero times eventually periodic. The variable \(t\) makes room for patterns such as powers of \(p\), whose gaps keep growing.
The construction encodes sums of Frobenius powers as products of rational-function factors; negative weights become denominator factors. A reconstruction lemma recovers those factors when a rational function of bounded degree matches the required powers at sufficiently many finite-field points. Further steps control cancellation and limiting configurations, preventing unintended zero times. The construction may temporarily use larger finite fields, but a final algebraic step brings all coefficients back to \(\mathbb F_p(t)\).
Together with Derksen’s classification, this gives an exact realization of every allowed zero pattern. The inverse theorem also has an end-to-end Lean 4 formalization.
This note focuses on the recurrence result discussed in Prescribing Infinite Patterns in Arithmetic Dynamics.