Lambek–Moser theorem

File:Lambek–Moser.svgs {{nowrap|1, 3, 4, 6, ...}} and {{nowrap|2, 5, 7, 10, ... .}} These sequences round down the integer multiples of $\backslash varphi$ and $\backslash varphi+1$, where $\backslash 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),\backslash 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$,

Equivalently, $f^*(n)$ may be defined as the number of values $x$ for which

It follows from either of these definitions that $f^*\{\}^*=f$. If the two functions $f$ and $f^*$ are plotted as histograms, they form mirror images of each other across the diagonal line $x=y$.{{sfn|Garry|1997}}

From these two functions $f$ and $f^*$, define two more functions $F$ and $F^*$, from positive integers to positive integers, by

\begin{align}

F(n)&=f(n)+n\\

F^*(n)&=f^*(n)+n\\

\end{align}

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.{{harvnb|Lambek|Moser|1954}}; {{harvnb|Honsberger|1970}}, pp. 95–96; {{harvnb|Fraenkel|1977}}.

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)=\backslash lfloor\backslash sqrt\{n-1\}\backslash rfloor$.

These two functions give $F(n)=n^2+n$ and $F^*(n)=\backslash lfloor\backslash sqrt\{n-1\}\backslash rfloor+n.$

For $n=1,2,3,\backslash 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.{{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 $f$ with the appropriate properties.

File:Prime Lambek–Moser.svg (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 $S=s\_1,s\_2,\backslash dots$ and $S^*=s^*\_1,s^*\_2,\backslash 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$.

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 {{nowrap|$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.{{sfn|Allouche|Dekking|2019}}

In the same work in which they proved the Lambek–Moser theorem, Lambek and Moser provided a method of going directly {{nowrap|from $F$,}} the function giving the {{nowrap|$n$th}} member of a set of positive integers, {{nowrap|to $F^*$,}} the function giving the {{nowrap|$n$th}} non-member, without going through $f$ {{nowrap|and $f^*$.}} Let $F^\{\backslash \#\}(n)$ denote the number of values of $x$ for which $F(x)\backslash le\; n$; this is an approximation to the inverse function {{nowrap|of $F$,}} but (because it uses $\backslash le$ in place {{nowrap|of )}} offset by one from the type of inverse used to define $f^*$ {{nowrap|from $f$.}} Then, for {{nowrap|any $n$,}} $F^*(n)$ is the limit of the sequence

$$n,\; n+F^\{\backslash \#\}(n),\; n+F^\{\backslash \#\}\backslash bigl(n+F^\{\backslash \#\}(n)\backslash bigr),\; \backslash dots,$$

meaning that this sequence eventually becomes constant and the value it takes when it does {{nowrap|is $F^*(n)$.{{harvnb|Lambek|Moser|1954}}; {{harvnb|Roberts|1992}}.}}

Lambek and Moser used the prime numbers as an example, following earlier work by Viggo Brun and D. H. Lehmer.{{harvnb|Brun|1931}}; {{harvnb|Lehmer|1932}}. If $\backslash pi(n)$ is the prime-counting function (the number of primes less than or equal {{nowrap|to $n$),}} then the {{nowrap|$n$th}} non-prime (1 or a composite number) is given by the limit of the sequence

$$n,\; n+\backslash pi(n),\; n+\backslash pi\backslash bigl(n+\backslash pi(n)\backslash bigr),\; \backslash 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 {{nowrap|$n$th}} positive integer that is not a {{nowrap|$k$th}} power can be obtained from the limiting formula as{{harvnb|Honsberger|1970}}, pp. 97–100; {{harvnb|Dos Reis|Silberger|1990}}; {{harvnb|Roberts|1992}}.

$$n+\backslash left\backslash lfloor\backslash sqrt[k]\{n\; +\; \backslash lfloor\backslash sqrt[k]\{n\}\backslash rfloor\}\backslash right\backslash rfloor.$$

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^*$.{{sfn|Lambek|Moser|1954}} Edsger W. Dijkstra has provided a visual proof of the result,{{sfn|Dijkstra|1980}} and later another proof based on algorithmic 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}}

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)\backslash le\; y$ if and only if $x\backslash le\; 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.{{sfn|Lambek|1994}}

{{main|Beatty sequence}}

Rayleigh's theorem states that for two positive irrational numbers $r$ and $s$, both greater than one, with $\backslash tfrac1r+\backslash tfrac1s=1$,

the two sequences $\backslash lfloor\; i\backslash cdot\; r\backslash rfloor$ and $\backslash lfloor\; i\backslash cdot\; s\backslash rfloor$ for $i=1,2,3,\backslash 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)=\backslash lfloor\; rn\backslash rfloor-n$ and $f^\backslash ast(n)=\backslash lfloor\; sn\backslash 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)=\backslash lfloor\; rn\backslash rfloor$ and $F^*(n)=\backslash lfloor\; sn\backslash 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.{{harvnb|Rayleigh|1894}}; {{harvnb|Beatty|1926}}; {{harvnb|Honsberger|1970}}, pp. 93–95; {{harvnb|Chamberland|2017}}.

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

{{reflist|30em}}

{{refbegin|30em}}

• {{citation

| last1 = Allouche | first1 = Jean-Paul

| last2 = Dekking | first2 = F. Michel

| arxiv = 1809.03424

| doi = 10.2140/moscow.2019.8.325

| issue = 4

| journal = Moscow Journal of Combinatorics and Number Theory

| mr = 4026541

| pages = 325–341

| title = Generalized Beatty sequences and complementary triples

| volume = 8

| year = 2019| s2cid = 119176190

}}

• {{citation

| last = Angel | first = Myer

| doi = 10.4153/CMB-1964-020-1

| journal = Canadian Mathematical Bulletin

| mr = 161826

| pages = 219–236

| title = Partitions of the natural numbers

| volume = 7

| year = 1964| issue = 2

| s2cid = 123729929

| doi-access = free

}}

• {{citation

| last = Beatty | first = Samuel | author-link = Samuel Beatty (mathematician)

| doi = 10.2307/2300153

| issue = 3

| journal = The American Mathematical Monthly

| jstor = 2300153

| page = 159

| title = Problem 3173

| volume = 33

| year = 1926}}; Solutions by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp. 159–160, {{JSTOR|2298716}}

• {{citation

| last = Brun | first = Viggo | author-link = Viggo Brun

| journal = Norsk Matematisk Tidsskrift

| language = no

| pages = 73–79

| title = Rechenregel zur Bildung der $n$-ten Primzahl

| trans-title = Calculating rules to build the {{nowrap|$n$th}} prime

| volume = 13

| year = 1931

| zbl = 0003.14902}}, as cited by {{harvnb|Lambek|Moser|1954}}

• {{citation

| last = Chamberland | first = Marc

| contribution = Beatty sequences

| contribution-url = https://books.google.com/books?id=ZXGYDwAAQBAJ&pg=PA32

| isbn = 978-0-691-17569-0

| pages = 32–33

| publisher = Princeton University Press

| title = Single Digits: In Praise of Small Numbers

| year = 2017}}

• {{citation

| last = Dijkstra | first = Edsger W. | author-link = Edsger W. Dijkstra

| publisher = University of Texas

| series = Report EWD753

| title = On a theorem by Lambek and Moser

| url = https://www.cs.utexas.edu/users/EWD/ewd07xx/EWD753.PDF

| year = 1980}}

• {{citation

| last = Dijkstra | first = Edsger W. | author-link = Edsger W. Dijkstra

| editor1-last = Broy | editor1-first = Manfred

| editor2-last = Schmidt | editor2-first = Gunther

| contribution = Lambek and Moser revisited

| contribution-url = https://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD776.html

| doi = 10.1007/978-94-009-7893-5_2

| pages = 19–23

| publisher = D. Reidel Publishing Co.

| series = NATO Advanced Study Institutes Series, Series C – Mathematical and Physical Sciences

| title = 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

| volume = 91

| year = 1982

| isbn = 978-90-277-1462-6 | zbl = 0533.40001}}

• {{citation

| last1 = Dos Reis | first1 = A. J.

| last2 = Silberger | first2 = D. M.

| 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}}

• {{citation

| last = Fraenkel | first = Aviezri S. | author-link = Aviezri Fraenkel

| doi = 10.2307/2319931

| issue = 2

| journal = The American Mathematical Monthly

| jstor = 2319931

| mr = 429815

| pages = 114–115

| title = Complementary systems of integers

| volume = 84

| year = 1977}}

• {{citation

| last = Garry | first = Y. K. K.

| issue = 4

| journal = Mathematical Excalibur

| page = 2

| title = Inverse sequences and complementary sequences

| url = https://www.math.ust.hk/excalibur/v3_n4.pdf

| volume = 3

| year = 1997}}

• {{citation

| last = Ginosar | first = Yuval

| arxiv = 1207.5633

| journal = Integers

| pages = A09:1–A09:4

| title = On the Lambek–Moser theorem

| url = https://www.emis.de/journals/INTEGERS/papers/o9/o9.Abstract.html

| volume = 14

| year = 2014}}

• {{citation

| last = Honsberger | first = Ross | author-link = Ross Honsberger

| contribution = Essay 12: Complementary sequences

| isbn = 0-394-70923-3

| mr = 3155264

| pages = 93–110

| publisher = Random House, Inc. | location = New York

| series = New Mathematical Library

| title = Ingenuity in Mathematics

| volume = 23

| year = 1970}}

• {{citation

| last = Lambek | first = Joachim | author-link = Joachim Lambek

| doi = 10.1006/jnth.1994.1043

| issue = 3

| journal = Journal of Number Theory

| mr = 1278405

| pages = 371–377

| title = Some Galois connections in elementary number theory

| volume = 47

| 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.1080/00029890.1954.11988496

| issue = 7

| journal = The American Mathematical Monthly

| jstor = 2308078

| pages = 454–458

| title = Inverse and complementary sequences of natural numbers

| volume = 61}}

• {{citation

| last = Lehmer | first = D. H. | author-link = D. H. Lehmer

| doi = 10.1090/S0002-9904-1932-05496-9

| issue = 10

| journal = Bulletin of the American Mathematical Society

| mr = 1562488

| pages = 693–694

| title = An inversive algorithm

| volume = 38

| year = 1932| doi-access = free

}}

• {{citation

| author = John William Strutt, Baron Rayleigh

| author-link = John William Strutt, 3rd Baron Rayleigh

| edition = 2nd

| page = 123

| publisher = Macmillan

| ref = CITEREFRayleigh1894

| title = The Theory of Sound

| url = https://books.google.com/books?id=EGQSAAAAIAAJ&pg=PA123

| volume = 1

| year = 1894}}

• {{citation

| last = Roberts | first = Joe

| doi = 10.2307/40148160

| isbn = 0-88385-502-X

| mr = 1189138

| page = 11

| publisher = Mathematical Association of America | location = Washington, DC

| series = MAA Spectrum

| title = Lure of the Integers

| url = https://books.google.com/books?id=DvX90EKMxGwC&pg=PA11

| year = 1992| jstor = 40148160

}}

• {{citation

| last = Wild | first = Roy E.

| journal = Pacific Journal of Mathematics

| mr = 67912

| pages = 85–91

| title = On the number of primitive Pythagorean triangles with area less than {{mvar|n}}

| url = https://projecteuclid.org/euclid.pjm/1103044611

| volume = 5

| year = 1955| doi = 10.2140/pjm.1955.5.85

| doi-access = free

}}

{{refend}}

{{DEFAULTSORT:Lambek-Moser theorem}}

Category:Integer sequences

Category:Theorems in number theory