Artículos

1.7: Teoría combinatoria de números - Matemáticas


Hay muchas preguntas interesantes que se encuentran entre la teoría de números y el análisis combinatorio. están separados en n clases, entonces al menos una clase contendrá elementos (a ), (b ), (c ) con (a + b = c ).

Considere el hecho de que si separamos los enteros positivos menores que (2 ^ n ) en clases (n ) poniendo 1 en la clase 1, los siguientes 2 en la clase 2, los siguientes 4 en la clase 3, etc. entonces ninguna clase contiene la suma de dos de sus elementos. Alternativamente, podríamos escribir cada entero m en la forma (2 ^ k theta ) donde ( theta ) es impar, y colocar (m ) en la (k ) ésima clase. Nuevamente, los números menores que (2 ^ n ) estarán en (n ) clases y si (m_1 = 2 ^ k theta_1 ) y (m_2 = 2 ^ k theta_2 ) están en la clase (k ) entonces (m_1 + m_2 = 2 ^ k ( theta_1 + theta_2) ) se encuentra en una clase con un número más alto. La forma más complicada de distribuir enteros que se describe a continuación nos permite distribuir 1, 2, ..., ( dfrac {3 ^ n − 1} {2} ) en (n ) clases de tal manera que ninguna clase tiene una solución para (a + b = c ):

1 2 5
3 4 6
10 11 7
13 12 8
. .
. .

Por otro lado, el teorema de Schur establece que si se separan los números 1, 2, 3,. , ([n! e] ) en clases (n ) de cualquier manera, entonces al menos una clase contendrá una solución a (a + b = c ). La brecha entre las dos últimas afirmaciones revela un problema interesante sin resolver, a saber, ¿se puede reemplazar la ([n! E] ) en el resultado de Schur por un número considerablemente menor? Los dos primeros ejemplos dados muestran que ciertamente no podemos ir tan bajo como (2n - 1 ), y el último ejemplo muestra que no podemos ir tan bajo como ( dfrac {3 ^ n − 1} {2} ) .

A continuación, damos una definición y hacemos varias observaciones para facilitar la demostración del teorema de Schur.

Sea (T_0 = 1 ), (T_n = nT_ {n − 1} + 1 ). Se comprueba fácilmente que

(T_n = n! (1 + dfrac {1} {1!} + Dfrac {2} {2!} Cdot cdot cdot + dfrac {1} {n!}) = [N! E ]. )

Por lo tanto, el teorema de Schur se puede reformular de la siguiente manera: si 1, 2, ..., (T_n ) se separan en (n ) clases de cualquier manera, al menos una clase contendrá una solución de (a + b = c ). Demostraremos esto asumiendo que los números 1, 2, ..., (T_n ) se han clasificado de n maneras sin que ninguna clase contenga una solución de (a + b = c ) y de esto se obtenga una contradicción. Tenga en cuenta que la condición (a + b ne c ) significa que ninguna clase puede contener la diferencia de dos de sus elementos.

