'A-Team' môn Toán chứng minh mối liên hệ quan trọng giữa phép cộng và tập hợp | Tạp chí Quanta

Trong một tập hợp số được chọn ngẫu nhiên, phép cộng có thể trở nên điên cuồng.

Cộng từng cặp từ một bộ như vậy lại với nhau và bạn sẽ có một danh sách mới có thể có nhiều số hơn danh sách bạn đã bắt đầu. Bắt đầu với 10 số ngẫu nhiên và danh sách mới này (được gọi là tập hợp tổng) sẽ có khoảng 50 phần tử. Bắt đầu với 100 và tổng có thể sẽ có khoảng 5,000; 1,000 số ban đầu ngẫu nhiên sẽ tạo thành tổng dài 500,000 số.

Nhưng nếu tập hợp ban đầu của bạn có cấu trúc thì tập tổng có thể có ít số hơn tập hợp này. Hãy xem xét một bộ 10 số khác: tất cả các số chẵn từ 2 đến 20. Bởi vì các cặp khác nhau sẽ có tổng bằng cùng một số - 10 + 12 giống như 8 + 14 và 6 + 16 - nên tập hợp đó chỉ có 19 số, không phải 50. Sự khác biệt này ngày càng trở nên sâu sắc hơn khi các bộ ngày càng lớn hơn. Một danh sách có cấu trúc gồm 1,000 số có thể có một tập hợp chỉ có 2,000 số trong đó.

Vào những năm 1960, một nhà toán học tên là Gregory Freiman bắt đầu nghiên cứu các tập hợp có tổng nhỏ trong nỗ lực thăm dò mối liên hệ giữa phép cộng và cấu trúc tập hợp - một kết nối quan trọng xác định lĩnh vực toán học của tổ hợp cộng tính. Freiman đã đạt được tiến bộ ấn tượng, chứng minh rằng một tập hợp có tổng nhỏ phải được chứa bởi một tập hợp lớn hơn có các phần tử được đặt cách nhau theo một khuôn mẫu rất đều đặn. Nhưng sau đó lĩnh vực này bị đình trệ. “Chứng minh ban đầu của Freiman cực kỳ khó hiểu, đến mức không ai thực sự chắc chắn rằng nó đúng. Vì vậy, nó không thực sự có tác động như nó có thể gây ra,” nói Ti-mô-thê Gowers, một nhà toán học tại Collège de France và Đại học Cambridge và là người đoạt huy chương Fields. "Nhưng sau đó Imre Ruzsa xông vào hiện trường.”

Trong một loạt các hai giấy tờ vào những năm 1990, Ruzsa đã chứng minh lại định lý Freiman bằng một lập luận mới rất hay. Vài năm sau đó, Katalin Marton, một nhà toán học có ảnh hưởng người Hungary đã qua đời vào năm 2019, đã điều chỉnh câu hỏi về một tổng nhỏ ngụ ý gì về cấu trúc của tập hợp ban đầu. Cô thay thế các loại phần tử xuất hiện trong tập hợp và loại cấu trúc mà các nhà toán học nên tìm kiếm, nghĩ rằng điều đó sẽ cho phép các nhà toán học trích xuất nhiều thông tin hơn nữa. Giả thuyết của Marton có mối liên hệ với các hệ thống chứng minh, lý thuyết mã hóa và mật mã, đồng thời chiếm một vị trí cao trong tổ hợp phụ gia.

Phỏng đoán của cô ấy “có vẻ như thực sự là một trong những điều cơ bản nhất mà chúng tôi không hiểu được,” nói. bến xanh, một nhà toán học tại Đại học Oxford. Nó “gần như củng cố rất nhiều thứ mà tôi quan tâm.”

Green gia nhập lực lượng với Gowers, Cách cư xử của Freddie của Đại học California, San Diego và Terence tao, người đoạt huy chương Fields tại Đại học California, Los Angeles để hình thành nên điều mà nhà toán học và blogger người Israel Gil Kalai được gọi là “Một nhóm” của các nhà toán học. Họ đã chứng minh một phiên bản của giả thuyết trong một bài báo chia sẻ vào ngày 9 tháng XNUMX.

Lưới Katz, một nhà toán học tại Đại học Rice, người không tham gia vào công việc này, mô tả chứng minh là “rất đơn giản” - và “ít nhiều hoàn toàn bất ngờ”.

