Teorema de Lambek-Moser

En particiones enteras de funciones monótonas

El teorema de Lambek-Moser es una descripción matemática de las particiones de los números naturales en dos conjuntos complementarios . Por ejemplo, se aplica a la partición de números en pares e impares , o en primos y no primos (uno y números compuestos ). El teorema de Lambek-Moser consta de dos partes. Una parte establece que dos funciones enteras no decrecientes cualesquiera que sean inversas, en cierto sentido, pueden usarse para dividir los números naturales en dos subconjuntos complementarios, y la otra parte establece que toda partición complementaria puede construirse de esta manera. Cuando se conoce una fórmula para el enésimo número natural de un conjunto, se puede utilizar el teorema de Lambek-Moser para obtener una fórmula para el enésimo número que no está en el conjunto. ${\displaystyle n}$ ${\displaystyle n}$

El teorema de Lambek-Moser pertenece a la teoría combinatoria de números . Lleva el nombre de Joachim Lambek y Leo Moser , quienes lo publicaron en 1954, ^[1] y debe distinguirse de un teorema no relacionado de Lambek y Moser, posteriormente reforzado por Wild, sobre el número de ternas pitagóricas primitivas . ^[2] Amplía el teorema de Rayleigh, que describe pares complementarios de secuencias de Beatty , las secuencias de múltiplos redondeados de números irracionales.

De funciones a particiones

Las cuatro funciones , , , y , para las dos secuencias de Beatty 1, 3, 4, 6, ... y 2, 5, 7, 10, ... . Estas secuencias redondean hacia abajo los múltiplos enteros de y , donde está la proporción áurea . ${\displaystyle f}$ ${\displaystyle f^{*}}$ ${\displaystyle F}$ ${\displaystyle F^{*}}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi +1}$ ${\displaystyle \varphi }$

Sea cualquier función, desde enteros positivos hasta enteros no negativos, que sea no decreciente (cada valor de la secuencia es al menos tan grande como cualquier valor anterior) y ilimitada (eventualmente aumenta más allá de cualquier valor fijo). La secuencia de sus valores puede omitir algunos números, por lo que es posible que no tenga una función inversa con las mismas propiedades. En su lugar, defina una función entera no decreciente y ilimitada que sea lo más cercana posible a la inversa en el sentido de que, para todos los números enteros positivos , ${\displaystyle f}$ ${\displaystyle f(1),f(2),f(3),\dots }$ ${\displaystyle f^{*}}$ ${\displaystyle n}$

$${\displaystyle f{\bigl (}f^{*}(n){\bigr )}<n\leq f{\bigl (}f^{*}(n)+1{\bigr )}.}$$

^[3]histogramas^[4] ${\displaystyle f^{*}(n)}$ ${\displaystyle x}$ ${\displaystyle f(x)<n}$ ${\displaystyle f^{*}{}^{*}=f}$ ${\displaystyle f}$ ${\displaystyle f^{*}}$ ${\displaystyle x=y}$

A partir de estas dos funciones y , define dos funciones más y , de enteros positivos a enteros positivos, por ${\displaystyle f}$ ${\displaystyle f^{*}}$ ${\displaystyle F}$ ${\displaystyle F^{*}}$

$${\displaystyle {\begin{aligned}F(n)&=f(n)+n\\F^{*}(n)&=f^{*}(n)+n\\\end{aligned}}}$$

^[3] ${\displaystyle F}$ ${\displaystyle F^{*}}$ ${\displaystyle F}$ ${\displaystyle F^{*}}$ ${\displaystyle n}$ ${\displaystyle n}$

Como ejemplo de la construcción de una partición a partir de una función, sea , la función que eleva al cuadrado su argumento. Entonces su inversa es la función de raíz cuadrada , cuya aproximación entera más cercana (en el sentido utilizado para el teorema de Lambek-Moser) es . Estas dos funciones dan y Para los valores de son los números pronicos ${\displaystyle f(n)=n^{2}}$ ${\displaystyle f^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor }$ ${\displaystyle F(n)=n^{2}+n}$ ${\displaystyle F^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor +n.}$ ${\displaystyle n=1,2,3,\dots }$ ${\displaystyle F}$

2, 6, 12, 20, 30, 42, 56, 72, 90, 110, ...

