Artigos

1.7: Teoria dos Números Combinatórios - Matemática


Existem muitas questões interessantes entre a teoria dos números e a análise combinatória. são separados em n classes, então pelo menos uma classe conterá os elementos (a ), (b ), (c ) com (a + b = c ).

Considere o fato de que se separarmos os inteiros positivos menores que (2 ^ n ) em (n ) classes, colocando 1 na classe 1, os próximos 2 na classe 2, os próximos 4 na classe 3, etc., então, nenhuma classe contém a soma de dois de seus elementos. Alternativamente, poderíamos escrever cada inteiro m na forma (2 ^ k theta ) onde ( theta ) é ímpar e colocar (m ) na (k ) ésima classe. Novamente, os números menores que (2 ^ n ) estarão em (n ) classes e se (m_1 = 2 ^ k theta_1 ) e (m_2 = 2 ^ k theta_2 ) estiverem na classe (k ) então (m_1 + m_2 = 2 ^ k ( theta_1 + theta_2) ) encontra-se em uma classe numerada mais alta. A maneira mais complicada de distribuir inteiros descrita abaixo nos permite distribuir 1, 2, ..., ( dfrac {3 ^ n − 1} {2} ) em (n ) classes de forma que nenhuma classe tem uma solução para (a + b = c ):

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

Por outro lado, o teorema de Schur afirma que se separarmos os números 1, 2, 3,. , ([n! e] ) em (n ) classes de qualquer maneira, então pelo menos uma classe conterá uma solução para (a + b = c ). A lacuna entre as duas últimas declarações revela um problema interessante não resolvido, ou seja, pode-se substituir o ([n! E] ) no resultado de Schur por um número consideravelmente menor? Os primeiros dois exemplos dados mostram que certamente não podemos ir tão baixo quanto (2n - 1 ), e o último exemplo mostra que não podemos ir tão baixo quanto ( dfrac {3 ^ n − 1} {2} ) .

Agora damos uma definição e fazemos várias observações para facilitar a prova do teorema de Schur.

Seja (T_0 = 1 ), (T_n = nT_ {n − 1} + 1 ). É facilmente verificado que

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

Assim, o teorema de Schur pode ser reformulado da seguinte forma: Se 1, 2, ..., (T_n ) são separados em (n ) classes de qualquer maneira, pelo menos uma classe conterá uma solução de (a + b = c ). Provaremos isso assumindo que os números 1, 2, ..., (T_n ) foram classificados de n formas sem nenhuma classe contendo uma solução de (a + b = c ) e a partir disso obtemos uma contradição. Observe que a condição (a + b ne c ) significa que nenhuma classe pode conter a diferença de dois de seus elementos.

Suponha que alguma classe, digamos (A ), contenha 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, ... )

e assim por diante. Notamos que todos os (b ) 's, (c )' s, (d ) 's, etc., são diferenças de (a )' se, portanto, não podem estar em (A ).

Agora, começamos com os elementos (T_n ). Pelo menos

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

destes devem estar em uma única classe, digamos (A_1 ). Em seguida, formamos (T_ {n - 1} ) (b ) 's. Estes não estão em (A_1 ) e, portanto, estão nas demais (n - 1 ) classes. Pelo menos

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

deles deve estar em uma única classe, digamos (A_2 ). Forme suas diferenças (T_ {n - 2} ), os (c ) 's. Esses números produzem (T_ {n - 2} ) nem em (A_1 ) nem em (A_2 ). Continuar desta maneira resulta em (T_ {n - 3} ) números que não estão em (A_1, A_2, A_3 ). Desta forma, eventualmente obtemos (T_0 = 1 ) número não pertencente a (A_1, A_2, ..., A_n ). Mas todos os números formados estão entre os números (1, 2, ..., T_n ) então temos uma contradição, que prova o teorema.

Declaramos, sem prova, a conexão com o último teorema de Fermat. Uma abordagem natural ao teorema de Fermat seria tentar mostrar que (x ^ n + y ^ n = z ^ n ) (mod (p )) é um módulo insolúvel algum (p ), desde que (p ) não divide (x cdot y cdot z ). No entanto, o teorema de Schur pode ser usado para mostrar que este método deve falhar e, de fato, se (p> n! E ) então (x ^ n + y ^ n = z ^ n ) (mod (p )) tem uma solução com (p ) não um fator de (xyz ).

