|
最近华人数学家黄皓，用了3页论文，云淡风轻般的证明了布尔函数敏感度的猜想。布尔函数敏感度是一个困扰学界多年的问题，甚至有很多科学家在听说这个猜想被证明后，都以为证明会非常繁锁，甚至直接打算用几周来学习，但是看到论文后又惊叹于作者论证方式的巧妙，而纷纷点赞。而从网上的资料来看，这名科学家是马化腾、李嘉诚的老乡，也是汕头人。他2007年北大本科毕业后，他继续到UCLA就读博士毕业后，目前担任美国艾默里大学数学系助理教授。主要研究领域包括极值组合、图论及计算机理论。从他对于敏度感问题的证明来看，笔者有强烈的智商被碾压的感觉，明显能感到作者肯定是一位妥妥的学霸。 什么是布尔函数敏感度1992年布尔函数敏感度猜想被提出。什么是布尔函数的敏感度呢？ 可以把这个过程看成是一个读者填写调查问卷或者上网申请贷款的过程。你回答n个选择题（有限选向的选择题其实是可以看作为布尔向量），最终得出结论，如果其中有一道题你的不同答案能够直接改变结果，那么这个调查对于这道题敏感。 具体数学描述如下： 1.假设x是一个n维布尔向量(由0，1组成） 布尔猜想的本质是敏感度s是关于n的一个多项式。
以上图为例，在第一个、第二个输入同时反转时输出改变，这个block的敏感度是2，而第三个输入反转时输出直接变化，则此block的敏感度为1，那么取最大值这个布尔函数的敏感度是2。 布尔函数敏感度猜想的证明过程在黄皓之前所有的数学家都还没有找出敏感度函数bs(f)与原函数无关的解， Kenyon and Kutin两位数学家在猜想提出的92年证明了
后来的Rubinstein在95年证明了
而bs(f)和n的关系30年间还没有什么眉目。不过有两位数学家Gotsman和Linial巧妙地把这个猜想转换成了一个超立体的几何顶点问题。以下图为例，其中正方体每个顶点的坐标在坐标轴上标出，其输出结果用颜色表示，如红色代表输出为真，蓝色代表输出为假，那么对输入X的反转，其实就是将顶点沿正方向的边移动，如下图由（0，1，0）移动到（1，1，0）顶点的颜色由蓝色变为红色，则代表布尔函数对这个变化敏感。一个点周围与它异色的点的数量，等于布尔函数在这个顶点的敏感度。布尔函数的敏感度就是所有顶点敏感度中的最大值。
这个转化也为本文奠定了重要的基础，不过为了解读清楚，咱们从更基础的说起。 1.特征值与特征向量 设A是n阶方阵，如果数λ和n维非零列向量x使关系式Ax=λx成立，那么这样的数λ称为矩阵A特征值，非零向量x称为A的对应于特征值λ的特征向量。式Ax=λx也可写成( A-λE)X=0。 直白的讲其实x在这里是方阵的变换向量，而经x变换向方阵A并未改变只是沿原来的方向伸展了λ倍。 2.邻接矩阵 邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。在本文中咱们只研究无向图，设G=(V,E)是一个无向图，其中顶点V={v1,v2,…,vn} [1] 。那么G的邻接矩阵A的任一元素A[i,j]=1代表vi到vj有边，为0则代表vi到vj无边。由于顶点到自身没法有边所是一个主对角线为0的n阶方阵。 3.柯西交错定理 注意啊这可不是柯西均值定理。A是一个n×n阶矩阵，B是A的m×m阶主子矩阵(m<n)。矩阵A的特征值为λ1 ≥ λ2 ≥ ̈ ̈ ̈ ≥λn，矩阵B的特征值为μ1 ≥ μ2 ≥ ̈ ̈ ̈ ≥μm，那么其特征值之间的关系为：
4.证明引理 按照以下方法构造一个
这里解释一下在上述公式中 所以当n=1时
那么求解其特征值必为 5.具体证明过程 假设λ1是矩阵AH的最大本征值，v是λ1对应的本征向量，v1是本征向量v里绝对值最大的分量。那么有
上述第一个等式是由依据特征值的定义，第二、三等式是（Av）1的展开，第一个不等式依据和的绝对值小于绝对值的和，最后一个不等式是由于∆(H)是所有块敏感度的最大值，因而也成立。因此
消去v1,那么可得|λ1| AH是一个（
再由咱们刚刚证得的 |λ1|
即布尔函数的敏感度大于 以上就是证明过程的解析了，读者是不是也有智商被猜想证明人黄皓碾压的感觉呢？ |
|
|
维的方阵
代表单位矩阵，即主对角线为1其余部分为0，注意当n=1时矩阵为2*2维，当n=2时矩阵左上是A1右下是-A1,即是一个4*4维矩阵。
,由数学归纳法可知
或者