mientras que los valores de son ${\displaystyle F^{*}}$

1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, ....

Estas dos secuencias son complementarias: cada número entero positivo pertenece exactamente a una de ellas. ^[4] El teorema de Lambek-Moser establece que este fenómeno no es específico de los números pronicos, sino que surge de cualquier elección con las propiedades apropiadas. ^[3] ${\displaystyle f}$

De particiones a funciones

Las dos funciones (flechas azules hacia la derecha) y (flechas rojas hacia la izquierda) que surgen de la partición de números enteros positivos en primos (2, 3, 5, 7, ...) y no primos (1, 4, 6, 8, . ..). Visualización basada en un método de Ángel. ^[5] ${\displaystyle f}$ ${\displaystyle f^{*}}$

La segunda parte del teorema de Lambek-Moser establece que esta construcción de particiones a partir de funciones inversas es universal, en el sentido de que puede explicar cualquier partición de números enteros positivos en dos partes infinitas. Si y son dos secuencias crecientes complementarias de números enteros, se pueden construir un par de funciones y de las cuales se puede derivar esta partición utilizando el teorema de Lambek-Moser. Para ello, defina y . ^[3] ${\displaystyle S=s_{1},s_{2},\dots }$ ${\displaystyle S^{*}=s_{1}^{*},s_{2}^{*},\dots }$ ${\displaystyle f}$ ${\displaystyle f^{*}}$ ${\displaystyle f(n)=s_{n}-n}$ ${\displaystyle f^{*}(n)=s_{n}^{*}-n}$

Uno de los ejemplos más simples al que se podría aplicar esto es la partición de números enteros positivos en números pares e impares . Las funciones y deberían dar el número par o impar, respectivamente, entonces y . De estos se derivan las dos funciones y . Forman un par inverso, y la partición generada mediante el teorema de Lambek-Moser a partir de este par es simplemente la partición de los números enteros positivos en números pares e impares. Otra partición de enteros, en números malos y números odiosos (por la paridad de la representación binaria ) utiliza casi las mismas funciones, ajustadas por los valores de la secuencia Thue-Morse . ^[6] ${\displaystyle F(n)}$ ${\displaystyle F^{*}(n)}$ ${\displaystyle n}$ ${\displaystyle F(n)=2n}$ ${\displaystyle F^{*}(n)=2n-1}$ ${\displaystyle f(n)=F(n)-n=n}$ ${\displaystyle f^{*}(n)=F^{*}(n)-n=n-1}$

Fórmula límite

