Math Labs

Số học và Lý thuyết số

Giả thuyết Goldbach

Giả thuyết chưa được chứng minh rằng mọi số chẵn lớn hơn 2 đều là tổng của hai số nguyên tố.

Trực giácMọi số chẵn, tách thành hai số nguyên tố?

Thử tính tay: 4=2+24=2+2, 6=3+36=3+3, 8=3+58=3+5, 10=3+7=5+510=3+7=5+5, 100=3+97=11+89=17+83=29+71=41+59=47+53100=3+97=11+89=17+83=29+71=41+59=47+53. Mọi số chẵn từng được kiểm tra — hàng nghìn tỉ số — đều tách được thành hai số nguyên tố, thường theo nhiều cách. Khẳng định rằng điều này luôn đúng, với mọi số chẵn n>2n>2, chính là giả thuyết Goldbach; chưa ai từng tìm ra phản ví dụ, và cũng chưa ai chứng minh được là không có phản ví dụ.

Với N=98, hiển thị 8 trong 13 đường đầu từ số nguyên tố p đến phần bù 98−p khi phần bù là bán nguyên tố P₂.
Định lý Chen tại N=98N=98: widget vẽ 88 đường đầu trong 1313 đường nối số nguyên tố pp tới 98−p98-p khi phần bù là bán nguyên tố (P2P_2). Định lý Chen chỉ cần ít nhất một biểu diễn như vậy cho mọi mục tiêu chẵn đủ lớn.

Đại họcPhát biểu chính xác và các biến thể

Định nghĩa: Số cách biểu diễn Goldbach

Với nn chẵn, đặt r(n)=#{(p,q):p,q prime, p≤q, p+q=n}r(n) = \#\{(p,q) : p,q \text{ prime},\, p\le q,\, p+q=n\} là số cách biểu diễn không thứ tự của nn thành tổng hai số nguyên tố. Giả thuyết Goldbach mạnh (nhị phân) phát biểu rằng n=p1+p2n = p_1 + p_2 có nghiệm là các số nguyên tố p1,p2p_1,p_2 với mọi số chẵn n>2n>2, tức r(n)≥1r(n)\ge1.

r(n)=#{(p,q):p,q prime, p≤q, p+q=n}r(n) = \#\{(p,q) : p,q \text{ prime},\, p\le q,\, p+q=n\}

Một phát biểu khác, yếu hơn, là giả thuyết Goldbach tam phân (hay "yếu"): mọi số lẻ n>5n>5 đều là tổng của ba số nguyên tố, n=p1+p2+p3n = p_1+p_2+p_3. Về mặt lịch sử, lá thư năm 1742 của Goldbach gửi Euler đề xuất một dạng của phát biểu tam phân (khi đó số 11 vẫn được coi là số nguyên tố); Euler phát biểu lại thành dạng nhị phân chuẩn ngày nay. Hai giả thuyết này ngày nay có tình trạng rất khác nhau, được tóm tắt ở bảng dưới.

n=p1+p2+p3,n odd, n>5n = p_1+p_2+p_3, \qquad n \text{ odd},\ n>5
Goldbach nhị phân so với tam phân: tình trạng hiện nay
Tiêu chíNhị phân (mạnh)Tam phân (yếu)
Phát biểun=p1+p2n = p_1 + p_2n=p1+p2+p3n = p_1+p_2+p_3
Tình trạngCòn mởĐã chứng minh (Helfgott, 2013)
Kết quả từng phần chắc chắn tốt nhấtĐịnh lý Chen (1973): nguyên tố + gần nguyên tố bậc 2Đã giải quyết trọn vẹn cho mọi n>5n>5

Đại họcHai định lý đã chứng minh trên con đường tới Goldbach

Tồn tại N0N_0 sao cho với mọi số chẵn n>N0n>N_0, n=p+mn = p + m trong đó pp là số nguyên tố và mm là số nguyên tố hoặc tích của đúng hai số nguyên tố (một số gần nguyên tố bậc 2).

Vì sao đúng?

Đây là kết quả gần nhất mà con người đạt được khi chứng minh Goldbach nhị phân bằng một lập luận hoàn toàn chặt chẽ, không điều kiện: nó nới lỏng 'số nguyên tố' thành 'số nguyên tố hoặc gần nguyên tố bậc 2' ở một phía, điều mà phương pháp sàng có thể xử lý dù không thể tách riêng số nguyên tố một cách chính xác.

