?

圖片來源：Pixabay

?

本文轉載自公眾號“量子位”

撰文 邊策 楊凈

?

這是一個嚴肅的科學問題，已經(jīng)困擾了人類數(shù)學家 25 年之久。根據(jù)常識，就是要保證果肉暴露在外面的面積最小，也就是切片的面積最小。如果跨越到更高的維度，是否依然成立？這就是 1995 年，由三位數(shù)學家提出的一個幾何學猜想。

?

現(xiàn)在，這個難題被一位華人統(tǒng)計學博士解決了。成果一經(jīng)發(fā)布，就迅速引起了數(shù)學、理論計算機科學、統(tǒng)計學等多個領域的科學家的關注。他們一致認為，數(shù)學大師、菲爾茲獎得主，原本猜想的提出者讓·布爾甘（Jean Bourgain）一定會對這一進展感到興奮。畢竟，在他去世前（2018 年）的幾個月里還在關心這一問題進展，但終其一生都未能解決。

?

?

困擾數(shù)學家 25 年的幾何問題

?

1984 年，著名數(shù)學家讓·布爾甘提出了一個猜想。

?

一個任意維度的凸體，用低一維的平面去平分，那么存在一個常數(shù) c，讓凸體至少存在一個切面的面積大于 c。

?

換句話說，如果你一刀平分“任意維度空間的西瓜”，隨便你怎么劈，總有一個切面總大于 c。（Ps：以往的科學家用的是蘋果的例子。但準確來說不能選蘋果，因為蘋果上下是凹的。）

?

在 3 維空間中，這個結論似乎很好理解，因為無論西瓜長成什么奇形怪狀，總不可能在每個角度都細長。像長形的西瓜，豎直切下去，切面很小，可以你也可以水平切開平分它，這樣切面就會很大。

?

但在 3 維世界中正確的事情，到了高維空間卻不一定成立。這個問題后來被布爾甘自己證明，但數(shù)學家們并不滿足于用平面切西瓜，而是希望能找到一個更小的切面，它可以是曲面。而這恰好是 1995 年 Kannan、Lovász 和 Simonovits 三人提出的 KLS 猜想關心的問題：用來平分的最小曲面面積是多少？

?

以二維空間里的一個三角形為例。這個最小的“曲面”是一段圓弧。用圓弧來平分一個三角形，中間的線長度最短，而最佳“平面”——直線——的效果略差。

?

如何用最小“切面”平分三角形。圖片來源：Quanta Magazine

?

到了更高維度的空間中，二等分的最佳平面和最佳曲面差距會變大嗎？切面的面積是否和維度 d 有關？

?

這個問題已經(jīng)不再是純粹的數(shù)學問題。普林斯頓大學數(shù)學系教授 Assaf Naor 表示，KLS 猜想在純粹的數(shù)學和理論計算機科學中都很重要。KLS 猜想的結果，直接關系到隨機行走算法的運行時間，如機器學習模型中采樣問題?！に宰詈蠼鉀Q這個幾何問題的學者，都并非幾何學的專家，而是來自計算機界。

?

?

用統(tǒng)計方法解決問題

?

經(jīng)過數(shù)學家的抽象，KLS 猜想就像一個封裝著氣體的容器，找到最佳切面就是尋找容器的“瓶頸”。

?

想象一個啞鈴形狀的容器，里面有一個氣體分子在隨機運動，啞鈴中間連接部分越細，分子就越難跑到另一側。

?

啞鈴形的平分切面很小。圖片來源：Yin Tat Lee 論文

?

現(xiàn)在人們想知道，在高維空間，這個凸的容器最細的地方有多細。（當然，啞鈴并非是凸的。）

?

2012 年，Eldan 通過引入一種稱為隨機定位的技術，來降低這個問題與維度上界。（到底是維度 d 的幾次冪。）

?

2015 年末，華盛頓大學的 Vempala 和 Yin Tat Lee改進了 Eldan 的隨機定位，以進一步將 KLS 因子（用于描述瓶頸是否存在）降低到維度的四次根 d1/4。

?

KLS 猜想的上界不斷降低。圖片來源：同上

?

甚至，他們還將冪指數(shù)降低到幾乎為 0，由于 d 的 0 次冪總是等于 1，Lee 和 Vempala 似乎證明了 KLS 因子是一個與維度無關的常數(shù)。

?

他們在 arXiv 上發(fā)布了他們的論文。但是幾天后，這篇文章就被人發(fā)現(xiàn)了一個缺陷，他們關于 d0 的證明是錯的。之后，二人修改了文章，把界限重新調整到 d1/4。幾年來，研究人員認為 KLS 猜想的探索已經(jīng)到此終結了。

?

?

不過他們還在論文中，保留了 d0 證明的一些想法。這也為后來的突破埋下伏筆。

?

他們的論文引起了另一位統(tǒng)計學者 Yuansi Chen 的注意。Chen 當時是加州大學伯克利分校的統(tǒng)計學研究生，他正在研究隨機采樣方法的混合率。而隨機采樣是許多類型統(tǒng)計推斷中的關鍵，例如貝葉斯統(tǒng)計。

?

Chen 深入研究文獻，花了數(shù)周時間試圖填補 Lee 和 Vempala 的證明中的空白，但依然沒有解決。于是他轉變了思路，在 Lee 和 Vempala 的思想指導下，他找到了一種方法，采用遞歸來降低 KLS 因子上界。

?

經(jīng)過反復迭代，這種方法將 KLS 猜想問題再次拉回到 d0 的上界。這一結果意味著，高維凸形物體不會有啞鈴那樣的結構。在 n 維凸體中隨機行走，遍歷整個圖形的速度比我們之前預想得要快得多。這將有助于計算機科學家對不同的隨機采樣算法進行優(yōu)先級排序。

