The Lambek–Moser theorem is a mathematical description of partitions of the natural numbers into two complementary sets. For instance, it applies to the partition of numbers into even and odd, or into prime and non-prime (one and the composite numbers). There are two parts to the Lambek–Moser theorem. 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. When a formula is known for the natural number in a set, the Lambek–Moser theorem can be used to obtain a formula for the number not in the set.
The Lambek–Moser theorem belongs to combinatorial number theory. It is named for Joachim Lambek and Leo Moser, who published it in 1954, and should be distinguished from an unrelated theorem of Lambek and Moser, later strengthened by Wild, on the number of primitive Pythagorean triples. It extends Rayleigh's theorem, which describes complementary pairs of Beatty sequences, the sequences of rounded multiples of irrational numbers.
From functions to partitions
Let be any function from positive integers to non-negative integers that is both non-decreasing (each value in the sequence is at least as large as any earlier value) and unbounded (it eventually increases past any fixed value). 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 ,
Equivalently, may be defined as the number of values for which . It follows from either of these definitions that . If the two functions and are plotted as histograms, they form mirror images of each other across the diagonal line .
From these two functions and , define two more functions and , from positive integers to positive integers, by
Then the first part of the Lambek–Moser theorem states that each positive integer occurs exactly once among the values of either or . That is, the values obtained from and the values obtained from form two complementary sets of positive integers. More strongly, each of these two functions maps its argument to the th member of its set in the partition.
As an example of the construction of a partition from a function, let , the function that squares its argument. Then its inverse is the square root function, whose closest integer approximation (in the sense used for the Lambek–Moser theorem) is . These two functions give and For the values of are the pronic numbers 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, ... while the values of are 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, .... These two sequences are complementary: each positive integer belongs to exactly one of them. The Lambek–Moser theorem states that this phenomenon is not specific to the pronic numbers, but rather it arises for any choice of with the appropriate properties.
From partitions to functions
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. If and are any two complementary increasing sequences of integers, one may construct a pair of functions and from which this partition may be derived using the Lambek–Moser theorem. To do so, define and .
One of the simplest examples to which this could be applied is the partition of positive integers into even and odd numbers. The functions and should give the even or odd number, respectively, so and . From these are derived the two functions and . 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.
Limit formula
In the same work in which they proved the Lambek–Moser theorem, Lambek and Moser provided a method of going directly the function giving the member of a set of positive integers, the function giving the non-member, without going through Let denote the number of values of for which ; this is an approximation to the inverse function but (because it uses in place offset by one from the type of inverse used to define Then, for is the limit of the sequence
meaning that this sequence eventually becomes constant and the value it takes when it does