Chứng minh

Chứng minh là một lập luận sàng có trọng số. Cố định số chẵn nn lớn và xét, với mỗi số nguyên tố p≤np\le n, liệu n−pn-p có ít ước nguyên tố hay không. Một sàng ngây thơ (sàng cận trên Selberg) có thể chỉ ra rằng số các p≤np\le n mà n−pn-p có nhiều nhất hai ước nguyên tố không quá nhỏ — nhưng chỉ dùng sàng đơn thuần thì không thể phân biệt "n−pn-p là số nguyên tố" với "n−pn-p có 3,4,…3,4,\dots ước nguyên tố" đủ mạnh để kết luận điều gì.

Công cụ then chốt của Chen, sàng có trọng số (hay "nguyên lý chuyển đổi"), gán cho mỗi ứng viên pp một trọng số dựng từ hai mức sàng khác nhau: một sàng cận trên cho biến cố "xấu" rằng n−pn-p có từ ba ước nguyên tố trở lên dưới ngưỡng z≈n1/3z\approx n^{1/3}, và một sàng cận dưới cho tổng số p≤np\le n mà n−pn-p nguyên tố cùng nhau với mọi số nguyên tố dưới zz. Lấy vế thứ hai trừ đi một bội số có trọng số thích hợp của vế thứ nhất tạo ra một tổng tổ hợp mà có thể chứng minh là dương khi nn đủ lớn — cho thấy tồn tại pp sao cho n−pn-p có nhiều nhất 22 ước nguyên tố trên ngưỡng, tức n−pn-p là số nguyên tố hoặc gần nguyên tố bậc 2.

Để "chứng minh được là dương", cần ước lượng một dạng song tuyến đến từ các số hạng dư của sàng, dùng các kết quả kiểu Bombieri–Vinogradov về phân bố số nguyên tố trong cấp số cộng với môđun lớn (trung bình trên các môđun tới khoảng n1/2−εn^{1/2-\varepsilon}); đây là đầu vào giải tích sâu sắc nhất, và cũng là lý do định lý cần nn "đủ lớn" thay vì đúng với mọi nn ngay từ đầu.

Định lý dừng lại ở "số nguyên tố hoặc gần nguyên tố bậc 2" chứ không phải "số nguyên tố hoặc số nguyên tố" vì các phương pháp sàng gặp phải vấn đề chẵn lẻ (parity problem): theo cách dựng, các trọng số sàng chuẩn không thể phân biệt số có số lượng ước nguyên tố chẵn với số có số lượng ước nguyên tố lẻ, nên chúng không bao giờ có thể sàng xuống tới riêng số nguyên tố từ kiểu lập luận này — gần nguyên tố bậc 2 là mục tiêu sắc bén nhất mà lý thuyết sàng hiện có thể đạt tới.

Mọi số lẻ n>5n>5 đều thoả n=p1+p2+p3n = p_1+p_2+p_3 với một số nguyên tố p1,p2,p3p_1,p_2,p_3 nào đó. I.M. Vinogradov đã chứng minh điều này năm 1937 cho mọi số lẻ nn đủ lớn; H. Helfgott hoàn tất chứng minh năm 2013, loại bỏ điều kiện "đủ lớn" và thiết lập kết quả cho mọi số lẻ n>5n>5.

Vì sao đúng?

Đây là thành công không điều kiện sâu sắc nhất của phương pháp vòng tròn áp dụng trực tiếp cho số nguyên tố, và nó biến giả thuyết Goldbach nhị phân từ một bài toán hoàn toàn mở thành một bài toán mà ít nhất phiên bản tổng ba số lẻ đã được giải quyết trọn vẹn.

Chứng minh

Chứng minh đi theo đúng phương pháp vòng tròn đã phác thảo trước đó trong nhánh lý thuyết số này, áp dụng cho tổng mũ có trọng số von Mangoldt F(α)=∑p≤nlog⁡p  e(pα)F(\alpha)=\sum_{p\le n}\log p\; e(p\alpha), với số cách biểu diễn có trọng số bởi ∫01F(α)3e(−nα) dα\int_0^1 F(\alpha)^3 e(-n\alpha)\,d\alpha.

