Lambek–Moser theorem


In combinatorial number theory, the Lambek–Moser theorem is a generalization of Beatty's theorem that defines a partition of the positive integers into two subsets from any monotonic integer-valued function. Conversely, any partition of the positive integers into two subsets may be defined from a monotonic function in this way.
The theorem was discovered by Leo Moser and Joachim Lambek. provides a visual proof of the result.

Statement of the theorem

The theorem applies to any non-decreasing and unbounded function that maps positive integers to non-negative integers. From any such function, define to be the integer-valued function that is as close as possible to the inverse function of, in the sense that, for all,
It follows from this definition that.
Further, let
Then the result states that and are strictly increasing and that the ranges of and form a partition of the positive integers.

Example

Let ; then.
Thus and
For the values of are the pronic numbers
while the values of are
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.

Beatty's theorem

, defining a partition of the integers from rounding their multiples by an irrational number, can be seen as an instance of the Lambek–Moser theorem. In Beatty's theorem, and where. The condition that be greater than one implies that these two functions are non-decreasing; the derived functions are and The sequences of values of and forming the derived partition are known as Beatty sequences.

Universality

The Lambek–Moser theorem is universal, in the sense that it can explain any partition of the integers into two infinite parts. If and are any two infinite subsets forming a partition of the integers, one may construct a pair of functions and from which this partition may be derived using the Lambek–Moser theorem: define and.
For instance, consider the partition of integers into even and odd numbers: let be the even numbers and be the odd numbers.
Then, so and similarly. These two functions and 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.
Lambek and Moser discuss formulas involving the prime-counting function for the functions and arising in this way from the partition of the positive integers into prime numbers and composite numbers.