Optimally Packing a Large Square by Unit Squares

Sintesi Tecnica: Impacchettamento Ottimale di un Grande Quadrato con Quadrati Unitari

Enunciato del Problema
Il documento affronta il problema di impacchettare un grande quadrato $S(x)$ di lato $x$ con quadrati unitari aventi interni disgiunti. L'obiettivo è minimizzare lo spazio sprecato $W(x)$, definito come l'area di $S(x)$ non coperta dai quadrati unitari. Sebbene $W(x) = 0$ quando $x$ è un intero, il problema diventa non banale quando $x$ non è un intero. Un impacchettamento ingenuo di quadrati unitari paralleli ai lati di $S(x)$ produce uno spazio sprecato di $W(x) = O(x\{x\})$, che si semplifica in $O(x)$ se la parte frazionaria $\{x\}$ è lontana dallo zero. La sfida centrale consiste nel determinare il tasso di crescita asintotica ottimale di $W(x)$ consentendo ai quadrati unitari di essere orientati con lievi angolazioni.

Contesto Storico e Limiti Precedenti
Il documento colloca il proprio contributo all'interno di una cronologia di limiti stabiliti:

• Limite Inferiore: Roth e Vaughan (1978) hanno dimostrato che $W(x) > 10^{-100}\sqrt{x - \lfloor x \rfloor}$, stabilendo che il limite non può essere migliore di $\Omega(x^{1/2})$.
• Limiti Superiori:
  • Erdős e Graham (1975) hanno mostrato che $W(x) = O(x^{7/11})$.
  • Montgomery ha migliorato questo risultato a $O(x^{(3-\sqrt{3})/2})$.
  • Chung e Graham (2009) hanno ulteriormente raffinato il limite a $O(x^{(3+\sqrt{2})/7} \log x)$.
  • Nel 2020, Chung e Graham avevano rivendicato un limite di $O(x^{3/5})$, ma il documento nota che tale risultato conteneva un errore, riportando il miglior limite noto a quello del 2009 fino al presente lavoro.

Metodologia
Il documento propone un nuovo algoritmo per raggiungere il limite $O(x^{3/5})$, correggendo l'errore nella rivendicazione del 2020. La dimostrazione procede attraverso quattro fasi distinte:

1. Impacchettamento Trivialità Iniziale: Il quadrato $S(x)$ viene prima impacchettato trivialmente con quadrati unitari allineati parallelamente ai lati, lasciando due strette regioni rettangolari di larghezza $h$. Un tale rettangolo, $R$, viene selezionato per un'ulteriore elaborazione.
2. Impacchettamento con Inclinazione: Il rettangolo $R$ viene impacchettato utilizzando "pile" di $n$ quadrati unitari inclinate di un angolo $\theta$. Queste pile toccano sia le pareti verticali che quelle inclinate del rettangolo. Questo processo lascia dietro di sé una regione trapezoidale $T$ alle estremità. L'angolo $\theta$ è scelto in modo tale che $\theta \asymp h^{-1/2}$.
3. Impacchettamento Trapezoidale a Due Stadi: Il cuore dell'algoritmo consiste nel riempire il trapezio $T$ utilizzando due sub-algoritmi complementari:
   • Algoritmo 1: Impacchetta $T$ utilizzando pile quasi orizzontali e verticali di lunghezza decrescente ($m, m-1, \dots$). Questo algoritmo introduce uno specifico scostamento angolare, cambiando l'inclinazione da $\psi$ alla base a $\phi$ alla sommità, dove la differenza $\phi - \psi \approx \theta$.
   • Algoritmo 2: Progettato per "annullare" lo scostamento angolare introdotto dall'Algoritmo 1. Esso inizia dove l'Algoritmo 1 termina, impacchettando pile di lunghezza $m+1$ e $m$ per ripristinare la geometria necessaria a riavviare l'Algoritmo 1.
   • Applicazione Iterativa: Questi due algoritmi vengono applicati consecutivamente in un ciclo. Il documento dimostra che i parametri ($\phi, \psi, \theta, m$) possono essere fissati o regolati in modo che i termini di errore ($\epsilon, \epsilon'$) non si accumulino in modo distruttivo durante le iterazioni.
4. Ottimizzazione dei Parametri: La larghezza $w$ del trapezio $T$ e il numero di iterazioni sono ottimizzati. L'algoritmo viene applicato circa $\approx \sqrt{h}$ volte per coprire il trapezio.

Risultati Chiave e Analisi
Il documento deriva lo spazio totale sprecato $W(x)$ sommando lo spreco delle pile verticali e lo spreco generato all'interno delle regioni trapezoidali:

• Spreco dalle Pile: L'impacchettamento delle $O(x)$ pile verticali con inclinazione $\theta$ genera uno spreco proporzionale a $O(x\theta)$.
• Spreco dai Trapezoidi: L'applicazione iterativa dei due algoritmi di impacchettamento sul trapezio $T$ genera uno spreco totale di $O(h^{3/4})$.
• Ottimizzazione: Lo spreco totale è limitato da $W(x) \ll \frac{x}{\sqrt{h}} + h^{3/4}$. Uguagliando i due termini ($x h^{-1/2} \sim h^{3/4}$), la scelta ottimale è $h \sim x^{4/5}$.

Sostituendo $h = x^{4/5}$ nel limite si ottiene:
$$W(x) = O(x^{3/5})$$

Significato e Rivendicazioni
Il documento sostiene di dimostrare rigorosamente che lo spazio sprecato nell'impacchettamento di un grande quadrato con quadrati unitari è limitato da $O(x^{3/5})$. Questo risultato valida la rivendicazione precedentemente fatta da Chung e Graham nel 2020, che era stata ritirata a causa di un errore. La significatività risiede nel fornire una prova corretta per questo specifico limite asintotico, migliorando il precedente miglior limite noto di $O(x^{(3+\sqrt{2})/7} \log x)$. Gli autori sottolineano che ciò è ottenuto attraverso un algoritmo costruttivo specifico che coinvolge l'interazione di due strategie di impacchettamento che gestiscono le discrepanze angolari e l'accumulo di errori all'interno di sub-regioni trapezoidali. Il documento non propone ulteriori applicazioni o implicazioni future oltre all'instaurazione di questo specifico limite superiore.