Skolem Meets Bateman-Horn
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917594336854016 |
|---|---|
| author | Luca, Florian Maynard, James Noubissie, Armand Ouaknine, Joël Worrell, James |
| author_facet | Luca, Florian Maynard, James Noubissie, Armand Ouaknine, Joël Worrell, James |
| contents | The Skolem Problem asks to determine whether a given integer linear recurrence sequence has a zero term. This problem arises across a wide range of topics in computer science, including loop termination, formal languages, automata theory, and control theory, amongst many others. Decidability of the Skolem Problem is notoriously open. The state of the art is a decision procedure for recurrences of order at most 4: an advance achieved some 40 years ago, based on Baker's theorem on linear forms in logarithms of algebraic numbers.
A new approach to the Skolem Problem was recently initiated via the notion of a Universal Skolem Set: a set $S$ of positive integers such that it is decidable whether a given non-degenerate linear recurrence sequence has a zero in $S$. Clearly, proving decidability of the Skolem Problem is equivalent to showing that $\mathbb{N}$ itself is a Universal Skolem Set. The main contribution of the present paper is to construct a Universal Skolem Set that has lower density at least $0.29$. We show moreover that this set has density one subject to the Bateman-Horn conjecture. The latter is a central unifying hypothesis concerning the frequency of prime numbers among the values of systems of polynomials. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_01152 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Skolem Meets Bateman-Horn Luca, Florian Maynard, James Noubissie, Armand Ouaknine, Joël Worrell, James Discrete Mathematics Number Theory F.3.0; G.2.0; I.1.2 The Skolem Problem asks to determine whether a given integer linear recurrence sequence has a zero term. This problem arises across a wide range of topics in computer science, including loop termination, formal languages, automata theory, and control theory, amongst many others. Decidability of the Skolem Problem is notoriously open. The state of the art is a decision procedure for recurrences of order at most 4: an advance achieved some 40 years ago, based on Baker's theorem on linear forms in logarithms of algebraic numbers. A new approach to the Skolem Problem was recently initiated via the notion of a Universal Skolem Set: a set $S$ of positive integers such that it is decidable whether a given non-degenerate linear recurrence sequence has a zero in $S$. Clearly, proving decidability of the Skolem Problem is equivalent to showing that $\mathbb{N}$ itself is a Universal Skolem Set. The main contribution of the present paper is to construct a Universal Skolem Set that has lower density at least $0.29$. We show moreover that this set has density one subject to the Bateman-Horn conjecture. The latter is a central unifying hypothesis concerning the frequency of prime numbers among the values of systems of polynomials. |
| title | Skolem Meets Bateman-Horn |
| topic | Discrete Mathematics Number Theory F.3.0; G.2.0; I.1.2 |
| url | https://arxiv.org/abs/2308.01152 |