สถิติใหม่ของการจัดเรียงทรงกลมที่มาจากแหล่งที่ไม่คาดคิด

• Boaz Klartag ได้นำเครื่องมือจาก เรขาคณิตนูน เข้ามาใช้กับปัญหาการจัดเรียงทรงกลมในมิติสูงมาก ซึ่งแตกต่างจากแนวทางเดิม
• วิธีการเชิงสุ่มแบบใหม่ของ Klartag สร้าง ทรงรีที่มีปริมาตรมากกว่าเดิม และทำลายสถิติเดิมลงอย่างมาก
• แนวทางนี้ทำให้สามารถจัดเรียง ทรงกลมได้มากขึ้นอย่างมหาศาลในปริภูมิมิติสูง
• ผลลัพธ์ครั้งนี้ปลุกการถกเถียงเรื่องความสำคัญของ ความเป็นระเบียบและสมมาตร ในการจัดเรียงกลับมาอีกครั้ง
• งานวิจัยนี้ได้รับความสนใจจากความเป็นไปได้ในการประยุกต์ใช้ที่หลากหลาย เช่น ด้านคริปโตกราฟีและการสื่อสาร

---

งานวิจัยการจัดเรียงทรงกลมก่อนหน้าและข้อจำกัด

• ในอดีต ข้อดีของวิธีของ Rogers คือ จุดเริ่มต้นของแลตทิซไม่จำเป็นต้องมีประสิทธิภาพมาก ขอเพียงเลือก ทรงรีที่เหมาะสม เท่านั้น
• แต่เนื่องจาก แกนของทรงรี สามารถบิดเปลี่ยนได้หลากหลายในมิติสูง จึงมีตัวเลือกมากเกินไปว่าจะขยายให้มีรูปทรงแบบใด
• หลังจากนั้น นักคณิตศาสตร์จึงหันกลับไปใช้ แนวทางของ Minkowski และโฟกัสที่ตัวแลตทิซเอง เชี่ยวชาญด้านทฤษฎีแลตทิซมากขึ้น และค่อย ๆ ห่างจากแนวทางเรขาคณิตของ Rogers
• กลยุทธ์นี้แสดงการปรับปรุงแบบค่อยเป็นค่อยไปในการจัดเรียงทรงกลมมิติสูง แต่เมื่อเทียบกับวิธีของ Rogers แล้วให้ ประสิทธิภาพที่ดีขึ้นเพียงเล็กน้อย
• ตลอดหลายทศวรรษที่ผ่านมาไม่เกิด การก้าวกระโดดครั้งใหญ่ และภาวะชะงักงันก็ยังดำเนินต่อไป

นวัตกรรมที่เริ่มต้นจากมุมมองคนนอก

• Boaz Klartag จาก Weizmann Institute of Science เดิมทีเป็นนักวิจัยด้าน เรขาคณิตนูน ไม่ใช่ทฤษฎีแลตทิซ
• เขาสนใจปัญหาการจัดเรียงทรงกลมมานาน แต่ไม่เคยมีโอกาสได้ทำวิจัยอย่างจริงจัง
• ในปี 2023 เมื่อมีเวลาใหม่ขึ้นมา เขาจึงเปิดสัมมนาร่วมกับ Barak Weiss แห่ง Tel Aviv University เพื่อศึกษา วรรณกรรมคลาสสิก (Minkowski, Rogers) อย่างเข้มข้น
• Klartag มองว่าวิธีทรงรีของ Rogers ไม่มีประสิทธิภาพเพราะขาดความชำนาญในการ จัดการรูปทรงนูน
• เขามั่นใจว่าหากสร้าง ทรงรีที่มีประสิทธิภาพกว่าเดิม ได้ ก็จะสามารถเขียนสถิติใหม่ของการจัดเรียงทรงกลมได้

การนำอัลกอริทึมการขยายแบบสุ่มมาใช้

