🔢 mathematics

A Distinct Covering System with Minimum Modulus 7 and Minimal Least Common Multiple 10080

Este artigo refuta a conjectura de Klein ao construir um sistema de cobertura distinto com módulo mínimo 7 e mínimo múltiplo comum 10080, enquanto simultaneamente prova que nenhum tal sistema pode existir com um mínimo múltiplo comum menor através de um argumento de filtragem em múltiplos estágios e verificação computacional.

Autores originais: Jiheng Zhang, Shiliang Zhang

Publicado 2026-07-22

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Jiheng Zhang, Shiliang Zhang

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 a reta numérica como uma rodovia infinita que se estende em ambas as direções, povoada por todos os números inteiros, do menos infinito ao infinito positivo. No mundo da matemática, especificamente em um ramo chamado teoria dos números, existe um enigma fascinante sobre como "cobrir" toda essa rodovia usando nada além de um conjunto de placas de trânsito. Essas placas são chamadas de progressões aritméticas. Pense em uma placa que diz: "A cada 7 carros, um é um carro vermelho", ou "A cada 12 carros, um é um carro azul". Se você posicionar placas suficientes em diferentes intervalos, poderá garantir que cada um dos carros seja vermelho ou azul (ou outra cor). Quando você consegue cobrir todos os inteiros com uma coleção desses padrões repetitivos, você criou um sistema de cobertura.

As regras do jogo tornam-se mais rigorosas quando os matemáticos perguntam sobre um sistema de cobertura distinto. Isso significa que cada placa deve ter um intervalo único; você não pode ter duas placas que digam ambas "a cada 7 carros". Você deve usar números diferentes para seus intervalos, como 7, 8, 9, 10 e assim por diante. Uma questão natural é: quão pequeno pode ser o menor intervalo? Por muito tempo, os matemáticos se perguntaram se haveria um limite rígido para o quão pequeno esse "módulo mínimo" poderia chegar. Recentemente, foi provado que existe, de fato, um limite, mas o mistério que permanecia era sobre a eficiência. Se você fixar o menor intervalo (digamos, 7), qual é o menor "maior número" (o mínimo múltiplo comum) que você precisa para fazer todo o sistema funcionar? É como perguntar: se o seu passo é de 7 passos, até onde você tem que caminhar antes que seu padrão de passos se alinhe perfeitamente com todas as posições possíveis na estrada?

Este artigo aborda exatamente essa questão para o caso específico onde o menor intervalo é 7. Os autores, Shiliang Zhang e Jiheng Zhang, propuseram-se a encontrar o absoluto mínimo "maior número" necessário para construir um sistema de cobertura distinto começando com um passo de 7. Antes deste trabalho, um matemático chamado Klein construiu um sistema funcional com um "maior número" de 15.120 e supôs que este seria o melhor possível. No entanto, os autores deste artigo provam que o palpite de Klein era alto demais. Eles construíram um novo sistema, mais eficiente, que funciona com um "maior número" de apenas 10.080. Além disso, eles provaram matematicamente que é impossível fazê-lo com qualquer número menor que 10.080. Eles não apenas encontraram uma solução melhor; eles provaram que esta é a melhor solução.

A História de Detetive do Número 10.080

Para entender como os autores resolveram isso, imagine que você é um detetive tentando encontrar uma chave específica em um enorme armazém empoeirado. O armazém contém todos os possíveis "maiores números" (mínimo múltiplo comum) que são múltiplos de 7 e que caem entre 5.040 e 10.080. Seu objetivo é provar que cada número neste intervalo é uma "chave falsa" que não abrirá a porta, enquanto o número 10.080 é a "chave real".

O Primeiro Filtro: A Soma Recíproca
Os autores começam aplicando um "filtro de soma recíproca". Em termos cotidianos, imagine que cada intervalo possível (como 7, 8, 9) contribui com um pouco de "poder de cobertura" para o sistema. A regra é que a soma do "poder" de todos os seus intervalos escolhidos deve ser maior que 1 para cobrir toda a rodovia. Se você somar o "poder" de cada intervalo possível disponível para um candidato específico e o total for menor que 1, esse candidato é imediatamente desqualificado. Este filtro foi muito eficaz, eliminando instantaneamente a maioria dos números no armazém e deixando apenas 18 candidatos suspeitos.

