บทนำ
ในช่วงกลางเดือนตุลาคม จัสติน กิลเมอร์ บินจากแคลิฟอร์เนียไปนิวยอร์กเพื่อร่วมงานแต่งงานของเพื่อน ขณะอยู่ที่ชายฝั่งตะวันออก เขาไปเยี่ยมที่ปรึกษาเก่าของเขา ไมเคิล แซกส์ซึ่งเป็นนักคณิตศาสตร์แห่งมหาวิทยาลัยรัตเกอร์ส ที่ซึ่งกิลเมอร์ได้รับปริญญาเอกเมื่อเจ็ดปีก่อน
Saks และ Gilmer กินข้าวกลางวันด้วยกัน แต่พวกเขาไม่ได้คุยกันเรื่องคณิตศาสตร์เลย อันที่จริง Gilmer ไม่ได้คิดอย่างจริงจังเกี่ยวกับคณิตศาสตร์เลยตั้งแต่จบที่ Rutgers ในปี 2015 นั่นคือตอนที่เขาตัดสินใจว่าเขาไม่ต้องการประกอบอาชีพด้านวิชาการและเริ่มสอนตัวเองในการเขียนโปรแกรมแทน ขณะที่เขาและ Saks รับประทานอาหาร Gilmer ก็เล่าให้ที่ปรึกษาเก่าฟังเกี่ยวกับงานของเขาที่ Google ซึ่งเขาทำงานเกี่ยวกับแมชชีนเลิร์นนิงและปัญญาประดิษฐ์
วันที่ Gilmer ไปเยี่ยม Rutgers มีแดดจัด ขณะที่เขาเดินไปรอบๆ เขาจำได้ว่าในปี 2013 เขาใช้เวลาช่วงปีที่ดีกว่านี้เดินไปตามเส้นทางเดียวกันในมหาวิทยาลัยได้อย่างไร โดยคิดถึงปัญหาที่เรียกว่าการคาดคะเนแบบปิดสหภาพ มันเป็นการตรึงใจแม้ว่าจะไร้ผล: สำหรับความพยายามทั้งหมดของเขา กิลเมอร์ประสบความสำเร็จในการสอนตัวเองเท่านั้นว่าทำไมปัญหาที่ดูเหมือนง่ายเกี่ยวกับชุดของตัวเลขจึงยากที่จะแก้ไข
“ฉันคิดว่าหลายคนคิดเกี่ยวกับปัญหาจนกว่าพวกเขาจะพอใจและเข้าใจว่าเหตุใดจึงยาก ฉันอาจใช้เวลากับมันมากกว่าคนส่วนใหญ่” กิลเมอร์กล่าว
หลังการเสด็จเยือนเมื่อเดือนตุลาคม มีบางสิ่งที่ไม่คาดฝันเกิดขึ้น พระองค์ทรงมีแนวคิดใหม่ กิลเมอร์เริ่มคิดถึงวิธีการใช้เทคนิคจากทฤษฎีสารสนเทศเพื่อแก้ปัญหาการคาดเดาแบบปิดสหภาพ เขาติดตามแนวคิดนี้เป็นเวลาหนึ่งเดือน โดยคาดหวังทุกครั้งว่าจะล้มเหลว แต่เส้นทางสู่การพิสูจน์กลับเปิดออก ในที่สุดเมื่อวันที่ 16 พฤศจิกายนเขา โพสต์ผลลัพธ์ที่ไม่เหมือนใคร นั่นทำให้นักคณิตศาสตร์สามารถพิสูจน์การคาดเดาทั้งหมดได้
กระดาษดังกล่าวทำให้งานติดตามผลยุ่งเหยิง นักคณิตศาสตร์ที่มหาวิทยาลัยออกซ์ฟอร์ด สถาบันเทคโนโลยีแมสซาชูเซตส์ และสถาบันเพื่อการศึกษาขั้นสูง รวมถึงสถาบันอื่น ๆ ได้สร้างขึ้นอย่างรวดเร็วจากวิธีการใหม่ของกิลเมอร์ แต่ก่อนที่จะทำ พวกเขาถามคำถามของตัวเองว่า ผู้ชายคนนี้คือใคร?
ครึ่งเต็ม
การคาดคะเนแบบปิดแบบยูเนียนนั้นเกี่ยวกับชุดของตัวเลขที่เรียกว่าชุด เช่น {1, 2} และ {2, 3, 4} คุณสามารถดำเนินการในฉากต่างๆ รวมถึงการรวมเข้าด้วยกันซึ่งหมายถึงการรวมเข้าด้วยกัน ตัวอย่างเช่น ยูเนียนของ {1, 2} และ {2, 3, 4} คือ {1, 2, 3, 4}
คอลเลกชันหรือตระกูลของชุดจะถือว่าเป็น "การรวมแบบปิด" หากการรวมกันของสองชุดในตระกูลเท่ากับชุดที่มีอยู่แล้วในตระกูล ตัวอย่างเช่น พิจารณาชุดสี่ชุดนี้:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}
รวมคู่ใดก็ได้และคุณจะได้ชุดที่มีอยู่ในครอบครัวแล้ว ทำให้ครอบครัวเป็นสหภาพที่ปิด
นักคณิตศาสตร์พูดคุยเกี่ยวกับรุ่นต่างๆ ของการคาดเดาแบบปิดสหภาพย้อนหลังไปถึงช่วงปี 1960 แต่ได้รับข้อความอย่างเป็นทางการครั้งแรกในปี 1979 ในบทความโดย ปีเตอร์ แฟรงเคิลนักคณิตศาสตร์ชาวฮังกาเรียนที่อพยพไปญี่ปุ่นในช่วงปี 1980 และถือว่าการแสดงข้างถนนเป็นหนึ่งในกิจกรรมของเขา
Frankl คาดเดาว่าหากกลุ่มของชุดเป็นแบบปิด จะต้องมีองค์ประกอบอย่างน้อยหนึ่งรายการ (หรือตัวเลข) ที่ปรากฏในอย่างน้อยครึ่งหนึ่งของชุด มันเป็นธรณีประตูตามธรรมชาติด้วยเหตุผลสองประการ
ประการแรก มีตัวอย่างที่มีอยู่ทั่วไปของครอบครัวแบบปิดซึ่งองค์ประกอบทั้งหมดปรากฏใน 50% ของชุดทั้งหมด เช่นเดียวกับชุดต่างๆ ที่คุณสร้างได้ตั้งแต่ตัวเลข 1 ถึง 10 เป็นต้น มีชุดดังกล่าว 1,024 ชุดซึ่งประกอบกันเป็นตระกูลปิดสหภาพ และแต่ละองค์ประกอบ 10 รายการปรากฏใน 512 รายการ และอย่างที่สอง ในเวลาที่แฟรงเคิลสร้างการคาดเดานั้นไม่มีใครเคยสร้างตัวอย่างของครอบครัวที่มีสหภาพปิดซึ่งการคาดเดาไม่ได้เกิดขึ้น
ดังนั้น 50% จึงดูเหมือนคำทำนายที่ถูกต้อง
ไม่ได้หมายความว่าจะพิสูจน์ได้ง่าย ในช่วงหลายปีที่ผ่านมาตั้งแต่บทความของ Frankl มีผลลัพธ์เพียงเล็กน้อย ก่อนงานของกิลเมอร์ เอกสารเหล่านั้นสามารถสร้างเกณฑ์ที่แตกต่างกันไปตามจำนวนชุดในตระกูลเท่านั้น (แทนที่จะเป็นเกณฑ์ 50% เดียวกันสำหรับตระกูลชุดทุกขนาด)
“รู้สึกว่ามันควรจะง่ายและคล้ายกับปัญหามากมายที่ง่าย แต่ก็ต้านทานการโจมตีได้” กล่าว วิล สวิน ของมหาวิทยาลัยโคลัมเบีย.
การขาดความก้าวหน้าสะท้อนทั้งลักษณะที่ยุ่งยากของปัญหาและข้อเท็จจริงที่ว่านักคณิตศาสตร์จำนวนมากไม่ต้องการคิดเกี่ยวกับมัน พวกเขากังวลว่าพวกเขาจะเสียเวลาหลายปีในอาชีพการงานเพื่อไล่ตามปัญหาที่ล่อลวงซึ่งไม่สามารถแก้ไขได้ กิลเมอร์จำวันหนึ่งในปี 2013 เมื่อเขาไปที่สำนักงานของ Saks และนำข้อสันนิษฐานที่ปิดโดยสหภาพแรงงานขึ้นมา ที่ปรึกษาของเขาซึ่งในอดีตเคยต่อสู้กับปัญหาด้วยตัวเอง เกือบจะโยนเขาออกจากห้อง
“ไมค์พูดว่า 'จัสติน คุณจะทำให้ฉันคิดถึงปัญหานี้อีกครั้ง และฉันไม่ต้องการทำเช่นนั้น'” กิลเมอร์กล่าว
ข้อมูลเชิงลึกของความไม่แน่นอน
หลังจากไปเยี่ยมรัตเกอร์ส กิลเมอร์ก็ครุ่นคิดถึงปัญหาในใจ พยายามเข้าใจว่าเหตุใดจึงยากนัก เขากระตุ้นตัวเองด้วยข้อเท็จจริงพื้นฐาน: หากคุณมีครอบครัว 100 ชุด จะมี 4,950 วิธีที่แตกต่างกันในการเลือกสองชุดและรวมเข้าด้วยกัน จากนั้นเขาถามตัวเองว่า: เป็นไปได้อย่างไรที่สหภาพที่แตกต่างกัน 4,950 ชุดกลับเข้าสู่ชุดข้อมูลเพียง 100 ชุด หากไม่มีองค์ประกอบใดปรากฏขึ้นในสหภาพเหล่านั้นด้วยความถี่อย่างน้อย
ถึงตอนนั้นเขากำลังเดินทางไปพิสูจน์ ทั้งๆ ที่เขายังไม่รู้เลย เทคนิคจากทฤษฎีสารสนเทศ ซึ่งให้วิธีคิดอย่างเข้มงวดเกี่ยวกับสิ่งที่คาดหวังเมื่อคุณดึงวัตถุคู่หนึ่งแบบสุ่ม จะพาเขาไปที่นั่น
ทฤษฎีสารสนเทศพัฒนาขึ้นในช่วงครึ่งแรกของศตวรรษที่ 20 ซึ่งโด่งดังที่สุดในงานเขียนของ Claude Shannon ในปี 1948 “ทฤษฎีทางคณิตศาสตร์ของการสื่อสาร” เอกสารนี้มีวิธีการคำนวณปริมาณข้อมูลที่จำเป็นในการส่งข้อความได้อย่างแม่นยำ โดยพิจารณาจากจำนวนความไม่แน่นอนของข้อความที่จะกล่าวถึง ลิงค์นี้ — ระหว่างข้อมูลและความไม่แน่นอน — เป็นข้อมูลเชิงลึกพื้นฐานที่น่าทึ่งของแชนนอน
ยกตัวอย่างของเล่น สมมติว่าฉันโยนเหรียญห้าครั้งแล้วส่งลำดับผลลัพธ์ให้คุณ หากเป็นเหรียญธรรมดา จะใช้ข้อมูล 99 บิตในการส่งข้อมูล แต่ถ้าเป็นเหรียญที่โหลด — พูดได้ว่า 1% มีแนวโน้มที่จะออกหัว — จะใช้เวลาน้อยกว่านี้มาก ตัวอย่างเช่น เราสามารถตกลงกันล่วงหน้าว่าฉันจะส่ง XNUMX (ข้อมูลบิตเดียว) ให้คุณหากเหรียญที่โหลดออกหัวทั้งห้าครั้ง ซึ่งเป็นไปได้มากที่จะทำ ผลลัพธ์ของการพลิกเหรียญที่ยุติธรรมนั้นน่าประหลาดใจมากกว่าการพลิกเหรียญที่มีอคติ ดังนั้นข้อมูลเพิ่มเติม
ความคิดเดียวกันนี้ใช้กับข้อมูลที่อยู่ในชุดตัวเลข ถ้าฉันมีครอบครัวของชุดปิดสหภาพ — เช่น 1,024 ชุดที่ทำจากตัวเลข 1 ถึง 10 — ฉันจะสุ่มเลือกสองชุด จากนั้นฉันสามารถสื่อสารองค์ประกอบของแต่ละชุดกับคุณได้ จำนวนข้อมูลที่ใช้ในการส่งข้อความนั้นสะท้อนถึงปริมาณความไม่แน่นอนเกี่ยวกับองค์ประกอบเหล่านั้น ตัวอย่างเช่น มีโอกาส 50% ที่องค์ประกอบแรกในชุดแรกจะเป็น 1 (เนื่องจาก 1 ปรากฏในครึ่งหนึ่งของชุดใน ครอบครัว) เช่นเดียวกับที่มีโอกาส 50% ที่ผลลัพธ์แรกในลำดับการโยนเหรียญอย่างยุติธรรมคือออกหัว
ทฤษฎีสารสนเทศมักปรากฏใน combinatorics ซึ่งเป็นสาขาหนึ่งของคณิตศาสตร์ที่เกี่ยวข้องกับการนับวัตถุ ซึ่งเป็นสิ่งที่ Gilmer ได้ศึกษาในฐานะนักศึกษาระดับบัณฑิตศึกษา แต่ในขณะที่เขาบินกลับบ้านที่แคลิฟอร์เนีย เขากังวลว่าวิธีที่เขาคิดที่จะเชื่อมโยงทฤษฎีข้อมูลเข้ากับการคาดเดาแบบปิดนั้นเป็นความเข้าใจที่ไร้เดียงสาของมือสมัครเล่น แน่นอนว่านักคณิตศาสตร์ที่ทำงานอยู่เคยพบวัตถุแวววาวนี้มาก่อนและยอมรับว่ามันเป็นทองคำของคนโง่ .
“พูดตามตรง ฉันรู้สึกประหลาดใจเล็กน้อยที่ไม่มีใครนึกถึงเรื่องนี้มาก่อน” กิลเมอร์กล่าว “แต่บางทีฉันไม่ควรแปลกใจ เพราะฉันเองก็คิดเรื่องนี้มาหนึ่งปีแล้ว และฉันก็รู้ทฤษฎีสารสนเทศ”
มีโอกาสมากกว่าไม่
Gilmer แก้ไขปัญหานี้ในตอนกลางคืนหลังจากทำงานที่ Google เสร็จ และในวันหยุดสุดสัปดาห์ตลอดช่วงครึ่งหลังของเดือนตุลาคมและต้นเดือนพฤศจิกายน เขาได้รับการสนับสนุนจากแนวคิดที่นักคณิตศาสตร์กลุ่มหนึ่งได้สำรวจเมื่อหลายปีก่อนใน ความร่วมมือแบบเปิด ในบล็อกของนักคณิตศาสตร์ชื่อดังอย่าง Tim Gowers เขายังทำงานโดยมีหนังสือเรียนอยู่ข้างๆ เพื่อที่เขาจะได้ค้นหาสูตรที่เขาลืมไปแล้ว
“คุณคิดว่าคนที่สร้างผลลัพธ์ที่ยอดเยี่ยมไม่ควรปรึกษาบทที่ 2 ของ องค์ประกอบของทฤษฎีสารสนเทศแต่ฉันทำ” กิลเมอร์กล่าว
กลยุทธ์ของกิลเมอร์คือการจินตนาการถึงครอบครัวที่ปิดสนิทซึ่งไม่มีองค์ประกอบใดปรากฏในฉากแม้แต่ 1% ของฉากทั้งหมด ซึ่งเป็นตัวอย่างที่สวนทางกับกรณีที่หากมีอยู่จริง จะเป็นการบิดเบือนการคาดเดาของแฟรงเคิล
สมมติว่าคุณเลือกชุด A และ B สองชุดจากตระกูลนี้โดยการสุ่ม และพิจารณาองค์ประกอบที่อาจอยู่ในชุดเหล่านั้น ทีละชุด ตอนนี้ถาม: อะไรคืออัตราเดิมพันที่ชุด A มีหมายเลข 1? และชุด B? เนื่องจากทุกองค์ประกอบมีโอกาสน้อยกว่า 1% เล็กน้อยที่จะปรากฏในชุดใดก็ตาม คุณจึงไม่คาดคิดว่า A หรือ B จะมี 1 ซึ่งหมายความว่ามีความประหลาดใจเล็กน้อย — และได้รับข้อมูลเพียงเล็กน้อย — หากคุณเรียนรู้ว่าในความเป็นจริงแล้ว ทำ.
ต่อไป ลองนึกถึงโอกาสที่ผลรวมของ A และ B จะมี 1 ก็ยังไม่น่าเป็นไปได้ แต่ก็มีโอกาสมากกว่าโอกาสที่จะปรากฏในชุดใดชุดหนึ่ง เป็นผลรวมของความน่าจะเป็นที่ปรากฏใน A และความน่าจะเป็นที่ปรากฏใน B ลบความน่าจะเป็นที่ปรากฏในทั้งสองอย่าง ดังนั้นอาจจะต่ำกว่า 2%
นี่ยังต่ำ แต่ก็ใกล้เคียงกับข้อเสนอ 50-50 นั่นหมายความว่าต้องใช้ข้อมูลเพิ่มเติมเพื่อแบ่งปันผลลัพธ์ กล่าวอีกนัยหนึ่ง หากมีกลุ่มสหภาพปิดซึ่งไม่มีองค์ประกอบใดปรากฏในอย่างน้อย 1% ของชุดทั้งหมด จะมีข้อมูลในการรวมกันของสองชุดมากกว่าในชุดใดชุดหนึ่ง
“แนวคิดในการเปิดเผยสิ่งต่าง ๆ ทีละองค์ประกอบและการดูจำนวนข้อมูลที่คุณเรียนรู้นั้นฉลาดมาก นั่นคือแนวคิดหลักของการพิสูจน์” กล่าว ไรอัน อัลไวส์ ของมหาวิทยาลัยพรินซ์ตัน
เมื่อถึงจุดนี้ กิลเมอร์เริ่มเข้าใกล้การคาดเดาของแฟรงเคิล นั่นเป็นเพราะมันง่ายที่จะแสดงให้เห็นว่าในครอบครัวที่มีสหภาพปิด การรวมกันของสองชุดจำเป็นต้องมีข้อมูลน้อยกว่าชุดเอง — ไม่มากกว่านั้น
เพื่อดูว่าเหตุใด ลองคิดถึงครอบครัวที่ปิดสนิทซึ่งมีชุดต่างๆ 1,024 ชุดที่คุณสร้างได้ตั้งแต่หมายเลข 1 ถึง 10 หากคุณสุ่มเลือกชุดเหล่านี้สองชุด โดยเฉลี่ยแล้วคุณจะได้ชุดที่มีห้าองค์ประกอบ (จากชุดทั้งหมด 1,024 ชุด 252 ชุดประกอบด้วยองค์ประกอบ 120 รายการ ทำให้เป็นขนาดชุดที่พบได้บ่อยที่สุด) นอกจากนี้ คุณยังมีแนวโน้มที่จะจบลงด้วยการรวมกันที่มีองค์ประกอบประมาณ XNUMX รายการ แต่มีเพียง XNUMX วิธีที่แตกต่างกันในการสร้างชุดที่มีเจ็ดองค์ประกอบ
ประเด็นคือ มีความไม่แน่นอนเกี่ยวกับเนื้อหาของชุดสุ่มสองชุดมากกว่าที่จะรวมกัน ยูเนี่ยนเอียงไปยังชุดที่ใหญ่กว่าซึ่งมีองค์ประกอบมากกว่า ซึ่งมีความเป็นไปได้น้อยกว่า เมื่อคุณนำสองชุดมารวมกันในครอบครัวที่ปิดโดยสหภาพ คุณจะรู้ว่าจะได้อะไร เช่น เมื่อคุณโยนเหรียญที่มีอคติ ซึ่งหมายความว่าสหภาพมีข้อมูลน้อยกว่าชุดที่ประกอบด้วย
ด้วยเหตุนี้ Gilmer จึงมีหลักฐาน เขารู้ว่าหากไม่มีองค์ประกอบแม้แต่ 1% ของฉาก สหภาพจะถูกบังคับให้บรรจุข้อมูลเพิ่มเติม แต่สหภาพจะต้องมีข้อมูลน้อยลง ดังนั้นต้องมีอย่างน้อยหนึ่งองค์ประกอบที่ปรากฏในอย่างน้อย 1% ของชุด
ผลักดันถึง 50
เมื่อกิลเมอร์โพสต์หลักฐานของเขาในวันที่ 16 พฤศจิกายน เขาได้รวมข้อความว่าเขาคิดว่ามันเป็นไปได้ที่จะใช้วิธีการของเขาเพื่อให้เข้าใกล้การพิสูจน์ของการคาดเดาทั้งหมดมากขึ้น ซึ่งอาจเพิ่มเกณฑ์เป็น 38%
ห้าวันต่อมา สาม ต่าง กลุ่ม ของนักคณิตศาสตร์โพสต์เอกสารภายในไม่กี่ชั่วโมงของกันและกันที่สร้างขึ้นจากงานของ Gilmer เพื่อทำเช่นนั้น เพิ่มเติม เอกสาร ตามแต่การระเบิดครั้งแรกดูเหมือนว่าจะใช้วิธีการของ Gilmer ไปไกลที่สุดเท่าที่จะทำได้ การได้รับถึง 50% มีแนวโน้มที่จะใช้แนวคิดใหม่เพิ่มเติม
ถึงกระนั้น สำหรับผู้เขียนบทความติดตามผลบางคน การได้ 38% ค่อนข้างตรงไปตรงมา และพวกเขาสงสัยว่าทำไม Gilmer ไม่ทำเอง คำอธิบายที่ง่ายที่สุดกลายเป็นคำอธิบายที่ถูกต้อง: หลังจากห่างหายไปกว่าครึ่งทศวรรษของวิชาคณิตศาสตร์ กิลเมอร์ก็ไม่รู้ว่าจะทำงานวิเคราะห์ทางเทคนิคบางอย่างที่จำเป็นเพื่อดึงมันออกมาได้อย่างไร
“ผมเป็นคนค่อนข้างขี้ขลาด และพูดตามตรงว่าผมติดอยู่” กิลเมอร์กล่าว “แต่ฉันก็อยากรู้ว่าชุมชนจะเอายังไงต่อ”
แต่กิลเมอร์คิดว่าสถานการณ์เดียวกันที่ทำให้เขาขาดการฝึกฝนอาจทำให้หลักฐานของเขาเป็นไปได้ในตอนแรก
“มันเป็นทางเดียวที่ฉันจะอธิบายได้ว่าทำไมฉันถึงคิดเกี่ยวกับปัญหาเป็นเวลาหนึ่งปีในบัณฑิตวิทยาลัยและไม่ก้าวหน้า ฉันออกจากวิชาคณิตศาสตร์เป็นเวลาหกปี จากนั้นจึงกลับมาที่ปัญหาและทำสิ่งใหม่นี้ให้สำเร็จ” เขากล่าว “ฉันไม่รู้จะอธิบายอย่างไร นอกจากว่าการเรียนรู้ของเครื่องทำให้ความคิดของฉันมีอคติ”
การแก้ไข: January 3, 2023
พาดหัวเดิมอ้างถึง Gilmer ว่าเป็น "วิศวกรของ Google" แท้จริงแล้วเขาเป็นนักวิจัย
