CS Paper Radar

Twisted Rational Zeros and Local-Global Principles for Linear Recurrence Sequences

Piotr Bacik

cs.FL math.NT ·submitted 2026-09-14 21:58 UTC · v1
theory

Abstract

The Skolem Problem asks whether a given linear recurrence sequence (LRS) has a zero term, and is equivalent to proving an effective version of the Skolem-Mahler-Lech theorem, which states that a non-degenerate LRS has finitely many zeros. Decidability of the Skolem Problem however, has remained open for many decades. Bilu et al. (2022) showed that the Skolem Problem for simple LRS is decidable subject to the weak $p$-adic Schanuel Conjecture and the Skolem Conjecture (also known as the exponential local-global principle), the latter of which states that an LRS has an integer zero if and only if it has a zero modulo every integer $m$. This paper works towards understanding the Skolem Conjecture. We provide an example showing that a natural strengthening of the Skolem Conjecture, where we restrict $m$ to be a prime power, is false. This failure is accounted for by the relationship between $p$-adic zeros of LRS (which arise naturally in the proof of the Skolem--Mahler--Lech theorem and have been studied algorithmically by Bacik et al. (2026)) and twisted rational zeros (introduced by Bilu et al. (2025)). By studying this relationship further, we are able to prove the main result of this paper: a local-global principle for simultaneous zeros of two coprime LRS, subject to the $p$-adic Schanuel Conjecture. A fundamental step in proving this result is characterising when twisted rational zeros are (or are not) $p$-adic zeros for infinitely many primes $p$, which we do unconditionally. This also answers two open questions of Bilu et al. (2025). Finally, we conjecture that the existence of twisted rational zeros is the only way that the aforementioned strengthened Skolem Conjecture may fail, which is supported by a heuristic argument.

Comment
23 pages, comments welcome

Closest papers

Nearest neighbours by meaning across the whole index.

Rich Sequences and Decidability of Arithmetic Theories

cs.LO cs.FL ·2026-09-17 ·Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine
similarity 0.58
Abstract

We develop a new framework for proving the undecidability of first-order theories of structures of the form $\langle \mathbb{N}; +, P \rangle$, $\langle \mathbb{N}; <, f \rangle$, and $\langle \mathbb{N}; +, f\rangle$, where $P \subseteq \mathbb{N}$ and $f \colon \mathbb{N} \to \mathbb{N}$. It is based on the recent proof of Hieronymi and Schulz that the first-order theory of $\langle \mathbb{N}; +, \{2^n \colon n \in \mathbb{N}\}, \{3^n \colon n \in \mathbb{N}\}\rangle$ is undecidable, and capable of transforming various randomness results about integer sequences into undecidability proofs. We apply our method to a large class of integer linear recurrence sequences, as well as various special functions, in particular showing that the first-order theories of $\langle \mathbb{N}; +, \{u_n \colon n \in \mathbb{N}\} \cap \mathbb{N}\rangle$, $\langle\mathbb{N}; <, n \mapsto \max\{0,u_n\}\rangle$, and $\langle \mathbb{N}; <, φ\rangle$ are undecidable, where $(u_n)_{n\in\mathbb{N}}$ is any integer LRS with exactly two non-repeated dominant roots satisfying a non-degeneracy assumption, and $φ$ is Euler's totient function.

0.26

Skolem-Mahler-Lech in rings of positive characteristic: a shorter proof and a multi-dimensional generalization

cs.LO math.NT ·2026-09-02 ·Ruiwen Dong, Doron Shafrir
theory similarity 0.57
Abstract

Let $R$ be a commutative ring and $f(a_1, \ldots, a_n) = \sum_{i=1}^k r_{i1}^{a_1} \cdots r_{in}^{a_n} m_i$ be a linear-exponential map over an $R$-module $M$. Dong and Shafrir (2026) showed that, when $\ell M = 0$ for some $\ell \in \mathbb{N}_{>0}$, the zero set of $f$ is the intersection of effectively computable $p$-normal sets, where $p$ ranges over the prime divisors of $\ell$. This generalizes an earlier theorem of Derksen and Masser (2012) on the solution set of $S$-unit equations over fields of positive characteristic. The purpose of this paper is twofold. First, we give a shorter proof of Dong and Shafrir's result, using the theorem of Derksen-Masser as a blackbox. Our proof also yields a decomposition of the zero set as a positive Boolean combination of affine transformations of zero sets of linear-exponential equations over fields. Second, we prove a multi-dimensional generalization of the Skolem-Mahler-Lech theorem over rings of finite characteristic. Specifically, we show that the zero set of every $n$-dimensional linear recurrence sequence over an $R$-module $M$ satisfying $\ell M = 0$ is the intersection of effectively computable $p$-normal sets (in $\mathbb{N}^n$), where $p$ ranges over the prime divisors of $\ell$. For example, this gives a decision procedure for whether two classical linear recurrence sequences have a common value over a ring of characteristic $p^a$ or $p^a q^b$, where $p$ and $q$ are primes.

