🔢 mathematics

Algorithmic aspects of Newman polynomials and their divisors

Este artigo investiga quais polinômios inteiros dividem polinômios de Newman analisando exemplos conhecidos de baixa medida de Mahler, identificando polinômios específicos que não dividem nenhum (melhorando assim o limite superior para uma constante universal potencial $\sigma$ ) e determinando a máxima potência do polinômio de Lehmer que pode dividir um polinômio de Newman dentro de limites específicos de grau.

Autores originais: Musbahu Idris, Jean-Marc Sac-Épée

Publicado 2026-04-29

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Musbahu Idris, Jean-Marc Sac-Épée

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um construtor mestre trabalhando com um conjunto muito específico de blocos de Lego. Esses blocos são especiais: eles só vêm em duas cores, Branco (representando o número 1) e Preto (representando o número 0). Você só pode construir torres (polinômios) usando essas duas cores, e toda torre deve começar e terminar com um bloco Branco. No mundo matemático, essas são chamadas de polinômios de Newman.

Os autores deste artigo estão fazendo uma pergunta fundamental: Todo outro tipo de "torre" matemática pode ser construído dentro de uma dessas torres especiais Brancas e Pretas?

Mais especificamente, eles estão analisando "torres inteiras" (polinômios com coeficientes de números inteiros) que possuem uma certa propriedade chamada medida de Mahler baixa. Pense na medida de Mahler como uma pontuação de "tamanho" ou "complexidade". Quanto menor a pontuação, mais "pequena" ou "simples" é a torre.

Aqui está uma descrição de sua jornada e descobertas:

1. A Grande Pergunta

Os matemáticos já sabiam que, se você permitir que seus blocos sejam Vermelhos, Brancos e Pretos (números -1, 0 e 1), então quase qualquer torre inteira pequena e simples pode ser encontrada dentro de uma torre maior feita dessas três cores.

Mas e se você estiver estritamente proibido de usar blocos Vermelhos? E se você puder apenas usar Brancos e Pretos? A regra ainda se mantém? Toda torre inteira pequena e simples ainda cabe dentro de uma torre Branca e Preta?

2. A Grande Busca (A Lista "Known180")

Os autores decidiram testar isso em uma lista massiva de 8.438 torres "pequenas" conhecidas (aquelas com uma medida de Mahler menor que 1,3). Eles escreveram um programa de computador para atuar como um holofote.

O Método: Para cada torre pequena na lista, o computador tentou encontrar uma torre "parceira" (feita de inteiros) tal que, quando multiplicadas, o resultado fosse uma torre Newman Branca e Preta perfeita.
A Restrição: O computador recebeu a ordem de parar de procurar se a torre resultante ficasse muito alta (grau superior a 1.000).
Os Resultados:
- O Problema da "Raiz Positiva": Primeiro, eles descartaram qualquer torre que tivesse uma "raiz real positiva". Imagine uma torre que tem um ponto fraco no lado ensolarado; matematicamente, essas nunca podem caber dentro de uma torre Newman.
- O Sucesso: Para quase todas as torres restantes, o computador encontrou uma correspondência! Provou-se que, se uma torre for pequena o suficiente (grau 44 ou menos) e não tiver esses "pontos fracos", ela pode ser construída dentro de uma torre Newman.
- O Mistério: Havia três torres teimosas na lista onde o computador não conseguiu encontrar uma correspondência dentro do limite de grau 1.000. Os autores não disseram que essas são impossíveis, apenas que ainda não encontraram um parceiro para elas.

3. O Muro da "Razão Áurea"

Havia uma crença de longa data de que a "Razão Áurea" (cerca de 1,618) era o limite. A ideia era: "Se sua torre for menor que a Razão Áurea, ela cabe".

Os autores (e outros que citam) provaram que isso estava errado. Eles encontraram torres específicas que são menores que a Razão Áurea, mas não conseguem caber dentro de qualquer torre Newman, não importa o quão alta a torre Newman fique.

O Novo Recorde: Eles encontraram uma torre de 10º grau com um tamanho de cerca de 1,419. Esta é a menor torre "impossível" encontrada até agora.
A Implicação: Isso empurra o "limite de segurança" para baixo. Se houver um número mágico (vamos chamá-lo de $\sigma$ ) que garanta que uma torre caberá, esse número deve ser inferior a 1,419.

4. O Experimento da "Dupla Dificuldade"

Na seção final, os autores analisaram uma famosa torre matemática chamada polinômio de Lehmer. Eles a viraram do avesso (substituindo $x$ por $-x$ ) para obter uma nova torre, vamos chamá-la de $l(x)$ .

Eles perguntaram: Podemos construir uma torre Newman que seja divisível pelo quadrado de $l(x)$ ( $l(x)^2$ )?

O Resultado: Sim! Eles usaram sua busca por computador para construir torres Newman até o grau 150 que contêm $l(x)^2$ como fator. Eles até forneceram os projetos (em um código chamado hexadecimal) para essas torres massivas.