• Klartag ใช้วิธีของตนเอง โดย ขยาย/หดขอบเขตของทรงรีแบบสุ่ม แยกตามทิศทางของแต่ละแกน
• เมื่อขอบเขตแตะจุดแลตทิซในทิศทางใด ก็หยุดการเติบโตในทิศทางนั้น แต่ยังคงขยายต่อในทิศทางอื่น
• ระหว่างกระบวนการนี้ ทรงรีจะสำรวจปริภูมิไปพร้อมกับค่อย ๆ ขยายตัวในรูปร่างที่ไม่สม่ำเสมอ
• เนื่องจากลักษณะเชิงสุ่มทำให้ทรงรีที่สร้างขึ้นแต่ละอันมีปริมาตรต่างกัน เขาจึง ทดลองหลายครั้ง เพื่อประเมินความเป็นไปได้ของทรงรีที่มีปริมาตรมากกว่าเดิม
• ภายในเวลาไม่กี่สัปดาห์ เขาก็พิสูจน์ได้ว่าสามารถได้ ทรงรีที่ใหญ่กว่าวิธีของ Rogers เดิม

การทำลายสถิติและผลกระทบ

• วิธีทรงรีแบบใหม่นี้ทำให้เกิด การปรับปรุงประสิทธิภาพการจัดเรียงทรงกลมครั้งใหญ่ที่สุด นับตั้งแต่ Rogers ในปี 1947
• เมื่อมิติเท่ากับ d จะสามารถจัดเรียงทรงกลมได้ มากกว่าวิธีก่อนหน้าถึง d เท่า
  • 100 มิติ → ราว 100 เท่า, 1,000,000 มิติ → ราว 1,000,000 เท่า
• Klartag ใช้ความเข้าใจจากเรขาคณิตนูนเพื่อฝ่าทะลุปัญหาแกนกลางเก่าแก่ของ แลตทิซและการจัดเรียงทรงกลม ได้ภายในเวลาไม่กี่เดือน
• ความสำเร็จของเขาทำให้แนวคิดที่ว่า การจัดเรียงที่อาศัย ความเป็นระเบียบและสมมาตร อาจทำให้ได้ความหนาแน่นสูงสุดกลับมาโดดเด่นอีกครั้ง
• ขณะเดียวกัน ในช่วงหลังมานี้ก็มีงานวิจัยอีกสายที่แข่งขันกัน โดยมองว่าต้องอาศัยความไร้ระเบียบแทนการใช้แลตทิซที่เป็นระเบียบ

การประเมินและแนวโน้มในอนาคต

• ขณะนี้ในแวดวงวิชาการยังมี ข้อถกเถียง ว่าวิธีการจัดเรียงของ Klartag เข้าใกล้คำตอบที่เหมาะที่สุดจริงหรือไม่ และยังมีพื้นที่ให้ปรับปรุงเพิ่มเติมอีกแค่ไหน
• คำตอบของปัญหานี้มีความสำคัญมากต่อ การประยุกต์ใช้จริง เช่น คริปโตกราฟีและวิศวกรรมการสื่อสาร
• แม้จะยังไม่ถึงขั้นนำไปใช้ในทางปฏิบัติทันที แต่ก็ได้รับ ความสนใจในฐานะเทคโนโลยีใหม่ จากแวดวงวิศวกรรมและสาขาอื่น ๆ
• Klartag หวังว่าโอกาสนี้จะช่วยกระชับ ความเชื่อมโยงระหว่างเรขาคณิตนูนกับทฤษฎีแลตทิซ ให้แน่นแฟ้นขึ้น
• เขาหวังว่าจะก้าวข้ามความแยกขาดระหว่างสองสาขา และขยายการบูรณาการนี้ไปสู่การแก้ ปัญหาแลตทิซอื่น ๆ นอกเหนือจากการจัดเรียง

[GN⁺]

ความเห็นจาก Hacker News