En el mismo trabajo en el que demostraron el teorema de Lambek-Moser, Lambek y Moser proporcionaron un método para ir directamente desde , ${\displaystyle F}$ la función que da el enésimo miembro de un conjunto de enteros positivos, a , la función que da el enésimo no miembro, sin pasando por y . Denotemos el número de valores de para los cuales ; esta es una aproximación a la función inversa de , pero (porque se usa en lugar de ) compensada en uno del tipo de inversa utilizada para definir from . Entonces, para cualquiera , es el límite de la secuencia ${\displaystyle n}$ ${\displaystyle F^{*}}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle f^{*}}$ ${\displaystyle F^{\#}(n)}$ ${\displaystyle x}$ ${\displaystyle F(x)\leq n}$ ${\displaystyle F}$ ${\displaystyle \leq }$ ${\displaystyle <}$ ${\displaystyle f^{*}}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle F^{*}(n)}$

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

es . ^[7] ${\displaystyle F^{*}(n)}$

Lambek y Moser utilizaron los números primos como ejemplo, siguiendo trabajos anteriores de Viggo Brun y DH Lehmer . ^[8] Si es la función de conteo de primos (el número de primos menor o igual que ), entonces el ésimo no primo (1 o un número compuesto ) viene dado por el límite de la secuencia ^[7] ${\displaystyle \pi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$

$${\displaystyle n,n+\pi (n),n+\pi {\bigl (}n+\pi (n){\bigr )},\dots }$$

Para algunas otras secuencias de números enteros, el límite correspondiente converge en un número fijo de pasos y es posible una fórmula directa para la secuencia complementaria. En particular, el enésimo entero positivo que no es una enésima potencia se puede obtener a partir de la fórmula limitante como ^[9] ${\displaystyle n}$ ${\displaystyle k}$

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

Historia y pruebas

El teorema fue descubierto por Leo Moser y Joachim Lambek , quienes lo publicaron en 1954. Moser y Lambek citan como inspiración el trabajo anterior de Samuel Beatty sobre las secuencias de Beatty , y también citan el trabajo de Viggo Brun y DH Lehmer desde principios de la década de 1930 en adelante. métodos relacionados con su fórmula limitante para . ^[1] Edsger W. Dijkstra ha proporcionado una prueba visual del resultado, ^[10] y posteriormente otra prueba basada en razonamiento algorítmico . ^[11] Yuval Ginosar ha proporcionado una prueba intuitiva basada en una analogía de dos atletas corriendo en direcciones opuestas alrededor de una pista circular. ^[12] ${\displaystyle F^{*}}$

Resultados relacionados

Para números enteros no negativos

Una variación del teorema se aplica a particiones de números enteros no negativos, en lugar de a particiones de números enteros positivos. Para esta variación, cada partición corresponde a una conexión de Galois de los enteros ordenados no negativos entre sí. Este es un par de funciones no decrecientes con la propiedad de que, para todos y , si y solo si . Las funciones correspondientes y están definidas de forma ligeramente menos simétrica por y . Para funciones definidas de esta manera, los valores de y (para argumentos no negativos, en lugar de argumentos positivos) forman una partición de los enteros no negativos, y cada partición se puede construir de esta manera. ^[13] ${\displaystyle (f,f^{*})}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle f(x)\leq y}$ ${\displaystyle x\leq f(y)}$ ${\displaystyle F}$ ${\displaystyle F^{*}}$ ${\displaystyle F(n)=f(n)+n}$ ${\displaystyle F^{*}(n)=f^{*}(n)+n+1}$ ${\displaystyle F}$ ${\displaystyle F^{*}}$

teorema de rayleigh

El teorema de Rayleigh establece que para dos números irracionales positivos y , ambos mayores que uno, con , las dos secuencias y para , obtenidas redondeando a la baja a un número entero los múltiplos de y , son complementarios. Puede verse como un ejemplo del teorema de Lambek-Moser con y . La condición de que y sea mayor que uno implica que estas dos funciones no son decrecientes; las funciones derivadas son y Las secuencias de valores de y que forman la partición derivada se conocen como secuencias de Beatty , después del redescubrimiento del teorema de Rayleigh por Samuel Beatty en 1926. ^[14] ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle {\tfrac {1}{r}}+{\tfrac {1}{s}}=1}$ ${\displaystyle \lfloor i\cdot r\rfloor }$ ${\displaystyle \lfloor i\cdot s\rfloor }$ ${\displaystyle i=1,2,3,\dots }$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle f(n)=\lfloor rn\rfloor -n}$ ${\displaystyle f^{\ast }(n)=\lfloor sn\rfloor -n}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle F(n)=\lfloor rn\rfloor }$ ${\displaystyle F^{*}(n)=\lfloor sn\rfloor .}$ ${\displaystyle F}$ ${\displaystyle F^{*}}$

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

1. Lambek y Moser 1954.
2. Salvaje 1955.
3. Lambek y Moser 1954; Honsberger 1970, págs. 95–96; Fraenkel 1977.
4. Garry 1997.
5. Ángel 1964.
6. Allouche y Dekking 2019.
7. Lambek y Moser 1954; Roberts 1992.
8. Brun 1931; Lehmer 1932.
9. Honsberger 1970, págs. 97-100; Dos Reis y Silberger 1990; Roberts 1992.
10. Dijkstra 1980.
11. Dijkstra 1982.
12. Ginósar 2014.
13. Lambek 1994.
14. Rayleigh 1894; Beatty 1926; Honsberger 1970, págs. 93–95; Chamberland 2017.

Referencias

