Bước đột phá làm sáng tỏ cấu trúc ẩn của số nguyên tố

 (science.org)
1 điểm bởi GN⁺ 2024-08-02 | 1 bình luận | Chia sẻ qua WhatsApp
  • Bản preprint ngày 31/5 của James Maynard và Larry Guth đã loại trừ một số ngoại lệ cụ thể của giả thuyết Riemann, tạo ra bước tiến đầu tiên sau nhiều thập kỷ cho bài toán 165 năm tuổi về việc tìm ra cấu trúc ẩn trong phân bố số nguyên tố
  • Đối tượng cốt lõi là các zero không tầm thường của hàm zeta Riemann, vốn liên hệ trực tiếp đến việc hiểu sai số giữa ước lượng số lượng số nguyên tố của Gauss và phân bố số nguyên tố thực tế
  • Máy tính đã xác nhận rằng hơn 10 nghìn tỷ zero đều có phần thực bằng 1/2, nhưng điều các nhà toán học mong muốn không phải là kiểm chứng thực nghiệm mà là chứng minh rằng các vị trí khác là không thể
  • Thành quả lần này đã hạ cận trên số lượng zero tại mốc 3/4 vốn không được cải thiện kể từ Albert Ingham năm 1940, đồng thời phá vỡ một rào cản lâu năm bằng cách kết hợp lý thuyết số giải tích với giải tích điều hòa
  • Dù chứng minh đầy đủ giả thuyết Riemann vẫn còn xa, kết quả này có thể dẫn đến các công cụ mới để ước lượng số lượng số nguyên tố trong những khoảng ngắn hơn và xử lý các bài toán khác của lý thuyết số

Giả thuyết Riemann giải mã phân bố số nguyên tố

  • Mọi số tự nhiên đều có thể được phân tích thành tích của các số nguyên tố chỉ chia hết cho chính nó và 1, và các nhà toán học từ lâu đã muốn hiểu những số nguyên tố này được sắp xếp như thế nào trên trục số
  • Thoạt nhìn, số nguyên tố có vẻ khá ngẫu nhiên, nhưng người ta tin rằng bên trong chúng có một cấu trúc ẩn
  • Trong 165 năm qua, trọng tâm của việc tìm kiếm cấu trúc đó là giả thuyết Riemann
    • Nếu được chứng minh, nó có thể đóng vai trò như một Rosetta Stone để giải mã số nguyên tố
    • Nó gắn với giải thưởng 1 triệu USD của Clay Mathematics Institute

Ước lượng của Gauss và các zero của hàm zeta

  • Carl Friedrich Gauss khi 16 tuổi vào cuối những năm 1700 đã nhận thấy số nguyên tố trở nên thưa dần khi giá trị tăng lên, và ông ước lượng rằng số lượng số nguyên tố không vượt quá X có tỷ lệ xấp xỉ X / ln X
  • Ước lượng này khớp rất tốt với thực tế, theo cách mà số lượng số nguyên tố thực sự dao động nhẹ lên xuống quanh đường cong đó
  • Năm 1859, Bernhard Riemann đã cố gắng dùng hàm zeta Riemann để xử lý sự khác biệt giữa đường cong của Gauss và phân bố số nguyên tố thực tế
    • Hàm này nhận đầu vào là số phức, tức các số có cả thành phần thực và ảo
    • Các zero của hàm zeta nơi hàm zeta Riemann bằng 0 trực tiếp mô tả các dao động sai số quanh đường cong của Gauss