• มีคนสารภาพว่าการอธิบายให้พ่อแม่เข้าใจว่างานของตัวเองเป็นอาชีพที่มีอยู่จริงนั้นยากเสมอ และยิ่งนึกภาพสถานการณ์ที่ต้องพูดว่า “ฉันศึกษารูปทรง แต่ศึกษาพวกที่ไม่มีส่วนเว้าเข้าไป” ก็ยิ่งชวนอึดอัด
  • จากประสบการณ์ของฉัน สรุปได้ว่าการใช่คำศัพท์เฉพาะยาก ๆ เพื่ออธิบายงานเป็นทางออกที่ดีที่สุด โดยมีตัวเลือกอยู่สามแบบ ถ้าอธิบายง่ายพอให้พ่อแม่เข้าใจ งานจะดูง่ายเกินไปจนได้คำตอบว่า “แล้วแบบนี้ได้เงินด้วยเหรอ?” ถ้าอธิบายอย่างถูกต้องว่าทำไมมันสำคัญ คำอธิบายก็จะยาวเกินจนพ่อแม่เริ่มเบื่อและเสียดายที่ถาม แต่ถ้าพูดสั้น ๆ ด้วยศัพท์เทคนิคซับซ้อน แม้จะฟังไม่รู้เรื่องแต่กลับดูยิ่งใหญ่ขึ้นมาเฉย ๆ ซึ่งดูจะเป็นทางเลือกที่ดีที่สุด
  • ฉันทำไมโครบิสิเนสผลิตชิ้นส่วนสำหรับอุปกรณ์ฟิสิกส์พลังงานสูง แต่เวลาจะอธิบายงานให้คนอื่นฟัง มันเป็นเรื่องเฉพาะทางสุดโต่ง แปลกแยกจากชีวิตประจำวันหลายชั้น และคนทั่วไปไม่เคยเจอเลย จนถึงตอนนี้ก็ยังหาวิธีทำให้เข้าใจไม่ได้
  • ฉันมักพูดแค่ว่า "ทำงานกับคอมพิวเตอร์" แล้วก็มักจะได้คำตอบประมาณ “อ้อ ดีเลย งานดีนี่” แล้วบทสนทนาก็จบลงอย่างสะดวก
  • สำหรับฉัน สิ่งที่ยากเสมอไม่ใช่คำถามว่า “ทำงานอะไร” แต่เป็นคำถามต่อมาว่า “มันมีประโยชน์ยังไง/เอาไปใช้ที่ไหน?” การอธิบายสายโซ่อันยาวของการที่งานวิจัยพื้นฐานนำไปสู่การใช้งานจริงให้สั้นและมีประสิทธิภาพนั้นเป็นเรื่องชวนปวดหัว
  • อย่างน้อยที่สุด sphere packing ก็เกี่ยวข้องอย่างใกล้ชิดกับปัญหาแกนกลางของทฤษฎีสารสนเทศ และเชื่อมโยงไปถึงการทำให้ระบบ Bell Telephone มีความน่าเชื่อถือมากขึ้น จึงพอเห็นบริบททางประวัติศาสตร์และความสำคัญได้ (แต่เรื่องรูปทรงนูนไม่ค่อยแน่ใจ)
• มีคนเล่าประสบการณ์ว่าเคยลองคิดอัลกอริทึมบีบอัดข้อมูลเวกเตอร์โดยใช้วิธีจัดเรียงทรงกลมให้แน่น (sphere packing) แต่แนวทางเชิงทฤษฎีนี้ใช้ได้ผลก็ต่อเมื่อข้อมูลมีความสม่ำเสมอมากเท่านั้น และยากจะนำไปใช้กับข้อมูลจริง
  • ถ้าจะทำให้ข้อมูลที่ไม่เป็นระเบียบ (ไม่สม่ำเสมอ) กลายเป็นสม่ำเสมอ เทคนิคที่ใช้กันทั่วไปคืออาศัยความรู้เฉพาะโดเมนเพื่อลดความไม่สมมาตร ตัวอย่างเช่น แม้ข้อมูลจะมีโครงสร้างมิติสูง แต่ในระดับเฉพาะที่ก็มักสม่ำเสมอได้พอสมควรเพราะมี noise อยู่ จึงคำนวณและเก็บ centroid ไว้ ซึ่งตัว centroid จะสม่ำเสมอมากขึ้น แล้วแยกเก็บแต่ละเวกเตอร์เป็นดัชนีของ centroid และเวกเตอร์ออฟเซ็ต ดัชนีเหมาะกับการบีบอัดแบบเอนโทรปีอย่างมีประสิทธิภาพ ส่วนออฟเซ็ตตอนนี้เกือบสม่ำเสมอแล้ว จึงเอากลยุทธ์ sphere packing เดิมมาใช้ได้ง่ายขึ้น
  • น่าจะมีคนลองไปแล้ว แต่ก็อาจดูได้ว่าการ precompression เพื่อลดความ sparse ของเวกเตอร์จะช่วยเพิ่มความสม่ำเสมอได้หรือไม่
  • มีการแซวเล่นว่าต้องระวังเวลาไป grop(e) กับเวกเตอร์จริง ๆ (grope แปลว่า “คลำ” และเป็นการพิมพ์ผิดจาก group)
  • มีการชี้ว่าควรขยายขอบเขตของทฤษฎีให้ครอบคลุมโจทย์เชิงปฏิบัติมากขึ้นด้วย (ก็คือข้อมูลที่ไม่เป็นเนื้อเดียวกัน) แม้ว่าถ้าการใช้งานจริงมีหลากหลายเกินไป แนวทางทั่วไปอาจใช้ยาก แต่ก็ยังควรให้ความสำคัญกับการต่อยอดงานวิจัยไปทางนี้
  • มีคนตั้งข้อสังเกตว่าในสาขาเก่าแก่ที่มีความสำคัญทางการค้ามานาน ผลลัพธ์ที่หยิบเก็บได้ง่าย ๆ ส่วนใหญ่ก็มักถูกเก็บไปเกือบหมดแล้ว