• Allouche, Jean-Paul; Dekking, F. Michel (2019), "Secuencias Beatty generalizadas y tripletas complementarias", Revista de Moscú de combinatoria y teoría de números , 8 (4): 325–341, arXiv : 1809.03424 , doi : 10.2140/moscow.2019.8.325, SEÑOR  4026541, S2CID  119176190
• Angel, Myer (1964), "Particiones de los números naturales", Canadian Mathematical Bulletin , 7 (2): 219–236, doi : 10.4153/CMB-1964-020-1 , MR  0161826, S2CID  123729929
• Beatty, Samuel (1926), "Problema 3173", The American Mathematical Monthly , 33 (3): 159, doi :10.2307/2300153, JSTOR  2300153; Soluciones de Beatty, A. Ostrowski, J. Hyslop y AC Aitken, vol. 34 (1927), págs. 159-160, JSTOR  2298716
• Brun, Viggo (1931), "Rechenregel zur Bildung der -ten Primzahl" [Cálculo de reglas para construir el número primo], Norsk Matematisk Tidsskrift (en noruego), 13 : 73–79, Zbl  0003.14902 ${\displaystyle n}$ ${\displaystyle n}$, citado por Lambek y Moser 1954
• Chamberland, Marc (2017), "Secuencias Beatty", Dígitos únicos: elogio de los números pequeños , Princeton University Press, págs. 32-33, ISBN 978-0-691-17569-0
• Dijkstra, Edsger W. (1980), Sobre un teorema de Lambek y Moser (PDF) , Informe EWD753, Universidad de Texas
• Dijkstra, Edsger W. (1982), "Lambek y Moser revisitados", en Broy, Manfred; Schmidt, Gunther (eds.), Fundamentos teóricos de la metodología de programación: notas de conferencias de una escuela de verano internacional, dirigida por FL Bauer, EW Dijkstra y CAR Hoare , Serie de Institutos de estudios avanzados de la OTAN, Serie C – Ciencias físicas y matemáticas, vol. 91, D. Reidel Publishing Co., págs. 19–23, doi :10.1007/978-94-009-7893-5_2, ISBN 978-90-277-1462-6, Zbl  0533.40001
• Dos Reis, AJ; Silberger, DM (1990), "Generación de no potencias mediante fórmula", Mathematics Magazine , 63 (1): 53–55, doi :10.1080/0025570X.1990.11977485, JSTOR  2691513, MR  1042938
• Fraenkel, Aviezri S. (1977), "Sistemas complementarios de números enteros", The American Mathematical Monthly , 84 (2): 114–115, doi :10.2307/2319931, JSTOR  2319931, MR  0429815
• Garry, YKK (1997), "Secuencias inversas y secuencias complementarias" (PDF) , Mathematical Excalibur , 3 (4): 2
• Ginosar, Yuval (2014), "Sobre el teorema de Lambek-Moser", Enteros , 14 : A09:1–A09:4, arXiv : 1207.5633
• Honsberger, Ross (1970), "Ensayo 12: Secuencias complementarias", Ingenuity in Mathematics , New Mathematical Library, vol. 23, Nueva York: Random House, Inc., págs. 93-110, ISBN 0-394-70923-3, SEÑOR  3155264
• Lambek, Joachim (1994), "Algunas conexiones de Galois en la teoría elemental de números", Journal of Number Theory , 47 (3): 371–377, doi : 10.1006/jnth.1994.1043 , MR  1278405
• Lambek, Joaquín ; Moser, Leo (agosto-septiembre de 1954), "Secuencias inversas y complementarias de números naturales", The American Mathematical Monthly , 61 (7): 454–458, doi :10.1080/00029890.1954.11988496, JSTOR  2308078
• Lehmer, DH (1932), "Un algoritmo inversivo", Boletín de la Sociedad Matemática Estadounidense , 38 (10): 693–694, doi : 10.1090/S0002-9904-1932-05496-9 , SEÑOR  1562488
• John William Strutt, Baron Rayleigh (1894), La teoría del sonido, vol. 1 (2ª ed.), Macmillan, pág. 123
• Roberts, Joe (1992), El atractivo de los números enteros, MAA Spectrum, Washington, DC: Asociación Matemática de América, pág. 11, doi :10.2307/40148160, ISBN 0-88385-502-X, JSTOR  40148160, SEÑOR  1189138
• Wild, Roy E. (1955), "Sobre el número de triángulos pitagóricos primitivos con un área menor que n", Pacific Journal of Mathematics , 5 : 85–91, doi : 10.2140/pjm.1955.5.85 , MR  0067912