Hirsch 猜想是 1957 年针对线性规划中单纯形算法复杂度提出的(参考1000个科学难题,数学卷,袁亚湘:“凸多面体的d-步猜想”)。其描述如下:假设 P 为 d 维多面体,且面数为 n, 那么多面体 P 直径不超过n-d。这里的直径是组合意义上的: P中两个顶点的距离即指连接该两个顶点的最小边数,而 P 的直径则为 P 中两顶点之间的最大距离。2010年,来自西班牙的Santos宣布,他发现了一个 Hirsch 猜想的反例。事实上,他构造了一个 43 维具有 86 个面的多面体,然而其直径却超过43
(http://arxiv.org/abs/1006.2814)。 其证明过程借助了 polymake,它是一个专门针对多面体研制的软件。谈及该猜想的证明过程,Santos提到: 2002年, V. Klee 专门建议 Santos:为什么你不试图否证 Hirsch 猜想呢? 当然,在此之前,Klee 也给了自己的学生同样的建议。但是,Santos 并没有立刻着手去研究 Hirsch 猜想。2007 年,老数学家Klee去世。同年,Santos开始了一年的学术休假,并访问 UC Davis。在那里,他遇到了研究多面体的专家 De Loera 和 Edward D. Kim。在与他们的交流中,Santos 开始认真思索 Hirsch 猜想,并最终发现了一个反例。当然,Hirsch 猜想的故事并不会因为这一反例而终结,人们会考虑刻画多面体的直径更好的界。因为这一研究无论从任何角度看都是迷人的。
Fuglede 本人首先对一些特殊情况,例如假定 T 是一个格子点集合,证明了该猜想。这一猜想将离散几何、分析等学科紧密结合在一起,且在采样理论中具有很强的背景。因而,吸引了多个不同领域的人的关注。在很长一段时间里,人们认为该猜想离
最终解决还很远 (包括 T. Tao 本人亦在论文中表达过类似的观点)。然而,2003年,借助 Hadamard 矩阵,在一篇8页的文章中,T. Tao 构造了一个反例,表明对于5维及以上情形,Fuglede猜想是错误的 http://arxiv.org/abs/math/0306134。这可能是 Tao 最好的工作之一。随后,人们将这一方法扩展到4维及3维,表明Fuglede 猜想在3,4 维也是错误的。但对于1,2维,Fuglede猜想仍无定论。值得注意的是,在解决这一问题中,Tao主要用了Hadamard 矩阵的结果。Hadamard 矩阵在组合设计及矩阵论等领域备受关注。而关于Hadamrd矩阵的猜想,亦是另外一个值得关注的问题 (http://en.wikipedia.org/wiki/Hadamard_matrix)。