alphaFeedback

WorksMathematics

Globally periodic rational difference equations of arbitrary order

AI contributions
  • Anthropic Claude Opus 5.5
  • Anthropic Claude Fable 5.1
View details
Ancillary data
Proof registry entry
View

Abstract

A rational difference equation of order kk with nonnegative coefficients is globally periodic if every solution with positive initial data repeats with a common period. Five such equations have long been known, among them the Lyness equation xn+2=(1+xn+1)/xnx_{n+2}=(1+x_{n+1})/x_n, and a problem of Gasull asks whether every globally periodic equation of this kind is obtained from one of the five by rescaling and unfolding. The answer was known to be yes for k∈{1,2,3,4,5,7,9,11}k\in\{1,2,3,4,5,7,9,11\}. Here I show that it is yes at every order. The proof rests on two ideas. The first is a tropical degeneration: global periodicity forces an associated min-plus recursion to be periodic, and this is refuted, for every choice of coefficients at once, by an unbounded solution of the min-plus recursion linearised along a periodic orbit. The second is the σ\sigma-bump, a linearised solution whose existence reduces to a combinatorial condition on residues modulo 2k2k; in the hardest case that condition comes down to a lemma on three-term progressions under unit multipliers modulo 2k2k. The proof, including its finite computations, has been formalised in the Lean proof assistant.

Disclaimer: This manuscript, and the accompanying Lean formalisation of the proof, have been generated by AI. The validity of the proof has been extensively machine-checked, but the proof is not fully understood by the human author.

Introduction

A difference equation is globally periodic if all of its orbits are periodic with a common period. The celebrated example is the Lyness equation

xn+2=1+xn+1xn(1)x_{n+2} = \frac{1+x_{n+1}}{x_n} \tag*{(1)}

