In mathematics, a Beatty sequence (or homogeneous Beatty sequence) is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926.
Rayleigh's theorem, named after Lord Rayleigh, states that the complement of a Beatty sequence, consisting of the positive integers that are not in the sequence, is itself a Beatty sequence generated by a different irrational number.
Beatty sequences can also be used to generate Sturmian words.
A positive irrational number generates the Beatty sequence
If then is also a positive irrational number. They naturally satisfy
and the sequences
form a pair of complementary Beatty sequences.
A more general non-homogeneous Beatty sequence takes the form
where is a real number. For , the complementary non-homogeneous Beatty sequences can be found by making so that
form a pair of complementary Beatty sequences.
For r = the golden mean, we have s = r + 1. In this case, the sequence , known as the lower Wythoff sequence, is
and the complementary sequence , the upper Wythoff sequence, is
- 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... (sequence A001950 in OEIS).
As another example, for r = √2, we have s = 2 + √2. In this case, the sequences are
- 1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, ... (sequence A001951 in OEIS) and
- 3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... (sequence A001952 in OEIS).
Notice that any number in the first sequence is lacking in the second, and vice versa.
Beatty sequences got their name from the problem posed in the American Mathematical Monthly by Samuel Beatty in 1926. It is probably one of the most often cited problems ever posed in the Monthly. However, even earlier, in 1894 such sequences were briefly mentioned by John W. Strutt (3rd Baron Rayleigh) in the second edition of his book The Theory of Sound.
The Rayleigh theorem (also known as Beatty's theorem) states that given an irrational number there exists so that the Beatty sequences and partition the set of positive integers: each positive integer belongs to exactly one of the two sequences.
Given let . We must show that every positive integer lies in one and only one of the two sequences and . We shall do so by considering the ordinal positions occupied by all the fractions j/r and k/s when they are jointly listed in nondecreasing order for positive integers j and k.
To see that no two of the numbers can occupy the same position (as a single number), suppose to the contrary that for some j and k. Then r/s = j/k, a rational number, but also, not a rational number. Therefore no two of the numbers occupy the same position.
For any j/r, there are j numbers i/r ≤ j/r and numbers , so that the position of in the list is . The equation implies
Likewise, the position of k/s in the list is .
Conclusion: every positive integer (that is, every position in the list) is of the form or of the form , but not both. The converse statement is also true: if p and q are two real numbers such that every positive integer occurs precisely once in the above list, then p and q are irrational and the sum of their reciprocals is 1.
Collisions: Suppose that, contrary to the theorem, there are integers j > 0 and k and m such that
This is equivalent to the inequalities
For non-zero j, the irrationality of r and s is incompatible with equality, so
which lead to
Adding these together and using the hypothesis, we get
which is impossible (one cannot have an integer between two adjacent integers). Thus the supposition must be false.
Anti-collisions: Suppose that, contrary to the theorem, there are integers j > 0 and k and m such that
Since j + 1 is non-zero and r and s are irrational, we can exclude equality, so
Then we get
Adding corresponding inequalities, we get
which is also impossible. Thus the supposition is false.
- if and only if
- where denotes or the fractional part of i.e., . Furthermore, if
- If , then
- Or, and thus, which is the given condition rearranged.
Relation with Sturmian sequences
The first difference
of the Beatty sequence associated to the irrational number is a characteristic Sturmian word over the alphabet .
The Lambek–Moser theorem generalizes the Rayleigh theorem and shows that more general pairs of sequences defined from an integer function and its inverse have the same property of partitioning the integers.
Uspensky's theorem states that, if are positive real numbers such that contains all positive integers exactly once, then That is, there is no equivalent of Rayleigh's theorem to three or more Beatty sequences.
- Beatty, Samuel (1926). "Problem 3173". American Mathematical Monthly 33 (3): 159. doi:10.2307/2300153.
- S. Beatty, A. Ostrowski, J. Hyslop, A. C. Aitken (1927). "Solutions to Problem 3173". American Mathematical Monthly 34 (3): 159–160. doi:10.2307/2298716. JSTOR 2298716.
- John William Strutt, 3rd Baron Rayleigh (1894). The Theory of Sound 1 (Second ed.). Macmillan. p. 123.
- J. V. Uspensky, On a problem arising out of the theory of a certain game, Amer. Math. Monthly 34 (1927), pp. 516–521.
- R. L. Graham, On a theorem of Uspensky, Amer. Math. Monthly 70 (1963), pp. 407–409.
- Holshouser, Arthur; Reiter, Harold (2001). "A generalization of Beatty's Theorem". Southwest Journal of Pure and Applied Mathematics 2: 24–29.
- Stolarsky, Kenneth (1976). "Beatty sequences, continued fractions, and certain shift operators". Canadian Mathematical Bulletin 19 (4): 473–482. doi:10.4153/CMB-1976-071-6. MR 0444558. Includes many references.