💻 computer science

Witness-split + window-cardinality refinement for $r_3(N)$ : Architecture, empirical results, and a structural hard pocket

Este artigo apresenta um arcabouço computacional reproduzível combinando divisão de testemunhas (witness-splitting), poda de cardinalidade de janela (window-cardinality pruning) e solvers híbridos SAT/MIP para investigar rigorosamente o limite superior de $r_3(212)$ , eliminando com sucesso a maioria dos candidatos a 44-conjuntos enquanto isola dois casos estruturais resistentes que permanecem não provados apesar de extensos esforços de verificação.

Autores originais: Mehmet Ergezer

Publicado 2026-06-04

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Mehmet Ergezer

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ê está tentando arrumar uma mala (os números de 1 a 212) com o maior número possível de itens, mas com uma regra estrita: Você não pode escolher três itens que formem um padrão aritmético perfeito.

Por exemplo, se você escolher o número 2, não poderá escolher também o 4 e o 6, porque $2, 4, 6$ é um padrão onde cada número é 2 unidades maior que o anterior. Isso é chamado de "progressão aritmética de 3 termos".

Matemáticos têm tentado descobrir o número máximo absoluto de itens que você pode colocar nessa mala sem quebrar a regra. Para uma mala de tamanho 211, a resposta conhecida é 43. A grande questão para este artigo é: Você consegue colocar 44 itens em uma mala de tamanho 212?

O autor, Mehmet Ergezer, não apenas adivinhou; ele construiu uma enorme fábrica digital para tentar provar que 44 é impossível. Veja como o artigo se divide, usando analogias simples:

1. A Estratégia: A Fábrica de "Divisão por Testemunha" (Witness Split)

Tentar verificar todas as combinações possíveis de 44 números entre 212 é como tentar encontrar um grão de areia específico em todas as praias da Terra. É grande demais para um único computador lidar.

Então, o autor usou um truque inteligente:

A Testemunha: Ele começou com uma lista "segura" conhecida de 43 números que já funciona.
A Divisão: Ele pegou os 24 números mais "importantes" dessa lista segura e pediu ao computador para verificar todos os cenários possíveis de "Sim/Não" para eles.
O Resultado: Isso transformou a montanha impossível de dados em 12,5 milhões de pilhas menores e gerenciáveis (chamadas de "pedaços" ou "chunks"). O computador então tentou resolver cada pilha, uma por uma.

2. As Ferramentas: A "Janela" e o "Refinamento"

Para tornar o computador mais rápido, o autor adicionou duas ferramentas especiais:

O Cartão de Janela (O Podador): Imagine olhar através de uma janela para uma pequena seção da mala. Já sabemos de matemática anterior que uma pequena janela de tamanho 50 só pode conter, digamos, 10 itens. O computador usa essa regra para descartar instantaneamente qualquer pilha que tente colocar 11 itens naquela janela. Esta foi a ferramenta mais poderosa, reduzindo o número de pilhas difíceis em quase 30%.
O Refinamento (O Mergulho Profundo): Se uma pilha fosse difícil demais para ser resolvida em 60 segundos, o computador não desistia. Ele pegava aquela pilha específica, adicionava mais regras a ela e tentava novamente com um tempo limite maior. Isso é como pegar uma caixa trancada, escolher uma fechadura específica e tentar novamente com uma chave maior.

3. Os Resultados: O "Bolso Difícil" (Hard Pocket)

Após rodar milhões dessas verificações em um cluster de supercomputadores, eis o que aconteceu:

Zero Sucesso: O computador nunca encontrou uma única maneira válida de embalar 44 itens. Toda vez que tentava, batia em um muro e dizia: "Impossível".
A Evidência: Isso é uma evidência forte de que 44 é impossível, mas não é uma prova formal ainda. Por quê? Porque ainda existem alguns pilhas teimosas que o computador não conseguiu terminar a tempo.

O "Bolso Difícil" (Os Pedaços Resistentes):
Das milhões de pilhas, o autor encontrou um pequeno e teimoso grupo de 45 pilhas que se recusaram a ser resolvidas mesmo após receberem tempo extra e ferramentas diferentes.

O Ataque LP: Eles tentaram um tipo diferente de resolvedor matemático (chamado HiGHS) que olha para o problema como uma curva suave. Ele falhou em resolver qualquer uma das 45 pilhas.
O Ataque CDCL: Eles tentaram um terceiro tipo de resolvedor (chamado CDCL) que trabalha como um detetive, aprendendo com seus erros. Este teve sucesso! Ele resolveu 18 das 45 pilhas.
Os 2 Finais: No entanto, 2 pilhas (rotuladas como T1c) permaneceram completamente sem solução. Elas resistiram ao primeiro resolvedor, ao segundo e ao terceiro. Elas são o "chefão final" deste problema.

