WorksPhysics and Astronomy
On a certain system of discrete equations with the Laurent property
Abstract
We consider a system of two bilinear discrete equations with four parameters. It defines a certain discrete dynamical system. Each of its solutions is represented as a pair of sequences. It is proved that for arbitrary initial data all terms of both sequences are Laurent polynomials in the initial data with integer coefficients. This property is called the Laurent property. The proof relies on an established connection between the system and the Somos-5 equation. It is shown that both components of the solution satisfy the same equation with the same parameters. To prove the main theorem, the strong Laurent property for the Somos-5 equation is used, which makes it possible to control negative powers of the initial data. An analogue of this property is obtained directly for the system under study. As corollaries, sufficient conditions for the integrality of solutions are found. An example of a pair of integer sequences illustrating the theorem on the strong Laurent property is given.
Introduction
Recently, quite a lot of research has been devoted to polynomial recurrence relations which, under certain conditions, can generate integer sequences [4, 8, 12]. Interest in them is explained by a wide range of applications in algebraic combinatorics, number theory, cryptography and theoretical physics. A characteristic property of such equations is the Laurent property [6, 7]: each term of the generated sequence is expressed as a Laurent polynomial in the initial data with integer coefficients.
Many examples of equations with the Laurent property of the form , where is a polynomial in the indicated variables, are known in the literature, however, of direct interest to us is the bilinear equation
Here it is assumed that is a pair of arbitrary parameters. Relation (0.1) is known in the literature as the Somos-5 equation.
In this paper we consider a system of two bilinear discrete equations
where are arbitrary parameters, and is a pair of sought sequences. Any solution of this system is determined by the initial data and the choice of parameter values.
Remark 0.1. The use of the same notation for the sought sequence both in (0.1) and in (0.2) is not accidental. We do this for convenience, since in the next section it will be shown that any solution of system (0.2) generates a pair of solutions of the Somos-5 equation, defined as relation (0.1), with suitable values of the parameters depending on the data
Definition 0.2. A solution of system (0.2) will be called non-singular if and for all .
Interest in system (0.2) is explained by the fact that, as we will show below, under certain conditions it generates a pair of integer sequences.
Remark 0.3. Systems of bilinear recurrence relations of the form (0.2) were considered earlier [1, 2]. In particular, in [2] a system of equations similar to ours was studied
For it, the Laurent property was proved and a general solution was constructed in terms of the Weierstrass function.
Theorem 0.4. Let be a non-singular solution of system (0.2). Then for all
In other words, each term of the sequences and is a Laurent polynomial in the initial data with coefficients from . In this case we say that the system possesses the Laurent property with respect to the initial data.
Practically, the meaning of this theorem is that it gives a sufficient criterion for constructing integer sequences. Indeed, let for . Then by virtue of Theorem 0.4 under this condition we obtain . If we now choose some integer values for the parameters , then . Note that the condition given above is sufficient but not necessary. Integer sequences can also arise for other initial data and parameters.
As for the Somos-5 equation, the following well-known statement can be formulated for it.
Theorem 0.5. By virtue of (0.1) the following holds:
As we have already said, system (0.2) generates two sequences satisfying the same Somos-5 equation. Therefore Theorem 0.4 could in principle be a consequence of Theorem 0.5. This is indeed so, however it turns out that precisely in such a formulation Theorem 0.5 cannot be directly applied due to certain technical difficulties. To prove Theorem 0.4, we will apply the so-called strong Laurent property for the Somos-5 equation formulated in [10].
Remark 0.6. Theorem 0.5 was first proved in the work of Fomin and Zelevinsky [7]. More precisely, the Laurent property was proved for an infinite family of recurrence relations of the form
known in the literature as Gale–Robinson equations [8]. Here and . The proof was based on an essential connection of these relations with the theory of cluster algebras.
The article is organized as follows. In the next section we prove a theorem stating that each of the components of the solution of system (2) satisfies the Somos-5 equation with the same pair of parameters . This fact underlies the proof of the main theorem on the Laurent property. The proof of Theorem 0.4 essentially relies on the theorem on the strong Laurent property for the Somos-5 equation. We formulate and discuss this theorem in Section 3. Section 4 is devoted to the proof of Theorem 0.4. In Section 5 we prove a theorem on the strong Laurent property for the system (2) under study. This theorem can be used to construct integer sequences when . In Section 6 an example of such a sequence is given. Section 7 is devoted to concluding remarks and discussion of possible practical applications of the sequences generated by the system of discrete equations studied in the article.
Connection of the studied system of discrete equations with the Somos-5 equation
In this section we present auxiliary lemmas establishing the connection of system (2) with the Somos-5 equation, and formulate the corresponding theorem.
Let a non-singular solution of system (2) be given, determined by some set of data. Define the sequences
Lemma 1.1. By virtue of system (2) and (5) the pair of relations holds
Proof. The proof is carried out by direct verification.
Remark 1.2. By virtue of (5) the following holds:
In other words, this system can be reduced to an equation with respect to one function or . If we consider this system as an independent object, we can notice that $p_n=v_nu_n-offsetof is a 2-invariant of this system. That is, the relation holds. This is consistent with condition (1.3), considered as a special case for this 2-invariant.
Remark 1.3. It should be noted that the conditions or , under which indeterminacies appear in system (1.2), cannot hold for a non-singular solution of system (0.2). In other words, by requiring and , we exclude these indeterminacies in system (1.2).
Lemma 1.4. System (1.2) with condition (1.3) admits the invariant
Proof. Denote the left-hand side of (1.4) by . Then
Substituting and , by virtue of system (1.2), into the last relation, we obtain . The lemma is proved. □
Note that the recurrence relation for the sequence can be written in the form
where . The function defines a fractional-linear (Möbius) transformation with coefficient matrix
As a result, we obtain a dynamical system which is the result of an infinite number of iterations of a birational map of recurrence type:
The inverse map, as is easy to verify, is defined as
Note that the inverse matrix does not participate here and therefore equation (1.5) is defined also for a degenerate matrix.
Lemma 1.5. System of equations (0.2) admits the invariant
where is an arbitrary non-singular solution.
Define
Lemma 1.6. By virtue of (6) and (12), the sequences and satisfy the recurrence relations
with parameters
where is the invariant of equation (9), determined by expression (8).
As we can see, the parameter is expressed as the determinant of the coefficient matrix (10). The parameter , unlike , depends on the initial data of the solution.
Lemma 1.7. For an arbitrary non-singular solution of system (2) the following relations hold
Proof. These relations are proved by direct verification. In doing so, one needs to use the equations of system (2) to express and , the substitutions (5) and (12). □
As a result of this section, we obtain the main statement of this section — a theorem following from Lemma 1.6 and Lemma 1.7.
Theorem 1.8. By virtue of system (2) the sequences and satisfy the Somos-5 equation with the same parameters , , determined by formulas (14). The quantity , given by formula (11), is an invariant of system (2).
Proof. The proof consists of direct verification. Substituting the expressions (15) for and into equations (13), written for each of these sequences, we obtain the required result. □
Remark 1.9. It is well known (see, for example, [10]) that equation (13) together with the substitution (15) leads to the Somos-5 equation. However, in the present paper the substitutions (15) for and arise in a non-trivial way as a consequence of system (2) (see Lemma 1.7), and are not postulated in advance.
Connection between the invariants of the studied system and the Somos-5 equation
It is known that the Somos-5 equation (1) admits the invariant [10]
The analogous expression for the invariant is obtained by replacing with . Note that by virtue of the first substitution in (15) the expression for is rewritten as
Similarly, by virtue of the second substitution in (15), we obtain
The following lemma can be regarded as a supplement to Theorem 1.8.
Lemma 2.1. For any non-singular solution of system (0.2), the value of the invariant , determined by (8), coincides with the value of ().
Proof. We use the first relation in (13) to eliminate in (17). Then we use the first substitution in (12) and express by virtue of (14). As a result, we obtain
Here one needs to eliminate and , by virtue of the equation and verify that indeed , where is determined by formula (8). The calculations, although cumbersome, are algorithmic. For the reasoning is completely analogous with replaced by . Hence, in particular, we obtain that .
:::
Thus, the sequences and , which by virtue of Theorem 1.8 satisfy the same Somos-5 equation, have the same value of the invariant.
Remark 2.2. Note that according to Theorem 1.8 on the connection of the studied system with the Somos-5 equation and the work of Hone [9], the general solution of the studied system (0.2) must be expressed through the -function of Weierstrass associated with some elliptic curve and its Jacobian. Formulas (14) uniquely determine from the data (0.3) of the studied system the coefficients of the corresponding Somos-5 equation. The Lemma 2.1 proved in this section says that the invariant (2.1) of the Somos-5 equation can be replaced by the invariant (1.7) (for ). By the formulas of Theorem 2.7 of [9] the equation of the elliptic curve is determined. The condition (non-vanishing of the discriminant of the curve) guarantees the non-singularity of this elliptic curve and, thereby, the correctness of the associated non-degenerate period lattice and the function . In fact, one needs to understand how the constants appearing in the formulas for these solutions must be related. A complete study of these questions is beyond the scope of this article.
Strong Laurent property of the Somos-5 equation
In principle, the idea of proving Theorem 0.4 on the Laurent property for system (2) is as follows. First we use Theorem 1.8, according to which each of the sequences and satisfies the Somos-5 equation. Then we apply the Laurent property to this equation (Theorem 0.5) and transfer it to the original system. However, such a course of action encounters technical difficulties.
It turns out that to prove Theorem 0.4 it is more convenient (and, essentially, necessary) to use the so-called strong Laurent property for the Somos-5 equation, which is formulated with the help of the following theorem proved in [10]. For convenience we formulate this theorem in our notation.
Here is expressed by (16). Recall that this is an invariant of the Somos-5 equation. Therefore is also an invariant. In the next section, for convenience, we will use the short notation .
To illustrate this theorem we show three Laurent polynomials generated by the Somos-5 equation:
Remark 3.2. In reality Theorem 3.1 does not strengthen Theorem 0.5, but rather refines it. It says that negative powers in in all iterations can be accounted for by a polynomial dependence on the indicated invariant of the Somos-5 equation.
Remark 3.3. It is important for us that Theorem 3.1 is also valid for . This fact can be obtained if we apply this theorem to the reversed sequence . In other words, one needs to use the symmetry of the Somos-5 equation. Therefore the given formulation of the theorem actually covers all .
Remark 3.4. Theorem 3.1 is a strong statement, but it does not lead to an algorithm for constructing integer sequences generated by Somos-5. Indeed, setting and , we cannot be sure that the value of the invariant is integer. Note that, by virtue of the definition of , here in fact we need the integrality of the product .
Let us explain why it is necessary to use Theorem 3.1 to prove the main theorem. Recall that Theorem 0.5 states that by virtue of the Somos-5 equation . Take an arbitrary polynomial . Suppose that and are iterations by virtue of system (0.2). Let us write out the expressions for these iterations explicitly:
The problem is that negative powers of these iterations do not belong to the ring , but are general rational functions. Therefore the polynomial , upon substitution of negative powers of and , does not transform into an element of the ring . On the other hand, polynomials belonging to the ring do not contain and in negative powers.
Proof of Theorem 0.4
Recall that this theorem states that all iterations generated by system (0.2) belong to the ring . For the iterations and , determined by the expressions in (3.3), this is obvious. By virtue of Lemma 2.1, we can make the replacement or, in other words, the invariant of the Somos-5 equation can be replaced by the invariant of system (0.2). Taking this replacement into account, we obtain: , and . Moreover , since
Substituting into an arbitrary Laurent polynomial , we obtain a mapping . In particular, since any iteration generated by the Somos-5 equation belongs to , then, taking these substitutions into account, it will belong to the ring . Similarly, by virtue of the symmetry of system (0.2), we obtain . Thus, Theorem 0.4 is completely proved.
Analogue of Theorem 3.1 for the studied system
It turns out that, using Theorem 3.1, one can prove an analogous theorem for the studied system (0.2).
Theorem 5.1. By virtue of the system of equations (0.2):
,
where and .
Proof. Recall that by Theorem 3.1, by virtue of the Somos-5 equation, we have , for all , where . Here and are the parameters of the Somos-5 equation; is the invariant of this equation.
Again suppose that and are iterations by virtue of system (0.2). Recall that in this case, by virtue of Lemma 2.1, we can make the replacement , where is the invariant of this system, determined by (4.1). Note that and , determined by (21), belong to . Obviously, , We use Lemma 2.1, which gives us the right to make the replacement and correspondingly . In this case we obtain the following:
and
Thus a mapping is defined, where is the ring of Laurent polynomials in Theorem 3.1. The theorem is proved. □
Remark 5.2. Note that, just as in the case of Theorem 3.1, this theorem essentially does not strengthen the ordinary Laurent property, but only refines it. Speaking informally, all negative powers in the variables and are ”hidden” here in the expressions for and .
Remark 5.3. As we have already said, Theorem 3.1 does not lead to an algorithm for constructing integer sequences for the Somos-5 equation. The same can be said about Theorem 5.1. It gives a sufficient criterion for integrality, but does not lead to an algorithm, since by choosing the conditions for and we cannot be sure that and , under these conditions, simultaneously take integer values. Nevertheless, one can find such an example.
Example of a pair of integer sequences
Consider an example illustrating Theorem 5.1. Let and . Since , Theorem 0.4 in this case does not guarantee the integrality of the sequences and . This requires an additional condition, which is given by Theorem 5.1. Note that although is fractional, the quantities and are integer. Under these conditions Theorem 5.1 guarantees the integrality of these sequences. Moreover, since we have taken all data positive and non-zero, this guarantees the non-singularity of and .
In the following table the first nine terms of these sequences are shown.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | 1 | 2 | 11 | 164 | 4210 | 274828 | 51 195 896 | 19 837 002 616 | |
| 1 | 1 | 3 | 16 | 194 | 6892 | 559 512 | 80 551 288 | 34 641 433 216 |
Table 1.
Let us look at this example to see what the greatest common divisors of the numbers and are. Denote . The first nine terms of this sequence are as follows:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | 1 | 1 | 1 | 2 | 2 | 4 | 8 | 8 |
Table 2.
Numerical computations for this example allow us to conjecture that , where is a non-decreasing sequence of non-negative integers. Note that in this case . In other words, within the computations performed the common divisors of and always turn out to be powers of two — one of the prime divisors of the determinant of the coefficient matrix.
Conclusion
The main results of the article are three theorems. Theorem 1.8 establishes that system (2) generates two sequences and , each of which satisfies the same Somos-5 equation with coefficients and , determined from the data of the system by formulas (14). Relying on Theorem 3.1 on the strong Laurent property for the Somos-5 equation and Theorem 1.8, we proved the main Theorem 0.4 on the Laurent property for system (2). Finally, Theorem 5.1 gives an analogue of the strong Laurent property for system (2).
One can pose the following inverse problem. Let some solution of the Somos-5 equation with fixed coefficients and be given. It is required to find a solution of the same Somos-5 equation such that the pair is a solution of system (2) with some coefficients.
Note that formally such a solution always exists. Indeed, take . It is easy to verify that is a solution of system (2) with , , , . However, it is not interesting and we fundamentally do not consider it as a solution. The search for non-trivial solutions of this inverse problem leads to a system of polynomial equations with respect to the data of system (2). As computations show, a non-trivial solution may not exist, and if it exists, it may not be unique.
Let us turn to the question of the potential possibilities of practical application of the sequences (not necessarily integer) generated by system (2). First of all, note that this system is quite simple in construction and therefore may be attractive from a practical point of view. Since both components of the solution satisfy the Somos-5 equation, it is natural to start with applications of the sequences generated by this equation, although it is worth noting that there exists a whole class of bilinear (quadratic) recurrence relations with similar properties. As an example, one can take the Gale–Robinson equations mentioned above.
Let us list some specific features that are interesting from the point of view of application in cryptography.
The sequences generated by the Somos-5 equation are closely related to elliptic curves [10] — mathematical objects on which modern cryptography is based. This allows one to construct cryptographic algorithms similar to existing ones, but relying on the properties of Somos sequences [3]. The second feature is the finiteness of the rank of the sequences generated by the recurrence relations given in the article (see, for example, [4, 5]). Note that among the bilinear equations given there are both equations for which the finiteness of rank is proved (for example, Somos-5) and equations for which this question remains open. For sequences of finite rank a multitude of identities holds, allowing one to compute iterations rapidly for large .
The third feature is special arithmetic properties. The study of the arithmetic properties of integer sequences generated by Somos-5 was initiated in [13] and then continued, for example, in [5, 11].
Apparently, pairs of non-singular integer sequences generated by system (0.2) possess specific arithmetic properties that may find application. However, their study is beyond the scope of this article.
Acknowledgements
This work was carried out within the framework of the state assignment of the Ministry of Education and Science of the Russian Federation on the project No. 126021217175-3.
Email address: [email protected]
Matrosov Institute for System Dynamics and Control Theory, Siberian Branch of Russian Academy of Sciences, PO Box 292, 664033 Irkutsk, Russia
References
- [1]Avdeeva M.O., Bykovskii V.A. Hyperelliptic system of sequences and functions // Far Eastern Math. J. 2016. Vol. 16, No. 2. P. 115–122
- [2]Bykovskii V. A., Ustinov A. V. Somos-4 and elliptic systems of sequences // Doklady Mathematics. 2016. Vol. 94, No. 3. P. 611–614. https://doi.org/10.1134/S1064562416060016
- [3]Illarionov A. A. Asymmetric cryptography and hyperelliptic sequences // Far Eastern Math. J. 2019. Vol. 19, No. 2. P. 185–196. https://doi.org/10.47910/FEMJ2019.2.185-196
- [4]Ustinov A. V. An elementary approach to the study of Somos sequences // Proc. Steklov Inst. Math. 2019. Vol. 305. P. 305–317. https://doi.org/10.1134/S0081543819060183
- [5]Ustinov A. V. On periodicity of the Somos sequences modulo m // Math. Notes. 2024. Vol. 115, N. 3. P. 405–413. https://doi.org/10.1134/S000143462403012X
- [6]Alman J., Cuenca C., Huang J. Laurent phenomenon sequences // J. Alg. Comb. 2020. Vol. 52, N. 3. P. 345–377. https://doi.org/10.1007/s10801-019-00903-9
- [7]Fomin S., Zelevinsky A. The Laurent phenomenon // Adv. Appl. Math. 2002. Vol. 28, N. 2. P. 119–144. https://doi.org/10.1006/aama.2001.0770
- [8]Gale D. The strange and surprising saga of the Somos sequences // The Mathematical Intelligencer. 1991. Vol. 13, N. 1. P. 40–42. https://doi.org/10.1007/BF03024070
- [9]Hone A. N. W. Sigma function solution of the initial value problem for Somos 5 sequences // Trans. AMS. 2007. Vol. 359, N. 10. P. 5019–5034. https://doi.org/10.1090/S0002-9947-07-04215-8
- [10]Hone A. N. W., Swart C. Integrality and the Laurent phenomenon for Somos 4 and Somos 5 sequences // Math. Proc. Camb. Phil. Soc. 2008. Vol. 145, N. 1. P. 65–85. https://doi.org/10.1017/S030500410800114X
- [11]van der Kamp P. H. Somos-4 and Somos-5 are arithmetic divisibility sequences // J. Difference Equ. Appl. 2016. Vol. 22, N. 4. P. 571–581. https://doi.org/10.1080/10236198.2015.1113272
- [12]Malouf J. L. An integer sequence from a rational recursion // Disc. Math. 1992. Vol. 110, N. 1–3. P. 257–261. https://doi.org/10.1016/0012-365X(92)90217-3
- [13]Robinson R. M. Periodicity of Somos sequences // Proc. Amer. Math. Soc. 1992. Vol. 116, N. 3. P. 613–619. https://doi.org/10.1090/S0002-9939-1992-1097344-3