Então eles fizeram a próxima pergunta: E quanto ao cubo de $l(x)$ ( $l(x)^3$ )?

O Resultado: Eles verificaram até o grau 160 e não encontraram nada. Nenhuma torre Newman desse tamanho poderia ser dividida por $l(x)^3$ . Isso sugere que, embora você possa encaixar o quadrado desta famosa torre, o cubo pode ser impossível de encaixar (ou, pelo menos, é incrivelmente difícil de encontrar).

Resumo

Pense neste artigo como uma história de detetive sobre encaixar formas em uma caixa:

A Caixa: Polinômios de Newman (apenas 0s e 1s).
Os Objetos: Polinômios inteiros com "tamanhos" pequenos (medida de Mahler).
A Descoberta: A maioria dos objetos pequenos cabe perfeitamente dentro da caixa.
A Exceção: Existem alguns objetos específicos que são pequenos o suficiente para parecer que deveriam caber, mas não cabem. Os autores encontraram o menor deles até agora, provando que o "limite" para encaixar é menor do que pensávamos.
O Bônus: Eles construíram com sucesso caixas gigantes que contêm formas complexas específicas (versões quadradas e cúbicas do polinômio de Lehmer), mostrando quão flexíveis essas torres de 0 e 1 podem ser.

O artigo conclui que, embora tenhamos resolvido muitos desses quebra-cabeças de encaixe, alguns permanecem sem solução, e a busca pelo "limite" definitivo do que pode caber continua.

1. Formulação do Problema

O artigo aborda a questão fundamental na teoria dos números algébricos relativa aos polinômios de Newman (polinômios com coeficientes em $\{0, 1\}$ e um termo constante igual a 1). Especificamente, investiga-se as condições sob as quais um polinômio com coeficientes inteiros $p(x)$ divide um polinômio de Newman.

A indagação central é se existe uma constante universal $\sigma$ tal que qualquer polinômio com coeficientes inteiros $p(x)$ com:

Nenhuma raiz real não-negativa, e
Medida de Mahler $M(p) < \sigma$ ,
necessariamente divide um polinômio de Newman.

Trabalhos anteriores estabeleceram que, se $M(p) < 2$ , $p(x)$ divide um polinômio com coeficientes em $\{-1, 0, 1\}$ . No entanto, restringir os coeficientes a $\{0, 1\}$ é uma condição muito mais estrita. Embora a Razão Áurea ( $g \approx 1,618$ ) tenha sido inicialmente considerada um limite natural, contraexemplos com medidas de Mahler em torno de 1,556 foram encontrados. O artigo visa refinar esse limite e determinar as propriedades de divisibilidade de polinômios com medidas de Mahler pequenas.

2. Metodologia

Os autores empregam uma combinação de Programação Linear Mista Inteira (PLMI) e certificação algorítmica para resolver dois problemas distintos: encontrar múltiplos de Newman e certificar a não existência de tais múltiplos.

A. Busca por Múltiplos de Newman (Abordagem PLMI)

Para determinar se um polinômio dado $p(x)$ divide um polinômio de Newman, os autores formulam o problema como um sistema de desigualdades lineares.

Formulação: Dado um polinômio mônico $p(x)$ de grau $2d$ , busca-se um polinômio $q(x)$ tal que o produto $N(x) = p(x)q(x)$ tenha coeficientes em $\{0, 1\}$ .
Restrições: Como os termos constantes de $p$ e $q$ são 1, o termo constante de $N$ é 1. Os coeficientes de $N(x)$ são combinações lineares dos coeficientes desconhecidos de $q(x)$ . A condição de que todos os coeficientes de $N(x)$ devem ser 0 ou 1 cria um sistema de desigualdades lineares com incógnitas inteiras.
Implementação: Os autores implementaram isso em Julia usando a linguagem de modelagem JuMP e o otimizador Gurobi. Eles buscaram soluções onde o grau do polinômio de Newman resultante não excedesse 1000.

B. Certificação de Não-Divisibilidade (Abordagem de Alcance)

Para provar que um polinômio não divide nenhum polinômio de Newman, os autores utilizam um método algorítmico introduzido por Hare e Mossinghoff.

Princípio: Seja $\beta$ uma raiz do polinômio candidato. Eles definem um conjunto $N'(\beta, d)$ representando os valores $F(\beta)$ para todos os polinômios de Newman $F$ de grau $\le d$ , restritos a um disco específico $I'(\beta)$ .
Algoritmo: O conjunto é construído recursivamente. Se o conjunto se estabilizar (ou seja, $N'(\beta, d+1) = N'(\beta, d)$ ) e 0 nunca for alcançado dentro deste conjunto, prova-se que $\beta$ não é uma raiz de nenhum polinômio de Newman. Consequentemente, o polinômio mínimo de $\beta$ não divide nenhum polinômio de Newman.
Implementação: Isso foi implementado independentemente em Julia (usando Polynomials.jl e Nemo.jl) e GP/PARI para garantir verificação cruzada.

