Optimally Packing a Large Square by Unit Squares

तकनीकी सारांश: एक बड़े वर्ग को इकाई वर्गों द्वारा इष्टतम रूप से भरना

समस्या विवरण
यह शोध पत्र एक बड़े वर्ग $S(x)$ को भरने की समस्या को संबोधित करता है, जिसकी भुजा की लंबाई $x$ है, जिसमें इकाई वर्गों (unit squares) को उनके आंतरिक भाग विलग (disjoint) रखते हुए भरा जाना है। इसका उद्देश्य व्यर्थ स्थान $W(x)$ को कम करना है, जिसे $S(x)$ का वह क्षेत्रफल परिभाषित किया गया है जो इकाई वर्गों द्वारा कवर नहीं किया गया है। जबकि जब $x$ एक पूर्णांक होता है तो $W(x) = 0$ होता है, यह समस्या तब गैर-तुच्छ (non-trivial) हो जाती है जब $x$ एक पूर्णांक नहीं होता है। $S(x)$ के किनारों के समानांतर इकाई वर्गों का एक सरल संरेखण (naive alignment) $W(x) = O(x\{x\})$ के बराबर व्यर्थ स्थान देता है, जो सरल होकर $O(x)$ हो जाता है यदि भिन्नात्मक भाग $\{x\}$ शून्य से दूर (bounded away from zero) हो। मुख्य चुनौती यह निर्धारित करना है कि इकाई वर्गों को थोड़े कोण पर झुकाकर उन्मुख (orient) करने की अनुमति देने से $W(x)$ की इष्टतम स्पर्शोन्मुखी वृद्धि दर (asymptotic growth rate) क्या होगी।

ऐतिहासिक संदर्भ और पूर्व सीमाएँ (Prior Bounds)
यह शोध पत्र अपने योगदान को स्थापित सीमाओं की एक समयरेखा के भीतर रखता है:

• निम्न सीमा (Lower Bound): रोथ और वॉनन (1978) ने सिद्ध किया कि $W(x) > 10^{-100}\sqrt{x - \lfloor x \rfloor}$, जिससे यह स्थापित हुआ कि यह सीमा $\Omega(x^{1/2})$ से बेहतर नहीं हो सकती है।
• उच्च सीमाएँ (Upper Bounds):
  • एर्डोस और ग्राहम (1975) ने दिखाया कि $W(x) = O(x^{7/11})$ है।
  • मोंटगोमरी ने इसे सुधारकर $O(x^{(3-\sqrt{3})/2})$ कर दिया।
  • चुंग और ग्राहम (2009) ने इसे और परिष्कृत करते हुए $O(x^{(3+\sqrt{2})/7} \log x)$ तक पहुँचाया।
  • 2020 में, चुंग और ग्राहम ने $O(x^{3/5})$ की सीमा का दावा किया, लेकिन शोध पत्र नोट करता है कि इस परिणाम में एक त्रुटि थी, जिससे वर्तमान कार्य तक सर्वोत्तम ज्ञात सीमा 2009 के परिणाम पर वापस आ गई।

कार्यप्रणाली (Methodology)
शोध पत्र $O(x^{3/5})$ की सीमा प्राप्त करने के लिए एक नया एल्गोरिदम प्रस्तावित करता है, जो 2020 के दावे में त्रुटि को सुधारता है। प्रमाण चार विशिष्ट चरणों में आगे बढ़ता है:

