AG Diskrete Mathematik und Mathematische Informatik
Winter Term 2007 / 2008
Prof. Dr. C.-P. Schnorr, Prof. Dr. T. Theobald
Dr. H. Bosse, R. Hartung, C. Riener, A. Scemama, R. Steffens
Semidefinite programming bounds for spherical codes
Lecture by F. Vallentin, CWI Amsterdam,
25. Jan. 08, 14 ct, Raum 612
Abtract:
Good distributions of points on the unit sphere in n-dimensional
Euclidean space are of interest in pure and applied mathematics, e.g.
in coding theory, approximation theory, geometry of numbers,
representation theory. Two measures of goodness are maximality and
optimality. We say that a subset of N points of the unit sphere is a
spherical code with parameters (n,N,t) if any two distinct points have
inner product at most t. Then, a maximal spherical code is one which
maximizes N given t, and an optimal spherical code is one which
minimizes t given N.
Only for very few parameters maximal or optimal spherical codes are
known, e.g. finding a maximal (n,N,1/2) spherical code amounts to the
kissing number problem which is only known for n = 1, 2, 3, 4, 8, 24.
Traditionally, these problems are treated with elementary geometry
and/or with the linear programming bound (LP bound) due to P. Delsarte
which generally gives upper bounds for packing problems in two-point
homogeneous spaces. Recently, a strengthening of the LP bound, namely
the semidefinite programming bound (SDP bound), has been proposed by
A. Schrijver in the context of binary codes.
In the talk I will show the general framework behind SDP bounds. In
particular I will consider the case of the unit sphere, where we get
new upper bounds for the kissing number in dimensions 5, 6, 7, 9, 10,
a unified proof of all the cases where the kissing number is known,
and a proof that the (4,10,1/6) spherical code, which is closely
related to the Petersen graph, is a new optimal spherical code.
This is joint work with Christine Bachoc, based on the papers available from
here.
AG Home