Lambek–Moser theorem

Template:Short description Template:Good article The Lambek–Moser theorem is a mathematical description of the partitions of 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 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 every complementary partition can be constructed in this way. When a formula is known for the Template:Nowrap natural number in a set, the Lambek–Moser theorem can be used to obtain a formula for the Template:Nowrap 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,Template:Sfn and should be distinguished from an unrelated theorem of Lambek and Moser, later strengthened by Roy Wild, on the number of primitive Pythagorean triples.Template:Sfn It extends Rayleigh's theorem, which describes complementary pairs of Beatty sequences, the sequences of rounded multiples of irrational numbers.

From functions to partitions

Template:Multiple image The graphs of any two inverse functions on the positive real numbers are reflections of each other across the diagonal line $x=y$.Template:Sfn For integer functions, it is possible to define an analogue of the inverse function, and a curve analogous to the graph of a function, called in this article a histogram, for which the same reflection property holds. In more detail, let $f$ be any function from positive integers to non-negative integers that is both non-decreasing (each value in the sequence $f(1),f(2),f(3),\dots$ is at least as large as the preceding value) and unbounded (it eventually increases past any fixed value). Define the histogram of $f$ to be a piecewise-linear curve through the points $(0,0)$, $(i-1,f(i))$, and $(i,f(i))$ for each positive integer $i$. It alternates between horizontal and vertical line segments. It is not the graph of a function, because of the vertical segments; however, if only the horizontal segments and their right endpoints are included, the result is the graph of $f(\lceil x\rceil )$, the function that rounds $x$ up to an integer and then applies $f$. The vertical segments connect these horizontal segments into a single continuous curve.Template:Sfn Define a non-decreasing and unbounded integer function $f^{\ast }$ that is as close as possible to the inverse in the sense that, for all positive integers $n$, $$f(f^{\ast }(n))<n\le f(f^{\ast }(n)+1).$$ Equivalently, $f^{\ast }(n)$ may be defined as the number of values $x$ for which $f(x)<n$. It follows from either of these definitions that $f^{\ast }{}^{\ast }=f$. Then, like a pair of inverse functions, the two functions $f$ and $f^{\ast }$ have histograms that are mirror images of each other across the diagonal line $x=y$.Template:Sfn

The four functions $f$, $f^{\ast }$, $F$, and $F^{\ast }$, for the two Beatty sequences Template:Nowrap and Template:Nowrap derived from the golden ratio. The value of $f$ at each integer $x$ is the height of the lowest point of the red histogram above $x$ on the horizontal axis, as shown by the blue arrow above $x=7$. The other three blue arrows show analogously how to determine the other three function values from the histogram.

From these two functions $f$ and $f^{\ast }$, define two more functions $F$ and $F^{\ast }$, from positive integers to positive integers, by

$$\begin{array}{cc}F(n)& =f(n)+n\\ F^{\ast }(n)& =f^{\ast }(n)+n\end{array}$$ Then the first part of the Lambek–Moser theorem states each positive integer occurs exactly once among the values of either $F$ or $F^{\ast }$. That is, the values obtained from $F$ and the values obtained from $F^{\ast }$ form two complementary sets of positive integers. More strongly, each of these two functions maps its argument $n$ to the $n$th member of its set in the partition.

As an example of the construction of a partition from a function, let $f(n)=n^2$, 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 $f^{\ast }(n)=\lfloor \sqrt{n-1}\rfloor$. These two functions give $F(n)=n^2+n$ and $F^{\ast }(n)=\lfloor \sqrt{n-1}\rfloor +n.$ For $n=1,2,3,\dots$ the values of $F$ are the pronic numbers

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

while the values of $F^{\ast }$ 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.Template:Sfn The Lambek–Moser theorem states this phenomenon is not specific to pronic numbers, but rather it arises for any choice of $f$ with the appropriate properties.

From partitions to functions

