Kỷ lục mới về xếp cầu đến từ một nguồn không ngờ tới

• Boaz Klartag đã đưa các công cụ của hình học lồi vào bài toán xếp cầu siêu cao chiều, khác với các cách tiếp cận trước đây
• Phương pháp ngẫu nhiên mới của Klartag tạo ra các ellipsoid có thể tích lớn hơn, qua đó cập nhật mạnh mẽ kỷ lục trước đó
• Cách tiếp cận này cho phép xếp nhiều quả cầu hơn một cách đáng kể trong không gian cao chiều
• Kết quả lần này làm sống lại cuộc tranh luận về tầm quan trọng của trật tự và tính đối xứng trong xếp chồng
• Nghiên cứu thu hút sự chú ý nhờ khả năng ứng dụng đa dạng, như trong mật mã học và truyền thông

---

Nghiên cứu xếp cầu trước đây và các giới hạn

• Ưu điểm của phương pháp Rogers trước đây là lưới ban đầu không nhất thiết phải hiệu quả, chỉ cần chọn được một ellipsoid phù hợp
• Tuy nhiên, các trục của ellipsoid có thể biến dạng theo nhiều cách trong không gian cao chiều, nên có quá nhiều lựa chọn về cách làm nó lớn lên
• Sau đó, các nhà toán học quay trở lại cách tiếp cận Minkowski, tập trung vào chính lưới, chuyên sâu vào lý thuyết lưới và dần rời xa hướng hình học của Rogers
• Chiến lược này cho thấy những cải thiện dần dần trong xếp cầu cao chiều, nhưng chỉ mang lại mức tăng hiệu quả nhỏ so với phương pháp Rogers
• Trong nhiều thập kỷ, không có bước nhảy vọt lớn nào xuất hiện và tình trạng đình trệ vẫn tiếp diễn

Đột phá bắt đầu từ một góc nhìn bên ngoài

• Boaz Klartag của Weizmann Institute of Science vốn là nhà nghiên cứu hình học lồi, không phải chuyên gia lý thuyết lưới
• Ông đã quan tâm đến bài toán xếp cầu từ lâu nhưng chưa có cơ hội nghiên cứu
• Đến năm 2023, khi có thêm thời gian, ông mở một seminar cùng Barak Weiss của Tel Aviv University để đào sâu các tài liệu kinh điển (Minkowski, Rogers)
• Klartag cho rằng phương pháp ellipsoid của Rogers kém hiệu quả vì thiếu kinh nghiệm trong thao tác với các hình lồi
• Ông tin rằng nếu tạo ra được ellipsoid hiệu quả hơn, có thể viết lại kỷ lục xếp cầu

Đưa vào thuật toán tăng trưởng ngẫu nhiên

• Klartag áp dụng phương pháp riêng của mình, trong đó biên của ellipsoid được giãn ra hoặc co lại ngẫu nhiên theo từng hướng trục
• Khi biên chạm vào một điểm lưới, sự tăng trưởng theo hướng đó sẽ dừng lại, trong khi các hướng khác vẫn tiếp tục
• Trong quá trình này, ellipsoid thăm dò không gian với hình dạng bất quy tắc và dần lớn lên
• Vì tính ngẫu nhiên khiến mỗi ellipsoid tạo ra có thể tích khác nhau, ông thử nghiệm nhiều lần để đánh giá khả năng tìm được ellipsoid có thể tích lớn hơn
• Chỉ trong vài tuần, ông đã chứng minh có thể tạo ra ellipsoid lớn hơn phương pháp Rogers

Cập nhật kỷ lục và tác động

• Phương pháp ellipsoid mới đạt được mức cải thiện hiệu quả xếp cầu lớn nhất kể từ Rogers (1947)
• Khi số chiều là d, có thể xếp nhiều quả cầu hơn gấp d lần so với cách trước đây
  • 100 chiều → khoảng 100 lần, 1.000.000 chiều → khoảng 1 triệu lần số quả cầu
• Với những hiểu biết từ hình học lồi, Klartag đã tạo đột phá cho các bài toán trung tâm lâu đời về lưới và xếp cầu chỉ trong vài tháng
• Thành tựu của ông khiến quan điểm cho rằng cách xếp dựa trên trật tự và tính đối xứng có thể đạt mật độ cao nhất một lần nữa được chú ý
• Ở chiều ngược lại, gần đây cũng có các nghiên cứu cạnh tranh cho rằng cần tận dụng sự hỗn loạn thay vì lưới đều đặn

Đánh giá và triển vọng tương lai

• Hiện trong giới học thuật vẫn có tranh luận về việc cách xếp của Klartag có thực sự gần tối ưu hay vẫn còn dư địa cải thiện thêm
• Lời giải cho vấn đề này rất quan trọng cả trong ứng dụng thực tế như mật mã học và kỹ thuật truyền thông
• Dù chưa ở giai đoạn ứng dụng thực tiễn, kết quả này đang được giới kỹ thuật chú ý như một công nghệ mới
• Klartag hy vọng từ bước ngoặt này, mối liên hệ giữa hình học lồi và lý thuyết lưới sẽ được củng cố
• Ông mong việc vượt qua sự tách rời giữa hai lĩnh vực sẽ giúp sự kết hợp này mở rộng sang những bài toán lưới khác ngoài xếp cầu