4. A Conclusão: O "Gap de Unidade"

O artigo conclui que:

Temos uma lista verificada de 43 números que funciona.
Temos evidências fortes de que 44 é impossível, porque o computador tentou milhões de vezes e falhou.
No entanto, devido a essas 2 pilhas finais teimosas, ainda não temos uma prova matemática de 100%. A resposta é quase certamente 43, mas o "gap" (lacuna) entre 43 e 44 ainda está tecnicamente aberto.

5. O Presente para a Comunidade

Em vez de apenas dizer "eu desisto", o autor está liberando todos os dados. Ele está entregando os 2 pilhas teimosas para o mundo como um desafio.

Ele fornece o código exato e os dados para que outros matemáticos possam tentar resolver apenas essas duas pilhas.
Ele até traduziu o problema para uma linguagem de sistemas de prova formal (Lean), convidando cientistas da computação para tentarem provar usando motores de lógica.

Em resumo: O autor construiu uma enorme máquina digital que tentou quebrar o recorde de embalar números sem padrões. A máquina falhou em encontrar uma maneira de quebrar o recorde, mas travou em dois pequenos e incrivelmente difíceis quebra-cabeças. O artigo diz: "Estamos 99,9% seguros de que a resposta é 43, mas aqui estão os dois quebra-cabeças finais que você precisa resolver para provar isso".

Resumo Técnico: Refinamento de Witness-Split + Window-Cardinality para $r_3(212)$

Enunciado do Problema
O artigo aborda o cálculo exato de $r_3(N)$ , definido como o tamanho máximo de um subconjunto de $[1, N]$ que não contém uma progressão aritmética de três termos (3-AP) não trivial. Enquanto o comportamento assintótico é bem estudado (ex: teorema de Roth, Kelley–Meka), o foco aqui é a fronteira finita em $N=212$ . Com base na OEIS A003002, $r_3(211) = 43$ . Os autores investigam o problema de decisão: Existe um subconjunto de 44 elementos livre de 3-AP em $[1, 212]$ ?
Os autores verificaram de forma independente uma testemunha (witness) de 43 elementos, estabelecendo que $r_3(212) \ge 43$ . A questão do limite superior é se $r_3(212) \le 43$ . Uma condição necessária para qualquer hipotético conjunto de 44 elementos é que ele deve conter ambos os extremos, 1 e 212; caso contrário, ele se traduziria em um conjunto de 44 elementos em $[1, 211]$ , contradizendo o valor conhecido. Assim, o problema reduz-se a provar a inviabilidade de um conjunto de 44 elementos contendo $\{1, 212\}$ .

Metodologia e Arquitetura
Os autores propõem um framework computacional reproduzível combinando cinco componentes para buscar um conjunto de 44 elementos viável:

Modelo CP-SAT de Forma Decisória: O problema é codificado usando variáveis booleanas $x_i$ para $i \in [1, 212]$ . As restrições incluem:
- Inequações de 3-AP: $x_a + x_b + x_c \le 2$ para todas as triplas $(a, b, c)$ que formam uma AP.
- Igualdade de cardinalidade: $\sum x_i = 44$ (mais rigoroso para propagação do que uma desigualdade).
- Forçamento de extremidades: $x_1 = x_{212} = 1$ .
- Quebra de simetria: Ordenação lexicográfica para eliminar a simetria de reflexão.
Witness-Splitting (Divisão por Testemunha): Para gerenciar o espaço de busca, os autores utilizam uma testemunha de 43 elementos $A_{43}$ verificada. Eles classificam os elementos de $A_{43}$ pelo grau de incidência de AP e selecionam os 24 superiores. O espaço de busca é dividido em $2^{24}$ "pedaços" (chunks) ao fixar os valores dessas 24 variáveis. Muitos pedaços são podados imediatamente se o prefixo fixo forçar uma 3-AP.
Pruning de Window-Cardinality (Poda de Cardinalidade de Janela): Uma intervenção crítica envolve a adição de inequações válidas derivadas da OEIS A003002. Para qualquer janela $[a, a+L-1]$ , a soma das variáveis é limitada por $r_3(L)$ . Com $N=212$ , isso adiciona 22.154 inequações, fortalecendo significativamente o modelo além das restrições brutas de 3-AP.
Refinamento Recursivo: Pedaços que retornam UNKNOWN na camada ampla (profundidade 24) são refinados estendendo o prefixo fixo com as próximas variáveis de testemunha de maior grau (profundidades 40, 48, 56, 64) e resolvendo novamente com limites de tempo mais longos.
Diversidade de Solvers e Engenharia: A campanha utiliza um pipeline baseado em SLURM rodando no cluster UMass Unity. Ela emprega:
- CP-SAT (OR-Tools): Para a passagem ampla e refinamento recursivo.
- HiGHS (MIP): Um solver baseado em relaxação LP usado para atacar os pedaços "UNKNOWN" mais difíceis.
- CDCL/SAT (CaDiCaL): Usado para reatacar pedaços resistentes a métodos LP, gerando provas DRAT de insatisfatibilidade.