?

?

三個計算機相關的科學家

?

雖然表面看上去，這三位學者似乎跟數(shù)學沒什么關系。但仔細翻看他們的履歷，他們都曾跟數(shù)學結下了不小的緣分。

?

首先，直接與研究相關的這位統(tǒng)計學博士后——Yuansi Chen（陳遠思，音譯）。今年年初，他開始在杜克大學統(tǒng)計科學系擔任助理教授的職位。主要研究方向是統(tǒng)計機器學習、優(yōu)化以及在神經(jīng)科學中的應用，尤其對其中域適應性、穩(wěn)定性、MCMC 采樣算法、卷積神經(jīng)網(wǎng)絡和計算神經(jīng)科學中出現(xiàn)的統(tǒng)計問題感興趣。

?

Yuansi Chen 于 2019 年在加州大學伯克利分校統(tǒng)計系獲得博士學位。其博士生導師是著名華裔統(tǒng)計學家、UC 伯克利統(tǒng)計系和電子工程與計算機科學系終身教授郁彬。在攻讀博士之前，他還在法國 Ecole Polytechnique 獲得了應用數(shù)學專業(yè)的工程師文憑。隨后，前往在蘇黎世聯(lián)邦理工學院 ETH Foundations of Data Science（ETH-FDS）做博士后研究。

?

而啟發(fā) Yuansi Chen 數(shù)學靈感的，是兩位計算機科學家，Yin Tat Lee 和 Santosh S. Vempala。

?

Yin Tat Lee，目前是華盛頓大學助理教授，本科畢業(yè)于香港中文大學。2012 年從港中文大學畢業(yè)后，前往麻省理工學院攻讀博士學位，隨后前往微軟研究院做博士后研究。他的研究方向主要在算法方面，包括凸優(yōu)化、凸幾何、譜圖理論和在線算法等廣泛的課題。

?

以往的研究里，他曾結合連續(xù)數(shù)學和離散數(shù)學的思想，大幅提升了在計算機科學和優(yōu)化中許多基本問題的算法，比如線性編程和最大流量問題。他曾獲得 SODA 最佳論文獎、NeurIPS 2018 最佳論文獎、NSF 職業(yè)獎。去年他還獲得了有“諾獎風向標”之稱的斯隆獎，以及美國最大的非政府獎學金之一——帕卡德獎學金。

?

再來看 Santosh S. Vempala，佐治亞理工學院計算機科學教授。主要研究領域是理論計算機科學，包括抽樣、學習、優(yōu)化和數(shù)據(jù)分析的算法工具；隨機線性代數(shù)，高維幾何。他曾在卡內基梅隆大學攻讀博士學位，本科畢業(yè)于印度理工學院的計算機專業(yè)，曾獲 NSF 職業(yè)獎、斯隆獎等獎項。在來到佐治亞理工學院之前，他曾擔任 MIT 應用數(shù)學系擔任教授、UC 伯克利米勒研究員。

?

?

數(shù)學家：不可思議

?

Yuansi Chen 的論文一發(fā)布，迅速就引起了數(shù)學界的學者關注。不光是因為此前的錯誤證明，還由于陳遠思這個名字在數(shù)學界十分陌生，研究人員對待這一成果十分謹慎。

?

但他的方法很容易被驗證。早期研究過 KLS 猜想的以色列數(shù)學家 Boáz Klartag，就在第一時間看了論文。他表示：“我基本上立即停止了我正在做的一切事情，并檢查了這篇論文。這篇論文是 100% 正確的，這一點毫無疑問?！?/p>

?

除了一眾數(shù)學家關注之外，這篇論文還引起了理論數(shù)學家、統(tǒng)計學等領域的注意。哈佛大學計算機科學教授、微軟研究院前新英格蘭首席研究員 Boaz Barak 則發(fā)推祝賀，并表示這是一個非常重要的突破，加速了對近似凸體體積的研究。

?

?

但點贊祝賀之余，也有不少學者表示十分遺憾。因為提出這一猜想的人菲爾茲獎得主布爾甘已于 2018 年去世，如果他還在的話，一定會為這一進展感到興奮。

?

據(jù) Quanta Magazine 報道，布爾甘曾在去世前幾個月，聯(lián)系了他的朋友、特拉維夫大學教授 Vitali Milman，詢問這一猜想是否有任何進展，想在離開之前知道答案。

?

但 Vitali Milman 說，布爾甘在這一問題上，花費的時間和投入的精力比任何其他問題多得多。沒想到，最后這個問題卻被統(tǒng)計學解決了。

?

參考鏈接：

[1] https://www.quantamagazine.org/statistics-postdoc-tames-decades-old-geometry-problem-20210301/?

[2] https://www.cc.gatech.edu/~vempala/papers/kls_survey.pdf?

[3] https://arxiv.org/abs/2011.13661?

[4] http://yintat.com/?

[5] https://people.math.ethz.ch/~chenyua/?

[6] https://www.cc.gatech.edu/news/604802/computer-scientists-make-kls-conjecture-breakthrough?

關注【深圳科普】微信公眾號，在對話框：
回復【最新活動】，了解近期科普活動
回復【科普行】，了解最新深圳科普行活動
回復【研學營】，了解最新科普研學營
回復【科普課堂】，了解最新科普課堂
回復【科普書籍】，了解最新科普書籍
回復【團體定制】，了解最新團體定制活動
回復【科普基地】，了解深圳科普基地詳情
回復【觀鳥知識】，學習觀鳥相關科普知識
回復【博物學院】，了解更多博物學院活動詳情