Tao sau đó đã bắt đầu nỗ lực chính thức hóa bằng chứng trong Nạc, một ngôn ngữ lập trình giúp các nhà toán học xác minh các định lý. Chỉ trong vài tuần, nỗ lực đó đã thành công. Sáng sớm Thứ Ba ngày 5 tháng XNUMX, Tao công bố rằng Lean đã chứng minh phỏng đoán mà không có bất kỳ lời “xin lỗi” nào - tuyên bố tiêu chuẩn xuất hiện khi máy tính không thể xác minh một bước nhất định. Đây là cách sử dụng cao nhất của như vậy công cụ xác minh kể từ năm 2021và đánh dấu một điểm uốn trong cách các nhà toán học viết chứng minh theo thuật ngữ mà máy tính có thể hiểu được. Gowers cho biết, nếu những công cụ này trở nên đủ dễ dàng để các nhà toán học sử dụng, chúng có thể thay thế cho quá trình đánh giá ngang hàng thường kéo dài và khó khăn.

Các thành phần của bằng chứng đã được nung nấu trong nhiều thập kỷ. Gowers hình thành những bước đi đầu tiên vào đầu những năm 2000. Nhưng phải mất 20 năm mới chứng minh được điều mà Kalai gọi là “chén thánh” của lĩnh vực này.

Trong nhóm

Để hiểu được phỏng đoán của Marton, cần làm quen với khái niệm nhóm, một đối tượng toán học bao gồm một tập hợp và một phép toán. Hãy nghĩ về các số nguyên - một tập hợp số vô hạn - và phép cộng. Mỗi lần bạn cộng hai số nguyên lại với nhau, bạn sẽ nhận được một số nguyên khác. Phép cộng cũng tuân theo một số quy tắc khác của phép toán nhóm, chẳng hạn như tính kết hợp, cho phép bạn thay đổi thứ tự các phép tính: 3 + (5 + 2) = (3 + 5) + 2.

Trong một nhóm, đôi khi bạn có thể tìm thấy những tập hợp nhỏ hơn thỏa mãn tất cả các đặc tính của nhóm. Ví dụ: nếu bạn cộng hai số chẵn bất kỳ, bạn sẽ nhận được một số chẵn khác. Các số chẵn là một nhóm, khiến chúng trở thành một nhóm con của các số nguyên. Ngược lại, các số lẻ không phải là một nhóm con. Nếu cộng hai số lẻ, bạn sẽ có một số chẵn — không có trong tập hợp ban đầu. Nhưng bạn có thể nhận được tất cả các số lẻ bằng cách thêm 1 vào mỗi số chẵn. Nhóm con dịch chuyển như thế này được gọi là coset. Nó không có tất cả các đặc tính của một nhóm con, nhưng nó vẫn giữ được cấu trúc của nhóm con theo nhiều cách. Ví dụ, giống như số chẵn, số lẻ đều cách đều nhau.

Marton cho rằng nếu bạn có một bộ thì chúng tôi sẽ gọi A được tạo thành từ các phần tử nhóm mà tổng của chúng không lớn hơn nhiều so với A chính nó thì tồn tại một nhóm con nào đó - gọi nó là G - với một tài sản đặc biệt. Sự thay đổi G một vài lần để tạo ra các bộ đệm, và những bộ đệm đó sẽ gộp lại với nhau để chứa bộ ban đầu A. Hơn nữa, cô cho rằng số lớp lân cận không tăng nhanh hơn nhiều so với kích thước của tập hợp — cô tin rằng nó phải liên hệ với nhau bởi một hệ số đa thức, trái ngược với sự tăng trưởng theo cấp số nhân nhanh hơn nhiều.

Điều này nghe có vẻ giống như một sự tò mò mang tính kỹ thuật cao. Nhưng vì nó liên quan đến một bài kiểm tra đơn giản - điều gì sẽ xảy ra khi bạn chỉ thêm hai phần tử vào tập hợp? — đối với cấu trúc bao trùm của một nhóm con, điều này rất quan trọng đối với các nhà toán học và nhà khoa học máy tính. Ý tưởng chung tương tự xuất hiện khi các nhà khoa học máy tính cố gắng mã hóa tin nhắn để bạn có thể giải mã chỉ một phần tin nhắn vào một lúc nào đó. Nó cũng xuất hiện trong các bằng chứng có thể kiểm tra được bằng xác suất, một dạng bằng chứng mà các nhà khoa học máy tính có thể xác minh bằng cách chỉ kiểm tra một vài thông tin riêng biệt. Trong mỗi trường hợp này, bạn chỉ làm việc với một vài điểm trong một cấu trúc — chỉ giải mã một vài bit từ một tin nhắn dài hoặc xác minh một phần nhỏ của một bằng chứng phức tạp — và kết luận điều gì đó về một cấu trúc cấp cao hơn, lớn hơn.

