Beatty sequence
In mathematics, a Beatty sequence is the sequence of integers found by taking the floor of the positive multiples of an irrational number that is greater than one. 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.
Definition
Any irrational number that is greater than one generates the Beatty sequenceThe two irrational numbers and naturally satisfy the equation.
The two Beatty sequences and that they generate form a pair of complementary Beatty sequences. Here, "complementary" means that every positive integer belongs to exactly one of these two sequences.
Examples
When is the golden ratio, the sequence of integer multiples of have the approximate valuesRounding these numbers down to integers gives the sequence, known as the lower Wythoff sequence, which is
In this case, the complementary Beatty sequence is generated by
Its integer multiples have the approximate values
Rounding these values down to integers produces the upper Wythoff sequence,
Every positive integer is in exactly one of these two sequences. These sequences define the optimal strategy for Wythoff's game, and are used in the definition of the Wythoff array.
As another example, for the square root of 2,, and. In this case, the sequences are
For and, the sequences are
Any number in the first sequence is absent in the second, and vice versa.
History
Beatty sequences got their name from the problem posed in The American Mathematical Monthly by Samuel Beatty in 1926. However, even earlier, in 1894 such sequences were briefly mentioned by Lord Rayleigh in the second edition of his book The Theory of Sound.Rayleigh theorem
Rayleigh'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.First proof
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 and 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, suppose to the contrary that for some j and k. Then =, a rational number, but also, not a rational number. Therefore, no two of the numbers occupy the same position.
For any, there are positive integers such that and positive integers such that, so that the position of in the list is. The equation implies
Likewise, the position of in the list is.
Conclusion: every positive integer 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.
Second proof
This is equivalent to the inequalitiesFor non-zero j, the irrationality of r and s is incompatible with equality, so
which leads to
Adding these together and using the hypothesis, we get
which is impossible. Thus the supposition must be false.
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.
Properties
A number belongs to the Beatty sequence if and only ifwhere denotes the fractional part of i.e.,.
Proof:
Furthermore,.
Proof:
Relation with Sturmian sequences
The first differenceof the Beatty sequence associated with the irrational number is a characteristic Sturmian word over the alphabet.
Generalizations
If slightly modified, the Rayleigh's theorem can be generalized to positive real numbers and negative integers as well: if positive real numbers and satisfy, the sequences and form a partition of integers. For example, the white and black keys of a piano keyboard are distributed as such sequences for and.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 for three or more Beatty sequences.