[GN⁺]

Ý kiến Hacker News

• Lời thú nhận rằng việc giải thích cho bố mẹ hiểu công việc của mình là một nghề thực sự luôn rất khó; tưởng tượng tình huống còn khó xử hơn khi phải nói rằng “con nghiên cứu các hình dạng, nhưng chỉ nghiên cứu những hình không có phần lõm vào”
  • Theo kinh nghiệm của tôi, cách tốt nhất để giải thích nghề nghiệp là dùng thuật ngữ chuyên môn khó. Có thể rút gọn thành ba lựa chọn: nếu giải thích tương đối dễ hiểu để bố mẹ có thể nắm được, công việc sẽ trông quá đơn giản và họ sẽ phản ứng kiểu “thế mà cũng kiếm ra tiền à?”; nếu giải thích đúng vì sao nó quan trọng thì phần giải thích lại quá dài, khiến bố mẹ chán nản và hối hận vì đã hỏi; còn nếu nói ngắn gọn bằng thuật ngữ chuyên môn phức tạp thì tuy họ không hiểu gì, nhưng lại tạo hiệu ứng trông có vẻ ghê gớm, và đó là lựa chọn tốt nhất
  • Tôi điều hành một micro-business làm linh kiện cho thiết bị vật lý năng lượng cao, nhưng khi giải thích công việc của mình cho người khác, tôi vẫn chưa tìm ra cách nào để họ hiểu được, vì đây là một chủ đề cực kỳ xa lạ, mang tính ngách, công chúng hầu như chưa bao giờ tiếp xúc và lại cách đời sống thực nhiều tầng nấc
  • Tôi chỉ nói đơn giản là “làm việc với máy tính”, rồi nhận được phản ứng “à, vậy cũng ổn đấy” và cuộc trò chuyện kết thúc, rất tiện
  • Với tôi, điều khó khăn luôn không phải câu hỏi “bạn làm gì” mà là câu hỏi tiếp theo: “cái đó có ích thế nào/dùng vào đâu?”; làm sao giải thích ngắn gọn mà hiệu quả chuỗi liên kết dài từ nghiên cứu cơ bản đến ứng dụng thực tế luôn là một bài toán khó
  • Ít nhất thì sphere packing có liên hệ chặt chẽ với các bài toán cốt lõi của lý thuyết thông tin, và từ đó nối tới việc nâng cao độ tin cậy của Bell Telephone System, nên có thể tìm thấy bối cảnh lịch sử và ý nghĩa quan trọng ở đó (còn với hình lồi thì tôi không rõ)
• Chia sẻ trải nghiệm từng suy nghĩ về thuật toán nén dữ liệu vector bằng cách dùng sphere packing; cách tiếp cận lý thuyết này chỉ hiệu quả khi dữ liệu rất đồng đều và khó áp dụng cho dữ liệu thực tế
  • Để biến dữ liệu phi cấu trúc (không đồng đều) thành đồng đều hơn, mẹo thường dùng là tận dụng tri thức miền để giảm tính bất đối xứng. Ví dụ, ngay cả khi dữ liệu có cấu trúc nhiều chiều, ở mức cục bộ nó vẫn dễ trở nên khá đồng đều do nhiễu. Nếu tính và lưu các centroid, thì các centroid sẽ đồng đều hơn; sau đó tách mỗi vector thành chỉ mục centroid và vector offset để lưu trữ. Chỉ mục phù hợp với nén entropy hiệu quả, còn offset thì nay đã gần đồng đều nên dễ áp dụng chiến lược sphere packing hiện có
  • Có lẽ bạn đã thử rồi, nhưng có thể xem liệu precompression có làm giảm độ thưa của vector và tăng tính đồng đều hay không
  • Một lời đùa rằng khi thật sự động vào vector thì phải cẩn thận (grope là “sờ soạng”, do gõ nhầm group)
  • Cần mở rộng phạm vi của lý thuyết sang các bài toán thực tế hơn, tức là dữ liệu không đồng nhất; nếu các trường hợp ứng dụng ngoài đời quá đa dạng thì một cách tiếp cận chung có thể sẽ khó, nhưng dù vậy vẫn đáng chú ý vì nhu cầu mở rộng nghiên cứu
  • Chỉ ra rằng ở các lĩnh vực cũ nhưng quan trọng về mặt thương mại, phần lớn thành quả dễ đạt được nhất đã bị hái hết từ lâu
