Generalização do problema de Brokar

A história

Hilbert, em 1900, no II Congresso Internacional de Matemáticos de Paris, observou a importância prática da teoria dos números. A solução de problemas abstratos frequentemente levava ao surgimento de um novo aparato matemático. Um exemplo vívido é o Teorema da Grande Fazenda, durante a prova de que, no final do século XX, foram investigadas as funções meromorfas usadas pelos engenheiros de design modernos nas fábricas de automóveis e aeronaves, bem como pelos especialistas em TI no âmbito da simulação. Os problemas dos "números bonitos" - gêmeos simples e números perfeitos, considerados quase inúteis na Grécia antiga, agora fornecem à criptografia moderna algoritmos estáveis ​​de geração de chaves.

Em 1913, Ramanujan popularizou a equação indefinida:

$$

$$n! + 1 = m ^ 2 (1)$$

Anteriormente, ele apareceu nos trabalhos de Henri Brocard. Segundo os historiadores, dois matemáticos começaram a estudar essa equação independentemente um do outro. Obviamente, o fatorial cresce mais rápido que o quadrado, para que as primeiras soluções possam ser obtidas rapidamente, enumerando os valores de n. Temos:

$$

$$4! = 5 ^ 2-1$$

$$

$$5! = 11 ^ 2-1$$

$$

$$7! = 71 ^ 2-1$$

Em 2000, os valores foram verificados por enumeração computacional $$$n$antes $$$10 ^ 9$, e não foi possível encontrar novas soluções. O artigo propõe minha abordagem para verificar casos particulares do problema de Brokar e também formula uma versão generalizada do problema matemático, cuja solução permite, independentemente da hipótese do ABC, resolver equações da forma:

$$

$$n! = P (x)$$

Pré-requisitos

A aritmética modular é uma ferramenta poderosa para uma avaliação preliminar da complexidade de um problema e para destacar casos especiais. Por exemplo, é fácil mostrar que, mesmo $$$m$O problema de Brokar não tem solução, uma vez que o fatorial de qualquer número natural, exceto a unidade, é uniforme. Um pré-requisito para um par de valores $$$(n, m)$na equação de Brokard é a divisibilidade do fatorial pela expressão:

$$

$$m ^ 2-1$$

O fatorial, por definição, é um produto de números naturais consecutivos. Utilizando as propriedades das séries naturais, é possível determinar o grau de um ou outro número primo na fatoração canônica do fatorial. Por exemplo $$$16!$contém 16 fatores consecutivos. Todo segundo fator é dividido por 2, todo quarto é dividido por 4, todo oitavo é 8 e todo 16 é 16. Assim, a decomposição $$$16!$por fatores contém 2 ao poder de $$$1 + 2 + 4 + 8 = 15$. A partir daqui, se houver um par $$$(16, m)$sendo uma solução para o problema de Brokar, então $$$m ^ 2$deve dar o restante de 1 ao dividir por qualquer potência de dois até o dia 15, inclusive. Formulamos a condição necessária para $$$m$ao resolver a equação 1:

Vamos $$$n!$não excede em certa medida $$$k$número primo $$$p$e há um número $$$m$em que o par $$$(n, m)$é uma solução para a equação 1. Então $$$m ^ 2-1$deve ser dividido em todos os graus $$$p$antes $$$F (k)$onde $$$F$- função de cálculo de graus $$$p$em decomposição $$$n!$. 2)

Propriedade P

Suponha que exista um algoritmo A que verifique a condição 2 necessária para obter algum número primo $$$p$. Chamamos esse algoritmo de teste-P. Que haja também um natural $$$n$satisfazendo a condição: $$$(n-1)! <m ^ 2 <n!$
Então dizemos que o número $$$m$possui uma propriedade P.

Considere um processo de 2 testes para arbitrários $$$m$entre $$$1023!$e $$$1024!$. Para $$$m ^ 2$As seguintes declarações serão verdadeiras:

1. $$$m ^ 2$dá um resto de 1 ao dividir por todos os poderes de dois a $$$2 ^ {1023-10 = 1013}$inclusivamente;
2. $$$m ^ 2-1$não dividido por $$$2 ^ {1024-10 = 1014}$.