C. Construção de Múltiplos com Raízes Repetidas

Os autores adaptaram a abordagem PLMI para encontrar polinômios de Newman divisíveis por $l(x)^2$ , onde $l(x)$ é o polinômio de Lehmer com $x \to -x$ .

Método: Em vez de desigualdades, resolveram um sistema de equações lineares derivado do resto da divisão euclidiana $N(x) = g(x)H(x) + R(x)$ . A condição $g(x) | N(x)$ requer que $R(x) = 0$ .
Otimização: Resolveram para coeficientes binários $a_i \in \{0, 1\}$ para satisfazer as condições de anulação do resto.

3. Resultados Principais

A. Divisibilidade de Polinômios com Pequena Medida de Mahler

Os autores analisaram um conjunto de dados de 8.438 polinômios conhecidos com medida de Mahler $< 1,3$ e grau $\le 180$ (conhecido como Known180).

Descoberta: Excluindo polinômios com raízes reais positivas, todos, exceto três, polinômios nesta lista foram encontrados dividindo um polinômio de Newman de grau $\le 1000$ .
Teorema: Todo polinômio com coeficientes inteiros de grau $\le 44$ com $M(p) < 1,3$ , sem raízes reais não-negativas e sem fatores ciclotômicos, divide um polinômio de Newman. Isso baseia-se no fato de que Known180 é completo até o grau 44.
Casos Não Resolvidos: Três polinômios específicos permanecem não resolvidos (nenhum múltiplo de Newman encontrado até o grau 1000), deixando em aberto a questão de se eles dividem polinômios de Newman de graus superiores.

B. Melhoria da Constante Universal $\sigma$

Usando o método de certificação, os autores identificaram novos polinômios que não dividem nenhum polinômio de Newman, reduzindo assim o limite superior para a constante hipotética $\sigma$ .

Novo Limite: Eles descobriram um polinômio de grau 10:
$x^{10} - x^8 - x^5 + x + 1$
com uma medida de Mahler de aproximadamente 1,419404632.
Significado: Isso melhora o limite superior anterior conhecido de $\approx 1,4366$ (Drungilas et al., 2023) e o limite anterior de $\approx 1,556$ (Hare & Mossinghoff). Se uma constante $\sigma$ existir, ela deve ser $\le 1,419404632$ .
Conjunto de Dados: O artigo fornece uma tabela de 33 exemplos certificados (graus 8–12) com medidas de Mahler $\le 1,556$ que não dividem nenhum polinômio de Newman.

C. Polinômios de Newman com Raízes Repetidas

Os autores investigaram polinômios de Newman divisíveis por $l(x)^2$ (onde $l(x)$ é o polinômio de Lehmer transformado).

Resultados: Eles construíram explicitamente polinômios de Newman divisíveis por $l(x)^2$ com graus até 150.
Resultado Negativo: Eles provaram que nenhum polinômio de Newman de grau $\le 160$ é divisível por $l(x)^3$ . Isso estende a verificação anterior de Mossinghoff (que parou no grau 120).
Dados: O artigo fornece uma tabela abrangente desses polinômios codificados em formato hexadecimal.

4. Significado e Contribuições

Refinamento de Limites: O artigo apertou significativamente os limites teóricos relativos à existência de múltiplos de Newman, empurrando o limite conhecido de "medida de Mahler proibida" de $\approx 1,436$ para $\approx 1,419$ .
Estrutura Algorítmica: Demonstra a eficácia da Programação Linear Mista Inteira (PLMI) na resolução de problemas de teoria dos números envolvendo polinômios com coeficientes restritos. O método mostrou-se flexível o suficiente para lidar tanto com restrições de desigualdade (encontrar múltiplos) quanto com restrições de igualdade (cancelar restos).
Dados Abrangentes: Os autores fornecem um conjunto de dados completo (análise Known180, não-divisores certificados e múltiplos construídos) disponível para pesquisa futura, incluindo scripts de verificação em GP/PARI.
Resolução de Questões Abertas: O trabalho confirma que, para polinômios de baixo grau ( $\le 44$ ) com pequena medida de Mahler, o obstáculo para dividir um polinômio de Newman é quase exclusivamente a presença de raízes reais positivas, com apenas três exceções menores pendentes de buscas em graus mais altos.

5. Conclusão

O artigo conclui que, embora a existência de uma constante universal $\sigma$ permaneça uma questão em aberto, o espaço de busca para contraexemplos foi drasticamente estreitado. Os autores sugerem que sua estrutura baseada em PLMI é uma ferramenta poderosa para investigações futuras sobre polinômios de Borwein, Littlewood e Newman, permitindo potencialmente novas melhorias nos limites e a descoberta de novas propriedades estruturais de polinômios com coeficientes restritos.