Lambek–Moser theorem: Difference between revisions
ce |
m →References: more links for Dos Reis & Silberger |
||
Line 143: | Line 143: | ||
| last1 = Dos Reis | first1 = A. J. |
| last1 = Dos Reis | first1 = A. J. |
||
| last2 = Silberger | first2 = D. M. |
| last2 = Silberger | first2 = D. M. |
||
| doi = 10. |
| doi = 10.1080/0025570X.1990.11977485 |
||
| issue = 1 |
| issue = 1 |
||
| journal = Mathematics Magazine |
| journal = Mathematics Magazine |
||
| jstor = 2691513 |
|||
| mr = 1042938 |
| mr = 1042938 |
||
| pages = 53–55 |
| pages = 53–55 |
||
| title = Generating nonpowers by formula |
| title = Generating nonpowers by formula |
||
| url = https://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/generating-nonpowers-by-formula |
|||
| volume = 63 |
| volume = 63 |
||
| year = 1990}} |
| year = 1990}} |
Revision as of 22:36, 13 September 2022
In combinatorial number theory, the Lambek–Moser theorem defines a partition of the positive integers into two subsets from any non-decreasing integer-valued function and its inverse function. It is a generalization of Rayleigh's theorem, on the complementary Beatty sequences obtained by rounding down irrational multiples of the integers. If a formula is known for the th smallest member of a set of positive integers, the Lambek–Moser theorem can be used to derive a formula for the th positive integer not in the set.
All partitions of the positive integers into two complementary subsets can be defined in this way. 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 numbers and the odd numbers, the evil numbers and the odious numbers, the prime numbers and the non-primes (1 and the composite numbers), and the th powers and non-powers.
The Lambek–Moser theorem 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]
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
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 positive integers , Equivalently, may be defined as the number of values for which . It follows from either of these definitions that . Further, define two more functions and , from positive integers to positive integers, by Then the first part of the theorem states that and are strictly increasing and that the ranges of and form a partition of the positive integers. Each of these two functions maps any integer to the th element of its set in the partition.[3]
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 and are any two complementary increasing sequences of integers, one may construct a pair of functions and from which this partition may be derived using the Lambek–Moser theorem. To do so, define and .[3]
Limits of iterated inverses
In the same work in which they proved the Lambek–Moser theorem, Lambek and Moser provided a method of going directly from , the function giving the th member of a set of positive integers, to , the function giving the th non-member, without going through and . Let denote the number of values of for which ; this is an approximation to the inverse function of , but (because it uses in place of ) offset by one from the type of inverse used to define from . Then, for any , is the limit of the sequence meaning that this sequence eventually becomes constant and the value it takes when it does is .[4]
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 with the property that, for all and , if and only if . The corresponding functions and are defined slightly less symmetrically by and . For functions defined in this way, the values of and (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.[5]
Examples
For instance, consider the partition of positive integers into even and odd numbers, let be the th even positive integer, and let be the th odd positive integer. Then the 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. 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]
As another example, let , 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 . These two functions give and For the values of are the pronic numbers
- 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, ...
while the values of 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.[7] 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.[3]
Following earlier work of Viggo Brun and D. H. Lehmer,[9] 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 non-primes (1 and the composite numbers). If is the prime-counting function (number of primes less than or equal to ), then the th non-prime is given by the limit of the sequence[4]
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 th positive integer that is not a th power can be obtained from the limiting formula as[10]
Rayleigh's theorem
Rayleigh's theorem states that for two positive irrational numbers and , both greater than one, with , the two sequences and for , obtained by rounding down to an integer the multiples of and , are complementary. It can be seen as an instance of the Lambek–Moser theorem with and . The condition that and 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, after Samuel Beatty's 1926 rediscovery of Rayleigh's theorem.[11]
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 .[1] Edsger W. Dijkstra has provided a visual proof of the result,[12] and later another proof based on algorithmic reasoning.[13] Yuval Ginosar has provided an intuitive proof based on an analogy of two athletes running in opposite directions around a circular racetrack.[14]
See also
- Hofstadter Figure-Figure sequences, another pair of complementary sequences to which the Lambek–Moser theorem can be applied
Notes
- ^ a b Lambek & Moser 1954.
- ^ Wild 1955.
- ^ a b c Lambek & Moser 1954; Honsberger 1970, pp. 95–96; Fraenkel 1977.
- ^ a b Lambek & Moser 1954; Roberts 1992.
- ^ Lambek 1994.
- ^ Allouche & Dekking 2019.
- ^ Garry 1997.
- ^ Angel 1964.
- ^ Brun 1931; Lehmer 1932.
- ^ Honsberger 1970, pp. 97–100; Dos Reis & Silberger 1990; Roberts 1992.
- ^ Rayleigh 1894; Beatty 1926; Honsberger 1970, pp. 93–95; Chamberland 2017.
- ^ Dijkstra 1980.
- ^ Dijkstra 1982.
- ^ Ginosar 2014.
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
- Angel, Myer (1964), "Partitions of the natural numbers", Canadian Mathematical Bulletin, 7: 219–236, doi:10.4153/CMB-1964-020-1, MR 0161826
- 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 -ten Primzahl" [Calculating rules to build the 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, 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.2307/2308078, 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, 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, MR 0067912