In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a Beatty sequence (or homogeneous Beatty sequence) is the
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
of
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s found by taking the
floor
A floor is the bottom surface of a room or vehicle. Floors vary from wikt:hovel, simple dirt in a cave to many layered surfaces made with modern technology. Floors may be stone, wood, bamboo, metal or any other material that can support the ex ...
of the positive
multiples of a positive
irrational number
In mathematics, the irrational numbers are all the real numbers that are not rational numbers. That is, irrational numbers cannot be expressed as the ratio of two integers. When the ratio of lengths of two line segments is an irrational number, ...
. Beatty sequences are named after
Samuel Beatty, who wrote about them in 1926.
Rayleigh's theorem, named after
Lord Rayleigh
John William Strutt, 3rd Baron Rayleigh ( ; 12 November 1842 – 30 June 1919), was an English physicist who received the Nobel Prize in Physics in 1904 "for his investigations of the densities of the most important gases and for his discovery ...
, states that the
complement
Complement may refer to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class collections into complementary sets
* Complementary color, in the visu ...
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 sequence
The 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
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their summation, sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if
\fr ...
, the complementary Beatty sequence is generated by
. In this case, the sequence
, known as the ''lower Wythoff sequence'', is
and the complementary sequence
, the ''upper Wythoff sequence'', is
These sequences define the optimal strategy for
Wythoff's game, and are used in the definition of the
Wythoff array
In mathematics, the Wythoff array is an infinite Matrix (mathematics), matrix of positive integers derived from the Fibonacci sequence and named after Dutch mathematician Willem Abraham Wythoff. Every positive integer occurs exactly once in the arr ...
.
As another example, for the
square root of 2
The square root of 2 (approximately 1.4142) is the positive real number that, when multiplied by itself or squared, equals the number 2. It may be written as \sqrt or 2^. It is an algebraic number, and therefore not a transcendental number. Te ...
,
,
. 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
''The American Mathematical Monthly'' is a peer-reviewed scientific journal of mathematics. It was established by Benjamin Finkel in 1894 and is published by Taylor & Francis on behalf of the Mathematical Association of America. It is an exposito ...
'' 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
Lord Rayleigh
John William Strutt, 3rd Baron Rayleigh ( ; 12 November 1842 – 30 June 1919), was an English physicist who received the Nobel Prize in Physics in 1904 "for his investigations of the densities of the most important gases and for his discovery ...
in the second edition of his book ''The Theory of Sound''.
Rayleigh theorem
Rayleigh's theorem (also known as Beatty's theorem) states that given an irrational number
there exists
so that the Beatty sequences
and
partition the
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
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 (as a single number), suppose to the contrary that
for some ''j'' and ''k''. Then
=
, a
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example,
The set of all ...
, 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 (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
In mathematics, a real number is a number that can be used to measurement, measure a continuous variable, continuous one-dimensional quantity such as a time, duration or temperature. Here, ''continuous'' means that pairs of values can have arbi ...
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
: 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 leads 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.
: 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.
Properties
A number
belongs to the Beatty sequence
if and only if
where
denotes the fractional part of
i.e.,
.
Proof:
Furthermore,
.
Proof:
Relation with Sturmian sequences
The
first difference
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
of 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 (not necessarily irrational) 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.
[R. L. Graham]
On a theorem of Uspensky
''Amer. Math. Monthly'' 70 (1963), pp. 407–409.
References
Further reading
*
* Includes many references.
External links
* {{mathworld, title = Beatty Sequence, urlname = BeattySequence
*
Alexander BogomolnyBeatty Sequences Cut-the-knot
Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet Union, Soviet-born Israeli Americans, Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow ...
Integer sequences
Theorems in number theory
Diophantine approximation
Combinatorics on words
Articles containing proofs