Editing Dual lattice (section)

==Transference theorems==

Each <math display="inline"> f \in L^* \setminus \{0\} </math> partitions <math display="inline"> L </math> according to the level sets corresponding to each of the integer values. Smaller choices of <math display="inline"> f </math> produce level sets with more distance between them; in particular, the distance between the layers is <math display="inline"> 1 / ||f|| </math>. <!--- picture would be great here. ---> Reasoning this way, one can show that finding small vectors in <math display="inline"> L^* </math> provides a lower bound on the largest size of non-overlapping spheres that can be placed around points of <math display="inline"> L </math>. In general, theorems relating the properties of a lattice with properties of its dual are known as transference theorems. In this section we explain some of them, along with some consequences for complexity theory.

We recall some terminology: For a lattice  <math display = "inline"> L</math> , let  <math display = "inline"> \lambda_i(L) </math> denote the smallest radius ball that contains a set of  <math display = "inline"> i </math> linearly independent vectors of  <math display = "inline"> L</math>. For instance,  <math display = "inline"> \lambda_1(L) </math> is the length of the shortest vector of  <math display = "inline"> L</math>. Let <math display = "inline"> \mu(L) = \text{max}_{x \in \mathbb{R}^n } d(x, L) </math> denote the covering radius of <math display = "inline"> L </math>.

In this notation, the lower bound mentioned in the introduction to this section states that <math display = "inline">  \mu(L) \geq \frac{1}{2 \lambda_1(L^*)} </math>.

{{math theorem 
|'''Theorem (Banaszczyk)'''<ref name="Banaszczyk 1993 pp. 625–635">{{cite journal | last=Banaszczyk | first=W. | title=New bounds in some transference theorems in the geometry of numbers | journal=Mathematische Annalen | publisher=Springer Science and Business Media LLC | volume=296 | issue=1 | year=1993 | issn=0025-5831 | doi=10.1007/bf01445125 | pages=625–635| s2cid=13921988 }}</ref> 
|For a lattice <math display = "inline"> L</math>:
*:<math> 1 \leq 2 \lambda_1(L) \mu(L^*) \leq n </math>
*:<math> 1 \leq \lambda_i(L) \lambda_{n - i + 1}(L^*) \leq n </math>
}}
There always an efficiently checkable certificate for the claim that a lattice has a short nonzero vector, namely the vector itself. An important corollary of Banaszcyk's transference theorem is that <math display="inline"> \lambda_1(L) \geq \frac{1}{\lambda_n(L^*)} </math>, which implies that to prove that a lattice has no short vectors, one can show a basis for the dual lattice consisting of short vectors. Using these ideas one can show that approximating the shortest vector of a lattice to within a factor of n (the [[Lattice problem#GapSVP|<math display = "inline"> \text{GAPSVP}_n </math> problem]]) is in <math display = "inline"> \text{NP} \cap \text{coNP} </math>.<ref>{{cite journal
 | last1 = Cai | first1 = Jin-Yi
 | last2 = Nerurkar | first2 = Ajay
 | doi = 10.1016/S0020-0190(00)00123-X
 | issue = 1-2
 | journal = Information Processing Letters
 | mr = 1797563
 | pages = 61–66
 | title = A note on the non-NP-hardness of approximate lattice problems under general Cook reductions
 | volume = 76
 | year = 2000}}</ref>

Other transference theorems:
* The relationship <math display = "inline"> \lambda_1(L) \lambda_1(L^*) \leq n </math> follows from [[Minkowski's theorem#Bounding the shortest vector|Minkowski's bound on the shortest vector]]; that is, <math display = "inline"> \lambda_1(L) \leq \sqrt{n} (\text{det}(L)^{1/n}) </math>, and <math display = "inline"> \lambda_1(L^*) \leq \sqrt{n} (\text{det}(L^*)^{1/n}) </math>, from which the claim follows since <math display = "inline"> \text{det}(L) = \frac{1}{\text{det}(L^*)} </math>.