1. प्रारंभिक तुच्छ पैकिंग (Initial Trivial Packing): वर्ग $S(x)$ को पहले $S(x)$ के किनारों के समानांतर संरेखित इकाई वर्गों के साथ तुच्छ रूप से भरा जाता है, जिससे चौड़ाई $h$ के दो संकीर्ण आयताकार क्षेत्र शेष रह जाते हैं। आगे की प्रक्रिया के लिए एक ऐसा आयत $R$ चुना जाता है।
2. झुकाव के साथ स्टैकिंग (Stacking with Inclination): आयत $R$ को एक कोण $\theta$ पर झुके हुए $n$ इकाई वर्गों के "स्टैक्स" (stacks) का उपयोग करके भरा जाता है। ये स्टैक आयत की ऊर्ध्वाधर और झुकी हुई दोनों दीवारों को छूते हैं। यह प्रक्रिया सिरों पर एक समलंब क्षेत्र (trapezoidal region) $T$ छोड़ देती है। कोण $\theta$ का चयन इस प्रकार किया जाता है कि $\theta \asymp h^{-1/2}$ हो।
3. दो-चरणीय समलंब पैकिंग (Two-Stage Trapezoidal Packing): एल्गोरिदम का मुख्य भाग $T$ को दो पूरक उप-एल्गोरिदम का उपयोग करके भरने में निहित है:
   • एल्गोरिदम 1: $T$ को घटते आकार के ($m, m-1, \dots$) लगभग क्षैतिज और ऊर्ध्वाधर स्टैक्स का उपयोग करके भरता है। यह एक विशिष्ट कोणीय बदलाव (angular shift) पेश करता है, जो नीचे $\psi$ से ऊपर $\phi$ तक झुकाव को बदल देता है, जहाँ अंतर $\phi - \psi \approx \theta$ है।
   • एल्गोरिदम 2: एल्गोरिदम 1 द्वारा पेश किए गए कोणीय बदलाव को "पूर्ववत" (undo) करने के लिए डिज़ाइन किया गया है। यह एल्गोरिदम 1 के अंत से शुरू होता है, $m+1$ और $m$ लंबाई के स्टैक्स को भरकर एल्गोरिदम 1 को पुनः आरंभ करने के लिए आवश्यक ज्यामिति को बहाल करता है।
   • पुनरावृत्ति अनुप्रयोग (Iterative Application): इन दोनों एल्गोरिदम को एक चक्र में बारी-बारी से लागू किया जाता है। शोध पत्र प्रदर्शित करता है कि मापदंडों ($\phi, \psi, \theta, m$) को इस तरह से स्थिर या समायोजित किया जा सकता है कि त्रुटि पद ($\epsilon, \epsilon'$) पुनरावृत्तियों पर विनाशकारी रूप से संचित न हों।
4. मापदंड अनुकूलन (Parameter Optimization): समलंब $T$ की चौड़ाई $w$ और पुनरावृत्तियों की संख्या को अनुकूलित किया जाता है। समलंब को कवर करने के लिए एल्गोरिदम को $\approx \sqrt{h}$ बार लागू किया जाता है।

मुख्य परिणाम और विश्लेषण
शोध पत्र ऊर्ध्वाधर स्टैक्स से होने वाली बर्बादी और समलंब क्षेत्रों के भीतर उत्पन्न बर्बादी को जोड़कर कुल व्यर्थ स्थान $W(x)$ का व्युत्पन्न करता है:

• स्टैक्स से व्यर्थ स्थान: झुकाव $\theta$ के साथ $O(x)$ ऊर्ध्धर स्टैक्स को भरने से $O(x\theta)$ के अनुपात में व्यर्थ स्थान उत्पन्न होता है।
• समलंबों से व्यर्थ स्थान: समलंब $T$ पर दो पैकिंग एल्गोरिदम के पुनरावृत्ति अनुप्रयोग से $O(h^{3/4})$ की कुल बर्बादी होती है।
• अनुकूलन: कुल व्यर्थ स्थान $W(x) \ll \frac{x}{\sqrt{h}} + h^{3/4}$ द्वारा सीमित है। दोनों पदों को समान करके ($x h^{-1/2} \sim h^{3/4}$), इष्टतम विकल्प $h \sim x^{4//5}$ प्राप्त होता है।

$h = x^{4/5}$ को सीमा में प्रतिस्थापित करने पर प्राप्त होता है:
$$W(x) = O(x^{3/5})$$

महत्व और दावे
शोध पत्र दावा करता है कि वह कठोरता से सिद्ध करता है कि इकाई वर्गों द्वारा एक बड़े वर्ग को भरने में व्यर्थ स्थान $O(x^{3/5})$ द्वारा सीमित है। यह परिणाम चुंग और ग्राहम द्वारा 2020 में किए गए दावे को मान्य करता है, जिसमें एक त्रुटि के कारण सुधार किया गया था। इसका महत्व इस विशिष्ट स्पर्शोन्मुखी सीमा के लिए एक सुधारात्मक प्रमाण प्रदान करने में निहित है, जो $O(x^{(3+\sqrt{2})/7} \log x)$ के पिछले सर्वोत्तम ज्ञात सीमा में सुधार करता है। लेखक इस बात पर जोर देते हैं कि यह एक विशिष्ट रचनात्मक एल्गोरिदम के माध्यम से प्राप्त किया गया है जिसमें कोणीय विसंगतियों और त्रुटि संचय को प्रबंधित करने वाले दो पैकिंग रणनीतियों का परस्पर प्रभाव शामिल है। यह शोध पत्र इस विशिष्ट ऊपरी सीमा को स्थापित करने के अलावा किसी अन्य अनुप्रयोग या भविष्य के निहितार्थों का प्रस्ताव नहीं करता है।