Algo relacionado ao teorema de Schur está um famoso teorema de Van der Waerden, que investigamos brevemente. No início da década de 1920, o seguinte problema surgiu em conexão com a teoria da distribuição de resíduos quadráticos. Imagine o conjunto de todos os inteiros a serem divididos de qualquer maneira em duas classes. Pode-se afirmar que progressões aritméticas de comprimento arbitrário podem ser encontradas em pelo menos uma dessas classes? O problema permaneceu sem solução por vários anos, apesar dos esforços concentrados de muitos matemáticos de destaque. Foi finalmente resolvido em 1928 por Van der Waerden. Como não é incomum em tais problemas, o primeiro passo de Van der Waerden foi tornar o problema mais geral e, portanto, mais fácil.

Van der Waerden provou o seguinte: Dados inteiros (k ) e ( ell ), existe um inteiro (W = W (k, ell) ) tal que se os números 1, 2, 3, ..., (W ) são separados em (k ) classes de qualquer maneira, então pelo menos uma classe conterá l termos em progressão aritmética. Não vamos dar a prova de Van der Waerden aqui. É extremamente complicado, difícil de ver e leva apenas a um limite fantasticamente grande para W (k, l). Por esta razão, o leitor pode considerar o problema não resolvido muito útil de encontrar uma prova alternativa mais simples de que (W (k, ell) ) existe e encontrar limites razoáveis ​​para ela. Teremos um pouco mais a dizer sobre a função (W (k, ell) ) um pouco mais tarde.

Nosso próximo problema de teoria dos números combinatórios lida com sequências “não médias”. Chamamos uma sequência (A: a_1

Dado um número (x ), escrito na base dez, decidimos se (x ) está em (R ) com base nas seguintes regras.

Primeiro colocamos (x ) em um conjunto de colchetes, colocando o primeiro dígito (contando da direita para a esquerda) no primeiro colchete, os próximos dois no segundo colchete, os próximos três no terceiro colchete e assim por diante. Se o último colchete não vazio (o colchete mais à esquerda que não consiste inteiramente de zeros) não tiver um número máximo de dígitos, nós o preencheremos com zeros. Por exemplo, os números

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

seria entre colchetes

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

respectivamente. Agora, suponha que o colchete (r ^ { text {th}} ) em (x ) contenha dígitos diferentes de zero, mas todos os outros colchetes à esquerda são 0. Ligue para o número representado pelos dígitos no (i ^ { text {th}} ) colchete (x_i ), (i = 1, 2, ..., r - 2 ). Além disso, denote por ( bar {x} ) o número representado pelo dígito nos dois últimos colchetes juntos, mas excluindo o último dígito. Para (x ) pertencer a (R ), exigimos

  1. o último dígito de (x ) deve ser 1,
  2. (x_i ) deve começar com 0 para (i = 1, 2, ..., r - 2, )
  3. (x_1 ^ 2 + cdot cdot cdot x_ {r - 2} ^ 2 = bar {x}. )

Em particular, observe que a satisfaz (2), mas viola (1) e (3) de forma que (a ) não está em (R ); mas (b ) e (c ) satisfazem todas as três condições e estão em (R ). Para verificar (3), não temos que (60 ^ 2 + 150 ^ 2 = 26100 ).

A seguir provamos que não há três inteiros em (R ) em progressão aritmética. Primeiro note que se dois elementos de 9R ) têm um número diferente de colchetes não vazios, sua média não pode satisfazer (1). Portanto, precisamos apenas considerar as médias dos elementos de (R ) com o mesmo número de colchetes não vazios. De (1) e (3) segue-se que os dois elementos de (R ) podem ser calculados em média colchete a colchete para os primeiros (r - 2 ) colchetes e também para os dois últimos colchetes tomados juntos. Assim, em nosso exemplo,

( 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) )

Isso viola (3) e, portanto, não está em (R ). Em geral, provaremos que se (x ) e (y ) estão em (R ), então ( bar {z} = dfrac {1} {2} (x + y) ) viola (3) e, portanto, não está em (R ).

Uma vez que (x ) e (y ) estão em (R ),

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