O Segundo Filtro: O Teste de Programação Inteira
Em seguida, os autores usaram uma poderosa ferramenta de computador chamada "programação inteira". Pense nisso como um resolvedor de quebra-cabeças super organizado. Para cada um dos 18 candidatos restantes, o computador tentou organizar as placas de trânsito (classes de resíduos) para ver se elas poderiam cobrir toda a rodovia sem deixar lacunas. O computador foi inteligente o suficiente para ignorar arranjos redundantes (como deslocar todo o padrão em um passo, o que não altera o resultado). Este filtro foi implacável; ele eliminou 14 dos 18 candidatos, provando que, não importa como você organizasse as placas para esses números, você sempre deixaria alguns carros descobertos.

O Terceiro Filtro: A Soma Parcial
Quatro candidatos restaram: 5.040, 7.560, 8.400 e 9.240. Estes eram os "casos difíceis". Os autores perceberam que, para alguns desses números, você poderia cobrir quase toda a rodovia, deixando apenas uma pequena fração de carros descobertos. Isso tornava os testes anteriores complicados. Para lidar com isso, eles usaram um "filtro de soma parcial". Em vez de assumir que as placas cobrem tudo perfeitamente, eles calcularam exatamente quanto da rodovia o melhor arranjo de um subconjunto de placas poderia cobrir. Eles descobriram que, para 8.400 e 9.240, mesmo o arranjo mais otimista de placas deixava uma lacuna grande demais para ser preenchida pelas placas restantes. Esses dois números foram descartados.

O Confronto Final: A Computação Gurobi
Isso deixou apenas dois suspeitos persistentes: 5.040 e 7.560. Esses números eram tão bons em cobrir a rodovia que poderiam cobrir mais de 96% e 98%, respectivamente, deixando apenas uma lacuna minúscula e difícil de encontrar. Para resolver isso, os autores executaram simulações computacionais massivas e exaustivas usando um software chamado Gurobi. Eles não apenas adivinharam; eles verificaram cada maneira possível de organizar as placas para esses dois números. O computador rodou por milhares de segundos, verificando milhões de possibilidades e, finalmente, declarou: "Inviável". Isso significa que é matematicamente impossível cobrir a rodovia com um passo mínimo de 7 usando 5.040 ou 7.560 como o maior número.

O Vencedor: 10.080
Com todos os números menores eliminados, os autores voltaram sua atenção para 10.080. Eles não apenas provaram que era possível; eles construíram o sistema real. Eles listaram os intervalos específicos e os pontos de partida (como "a cada 7 carros começando no 6", "a cada 8 carros começando no 7" e assim por diante) que cobrem perfeitamente toda a reta numérica. Eles verificaram que este sistema funciona, provando que 10.080 é, de fato, uma solução funcional.

A Conclusão

O artigo conclui com uma resposta definitiva: o menor "maior número" possível para um sistema de cobertura distinto com um passo mínimo de 7 é exatamente 10.080. Isso melhora o recorde anterior de 15.120. Os autores não apenas encontraram um número melhor; eles provaram que nenhum número menor poderia funcionar. Eles fizeram isso filtrando sistematicamente todas as possibilidades, desde simples verificações matemáticas até simulações computacionais complexas, não deixando pedra sobre pedra. O resultado é um fato preciso e comprovado no mundo da teoria dos números, mostrando que, embora você possa chegar muito perto de cobrir a rodovia infinita com números menores, você simplesmente não consegue fazê-lo perfeitamente até atingir 10.080.

Resumo Técnico: Um Sistema de Cobertura Distinto com Módulo Mínimo 7 e Mínimo Mínimo de Mínimo Comum Múltiplo 10080

Enunciado do Problema
O artigo aborda o problema de determinar o mínimo possível do mínimo comum múltiplo (LCM), denotado por $L_{\min}(m)$ , para um sistema de cobertura distinto com um módulo mínimo $m$ prescrito. Um sistema de cobertura distinto é uma coleção finita de progressões aritméticas $\{a_i \pmod{m_i}\}$ com módulos $m_i$ pairwise distintos que cobrem todos os inteiros. Embora Hough (2015) tenha provado que o módulo mínimo em qualquer sistema de cobertura distinto é limitado por uma constante absoluta, os valores específicos de $L_{\min}(m)$ para $m \le 6$ foram objeto de construção e verificação explícitas.

Previamente a este trabalho, os valores para $m \le 6$ foram estabelecidos: $L_{\min}(3)=120$ , $L_{\min}(4)=360$ , $L_{\min}(5)=1440$ e $L_{\min}(6)=5040$ . Para $m=7$ , Klein (2024) construiu um sistema com $L=15120$ e conjecturou que este seria o mínimo. Este artigo visa resolver o caso $m=7$ construindo um sistema com um LCM menor e provando que nenhum LCM menor é possível.

