Hostname: page-component-54dcc4c588-br6xx Total loading time: 0 Render date: 2025-10-06T09:38:48.601Z Has data issue: false hasContentIssue false
  • English
  • Français

QUANTITATIVE GROWTH OF LINEAR RECURRENCES

Part of: Geometry of numbers Diophantine approximation, transcendental number theory Sequences and sets Diophantine equations

Published online by Cambridge University Press:  06 October 2025

ARMAND NOUBISSIE
ARMAND NOUBISSIE*
Affiliation:
Graz University of Technology , Institute for Analysis and Number Theory, Münzgrabenstrasse 36/II, 8010 Graz, Austria
*
e-mail: armand.noubissie@tugraz.at
Get access Rights & Permissions [Opens in a new window]

Abstract

Let $\{u_n\}_n$ be a nondegenerate linear recurrence sequence of integers with Binet’s formula given by ${u_n= \sum _{i=1}^{m} P_i(n)\alpha _i^n.}$ Assume $\max _i \vert \alpha _i \vert>1$. In 1977, Loxton and Van der Poorten conjectured that for any $\epsilon>0$, there is an effectively computable constant $C(\epsilon )$ such that if $ \vert u_n \vert < (\max _i\{ \vert \alpha _i \vert \})^{n(1-\epsilon )}$, then $n<C(\epsilon )$. Using results of Schmidt and Evertse, a complete noneffective (qualitative) proof of this conjecture was given by Fuchs and Heintze [‘On the growth of linear recurrences in function fields’, Bull. Aust. Math. Soc. 104(1) (2021), 11–20] and, independently, by Karimov et al. [‘The power of positivity’, Proc. LICS 23 (2023), 1–11]. In this paper, we give an effective upper bound for the number of solutions of the inequality $\vert u_n \vert < (\max _i\{ \vert \alpha _i \vert \})^{n(1-\epsilon )}$, thus extending several earlier results by Schmidt, Schlickewei and Van der Poorten.

Keywords

recurrenceDiophantine equationsgeometry of numbers

MSC classification

Primary: 11B37: Recurrences
Secondary: 11J25: Diophantine inequalities 11H06: Lattices and convex bodies 11D61: Exponential equations

Information

Type
Research Article
Information
Journal of the Australian Mathematical Society , First View , pp. 1 - 34
Check for updates
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

Communicated by Dmitry Badziahin

This research was funded in whole or in part by Austrian Science Fund (FWF): I4406.

References

Bombieri, E. and Gubler, W., Heights in Diophantine Geometry (Cambridge University Press, New York, 2006).Google Scholar
Bombieri, E. and Vaaler, J., ‘On Siegel’s lemma’, Invent. Math. 73 (1983), 11–32.10.1007/BF01393823CrossRefGoogle Scholar
Edixhoven, B. and Evertse, J.-H., Diophantine Approximation and Abelian Varieties, Lecture Notes in Mathematics, 1566 (Springer Verlag, Berlin, 1993).10.1007/978-3-540-48208-6CrossRefGoogle Scholar
Evertse, J.-H., ‘On sums of $S$ -units and linear recurrences’, Compos. Math. 53(2) (1984), 225–244.Google Scholar
Evertse, J.-H., ‘An improvement of the quantitative subspace theorem’, Compos. Math. 101(3) (1996), 225–311.Google Scholar
Fuchs, C. and Heintze, S., ‘On the growth of linear recurrences in function fields’, Bull. Aust. Math. Soc. 104(1) (2021), 11–20.10.1017/S0004972720001094CrossRefGoogle Scholar
Karimov, T., Kelmendi, E., Nieuwveld, J., Ouaknine, J. and Worrell, J., ‘The power of positivity’, Proc. LICS 23 (2023), 1–11.Google Scholar
Loxton, B. H. and Van Poorten, A. J., ‘On the growth of linear recurrences’, Math. Proc. Cambridge Philos. Soc. 81 (1977), 369.10.1017/S0305004100053445CrossRefGoogle Scholar
Luca, F. and Noubissie, A., ‘Linear combinations of factorial and $S$ -unit in a ternary recurrence sequence with a double root’, Period. Math. Hungar. 86 (2023), 422–441.10.1007/s10998-022-00481-7CrossRefGoogle Scholar
Ouaknine, J. and Worrell, J., ‘Ultimate positivity problem is decidable for simple linear recurrence sequences’, in: Proceedings of the ICALP, Lecture Notes in Computer Science LNCS, 8573 (eds. J. Esparza, P. Fraigniaud, T. Husfeldt and E. Koutsoupias) (Springer Verlag, Berlin, 2014).Google Scholar
Schlickewei, H. P. and Schmidt, W. M., ‘The number of solutions of polynomials-exponential equations’, Compos. Math. 120 (2000), 193–225.10.1023/A:1001719425893CrossRefGoogle Scholar
Schlickewei, H. P. and Van der Poorten, A. J., ‘Zeros of linear recurrence sequences’, Bull. Aust. Math. Soc. 44 (1991), 215–223.Google Scholar
Schmidt, W. M., Diophantine Approximation, Lecture Notes in Mathematics, 785 (Springer Verlag, Berlin, 1980).Google Scholar
Schmidt, W. M., ‘The zero multiplicity of linear recurrence sequences’, Acta Math. 182 (1999), 243–282.10.1007/BF02392575CrossRefGoogle Scholar