Những ràng buộc mà giả thuyết Riemann yêu cầu

  • Giả thuyết Riemann dự đoán rằng ngoài một số nghiệm tầm thường xuất hiện ở đầu vào âm, thì với mọi zero của hàm zeta, phần thực của đầu vào phải bằng 1/2
  • Nếu giả thuyết này đúng, biến động trong số lượng số nguyên tố sẽ bị giới hạn, đồng nghĩa với việc không có những cụm quá lớn hay những khoảng trống quá lớn của số nguyên tố trên trục số
  • Cho đến nay, máy tính đã kiểm tra hơn 10 nghìn tỷ zero không tầm thường của hàm zeta và tất cả đều nằm chính xác trên đường phần thực 1/2
  • Nhưng chỉ kiểm chứng thực nghiệm thì chưa đủ
    • Theo Maynard, một chứng minh không chỉ xác nhận rằng mệnh đề là đúng, mà còn giúp hiểu vì sao nó đúng và mang lại các kỹ thuật mới mạnh mẽ để xử lý số nguyên tố
    • Hiện vẫn chưa có ngay cả một hướng tấn công thực sự khả dĩ để chứng minh giả thuyết Riemann

Khe hẹp mà kết quả lần này nhắm tới

  • Vì chưa thể trực tiếp chứng minh toàn bộ giả thuyết Riemann, các nhà toán học đã chia nhỏ bài toán bằng cách thu hẹp các vùng mà zero của hàm zeta không thể tồn tại
  • Các zero không tầm thường của hàm zeta vốn đã bị giới hạn trong khoảng giữa 0 và 1
  • Ngoài ra còn có đối xứng gương quanh 1/2, nên nếu loại trừ được các zero tại mốc 3/4 thì cũng loại trừ được các zero tại mốc 1/4
  • Các kỹ thuật trước đây hoạt động tốt hơn ở khoảng giữa 1/2 và 3/4, hoặc giữa 3/4 và 1, nhưng vẫn còn khả năng nhiều zero có thể ẩn tại 3/4
  • Cận trên tốt nhất cho số lượng zero có thể nằm ở 3/4 là kết quả của nhà toán học Anh Albert Ingham năm 1940, và từ đó đến nay không ai cải thiện được

Cách tiếp cận của Maynard và Guth

  • Maynard là nhà toán học chuyên về lý thuyết số giải tích, từng nhận Huy chương Fields năm 2022, và trong 10 năm qua ông đã liên tục suy nghĩ về bài toán này vào mỗi chiều thứ Sáu nhưng không đạt kết quả
  • Tại hội nghị của American Mathematical Society năm 2020, Maynard đã nhờ Larry Guth của MIT, người chuyên về giải tích điều hòa, hỗ trợ
    • Giải tích điều hòa là nhóm kỹ thuật liên quan đến việc vay mượn ý tưởng từ vật lý để tách âm thanh thành các thành phần cấu thành
    • Guth cũng bám theo bài toán này trong vài năm, và ngay trước khi từ bỏ đã cùng Maynard tìm ra bước đột phá
  • Hai người mượn chiến lược từ ngôn ngữ toán học của nhau, trao đổi ý tưởng qua email đêm khuya, và bằng một cách không chính thống đã phá vỡ cận trên của Ingham

