Lambek–Moser theorem

Lambek–Moser theorem In 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. inversement, 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.[1] Contenu 1 Énoncé du théorème 2 Exemple 3 Beatty's theorem 4 Universality 5 Voir également 6 Remarques 7 References Statement of the theorem The theorem applies to any non-decreasing and unbounded function f that maps positive integers to non-negative integers. From any such function f, define f * to be the integer-valued function that is as close as possible to the inverse function of f, dans le sens où, for all n, f (f *(n)) < n ≤ f (f *(n) + 1). It follows from this definition that f ** = f. Further, let F(n) = f (n) + n and G(n) = f *(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 f (n) = n2;[2] then {displaystyle f^{ast }(n)=lfloor {sqrt {n-1}}rfloor } . Thus F(n) = n2 + n and {displaystyle 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 f 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, {style d'affichage f(n)=lfloor rnrfloor -n} et {style d'affichage f^{dernièrement }(n)=lfloor snrfloor -n,} où {style d'affichage {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 {style d'affichage F(n)=lfloor rnrfloor } et {style d'affichage G(n)=lfloor snrfloor .} The sequences of values of F and G forming the derived partition are known as Beatty sequences.

Universality The Lambek–Moser theorem is universal, in the sense that it can explain any partition of the integers into two infinite parts. If S = s1,s2,... and T = t1,t2,... are any two infinite subsets forming a partition of the integers, one may construct a pair of functions f and f * from which this partition may be derived using the Lambek–Moser theorem: define f (n) = sn − n and f *(n) = tn − n.

Par exemple, consider the partition of integers into even and odd numbers: let S be the even numbers and T be the odd numbers. Then sn = 2n, so f (n) = n and similarly f *(n) = n − 1. These two functions f and f * 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.

Lambek and Moser discuss formulas involving the prime-counting function for the functions f and f * arising in this way from the partition of the positive integers into prime numbers and composite numbers.

See also Hofstadter Figure-Figure sequences, another pair of complementary sequences to which the Lambek–Moser theorem can be applied Notes ^ For another proof, voir "A proof for the Lambek and Moser theorem" (PDF), Mathematical Excalibur, 4 (1): 2, 1998 ^ Example from Garry, Oui. K. K. (1997), "Inverse sequences and complementary sequences" (PDF), Mathematical Excalibur, 3 (4): 2 References Beatty, Samuel (1926), "Problème 3173", Mensuel mathématique américain, 33 (3): 159, est ce que je:10.2307/2300153 Solutions by Beatty, UN. Ostrowski, J. Hyslop, et un. C. Aitken, volume. 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", Le mensuel mathématique américain, 61 (7): 454–458, est ce que je:10.2307/2308078 Catégories: Integer sequencesTheorems in number theory

Si vous voulez connaître d'autres articles similaires à Lambek–Moser theorem vous pouvez visiter la catégorie Integer sequences.

Laisser un commentaire

Votre adresse email ne sera pas publiée.


Nous utilisons nos propres cookies et ceux de tiers pour améliorer l'expérience utilisateur Plus d'informations