Lambek–Moser theorem: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 14:14, 3 March 2024

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 $n$ th natural number in a set, the Lambek–Moser theorem can be used to obtain a formula for the $n$ th 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,^[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.

From functions to partitions

The four functions $f$ , $f^{*}$ , $F$ , and $F^{*}$ , for the two Beatty sequences 1, 3, 4, 6, ... and 2, 5, 7, 10, ... . These sequences round down the integer multiples of $\varphi$ and $\varphi +1$ , where $\varphi$ is the golden ratio.

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 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 $f^{*}$ that is as close as possible to the inverse in the sense that, for all positive integers $n$ , $f{\bigl (}f^{*}(n){\bigr )}<n\leq f{\bigl (}f^{*}(n)+1{\bigr )}.$ Equivalently, $f^{*}(n)$ may be defined as the number of values $x$ for which $f(x)<n$ . It follows from either of these definitions that $f^{*}{}^{*}=f$ .^[3] If the two functions $f$ and $f^{*}$ are plotted as histograms, they form mirror images of each other across the diagonal line $x=y$ .^[4]

From these two functions $f$ and $f^{*}$ , define two more functions $F$ and $F^{*}$ , from positive integers to positive integers, by ${\begin{aligned}F(n)&=f(n)+n\\F^{*}(n)&=f^{*}(n)+n\\\end{aligned}}$ Then the first part of the Lambek–Moser theorem states that each positive integer occurs exactly once among the values of either $F$ or $F^{*}$ . That is, the values obtained from $F$ and the values obtained from $F^{*}$ 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.^[3]

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^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor$ . These two functions give $F(n)=n^{2}+n$ and $F^{*}(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^{*}$ 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.^[4] The Lambek–Moser theorem states that this phenomenon is not specific to the pronic numbers, but rather it arises for any choice of $f$ with the appropriate properties.^[3]

From partitions to functions

The two functions $f$ (rightward blue arrows) and $f^{*}$ (leftward red arrows) arising from the partition of positive integers into primes (2, 3, 5, 7, ...) and non-primes (1, 4, 6, 8, ...). Visualization based on a method of Angel.^[5]

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 $S=s_{1},s_{2},\dots$ and $S^{*}=s_{1}^{*},s_{2}^{*},\dots$ are any two complementary increasing sequences of integers, one may construct a pair of functions $f$ and $f^{*}$ from which this partition may be derived using the Lambek–Moser theorem. To do so, define $f(n)=s_{n}-n$ and $f^{*}(n)=s_{n}^{*}-n$ .^[3]

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^{*}(n)$ should give the $n$ th even or odd number, respectively, so $F(n)=2n$ and $F^{*}(n)=2n-1$ . From these are derived the two functions $f(n)=F(n)-n=n$ and $f^{*}(n)=F^{*}(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.^[6]

Limit formula

In the same work in which they proved the Lambek–Moser theorem, Lambek and Moser provided a method of going directly from $F$ , the function giving the $n$ th member of a set of positive integers, to $F^{*}$ , the function giving the $n$ th non-member, without going through $f$ and $f^{*}$ . Let $F^{\#}(n)$ denote the number of values of $x$ for which $F(x)\leq n$ ; this is an approximation to the inverse function of $F$ , but (because it uses $\leq$ in place of $<$ ) offset by one from the type of inverse used to define $f^{*}$ from $f$ . Then, for any $n$ , $F^{*}(n)$ is the limit of the sequence $n,n+F^{\#}(n),n+F^{\#}{\bigl (}n+F^{\#}(n){\bigr )},\dots ,$ meaning that this sequence eventually becomes constant and the value it takes when it does is $F^{*}(n)$ .^[7]

Lambek and Moser used the prime numbers as an example, following earlier work by Viggo Brun and D. H. Lehmer.^[8] If $\pi (n)$ is the prime-counting function (the number of primes less than or equal to $n$ ), then the $n$ th non-prime (1 or a composite number) is given by the limit of the sequence^[7] $n,n+\pi (n),n+\pi {\bigl (}n+\pi (n){\bigr )},\dots$

For some other sequences of integers, the corresponding limit converges in a fixed number of steps, and a direct formula for the complementary sequence is possible. In particular, the $n$ th positive integer that is not a $k$ th power can be obtained from the limiting formula as^[9] $n+\left\lfloor {\sqrt[{k}]{n+\lfloor {\sqrt[{k}]{n}}\rfloor }}\right\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^{*}$ .^[1] Edsger W. Dijkstra has provided a visual proof of the result,^[10] and later another proof based on algorithmic reasoning.^[11] Yuval Ginosar has provided an intuitive proof based on an analogy of two athletes running in opposite directions around a circular racetrack.^[12]

Related results

For non-negative integers

A variation of the theorem applies to partitions of the non-negative integers, rather than to partitions of the positive integers. 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^{*})$ with the property that, for all $x$ and $y$ , $f(x)\leq y$ if and only if $x\leq f(y)$ . The corresponding functions $F$ and $F^{*}$ are defined slightly less symmetrically by $F(n)=f(n)+n$ and $F^{*}(n)=f^{*}(n)+n+1$ . For functions defined in this way, the values of $F$ and $F^{*}$ (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.^[13]

Rayleigh's theorem

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

Notes

^ ^a ^b Lambek & Moser 1954.
^ Wild 1955.
^ ^a ^b ^c ^d Lambek & Moser 1954; Honsberger 1970, pp. 95–96; Fraenkel 1977.
^ ^a ^b Garry 1997.
^ Angel 1964.
^ Allouche & Dekking 2019.
^ ^a ^b Lambek & Moser 1954; Roberts 1992.
^ Brun 1931; Lehmer 1932.
^ Honsberger 1970, pp. 97–100; Dos Reis & Silberger 1990; Roberts 1992.
^ Dijkstra 1980.
^ Dijkstra 1982.
^ Ginosar 2014.
^ Lambek 1994.
^ Rayleigh 1894; Beatty 1926; Honsberger 1970, pp. 93–95; Chamberland 2017.

References

Allouche, Jean-Paul; Dekking, F. Michel (2019), "Generalized Beatty sequences and complementary triples", Moscow Journal of Combinatorics and Number Theory, 8 (4): 325–341, arXiv:1809.03424, doi:10.2140/moscow.2019.8.325, MR 4026541, S2CID 119176190
Angel, Myer (1964), "Partitions of the natural numbers", Canadian Mathematical Bulletin, 7 (2): 219–236, doi:10.4153/CMB-1964-020-1, MR 0161826, S2CID 123729929
Beatty, Samuel (1926), "Problem 3173", The American Mathematical Monthly, 33 (3): 159, doi:10.2307/2300153, JSTOR 2300153; Solutions by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp. 159–160, JSTOR 2298716
Brun, Viggo (1931), "Rechenregel zur Bildung der $n$ -ten Primzahl" [Calculating rules to build the $n$ th prime], Norsk Matematisk Tidsskrift (in Norwegian), 13: 73–79, Zbl 0003.14902, as cited by Lambek & Moser 1954
Chamberland, Marc (2017), "Beatty sequences", Single Digits: In Praise of Small Numbers, Princeton University Press, pp. 32–33, ISBN 978-0-691-17569-0
Dijkstra, Edsger W. (1980), On a theorem by Lambek and Moser (PDF), Report EWD753, University of Texas
Dijkstra, Edsger W. (1982), "Lambek and Moser revisited", in Broy, Manfred; Schmidt, Gunther (eds.), Theoretical Foundations of Programming Methodology: Lecture Notes of an International Summer School, directed by F. L. Bauer, E. W. Dijkstra and C. A. R. Hoare, NATO Advanced Study Institutes Series, Series C – Mathematical and Physical Sciences, vol. 91, D. Reidel Publishing Co., pp. 19–23, doi:10.1007/978-94-009-7893-5_2, ISBN 978-90-277-1462-6, Zbl 0533.40001
Dos Reis, A. J.; Silberger, D. M. (1990), "Generating nonpowers by formula", Mathematics Magazine, 63 (1): 53–55, doi:10.1080/0025570X.1990.11977485, JSTOR 2691513, MR 1042938
Fraenkel, Aviezri S. (1977), "Complementary systems of integers", The American Mathematical Monthly, 84 (2): 114–115, doi:10.2307/2319931, JSTOR 2319931, MR 0429815
Garry, Y. K. K. (1997), "Inverse sequences and complementary sequences" (PDF), Mathematical Excalibur, 3 (4): 2
Ginosar, Yuval (2014), "On the Lambek–Moser theorem", Integers, 14: A09:1–A09:4, arXiv:1207.5633
Honsberger, Ross (1970), "Essay 12: Complementary sequences", Ingenuity in Mathematics, New Mathematical Library, vol. 23, New York: Random House, Inc., pp. 93–110, ISBN 0-394-70923-3, MR 3155264
Lambek, Joachim (1994), "Some Galois connections in elementary number theory", Journal of Number Theory, 47 (3): 371–377, doi:10.1006/jnth.1994.1043, MR 1278405
Lambek, Joachim; Moser, Leo (August–September 1954), "Inverse and complementary sequences of natural numbers", The American Mathematical Monthly, 61 (7): 454–458, doi:10.1080/00029890.1954.11988496, JSTOR 2308078
Lehmer, D. H. (1932), "An inversive algorithm", Bulletin of the American Mathematical Society, 38 (10): 693–694, doi:10.1090/S0002-9904-1932-05496-9, MR 1562488
John William Strutt, Baron Rayleigh (1894), The Theory of Sound, vol. 1 (2nd ed.), Macmillan, p. 123
Roberts, Joe (1992), Lure of the Integers, MAA Spectrum, Washington, DC: Mathematical Association of America, p. 11, doi:10.2307/40148160, ISBN 0-88385-502-X, JSTOR 40148160, MR 1189138
Wild, Roy E. (1955), "On the number of primitive Pythagorean triangles with area less than $n$ ", Pacific Journal of Mathematics, 5: 85–91, doi:10.2140/pjm.1955.5.85, MR 0067912

[FOOTNOTELambekMoser1954-1] Lambek & Moser 1954.

[FOOTNOTEWild1955-2] Wild 1955.

[statement-3] Lambek & Moser 1954; Honsberger 1970, pp. 95–96; Fraenkel 1977.

[FOOTNOTEGarry1997-4] Garry 1997.

[FOOTNOTEAngel1964-5] Angel 1964.

[FOOTNOTEAlloucheDekking2019-6] Allouche & Dekking 2019.

[lure-7] Lambek & Moser 1954; Roberts 1992.

[8] Brun 1931; Lehmer 1932.

[9] Honsberger 1970, pp. 97–100; Dos Reis & Silberger 1990; Roberts 1992.

[FOOTNOTEDijkstra1980-10] Dijkstra 1980.

[FOOTNOTEDijkstra1982-11] Dijkstra 1982.

[FOOTNOTEGinosar2014-12] Ginosar 2014.

[FOOTNOTELambek1994-13] Lambek 1994.

[14] Rayleigh 1894; Beatty 1926; Honsberger 1970, pp. 93–95; Chamberland 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Line 1: / Line 1: @@
 {{short description|On integer partitions from monotonic functions}}
-In [[combinatorial number theory]], the '''Lambek–Moser theorem''' defines a [[partition (number theory)|partition]] of the positive [[integer]]s into two subsets from any [[monotonic function|non-decreasing]] integer-valued function and its [[inverse function]]. It is a generalization of [[Beatty sequence|Rayleigh's theorem]], on the complementary [[Beatty sequence]]s obtained by rounding down irrational multiples of the integers. If a formula or function is known for the <math>n</math>th smallest member of a set of positive integers, the Lambek–Moser theorem can be used to derive a formula for the <math>n</math>th positive integer not in the set.
+The '''Lambek–Moser theorem''' is a mathematical description of partitions of the [[natural number]]s into two [[Complement (set theory)|complementary sets]]. For instance, it applies to the partition of numbers into [[even number|even]] and [[odd number|odd]], or into [[prime number|prime]] and non-prime (one and the [[composite number]]s). There are two parts to the Lambek–Moser theorem. One part states that any two [[monotonic function|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 {{nowrap|<math>n</math>th}} natural number in a set, the Lambek–Moser theorem can be used to obtain a formula for the {{nowrap|<math>n</math>th}} 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,{{sfn|Lambek|Moser|1954}} and should be distinguished from an unrelated theorem of Lambek and Moser, later strengthened by Wild, on the number of [[primitive Pythagorean triple]]s.{{sfn|Wild|1955}} It extends Rayleigh's theorem, which describes complementary pairs of [[Beatty sequence]]s, the sequences of rounded multiples of irrational numbers.
-Any partition of the positive integers into two complementary subsets may be defined from a non-decreasing function using the Lambek–Moser theorem. As well as the Beatty sequences, other pairs of complementary sets of positive integers to which the Lambek–Moser theorem can be applied include the [[even number]]s and the [[odd number]]s, the [[evil number]]s and the [[odious number]]s, the [[prime number]]s and the non-primes (1 and the [[composite number]]s), and the <math>k</math>th powers and non-powers.
+==From functions to partitions==
-The Lambek–Moser theorem is named for [[Joachim Lambek]] and [[Leo Moser]], who published it in 1954,{{sfn|Lambek|Moser|1954}} and should be distinguished from an unrelated theorem of Lambek and Moser, later strengthened by Wild, on the number of [[primitive Pythagorean triple]]s.{{sfn|Wild|1955}}
-==Statement==
-There are two parts to the Lambek–Moser theorem. One part states that two integers functions that are inverse, in a certain sense, can be used to construct a partition of the positive integers into two complementary subsets, and the other part states that every complementary partition can be constructed in this way.
-===From functions to partitions===
 [[File:Lambek–Moser.svg|thumb|upright=1.35|The four functions <math>f</math>, <math>f^*</math>, <math>F</math>, and <math>F^*</math>, for the two [[Beatty sequence]]s {{nowrap|1, 3, 4, 6, ...}} and {{nowrap|2, 5, 7, 10, ... .}} These sequences round down the integer multiples of <math>\varphi</math> and <math>\varphi+1</math>, where <math>\varphi</math> is the [[golden ratio]].]]
-The theorem applies to any [[monotonic function|non-decreasing]] and un[[bounded function]] <math>f</math> that maps positive integers to non-negative integers. From any such function <math>f</math>, define <math>f^*</math> to be the integer-valued function that is as close as possible to the [[inverse function]] of <math>f</math>, in the sense that, for all positive integers <math>n</math>,
+Let <math>f</math> be any function from positive [[integer]]s to non-negative integers that is both [[monotonic function|non-decreasing]] (each value in the sequence <math>f(1),f(2),f(3),\dots</math> is at least as large as any earlier value) and [[bounded function|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 <math>f^*</math> that is as close as possible to the inverse in the sense that, for all positive integers <math>n</math>,
 <math display=block>f\bigl(f^*(n)\bigr) < n \le f\bigl(f^*(n)+1\bigr).</math>
 Equivalently, <math>f^*(n)</math> may be defined as the number of values <math>x</math> for which <math>f(x)<n</math>.
-It follows from either of these definitions that <math>f^*{}^*=f</math>.
+It follows from either of these definitions that <math>f^*{}^*=f</math>.<ref name=statement/> If the two functions <math>f</math> and <math>f^*</math> are plotted as [[histogram]]s, they form mirror images of each other across the diagonal line <math>x=y</math>.{{sfn|Garry|1997}}
-Further, define two more functions <math>F</math> and <math>F^*</math>, from positive integers to positive integers, by
+From these two functions <math>f</math> and <math>f^*</math>, define two more functions <math>F</math> and <math>F^*</math>, from positive integers to positive integers, by
 <math display=block>
 \begin{align}
@@ Line 21: / Line 18: @@
 F^*(n)&=f^*(n)+n\\
 \end{align}</math>
-Then the first part of the theorem states that <math>F</math> and <math>F^*</math> are strictly increasing and that the ranges of <math>F</math> and <math>F^*</math> form a partition of the positive integers. Each of these two functions maps any integer <math>i</math> to the <math>i</math>th element of its set in the partition.<ref name=statement>{{harvnb|Lambek|Moser|1954}}; {{harvnb|Honsberger|1970}}, pp. 95–96; {{harvnb|Fraenkel|1977}}.</ref>
+Then the first part of the Lambek–Moser theorem states that each positive integer occurs exactly once among the values of either <math>F</math> or <math>F^*</math>.
+That is, the values obtained from <math>F</math> and the values obtained from <math>F^*</math> form two complementary sets of positive integers. More strongly, each of these two functions maps its argument <math>n</math> to the <math>n</math>th member of its set in the partition.<ref name=statement>{{harvnb|Lambek|Moser|1954}}; {{harvnb|Honsberger|1970}}, pp. 95–96; {{harvnb|Fraenkel|1977}}.</ref>
+As an example of the construction of a partition from a function, let <math>f(n)=n^2</math>, the function that [[Square (algebra)|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 <math>f^*(n)=\lfloor\sqrt{n-1}\rfloor</math>.
-===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 <math>S=s_1,s_2,\dots</math> and <math>S^*=s^*_1,s^*_2,\dots</math> are any two complementary increasing sequences of integers, one may construct a pair of functions <math>f</math> and <math>f^*</math> from which this partition may be derived using the Lambek–Moser theorem. To do so, define <math>f(n)=s_n-n</math> and <math>f^*(n)=s^*_n-n</math>.<ref name=statement/>
-===Limits of iterated inverses===
-In the same work in which they proved the Lambek–Moser theorem, Lambek and Moser provided a method of reconstructing <math>F^*</math> directly from <math>F</math>, without going through <math>f</math> and <math>f^*</math>. Let <math>F^{\#}(n)</math> denote the number of values of <math>x</math> for which <math>F(x)\le n</math>; this is an approximation to the inverse function of <math>F</math>, but (because it uses <math>\le</math> in place of <math><</math>) offset by one from the type of inverse used to define <math>f^*</math> from <math>f</math>. Then, for any <math>n</math>, <math>F^*(n)</math> is the limit of the sequence
-<math display=block>n, n+F^{\#}(n), n+F^{\#}\bigl(n+F^{\#}(n)\bigr), \dots,</math>
-meaning that this sequence eventually becomes constant and the value it takes when it does is <math>F^*(n)</math>.<ref name=lure>{{harvnb|Lambek|Moser|1954}}; {{harvnb|Roberts|1992}}.</ref>
-===For non-negative integers===
-A variation of the theorem applies to partitions of the non-negative integers, rather than to partitions of the positive integers. 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
-<math>(f,f^*)</math> with the property that, for all <math>x</math> and <math>y</math>, <math>f(x)\le y</math> if and only if <math>x\le f(y)</math>. The corresponding functions <math>F</math> and <math>F^*</math> are defined slightly less symmetrically by <math>F(n)=f(n)+n</math> and <math>F^*(n)=f^*(n)+n+1</math>. For functions defined in this way, the values of <math>F</math> and <math>F^*</math> (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.{{sfn|Lambek|1994}}
-==Examples==
-For instance, consider the partition of positive integers into [[Parity (mathematics)|even and odd numbers]], let <math>F(n)=2n</math> be the <math>n</math>th even positive integer, and let <math>F^*(n)=2n-1</math> be the <math>n</math>th odd positive integer. Then the two functions <math>f(n)=F(n)-n=n</math> and <math>f^*(n)=F^*(n)-n=n-1</math> 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 number]]s and [[odious number]]s (by the parity of the [[binary representation]]) uses almost the same functions, adjusted by the values of the [[Thue–Morse sequence]].{{sfn|Allouche|Dekking|2019}}
-As another example, let <math>f(n)=n^2</math>, the function that [[Square (algebra)|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 <math>f^*(n)=\lfloor\sqrt{n-1}\rfloor</math>.
 These two functions give <math>F(n)=n^2+n</math> and <math>F^*(n)=\lfloor\sqrt{n-1}\rfloor+n.</math>
 For <math>n=1,2,3,\dots</math> the values of <math>F</math> are the [[pronic number]]s
@@ Line 46: / Line 29: @@
 These two sequences are complementary: each positive integer belongs to exactly one of them.{{sfn|Garry|1997}} The Lambek–Moser theorem states that this phenomenon is not specific to the pronic numbers, but rather it arises for any choice of <math>f</math> with the appropriate properties.<ref name=statement/>
+==From partitions to functions==
 [[File:Prime Lambek–Moser.svg|thumb|The two functions <math>f</math> (rightward blue arrows) and <math>f^*</math> (leftward red arrows) arising from the partition of positive integers into [[prime number|primes]] (2, 3, 5, 7, ...) and non-primes (1, 4, 6, 8, ...). Visualization based on a method of Angel.{{sfn|Angel|1964}}]]
+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 <math>S=s_1,s_2,\dots</math> and <math>S^*=s^*_1,s^*_2,\dots</math> are any two complementary increasing sequences of integers, one may construct a pair of functions <math>f</math> and <math>f^*</math> from which this partition may be derived using the Lambek–Moser theorem. To do so, define <math>f(n)=s_n-n</math> and <math>f^*(n)=s^*_n-n</math>.<ref name=statement/>
-Following earlier work of [[Viggo Brun]] and [[D. H. Lehmer]],<ref>{{harvnb|Brun|1931}}; {{harvnb|Lehmer|1932}}.</ref> Lambek and Moser discuss formulas involving the [[prime-counting function]] for the functions <math>f</math> and <math>f^*</math> arising in this way from the partition of the positive integers into [[prime number]]s and non-primes (1 and the [[composite number]]s). If <math>\pi(n)</math> is the prime-counting function (number of primes less than or equal to <math>n</math>), then the <math>n</math>th non-prime is given by the limit of the sequence<ref name=lure/>
+One of the simplest examples to which this could be applied is the partition of positive integers into [[Parity (mathematics)|even and odd numbers]]. The functions <math>F(n)</math> and <math>F^*(n)</math> should give the {{nowrap|<math>n</math>th}} even or odd number, respectively, so <math>F(n)=2n</math>  and <math>F^*(n)=2n-1</math>. From these are derived the two functions <math>f(n)=F(n)-n=n</math> and <math>f^*(n)=F^*(n)-n=n-1</math>. 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 number]]s and [[odious number]]s (by the parity of the [[binary representation]]) uses almost the same functions, adjusted by the values of the [[Thue–Morse sequence]].{{sfn|Allouche|Dekking|2019}}
+==Limit formula==
+In the same work in which they proved the Lambek–Moser theorem, Lambek and Moser provided a method of going directly {{nowrap|from <math>F</math>,}} the function giving the {{nowrap|<math>n</math>th}} member of a set of positive integers, {{nowrap|to <math>F^*</math>,}} the function giving the {{nowrap|<math>n</math>th}} non-member, without going through <math>f</math> {{nowrap|and <math>f^*</math>.}} Let <math>F^{\#}(n)</math> denote the number of values of <math>x</math> for which <math>F(x)\le n</math>; this is an approximation to the inverse function {{nowrap|of <math>F</math>,}} but (because it uses <math>\le</math> in place {{nowrap|of <math><</math>)}} offset by one from the type of inverse used to define <math>f^*</math> {{nowrap|from <math>f</math>.}} Then, for {{nowrap|any <math>n</math>,}} <math>F^*(n)</math> is the limit of the sequence
+<math display=block>n, n+F^{\#}(n), n+F^{\#}\bigl(n+F^{\#}(n)\bigr), \dots,</math>
+meaning that this sequence eventually becomes constant and the value it takes when it does {{nowrap|is <math>F^*(n)</math>.<ref name=lure>{{harvnb|Lambek|Moser|1954}}; {{harvnb|Roberts|1992}}.</ref>}}
+Lambek and Moser used the [[prime number]]s as an example, following earlier work by [[Viggo Brun]] and [[D. H. Lehmer]].<ref>{{harvnb|Brun|1931}}; {{harvnb|Lehmer|1932}}.</ref> If <math>\pi(n)</math> is the [[prime-counting function]] (the number of primes less than or equal {{nowrap|to <math>n</math>),}} then the {{nowrap|<math>n</math>th}} non-prime (1 or a [[composite number]]) is given by the limit of the sequence<ref name=lure/>
 <math display=block>n, n+\pi(n), n+\pi\bigl(n+\pi(n)\bigr), \dots</math>
-For some other sequences of integers, the corresponding limit converges in a fixed number of steps, and a direct formula for the complementary sequence is possible. In particular, the <math>n</math>th positive integer that is not a <math>k</math>th power can be obtained from the limiting formula as<ref>{{harvnb|Honsberger|1970}}, pp. 97–100; {{harvnb|Dos Reis|Silberger|1990}}; {{harvnb|Roberts|1992}}.</ref>
+For some other sequences of integers, the corresponding limit converges in a fixed number of steps, and a direct formula for the complementary sequence is possible. In particular, the {{nowrap|<math>n</math>th}} positive integer that is not a {{nowrap|<math>k</math>th}} power can be obtained from the limiting formula as<ref>{{harvnb|Honsberger|1970}}, pp. 97–100; {{harvnb|Dos Reis|Silberger|1990}}; {{harvnb|Roberts|1992}}.</ref>
 <math display=block>n+\left\lfloor\sqrt[k]{n + \lfloor\sqrt[k]{n}\rfloor}\right\rfloor.</math>
+==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 (mathematician)|Samuel Beatty]] on [[Beatty sequence]]s 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 <math>F^*</math>.{{sfn|Lambek|Moser|1954}} [[Edsger W. Dijkstra]] has provided a [[proof without words|visual proof]] of the result,{{sfn|Dijkstra|1980}} and later another proof based on [[algorithm]]ic reasoning.{{sfn|Dijkstra|1982}} Yuval Ginosar has provided an intuitive proof based on an analogy of two athletes running in opposite directions around a circular racetrack.{{sfn|Ginosar|2014}}
+==Related results==
+===For non-negative integers===
+A variation of the theorem applies to partitions of the non-negative integers, rather than to partitions of the positive integers. 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
+<math>(f,f^*)</math> with the property that, for all <math>x</math> and <math>y</math>, <math>f(x)\le y</math> if and only if <math>x\le f(y)</math>. The corresponding functions <math>F</math> and <math>F^*</math> are defined slightly less symmetrically by <math>F(n)=f(n)+n</math> and <math>F^*(n)=f^*(n)+n+1</math>. For functions defined in this way, the values of <math>F</math> and <math>F^*</math> (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.{{sfn|Lambek|1994}}
 ===Rayleigh's theorem===
@@ Line 57: / Line 58: @@
 [[Beatty sequence|Rayleigh's theorem]] states that for two positive [[irrational number]]s <math>r</math> and <math>s</math>, both greater than one, with <math>\tfrac1r+\tfrac1s=1</math>,
 the two sequences <math>\lfloor i\cdot r\rfloor</math> and <math>\lfloor i\cdot s\rfloor</math> for <math>i=1,2,3,\dots</math>, obtained by rounding down to an integer the multiples of <math>r</math> and <math>s</math>, are complementary. It can be seen as an instance of the Lambek–Moser theorem with <math>f(n)=\lfloor rn\rfloor-n</math> and <math>f^\ast(n)=\lfloor sn\rfloor-n</math>. The condition that <math>r</math> and <math>s</math> be greater than one implies that these two functions are non-decreasing; the derived functions are <math>F(n)=\lfloor rn\rfloor</math> and <math>F^*(n)=\lfloor sn\rfloor.</math> The sequences of values of <math>F</math> and <math>F^*</math> forming the derived partition are known as [[Beatty sequence]]s, after [[Samuel Beatty (mathematician)|Samuel Beatty]]'s 1926 rediscovery of Rayleigh's theorem.<ref>{{harvnb|Rayleigh|1894}}; {{harvnb|Beatty|1926}}; {{harvnb|Honsberger|1970}}, pp. 93–95; {{harvnb|Chamberland|2017}}.</ref>
-==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 (mathematician)|Samuel Beatty]] on [[Beatty sequence]]s 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 <math>F^*</math>.{{sfn|Lambek|Moser|1954}} [[Edsger W. Dijkstra]] has provided a [[proof without words|visual proof]] of the result,{{sfn|Dijkstra|1980}} and later another proof based on [[algorithm]]ic reasoning.{{sfn|Dijkstra|1982}} Yuval Ginosar has provided an intuitive proof based on an analogy of two athletes running in opposite directions around a circular racetrack.{{sfn|Ginosar|2014}}
 ==See also==
@@ Line 80: / Line 78: @@
  | title = Generalized Beatty sequences and complementary triples
  | volume = 8
- | year = 2019}}
+ | year = 2019| s2cid = 119176190
+ }}
 *{{citation
  | last = Angel | first = Myer
@@ Line 89: / Line 88: @@
  | title = Partitions of the natural numbers
  | volume = 7
- | year = 1964}}
+ | year = 1964| issue = 2
+ | s2cid = 123729929
+ | doi-access = free
+ }}
 *{{citation
  | last = Beatty | first = Samuel | author-link = Samuel Beatty (mathematician)
@@ Line 99: / Line 101: @@
  | title = Problem 3173
  | volume = 33
- | year = 1926}}; Solutions by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp.&nbsp;159–160, {{jstor|2298716}}
+ | year = 1926}}; Solutions by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp.&nbsp;159–160, {{JSTOR|2298716}}
 *{{citation
  | last = Brun | first = Viggo | author-link = Viggo Brun
@@ Line 106: / Line 108: @@
  | pages = 73–79
  | title = Rechenregel zur Bildung der <math>n</math>-ten Primzahl
- | trans-title = Calculating rules to build the <math>n</math>th prime
+ | trans-title = Calculating rules to build the {{nowrap|<math>n</math>th}} prime
  | volume = 13
  | year = 1931
@@ Line 139: / Line 141: @@
  | volume = 91
  | year = 1982
- | zbl = 0533.40001}}
+ | isbn = 978-90-277-1462-6 | zbl = 0533.40001}}
 *{{citation
  | last1 = Dos Reis | first1 = A. J.
  | last2 = Silberger | first2 = D. M.
- | doi = 10.2307/2691513
+ | doi = 10.1080/0025570X.1990.11977485
  | issue = 1
  | journal = Mathematics Magazine
+ | jstor = 2691513
  | mr = 1042938
  | pages = 53–55
  | title = Generating nonpowers by formula
+ | url = https://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/generating-nonpowers-by-formula
  | volume = 63
  | year = 1990}}
@@ Line 200: / Line 204: @@
  | title = Some Galois connections in elementary number theory
  | volume = 47
- | year = 1994}}
+ | year = 1994| doi-access = free
+ }}
 *{{citation
  | last1 = Lambek | first1 = Joachim | author1-link = Joachim Lambek
  | last2 = Moser | first2 = Leo | author2-link = Leo Moser
  | date = August–September 1954
- | doi = 10.2307/2308078
+ | doi = 10.1080/00029890.1954.11988496
  | issue = 7
  | journal = [[The American Mathematical Monthly]]
@@ Line 221: / Line 226: @@
  | title = An inversive algorithm
  | volume = 38
- | year = 1932}}
+ | year = 1932| doi-access = free
+ }}
 *{{citation
  | author = John William Strutt, Baron Rayleigh
@@ Line 243: / Line 249: @@
  | title = Lure of the Integers
  | url = https://books.google.com/books?id=DvX90EKMxGwC&pg=PA11
- | year = 1992}}
+ | year = 1992| jstor = 40148160
+ }}
 *{{citation
  | last = Wild | first = Roy E.
@@ Line 252: / Line 259: @@
  | url = https://projecteuclid.org/euclid.pjm/1103044611
  | volume = 5
- | year = 1955}}
+ | year = 1955| doi = 10.2140/pjm.1955.5.85
+ | doi-access = free
+ }}
 {{refend}}