Heilbronn's Problem in the Unit Triangle: Certified Optimal Configurations for up to $n\le 8$

Resumo Técnico: Configurações Ótimas Certificadas para o Problema de Heilbronn no Triângulo Unitário ($n \le 8$)

Definição do Problema
Este artigo aborda o problema do triângulo de Heilbronn dentro do domínio específico do triângulo retângulo unitário $T = \{(x, y) \in \mathbb{R}^2 : x \ge 0, y \ge 0, x + y \le 1\}$, que possui uma área de $1/2$. O objetivo é determinar o posicionamento de $n$ pontos dentro de $T$ que maximize a área mínima entre todos os triângulos formados por trios desses pontos. Seja $\Delta^\triangle_n$ esta área mínima máxima alcançável. Embora existam extensos resultados exatos para o quadrado unitário, este trabalho foca no simplex unitário, observando que transformações afins preservam razões de área, mas não mapeiam triângulos para quadrados, o que exige uma análise específica do domínio.

Metodologia
Os autores empregam um arcabouço de Programação Quadrática com Restrições Inteiras Mistas (MIQCP), previamente desenvolvido para o quadrado unitário em um artigo complementar [1], adaptado aqui para o domínio triangular. A essência da metodologia baseia-se em duas percepções estruturais:

1. Estrutura de Fronteira (Proposição 1): Para $n \ge 5$, a menos que uma configuração ótima ocupe todos os três vértices de $T$, existe uma configuração ótima (ou uma imagem afim preservadora de área de uma) com pelo menos quatro pontos na fronteira $\partial T$. Crucialmente, uma aresta do triângulo deve carregar dois desses pontos de fronteira, enquanto as outras duas arestas carregam pelo menos um cada.
2. Redução de Simetria (Corolário 1): Utilizando a simetria afim $S_3$ do triângulo (permutando vértices com módulo de Jacobiano 1), os autores fixam a aresta que carrega dois pontos de fronteira (escolhida como a perna $e_1$) e rotulam os pontos no sentido anti-horário. Isso reduz o espaço de busca ao fixar quatro pontos de fronteira e quebrar simetrias de reflexão residuais.

O modelo de otimização (Equação 1) maximiza uma variável $z$ sujeita a restrições que garantem que $z$ seja menor ou igual à área absoluta de cada triângulo formado pelos $n$ pontos. Os termos bilineares nos cálculos de área são tratados via substituição ($w_{ij} = x_i y_j$), e variáveis binárias $b_t$ gerenciam a orientação das áreas com sinal. O problema é resolvido para otimalidade global comprovada utilizando o solver Gurobi 13.

Principais Contribuições e Resultados
O artigo fornece as primeiras provas de otimalidade global para $n=7$ e $n=8$ no triângulo unitário, fechando lacunas significativas deixadas por métodos anteriores de busca em grade e branch-and-bound.

• Soluções Exatas para $n \le 7$: Os autores recuperam ótimos exatos com configurações de coordenadas explícitas:
  • $n=3, 4$: Resultados clássicos ($1/2$ e $1/6$).
  • $n=5$: $\frac{3}{2} - \sqrt{2}$. A solução é uma família de um parâmetro; os autores listam um ponto extremo representativo.
  • $n=6$: $1/16$. Esta é uma família de dois parâmetros; um representante racional é fornecido.
  • $n=7$: $7/144$. A configuração ótima reside em uma grade de $1/12$.
• Certificação Numérica para $n=8$: Para $n=8$, nenhuma expressão de forma fechada é conhecida. Os autores confirmam uma conjectura de Chen, Zeng e Zhou [7] de que o ótimo é a raiz real única de um polinômio séptico (grau 7) específico.
  • A solução numérica é certificada com 250 dígitos.
  • Os autores provam que o grupo de Galois deste polinômio séptico é o grupo simétrico $S_7$. Consequentemente, o valor ótimo e as coordenadas não podem ser expressos em radicais, explicando por que a literatura anterior lista apenas aproximações numéricas.
• Eficiência: O modelo MIQCP proposto resolve $n=7$ em 22,6 segundos e $n=8$ em 2324 segundos em uma única máquina. Isso contrasta fortemente com esforços anteriores: uma busca em grade para $n=7$ deixou um erro de 18%, e uma abordagem de branch-and-bound para $n=8$ exigiu 11.000 horas de CPU para atingir um erro de apenas $2,7 \times 10^{-5}$.

Significância e Alegações
O artigo alega estabelecer as primeiras provas de otimalidade para $n=7$ e $n=8$ no triângulo unitário. Ao alavancar o resultado da estrutura de fronteira, os autores reduzem o problema de otimização contínua a um modelo de inteiros mistos tratável que certifica a otimalidade global.

Para $n=8$, o trabalho faz a ponte entre a conjectura numérica e a certificação rigorosa. Embora os autores não provem que o conjunto específico de 11 triângulos mínimos identificados por Chen, Zeng e Zhou é o único conjunto mínimo (uma condição necessária para provar totalmente a conjectura), sua reconstrução confirma a raiz conjecturada com precisão extrema e valida as propriedades do grupo de Galois. O artigo conclui que a principal questão aberta restante para $n=8$ é demonstrar que todos os onze triângulos específicos no conjunto conjecturado são simultaneamente mínimos. O trabalho futuro é identificado como a extensão desses certificados para $n \ge 9$ e a caracterização das famílias ótimas para $n=5$ e $n=6$.