On the growth of hypergeometric sequences
George Kenison, Jakub Konieczny, Florian Luca, Andrew Scoones, Mahsa Shirmohammadi, James Worrell · 2025
Read On the growth of hypergeometric sequences by George Kenison, Jakub Konieczny, Florian Luca, Andrew Scoones, Mahsa Shirmohammadi, James Worrell (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22437.txt.
Introduction
George Kenison and co-authors bound the growth of hypergeometric sequences in a 2025 math paper. These sequences follow a simple rule where each term is a polynomial multiple of the last. They appear across math and computing. The team proves linear growth bounds for their Weil heights in key classes, and applies the result to the membership problem, which asks whether a target value occurs in such a sequence.
Catalog record
| CREATOR | George Kenison, Jakub Konieczny, Florian Luca, Andrew Scoones, Mahsa Shirmohammadi, James Worrell |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-22437
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the growth of hypergeometric sequences George Kenison, Jakub Konieczny, Florian Luca, Andrew Scoones, Mahsa Shirmohammadi, James Worrell Abstract Hypergeometric sequences obey first-order linear recurrence relations with polynomial coefficients and are commonplace throughout the mathematical and computational sciences. For certain classes of hypergeometric sequences, we prove linear growth estimates on their Weil heights. We give an application of our effective results, towards the Membership Problem from Computer Science. Recall that Membership asks to procedurally determine whether a specificed target is an element of a given recurrence sequence. \DeclareSourcemap \maps [datatype=bibtex] \map \step [fieldset=issn, null] \step [fieldset=editor, null] \step [fieldset=address, null] 1 Introduction In this work, we estimate the growths of Weil complexity of hypergeometric sequences. Recall that a rational-valued sequence is hypergeometric if its terms obey a first-order recurrence relation with polynomial coefficients. Specifically, a rational-valued sequence \langle u_{n}\rangle_{n=0}^{\infty} is hypergeometric if its terms obey a recurrence relation of the form f(n)u_{n}=g(n)u_{n-1}, (1) where f(x),g(x)\in\mathbb{Q}[x] are polynomials with rational coefficients and the initial value u_{0}\in\mathbb{Q} is rational. Here and throughout we shall assume that f(x) has no non-negative integer zeroes. This setup and the assumption on f(x) means that the recurrence relation ( 1 ) uniquely defines an infinite sequence of rational numbers. Arguably, the hypergeometric sequences constitute the simplest class of P-finite sequences. Recall that a sequence is P-finite (sometimes holonomic ) if its terms obey a linear recurrence relation with polynomial coefficients. Hypergeometric sequences appear throughout the mathematical and computational sciences in relation to their generating functions. Indeed, these generating functions encompass the common trigonometric and hypergeometric functions and have numerous applications in analytic combinatorics and algebraic computation [ 10 , 18 ] . Main Contributions Given a hypergeometric sequence \langle u_{n}\rangle_{n=0}^{\infty} that obeys recurrence relation ( 1 ), we call the roots of the polynomial coefficients f and g the parameters of sequence \langle u_{n}\rangle_{n=0}^{\infty} . We define classes \mathscr{C} and \mathscr{D} of hypergeometric sequences that make additional assumptions on the parameters as laid out below. Our main contributions are Theorems 1 and 2 , which give linear growth estimates on the Weil heights of hypergeometric sequences in these classes. Our results generalise the following observation. When \langle u_{n}\rangle_{n=0}^{\infty} is a non-constant geometric sequence of the form u_{n}=\alpha^{n} , we have that h_{\weil}(u_{n})=nh_{\weil}(\alpha) . We note that the growths rates of rational hypergeometric sequences (i.e., the class of \langle u_{n}\rangle_{n=0}^{\infty} for which u_{n}=q(n) with q\in\mathbb{Z}[n] ) are given by the well-known estimate h_{\weil}(u_{n})=\deg(q)\log(n)+O(1) (see Proposition 6 ). Thus we exclude the class of rational hypergeometric sequences in \mathscr{C} and \mathscr{D} below. Henceforth for functions a,b\colon\mathbb{N}_{0}\to\mathbb{R} , we shall employ the standard Vinogradov and big-O notations a(n)\gg b(n) and a(n)=O(b(n)) to indicate that there exist constants N\in\mathbb{N}_{0} and C>0 such that for all n\geq N_{0} , |a(n)|\geq C|b(n)| and |a(n)|\leq C|b(n)| , respectively. Definition (Class \mathscr{C} ) . L et \mathscr{C} denote the family of non-rational hypergeometric sequences whose parameters lie in \mathbb{Q}(\sqrt{\Delta_{1}})\cup\mathbb{Q}(\sqrt{\Delta_{2}})\cup\mathbb{Q}(\sqrt{\Delta_{1}\Delta_{2}}) for some square-free \Delta_{1},\Delta_{2},\Delta_{1}\Delta_{2}\in\mathbb{Z} . Theorem 1 . For hypergeometric sequences \langle u_{n}\rangle_{n=0}^{\infty} in class \mathscr{C} , we have h_{\weil}(u_{n})\gg n . Here the implied constant depends only on \langle u_{n}\rangle_{n=0}^{\infty} . The proof of Theorem 1 is a straightforward corollary of Propositions 7 and 6 in Section 3 . Definition (Class \mathscr{D} ) . L et \mathscr{D} denote the family of non-rational hypergeometric sequences whose parameters \alpha_{1},\ldots,\alpha_{d} and \beta_{1},\ldots,\beta_{d} (the roots of f and g respectively) satisfy the following condition: there is no permutation \sigma\in S_{d} for which \mathbb{Q}(\alpha_{i})=\mathbb{Q}(\beta_{\sigma(i)}) holds for all 1\leq i\leq d . Theorem 2 . Let \langle u_{n}\rangle_{n=0}^{\infty} be a hypergeometric sequence in class \mathscr{D} that, in addition, satisfies either of the following conditions. 1. Each of the irreducible factors of the polynomial fg has degree at most two. 2. The splitting field of fg is cyclotomic. Then h_{\weil}\gg n . Here the implied constant is computable and, further, depends only on fg and a prime p . Theorem 2 follows as a straightforward corollary of Propositions 17 and 18 in Section 4 . A minor contribution in Section 5 is an application of our effective result in Theorem 2 towards decision procedures for the Membership Problem from theoretical computer science ( Corollary 20 ). Approach On the one hand, Theorems 1 and 2 both concern linear growth estimates for the Weil heights of hypergeometric sequences. On the other hand, the approaches taken towards these theorems are fundamentally different. We arrive at the non-effective result in Theorem 1 ( Section 3 ) by way of a lower-bound on the number of large prime divisors that contribute towards the linear growth of the Weil heights. By contrast, the effective results in Theorem 2 ( Section 4 ) follow from observations on the p -adic valuations of certain hypergeometric sequences. More specifically, we prove the existence of a prime p for which the p -adic valuations of such sequences diverge. In fact, the set of primes for which this estimate holds has positive density by Chebotarev’s theorem (see Proposition 15 ); however, for our purposes we need only exhibit one such prime. Related Works The prime divisors of hypergeometric sequences The p -adic techniques herein bear many similarities with the methods employed in previous works on hypergeometric sequences. Researchers have long been interested in developing criteria to establish whether the terms of a hypergeometric sequence are integer valued. Research in this direction includes early work by Landau [ 21 ] , which uses p -adic analysis to establish a necessary and sufficient condition for the integrality in the class of factorial hypergeometric sequences. Authors such as Dwork [ 7 ] and Christol [ 5 ] gave criteria for the p-adic integrality of hypergeometric sequences with rational parameters. Closer to our setting, Hong and Wang [ 16 ] establish a criterion for the integrality of hypergeometric series with parameters from quadratic fields. More recent work, by Franc, Gannon, and Mason [ 11 ] , considers p -adic unboundedness (therein a hypergeometric sequence is p -adically unbounded if arbitrarily high powers of p appear in the denominators of the terms of the sequence). Those authors show that the set of primes where the coefficient sequence of a hypergeometric series {}_{2}F_{1} with rational parameters is unbounded is (essentially) given by a finite union certain arithmetic progressions. The main result in [ 12 ] gave a formulation for the Dirichlet density of the set of p -adically bounded primes for such hypergeometric sequences. Previous works [ 25 , 1 , 20 ] have leveraged techniques concerning prime divisors in order to characterise the asymptotic growth of \nu_{p}(u_{n}) as n\to\infty where \langle u_{n}\rangle_{n=0}^{\infty} is monic hypergeometric sequence. Recall that a hypergeometric sequence \langle u_{n}\rangle_{n=0}^{\infty} is monic if it satisfies a first-order recurrence relation of the form u_{n}=g(n)u_{n-1} . The characterisations for asymptotic growth are given in terms of the number of roots of g in \mathbb{Z}/p\mathbb{Z} , which we obtain from Hensel’s lemma. Our result in Theorem 1 establishes a growth estimate for hypergeometric sequences with quadratic parameters. Our approach relies on machinery developed in the study of roots of quadratic congruences to prime moduli. Groundbreaking work by Duke, Friedlander, and Iwaniec [ 6 ] showed that, in the limit, the normalised roots of a quadratic polynomial