“Bạn có thể giả vờ rằng mọi thứ đều là một tập hợp con lớn của một nhóm,” nói Tom Sanders, một cựu sinh viên của Gowers, hiện là đồng nghiệp của Green's tại Oxford, hoặc bạn có thể, “có được mọi thứ bạn muốn từ sự tồn tại của nhiều sự trùng hợp cộng gộp. Cả hai quan điểm này đều hữu ích.”

Ruzsa công bố giả thuyết của Marton vào năm 1999, ghi công đầy đủ cho cô ấy. “Cô ấy đưa ra phỏng đoán đó một cách độc lập với tôi và Freiman, và có lẽ trước chúng tôi,” anh nói. “Đó là lý do tại sao khi nói chuyện với cô ấy, tôi quyết định gọi đó là phỏng đoán của cô ấy.” Tuy nhiên, các nhà toán học hiện nay gọi nó là giả thuyết Freiman-Ruzsa đa thức, hay PFR.

Zeros và Ones

Nhóm, giống như nhiều đối tượng toán học, có nhiều dạng khác nhau. Marton cho rằng phỏng đoán của cô đúng với mọi nhóm. Điều này vẫn chưa được hiển thị. Bài báo mới chứng minh điều đó cho một loại nhóm cụ thể, lấy các phần tử của nó là danh sách các số nhị phân như (0, 1, 1, 1, 0). Vì máy tính hoạt động ở dạng nhị phân nên nhóm này rất quan trọng trong khoa học máy tính. Nhưng nó cũng hữu ích trong tổ hợp cộng tính. Sanders nói: “Nó giống như bối cảnh đồ chơi này, trong đó bạn có thể chơi đùa và thử mọi thứ. Ông nói thêm: “Đại số hay hơn rất nhiều” so với việc làm việc với các số nguyên.