Por outro lado, (z ) em (R ) implica

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

Portanto, se (z ) está em (R ), então

( 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}. )

Desse modo

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

o que implica (x_i = y_i ) para (i = 1, 2, ..., r - 2 ). Isso junto com (1) e (2) implica que (x ) e (y ) não são distintos.

A sequência de Szekeres começa com 1, 2, 4, 5, 10, 11, ... Nossa sequência começa com

100000, 1000100100, 1000400200, ....

No entanto, os termos desta sequência são eventualmente muito menores do que os termos correspondentes da sequência de Szekeres. Agora estimamos quantos inteiros em (R ) contêm exatamente (r ) colchetes. Dados (r ) colchetes, podemos formar o primeiro dígito em cada um dos (r - 2 ) colchetes 0. Podemos preencher os primeiros (r - 2 ) colchetes de maneira arbitrária. Isso pode ser feito em

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

maneiras. Os dois últimos colchetes podem ser preenchidos de forma a satisfazer (1) e (3).

Para ver isso, precisamos apenas verificar se os dois últimos colchetes não serão sobrecarregados e se o último dígito, que definiremos como 1, não sofrerá interferência. Isso decorre da desigualdade

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

Para um dado (n ) seja (r ) o inteiro determinado por

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

Uma vez que todos os inteiros com no máximo (r ) colchetes não excederão (n ), e uma vez que (r ) colchetes podem ser preenchidos conforme a especificação em (10 ​​^ { dfrac {1} {2} ( r - 2) (r - 1)} ) formas, temos

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

Do lado direito de (7.1), temos

(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})} )

onde todos os logs são baseados em 10.

Uma velha conjectura era que ( dfrac {A (n)} {n} to 0 ) para cada sequência não média. Isso só foi provado recentemente (1954) por K. F. Roth. Sua prova não é elementar.

L. Moser usou uma técnica semelhante para obter limites inferiores para a função de Van der Waerden (W (k, ell) ). Ele provou que (W (k, ell)> ell k ^ { log k} ), ou seja, mostrou como distribuir os números, 1, 2, ..., ([ ell k ^ { log k}] ) em classes (k ) de forma que nenhuma classe contenha 3 termos em progressão aritmética. Usando um método bem diferente, Erdo ( ddot {o} ) s e Rado mostraram que (W (k, ell)> sqrt {2 ell k ^ { ell}} ).

Erd ( ddot {o} ) s levantou a seguinte questão: Qual é o número máximo de inteiros (a_1

[2 ^ k le kn, ]

que implica

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

Agora mostramos como Erd ( ddot {o} ) s e Moser melhoraram essas estimativas (Nota do editor: O melhor limite inferior atual pode ser encontrado em I. Aliev, “Lema de Siegel e conjuntos distintos de soma,” Computação Discreta. Geom. 39 (2008), 59-66.) Para

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

que implica

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

A conjectura de Erd ( ddot {o} ) s é que

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

Denote a soma de (a ) 's distintos por (s_1, s_2, ..., s_ {2 ^ k} ) e deixe (A = a_1 + a_2 + cdot cdot cdot a_k ) . Observe que a soma média é ( dfrac {A} {2} ) uma vez que podemos emparelhar cada soma com a soma do conjunto complementar. Isso sugere que estimamos ( sum_i (s_i - dfrac {A} {2}) ^ 2 ).

Nós temos

( 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 , )

onde a última soma ultrapassa as (2 ^ k ) possíveis distribuições de sinal. Após o quadrado, descobrimos que todos os termos cruzados vêm em pares, enquanto cada (a_i ^ 2 ) aparecerá (2 ^ k ) vezes. Desse modo

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

Assim, o número de somas (s_i ) para as quais

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

não pode exceder (2 ^ {k - 1} ). Como todas as somas são diferentes, temos (2 ^ {k - 1} ) números distintos em uma faixa de comprimento (2n sqrt {k} ). Isso resulta em (2 ^ {k - 1} le 2n sqrt {k} ) conforme necessário.

Seja (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), )

onde (P (z) ) é um polinômio de grau ( le ell ). Se (z para -1 ) no eixo real, o lado direito permanece limitado, mas o lado esquerdo se aproxima do infinito, já que ambos os termos do lado esquerdo são positivos, e o segundo tende para o infinito. Essa contradição prova o teorema.