0.26

Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence

cs.CC math.NT ·2026-11-01 ·Joseph M. Shunia
theory similarity 0.55
Abstract · 12 pages. An earlier version appeared as Revision 2 of ECCC TR23-200: https://eccc.weizmann.ac.il/report/2023/200/#revision2

We give a deterministic polynomial-time primality test whose main verification is the congruence $(1+X)^n=1+X^n$ in $C_n[X]/(X^r-b(Y))$, where $C_n=(\mathbb{Z}/n\mathbb{Z})[Y]/(Φ_r(Y))$. Two identities in the coefficient ring normalize $b$ and ensure compatibility with the main congruence. A finite-field root count and a lattice bound show that an accepted input is a prime power; elementary preprocessing excludes nontrivial perfect powers. We construct $b$ deterministically using Jacobi sums and the uniform Dedekind-zeta zero-free theorem of Cureton and Thorner, which extends OpenAI's Hecke zero-free theorem. The total bit complexity is $L^{32+o(1)}$, where $L=\lceil\log_2 n\rceil$, and verification after constructing $b$ costs $L^{6+o(1)}$. More generally, for a fixed real algebraic $1/2\leθ<1$, a common zero-free boundary $\Re s>θ$ for the relevant Dedekind zeta functions gives $L^{\max\{6,(1-θ)^{-1}\}+o(1)}$. This bound reaches $L^{6+o(1)}$ at $θ=5/6$, and hence under GRH. We state a fixed-base modification of Agrawal's conjecture for odd integers passing the base-$2$ Fermat test, using the modulus $X^r-2$ with $r$ the least positive integer not dividing $n(n-1)$.

0.44

A Degree--Size Relation for Resolution over Polynomials

cs.CC cs.LO ·2026-09-30 ·Shuo Pang
similarity 0.53
Abstract · Parameters in Section 8 (Conclusions) made explicit

For every constant-width CNF, we show that linear degree in polynomial calculus (PC) implies exponential size in resolution over constant-degree polynomials, over the same prime field. Applications include exponential lower bounds for CNFs in $\operatorname{Res}(\operatorname{PC}_r/\mathbb{F}_p)$ and hence in $\operatorname{Res}(\oplus_p)$, separations between different moduli, improved lower bounds for $\operatorname{Res}(k)$ up to $k=\varepsilon\log n$, proof-search consequences, and an implication of super-polynomial $AC^0[p]$-Frege bounds from very strong PC degree lower bounds. The proof uses the common-multiplier idea isolated from Braun [arXiv:2609.23015] to construct a Razborov--Smolensky approximation that preserves inferences, without introducing extension variables. The approximation errors are measured by ranks of the multiplication maps induced by the error-witness polynomials, modulo bounded-degree PC consequences.

0.49

On existential Büchi arithmetic in two coprime bases

cs.LO cs.FL ·2026-08-25 ·Joris Nieuwveld
similarity 0.53
Abstract

For multiplicatively independent natural numbers $α$ and $β$, Villemaire showed in 1992 that the first-order theory of Presburger arithmetic expanded with both Büchi predicates $V_α$ and $V_β$ is undecidable, as it encodes multiplication. In recent years, Hieronymi and Schulz showed that Presburger arithmetic expanded with the weaker power predicates $α^\mathbb{N} = \{α^n: n \in \mathbb{N}\}$ and $β^\mathbb{N}$ is also undecidable, while Karimov et al. showed that the existential fragment of this theory is decidable. These results left open the natural problem of determining the decidability of the existential fragment of Villemaire's original expansion. We settle this question for coprime $α$ and $β$. Specifically, we give a quantifier-elimination argument that proves the decidability of the existential fragment of $\mathsf{FO}(\mathbb{Z};<,+, V_α, V_β)$.

0.45