Trên các cung lớn (khoảng ngắn quanh các số hữu tỉ a/qa/q với qq nhỏ), định lý Siegel–Walfisz về số nguyên tố trong cấp số cộng — đều với môđun qq tới bất kỳ luỹ thừa cố định nào của log⁡n\log n — cho phép tính tích phân ở đó một cách tường minh, cho ra số hạng chính 12S(n) n2\tfrac12\mathfrak S(n)\,n^2 trong đó S(n)\mathfrak S(n), "chuỗi kỳ dị," là tích các mật độ địa phương, mỗi số nguyên tố một mật độ, đo tần suất nn giải được dưới dạng p1+p2+p3p_1+p_2+p_3 theo môđun số nguyên tố đó. Với nn lẻ, mọi điều kiện địa phương đều giải được (không có chướng ngại nào tương tự chướng ngại chẵn lẻ gây khó khăn cho trường hợp nhị phân), nên S(n)\mathfrak S(n) bị chặn xa khỏi 00, và số hạng chính thực sự dương và có kích thước n2n^2.

Trên các cung nhỏ, ước lượng tổng mũ của Vinogradov cho số nguyên tố — một cận rất không tầm thường ∣F(α)∣≪n(log⁡n)4/q1/2|F(\alpha)|\ll n(\log n)^4/q^{1/2} đúng ở đó — cho thấy đóng góp là o(n2)o(n^2), nhỏ hơn hẳn số hạng chính, nên không thể triệt tiêu đóng góp dương từ các cung lớn. Kết hợp cả hai cho ra số cách biểu diễn dương khi nn đủ lớn, đó chính là định lý năm 1937 của Vinogradov.

Việc Helfgott hoàn tất năm 2013 làm cho mọi bước trên trở nên hoàn toàn tường minh thay vì chỉ "đủ lớn": các ước lượng cung lớn và cung nhỏ sắc hơn (bao gồm các cận tường minh, được máy tính kiểm chứng, cho không điểm của hàm LL Dirichlet tới một độ cao cụ thể) đã lấp đầy khoảng trống giữa ngưỡng tường minh nơi lập luận giải tích hoạt động và phạm vi đã được kiểm tra trực tiếp bằng máy tính, cho ra một chứng minh không điều kiện cho đúng nghĩa mọi số lẻ n>5n>5.

Đại họcỨng dụng thực tiễn và Ví dụ minh họa

Các cấu trúc tổng số nguyên tố kiểu Goldbach xuất hiện như những phép kiểm tra hợp lý trong việc sinh khoá mật mã (các số lớn được xây từ tổ hợp số nguyên tố không nên vô tình đơn giản hoá), và các thuật toán sàng phân đoạn được phát triển để tìm kiếm các biểu diễn Goldbach đi thẳng vào cùng bộ công cụ lý thuyết số tính toán dùng để tìm số nguyên tố lớn cho các hệ mật kiểu RSA. Việc kiểm tra giả thuyết bằng máy tính cho mọi số chẵn tới 4×10184\times10^{18} tự nó là một thành tựu mang tính cột mốc trong kỹ nghệ thuật toán và tính toán phân tán, đòi hỏi các sàng phân đoạn được song song hoá cẩn thận trên nhiều máy.

Cột xanh cho mọi mục tiêu chẵn từ 4 đến 120; kiểm chứng hữu hạn không phải chứng minh.
Biểu đồ độ phủ kiểm tra từng số chẵn từ 44 đến 120120 có biểu diễn thành tổng hai số nguyên tố hay không; mọi cột trong khoảng này đều màu xanh. Đây chỉ là tính toán hữu hạn — giả thuyết vẫn chưa được chứng minh, dù đã kiểm chứng đến 4×10184\times10^{18}.

Ví dụ: Đếm các cách biểu diễn của 100

Tìm r(100)r(100), số cách viết 100100 thành tổng không thứ tự của hai số nguyên tố.

Lời giải

