En la teoría combinatoria de números , el teorema de Lambek-Moser es una generalización del teorema de Beatty que define una partición de los enteros positivos en dos subconjuntos de cualquier función monótona con valores enteros. A la inversa, cualquier partición de los enteros positivos en dos subconjuntos puede definirse a partir de una función monótona de esta manera.
El teorema fue descubierto por Leo Moser y Joachim Lambek . Dijkstra (1980) proporciona una prueba visual del resultado. [1]
Declaración del teorema
El teorema se aplica a cualquier función f no decreciente e ilimitada que mapea enteros positivos con enteros no negativos. A partir de cualquier función f , defina f * como la función con valores enteros que está lo más cerca posible de la función inversa de f , en el sentido de que, para todo n ,
- f ( f * ( n )) < n ≤ f ( f * ( n ) + 1) .
De esta definición se deduce que f ** = f . Además, deja
- F ( n ) = f ( n ) + n y G ( n ) = f * ( n ) + n .
Entonces, el resultado indica que F y G aumentan estrictamente y que los rangos de F y G forman una partición de los enteros positivos.
Ejemplo
Sea f ( n ) = n 2 ; [2] entonces. Por tanto, F ( n ) = n 2 + n yPara n = 1, 2, 3, ... los valores de F son los números pronicos
- 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, ...
mientras que los valores de G son
- 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, ....
Estas dos secuencias son complementarias: cada entero positivo pertenece exactamente a una de ellas. El teorema de Lambek-Moser establece que este fenómeno no es específico de los números pronicos, sino que surge para cualquier elección de f con las propiedades apropiadas.
Teorema de beatty
El teorema de Beatty , que define una partición de los enteros a partir de redondear sus múltiplos por un número irracional r > 1 , puede verse como un ejemplo del teorema de Lambek-Moser. En el teorema de Beatty, y dónde . La condición de que r (y por lo tanto s ) sea mayor que uno implica que estas dos funciones no son decrecientes; las funciones derivadas son y Las secuencias de valores de F y G que forman la partición derivada se conocen como secuencias de Beatty.
Universalidad
El teorema de Lambek-Moser es universal, en el sentido de que puede explicar cualquier partición de los números enteros en dos partes infinitas. Si S = s 1 , s 2 , ... y T = t 1 , t 2 , ... son dos subconjuntos infinitos que forman una partición de los enteros, se puede construir un par de funciones f y f * a partir de las cuales este La partición se puede derivar usando el teorema de Lambek-Moser: defina f ( n ) = s n - n y f * ( n ) = t n - n .
Por ejemplo, considere la partición de números enteros en números pares e impares : sean S los números pares y T los impares. Entonces s n = 2 n , entonces f ( n ) = n y de manera similar f * ( n ) = n - 1 . Estas dos funciones f y f * forman un par inverso, y la partición generada mediante el teorema de Lambek-Moser a partir de este par es solo la partición de los enteros positivos en números pares e impares.
Lambek y Moser discutir fórmulas que implican la función principal de conteo para las funciones f y f * que surge de esta manera desde la partición de los números enteros positivos en números primos y números compuestos .
Ver también
- Secuencias figura-figura de Hofstadter , otro par de secuencias complementarias a las que se puede aplicar el teorema de Lambek-Moser
Notas
- ^ Para ver otra prueba, consulte "Una prueba del teorema de Lambek y Moser" (PDF) , Excalibur matemático , 4 (1): 2, 1998
- ^ Ejemplo de Garry, YKK (1997), "Secuencias inversas y secuencias complementarias" (PDF) , Excalibur matemático , 3 (4): 2
Referencias
- Beatty, Samuel (1926), "Problema 3173", American Mathematical Monthly , 33 (3): 159, doi : 10.2307 / 2300153 CS1 maint: parámetro desalentado ( enlace ) Soluciones de Beatty, A. Ostrowski, J. Hyslop y AC Aitken, vol. 34 (1927), págs. 159-160.
- Dijkstra, Edsger W. (1980), Sobre un teorema de Lambek y Moser (PDF) , Informe EWD753, Universidad de Texas CS1 maint: parámetro desalentado ( enlace ).
- Lambek, Joachim ; Moser, Leo (agosto-septiembre de 1954), "Secuencias inversas y complementarias de números naturales", The American Mathematical Monthly , 61 (7): 454–458, doi : 10.2307 / 2308078