Somos sequence

Last updated December 18, 2023

In mathematics, a Somos sequence is a sequence of numbers defined by a certain recurrence relation, described below. They were discovered by mathematician Michael Somos. From the form of their defining recurrence (which involves division), one would expect the terms of the sequence to be fractions, but nevertheless many Somos sequences have the property that all of their members are integers.

Recurrence equations

For an integer number k larger than 1, the Somos-k sequence $(a_{0},a_{1},a_{2},\ldots )$ is defined by the equation

a_{n}a_{n-k}=a_{n-1}a_{n-k+1}+a_{n-2}a_{n-k+2}+\cdots +a_{n-(k-1)/2}a_{n-(k+1)/2}

when k is odd, or by the analogous equation

a_{n}a_{n-k}=a_{n-1}a_{n-k+1}+a_{n-2}a_{n-k+2}+\cdots +(a_{n-k/2})^{2}

when k is even, together with the initial values

a_i = 1 for i < k.

For k = 2 or 3, these recursions are very simple (there is no addition on the right-hand side) and they define the all-ones sequence (1, 1, 1, 1, 1, 1, ...). In the first nontrivial case, k = 4, the defining equation is

a_{n}a_{n-4}=a_{n-1}a_{n-3}+a_{n-2}^{2}

while for k = 5 the equation is

a_{n}a_{n-5}=a_{n-1}a_{n-4}+a_{n-2}a_{n-3}\,.

These equations can be rearranged into the form of a recurrence relation, in which the value a_n on the left hand side of the recurrence is defined by a formula on the right hand side, by dividing the formula by a_n − k. For k = 4, this yields the recurrence

a_{n}={\frac {a_{n-1}a_{n-3}+a_{n-2}^{2}}{a_{n-4}}}

while for k = 5 it gives the recurrence

a_{n}={\frac {a_{n-1}a_{n-4}+a_{n-2}a_{n-3}}{a_{n-5}}}.

While in the usual definition of the Somos sequences, the values of a_i for i < k are all set equal to 1, it is also possible to define other sequences by using the same recurrences with different initial values.

Sequence values

The values in the Somos-4 sequence are

1, 1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898, ... (sequence A006720 in the OEIS ).

The values in the Somos-5 sequence are

1, 1, 1, 1, 1, 2, 3, 5, 11, 37, 83, 274, 1217, 6161, 22833, 165713, ... (sequence A006721 in the OEIS ).

The values in the Somos-6 sequence are

1, 1, 1, 1, 1, 1, 3, 5, 9, 23, 75, 421, 1103, 5047, 41783, 281527, ... (sequence A006722 in the OEIS ).

The values in the Somos-7 sequence are

1, 1, 1, 1, 1, 1, 1, 3, 5, 9, 17, 41, 137, 769, 1925, 7203, 34081, ... (sequence A006723 in the OEIS ).

The first 17 values in the Somos-8 sequence are

1, 1, 1, 1, 1, 1, 1, 1, 4, 7, 13, 25, 61, 187, 775, 5827, 14815 [the next value is fractional].^{[ citation needed ]}

Integrality

The form of the recurrences describing the Somos sequences involves divisions, making it appear likely that the sequences defined by these recurrence will contain fractional values. Nevertheless, for k ≤ 7 the Somos sequences contain only integer values.^[1]^[2]^[3] Several mathematicians have studied the problem of proving and explaining this integer property of the Somos sequences; it is closely related to the combinatorics of cluster algebras.^[4]^[2]^[5]^[6]

For k ≥ 8 the analogously defined sequences eventually contain fractional values. For Somos-8 the first fractional value is the 18th term with value 420514/7.

For k < 7, changing the initial values (but using the same recurrence relation) also typically results in fractional values.

Related Research Articles

In mathematics, the Bernoulli numbers $B n$ are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

In mathematics, the factorial of a non-negative integer $,$ denoted by $,$ is the product of all positive integers less than or equal to $.$ The factorial of also equals the product of $with the next smaller factorial:$

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members. The number of elements is called the length of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers to the elements at each position. The notion of a sequence can be generalized to an indexed family, defined as a function from an arbitrary index set.

In mathematics, a recurrence relation is an equation according to which the $th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.$

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

In mathematics, the double factorial of a number $n$ , denoted by $n ‼$ , is the product of all the positive integers up to $n$ that have the same parity as $n$ . That is,

In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is efficiently computable is known. A number of constraints are known, showing what such a "formula" can and cannot be.

Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.

<span class="mw-page-title-main">Znám's problem</span> On divisibility among sets of integers

In number theory, Znám's problem asks which sets of integers have the property that each integer in the set is a proper divisor of the product of the other integers in the set, plus 1. Znám's problem is named after the Slovak mathematician Štefan Znám, who suggested it in 1972, although other mathematicians had considered similar problems around the same time.

In number theory, the Padovan sequence is the sequence of integers P(n) defined by the initial values

In mathematics, Somos' quadratic recurrence constant, named after Michael Somos, is the number

<span class="mw-page-title-main">Sylvester's sequence</span> Doubly exponential integer sequence

In number theory, Sylvester's sequence is an integer sequence in which each term is the product of the previous terms, plus one. The first few terms of the sequence are

In mathematics, the Jacobsthal numbers are an integer sequence named after the German mathematician Ernst Jacobsthal. Like the related Fibonacci numbers, they are a specific type of Lucas sequence $for which P = 1, and Q = -2—and are defined by a similar recurrence relation: in simple terms, the sequence starts with 0 and 1, then each following number is found by adding the number before it to twice the number before that. The first Jacobsthal numbers are:$

