Discrete groups, expanding graphs and invariant measures
Discrete groups, expanding graphs and invariant measures
复制标题
DOI：
10.1007/978-3-0346-0332-4
复制
发表时间：
1994-08
期刊：
影响因子：
--
通讯作者：
A. Lubotzky
中科院分区：
文献类型：
--
作者：
A. Lubotzky
在最后？十五年来，两个看似无关的问题，一个在计算机科学中，另一个在测度论中，却通过表示论和解析数论中惊人相似的技术得到了解决。一个问题是扩展图（“扩展器”）的显式构造。这些是高度连接的稀疏图，其存在可以很容易地证明，但其显式 c 结构结果是一个 diff？邪教任务。由于扩展器充当各种分布式网络的基本构建块，因此显式构造是非常不可能的。另一个问题是由 Ruziewicz 大约七十年前提出并由 Banach [Ba] 研究的。它询问勒贝格测度是否是唯一的？总措施一的有限附加措施，de？ nd 在 n 维球体的勒贝格子集上并且在所有旋转下保持不变。这两个问题似乎在？乍一看，完全不相关。因此，令人惊讶的是，这两个问题都使用相似的方法来解决：最初，半单李群表示论中的 Kazhdan 性质（T）在这两种情况下都被应用，以获得部分结果，后来，这两个问题都使用自守形式理论中（已证明的）拉马努金猜想来解决。表示论和自同构形式与这些问题有任何关系，这一事实令人惊讶，也暗示这两个问题密切相关。
In the last? fteen years two seemingly unrelated problems, one in computer science and the other in measure theory, were solved by amazingly similar techniques from representation theory and from analytic number theory. One problem is the-plicit construction of expanding graphs («expanders»). These are highly connected sparse graphs whose existence can be easily demonstrated but whose explicit c-struction turns out to be a dif? cult task. Since expanders serve as basic building blocks for various distributed networks, an explicit construction is highly des-able. The other problem is one posed by Ruziewicz about seventy years ago and studied by Banach [Ba]. It asks whether the Lebesgue measure is the only? nitely additive measure of total measure one, de? ned on the Lebesgue subsets of the n-dimensional sphere and invariant under all rotations. The two problems seem, at? rst glance, totally unrelated. It is therefore so-what surprising that both problems were solved using similar methods: initially, Kazhdan’s property (T) from representation theory of semi-simple Lie groups was applied in both cases to achieve partial results, and later on, both problems were solved using the (proved) Ramanujan conjecture from the theory of automorphic forms. The fact that representation theory and automorphic forms have anything to do with these problems is a surprise and a hint as well that the two questions are strongly related.