Optimally Packing a Large Square by Unit Squares

Resumo Técnico: Empacotamento Ótimo de um Quadrado Grande por Quadrados Unitários

Enunciado do Problema
O artigo aborda o problema de empacotar um quadrado grande $S(x)$ de lado $x$ com quadrados unitários que possuem interiores disjuntos. O objetivo é minimizar o espaço desperdiçado $W(x)$, definido como a área de $S(x)$ não coberta pelos quadrados unitários. Embora $W(x) = 0$ quando $x$ é um inteiro, o problema torna-se não trivial quando $x$ não é um inteiro. Um empacotamento ingênuo de quadrados unitários paralelos aos lados de $S(x)$ resulta em um espaço desperdiçado de $W(x) = O(x\{x\})$, o que simplifica para $O(x)$ se a parte fracionária $\{x\}$ estiver afastada de zero. O desafio central é determinar a taxa de crescimento assintótico ótima de $W(x)$ ao permitir que os quadrados unitários sejam orientados em ângulos ligeiros.

Contexto Histórico e Limites Anteriores
O artigo situa sua contribuição dentro de uma linha do tempo de limites estabelecidos:

• Limite Inferior: Roth e Vaughan (1978) provaram que $W(x) > 10^{-100}\sqrt{x - \lfloor x \rfloor}$, estabelecendo que o limite não pode ser melhor que $\Omega(x^{1/2})$.
• Limites Superiores:
  • Erdős e Graham (1975) mostraram que $W(x) = O(x^{7/11})$.
  • Montgomery melhorou isso para $O(x^{(3-\sqrt{3})/2})$.
  • Chung e Graham (2009) refinaram ainda mais o limite para $O(x^{(3+\sqrt{2})/7} \log x)$.
  • Em 2020, Chung e Graham alegaram um limite de $O(x^{3/5})$, mas o artigo observa que este resultado continha um erro, retornando ao melhor limite conhecido, o de 2009, até o presente trabalho.

Metodologia
O artigo propõe um novo algoritmo para alcançar o limite $O(x^{3/5})$, corrigindo o erro na alegação de 2020. A prova prossegue em quatro estágios distintos:

1. Empacotamento Trivial Inicial: O quadrado $S(x)$ é primeiro empacotado trivialmente com quadrados unitários alinhados paralelamente aos lados, deixando duas regiões retangulares estreitas de largura $h$. Uma dessas regiões retangulares, $R$, é selecionada para processamento posterior.
2. Empilhamento com Inclinação: O retângulo $R$ é empacotado usando "pilhas" de $n$ quadrados unitários inclinadas em um ângulo $\theta$. Essas pilhas tocam tanto as paredes verticais quanto as paredes inclinadas do retângulo. Este processo deixa para trás uma região trapezoidal $T$ nas extremidades. O ângulo $\theta$ é escolhido de tal forma que $\theta \asymp h^{-1/2}$.
3. Empacotamento Trapezoidal de Dois Estágios: O núcleo do algoritmo envolve o preenchimento do trapézio $T$ usando dois subalgoritmos complementares:
   • Algoritmo 1: Empacota $T$ usando pilhas quase horizontais e verticais de comprimentos decrescentes ($m, m-1, \dots$). Este algoritmo introduz um deslocamento angular específico, mudando a inclinação de $\psi$ na base para $\phi$ no topo, onde a diferença $\phi - \psi \approx \theta$.
   • Algoritmo 2: Projetado para "desfazer" o deslocamento angular introduzido pelo Algoritmo 1. Ele começa onde o Algoritmo 1 termina, empacotando pilhas de comprimento $m+1$ e $m$ para restaurar a geometria necessária para reiniciar o Algoritmo 1.
   • Aplicação Iterativa: Estes dois algoritmos são aplicados sucessivamente em um ciclo. O artigo demonstra que os parâmetros ($\phi, \psi, \theta, m$) podem ser fixados ou ajustados de modo que os termos de erro ($\epsilon, \epsilon'$) não se acumulem destrutivamente ao longo das iterações.
4. Otimização de Parâmetros: A largura $w$ do trapézio $T$ e o número de iterações são otimizados. O algoritmo é aplicado aproximadamente $\sqrt{h}$ vezes para cobrir o trapézio.

Resultados Principais e Análise
O artigo deriva o desperdício total de espaço $W(x)$ somando o desperdício das pilhas verticais e o desperdício gerado dentro das regiões trapezoidais:

• Desperdício das Pilhas: O empacotamento das $O(x)$ pilhas verticais com inclinação $\theta$ gera um desperdício proporcional a $O(x\theta)$.
• Desperdício dos Trapézios: A aplicação iterativa dos dois algoritmos de empacotamento no trapézio $T$ gera um desperdício total de $O(h^{3/4})$.
• Otimização: O desperdício total é limitado por $W(x) \ll \frac{x}{\sqrt{h}} + h^{3/4}$. Ao igualar os dois termos ($x h^{-1/2} \sim h^{3/4}$), a escolha ótima é $h \sim x^{4/5}$.

Substituindo $h = x^{4/5}$ no limite, obtém-se:
$$W(x) = O(x^{3/5})$$

Significância e Alegações
O artigo afirma provar rigorosamente que o espaço desperdiçado no empacotamento de um quadrado grande por quadrados unitários é limitado por $O(x^{3/5})$. Este resultado valida a alegação feita anteriormente por Chung e Graham em 2020, que havia sido retratada devido a um erro. A significância reside no fornecimento de uma prova corrigida para este limite assintótico específico, melhorando o limite anterior de $O(x^{(3+\sqrt{2})/7} \log x)$. Os autores enfatizam que isso é alcançado através de um algoritmo construtivo específico envolvendo a interação de duas estratégias de empacotamento que gerenciam discrepâncias angulares e acúmulo de erro dentro de sub-regiões trapezoidais. O artigo não propõe aplicações futuras ou implicações além do estabelecimento deste limite superior específico.