Các danh sách có độ dài cố định và mỗi bit có thể là 0 hoặc 1. Bạn cộng chúng lại với nhau bằng cách thêm từng mục vào mục tương ứng của nó trong danh sách khác, với quy tắc 1 + 1 = 0. Vậy (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR là một nỗ lực nhằm tìm ra một tập hợp có thể trông như thế nào nếu nó không hẳn là một nhóm con nhưng có một số đặc điểm giống nhóm.

Để làm cho PFR chính xác, hãy tưởng tượng bạn có một tập hợp các danh sách nhị phân được gọi là A. Bây giờ lấy mọi cặp phần tử từ A và thêm chúng lên. Các tổng kết quả tạo thành tổng của A, Được gọi là A + A. Nếu các phần tử của A được chọn ngẫu nhiên thì hầu hết các tổng đều khác nhau. Nếu có k các yếu tố trong A, điều đó có nghĩa là sẽ có khoảng k²/2 phần tử trong tập hợp. Khi k lớn — chẳng hạn, 1,000 — k²/2 lớn hơn rất nhiều so với k. Nhưng nếu A là một nhóm con, mọi phần tử của A + A là A, điều đó có nghĩa là A + A có cùng kích thước với A chính nó.

PFR coi các tập hợp không ngẫu nhiên nhưng cũng không phải là nhóm con. Trong các tập hợp này, số phần tử trong A + A hơi nhỏ - chẳng hạn như 10kHoặc 100k. “Nó thực sự hữu ích khi khái niệm về cấu trúc của bạn phong phú hơn nhiều so với việc chỉ là một cấu trúc đại số chính xác,” nói. Shachar Lovett, một nhà khoa học máy tính tại Đại học California, San Diego.

Tao nói rằng tất cả các tập hợp mà các nhà toán học biết đều tuân theo tính chất này “khá gần với các nhóm con thực tế”. “Đó là trực giác, rằng không có bất kỳ nhóm giả mạo nào khác đang tồn tại xung quanh.” Freiman đã chứng minh một phiên bản của tuyên bố này trong tác phẩm gốc của mình. Năm 1999, Ruzsa mở rộng định lý Freiman từ số nguyên sang danh sách nhị phân. Anh ấy tự hào rằng khi số phần tử trong A + A là bội số không đổi của kích thước của A, A được chứa trong một nhóm con.

Nhưng định lý Ruzsa yêu cầu nhóm con phải rất lớn. Cái nhìn sâu sắc của Marton là thừa nhận rằng thay vì bị giới hạn trong một nhóm nhỏ khổng lồ, A có thể được chứa trong một số đa thức các lớp lân cận của một nhóm con không lớn hơn tập ban đầu A.

'Tôi biết một ý tưởng thực tế khi tôi nhìn thấy một ý tưởng thực tế'

Vào khoảng đầu thiên niên kỷ, Gowers tình cờ thấy cách chứng minh của Ruzsa về định lý Freiman khi đang nghiên cứu một bài toán khác về các tập hợp chứa các chuỗi số cách đều nhau. Gowers nói: “Tôi cần thứ gì đó như thế này, kiểu lấy thông tin cấu trúc từ thông tin lỏng lẻo hơn nhiều về một tập hợp nhất định”. “Tôi rất may mắn vì trước đó không lâu, Ruzsa đã đưa ra được bằng chứng hoàn toàn tuyệt vời này.”

Gowers bắt đầu tìm ra cách chứng minh tiềm năng cho phiên bản đa thức của giả thuyết. Ý tưởng của anh ấy là bắt đầu với một bộ A có tổng tương đối nhỏ, sau đó thao tác dần dần A thành một nhóm con. Nếu anh ta có thể chứng minh được rằng nhóm con thu được giống với tập hợp ban đầu A, anh ta có thể dễ dàng kết luận rằng phỏng đoán là đúng. Gowers đã chia sẻ ý tưởng của mình với các đồng nghiệp, nhưng không ai có thể biến chúng thành một bằng chứng đầy đủ. Mặc dù chiến lược của Gowers đã thành công trong một số trường hợp, nhưng trong một số trường hợp khác, sự thao túng đã diễn ra. A càng đi xa khỏi kết luận mong muốn của giả thuyết Freiman-Ruzsa đa thức.

Cuối cùng, sân vẫn tiếp tục. Năm 2012, Sanders gần như đã chứng minh được PFR. Nhưng số lượng các nhóm con dịch chuyển mà anh ta cần đã ở trên mức đa thức, mặc dù chỉ một chút thôi. Gowers nói: “Một khi anh ấy làm điều đó, điều đó có nghĩa là nó trở thành một việc ít cấp bách hơn, nhưng vẫn là một vấn đề thực sự thú vị mà tôi rất yêu thích”.

Nhưng ý tưởng của Gowers vẫn tồn tại trong ký ức và ổ cứng của đồng nghiệp. Green, người cũng từng là học trò của Gowers, nói: “Có một ý tưởng thực sự ở đó. “Tôi biết một ý tưởng thực sự khi tôi nhìn thấy một ý tưởng thực sự.” Mùa hè này, Green, Manners và Tao cuối cùng đã giải phóng những ý tưởng của Gowers khỏi luyện ngục của họ.

Green, Tao và Manners đã cộng tác sâu 37 trang trước khi họ nghĩ đến việc quay lại những ý tưởng năm 20 tuổi của Gowers. Vào ngày 23 tháng XNUMX giấy, họ đã sử dụng thành công một khái niệm trong lý thuyết xác suất được gọi là các biến ngẫu nhiên để thăm dò cấu trúc của các tập hợp có tổng nhỏ. Bằng cách thực hiện chuyển đổi này, nhóm có thể thao tác các bộ của mình một cách khéo léo hơn. Manners nói: “Việc xử lý các biến ngẫu nhiên bằng cách nào đó ít cứng nhắc hơn nhiều so với việc xử lý các tập hợp. Với một biến ngẫu nhiên, “Tôi có thể điều chỉnh một trong các xác suất một lượng nhỏ và điều đó có thể mang lại cho tôi một biến ngẫu nhiên tốt hơn”.

Sử dụng quan điểm xác suất này, Green, Manners và Tao có thể chuyển từ làm việc với số phần tử trong một tập hợp sang đo lường thông tin chứa trong một biến ngẫu nhiên, một đại lượng gọi là entropy. Entropy không phải là điều mới mẻ đối với tổ hợp cộng tính. Thực ra, Tào đã cố gắng để phổ biến khái niệm này vào cuối những năm 2000. Nhưng chưa có ai thử sử dụng nó trên giả thuyết Freiman-Ruzsa đa thức. Green, Manners và Tao phát hiện ra nó rất mạnh mẽ. Nhưng họ vẫn không thể chứng minh được giả thuyết đó.

Khi cả nhóm nghiền ngẫm những kết quả mới, họ nhận ra rằng cuối cùng họ đã xây dựng được một môi trường trong đó những ý tưởng đang ngủ quên của Gowers có thể phát triển. Nếu họ đo kích thước của một tập hợp bằng cách sử dụng entropy của nó, thay vì số phần tử của nó, thì các chi tiết kỹ thuật có thể hoạt động tốt hơn nhiều. Tao nói: “Tại một thời điểm nào đó, chúng tôi nhận ra rằng những ý tưởng cũ này của Tim từ 20 năm trước thực sự có nhiều khả năng thành công hơn những ý tưởng mà chúng tôi đang thử nghiệm”. “Và vì vậy chúng tôi đã đưa Tim trở lại dự án. Và sau đó tất cả các mảnh ghép lại với nhau một cách độc đáo đến mức đáng ngạc nhiên.”

Tuy nhiên, vẫn còn nhiều chi tiết cần phải tìm ra trước khi đưa ra được bằng chứng. Manners nói: “Thật là ngu ngốc khi cả bốn chúng tôi đều vô cùng bận rộn với những việc khác. “Bạn muốn công bố kết quả tuyệt vời này và nói với thế giới, nhưng thực tế bạn vẫn phải viết bài kiểm tra giữa kỳ của mình.” Cuối cùng, nhóm đã vượt qua và vào ngày 9 tháng XNUMX, họ đã đăng bài báo của mình. Họ đã chứng minh rằng nếu A + A không lớn hơn k lần kích thước của Athì A có thể được bao phủ bởi không quá khoảng k¹² độ dịch chuyển của một nhóm con không lớn hơn A. Đây có thể là một số lượng ca làm việc khổng lồ. Nhưng nó là một đa thức nên nó không tăng nhanh theo cấp số nhân như k trở nên lớn hơn, như thể nó sẽ xảy ra k đã ở trong số mũ.

Vài ngày sau, Tào bắt đầu chính thức hóa việc chứng minh. Anh ấy đã cộng tác điều hành dự án chính thức hóa, sử dụng gói kiểm soát phiên bản GitHub để điều phối các đóng góp từ 25 tình nguyện viên trên khắp thế giới. Họ đã sử dụng một công cụ gọi là Blueprint được phát triển bởi Patrick Massot, một nhà toán học tại Đại học Paris-Saclay, để tổ chức các nỗ lực dịch từ những gì Tao gọi là “Tiếng Anh toán học” vào mã máy tính. Blueprint có thể, trong số những thứ khác, tạo ra một biểu đồ mô tả các bước logic khác nhau liên quan đến việc chứng minh. Khi tất cả các bong bóng đã được bao phủ trong cái mà Tao gọi là “màu xanh lá cây đáng yêu”, nhóm đã hoàn thành công việc. Họ phát hiện ra một vài lỗi đánh máy rất nhỏ trong bài báo - trong một bài viết trực tuyến tin nhắn, Tao lưu ý rằng “các phần thú vị nhất về mặt toán học của dự án tương đối đơn giản để chính thức hóa, nhưng chính các bước kỹ thuật 'rõ ràng' mới mất nhiều thời gian nhất."

Marton qua đời chỉ vài năm trước khi giả thuyết nổi tiếng của bà được chứng minh, nhưng bằng chứng đó phản ánh bà công việc của cuộc sống về entropy và lý thuyết thông tin. Gowers nói: “Mọi thứ hoạt động tốt hơn nhiều khi bạn thực hiện nó trong khuôn khổ entropy này so với trong khuôn khổ mà tôi đang cố gắng thực hiện”. “Đối với tôi, nó vẫn có vẻ hơi kỳ diệu.”

Quanta đang tiến hành một loạt cuộc khảo sát để phục vụ khán giả của chúng tôi tốt hơn. Lấy của chúng tôi khảo sát độc giả môn toán và bạn sẽ được tham gia để giành chiến thắng miễn phí Quanta buôn