符号与单位向量内积猜想获证

任给 n 维单位向量 a, 随机产生符号向量 x（每个分量等概率取 1 或 -1）， 猜想： ，其中 Prob 表示概率。

此为 符号与单位向量内积猜想，也称为 托氏猜想（Tomaszewski猜想）。1986年4月Richard Guy发表于《美国数学月刊》的论文[1]中首次提出该猜想，并归功于Boguslav Tomaszewski。该猜想有一个等价的几何版本：

一个n维超立方体的内接球的平行支撑超平面可以夹住该超立方体 至少一半的顶点。

以n=2为例，如下图所示，正方形有4个顶点，内接圆的任意两条平行切线至少夹住2个顶点，当平行线与正方形边重合时夹住4个顶点。

托氏猜想自提出以来广为关注。1992年，Holzman和Kleitman[2]证明了概率下界至少 为3/8=0.375，该记录一直保持到2017年才被Boppana和Holzman[3]打破，下界改进到 0.406；2020、2021年学者们进一步改进到 0.427[4]和 0.46[5]，被证明的下界逐渐接近0.5。另一条证明路线是依次证明n=2,3,4... 成立，比如2017年[6]证明了n≤9时猜想成立。还有一条路线是 证明 对最小的b成立 ，[7]提到了 。值得一提的是，Hiriart-Urruty 2008年将该猜想列为优化与矩阵分析9个公开问题中的第8个[7]（有趣的是，Hiriart-Urruty在2007年[8]中提了14个公开问题，这样“凑”出了 优化23个公开问题）。

2022年5月底，以色列巴伊兰大学数学系两位学者N.Keller和O.Klein 彻底证明了托氏猜想，论文发表在Advances in Mathematics[9]。

托氏猜想（现需改称 托氏定理，Tomaszewski定理）在优化中的应用最早追溯到三位国际知名专家Ben-Tal, Nemirovski和Roos在2002年发表的著名论文[10]，该论文在未知 托氏猜想的前提下，独立提出了该猜想，并且 独立证明了1/3的概率下界。此外，该论文还提出了更一般的猜想：

对任一 n 阶对称矩阵 B，随机产生符号向量 x（每个分量等概率取 1 或者 -1），总成立 。

当B是半正定且秩为1时，上述猜想退化成 托氏定理。

论文[10]证明了的下界，并作为应用分析了齐次二次约束二次非凸优化的半定规划算法的近似比。2008年何斯迈教授、罗智泉院士、聂家旺教授、张树中教授[11]首次证得 0.03的常数下界。 同年，该下界被改进成 0.0309[12]。 2013年， 袁亚湘院士用一个简单的例子（n=6, B为元素全为-1的矩阵，相应的概率 证伪了Ben-Tal，Nemirovski，Roos的猜想[13]。

2022年，在 戴彧虹研究员的指导下，中国科学院大学的本科生 杨景添同学构造了如下一个概率为 3/16的具体例子： （左右滑动查看完整内容）

笔者开设的《数学软件》课程中对 矩阵情形的猜想布置了大作业，北航数学科学学院的本科生 岳泽阳同学利用数值模拟的方法，算得概率为 3/16的例子。

参考文献

[1] R.K. Guy, Any answers anent these analytical enigmas? Am. Math. Mon. 93(4), (1986) 279-281.

[2] R. Holzman, D.J. Kleitman, On the product of sign vectors and unit vectors, Combinatorica 12(3), (1992) 303-316.

[3] R.B. Boppana, R. Holzman, Tomaszewski’s problem on randomly signed sums: breaking the 3/8 barrier, Electron. J. Comb. 24(3), (2017) P3.40.

[4] R.B. Boppana, H. Hendriks, M.C.A. van Zuijlen, Tomaszewski’s problem on randomly signed sums, Electron. J. Comb. 28(2), (2021) P2.35.

[6] H.Hendriks, M.C. Zuijlen, Linear combinations of Rademacher random variables. arXiv:1703.07251 (2017)

[7] Hiriart-Urruty, J.B., A new series of conjectures and open questions in optimization and matrix analysis.ESAIM: Control Optim. Calc. Var., 15, (2008) 454-470.

[8] Hiriart-Urruty, J.B., Potpourri of Conjectures and Open Questions in Nonlinear Analysis and Optimization, SIAM Rev., 49(2),(2007) 255-273.

[10] Ben-Tal A., Nemirovski A., Roos C., Robust solutions of uncertain quadratic and conic quadratic problems, SIAM J. Optim., 13(2), (2002) 535-560.

[11] He S.,Luo Z.-Q., Nie J., Zhang S., Semidefinite relaxation bounds for indefinite homogneous quadratic optimization, SIAM J. Optim.,19, (2008) 503-523.

[12] Veraar M., A note on optimal probability lower bounds for centered random variables,Colloq. Math., 113, (2008) 231-240.

[13] Yuan Y.-x.: A Counter-Example to a Conjecture of Ben-Tal, Nemirovski and Roos, J. Oper. Res. Soc. China, 1,(2013) 155-157.

作者：夏勇 北京航空航天大学

校对： 魏银璐

排版：柚子美编七号（西安交大金融优化组河图）

如需转载请联系公众号