The two functions $f$ (rightward blue arrows) and $f^{\ast }$ (leftward red arrows) arising from the partition of positive integers into primes (2, 3, 5, 7, ...) and non-primes (1, 4, 6, 8, ...).

Each blue arrow passes from a number $n$ through $s_n$ to $f(n)=s_n-n$, and each red arrow passes from a number $n$ through $s_n^{\ast }$ to $f^{\ast }(n)=s_n^{\ast }-n$. Visualization based on a method of Angel.Template:Sfn

The second part of the Lambek–Moser theorem states this construction of partitions from inverse functions is universal, in the sense it can explain any partition of positive integers into two infinite parts. If $S=s_1,s_2,\dots$ and $S^{\ast }=s_1^{\ast },s_2^{\ast },\dots$ are any two complementary increasing sequences of integers, one may construct a pair of functions $f$ and $f^{\ast }$ from which this partition may be derived using the Lambek–Moser theorem. To do so, define $f(n)=s_n-n$ and $f^{\ast }(n)=s_n^{\ast }-n$.

One of the simplest examples to which this could be applied is the partition of positive integers into even and odd numbers. The functions $F(n)$ and $F^{\ast }(n)$ should give the Template:Nowrap even or odd number, respectively, so $F(n)=2n$ and $F^{\ast }(n)=2n-1$. From these are derived the two functions $f(n)=F(n)-n=n$ and $f^{\ast }(n)=F^{\ast }(n)-n=n-1$. 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.Template:Sfn

Limit formula