Turan e e Erd ( ddot {o} ) s conjeturaram que se (f (n)> 0 ) para todos suficientemente grandes (n ) then lim sup (f (n) = infty ) mas isso parece muito difícil de provar. Uma conjectura ainda mais forte seria que se (a_k> ck ^ 2 ) então lim sup (f (n) = infty ). O resultado mais conhecido nesta direção é apenas lim sup (f (n) ge 2 ).

Fuchs e Erdös provaram recentemente que

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

é impossível. Se (a_k = k ^ 2 ) chega-se ao problema dos pontos da rede em um círculo de raio (n ). Aqui Hardy e Landau provaram

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

não segura. Embora não seja tão forte quanto isso, o resultado de Erd ( ddot {o} ) s e Fuchs é aplicável a uma situação muito mais geral e é muito mais fácil (mas não muito fácil) de provar.

Seja (a_1

Um problema interessante não resolvido ao longo dessas linhas é encontrar uma sequência (B ): (b_1

Sejam (a_1

P. Scherk melhorou o ( dfrac {n} {2} ) para (n (2 - sqrt {2}) = 0,586n ). Por um método totalmente diferente, L. Moser melhorou isso para (. 712n ). Por outro lado, Selfridge, Ralston e Motzkin usaram S.W.A.C. para refutar a conjectura original e ter encontrado exemplos onde nenhum número é representável mais do que (. 8n ) vezes como uma diferença entre um (a ) e (a ) (b ).

Ainda outro conjunto de problemas interessantes da teoria dos números combinatórios gira em torno do conceito de cadeia de adição introduzido por A. Scholz. Uma cadeia de adição para (n ) é um conjunto de inteiros (1 = a_0

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

formar uma cadeia com (r = 12 ); o mesmo vale para

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

Em qualquer caso, devemos ter (a_1 = 2 ) e (a_2 = 3 ) ou 4. Pelo comprimento ( ell = ell (n) ) Scholtz entende o menor ( ell ) para o qual existe uma cadeia de adição (a_0, a_1, ..., a _ { ell} = n ).

Scholtz afirmou o seguinte:

(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). )

Os dois primeiros são fáceis de provar. A terceira, conjeturaríamos ser falsa. Scholtz supôs que o primeiro poderia ser melhorado e levantou a questão de saber se

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

Poderia ser melhorado.

No que se segue, provamos (1) e esboçamos uma prova devida a A. Brauer que

( ell (n) thicksim log_2 n. )

Suponha que inteiros sejam escritos na base 2 e busquemos uma cadeia de adição para 10110110, digamos. Podemos formar a corrente

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

Neste processo, cada dígito “custa” no máximo dois elementos na cadeia de forma que ( ell <2 log_2 n ). Visto que o lado esquerdo da desigualdade de (1) é trivial, o método sugerido acima produz uma prova de (1).

A ideia de Brauer é construir um grande estoque de números primeiro e usá-lo quando surgir a ocasião. Suponha que (n ) seja cerca de (2 ^ m ). Começamos com a cadeia 1, 2, ..., (2 ^ r ), onde (r ) será determinado posteriormente. Agora podemos quebrar os dígitos de (n ) em blocos de (m / r ) com (r ) dígitos em cada bloco. Por exemplo, suponha

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

Aqui (m = 15 ), (r = 3 ).

Começando com nosso estoque de todos os números de 3 dígitos, podemos proceder da seguinte forma:

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

onde entre os estágios sublinhados dobramos e nos estágios sublinhados adicionamos o número apropriado de nosso estoque para aumentar (n ). Nesse caso, precisaríamos de (2 ^ 3 + 2 ^ {15} + 5 ) etapas. Em geral, o número de passos para um número sob (2 ^ m ) seria cerca de (2 ^ r + m + dfrac {m} {c} ). Pela escolha apropriada de (r ) poderíamos fazer (2 ^ r + dfrac {m} {r} ) tão pequeno quanto quisermos em comparação com (m ). Na verdade, usando essa ideia, Brauer provou em geral

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


Assista o vídeo: Aula 08 - Números primos e o teorema fundamental da aritmética (Novembro 2021).