Positivity Proofs for Third-Order Holonomic Sequences via Differences Scaled by Rational Functions

cs.DM cs.SCmath.DS ·2026-11-07 ·Fugen Hagihara
similarity 0.51
Abstract · 23 pages, 1 figure

We study the positivity of sequences $f$ that satisfy a third-order holonomic recurrence $f(n+3)= P_2(n) f(n+2) + P_1(n) f(n+1) + P_0(n) f(n)$ whose coefficients $P_0$, $P_1$ and $P_2$ are rational functions in $\R(x)$. We provide a sufficient condition on $P_0$, $P_1$ and $P_2$ for the recurrence to admit a solution all but finitely many terms of which are positive, and whose positivity is robust under small perturbations of the initial values. This sufficient condition is also a necessary condition for a subclass of the recurrences. By developing the proof of this sufficient condition, for another subclass of the recurrences, we show that it is decidable whether all the terms of a given sequence are positive for any initial values outside an exceptional plane. It is common to construct a positivity certificate, which guarantees the positivity of a solution, to show this kind of decidability. In this paper, we construct a new type of positivity certificate via the $S$-scaled difference $f(n+1) - S(n) f(n)$ for a suitable $S \in \R(x)$. This result partially improves the work by Ibrahim and Salvy.

0.28

Eventual Nonnegativity of a Matrix Is in P

cs.LO ·2026-09-20 ·Julian D'Costa
theorycode/data similarity 0.51
Abstract · 19 pages, including appendix. v2: added a reference and minor edits to the exposition. A Lean 4 formalisation of the structural criterion an…

Given a rational matrix $A$, is every sufficiently large power $A^n$ entrywise nonnegative? We prove that this problem is decidable in deterministic polynomial time. This is in contrast with deciding eventual nonnegativity of a single prescribed entry sequence $(A^n)_{ij}$, which amounts to the Ultimate Positivity Problem for linear recurrence sequences, whose decidability is open. The previous decidability procedure (D'Costa, Ouaknine and Worrell, STACS 2024) splits the matrix powers into residue classes modulo a torsion exponent $D$ whose value can be exponential in the input size. We show that it is sufficient to check a single progression $A^{Dk+1}$: the exponents $n$ with $A^n \geq 0$ are closed under addition, and two consecutive exponents of the progression are coprime, so they generate every sufficiently large exponent. Along the progression, eigenvalues are grouped by their common $D$th power, and the required coefficients for each group are computed without forming $A^D$, any $λ^D$, or a splitting field: each summand is evaluated in its own root field $\mathbb{Q}(λ)$, and Galois equivariance keeps the degree and height of every class sum polynomially bounded, enabling certified zero and sign tests. The same algorithm with one case rejected decides eventual positivity, and a variant decides whether the matrix has any nonnegative power at all.

0.40

Removing $m$ from $m$-pile Divisor Nim

cs.DM math.CO ·2026-10-03 ·Satyam Tyagi
theory similarity 0.50
Abstract · 23 pages, 15 tables

In Divisor Nim, a player removes from one heap a positive number of stones that divides the size of every other heap. We prove that the Sprague--Grundy (SG) value satisfies $g(P)\le 2h_{\min}+\lfloor\log_2h_{\min}\rfloor$, where $h_{\min}$ is the smallest nonempty heap, independently of the number and sizes of the other heaps. The proof starts with odd heaps and classifies removals by their factors of $2$. The largest heap in a starting board then supplies an SG bound valid throughout every successor chain. When one heap varies, we sharpen Morisawa's eventual-period bound: the smallest fixed heap controls the SG value range, the number of consecutive values compared, and an increase in the varying heap that repeats legal moves. The remaining dependence on the fixed board lies in the SG periods of direct successors. Using the largest fixed heap, we derive an explicit common period for all these recursive layers. Its possible prime divisors belong to a fixed finite set, independent of heap count; their exponents remain controlled by the total fixed stones. Finally, joining boards under one shared divisor rule preserves and can tighten the SG ceiling. Minimum 2-adic depth and its count parity determine every joined outcome, and a join with at least two odd heaps has exact SG value $0$ or $1$. We close with two conjectures: $g(P)\le2h_{\min}$, and that the least eventual SG period, when one heap varies, divides $2\operatorname{lcm}(1,\ldots,h_{\max})$. Here $h_{\max}$ is the largest fixed heap, excluding the varying heap. The second claim would remove heap-count dependence from the period bound as well.

0.30