Skip to main content
added 224 characters in body
Source Link

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.

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.

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.

added 349 characters in body
Source Link

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.

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.

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.

Source Link

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

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.