Expected value of the length of the shortest non-zero vector in a lattice?

Question

$\DeclareMathOperator\SL{SL}$What is the expected value of the length of the shortest non-zero vector in a (unimodular) lattice? I.e., let $G=\SL_n(\mathbb{R})$ with Haar measure $\mu$, $\Gamma=\SL_n(\mathbb{Z})$, $\lambda_1(\Lambda)$ the length of shortest non-zero vector in the lattice $\Lambda$, and consider the average $$ \frac{1}{\mu(G/\Gamma)}\int_{G/\Gamma}\lambda_1(\Lambda) \ d\mu(\Lambda). $$ For example in dimension two we get something like $$ \frac{3}{\pi}\int_{x=-1/2}^{x=1/2}\int_{y=\sqrt{1-x^2}}^{y=\infty}\frac{1}{\sqrt{y}}\frac{dydx}{y^2}\approx 0.682679. $$ I assume this is hard to calculate or approximate for general $n$ (fundamental domain, meaningful expressions for $\lambda_1$ given some representative basis for $\Lambda$, etc.).

I see things like the "Gaussian heuristic" in lattice crypto papers, but are there any reasonable results on such lattice statistics? Even numerical results (e.g. sample the space, approximate $\lambda_1$ on the samples, average) would be interesting.

Answer 1

This value may be calculated using an "integration formula". Typically ones go by the names of Rodgers' integration formula and Siegal's integration formula. Seungki Kim's thesis On the Shape of a Random High-Dimensional Lattice has some nice introductory material on them. For example, Theorem 1.1 states that Siegal's integration formula

Let $\rho:\mathbb{R}^n\to\mathbb{R}$ be a compactly supported and bounded Borel measurable function. Then

$$ \frac{1}{\mu(G/\Gamma)}\int_{G/\Gamma}\sum_{x\in \Lambda\setminus\{0\}}\rho(x)d\mu(\Lambda) = \int_{\mathbb{R}^n}\rho(x)dx. $$ By choosing $\rho$ appropriately (I believe an indicator function of a ball suffices) you can get an estimate of the average number of lattice points in a ball of radius of your choice. This is a slightly different integral than the one you consider, but can still be used to extract information regarding the behavior of $\lambda_1(\Lambda)$ "on average".

I see things like the "Gaussian heuristic" in lattice crypto papers, but are there any reasonable results on such lattice statistics?

There are two things to say. First, lattice crypto cannot use the above integration formula, as the distribution of lattices that appear in lattice-based crypto (uniformly random $q$-ary lattices, equivalently the image of a uniformly random $q$-ary code under a $q$-ary variant of Construction A) are not sampled from the Haar measure. I believe for large enough parameters one can get things to work, but they are too large for lattice crypto (I remember checking at some point and it was something like $q$-ary lattices for $q = 2^{n^2}$. I believe this result is due to Goldstein and Mayer's On the equidistribution of Hecke points, but won't check now).

Fortunately, cryptographers have worked out some integration formula for the setting of $q$-ary lattices recently (meaning the day before you asked your question), see this. Corollary 2 of that paper appears to be exactly what you want (provided you care about $q$-ary lattices. For Haar-random lattices, use an argument of this type based on Siegal's integration formula instead).

For other resources of this type, you may find Random Lattices: Theory and Practice by Aono, Espitau, and Nguyen to be interesting.