• มีคนเห็นด้วยกับคำกล่าวของ Klartag ที่ว่า “รูปทรงนูนทรงพลังมากและมีคุณค่าในการใช้งานสูง” โดยเล่าว่าถึงจะไม่ใช่นักคณิตศาสตร์ แต่ก็มักเห็นอัลกอริทึม Convex Hull โผล่มาในปัญหาที่คาดไม่ถึงอยู่เสมอ โดยเฉพาะงานอย่างการแยกพาเลตต์สีจากภาพแบบอัตโนมัติ พร้อมแนบลิงก์บทความอ้างอิง Convex Hull and automatic palette decomposition
• มีคนสงสัยว่าถ้าวิธี sphere packing แบบใหม่ของ Klartag ทำให้บรรจุทรงกลมได้มากขึ้น d เท่าเมื่อมิติเป็น d นั่นก็หมายความว่าใน 100 มิติคือเพิ่ม 100 เท่า และในหนึ่งล้านมิติคือเพิ่มหนึ่งล้านเท่า ซึ่งเป็นตัวเลขมหาศาล จึงอยากรู้ว่าในระบบสื่อสารต่าง ๆ มันจะแปลว่าต้องใช้แบนด์วิดท์น้อยลงหลายสิบถึงหลายร้อยเท่า หรือใช้พลังงานน้อยลงมากจริงหรือไม่
  • ในความเป็นจริง เมื่อมิติสูงขึ้น ความหนาแน่น (density) จะยิ่งแย่ลงแบบเอ็กซ์โปเนนเชียลเป็น n^2/2^n ดังนั้นการปรับปรุงเชิงเส้นในทางทฤษฎีจึงไม่ได้สะท้อนมาเป็นประสิทธิภาพจริงทั้งหมด กล่าวคือมันมีประโยชน์กับข้อมูลที่มีโครงสร้างมิติสูงโดยธรรมชาติ แต่กับข้อมูลดิจิทัล (ที่เลือกได้แค่ความยาว) เราสามารถเลือกมิติเล็กได้ ดูรายละเอียด sphere packing เพิ่มเติมได้ที่ wikipedia link