In the same work in which they proved the Lambek–Moser theorem, Lambek and Moser provided a method of going directly Template:Nowrap the function giving the Template:Nowrap member of a set of positive integers, Template:Nowrap the function giving the Template:Nowrap non-member, without going through $f$ Template:Nowrap Let $F^{\mathrm{\#}}(n)$ denote the number of values of $x$ for which $F(x)\le n$; this is an approximation to the inverse function Template:Nowrap but (because it uses $\le$ in place Template:Nowrap offset by one from the type of inverse used to define $f^{\ast }$ Template:Nowrap Then, for Template:Nowrap $F^{\ast }(n)$ is the limit of the sequence $$n,n+F^{\mathrm{\#}}(n),n+F^{\mathrm{\#}}(n+F^{\mathrm{\#}}(n)),\dots ,$$ meaning that, after a certain point, all successive values in this sequence become equal to each other, and the resulting value Template:Nowrap

Lambek and Moser used prime numbers as an example, following earlier work by Viggo Brun and D. H. Lehmer. If $\pi (n)$ is the prime-counting function (the number of primes less than or equal Template:Nowrap then the Template:Nowrap non-prime (1 or a composite number) is given by the limit of the sequence: $$n,n+\pi (n),n+\pi (n+\pi (n)),\dots$$

For some choices of $F$, the sequence $n,n+F^{\mathrm{\#}}(n),\dots$ will start repeating after a fixed number of steps, no matter which value of $n$ it starts with. When this happens, the element of the sequence at the point where it starts repeating gives a direct formula for the complementary function $F^{\ast }$. For example, this happens when $F(n)=n^k$, the Template:Nowrap power Template:Nowrap (for an integer Template:Nowrap the sequence always starts repeating by its third term. Using this idea, the Template:Nowrap positive integer that is not a Template:Nowrap power is given by the third (repeating) term of the limiting formula as $$n+\lfloor \sqrt[k]{n+\lfloor \sqrt[k]{n}\rfloor }\rfloor .$$

History and proofs

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 $F^{\ast }$.Template:Sfn

Edsger Dijkstra's visual proof, illustrated using the triangular and non-triangular numbers (blue and yellow rectangles, respectively)

Edsger W. Dijkstra has provided a visual "proof" of the result (scare quotes as given by Dijkstra),Template:Sfn and later a more rigorous proof based on algorithmic reasoning.Template:Sfn The first of these two proofs represents an integer partition geometrically, as an arrangement of rectangles in the plane. These rectangles have dimensions $1\times n_i$ (unit width) for numbers $n_i$ that belong to the first set of the partition, and $n_i^{\ast }\times 1$ (unit height) for numbers $n_i^{\ast }$ in the second set. They are placed so that the bottom left corner of each rectangle lies on the diagonal line $x+y=-2$, and so that they together cover the integer squares of the half-plane above this line. The first rectangle, a unit square, is placed with its top right corner at the origin. The rectangles are then added one by one in order by their areas; each vertical rectangle is added to the left of the previous rectangles, with its bottom left corner on this diagonal line, while each horizontal rectangle is added above the previous rectangles, again with its bottom left corner on this diagonal line. Then the functions $f(i)$ and $F(i)$ of the theorem can be read off from this packing as the heights that the Template:Nowrap vertical rectangle rises above the $x$-axis or its bottom edge, respectively. Similarly, the functions $f^{\ast }(i)$ and $F^{\ast }(i)$ can be read off as the amount that the Template:Nowrap horizontal rectangle extends to the right of the $y$-axis or its left edge, respectively. Conversely, any two functions $f$ and $f^{\ast }$ or $F$ and $F^{\ast }$ meeting the conditions of the theorem give rise to a rectangle packing of this type, from which the values of $F$ and $F^{\ast }$ can be seen to be a partition of the integers.Template:Sfn

Yuval Ginosar has provided an intuitive proof based on an analogy of two athletes running in opposite directions, at varying speeds, around a circular racetrack. Each time one of the athletes crosses a fixed mark on the track, they report the number of times they have met the other athlete (counting the start of the race as a meeting). Because they cross paths a countable number of times, the mark can be placed at a point on the track where they never meet. Then, between each two consecutive times the athletes meet, they will together cover each point on the track once, so during this time exactly one of them will cross the mark and report their number of meetings. Therefore, the sets of numbers reported by each athlete form a partition of the positive integers. From this setup Ginosar derives the remaining properties of the Lambek–Moser theorem.Template:Sfn

Related results

For non-negative integers

As stated above, the Lambek–Moser theorem applies to partitions of the positive integers. A variation of the theorem applies instead to partitions of non-negative integers, including zero. For this variation, every partition corresponds to a Galois connection of the ordered non-negative integers to themselves. This is a pair of non-decreasing functions $(f,f^{\ast })$ with the property that, for all $x$ and $y$, $f(x)\le y$ if and only if $x\le f(y)$. The corresponding functions $F$ and $F^{\ast }$ are defined slightly less symmetrically by $F(n)=f(n)+n$ and $F^{\ast }(n)=f^{\ast }(n)+n+1$. For functions defined in this way, the values of $F$ and $F^{\ast }$ (for non-negative arguments, rather than positive arguments) form a partition of the non-negative integers, and every partition can be constructed in this way.Template:Sfn

Rayleigh's theorem

Template:Main Rayleigh's theorem states that for two positive irrational numbers Template:Nowrap both greater than one, with Template:Nowrap the two sequences $\lfloor i\cdot r\rfloor$ and $\lfloor i\cdot s\rfloor$ Template:Nowrap obtained by rounding down to an integer the multiples of Template:Nowrap are complementary. It can be seen as an instance of the Lambek–Moser theorem with $f(n)=\lfloor rn\rfloor -n$ and Template:Nowrap The condition that Template:Nowrap be greater than one implies these two functions are non-decreasing; the derived functions are $F(n)=\lfloor rn\rfloor$ and Template:Nowrap The sequences of values of $F$ and $F^{\ast }$ forming the derived partition are known as Beatty sequences, after Samuel Beatty's 1926 rediscovery of Rayleigh's theorem.

See also

• Hofstadter Figure-Figure sequences, another pair of complementary sequences to which the Lambek–Moser theorem can be applied

References

• Template:Citation
• Template:Citation
• Template:Citation; Solutions by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp. 159–160, Template:JSTOR
• Template:Citation
• Template:Citation, as cited by Template:Harvnb
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation