Decompondo uma fatorial em grandes fatores

Acabei de enviar para o Arxiv o artigo “Decompondo uma fatorial em grandes fatores“Este artigo estuda a quantidade definido como a maior quantidade de que é possível fatorar em fatores cada um dos quais é pelo menos . Os primeiros valores desta sequência são

(OEIS A034258). Por exemplo, nós temos porque, por um lado, podemos levar em consideração

Mas por outro lado, não é possível fatorar em nove fatores, cada um dos quais é ou superior.

Essa quantidade foi introduzido por Erdös, que pediu limites superior e inferior ; informalmente, isso pergunta como se pode se separar equitativamente em fatores. Ao considerar um número arbitrário, isso é essencialmente uma variante do notório Problema da mochila (depois de tomar logaritmos), mas pode -se esperar que a estrutura específica do fatorial Pode tornar esse problema específico do tipo Knapsack mais tratável. Desde

Para qualquer fatoração putativa, obtemos um limite superior

Graças à aproximação de Stirling. A certa altura, Erdös, Selfridge e Strauss alegaram que esse limite superior period assintoticamente nítido, no sentido de que

como ; informalmente, isso significa que podemos dividir em fatores que são (principalmente) aproximadamente do mesmo tamanho, quando é grande. No entanto, conforme relatado em este artigo posteriorErdös “acreditava que Straus havia escrito nossa prova … Infelizmente, Straus de repente morreu e nenhum vestígio foi encontrado sobre suas anotações. Além disso, nunca poderíamos reconstruir nossa prova, para que nossa afirmação agora possa ser chamada apenas uma conjectura”.

Alguma exploração adicional de foi realizado por Man e Selfridge. Existe uma construção simples que dá o limite inferior

Isso vem de começar com a fatorização padrão e transferir alguns poderes de Desde a parte posterior da sequência até a parte anterior, para reequilibrar um pouco os termos. Mais precisamente, se alguém take away um poder de dois dos números pares entre e e um poder adicional de dois dos múltiplos de quatro entre para isso libera poderes de dois que se pode distribuir entre os números até para trazer todos eles pelo menos em tamanho. Um procedimento mais complicado que envolve a transferência de ambos os poderes de e Então dá a melhoria . Nesse ponto, no entanto, as coisas ficaram mais complicadas e as seguintes conjecturas foram feitas por Man e Selfridge:

Nesta nota, estabelecemos os limites

como onde é a constante explícita

Em specific, isso recupera o resultado perdido (2). Um limite superior da forma