Quét các số nguyên tố p≤50p\le50 và kiểm tra xem 100−p100-p có phải số nguyên tố không. p=3p=3: 9797 là số nguyên tố. p=11p=11: 8989 là số nguyên tố. p=17p=17: 8383 là số nguyên tố. p=29p=29: 7171 là số nguyên tố. p=41p=41: 5959 là số nguyên tố. p=47p=47: 5353 là số nguyên tố. Kiểm tra các số nguyên tố còn lại dưới 5050 (2,5,7,13,19,23,31,37,432,5,7,13,19,23,31,37,43) cho ra đối tác hợp số (98,95,93,87,81,77,69,63,5798,95,93,87,81,77,69,63,57 tương ứng).

Gom các trường hợp thành công: 100=3+97=11+89=17+83=29+71=41+59=47+53100=3+97=11+89=17+83=29+71=41+59=47+53.

Đếm các cặp không thứ tự này cho r(100)r(100) = 66, khớp với giá trị đã biết rõ cho n=100n=100.

Ví dụ: Định lý Chen trong thực tế

Minh hoạ định lý Chen với n=98n=98: tìm một số nguyên tố pp sao cho 98−p98-p là số nguyên tố hoặc gần nguyên tố bậc 2, và xác định trường hợp nào xảy ra.

Lời giải

Thử p=19p=19: 98−19=7998-19=79, là số nguyên tố, vậy điều này đã thoả mãn phát biểu Goldbach nhị phân mạnh hơn (một phần thưởng, vì 9898 đủ nhỏ để cả hai giả thuyết được kiểm chứng trực tiếp bằng tìm kiếm, không chỉ nhờ bảo đảm yếu hơn của Chen).

Để thấy phương án "số nguyên tố hoặc gần nguyên tố bậc 2" mà định lý Chen cụ thể bảo đảm trong trường hợp tổng quát, thử p=7p=7: 98−7=91=7×1398-7=91=7\times13, tích của đúng hai số nguyên tố — một số gần nguyên tố bậc 2. Vậy p=7p=7 minh hoạ nhánh gần nguyên tố bậc 2 của định lý Chen: 98=7+9198=7+91 với 9191 là gần nguyên tố bậc 2, bản thân nó không phải số nguyên tố.

Sự phân biệt này quan trọng: định lý Chen chỉ bảo đảm tồn tại một pp như vậy với n−pn-p là số nguyên tố hoặc gần nguyên tố bậc 2; bản thân nó không bảo đảm kết quả mạnh hơn "số nguyên tố hoặc số nguyên tố". Với n=98n=98 ta tình cờ tìm được cả một cặp Goldbach thực thụ (19+7919+79) lẫn một chứng nhân gần nguyên tố bậc 2 thực thụ (7+917+91), nhưng riêng phương pháp chứng minh của Chen chỉ mang lại loại bảo đảm sau cho nn lớn đến mức thiên văn, nơi tìm kiếm trực tiếp là bất khả thi.

Các đường từ số nguyên tố p đến phần bù 98−p khi phần bù là bán nguyên tố P₂, với mục tiêu N=98.
Ví dụ hữu hạn về dạng tổng số nguyên tố cộng bán nguyên tố trong định lý Chen tại N=98N=98: widget vẽ 88 trong 1313 đường đầu nối số nguyên tố pp tới 98−p98-p khi phần bù là bán nguyên tố (P2P_2). Tính toán nhỏ này minh họa dạng số hạng được phép, không áp dụng kết luận của Chen chỉ bảo đảm với NN đủ lớn.

Phát biểu nào là giả thuyết Goldbach mạnh (nhị phân)?

r(100)r(100), số cách viết 100100 thành tổng không thứ tự của hai số nguyên tố, bằng bao nhiêu?

Điều nào sau đây là điều mà định lý Chen thực sự chứng minh?

Việc kiểm chứng bằng máy tính giả thuyết Goldbach cho mọi số chẵn tới 4×10184\times10^{18} minh hoạ điều gì trong khoa học máy tính?

Tài liệu tham khảo

  1. H. A. Helfgott (2013). The ternary Goldbach conjecture is true · arXiv:1312.7748
  2. J. R. Chen (1973). On the representation of a larger even integer as the sum of a prime and the product of at most two primes · DOI:10.1360/ya1973-16-2-157
  3. T. Oliveira e Silva, S. Herzog, S. Pardi (2014). Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4×10184\times10^{18} · DOI:10.1090/S0025-5718-2013-02787-1