The lattice handshake number ("nearly kissing" number)?

Question

Update: I'm happy to say that this question has been made essentially obsolete by the breakthrough result of Serge Vlăduţ, who showed that the kissing number is exponentially large: https://arxiv.org/abs/1802.00886 !

Recall that the kissing number in $n$ dimensions is the maximal number $M$ such that there exist $x_1, \ldots, x_M \in \mathbb{R}^n$ with $\|x_i\| = 1$ and $\|x_i - x_j\| \geq 1$ for $i\neq j$. Equivalently, the kissing number is the largest number of non-overlapping spheres of fixed radius that are all tangent to some center sphere with the same radius. It is presumably called the kissing number because the spheres are all "kissing" (i.e., tangent to) the center sphere.

The lattice kissing number is the same thing, but we restrict to the case when the $x_i$ span a lattice. I.e., the lattice kissing number is the maximal number of points of length $\lambda_1(L)$ in a lattice $L \subset \mathbb{R}^n$, where $\lambda_1(L)$ is the length of the shortest non-zero lattice vector. It is a long-standing open problem to find a lattice with kissing number $2^{C n}$ for some positive constant $C$. The current best constructions are quite far from this, giving a lower bound of only $n^{\Theta(\log n)}$. (In contrast, if we don't restrict to lattices, then we know that the kissing number is exponential.)

My question is what happens when we relax the requirement that the spheres kiss. I.e., what if some of them only shake hands? Formally, for $\epsilon > 0$, we call the $\varepsilon$-lattice handshake number the maximal number of non-zero lattice points in a ball of radius $(1+\varepsilon) \cdot \lambda_1(L)$. It is relatively easy to see that this value is at least $(1+\varepsilon)^n$. (This is true in expectation for a random lattice sampled from the Haar measure.) So, it's exponential when $\varepsilon$ is constant, but what happens when $\varepsilon = \varepsilon(n) = o(1)$ is a function of $n$ that goes to zero? Are there known families of lattices that achieve exponential handshake number for such $\varepsilon$?

I have a particular application in mind, but one can imagine how a family of "near-kissing" lattices would be quite useful in general.

Edit: The application is now up on the arXiv, https://arxiv.org/abs/1712.00942 . In particular, we need a family of lattices whose $\varepsilon$-handshake number is at least $(1+\varepsilon+\delta)^n$ for any constants $\varepsilon, \delta > 0$ in order to show a certain quantitative hardness result for the lattice Shortest Vector Problem.

Answer 1

I'm happy to say that this question has been answered by the breakthrough result of Serge Vlăduţ, who showed that the kissing number is exponentially large: https://arxiv.org/abs/1802.00886 !

I.e., there exists a constant $C > 0$ and a sequence of lattices $L_n \subset \mathbb{R}^n$ such that $L_n$ has at least $2^{C n}$ non-zero vectors of exactly minimal length. This is far stronger than what I wanted, which was a sequence with exponentially many vectors of approximately minimal length, and it in particular more than suffices for the application that I mentioned in the question. (It was also a tremendous surprise (at least to me)! I started thinking about the handshake number specifically because I did not expect a result like Vlăduţ's in the near future.)

More specifically, if we define the handshake number as

$$N_{\varepsilon}(n) := \max_{L\, \subset\, \mathbb{R}^n} \;\#\; \{ y \in L \ : \ 0 < \|y\| \leq (1+\varepsilon) \lambda_1(L) \}$$

for positive integer $n$ and $\varepsilon \geq 0$, then Vlăduţ's result immediately yields the correct asymptotics of $N_{\varepsilon}(n)$ for all $\varepsilon$ [1]:

$$\max\{ 2^{\Omega(n)},\ (1+\varepsilon)^n\} \leq N_{\varepsilon}(n) \leq 2^{O(n)} (1+\varepsilon)^n \; .$$

Indeed, the lower bound of $2^{\Omega(n)}$ is Vlăduţ's amazing result. The other bounds are more-or-less trivial: the upper bound follows from a packing argument. The lower bound of $(1+\varepsilon)^n$ is true in expectation for a random lattice in the sense of Siegel (equivalently, this is true in expectation for $\{ z \in \mathbb{Z}^n \ : \ \langle a, x \rangle \equiv 0 \bmod p\}$ with $a \in \mathbb{Z}_p^n$ chosen uniformly at random for a sufficiently large prime $p$).

So, "all" that remains is to settle the constant in the exponent. (The question is also interesting in other norms. It will be interesting to see whether Vlăduţ's result extends to other $\ell_p$ norms, for example.)