Na prática, a maioria dos números quadrados entre $$$1023!$e $$$1024!$falhar no teste 2 nas primeiras 200 iterações. Se o número $$$m ^ 2$do intervalo especificado e $$$m$possui uma propriedade 2, em seguida, no sistema binário $$$m ^ 2$termina em $$$100..001$, onde os zeros são exatamente 1012. Em seguida, para verificar a condição 2, podemos calcular $$$m ^ 2$até os últimos 8 dígitos e verifique os últimos 8 dígitos. Se houver uma sequência diferente de $$$0000 0001$o teste 2 falhou. Cálculo seqüencial de cada valor testado com uma precisão de 8, 16, 24 etc. caracteres, você pode verificar rapidamente a condição 2 para obter um grande conjunto de valores usando um mínimo de recursos do sistema. Os tamanhos de cadeias que são múltiplos de 8 são justificados pela estrutura de bytes da RAM dos computadores modernos: um byte inteiro será usado para armazenar cadeias menores. Para cadeias grandes e não múltiplos de 8, também haverá bits de memória não utilizados.

Seja necessário verificar a declaração:
Entre $$$n$de um segmento $$$[k_1, k_2]$não há soluções para a equação 1 para qualquer $$$m$onde $$$n, m, k_1, k_2$natural.

Usando a fórmula Stirling, definimos as lacunas $$$(a_1, b_1), (a_2, b_2), .., (a_l, b_l)$onde $$$l = k_2-k_1 + 1$. Para a i-ésima lacuna:

$$

$$a_i = {(s / e)} ^ s e ^ {1 / {12s + 1}} {\ sqrt {2 \ pi s}}$$

$$

$$b_i = {(s / e)} ^ s e ^ {1 / {12s}} {\ sqrt {2 \ pi s}}$$

$$

$$s = k_1 + i-1$$

Então a afirmação é verdadeira:
Se entre os números quadrados de $$$(a_1, b_1), (a_2, b_2), .., (a_l, b_l)$nenhum passou no teste 2, então a equação 1 não tem solução no intervalo $$$[k_1, k_2]$. O inverso não é verdadeiro.

Uma generalização do problema de Brokar sob as condições necessárias

Em geral, um número quadrado com uma propriedade p tem uma base no cálculo $$$p$ver: $$$t00..001$, com o número de zeros $$$F (k) -1$. Em seguida, podemos generalizar o problema da propriedade P:
Que sejam descritas duas funções: $$$F$e $$$G$retornando valores naturais para qualquer argumento natural e $$$G$não pode ser representado como um polinômio com coeficientes inteiros. Então é necessário formular um critério para o qual entre os números $$$m$deitado entre $$$G (t)$e $$$G (t + 1)$e tendo na notação no cálculo com base p a forma:

$$

$$k_100..00k_2 (3)$$

você pode escolher apenas aqueles que têm uma raiz natural do enésimo grau, em que o número de zeros no registro 3 é dado pela função $$$F$dependente $$$t$. Ao fazer isso, $$$k_1$pode ser um parâmetro, um valor arbitrário ou uma constante e $$$k_2$sempre uma constante. 4)

Por exemplo, você pode colocar o problema da extração da raiz cúbica a partir de números $$$n$tendo em notação hexadecimal $$$k00..001$onde $$$k$qualquer número hexadecimal é maior que 1 e o número de zeros para um determinado $$$n$igual ao maior $$$t$para o qual a desigualdade é válida:

$$

$$2 ^ t + 3t-1 <n$$

A base para a redação do artigo foi a afirmação sobre a relação direta entre o número de zeros no registro 3 em um cálculo arbitrário para o valor do lado esquerdo da equação 1 ao substituir as raízes já encontradas e o número $$$n$. Se a equação 1 tem exatamente 3 raízes, esse fato pode ser provado resolvendo o caso especial correspondente do problema 4. O inverso não é verdadeiro.

Conclusão

Falando sobre a importância prática de problemas abstratos da teoria dos números, como um fator que estimula o desenvolvimento do aparato matemático, vale mencionar uma equação interessante em números inteiros, cuja solução é impossível dentro da estrutura da generalização acima:

$$

$$11 + ({2 ^ {n ^ 2-1} -2 ^ {3n-3}}) / (2 ^ {n-1} -1) \ equiv 0 \ pmod {2 ^ {m + 1} -1 } (5)$$

Esta equação segue logicamente as tentativas de aproximar os números de Lucas pelo método não recorrente. A solução do Problema 5 ajudará a descobrir novas propriedades dos números de Mersenne e a formular as condições necessárias para acelerar o trabalho de programas de pesquisa distribuídos para números primos grandes com base no teste de Luc-Lemer.

Por analogia com o fraco problema de Goldbach, supõe-se que os testes P ajudem a obter um grande limite inferior para todas as raízes da equação 1, exceto $$$(4, 5), (5, 11)$e $$$(7, 71)$, e o estudo do problema 3 levará à prova da insolabilidade da equação 1 em números inteiros para valores suficientemente grandes de n.

Fontes

Problemas de Hilbert
O desafio de Brokar