Supongamos que alguna clase, digamos (A ), contiene elementos (a_1

(b_1 = a_2 - a_1, b_2 = a_3 - a_1, b_3 = a_4 - a_1, ... )
(c_1 = b_2 - b_1, c_2 = b_3 - b_1, c_3 = b_4 - b_1, ... )
(d_1 = c_2 - c_1, d_2 = c_3 - c_1, d_3 = c_4 - c_1, ... )

y así. Observamos que todas las (b ), (c ), (d ), etc., son diferencias de (a ) y, por lo tanto, no pueden estar en (A ).

Ahora, comenzamos con los elementos (T_n ). Por lo menos

( lfloor dfrac {T_n} {n} + 1 rfloor = T_ {n - 1} + 1 )

de estos deben estar en una sola clase, digamos (A_1 ). Luego formamos (T_ {n - 1} ) (b ) 's. Estos no se encuentran en (A_1 ) y, por lo tanto, se encuentran en las clases (n - 1 ) restantes. Por lo menos

( lfloor dfrac {T_ {n - 1}} {n - 1} + 1 rfloor = T_ {n - 1} + 1 )

de ellos deben estar en una sola clase, digamos (A_2 ). Forma sus diferencias (T_ {n - 2} ), las (c ). Éstos producen (T_ {n - 2} ) números ni en (A_1 ) ni en (A_2 ). Continuar de esta manera produce (T_ {n - 3} ) números que no están en (A_1, A_2, A_3 ). De esta manera eventualmente obtenemos (T_0 = 1 ) número que no pertenece a (A_1, A_2, ..., A_n ). Pero todos los números formados están entre los números (1, 2, ..., T_n ) por lo que tenemos una contradicción, que prueba el teorema.

Declaramos, sin prueba, la conexión con el último teorema de Fermat. Un enfoque natural del teorema de Fermat sería tratar de demostrar que (x ^ n + y ^ n = z ^ n ) (mod (p )) es insoluble en módulo algunos (p ), siempre que (p ) no divide (x cdot y cdot z ). Sin embargo, el teorema de Schur puede usarse para demostrar que este método debe fallar y, de hecho, si (p> n! E ) entonces (x ^ n + y ^ n = z ^ n ) (mod (p )) tiene una solución con (p ) no un factor de (xyz ).

Algo relacionado con el teorema de Schur es un famoso teorema de Van der Waerden, que investigamos brevemente. A principios de la década de 1920, surgió el siguiente problema en relación con la teoría de la distribución de residuos cuadráticos. Imagine el conjunto de todos los números enteros divididos de cualquier manera en dos clases. ¿Se puede afirmar que se pueden encontrar progresiones aritméticas de longitud arbitraria en al menos una de estas clases? El problema permaneció sin resolver durante varios años a pesar de los esfuerzos concentrados de muchos matemáticos destacados. Finalmente fue resuelto en 1928 por Van der Waerden. Como no es infrecuente con estos problemas, el primer paso de Van der Waerden fue hacer el problema más general y, por tanto, más fácil.

Van der Waerden demostró lo siguiente: Dados los números enteros (k ) y ( ell ), existe un número entero (W = W (k, ell) ) tal que si los números 1, 2, 3, ..., (W ) se separan en (k ) clases de cualquier manera, entonces al menos una clase contendrá l términos en progresión aritmética. No daremos aquí la prueba de Van der Waerden. Es extremadamente complicado, difícil de ver a través y solo conduce a un límite fantásticamente grande para W (k, l). Por esta razón, el lector podría considerar el valioso problema sin resolver de encontrar una prueba alternativa más simple de que (W (k, ell) ) existe y encontrar límites razonables para ella. Tendremos algo más que decir sobre la función (W (k, ell) ) un poco más tarde.

Nuestro próximo problema de la teoría combinatoria de números se ocupa de las secuencias "no promediadoras". Llamamos a una secuencia (A: a_1

Dado un número (x ), escrito en base diez, decidimos si (x ) está en (R ) sobre la base de las siguientes reglas.

Primero encerramos (x ) entre corchetes, poniendo el primer dígito (contando de derecha a izquierda) en el primer corchete, los dos siguientes en el segundo corchete, los tres siguientes en el tercer corchete, y así sucesivamente. Si el último corchete no vacío (el corchete más a la izquierda que no consta completamente de ceros) no tiene un número máximo de dígitos, lo llenamos con ceros. Por ejemplo, los números

(a = 32653200200 ), (b = 100026000150600 ), (c = 1000866600290500 )

estaría entre corchetes

(a = (00003) (2653) (200) (20) (0), )
(b = (10002) (6100) (150) (60) (0), )
(c = (10008) (6600) (290) (50) (0), )

respectivamente. Ahora suponga que el corchete (r ^ { text {th}} ) en (x ) contiene dígitos distintos de cero, pero todos los corchetes adicionales a la izquierda son 0. Llame al número representado por los dígitos en el (i ^ { text {th}} ) corchete (x_i ), (i = 1, 2, ..., r - 2 ). Además, denote por ( bar {x} ) el número representado por el dígito en los dos últimos corchetes tomados juntos, pero excluyendo el último dígito. Para que (x ) pertenezca a (R ) requerimos

  1. el último dígito de (x ) debe ser 1,
  2. (x_i ) debe comenzar con 0 para (i = 1, 2, ..., r - 2, )
  3. (x_1 ^ 2 + cdot cdot cdot x_ {r - 2} ^ 2 = bar {x}. )

En particular, observe que a satisface (2) pero viola (1) y (3) de modo que (a ) no está en (R ); pero (b ) y (c ) satisfacen las tres condiciones y están en (R ). Para comprobar (3) no es que (60 ^ 2 + 150 ^ 2 = 26100 ).

A continuación, probamos que no hay tres números enteros en (R ) en progresión aritmética. En primer lugar, observe que si dos elementos de 9R ) tienen un número diferente de paréntesis no vacíos, su promedio no puede satisfacer (1). Por lo tanto, solo necesitamos considerar promedios de elementos de (R ) que tienen el mismo número de paréntesis no vacíos. De (1) y (3) se deduce que los dos elementos de (R ) se pueden promediar paréntesis por paréntesis para los primeros (r - 2 ) paréntesis y también para los dos últimos paréntesis tomados juntos. Así, en nuestro ejemplo,

( dfrac {1} {2} (60 + 50) = 55, dfrac {1} {2} (150 + 290) = 220, )
( dfrac {1} {2} (100026100 + 100086600) = 100056350, )
( dfrac {1} {2} (b + c) = (10005) (6350) (220) (55) (0) )

Esto viola (3) y por lo tanto no está en (R ). En general, demostraremos que si (x ) y (y ) están en (R ) entonces ( bar {z} = dfrac {1} {2} (x + y) ) viola (3) y por lo tanto no está en (R ).

Dado que (x ) y (y ) están en (R ),

( bar {z} = dfrac { bar {x} + bar {y}} {2} = sum_ {i = 1} ^ {r - 2} dfrac {x_i ^ 2 + y_i ^ 2 } {2}. )

Por otro lado, (z ) en (R ) implica

( bar {z} = sum_ {i = 1} ^ {r - 2} z_i ^ 2 = sum_ {i = 1} ^ {r - 2} dfrac {(x_i + y_i) ^ 2} { 2}. )

Por tanto, si (z ) está en (R ) entonces

( sum_ {i = 1} ^ {r - 2} dfrac {x_i ^ 2 + y_i ^ 2} {2} = sum_ {i = 1} ^ {r - 2} dfrac {(x_i + y_i ) ^ 2} {2}. )

Por lo tanto

( sum_ {i = 1} ^ {r - 2} dfrac {(x_i - y_i) ^ 2} {2} = 0, )

lo que implica (x_i = y_i ) para (i = 1, 2, ..., r - 2 ). Esto junto con (1) y (2) implica que (x ) y (y ) no son distintos.

La secuencia de Szekeres comienza con 1, 2, 4, 5, 10, 11, ... Nuestra secuencia comienza con

100000, 1000100100, 1000400200, ....

Sin embargo, los términos de esta secuencia son eventualmente mucho más pequeños que los términos correspondientes de la secuencia de Szekeres. Ahora estimamos cuántos enteros en (R ) contienen exactamente (r ) corchetes. Dados los corchetes (r ) podemos hacer el primer dígito en cada uno de los corchetes (r - 2 ) 0. Podemos completar los primeros corchetes (r - 2 ) de una manera arbitraria. Esto se puede hacer en

(10 ​​^ {0 + 1+ 2 + cdot cdot cdot + (r - 2)} = 10 ^ { dfrac {1} {2} (r - 1) (r - 2)} )

formas. Los dos últimos corchetes se pueden rellenar de forma que se satisfagan (1) y (3).

Para ver esto, solo necesitamos verificar que los dos últimos corchetes no se llenen en exceso y que el último dígito, que estableceremos igual a 1, no se verá interferido. Esto se sigue de la desigualdad

((10 ^ 1) ^ 2 + (10 ^ 2) ^ 2 + cdot cdot cdot + (10 ^ {r - 2}) ^ 2 <10 ^ {2 (r - 1)}. )

Para un (n ) dado, sea (r ) el número entero determinado por

[10 ^ { dfrac {1} {2} r (r + 1)} le n <10 ^ { dfrac {1} {2} (r + 1) (r + 2)}. ]

Dado que todos los enteros con como máximo (r ) corchetes no excederán (n ), y dado que (r ) corchetes se pueden completar según la especificación en (10 ​​^ { dfrac {1} {2} ( r - 2) (r - 1)} ) formas, tenemos

[R (n) ge 10 ^ { dfrac {1} {2} (r - 2) (r - 1)} ]

Desde el lado derecho de (7.1) tenemos

(r + 2> sqrt {2 log n} )

de modo que (7.2) implica que

(R (n) ge 10 ^ { dfrac {1} {2} (r - 2) (r - 1)}> 10 ^ { log n - c sqrt { log n}}> 10 ^ {( log n) (1 - c / sqrt { log n})} )

donde todos los registros están en base 10.

Una vieja conjetura era que ( dfrac {A (n)} {n} a 0 ) para cada secuencia que no promedia. K. F. Roth sólo lo ha probado muy recientemente (1954). Su prueba no es elemental.

L. Moser ha utilizado una técnica similar para obtener límites inferiores para la función de Van der Waerden (W (k, ell) ). Demostró que (W (k, ell)> ell k ^ { log k} ), es decir, mostró cómo distribuir los números, 1, 2, ..., ([ ell k ^ { log k}] ) en clases (k ) de tal manera que ninguna clase contenga 3 términos en progresión aritmética. Usando un método bastante diferente, Erdo ( ddot {o} ) sy Rado han demostrado que (W (k, ell)> sqrt {2 ell k ^ { ell}} ).

Erd ( ddot {o} ) s ha planteado la siguiente pregunta: ¿Cuál es el número máximo de enteros (a_1

[2 ^ k le kn, ]

lo que implica

[k < dfrac { log n} { log 2} + (1 + o (1)) dfrac { log log n} { log 2}. ]

Ahora mostramos cómo Erd ( ddot {o} ) sy Moser mejoraron estas estimaciones (Nota del editor: El mejor límite inferior actual se puede encontrar en I. Aliev, “Lema de Siegel y conjuntos sumamente distintos”, Computación discreta. Geom.39 (2008), 59–66.) A

[2 ^ k <4 sqrt {k} n, ]

lo que implica

[k < dfrac { log n} { log 2} + (1 + o (1)) dfrac { log log n} {2 log 2}. ]

La conjetura de Erd ( ddot {o} ) s es que

[k = dfrac { log n} { log 2} + o (1). ]

Denote la suma de (a ) distintas por (s_1, s_2, ..., s_ {2 ^ k} ) y sea (A = a_1 + a_2 + cdot cdot cdot a_k ) . Observe que la suma promedio es ( dfrac {A} {2} ) ya que podemos emparejar cada suma con la suma del conjunto complementario. Esto sugiere que estimamos ( sum_i (s_i - dfrac {A} {2}) ^ 2 ).

Tenemos

( sum_i (s_i - dfrac {A} {2}) ^ 2 = sum dfrac {1} {2} ( pm a_1 pm a_2 pm cdot cdot cdot pm a_k) ^ 2 , )

donde la última suma corre sobre las (2 ^ k ) posibles distribuciones de signo. Al elevar al cuadrado, encontramos que todos los términos cruzados vienen en pares, mientras que cada (a_i ^ 2 ) aparecerá (2 ^ k ) veces. Por lo tanto

( sum_i (s_i - dfrac {A} {2}) ^ 2 = 2 ^ k sum a_i ^ 2 <2 ^ {k - 2} n ^ 2 k. )

Por tanto, el número de sumas (s_i ) para las cuales

(| s_i - dfrac {A} {2} | ge n sqrt {k} )

no puede exceder (2 ^ {k - 1} ). Dado que todas las sumas son diferentes, tenemos (2 ^ {k - 1} ) números distintos en un rango de longitud (2n sqrt {k} ). Esto produce (2 ^ {k - 1} le 2n sqrt {k} ) según sea necesario.

Sea (a_1

( dfrac {1} {2} ( sum a ^ {a_k}) ^ 2 + sum z ^ {2a_k} = sum f (n) z ^ n )
(= P _ { ell} (z) + a dfrac {z ^ { ell + 1}} {1 - z}, (f ( ell + 1) = a), )

donde (P (z) ) es un polinomio de grado ( le ell ). Si (z a -1 ) en el eje real, el lado derecho permanece acotado, pero el lado izquierdo se acerca al infinito, ya que ambos términos del lado izquierdo son positivos y el segundo tiende al infinito. Esta contradicción prueba el teorema.

Turan y Erd ( ddot {o} ) s conjeturaron que si (f (n)> 0 ) para todo (n ) suficientemente grande entonces lim sup (f (n) = infty ) pero esto parece muy difícil de probar. Una conjetura aún más fuerte sería que si (a_k> ck ^ 2 ) entonces lim sup (f (n) = infty ). El resultado más conocido en esta dirección es solo lim sup (f (n) ge 2 ).

Fuchs y Erdös demostraron recientemente que

( sum_ {k = 1} ^ {n} f (k) = cn + o ( dfrac {n ^ { dfrac {1} {4}} { log n}) )

es imposible. Si (a_k = k ^ 2 ) se llega al problema de los puntos de celosía en un círculo de radio (n ). Aquí Hardy y Landau demostraron

( sum_ {k = 1} ^ n f (k) = pi n + o (n log n) )

no se sostiene. Aunque no es tan fuerte como este, el resultado de Erd ( ddot {o} ) sy Fuchs es aplicable a una situación mucho más general y es mucho más fácil (pero no muy fácil) de probar.

Sea (a_1

Un problema interesante sin resolver en este sentido es encontrar una secuencia (B ): (b_1

Sea (a_1

P. Scherk mejoró ( dfrac {n} {2} ) a (n (2 - sqrt {2}) = .586n ). Mediante un método completamente diferente, L. Moser mejoró esto hasta (. 712n ). Por otro lado, Selfridge, Ralston y Motzkin han utilizado S.W.A.C. para refutar la conjetura original y haber encontrado ejemplos donde ningún número es representable más de (. 8n ) veces como una diferencia entre una (a ) y (a ) (b ).

Otro conjunto más de problemas interesantes de la teoría combinatoria de números gira en torno al concepto de cadena de adición introducido por A. Scholz. Una cadena de suma para (n ) es un conjunto de enteros (1 = a_0

1, 2, 4, 8, 16, 24, 40, 80, 160, 320, 640, 664, 666

formar una cadena con (r = 12 ); lo mismo vale para

1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 324, 648, 666.

En cualquier caso, debemos tener (a_1 = 2 ), y (a_2 = 3 ) o 4. Por la longitud ( ell = ell (n) ) Scholtz entiende el ( ell ) más pequeño para lo cual existe una cadena de adición (a_0, a_1, ..., a _ { ell} = n ).

Scholtz declaró lo siguiente:

(m + 1 le ell (n) le 2m ) para (2 ^ m + 1 le n le 2 ^ {m + 1} ) ( (m ge 1 ));
( ell (ab) le ell (a) + ell (b); )
( ell (2 ^ {m + 1} - 1) le m + ell (m + 1). )

Los dos primeros son fáciles de probar. El tercero podríamos conjeturar que es falso. Scholtz supuso que el primero podría mejorarse y planteó la cuestión de si

(1 le text {lim sup} _ {n to infty} dfrac { ell (n)} { log_2 n} le 2 )

podría ser mejorado.

En lo que sigue demostramos (1) y esbozamos una demostración debida a A. Brauer de que

( ell (n) thicksim log_2 n. )

Suponga que los números enteros se escriben en base 2 y buscamos una cadena de suma para 10110110, digamos. Podríamos formar la cadena

1, 10, 100, 101, 1010, 1011, 10110, 101100, 101101, 1011010,
1011011, 10110110, 101101100, 101101101.

En este proceso, cada dígito "cuesta" como máximo dos elementos en la cadena de modo que ( ell <2 log_2 n ). Dado que el lado izquierdo de la desigualdad de (1) es trivial, el método sugerido anteriormente produce una prueba de (1).

La idea de Brauer es acumular una gran cantidad de números primero y usarlos cuando surja la ocasión. Suponga que (n ) es aproximadamente (2 ^ m ). Comenzamos con la cadena 1, 2, ..., (2 ^ r ), donde (r ) se determinará más adelante. Ahora podemos dividir los dígitos de (n ) en bloques (m / r ) con (r ) dígitos en cada bloque. Por ejemplo, suponga

(n = (101) (110) (010) (101) (111) )

Aquí (m = 15 ), (r = 3 ).

Comenzando con nuestro stock de los números de 3 dígitos, podemos proceder de la siguiente manera:

1, 10, 100, ( underline {101} ), 1010, 10100, 101000, ( underline {101110} ),
1011100, 10111000, 101110000, ( underline {101110010} ), ...

donde entre las etapas subrayadas duplicamos y en las etapas subrayadas agregamos el número apropiado de nuestro stock para acumular (n ). En este caso, necesitaríamos (2 ^ 3 + 2 ^ {15} + 5 ) pasos. En general, el número de pasos para un número debajo de (2 ^ m ) sería aproximadamente (2 ^ r + m + dfrac {m} {c} ). Mediante la elección apropiada de (r ) podríamos hacer que (2 ^ r + dfrac {m} {r} ) sea tan pequeño como queramos en comparación con (m ). De hecho, utilizando esta idea, Brauer demostró en general

( ell (n) < log_2 n {1 + dfrac {1} { log log n} + dfrac {2 log 2} {( log n) ^ {1 - log 2}} }. )


Ver el vídeo: TEORÍA COMBINATORIA. Combinaciones. Ecuaciones. Ejercicio 1 (Septiembre 2021).