2
$\begingroup$

I'm looking for references pertaining to the remark at the bottom of p.18 of Conway-Sloane, "Sphere Packings, Lattices and Groups" (3rd ed), henceforth referred to as "SPLG".

First, given a lattice Lambda in R^n, we define the density of a lattice packing of Lambda to be (cf SPLG p.10): $\Delta = V_n \rho ^n / (\det \Lambda)^{1/2}$

where

$V_n$ = volume of the unit sphere in $R^n$

$\rho$ = half the minimal distance between lattice points ("packing radius of $\Lambda$")

Minkowski (SPLG p.14) gave a non-constructive proof that there exists a lattice in dim n with $\Delta \geq \zeta(n) / 2^{n-1}.$

Finally, at the bottom of p.18 of SPLG the authors notes that

"... there are algorithms that would theoretically enable on to write down generating vectors of such a lattice in bound time."

Can anyone provide references of such algorithms? THANKS!

Improve this question
$\endgroup$
6
  • $\begingroup$ I think the main idea is that when $\Lambda$ chosen randomly from the Siegel measure on lattice of determinant 1, and $\rho$ is such that $V_n\rho^n=\zeta(n)/2^{n-1}$, then the mean number of primitive lattice points (i. e. counting all points that lie on the same line through the origin as only one point) that fall in the ball of radius $2\rho$ is going to be 1. Since the number is obsiously not constant, that means there is a lattice where the number is zero. $\endgroup$
    – Yoav Kallus
    Commented Mar 18, 2021 at 1:46
  • $\begingroup$ So an algorithm that would "theoretically enable one to write down generating vectors of such a lattice" is to discretize the space of lattices of determinant 1 and check each lattice. At a fine enough scale you will get a lattice with packing radius $>\rho$. You might ask for a bound on the discretization level required, but since this algorithm isn't practical anyway, I'm not sure if anyone has bothered to calculate such a bound. $\endgroup$
    – Yoav Kallus
    Commented Mar 18, 2021 at 2:11
  • $\begingroup$ @YoavKallus: Thanks for your comments. If I understand you correctly, you the idea is to look a "finite Riemann sum" analog of the integral in Siegel's proof by taking a finer and finer partitions of SL(n,Z)\SL(n,R), and eventually pick up the desired lattice... ? Are there examples where such calculations are worked out in small dimensions? Thanks! $\endgroup$
    – W Sao
    Commented Mar 18, 2021 at 20:00
  • 1
    $\begingroup$ Not that I know of, but it should be easy enough to set up for your self. Look at "Mean values over the space of lattices" by C. A. Rogers. You can take the generating vectors $(1/L^{1/(n-1)}, 0, 0, \ldots, a_1)$, $(0, 1/L^{1/(n-1)}, 0, \ldots, a_2)$, ..., $(0, \ldots, 1/L^{1/(n-1)}, a_{n-1})$, $(0, \ldots, 0, L)$ where $a_i$ are integers varying from 0 to L-1, and let L be larger and larger until you encounter a satisfactory lattice. $\endgroup$
    – Yoav Kallus
    Commented Mar 18, 2021 at 22:21
  • $\begingroup$ I believe that Hlawka's original proof actually used a finite distribution, so that you don't have to worry about issues of discretizing a continuous distribution. $\endgroup$
    – Noah Stephens-Davidowitz
    Commented Jul 27, 2021 at 17:46

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .