Serge Vlăduţ : Lattices with exponentially large kissing numbers

   (I thank Avi Wigderson for telling me about it.) Serge Vlăduţ just arxived a paper with examples of lattices in R^n such that the kissing number is exponential in n. The existence of such a lattice is a very old open problem and the best record was an example where the kissing number is n^{\log n}. (This is based on a 1959 construction of Barnes and Wall and can be found in the famous book by Conway and Sloane.) Noga Alon found in 1997 collections of spheres so that each one touches subexponentially many others. Vlăduţ’s result is very exciting!

A crucial step was a result by Ashikhmin,  Barg, and Vlăduţ from 2001 showing that certain algebraic-geometry binary linear codes have exponentially many minimal weight vectors. (This result disproved a conjecture by Nati Linial and me.) This follows by applying in a very clever way early 80s constructions going back to Bos, Conway, Sloane and Barnes and Sloane, and this requires some subtle selection of the AG-codes that can be used. To quote the author: “In order to apply Constuctions D and E we need specific good curves (the curves in the Garcia Stichtenoth towers do not perfectly match our construction) and some Drinfeld modular curves  perfectly suit our purposes.”

These lines of ideas and appropriate AG-codes look to me the most promising avenue towards exponential lower bound for the Borsuk problem. (See, e.g.,  this paper and this post) We need for that purpose AG codes X where the maximum weight occurs exponentially often (this need not be difficult) and that every subset of vectors that misses the maximum distance is exponentially smaller than |X|.


This entry was posted in Combinatorics, Geometry and tagged . Bookmark the permalink.

4 Responses to Serge Vlăduţ : Lattices with exponentially large kissing numbers

  1. Gil Kalai says:

    A long time dream regarding algebraic geometry codes is to use them for finding exponentially better binary codes compared to the Gilbert-Varshamov bound (this is known for a large alphabet), and even exponentially better sphere packing compared to the Minkowski 1905 lower bound.

  2. Pingback: Test your intuition 33: Why is the density of any packing of unit balls decay exponentially with the dimension? | Combinatorics and more

  3. apgoucher says:

    Reblogged this on Complex Projective 4-Space and commented:
    Conway and Sloane’s excellent tome, Sphere Packings, Lattices and Groups, is now due a fourth edition. Maryna Viakovska’s proofs of optimality of the E8 and Leech lattices should go in the fourth edition as well…

  4. Pingback: Coloring Problems for Arrangements of Circles (and Pseudocircles) | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s