• มีคนคิดว่านักคณิตศาสตร์ควรสามารถทำปริญญาเอกใบที่สองในสาขาใกล้เคียงแต่ไม่ใช่สาขาเดิมได้ หลังจากจบปริญญาเอกใบแรกไปแล้วไม่กี่ปี
  • จุดประสงค์พื้นฐานของปริญญาเอกคือการพิสูจน์ความสามารถในการทำวิจัยอย่างอิสระ ดังนั้นในทางปฏิบัติ นักวิจัยจำนวนมากก็ย้ายไปสาขาอื่นหรือเปลี่ยนหัวข้อที่สนใจหลังเรียนจบปริญญาเอกอยู่แล้ว และหลังจากนั้นสิ่งสำคัญก็คือตัว “การวิจัย” เอง
  • มีการยกตัวอย่างว่ากรณีแบบนี้เกิดขึ้นได้จริง โดยนักคณิตศาสตร์ชื่อดัง Bela Bollobas มีปริญญาเอกสองใบในสองสาขา คือเรขาคณิตเชิงจัดเรียงและฟังก์ชันนัลอะนาลิซิส แม้ว่าในแวดวงวิชาการยุคปัจจุบัน การลองทำแบบนี้อีกคงยากมากก็ตาม
  • ถ้ามีความยืดหยุ่นเชิงสถาบันแบบนี้ทั่วทั้งวงการวิทยาศาสตร์ ก็อาจช่วยให้เทคนิคและแนวคิดจากต่างสาขาแลกเปลี่ยนกันได้เร็วขึ้น และเร่งความก้าวหน้าทางวิทยาศาสตร์ได้ โดยเฉพาะในสาขาอย่างคณิตศาสตร์ที่ความเชื่อมโยงระหว่างแขนงต่าง ๆ สำคัญมาก
• มีคำถามแบบมือใหม่ว่า sphere packing ที่ดีที่สุดนั้นเกี่ยวข้องกับ lattice แบบสม่ำเสมอเสมอหรือไม่ เพราะใน 2D และ 3D ดูเหมือนจะเป็นเช่นนั้น จึงสงสัยว่ามันขยายไปถึง ND หรือเปล่า
  • นอกจาก 2 และ 3 มิติแล้ว ยังมีกรณีที่พิสูจน์ได้ว่า best packing อยู่ในรูป lattice แบบสม่ำเสมอใน 8 มิติ (แลตทิซ E₈) และ 24 มิติ (แลตทิซ Leech) ซึ่ง Maryna Viazovska และผู้ร่วมงานพิสูจน์ไว้ในปี 2017 พร้อมแนบลิงก์งานอ้างอิง บทความ 1, บทความ 2, ไฟล์อธิบาย PDF แต่ในมิติอื่น ๆ ก็อาจมีตัวอย่างโต้แย้งว่าการจัดเรียงที่ดีที่สุดไม่ใช่ lattice แบบสม่ำเสมอ และในบางมิติก็มีรูปแบบไม่เป็นระเบียบที่หนาแน่นกว่าได้
  • ไม่จำเป็นต้องเป็นแบบนั้นเสมอไป แม้แต่ใน 3 มิติ นอกจากการเรียงแบบ lattice แล้ว ก็ยังมีการเรียงแบบ non-lattice ได้อีกนับไม่ถ้วนโดยเลื่อนแนวนอนของแต่ละชั้นต่างกันไป ซึ่งยังคงให้ความหนาแน่นเท่ากับ FCC lattice อยู่ และในมิติสูงก็มีข้อคาดเดาว่าการจัดเรียงที่ดีที่สุดอาจเป็น non-lattice เสมอ เพราะขาดสมมาตรที่เพียงพอ
• มีคนสงสัยว่ารูปแบบ sphere packing ใหม่นี้จะเริ่มเหนือกว่าวิธีเดิมที่มีการพิสูจน์ความหนาแน่นสูงสุดไว้แล้วตั้งแต่มิติขั้นต่ำเท่าไร
• มีการเสนอทิศทางต่อยอดว่างานวิจัยนี้จะนำไปใช้พัฒนาระบบสื่อสารที่ปลอดภัยขึ้น เชื่อถือได้มากขึ้น และประหยัดพลังงานมากขึ้นจริงในด้านวิทยาการเข้ารหัสและการสื่อสารได้หรือไม่ ซึ่งเป็นสาขาวิจัยที่น่าสนใจมาก
• มีการเปรียบเทียบแบบขำ ๆ ถึง ‘Cow Packing’ ในฟิสิกส์จริง (เช่น การศึกษาว่าจะจัดวัวให้มีความหนาแน่นเหมาะสมที่สุดในทางทฤษฎี) ว่าอาจมีการประยุกต์ใช้ได้จริง
• sphere packing เป็นหัวข้อที่น่าสนใจเพราะไปโผล่ในปัญหาของงานประยุกต์ได้หลากหลายมาก และชวนให้อยากอ่านงานวิจัยฉบับเต็มอย่างละเอียด