ECCC-Report TR10-120https://eccc.weizmann.ac.il/report/2010/120Comments and Revisions published for TR10-120en-usTue, 27 Jul 2010 17:25:27 +0300
Paper TR10-120
| Lower bounds for designs in symmetric spaces |
Alex Samorodnitsky,
Noa Eidelstein
https://eccc.weizmann.ac.il/report/2010/120A design is a finite set of points in a space on which every "simple" functions averages to its global mean. Illustrative examples of simple functions are low-degree polynomials on the Euclidean sphere or on the Hamming cube.
We prove lower bounds on designs in spaces with a large group of symmetries. These spaces include globally symmetric Riemannian spaces (of any rank) and commutative association schemes with $1$-transitive group of symmetries.
Our bounds are, in general, implicit, relying on estimates on the spectral behavior of certain symmetry-invariant linear operators.
They reduce to the first linear programming bound for designs in globally symmetric Riemannian spaces of rank-$1$ or in distance regular graphs. The proofs are different though, coming from viewpoint of abstract harmonic analysis in symmetric spaces. As a dividend we obtain the following geometric fact: a design is large because a union of "spherical caps" around its points "covers" the whole space.Tue, 27 Jul 2010 17:25:27 +0300https://eccc.weizmann.ac.il/report/2010/120