Resultados Empíricos
A campanha processou milhões de subproblemas através da varredura de profundidade-24 e várias etapas de refinamento.

Zero Soluções Viáveis: Em todos os subproblemas testados (passagem ampla, refinamentos, HiGHS e CDCL), zero conjuntos de 44 elementos foram encontrados. Isso fornece um forte suporte empírico para $r_3(212) = 43$ , embora não seja uma prova formal.
Impacto da Window-Cardinality: Habilitar as inequações de window-cardinality reduziu a taxa de UNKNOWN nas passagens amplas em aproximadamente 28 pontos percentuais (ex: de ~30% para ~1,65% em lotes controlados), tornando-a a camada de poda mais eficaz.
O Núcleo de Dificuldade Estrutural (Hard Pocket):
- De um lote de expansão de 100.000 pedaços, 6.071 retornaram UNKNOWN.
- Um recapitulativo de 300 segundos de uma amostra aleatória desses deixou 45 pedaços resistentes (Tier T1).
- Ataque HiGHS: Uma execução de uma hora do HiGHS fechou 0/45. Uma auditoria de 8 horas fechou 25/45, deixando 20 pedaços (Tier T1b) com limites duais presos em 0.0, indicando que a relaxação LP não forneceu um certificado de insatisfatibilidade.
- Ataque CDCL: Um ataque puro de CDCL/SAT nos 20 pedaços T1b fechou 18/20, gerando provas DRAT independentemente verificadas.
- O Residual (T1c): Dois pedaços (IDs 40959 e 48895) permaneceram UNKNOWN mesmo após execuções de 12 horas de CDCL puro e diagnósticos de CDCL com janela de 4 horas. Esses dois pedaços resistem aos paradigmas CP-SAT, HiGHS (LP-MIP) e CDCL.

Contribuições Principais
O artigo enquadra explicitamente sua contribuição como metodológica, e não como um novo valor exato para $r_3(212)$ . As contribuições específicas são:

Arquitetura: Um framework reproduzível combinando witness-splitting, poda de window-cardinality e refinamento recursivo para buscas de limite superior exatas.
Relato Empírico: Uma análise detalhada da campanha $N=212, K=44$ , incluindo trade-offs de solvers e a não uniformidade do espaço de busca (ex: pedaços "middle-out" com atribuições de pin específicas são significativamente mais difíceis).
Caracterização do Núcleo de Dificuldade: Identificação de uma obstrução estrutural (T1c) que é invariante através dos paradigmas CP-SAT, HiGHS e CDCL sob limites de tempo generosos.
Liberação de Benchmarks: Uma liberação em camadas de instâncias:
- T1a: 25 pedaços fechados pelo HiGHS.
- T1b \ T1c: 18 pedaços fechados por CDCL com provas DRAT.
- T1c: Os 2 pedaços residuais finais, enquadrados como o problema aberto mais agudo.
- T2/T3: Os 6.071 UNKNOWNs amplos e o gerador completo de 12,5M de pedaços para tentativas futuras.
Formalização: Uma codificação em Lean 4 dos alvos T1c para sistemas de busca de prova formal.

Significância e Alegações
Os autores alegam modestamente que, embora a campanha apoie fortemente a conjectura $r_3(212) = 43$ , ela não constitui uma prova formal devido ao residual T1c não resolvido. A significância reside em isolar a barreira computacional específica:

O gap entre os limites certificados é exatamente um ( $43 \le r_3(212) \le 44$ ).
A falha dos métodos baseados em LP (HiGHS) e o sucesso parcial do CDCL sugerem que a dificuldade não é apenas um artefato de propagação, mas uma propriedade estrutural onde o gap da relaxação LP é apertado e o certificado de insatisfatibilidade inteira é combinatoriamente difuso.
O trabalho postula que fechar o gap requer ou limites aditivo-combinatórios mais fortes (ex: limites de partição de análise de Fourier ou de múltiplas janelas) ou sistemas de branch-and-bound customizados que explorem simetrias específicas do problema não capturadas por solvers de propósito geral.

O trabalho serve como um benchmark para a comunidade, oferecendo instâncias específicas e verificadas (T1c) que representam o limite atual dos solvers de otimização combinatória de propósito geral para esta classe de problemas.