In mathematics, the Schröder number $also called a large Schröder number or big Schröder number, describes the number of lattice paths from the southwest corner of an grid to the northeast corner using only single steps north, northeast, or east, that do not rise above the SW-NE diagonal.$

In mathematics, an elliptic divisibility sequence (EDS) is a sequence of integers satisfying a nonlinear recursion relation arising from division polynomials on elliptic curves. EDS were first defined, and their arithmetic properties studied, by Morgan Ward in the 1940s. They attracted only sporadic attention until around 2000, when EDS were taken up as a class of nonlinear recurrences that are more amenable to analysis than most such sequences. This tractability is due primarily to the close connection between EDS and elliptic curves. In addition to the intrinsic interest that EDS have within number theory, EDS have applications to other areas of mathematics including logic and cryptography.

In mathematics, the pentagram map is a discrete dynamical system on the moduli space of polygons in the projective plane. The pentagram map takes a given polygon, finds the intersections of the shortest diagonals of the polygon, and constructs a new polygon from these intersections. Richard Schwartz introduced the pentagram map for a general polygon in a 1992 paper though it seems that the special case, in which the map is defined for pentagons only, goes back to an 1871 paper of Alfred Clebsch and a 1945 paper of Theodore Motzkin. The pentagram map is similar in spirit to the constructions underlying Desargues' theorem and Poncelet's porism. It echoes the rationale and construction underlying a conjecture of Branko Grünbaum concerning the diagonals of a polygon.

In mathematics, the telephone numbers or the involution numbers form a sequence of integers that count the ways $n$ people can be connected by person-to-person telephone calls. These numbers also describe the number of matchings of a complete graph on $n$ vertices, the number of permutations on $n$ elements that are involutions, the sum of absolute values of coefficients of the Hermite polynomials, the number of standard Young tableaux with $n$ cells, and the sum of the degrees of the irreducible representations of the symmetric group. Involution numbers were first studied in 1800 by Heinrich August Rothe, who gave a recurrence equation by which they may be calculated, giving the values

In mathematics, the Wythoff array is an infinite matrix of integers derived from the Fibonacci sequence and named after Dutch mathematician Willem Abraham Wythoff. Every positive integer occurs exactly once in the array, and every integer sequence defined by the Fibonacci recurrence can be derived by shifting a row of the array.

<span class="mw-page-title-main">Constant-recursive sequence</span> Infinite sequence of numbers satisfying a linear equation

In mathematics and theoretical computer science, a constant-recursive sequence is an infinite sequence of numbers in which each number in the sequence is equal to a fixed linear combination of one or more of its immediate predecessors. The concept is variously known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, a C-finite sequence, or a solution to a linear recurrence with constant coefficients.

In mathematics, a Göbel sequence is a sequence of rational numbers defined by the recurrence relation

References

↑ Malouf, Janice L. (1992), "An integer sequence from a rational recursion", Discrete Mathematics , 110 (1–3): 257–261, doi: 10.1016/0012-365X(92)90714-Q .
1 2 Carroll, Gabriel D.; Speyer, David E. (2004), "The Cube Recurrence", Electronic Journal of Combinatorics , 11: R73, arXiv: math.CO/0403417 , doi:10.37236/1826, S2CID 1446749 .
↑ "A Bare-Bones Chronology of Somos Sequences". faculty.uml.edu. Retrieved 2023-11-27.
↑ Fomin, Sergey; Zelevinsky, Andrei (2002), "The Laurent phenomenon", Advances in Applied Mathematics , 28 (2): 119–144, arXiv: math.CO/0104241 , doi:10.1006/aama.2001.0770, S2CID 119157629 .
↑ Hone, Andrew N. W. (2021). "Casting light on shadow Somos sequences". arXiv: 2111.10905 [math.CO].
↑ Stone, Alex (18 November 2023). "The Astonishing Behavior of Recursive Sequences". Quanta Magazine .

External links

Jim Propp's Somos Sequence Site
Weisstein, Eric W. "Somos Sequence". MathWorld .
The Troublemaker Number. Numberphile video on the Somos sequences

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Malouf, Janice L. (1992), "An integer sequence from a rational recursion", Discrete Mathematics , 110 (1–3): 257–261, doi: 10.1016/0012-365X(92)90714-Q .

[:0-2] 1 2 Carroll, Gabriel D.; Speyer, David E. (2004), "The Cube Recurrence", Electronic Journal of Combinatorics , 11: R73, arXiv: math.CO/0403417 , doi:10.37236/1826, S2CID 1446749 .

[3] "A Bare-Bones Chronology of Somos Sequences". faculty.uml.edu. Retrieved 2023-11-27.

[4] Fomin, Sergey; Zelevinsky, Andrei (2002), "The Laurent phenomenon", Advances in Applied Mathematics , 28 (2): 119–144, arXiv: math.CO/0104241 , doi:10.1006/aama.2001.0770, S2CID 119157629 .

[5] Hone, Andrew N. W. (2021). "Casting light on shadow Somos sequences". arXiv: 2111.10905 [math.CO].

[6] Stone, Alex (18 November 2023). "The Astonishing Behavior of Recursive Sequences". Quanta Magazine .

[1]

[2]

[3]

[4]

[5]

[6]