para alguns Por Erdös e Graham (Problema de Erdös #391). Conjetamos que o limite superior (3) é nítido, assim

que é consistente com as conjecturas acima (i), (ii), (iii) de Man e Selfridge, embora numericamente a convergência seja um pouco lenta.

O argumento limite superior para (3) é simples o suficiente para que também possa ser modificado para estabelecer a primeira conjectura (i) de Man e Selfridge; em princípio, (ii) e (iii) agora também são redutíveis a um cálculo finito, mas infelizmente as constantes implícitas no limite inferior de (3) são muito fracos para tornar isso diretamente viável. No entanto, pode ser possível agora agrupar a verificação de (ii) e (iii) fornecendo um conjunto adequado de fatizações para cobrir o tamanho médio combinado com alguma versão eficaz do argumento inferior que pode estabelecer para todos depois de um certo limiar. O valor Esperado por Man e Selfridge parece ser um caso de teste bastante adequado: as construções que tentei caíram um pouco aquém do limiar conjectado de mas parece quase ao seu alcance que um rearranjo suficientemente eficiente dos fatores pode funcionar aqui.

Agora descrevemos a prova do limite superior e inferior (3). Para melhorar o limite superior trivial (1)pode -se usar os grandes fatores primos de . De fato, todo primo entre e divide pelo menos uma vez (e os entre e divida duas vezes) e qualquer fator que contém esse fator, portanto, deve ser significativamente maior do que o valor de referência de . Esta observação já leva prontamente a algum limite superior da forma (4) para alguns que são um pouco menos do que (observando que qualquer múltiplo de que excede deve de fato exceder ) é o que leva à constante precisa .

Para construções mais baixas anteriores, uma começou com a fatorização inicial e depois tentou “melhorar” essa fatoração, movendo alguns dos principais fatores. Para o limite inferior (3)começamos com uma fatoração aproximada aproximadamente da forma

onde é o limite inferior alvo (então, um pouco menor que ), e é um parâmetro de número pure de tamanho moderadamente embora haja flexibilidade significativa aqui). Se denotarmos o lado direito aqui por então é basicamente um produto de Números de tamanho pelo menos . Não é literalmente igual a ; No entanto, uma aplicação fácil de Fórmula de Legendre mostra isso para pequenos primos estranhos Assim, e têm quase exatamente o mesmo número de fatores de . Por outro lado, como é estranho, não contém fatores de enquanto contém sobre tais fatores. As principais fatorizações de e diferem um pouco em geral, mas tem um pouco mais de fatores principais como (sobre tais fatores, de fato). Por algumas aplicações cuidadosas do teorema do número primo, pode -se ajustar alguns dos grandes primos que aparecem em Para fazer a principal fatorização de e concordo quase exatamente, exceto que está faltando a maioria dos poderes de em embora tenham alguns fatores primários grandes adicionais além dos contidos em para compensar. Com uma escolha adequada de limiar pode -se então substituir esses grandes fatores primários grandes por poderes de dois para obter uma fatorização de em termos que são todos pelo menos dando o limite inferior.

A abordagem geral de primeiro localizar alguma fatoração aproximada de (onde a aproximação está no sentido “adelico” de não ter apenas aproximadamente a magnitude certa, mas também aproximadamente o número certo de fatores de para vários primos ) e depois em movimento os fatores para obter uma fatoração exata de parece promissor por também resolver as conjecturas (ii), (iii) mencionadas acima. Por exemplo, eu period capaz de verificar numericamente que Pelo procedimento a seguir:

• Comece com a fatoração aproximada de Assim, por . Por isso é o produto de números ímpares, cada um dos quais é pelo menos .
• Chame um Prime Odd -Evoso se dividir mais frequentemente do que e -Evoso se dividir mais frequentemente do que . Acontece que existem mais -Evy Primes do que -eavos primos (contagem de multiplicidade). Por outro lado, contém poderes de enquanto não tem nenhum. Isso representa o (multi) conjunto de primos, é preciso redistribuir para converter uma fatorização de para uma fatoração de .
• Usando um algoritmo ganancioso, pode -se corresponder a um -eavy prime para cada um -eavy prime (contagem de multiplicidade) de tal maneira que para um pequeno (na maioria dos casos, pode -se fazer e muitas vezes um também tem ). Se então substituímos na fatoração de por para cada um -eavy prime isso aumenta (e não diminui nenhum dos fatores de ), ao eliminar todo o -i comaente. Com um algoritmo correspondente um tanto grosseiro, pude fazer isso usando do poderes de dividindo saindo poderes restantes à minha disposição. (Não afirmo que essa seja a correspondência mais eficiente, em termos de poderes de dois necessários, mas foi suficiente.)
• Ainda existem -i comestivo que sobrou na fatoração de (a versão modificada de) . Substituindo cada um desses primos por e depois distribuir o restante Poderes de dois arbitrariamente, isso obtém uma fatorização de em termos, cada um dos quais é pelo menos .

No entanto, não consegui ajustar os parâmetros para alcançar dessa maneira. Talvez alguns leitores aqui que sejam adeptos aos computadores possam criar uma construção mais eficiente para se aproximar desse limite? Se alguém puder encontrar uma maneira de atingir esse limite, provavelmente pode ser adaptado para resolver conjecturas (ii) e (iii) acima após algum esforço numérico adicional.