Lambek–Moser theorem

In mathematics, and particularly 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. Dijkstra (1980) provides a visual proof of the result.

Statement of the theorem

The theorem applies to an non-decreasing 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 n,

ƒ(ƒ*(n)) < n ≤ ƒ(ƒ*(n) + 1).

It follows from this definition that ƒ** = ƒ.

Further, define

F(n) = ƒ(n) + n and G(n) = ƒ*(n) + n.

Then the result states that F and G are strictly increasing and that the ranges of F and G form a partition of the positive integers.

Example

Let ƒ(n) = n²; then $\scriptstyle f^{\ast }(n)=\lfloor {\sqrt {n-1}}\rfloor$. Thus F(n) = n² + n and $\scriptstyle G(n)=\lfloor {\sqrt {n-1}}\rfloor +n.$ For n = 1, 2, 3, ... the values of F are the pronic numbers

2, 6, 12, 20, 30, 42, 56, 72, 90, 110, ...

while the values of G 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.

Beatty's theorem

Beatty's theorem, defining a partition of the integers from rounding their multiples by an irrational number r > 1, can be seen as an instance of the Lambek–Moser theorem. In Beatty's theorem, $\scriptstyle f(n)=\lfloor rn\rfloor -n$ and $\scriptstyle f^{\ast }(n)=\lfloor sn\rfloor -n,$ where $\scriptstyle {\tfrac {1}{r}}+{\tfrac {1}{s}}=1$. The condition that r (and therefore s) be greater than one implies that these two functions are non-decreasing; the derived functions are $\scriptstyle F(n)=\lfloor rn\rfloor$ and $\scriptstyle G(n)=\lfloor sn\rfloor .$ The sequences of values of F and G forming the derived partition are known as Beatty sequences.

Universality

If S = s₁,s₂,... and T = t₁,t₂,... are any two infinite subsets forming a partition of the integers, one may derive a pair of functions ƒ and ƒ* from which this partition may be derived using Beatty's theorem: ƒ(n) = s_n − n and ƒ*(n) = t_n − n. For instance, consider the partition of integers into even and odd numbers: let S be the even numbers and T be the odd numbers. Then s_n = 2n, so ƒ(n) = n and similarly ƒ*(n) = n − 1. 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.

References

• Beatty, Samuel (1926), "Problem 3173", American Mathematical Monthly, 33 (3): 159, doi:10.2307/2300153 Solutions by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp. 159-160.
• Dijkstra, Edsger W. (1980), On a theorem by Lambek and Moser (PDF), Report EWD753, University of Texas.
• Lambek, Joachim; Moser, Leo (Aug-Sep, 1954), "Inverse and Complementary Sequences of Natural Numbers", The American Mathematical Monthly, 61 (7): 454–458, doi:10.2307/2308078 {{citation}}: Check date values in: |date= (help)