Optimally Packing a Large Square by Unit Squares

Resumen Técnico: Empaquetamiento Óptimo de un Cuadrado Grande con Cuadrados Unitarios

Planteamiento del Problema
El artículo aborda el problema de empaquetar un cuadrado grande $S(x)$ de lado $x$ con cuadrados unitarios que tengan interiores disjuntos. El objetivo es minimizar el espacio desperdiciado $W(x)$, definido como el área de $S(x)$ no cubierta por los cuadrados unitarios. Si bien $W(x) = 0$ cuando $x$ es un entero, el problema se vuelve no trivial cuando $x$ no es un entero. Un alineamiento ingenuo de los cuadrados unitarios paralelos a los lados de $S(x)$ produce un espacio desperdiciado de $W(x) = O(x\{x\})$, lo que se simplifica a $O(x)$ si la parte fraccionaria $\{x\}$ está alejada de cero. El desafío central es determinar la tasa de crecimiento asintótico óptima de $W(x)$ permitiendo que los cuadrados unitarios se orienten en ángulos ligeros.

Contexto Histórico y Límites Previos
El artículo sitúa su contribución dentro de una cronología de límites establecidos:

• Límite Inferior: Roth y Vaughan (1978) demostraron que $W(x) > 10^{-100}\sqrt{x - \lfloor x \rfloor}$, estableciendo que el límite no puede ser mejor que $\Omega(x^{1/2})$.
• Límites Superiores:
  • Erdős y Graham (1975) mostraron que $W(x) = O(x^{7/11})$.
  • Montgomery mejoró esto a $O(x^{(3-\sqrt{3})/2})$.
  • Chung y Graham (2009) refinaron aún más el límite a $O(x^{(3+\sqrt{2})/7} \log x)$.
  • En 2020, Chung y Graham afirmaron un límite de $O(x^{3/5})$, pero el artículo señala que este resultado contenía un error, revirtiendo el mejor límite conocido al de 2009 hasta el presente trabajo.

Metodología
El artículo propone un nuevo algoritmo para lograr el límite $O(x^{3/5})$, corrigiendo el error en la afirmación de 2020. La prueba procede en cuatro etapas distintas:

1. Empaquetamiento Trivial Inicial: El cuadrado $S(x)$ se empaqueta primero de forma trivial con cuadrados unitarios alineados paralelamente a los lados, dejando dos regiones rectangulares estrechas de ancho $h$. Se selecciona una de estas regiones rectangulares, $R$, para un procesamiento posterior.
2. Apilamiento con Inclinación: La región $R$ se empaqueta utilizando "pilas" de $n$ cuadrados unitarios inclinadas en un ángulo $\theta$. Estas pilas tocan tanto las paredes verticales como las inclinadas del rectángulo. Este proceso deja atrás una región trapezoidal $T$ en los extremos. El ángulo $\theta$ se elige tal que $\theta \asymp h^{-1/2}$.
3. Empaquetamiento Trapezoidal de Dos Etapas: El núcleo del algoritmo consiste en llenar el trapezoide $T$ utilizando dos subalgoritmos complementarios:
   • Algoritmo 1: Empaqueta $T$ usando pilas casi horizontales y verticales de longitud decreciente ($m, m-1, \dots$). Este algoritmo introduce un desplazamiento angular específico, cambiando la inclinación de $\psi$ en la base a $\phi$ en la parte superior, donde la diferencia $\phi - \psi \approx \theta$.
   • Algoritmo 2: Diseñado para "deshacer" el desplazamiento angular introducido por el Algoritmo 1. Comienza donde termina el Algoritmo 1, empaquetando pilas de longitud $m+1$ y $m$ para restaurar la geometría requerida para reiniciar el Algoritmo 1.
   • Aplicación Iterativa: Estos dos algoritmos se aplican consecutivamente en un ciclo. El artículo demuestra que los parámetros ($\phi, \psi, \theta, m$) pueden fijarse o ajustarse de tal manera que los términos de error ($\epsilon, \epsilon'$) no se acumulen de forma destructiva durante las iteraciones.
4. Optimización de Parámetros: El ancho $w$ del trapezoide $T$ y el número de iteraciones se optimizan. El algoritmo se aplica aproximadamente $\sqrt{h}$ veces para cubrir el trapezoide.

Resultos Clave y Análisis
El artículo deriva el espacio desperdiciado total $W(x)$ sumando el desperdicio de las pilas verticales y el desperdicio generado dentro de las regiones trapezoidales:

• Desperdicio de las Pilas: El empaquetamiento de las $O(x)$ pilas verticales con inclinación $\theta$ genera un desperdicio proporcional a $O(x\theta)$.
• Desperdicio de los Trapecios: La aplicación iterativa de los dos algoritmos de empaquetamiento en el trapezoide $T$ genera un desperdicio total de $O(h^{3/4})$.
• Optimización: El desperdicio total está acotado por $W(x) \ll \frac{x}{\sqrt{h}} + h^{3/4}$. Al igualar los dos términos ($x h^{-1/2} \sim h^{3/4}$), la elección óptima es $h \sim x^{4/5}$.

Sustituyendo $h = x^{4/5}$ en el límite se obtiene:
$$W(x) = O(x^{3/5})$$

Significancia y Reivindicaciones
El artículo afirma demostrar rigurosamente que el espacio desperdiciado al empaquetar un cuadrado grande con cuadrados unitarios está acotado por $O(x^{3/5})$. Este resultado valida la afirmación realizada previamente por Chung y Graham en 2020, la cual había sido retractada debido a un error. La significancia radica en proporcionar una prueba corregida para este límite asintótico específico, mejorando el mejor límite conocido anteriormente de $O(x^{(3+\sqrt{2})/7} \log x)$. Los autores enfatizan que esto se logra mediante un algoritmo constructivo específico que involucra la interacción de dos estrategias de empaquetamiento que gestionan las discrepancias angulares y la acumulación de errores dentro de las subregiones trapezoidales. El artículo no propone aplicaciones futuras ni implicaciones más allá de establecer este límite superior específico.