Lambek–Moser theorem
The Lambek–Moser theorem is a mathematical description of partitions of the natural numbers into two complementary sets.
One part states that any two non-decreasing integer functions that are inverse, in a certain sense, can be used to split the natural numbers into two complementary subsets, and the other part states that every complementary partition can be constructed in this way.
th natural number in a set, the Lambek–Moser theorem can be used to obtain a formula for the
The Lambek–Moser theorem belongs to combinatorial number theory.
It is named for Joachim Lambek and Leo Moser, who published it in 1954,[1] and should be distinguished from an unrelated theorem of Lambek and Moser, later strengthened by Wild, on the number of primitive Pythagorean triples.
[2] It extends Rayleigh's theorem, which describes complementary pairs of Beatty sequences, the sequences of rounded multiples of irrational numbers.
The sequence of its values may skip some numbers, so it might not have an inverse function with the same properties.
Instead, define a non-decreasing and unbounded integer function
that is as close as possible to the inverse in the sense that, for all positive integers
are plotted as histograms, they form mirror images of each other across the diagonal line
Then the first part of the Lambek–Moser theorem states that each positive integer occurs exactly once among the values of either
form two complementary sets of positive integers.
Then its inverse is the square root function, whose closest integer approximation (in the sense used for the Lambek–Moser theorem) is
are These two sequences are complementary: each positive integer belongs to exactly one of them.
[4] The Lambek–Moser theorem states that this phenomenon is not specific to the pronic numbers, but rather it arises for any choice of
[3] The second part of the Lambek–Moser theorem states that this construction of partitions from inverse functions is universal, in the sense that it can explain any partition of the positive integers into two infinite parts.
are any two complementary increasing sequences of integers, one may construct a pair of functions
[3] One of the simplest examples to which this could be applied is the partition of positive integers into even and odd numbers.
They form an inverse pair, and the partition generated via the Lambek–Moser theorem from this pair is just the partition of the positive integers into even and odd numbers.
Another integer partition, into evil numbers and odious numbers (by the parity of the binary representation) uses almost the same functions, adjusted by the values of the Thue–Morse sequence.
[6] In the same work in which they proved the Lambek–Moser theorem, Lambek and Moser provided a method of going directly from
meaning that this sequence eventually becomes constant and the value it takes when it does is
[7] Lambek and Moser used the prime numbers as an example, following earlier work by Viggo Brun and D. H.
is the prime-counting function (the number of primes less than or equal to
th non-prime (1 or a composite number) is given by the limit of the sequence[7]
The theorem was discovered by Leo Moser and Joachim Lambek, who published it in 1954.
Moser and Lambek cite the previous work of Samuel Beatty on Beatty sequences as their inspiration, and also cite the work of Viggo Brun and D. H. Lehmer from the early 1930s on methods related to their limiting formula for
[11] Yuval Ginosar has provided an intuitive proof based on an analogy of two athletes running in opposite directions around a circular racetrack.
For this variation, every partition corresponds to a Galois connection of the ordered non-negative integers to themselves.
[13] Rayleigh's theorem states that for two positive irrational numbers