• Đồng ý với nhận định của Klartag rằng “hình lồi rất mạnh và có giá trị ứng dụng cao”; dù không phải nhà toán học, người bình luận cho biết mình thường xuyên thấy thuật toán Convex Hull xuất hiện ở những nơi không ngờ tới, đặc biệt trong các bài toán như tự động phân rã bảng màu của ảnh, và cung cấp bài báo tham khảo Convex Hull and automatic palette decomposition
• Klartag nói rằng cách sphere packing mới của ông có thể xếp được nhiều quả cầu hơn phương pháp cũ theo hệ số d nếu số chiều là d; vậy thì ở 100 chiều là gấp 100 lần, ở một triệu chiều là gấp một triệu lần, con số này thật khổng lồ, nên có người thắc mắc liệu điều đó có đồng nghĩa với việc trong nhiều hệ thống truyền thông thực tế, băng thông tăng lên hàng chục đến hàng trăm lần hoặc điện năng tiêu thụ giảm mạnh hay không
  • Trên thực tế, khi số chiều tăng thì mật độ giảm theo hàm mũ như n^2/2^n, nên mức cải thiện tuyến tính trên lý thuyết không chuyển nguyên vẹn thành hiệu năng thực tế. Nói cách khác, điều này hữu ích với dữ liệu vốn có cấu trúc nhiều chiều một cách tự nhiên, còn với dữ liệu số (nơi ta có thể chọn độ dài) thì có thể chọn số chiều nhỏ. Xem thêm về sphere packing tại wikipedia link
• Ý kiến cho rằng nhà toán học nên có thể lấy bằng tiến sĩ thứ hai ở một chuyên ngành lân cận, không phải đúng cùng lĩnh vực, vài năm sau bằng tiến sĩ đầu tiên
  • Mục đích cốt lõi của bằng tiến sĩ là chứng minh năng lực nghiên cứu độc lập, nên trên thực tế nhiều nhà nghiên cứu sau khi tốt nghiệp tiến sĩ sẽ chuyển sang lĩnh vực khác hoặc đổi chủ đề quan tâm; từ thời điểm đó, trọng tâm là “nghiên cứu” tự thân
  • Một ví dụ nổi tiếng cho thấy điều này là có thể: nhà toán học Bela Bollobas có hai bằng tiến sĩ, một ở hình học rời rạc và một ở giải tích hàm; tuy vậy trong học giới hiện đại, việc thử lại như vậy sẽ rất khó
  • Nếu sự linh hoạt thể chế như vậy tồn tại rộng khắp trong khoa học, các kỹ thuật và ý tưởng từ những lĩnh vực khác nhau có thể lưu chuyển nhanh hơn, qua đó đẩy nhanh tiến bộ khoa học; điều này đặc biệt hữu ích trong những lĩnh vực như toán học, nơi kết nối giữa các phân ngành rất quan trọng
• Câu hỏi của người mới học: liệu sphere packing tối ưu có luôn gắn với lưới đều hay không; trong 2D và 3D thì có vẻ đúng, nhưng không rõ điều đó có mở rộng lên ND không
  • Ngoài 2 và 3 chiều, còn có các trường hợp đã được chứng minh best packing có dạng lattice đều ở 8 chiều (lattice E₈) và 24 chiều (lattice Leech). Điều này được Maryna Viazovska và cộng sự chứng minh vào năm 2017; người bình luận cung cấp các liên kết tài liệu liên quan bài báo 1, bài báo 2, bài giải thích pdf. Tuy nhiên, ở các chiều khác có thể tồn tại phản ví dụ nơi packing tối ưu không phải lattice đều, và ở một số chiều các cấu trúc bất quy tắc thậm chí còn đặc hơn
  • Không hẳn luôn như vậy; ngay cả trong 3 chiều, ngoài cách xếp theo lattice đều còn có vô số cách xếp phi lattice bằng cách thay đổi độ dịch ngang của từng lớp, và khi đó mật độ vẫn bằng FCC lattice. Ở không gian nhiều chiều hơn, do thiếu đối xứng, thậm chí còn có giả thuyết rằng packing tối ưu luôn là phi lattice
• Thắc mắc về số chiều nhỏ nhất mà tại đó cấu trúc sphere packing mới này vượt qua các chiều vốn đã có mật độ tốt nhất được chứng minh trước đây
• Gợi ý hướng phát triển rằng kết quả nghiên cứu này có thể được ứng dụng trong mật mã học và truyền thông để xây dựng các hệ thống truyền thông an toàn hơn, đáng tin cậy hơn và tiết kiệm năng lượng hơn trong thực tế hay không; đây là một lĩnh vực nghiên cứu rất thú vị
• Một ẩn dụ dí dỏm nhắc tới “Cow Packing” trong vật lý thực, kiểu nghiên cứu lý thuyết về việc nhồi bò với mật độ tối ưu, như một ví von về khả năng ứng dụng thực tiễn
• Sphere packing thật thú vị vì nó xuất hiện trong rất nhiều bài toán thuộc các lĩnh vực ứng dụng khác nhau; mong chờ được đọc kỹ bài báo này