2
$\begingroup$

Let $\Lambda\subset \mathbb{Z}^n$ be an $n-$ dimensional lattice with determinant $d$. We know that the probability that a uniformly random integer vector $x$ is a point in $\Lambda$ is given by $\dfrac{1}{d}$. Denote $\lambda_1$ be the length of the shortest nonzero vector in $\Lambda$ and we know by Minkowski that if the $n-$dimensional ball $B:=B_R(\mathbf{0}$) has the property that $\textbf{vol}(B)\geq 2^n\cdot d$, then $B$ contains a nonzero lattice point in $\Lambda$ and also that $\lambda_1\leq \sqrt{n}d^{1/n}$.

Now, suppose that $\Lambda$ is a uniformly random chosen $n-$dimensional lattice with determinant $d$ and let $\delta\in (0,1)$. I want to get a nice upper bound for $$\Pr[\lambda_1(\Lambda)\leq\delta\sqrt{n}d^{1 / n}]$$, in other words, would like to make it as negligible as it can be with the proper choice of $\delta$.

My attempt is that $\Pr[\lambda_1(\Lambda)\leq\delta\sqrt{n}d^{1 / n}]$ is equal to $\Pr[\text{at least one nonzero vector in } \Lambda \text{ has norm }\leq \delta\sqrt{n}d^{1 / n}]$. If I take $R=\delta\sqrt{n}d^{1 / n}$, then the above probability is equivalent to $\Pr[\exists\mathbf{0}\neq\mathbf{x}\in\Lambda \cap B_R(\mathbf{0})]$. So this seems that I have to use a union bound, that is, $\Pr[\exists\mathbf{0}\neq\mathbf{x}\in\Lambda \cap B_R(\mathbf{0})]\leq \displaystyle\sum \Pr[\mathbf{x}\in\Lambda \cap B_R(\mathbf{0})]$, where the sum is over all nonzero integer vectors $\mathbf{x}\in\mathbb{Z}^n$.

So my questions are:

  1. Is the above inequality that I did using the union bound correct? Are the description of events I made correct?
  2. If the answers to my first question are in the affirmative, how do I calculate $\displaystyle\sum \Pr[\mathbf{x}\in\Lambda \cap B_R(\mathbf{0})]$? Is it equal to $\dfrac{\textbf{vol}(B_R(\mathbf{0}))}{d}$?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.