Khả năng lan sang toàn bộ lý thuyết số

  • Maksym Radziwill đánh giá công trình này là ý tưởng mới đầu tiên trong 50 năm về việc truy tìm các zero của hàm zeta, và cho rằng một lĩnh vực bị bỏ quên quá lâu nay có thể lại chuyển động
  • Cận trên được cải thiện gần như không giúp ích cho việc chứng minh toàn bộ giả thuyết Riemann, nhưng có thể ảnh hưởng đến lý thuyết số nói chung
    • Các nhà toán học có thể ước lượng tốt hơn số lượng số nguyên tố trong những khoảng ngắn hơn
    • Radziwill cho rằng chiến lược mới có thể giúp đơn giản hóa công trình trước đây của ông liên quan đến các hệ động lực
    • Nó cũng có thể hữu ích cho bài toán Kakeya
    • Guth quan tâm đến việc dùng ý tưởng này để khám phá mối liên hệ sâu sắc giữa vật lý của sóng và sự phân bố của các tập hợp số

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-08-02
Ý kiến trên Hacker News

  • Đây là nội dung từ tháng 5, và Quanta đã có một bài hay hơn; nó cũng đã được thảo luận ở đây rồi
    https://www.quantamagazine.org/sensational-proof-delivers-ne...

  • Thử tưởng tượng phát hiện này dẫn tới một đột phá lớn hơn về số nguyên tố, khiến việc phân tích thừa số nguyên tố các số nguyên lớn trở nên dễ dàng và làm cho mật mã khóa công khai như RSA bị vô hiệu hóa chỉ sau một đêm
    Nếu ngay cả CPU tiêu dùng cũng cho phép bất kỳ ai bẻ khóa các khóa có kích thước dùng trong dịch vụ thực tế, liệu ngành này có kế hoạch khôi phục thảm họa cho tình huống như vậy không? Các hãng lớn có thể nhanh chóng chuyển sang những hệ mật mã khác chưa bị phá vỡ không? Với giới phát triển jailbreak, modder console hay phe “tự do thiết bị” thì đó sẽ là một ngày như thiên đường, nhưng tác động tổng thể có lẽ sẽ mang tính thảm họa và khó đoán
    Có cảm giác ngành này không xem đột phá bất ngờ trong lý thuyết số là một sự kiện có thể xảy ra

    • Với RSA thì chuyện như vậy đã xảy ra nhiều lần rồi
      Từng có thời chính phủ Mỹ hạn chế xuất khẩu khóa RSA dài, và có lúc phần lớn thế giới dùng khóa RSA 128 bit, rồi phải vội chuyển sang khóa 512 bit vì phương pháp Dixon. Sau đó lại phải vội nâng lên 1024 bit vì special number field sieve, rồi lên 2048 bit vì general number field sieve; đó cũng không phải chuyện quá xa xưa
      Nhìn vào phần cứng mã hóa RSA những năm 80, có những thiết bị tự hào vì xử lý được 512 bit. Giờ thì vô dụng
      https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf
      Công thức độ phức tạp của special/general number field sieve chỉ khác nhau vài hằng số; nhìn vào các hằng số đó, tôi tự hỏi liệu chúng có thật sự giống giới hạn cơ bản không. Thật khó mà tin chắc rằng không có cách nào tiếp tục giảm các hằng số ấy để làm cho cả khóa 2048 bit cũng trở nên vô dụng
      Không cần phải hỏi “nếu RSA bị phá thì chuyện gì sẽ xảy ra”. Từ kinh nghiệm đã chứng kiến chuyện này nhiều lần, có thể nói ngay rằng mọi người sẽ cuống cuồng tăng kích thước khóa một lần nữa và kiểm toán toàn bộ dữ liệu có khả năng đã bị lộ
    • Nếu có ai tìm ra cách phân tích thừa số nguyên lớn một cách dễ dàng trên phần cứng tiêu dùng, thì sẽ rất đau đớn, vì RSA là một trong các thuật toán khóa công khai chủ chốt
      Tuy nhiên, trước khi lo lắng, cũng nên nhớ rằng RSA đã trụ vững qua 47 năm bị phân tích mật mã tích cực. Trong thời gian đó có nhiều thuật toán thay thế được đề xuất là ưu việt hơn, nhưng không ít trong số đó đã bị phá không lâu sau
      Xu hướng chuyển sang các thuật toán đường cong elliptic chủ yếu cũng là vì máy tính có thể xử lý mã hóa/giải mã dễ dàng hơn
      Cá nhân tôi, nếu phải đặt cược vào thuật toán khóa công khai nào vẫn còn tồn tại sau 10 năm nữa, tôi sẽ đặt vào RSA
    • Có vẻ đây là điểm mà việc chuyển sang đường cong elliptic xuất hiện, và cả chữ ký lẫn bắt tay (Diffie-Hellman) dường như đã tiến khá xa rồi
      Khôi phục thảm họa chắc chắn không phải việc làm trong 1 phút, nhưng nếu RSA/DH trở nên không an toàn chỉ sau một đêm thì cũng không có vẻ mọi thứ sẽ cứ thế bị mở toang. Các khóa SSH của tôi hiện cũng đang là sự pha trộn của nhiều cơ chế
    • Ngành này còn không chuẩn bị nổi cho một bản cập nhật CrowdStrike tệ hại, nhưng dù sao sau vài ngày cũng đã xử lý được
      Có vẻ năng lực chuẩn bị cho các kịch bản thảm họa thường bị đánh giá quá cao, còn năng lực sống sót qua chúng lại bị đánh giá quá thấp
    • Có quan điểm cho rằng việc phát hiện cách phân tích thừa số nhanh là cực kỳ hiếm. Kiểu như rất nhiều người thông minh đã xem xét rồi nên hiện tại có lẽ là bất khả thi, nhưng chính câu chuyện đó cũng có thể là điểm yếu
      Rủi ro này thực tế chẳng kém rủi ro một cơn bão Mặt Trời quy mô lớn làm sập lưới điện, rồi do chậm trễ trong sản xuất máy biến áp và thiếu dự trữ mà phải trải qua giai đoạn phục hồi kéo dài nhiều năm như thời đồ đá; nhưng từ góc nhìn đó, nó có vẻ quá nhỏ và quá lý thuyết nên khó dành nhiều thời gian cho nó
      Về kế hoạch, tôi không rõ đơn giản chuyển sang ECC có dễ đến vậy không. Mã hóa bất đối xứng thực tế của ECC dựa vào bí mật dùng chung, và nếu giả định RSA bị phá khiến kênh trao đổi không còn an toàn, nó có thể còn dễ bị tấn công trung gian hơn RSA. Có vẻ không phải một thay thế dễ dàng
      Riêng chuyện khác, cũng có khả năng RSA đã bị phá rồi và lời giải đang được các cơ quan giải mã giữ bí mật. Với họ, việc che giấu một đột phá sẽ rất hấp dẫn, và họ cũng có thể tìm cách kìm nén một “đột phá bất ngờ trong lý thuyết số”

  • Mọi người luôn nghĩ cấu trúc của các số nguyên tố là phức tạp, nhưng thực ra tôi xem nó chỉ là một cấu trúc đệ quy của kích thước khoảng cách mà các bội số của những khoảng cách trước đó không chạm tới được.
    Điều đó không có nghĩa là sẽ dễ “dự đoán” nếu không theo dõi tất cả các khoảng cách trước đó, nhưng về bản chất nó không phải là một cấu trúc phức tạp. Thật thú vị khi một cấu trúc đơn giản như vậy lại khó nắm bắt đến thế. Nó giống như dãy 3n+1 sinh ra độ phức tạp, hay ánh xạ logistic trở nên phức tạp khi vượt qua một ngưỡng tới hạn

    • Bộ sinh tạo ra “mọi số nguyên tố” khá đơn giản và tất định.
      Nhưng nếu chỉ cho số nguyên tố n và muốn lấy số nguyên tố tiếp theo, ta phải tính lại các phần dư không tầm thường, nên chỉ riêng biểu diễn nhị phân của số n không chứa đủ thông tin để trả lời nhanh số nguyên tố tiếp theo là gì. Trước hết cần tính trước một vài điểm mốc. Rốt cuộc vẫn có thêm độ phức tạp, nhưng vẫn khá đơn giản và hiển nhiên; đây thậm chí không phải là bài toán thuộc NP
    • À, đúng rồi. Chẳng có gì đơn giản hơn việc cung cấp lý thuyết nền tảng cho lý thuyết số, một trong những lĩnh vực nghiêm ngặt nhất và gây áp lực trí tuệ nhất trong toán học /s
    • Tôi thắc mắc tại sao chuyện này không được coi là một vấn đề đã được giải quyết.
      https://en.wikipedia.org/wiki/Information_theory
      https://en.wikipedia.org/wiki/Computational_irreducibility
      https://en.wikipedia.org/wiki/Aperiodic_tiling

  • Đoạn “trong các phiên suy nghĩ chuyên dụng vào chiều thứ Sáu, ông đã liên tục quay lại vấn đề này suốt 10 năm qua nhưng không có kết quả” thật truyền cảm hứng

    • Tôi nhớ Richard Hamming cũng từng để trống chiều thứ Sáu cho những suy nghĩ sâu và lớn. Một cách làm rất hay

  • Khi vẽ đường cong Gauss và đường cong Riemann trong một không gian cụ thể, ta thấy có gì đó còn kỳ diệu hơn.
    Muốn thấy ý nói về các không điểm tầm thường và không tầm thường là gì thì có thể xem hoạt ảnh Wikipedia này: [https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_I...](https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_Im_1_to_51.ogg)
    Về cơ bản, tôi nghĩ nó gợi ý rằng vẫn còn một mối quan hệ khác giữa số thực và số ảo mà ta chưa phát hiện ra.
    Và vì toán học Riemann có liên quan đến cơ học lượng tử, điều này cũng có hàm ý đối với việc tìm kiếm một lý thuyết về hấp dẫn.
    Việc các số nguyên tố có liên quan, hoặc có thể liên quan, đến lý thuyết hấp dẫn nghe như khoa học kỳ lạ vậy

  • Tôi tò mò về cách diễn đạt “cuối cùng họ đã đi vài nước cờ phi chính thống để phá vỡ giới hạn của Ingham”.
    Vì sao việc đem phương pháp từ lĩnh vực khác sang lại là phi chính thống? Với nền tảng kỹ thuật, chuyện đó ngược lại rất phổ biến. Giải tích điều hòa là công cụ nền tảng trong nhiều lĩnh vực như âm thanh, sóng, phân tích điện, thống kê, và các thuật toán của nó bên trong cũng là toán học thuần túy.
    Nếu muốn tìm cấu trúc lặp trong một hệ cơ sở nào đó, việc thử nhiều kỹ thuật biểu diễn khác nhau rồi chọn cái phù hợp nhất với bài toán chẳng phải là bình thường sao?

    • Tôi không đọc câu trích dẫn đó theo nghĩa phần phi chính thống của cách tiếp cận chỉ là dùng ý tưởng từ giải tích điều hòa. Việc dùng giải tích điều hòa trong lý thuyết số hoàn toàn không mới.
      Trong bài giảng đầu tiên về lý thuyết số giải tích, ý tưởng cốt lõi, và cũng là ý tưởng cốt lõi trong bài báo nổi tiếng năm 1859 của Riemann, có thể gọi là “giải tích điều hòa”. Việc Riemann là người tiên phong của lĩnh vực này cũng không phải ngẫu nhiên: https://old.reddit.com/r/math/comments/16bh3mi/what_is_the_b...
      Xu hướng lớn nóng nhất trong lý thuyết số hiện nay về bản chất cũng là giải tích điều hòa “chiều cao” trên các trường số: https://en.wikipedia.org/wiki/Automorphic_form, https://en.wikipedia.org/wiki/Langlands_program. Trường hợp một chiều mà chương trình Langlands muốn khái quát hóa là https://en.wikipedia.org/wiki/Tate%27s_thesis, còn được gọi là “phân tích Fourier trên các trường số” và là một trong những ý tưởng quan trọng nhất của lý thuyết số thế kỷ 20.
      Trong danh mục trích dẫn của bài báo Guth-Maynard còn có cuốn sách năm 1994 H. Montgomery, Ten Lectures On The Interface Between Analytic Number Theory And Harmonic Analysis, No. 84. American Mathematical Soc., 1994. Ngay từ năm 1994 đã có đủ giao điểm cho mười bài giảng, và nhìn vào số lượt trích dẫn của cuốn sách đó thì còn có nhiều giao điểm hơn thế nữa. Chính tôi cũng đã trích dẫn cuốn này trong hơn một nửa các bài báo của mình.
      Điều đáng ngạc nhiên không phải là việc họ dùng giải tích điều hòa, mà là áp dụng nó ở đâu và như thế nào. Đây là phần thật sự bất khả thi để truyền đạt cho độc giả đại chúng, nên tôi không muốn trách người viết bài.
      Nghe như đang nói “tạo ra liên kết thì có gì đáng ngạc nhiên”, nhưng các đột phá thường đến từ những liên kết mới, và việc thỉnh thoảng có những đột phá như vậy không có nghĩa là các liên kết mới không đáng ngạc nhiên
    • “Phi chính thống” có thể là cách nói hơi mạnh, nhưng có lẽ ý muốn nói là họ áp dụng theo cách mới các kỹ thuật sẵn có từ một lĩnh vực khác.
      Trong toán học, các đột phá lớn khá thường xuất hiện khi ai đó nhận ra sự song song giữa hai vùng thoạt nhìn không liên quan, rồi dùng ý tưởng của một vùng làm trực giác cho vùng kia.
      Phần khó nằm ở chỗ các liên kết liên ngành như vậy thường không hiển nhiên. Để thấy được sự tương đồng có thể cần một bước nhảy hiểu biết đáng kể
    • Cách diễn đạt hơi buồn cười. Chỉ là nhà báo viết theo kiểu nhà báo thôi.
      Cũng có thể nói rằng mọi phát hiện trong toán học đều có phần nào đó là “phi chính thống”. Chính thống rốt cuộc chỉ là toàn bộ những gì đã được biết cho đến nay

  • Từ câu “Thoạt nhìn thì có vẻ khá ngẫu nhiên. Nhưng thực ra người ta cho rằng bên trong các số nguyên tố có kiểu cấu trúc ẩn như vậy”, tôi tò mò không biết mẫu hình số nguyên tố giả định sẽ trông như thế nào
    Có phải người ta đang kỳ vọng một thứ như công thức dạng đóng không? Nếu giả thuyết Riemann được chứng minh, bước tiếp theo để hiểu phân bố sẽ là gì? Hay người ta kỳ vọng bản thân chứng minh đó sẽ chứa câu trả lời này?

  • Mỗi lần nghe chuyện về James Maynard, tôi lại càng tin chắc rằng ông là một thiên tài chỉ xuất hiện một lần trong một thế hệ
    Ông đã có quá nhiều đóng góp cho lý thuyết số nguyên tố, và tôi có cảm giác có khi trong đời mình sẽ được thấy chứng minh của giả thuyết Riemann

  • Đây là hình tôi mới thấy lần đầu nhưng khá cuốn hút nên thấy tò mò. Mẫu hình xuất hiện khi vẽ các số nguyên tố bằng đồ thị tọa độ cực là phát hiện gần đây, hay đã được biết từ lâu và chỉ được dùng làm minh họa? Tôi muốn biết tên gọi và lịch sử của nó

  • Hơi lạc đề một chút, nhưng câu này khiến tôi nghĩ đến một khía cạnh mà các bộ chứng minh tự động xử lý, nhưng có lẽ chúng ta còn chưa bắt đầu suy nghĩ tới
    “Nhà toán học Alex Kontorovich của Đại học Rutgers nói: ‘Đó là một đột phá gây chấn động. Trong chứng minh này có đầy những ý tưởng mới mà mọi người sẽ khai thác trong nhiều năm tới’”
    Chứng minh của một điều gì đó nhiều khi thú vị hơn không phải như một phương tiện để đem lại tính chặt chẽ, mà như một góc nhìn mới về đối tượng đó. Tôi tò mò liệu trong toán học tự động đã có những công trình theo hướng như vậy chưa