every positive solution of which repeats with period 5 [27]. Global periodicity is a fragile property, and equations that have it are rare. In a survey of open problems in low-dimensional dynamics, Gasull [ [12] records five globally periodic rational difference equations with nonnegative coefficients,

xn+1=xn,xn+1=1xn,xn+2=xn+1xn,xn+2=1+xn+1xn,xn+3=1+xn+1+xn+2xn,(2)x_{n+1}=x_n,\qquad x_{n+1}=\frac{1}{x_n},\qquad x_{n+2}=\frac{x_{n+1}}{x_n},\qquad x_{n+2}=\frac{1+x_{n+1}}{x_n},\qquad x_{n+3}=\frac{1+x_{n+1}+x_{n+2}}{x_n}, \tag*{(2)}

of periods 1, 2, 6, 5 and 8 respectively. The 8-cycle of the last was found by H. Todd [22, 28]. New examples can be made from these in two trivial ways: by rescaling, yn=αxny_n=\alpha x_n with α>0\alpha>0, and by unfolding: multiplying every index in an equation of order kk by an integer ℓ≥1\ell\geq1 gives an equation of order ℓk\ell k whose solutions are the interleavings of ℓ\ell solutions of the original one, and which is therefore again globally periodic. Gasull’s Problem 11 asks whether there are any others. More precisely, consider the equations of order k≥1k \ge1,

xn+k=A0+A1xn+A2xn+1+⋯+Akxn+k−1B0+B1xn+B2xn+1+⋯+Bkxn+k−1,(3)x_{n+k}=\frac{A_0+A_1x_n+A_2x_{n+1}+\cdots+A_kx_{n+k-1}}{B_0+B_1x_n+B_2x_{n+1}+\cdots+B_kx_{n+k-1}}, \tag*{(3)}

with Ai,Bi≥0A_i,B_i \ge0, ∑iAi>0\sum_i A_i > 0 and ∑iBi>0\sum_i B_i > 0, acting on positive initial data. (Gasull also assumes A12+B12≠0A_1^2+B_1^2 \ne0, so that the equation genuinely involves xnx_n; I do not need this, because global periodicity forces it, as the first step of the proof shows.) Is every globally periodic equation of the form (3) obtained from one of (2) by rescaling and unfolding?

Here I show that the answer is yes at every order.

Theorem 1.1. Let (3) be globally periodic, that is, suppose there is a p≥1p \ge1 such that every positive solution satisfies xn+p=xnx_{n+p}=x_n. Then, up to multiplying the numerator and denominator by a common positive constant, (3) is one of the following equations, written from the second on with the denominator cleared:

  1. the shift xn+k=xnx_{n+k}=x_n;

  1. xn+kxn=ax_{n+k}x_n=a, with a>0a>0;

  1. k=2mk=2m and xn+2mxn=bxn+mx_{n+2m}x_n=bx_{n+m}, with b>0b>0;

  1. k=2mk=2m and xn+2mxn=b2+bxn+mx_{n+2m}x_n=b^2+bx_{n+m}, with b>0b>0;

  1. k=3mk=3m and xn+3mxn=b2+b(xn+m+xn+2m)x_{n+3m}x_n=b^2+b(x_{n+m}+x_{n+2m}), with b>0b>0.

These are, respectively, the kk-fold unfoldings of the first two equations of (2) and the mm-fold unfoldings of the last three, after rescaling; so every globally periodic equation of the form (3) is equivalent to one of the five equations of (2).

Conversely, each equation in the list is globally periodic, with periods kk, 2k2k, 6m6m, 5m5m and 8m8m respectively, since it is an unfolding of a rescaling of one of (2); so Theorem 1.1 is a complete classification.

The requirement of a common period loses nothing: if every orbit in (0,∞)k(0,\infty)^k is periodic, the state map is a continuous bijection, hence a homeomorphism by invariance of domain, and a pointwise periodic homeomorphism of a connected manifold is periodic [29]; often it can even be linearised globally [7]. (Discontinuous maps can be pointwise periodic without being periodic [9].) This remark is not used in the proof.

The question has a long history. Essentially the same question was asked by Graham et al. [ [14]; the generalisation that Graham had in mind for his Problem 1343 in Mathematics Magazine asks for equations of much the same form [22 Remark 1]. A version of the question is posed by Grove and Ladas [ [15]; at order two it is Conjecture 6.5.6 of Kulenővić and Ladas [ [24]. After partial results of Kocić et al. [ [22], order two was settled by Barbeau et al. [ [1], and Csörnyei and Laczkovich [ [10] settled, even for complex coefficients, orders two and three and the reciprocal equations xn+kxn=c0+∑j=1k−1cjxn+jx_{n+k}x_n=c_0+\sum_{j=1}^{k-1}c_jx_{n+j} in which every cjc_j is nonzero (the full support). Cima et al. [ [6] reduced the problem to a reciprocal family with palindromic coefficients, and showed, using a continuum of 2-periodic points at odd order (Section 6), that the answer is yes for k∈{1,2,3,4,5,7,9,11}k \in\{1,2,3,4,5,7,9,11\}. The general case has remained open. Different approaches to the global periodicity problem are surveyed by Cima et al. [ [8]. Over the complex numbers and with arbitrary coefficients, periodic linear fractional recurrences have been studied from the point of view of birational geometry by Bedford and Kim [ [2, 4] at orders 2 and 3, and Bedford and Kim [ [3] show that for every kk there are such recurrences of order kk and period 4k4k; positivity of the coefficients, which is essential here, plays no role there.

The proof has two quite different halves. The first is analytic and short. A surjectivity argument, followed by a Lyapunov function and the derivative at a fixed point, shows that a globally periodic equation is either the shift or of the reciprocal form

xn+kxn=c0+∑j∈Scjxn+j,c0≥0,cj>0 for j∈S⊂{1,…,k−1},(4)x_{n+k}x_n=c_0+\sum_{j\in S}c_jx_{n+j},\qquad c_0\geq0,\quad c_j>0\ \text{for }j\in S\subset\{1,\ldots,k-1\}, \tag*{(4)}

and linearising at the interior equilibrium shows that the coefficients are palindromic, cj=ck−jc_j=c_{k-j}. Throughout, θ=1\theta=1 if c0>0c_0>0 and θ=0\theta=0 if c0=0c_0=0; most of the arguments treat both values at once. Unfolding then lets me assume that the support SS is primitive, gcd⁡(S∪{k})=1\gcd(S\cup\{k\})=1. When SS has at most two elements, the problem reduces to equations of order at most three, which are settled with the min-plus recursion described below (and, at order three with c0=0c_0=0, with the linearisation), and to a spectral statement about the polynomial λk+1−ϵ(λj+λk−j)\lambda^k+1-\epsilon(\lambda^j+\lambda^{k-j}), which is settled with Kronecker’s theorem on algebraic integers whose conjugates all lie on the unit circle.

The second half, which is most of the paper, deals with supports of three or more elements, and it is combinatorial. The key observation is that global periodicity survives degeneration. If the initial data are taken to be powers δei\delta^{e_i} of a small parameter δ\delta, the exponents of the solution follow a piecewise-linear (min-plus) recursion that depends only on the support and on θ\theta. For the Lyness equation, for example, xn≈δenx_n\approx\delta^{e_n} turns xn+2xn=1+xn+1x_{n+2}x_n=1+x_{n+1} into en+2+en=min⁡(0,en+1)e_{n+2}+e_n=\min(0,e_{n+1}), and every integer solution of this recursion has period 5, just as the solutions of the equation do. In general a globally periodic equation forces its min-plus recursion to be periodic. Because all the coefficients are positive, there is no cancellation: each term of the solution behaves like a positive multiple of a power of δ\delta, and these leading coefficients follow a recursion of their own, which must also be periodic; this is what settles orders two and three when c0>0c_0>0. The passage to a piecewise-linear recursion is the limiting procedure of Tokihiro et al. [ [32], now called ultradiscretisation and familiar from integrable systems [16, 17, 30]; for the full support it was already used by Csörnyei and Laczkovich [ [10]. Tropical versions also appear in the theory of cluster algebras, where Fomin and Zelevinsky [ [11] use them to prove the periodicity of Zamolodchikov’s YY-systems, of which the Lyness equation is the case of type A2A_2; here the information flows the other way, from the equation to its tropical version.

For larger supports, global periodicity of an equation is refuted, for every choice of positive coefficients at once, by exhibiting an unbounded solution of the tangent recursion, the linearisation of the min-plus recursion along a periodic solution. The idea is to perturb a periodic orbit of the min-plus recursion slightly. Only the terms that attain the minimum see the perturbation, so it follows a recursion of the same kind, and if the perturbation can grow without bound, the min-plus recursion, and with it the equation, cannot be periodic. For the supports with at least three elements, the periodic orbits used have, except at order 6, a minimum that is always negative, so that the constant term never attains it, and both values of θ\theta are refuted at once.

I construct the unbounded tangent solutions explicitly, case by case (Table 1). Apart from the full support and most supports at odd order, which have tangent solutions of their own, the workhorse is the σ\sigma-bump: a linearly growing tangent solution supported on two positions in every block of kk, whose existence reduces to a purely combinatorial condition on a set of residues modulo 2k2k (Definition 3.11). The hardest case is even order with every element of SS odd, where the residues are chosen as a half-arc {y:νy mod 2k∈[0,k)}\{y:\nu y\bmod2k\in[0,k)\} for a suitable odd multiplier ν\nu, and what is needed is a lemma about three-term arithmetic progressions under unit multipliers modulo 2k2k, proved with the geometry of numbers in a plane lattice of determinant 2k2k and Jacobsthal’s function.

Several steps finish with a finite computation, for instance at small orders where the general arguments do not yet apply; each is stated precisely in the text and listed in Table 1.

Every finite computation is carried out in exact integer arithmetic, and the whole proof, including these computations, has been formalised and kernel-checked in the Lean proof assistant (Appendix § 14).

As far as I know, the following ingredients are new: the tangent recursion and the two-scale pinning lemma (Lemma 3.5), which turn an unbounded solution of the linearised min-plus recursion into a proof that the equation is not periodic; the use of such tangent solutions to refute global periodicity for every choice of coefficients at once; the σ\sigma-bump and its carriers (the parity, band and half-arc carriers); and the theorem on three-term progressions under unit multipliers (Theorem 9.1). Ultradiscretisation itself is not new, nor is the use of the leading coefficients at orders two and three, which goes back to Csörnyei and Laczkovich [ [10]. I am not aware of an earlier use of the derivative of a min-plus map along a periodic orbit to show that the map is not periodic (“linearised” means something different in the ultradiscrete literature, namely straight-line motion on a tropical Jacobian). A by-product is a purely tropical statement: for every palindromic support with at least three elements, and either θ\theta, no power of the min-plus map is the identity (Corollary 10.1).

Section 2 reduces the problem to primitive palindromic supports of the reciprocal form and Section 3 develops the min-plus machinery and the σ\sigma-bump; Sections 4–9 treat the cases of Table 1, Section 10 puts them together, and the appendices hold the finite range of Theorem 9.1 and the bounds on Jacobsthal’s function, the most mechanical case checks, and a description of the formalisation. A reader who wants only the shape of the argument can read Sections 2 and 3, the statements of the main theorems of the later sections, and Section 10.

Reduction to the reciprocal family

Here I show that a globally periodic equation (3) is the shift or of the reciprocal form (8) with palindromic coefficients, and that it is enough to treat supports with gcd⁡(S∪{k})=1\gcd(S \cup\{k\}) = 1 (Corollary 2.9).

Most of this is known. The reduction to the reciprocal form and palindromy are the Reduction Theorem (Theorem 2.4) of Cima et al. [ [6], and Csörnyei and Laczkovich [ [10] proved ∣cj∣=∣ck−j∣|c_j| = |c_{k-j}| for complex coefficients. I follow the route of Cima, Gasull and Mañosas (preimages of a one-parameter family of states, a Lyapunov function, and the derivative at a fixed point), and give self-contained proofs because the linearisation is needed again in Section 4 and palindromy follows from a short period-sum argument. That the linearisation of a periodic recurrence at a fixed point has finite order goes back to Kurshan and Gopinath [ [25]; it was used by Kocić et al. [ [22], Csörnyei and Laczkovich [ [10] and, with affine normal forms at order two, Rubió-Massagué and Mañosa [2007].

The state map

References

  1. [1]E. J. Barbeau, Boaz Gelbord, and Stephen Tanny. Periodicities of solutions of the generalized Lyness recursion. Journal of Difference Equations and Applications, 1(3):291–306, 1995. doi: 10.1080/10236199508808028.DOI
  2. [2]Eric Bedford and Kyounghee Kim. Periodicities in linear fractional recurrences: degree growth of birational surface maps. Michigan Mathematical Journal, 54(3):647–670, 2006. doi: 10.1307/mmj/1163789919.DOI
  3. [3]Eric Bedford and Kyounghee Kim. Linear fractional recurrences: periodicities and integrability. Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série 6, 20(S2):33–56, 2011. doi: 10.5802/afst.1304.DOI
  4. [4]Eric Bedford and Kyounghee Kim. Dynamics of (pseudo) automorphisms of 3-space: periodicity versus positive entropy. Publicacions Matemàtiques, 58:65–119, 2014. doi: 10.5565/publmat_58114_04.DOI
  5. [5]Enrico Bombieri and Walter Gubler. Heights in Diophantine Geometry, volume 4 of New Mathematical Monographs. Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511542879.
  6. [6]Anna Cima, Armengol Gasull, and Francesc Mañosas. On periodic rational difference equations of order k. Journal of Difference Equations and Applications, 10(6):549–559, 2004. doi: 10.1080/10236190410001667977.DOI
  7. [7]Anna Cima, Armengol Gasull, and Francesc Mañosas. Global linearization of periodic difference equations. Discrete and Continuous Dynamical Systems, 32(5):1575–1595, 2012. doi: 10.3934/dcds.2012.32.1575.DOI
  8. [8]Anna Cima, Armengol Gasull, Víctor Mañosa, and Francesc Mañosas. Different approaches to the global periodicity problem. In Difference Equations, Discrete Dynamical Systems and Applications, volume 180 of Springer Proceedings in Mathematics & Statistics, pages 85–106. Springer, 2016. doi: 10.1007/978-3-662-52927-0_7.DOI
  9. [9]Anna Cima, Armengol Gasull, Víctor Mañosa, and Francesc Mañosas. Pointwise periodic maps with quantized first integrals. Communications in Nonlinear Science and Numerical Simulation, 108:106150, 2022. doi: 10.1016/j.cnsns.2021.106150.DOI
  10. [10]Marianna Csörnyei and Miklós Laczkovich. Some periodic and non-periodic recursions. Monatshefte für Mathematik, 132(3):215–236, 2001. doi: 10.1007/s006050170042.DOI
  11. [11]Sergey Fomin and Andrei Zelevinsky. Y-systems and generalized associahedra. Annals of Mathematics, 158(3):977–1018, 2003. doi: 10.4007/annals.2003.158.977.DOI
  12. [12]Armengol Gasull. Some open problems in low dimensional dynamical systems. SeMA Journal, 78:233–269, 2021. doi: 10.1007/s40324-021-00244-3. arXiv:2012.02524.DOI
  13. [13]Michael Golomb and David Callan. Periodic recursive sequences: Problem E3437 and solution. The American Mathematical Monthly, 99(9):882–883, 1992. doi: 10.2307/2324138.
  14. [14]Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Reading, MA, 1989.
  15. [15]E. A. Grove and G. Ladas. Periodicities in Nonlinear Difference Equations, volume 4 of Advances in Discrete Mathematics and Applications. Chapman & Hall/CRC, Boca Raton, FL, 2005. doi: 10.1201/9781420037722.DOI
  16. [16]Rei Inoue and Tomoyuki Takenawa. Tropical spectral curves and integrable cellular automata. International Mathematics Research Notices, 2008:rnn019, 2008. doi: 10.1093/imrn/rnn019.DOI
  17. [17]Rei Inoue, Atsuo Kuniba, and Taichiro Takagi. Integrable structure of box-ball systems: crystal, Bethe ansatz, ultradiscretization and tropical geometry. Journal of Physics A: Mathematical and Theoretical, 45:073001, 2012. doi: 10.1088/1751-8113/45/7/073001.DOI
  18. [18]Henryk Iwaniec. On the problem of Jacobsthal. Demonstratio Mathematica, 11(1):225–231, 1978. doi: 10.1515/dema-1978-0121.DOI
  19. [19]Ernst Jacobsthal. Über Sequenzen ganzer Zahlen, von denen keine zu n teilerfremd ist. I. Det Kongelige Norske Videnskabers Selskabs Forhandlinger (Trondheim), 33:117–124, 1960a.
  20. [22]V. L. Kocić, G. Ladas, and I. W. Rodrigues. On rational recursive sequences. Journal of Mathematical Analysis and Applications, 173:127–157, 1993. doi: 10.1006/jmaa.1993.1057.DOI
  21. [23]Leopold Kronecker. Zwei Sätze über Gleichungen mit ganzzahligen Coefficienten. Journal für die reine und angewandte Mathematik, 53:173–175, 1857. doi: 10.1515/crll.1857.53.173.DOI
  22. [24]M. R. S. Kulenović and G. Ladas. Open problems and conjectures: On period two solutions of xₙ₊₁ = (α+βxₙ+γxₙ₋₁)/(a+bxₙ+cxₙ₋₁). Journal of Difference Equations and Applications, 6(5):641–646, 2000. doi: 10.1080/10236190008808249.DOI
  23. [25]R. P. Kurshan and B. Gopinath. Recursively generated periodic sequences. Canadian Journal of Mathematics, 26(6):1356–1371, 1974. doi: 10.4153/CJM-1974-129-6.DOI
  24. [26]Antonio Linero Bas and Daniel Nieves Roldán. Periods of a max-type equation. Journal of Difference Equations and Applications, 27(11):1608–1645, 2021. doi: 10.1080/10236198.2021.2000971.
  25. [27]R. C. Lyness. Cycles. The Mathematical Gazette, 26(268):62, 1942. doi: 10.2307/3606036. Note 1581.
  26. [28]R. C. Lyness. Cycles. The Mathematical Gazette, 29(287):231–233, 1945. doi: 10.2307/3609268. Note 1847.
  27. [29]Deane Montgomery. Pointwise periodic homeomorphisms. American Journal of Mathematics, 59(1):118–120, 1937. doi: 10.2307/2371565.DOI
  28. [30]Atsushi Nobe. Ultradiscrete QRT maps and tropical elliptic curves. Journal of Physics A: Mathematical and Theoretical, 41:125205, 2008. doi: 10.1088/1751-8113/41/12/125205.DOI
  29. [32]Tetsuji Tokihiro, Daisuke Takahashi, Junta Matsukidaira, and Junkichi Satsuma. From soliton equations to integrable cellular automata through a limiting procedure. Physical Review Letters, 76:3247–3250, 1996. doi: 10.1103/physrevlett.76.3247.DOI

Paper details

vlnc:W_4jdvrwpc
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Mathematics

Anthropic Claude Opus 5.5, Anthropic Claude Fable 5.1 · View statement →

Looking for related papers…
Contents