對於一個包含至少2個集合的、對並運算封閉的有限集合族,至少存在一個元素,使得它在至少一半的集合裏出現過。
我們來解讀一下這個猜想說的啥。
首先集合,就是包含了一係列元素的合集,這裏麵的元素既可以是數字,也可以是變量等。
例如這是一個我們常見的數集,而且是有限的(隻包括3個元素):{1,2,3}
至於無限數集,就像是自然數集、有理數集、整數集這種由無限個元素組成的集合。
當然,集合也有集合,它們組合起來,就可以被叫做集族,例如下圖中f就是一個集族:
在這些集族中,有一類特殊的集族對並運算封閉。
對集族中的集合而言,並運算就是對兩個集合求並集;至於並運算封閉,即是指在對任意兩個集合進行並運算後,其結果仍然在這個集族中。
以下麵這個集族為例:{1}{1,2}{1,2,3}{1,2,3,4}
無論是對{1}、{1,2}求並集,還是對{2,3,4}、{1}求並集,還是對{1,2}、{2,3,4}求並集……任意兩個集合求並集,其結果都會在這個集族中。
所以,上麵這個集族就符合並封閉集合這一要求,而並封閉猜想也正是基於此而提出。
值得注意的是,這一猜想中的“一半”是緊致的,畢竟對於任何一個集合的子集族,所有的元素恰好在一半的集合裏出現過。
它於1979年被一個叫péter frankl的數學家提出,所以也一度被叫做frankl猜想。
看起來似乎不難,然而到實際解決時,一眾數學家才發現這並不簡單。
達特茅斯學院數學教授peter winkler曾經在1987年就這個猜想給出尖銳的評價:
並封閉集合猜想確實很有名,除了它的起源和它的答案。
為了解決這個問題,數學家們也已經嚐試過不少方法。
例如有人試著給猜想加上一些限製條件,讓它在這些情況下成立。
像是將它和圖論中的二分圖(bipartite graph)聯係起來,證明具備其中某種性質的集族,在這個猜想的條件下成立。
又或是給其中的元素加以限製,再加以證明……
but,無論是哪種方法,距離真正需要證明的猜想都還差不少距離。
來自哥倫比亞大學的助理教授will sawin對此評價稱:
它看起來似乎是個不難解決的東西,畢竟長得和那種“容易解決的問題”很像。
然而,如今卻沒有任何一個證明能真正搞定它。
問題就這樣進度緩慢,直到2022年秋天,穀歌研究員justin gilmer借著朋友結婚的契機,迴到了羅格斯大學校園。
gilmer迴母校的時間是2022年10月,此時距他畢業離開數學學術圈,已過去7年。這些年來,他自覺無心專注純數學領域,轉而自學編程,投身了it行業。
此次返校,他拜訪了導師薩克斯,還四處轉了轉。
就在散步中,他突然迴憶起——當年自己徘徊於校園小徑,苦苦思索的一個數學問題:
沒錯,就是那個對“並封閉集合猜想”的證明。
讀博期間,gilmer絞盡腦汁,花了一整年時間卻毫無進展,隻是搞明白了為什麽這一看似簡單的問題難以解決。
為此,他還去找過導師薩克斯。但導師也曾在該問題上停滯不前,因而他既不看好gilmer的研究,也不願重新碰這一領域。據gilmer迴憶,當時導師差點把他趕出房間。
但現在,重迴校園轉一圈的gilmer有了個新想法:用信息論及相關原理解決並封閉猜想問題。
gilmer的思路是找反例。
根據並封閉集合猜想,一個正常的並封閉集族中,至少應該有一個元素在多於一半的集合中出現。
既然如此,隻要想辦法構造一個特殊的集族,裏麵沒有一個元素出現在超過1%的集合中,這個猜想就會被證偽,反之如果構造不出來,那麽猜想就可能成立。
現在,我們用信息論視角看這一猜想:
正常來說,如果從集族中任意挑出兩個集合,這兩個集合取並集後,並集中的元素比原來兩個集合更多,其信息熵應該比原來的單獨兩個集合更低。
然而如果基於“沒有一個元素出現在超過1%集合”這個限製條件,任意兩個集合取並集後,計算出來的信息熵竟然比原來的單獨兩個集合更高。
這顯然是不可能的,因此不存在這麽一個特殊的集族,glimer的反例也沒有找到。
但這也就意味著在“並封閉”集族中,至少存在一個元素,會出現在超過1%的集合中。
2022年11月16日,gilmer將這一思路寫成論文,發表在了arxiv上。
當然,他這篇論文還不是“完全體”,也就是說並沒有完全證明並封閉集合猜想——
畢竟這隻是至少1%,還不意味著原來的並封閉集合猜想中的至少50%就成立。
但這個新思路已經足夠讓學界震動。
普林斯頓大學數學家ryan alweiss評價“引入信息量”這一操作:非常聰明。
僅僅幾天後,就有3個不同的數學研究組基於他的研究,先後發表了研究論文,隨後也有更多研究者跟進,他們所在院校機構有牛津、普林斯頓、哥大、布裏斯托等。
在後續研究中,對“並封閉集合猜想”的概率值證明,被推進到了38%。
令這些數學家好奇的是,基於gilmer的研究,他自己上手將概率值推進到38%並不難。
對此,gilmer表示,自己已經五年多沒碰數學了,確實不知道如何進行分析工作來將其進一步推進下去。
不過,他也認為,正是因為對相關數學方法的生疏,讓他跳出了常理,用圈外辦法取得突破。
我們來解讀一下這個猜想說的啥。
首先集合,就是包含了一係列元素的合集,這裏麵的元素既可以是數字,也可以是變量等。
例如這是一個我們常見的數集,而且是有限的(隻包括3個元素):{1,2,3}
至於無限數集,就像是自然數集、有理數集、整數集這種由無限個元素組成的集合。
當然,集合也有集合,它們組合起來,就可以被叫做集族,例如下圖中f就是一個集族:
在這些集族中,有一類特殊的集族對並運算封閉。
對集族中的集合而言,並運算就是對兩個集合求並集;至於並運算封閉,即是指在對任意兩個集合進行並運算後,其結果仍然在這個集族中。
以下麵這個集族為例:{1}{1,2}{1,2,3}{1,2,3,4}
無論是對{1}、{1,2}求並集,還是對{2,3,4}、{1}求並集,還是對{1,2}、{2,3,4}求並集……任意兩個集合求並集,其結果都會在這個集族中。
所以,上麵這個集族就符合並封閉集合這一要求,而並封閉猜想也正是基於此而提出。
值得注意的是,這一猜想中的“一半”是緊致的,畢竟對於任何一個集合的子集族,所有的元素恰好在一半的集合裏出現過。
它於1979年被一個叫péter frankl的數學家提出,所以也一度被叫做frankl猜想。
看起來似乎不難,然而到實際解決時,一眾數學家才發現這並不簡單。
達特茅斯學院數學教授peter winkler曾經在1987年就這個猜想給出尖銳的評價:
並封閉集合猜想確實很有名,除了它的起源和它的答案。
為了解決這個問題,數學家們也已經嚐試過不少方法。
例如有人試著給猜想加上一些限製條件,讓它在這些情況下成立。
像是將它和圖論中的二分圖(bipartite graph)聯係起來,證明具備其中某種性質的集族,在這個猜想的條件下成立。
又或是給其中的元素加以限製,再加以證明……
but,無論是哪種方法,距離真正需要證明的猜想都還差不少距離。
來自哥倫比亞大學的助理教授will sawin對此評價稱:
它看起來似乎是個不難解決的東西,畢竟長得和那種“容易解決的問題”很像。
然而,如今卻沒有任何一個證明能真正搞定它。
問題就這樣進度緩慢,直到2022年秋天,穀歌研究員justin gilmer借著朋友結婚的契機,迴到了羅格斯大學校園。
gilmer迴母校的時間是2022年10月,此時距他畢業離開數學學術圈,已過去7年。這些年來,他自覺無心專注純數學領域,轉而自學編程,投身了it行業。
此次返校,他拜訪了導師薩克斯,還四處轉了轉。
就在散步中,他突然迴憶起——當年自己徘徊於校園小徑,苦苦思索的一個數學問題:
沒錯,就是那個對“並封閉集合猜想”的證明。
讀博期間,gilmer絞盡腦汁,花了一整年時間卻毫無進展,隻是搞明白了為什麽這一看似簡單的問題難以解決。
為此,他還去找過導師薩克斯。但導師也曾在該問題上停滯不前,因而他既不看好gilmer的研究,也不願重新碰這一領域。據gilmer迴憶,當時導師差點把他趕出房間。
但現在,重迴校園轉一圈的gilmer有了個新想法:用信息論及相關原理解決並封閉猜想問題。
gilmer的思路是找反例。
根據並封閉集合猜想,一個正常的並封閉集族中,至少應該有一個元素在多於一半的集合中出現。
既然如此,隻要想辦法構造一個特殊的集族,裏麵沒有一個元素出現在超過1%的集合中,這個猜想就會被證偽,反之如果構造不出來,那麽猜想就可能成立。
現在,我們用信息論視角看這一猜想:
正常來說,如果從集族中任意挑出兩個集合,這兩個集合取並集後,並集中的元素比原來兩個集合更多,其信息熵應該比原來的單獨兩個集合更低。
然而如果基於“沒有一個元素出現在超過1%集合”這個限製條件,任意兩個集合取並集後,計算出來的信息熵竟然比原來的單獨兩個集合更高。
這顯然是不可能的,因此不存在這麽一個特殊的集族,glimer的反例也沒有找到。
但這也就意味著在“並封閉”集族中,至少存在一個元素,會出現在超過1%的集合中。
2022年11月16日,gilmer將這一思路寫成論文,發表在了arxiv上。
當然,他這篇論文還不是“完全體”,也就是說並沒有完全證明並封閉集合猜想——
畢竟這隻是至少1%,還不意味著原來的並封閉集合猜想中的至少50%就成立。
但這個新思路已經足夠讓學界震動。
普林斯頓大學數學家ryan alweiss評價“引入信息量”這一操作:非常聰明。
僅僅幾天後,就有3個不同的數學研究組基於他的研究,先後發表了研究論文,隨後也有更多研究者跟進,他們所在院校機構有牛津、普林斯頓、哥大、布裏斯托等。
在後續研究中,對“並封閉集合猜想”的概率值證明,被推進到了38%。
令這些數學家好奇的是,基於gilmer的研究,他自己上手將概率值推進到38%並不難。
對此,gilmer表示,自己已經五年多沒碰數學了,確實不知道如何進行分析工作來將其進一步推進下去。
不過,他也認為,正是因為對相關數學方法的生疏,讓他跳出了常理,用圈外辦法取得突破。