Metodologia
Os autores empregam uma estratégia de filtragem sucessiva para eliminar valores candidatos para o LCM $L$ no intervalo $5040 \le L < 10080$ . A prova baseia-se no princípio da "completude de divisores": se um sistema de cobertura distinto existe com módulo mínimo $m$ e LCM $L$ , pode-se adicionar classes de congruência arbitrárias para qualquer divisor $d$ de $L$ (onde $d \ge m$ ) sem destruir a propriedade de cobertura. Assim, para provar a não existência para um $L$ específico, basta mostrar que o conjunto de módulos "completado por divisores" $D_m(L) = \{d : d|L, d \ge m\}$ não pode formar um sistema de cobertura.

O processo de filtragem consiste em quatro estágios:

Filtro de Soma de Recíprocos: Baseado na obstrução de Mirsky–Newman (Lema 1), que afirma que para qualquer sistema de cobertura distinto, $\sum 1/m_i > 1$ . Os autores computam $S_7(L) = \sum_{d|L, d \ge 7} 1/d$ . Se $S_7(L) \le 1$ , $L$ é imediatamente descartado. Isso reduz o espaço de busca de todos os múltiplos de 7 no intervalo para 18 candidatos.
Filtro de Programação Inteira (IP): Para os candidatos restantes, os autores formulam um problema de viabilidade de programação inteira binária. Variáveis $x_{m,a}$ indicam se a classe de resíduo $a \pmod m$ é selecionada. As restrições impõem exatamente uma classe por módulo e a cobertura de todos os resíduos módulo $L$ . Para reduzir a simetria, os autores aplicam normalizações de invariância por translação e troca de camada de resíduo (Lemmas 2 e 3) para fixar classes de congruência específicas (ex: $6 \pmod 7$ , $7 \pmod 8$ ) antes de resolver. Este filtro elimina 14 dos 18 candidatos.
Filtro de Soma Parcial: Para os casos restantes mais difíceis (especificamente 8400 e 9240), os autores refinam o argumento da soma de recíprocos. Em vez de assumir que todas as classes selecionadas são disjuntas, eles computam a cobertura máxima $\alpha_A(L)$ de um subconjunto de módulos $A$ via uma IP menor, então adicionam a contribuição máxima teórica dos módulos restantes $B$ . Se $\alpha_A(L) + \sum_{m \in B} 1/m < 1$ , o candidato é descartado. Isso elimina 8400 e 9240.
Computação Completa Gurobi: Os dois últimos candidatos, $L=5040$ e $L=7560$ , resistem ao filtro de soma parcial porque admitem "quase-coberturas" (cobrem >96% e >98% dos resíduos, respectivamente). Esses casos são resolvidos executando verificações de viabilidade completas usando o solver Gurobi (v13.0.1) nos sistemas completos de completude de divisores.

Contribuições Principais e Resultados

Construção: Os autores constroem explicitamente um sistema de cobertura distinto com módulo mínimo 7 e mínimo comum múltiplo 10080. Este sistema consiste em 63 módulos distintos, sendo o menor deles 7.
Prova de Minimalidade: O artigo prova que $L_{\min}(7) = 10080$ . Ao eliminar sistematicamente todos os $L < 10080$ (especificamente os 18 candidatos que sobreviveram ao filtro de soma inicial), os autores demonstram que nenhum sistema de cobertura distinto com módulo mínimo 7 pode ter um LCM menor que 10080.
Refutação da Conjectura: O resultado desmente a conjectura de Klein de que 15120 era o LCM mínimo para $m=7$ .
Dados Computacionais: O artigo fornece uma tabela abrangente de tempos de execução do Gurobi e resultados para todos os 18 candidatos, incluindo os dois casos mais difíceis ( $L=5040$ e $L=7560$ ), que exigiram aproximadamente 13.789 e 13.159 segundos, respectivamente, para provar a inviabilidade.

Significância
O artigo estabelece o valor exato de $L_{\min}(7)$ , estendendo a sequência conhecida de LCMs mínimos para sistemas de cobertura distintos. O trabalho demonstra a eficácia de combinar teoria analítica dos números (somas de recíprocos) com otimização combinatória (programação inteira e branch-and-bound) para resolver problemas de existência em progressões aritméticas. Os autores observam que a dificuldade encontrada com $L=5040$ e $L=7560$ — onde os sistemas cobrem quase todos os resíduos, mas falham em cobrir o restante — sugere que melhorias futuras na prova de minimalidade para módulos mais altos podem exigir certificados híbridos mais aguçados capazes de distinguir "quase-coberturas" de sistemas de cobertura genuínos sem depender apenas da verificação total de branch-and-bound.

A História de Detetive do Número 10.080

A Conclusão

Mais como este