Don't worry! You can be part of the hip crowd at the next cocktail party in just three easy steps!

First, I will tell you what a lattice is. It is actually really easy.

Second, we will prove a tiny fact about lattices so that those poor neurons that did all the work in the first step have some friends.

Third, nothing. There isn't even a third step. That's how easy it is!

So, let's tackle the first step. What, actually, is a lattice?

The answer could not be easier. It is simply a grid of points. Like this:

The formal definition is just as simple:

Given $n$ linearly independent vectors $b_1, b_2, \ldots, b_n \in \mathbb{R}^m$, the lattice generated by them is defined as

\[

\mathcal{L}(b_1, b_2, \ldots, b_n) = \left\{ \sum x_i b_i \middle| x_i \in \mathbb{Z} \right\}.

\]

We can add those so called basis vectors $b_i$ to our diagram and will readily see how each point is constructed.

And now you already know what a lattice is! In the next step we will talk about some more definitions and show the proof of a theorem.

We will be discussing something related to the question of what the length of the shortest non-zero vector in a given lattice $\mathcal{L}$ is.

Definition:

$\lambda_1(\mathcal{L})$ is the length of the shortest non-zero vector in $\mathcal{L}$. We use the euclidean norm for the definition of length.And we also need the volume of a lattice which we are not going to define formally we will just take it to be the volume of that $n$ dimensional parallelogram in the picture:

Now we can already prove

*Blichfeld's Theorem*! It makes a statement about where we can find a lattice point and roughly goes as follows:

For a lattice $\mathcal{L}\subseteq \mathbb{R}^n$ and a set $S \subseteq \mathbb{R}^n$ where the volume of $S$ is bigger than the volume of the lattice there exist two nonequal points $z_1, z_2 \in S$ such that $z_1 - z_2 \in \mathcal{L}$.And here is the idea of the proof in a graphical way! First we simply draw an example for the set $S$ in blue:

Now we cut up our set and move all the parts into our first parallelogram!

Now we will use a little trick to expand this result and make a statement about an actual point from the set being on the lattice not just the difference of two points!

What we will show is called

*Minkowski's Convex Body Theorem*and it states roughly

Let $\mathcal{L}$ be a lattice. Then any centrally-symmetric convex set $S$, with volume bigger than $2^n$ times the volume of the lattice contains a nonzero lattice point.So after this we will know such a set it will contain a lattice point and using a simple sphere as the set allows us to put a bound on $\lambda_1(\mathcal{L})$.

Let's get to it then!

First we blow up our lattice to twice its size along every dimension!

Now we add our centrally-symmetric convex set $S$. Again in blue.

And because we picked the volume of $S$ to be bigger than $2^n$ times the volume of the lattice we still get the colliding points from the last theorem EVEN in the double size lattice!

But since our set $S$ is symmetric about the origin if $z_2 \in S$ it follows that $-z_2 \in S$ and because it is convex $z_1, -z_2 \in S$ implies $\frac{z_1 - z_2}{2} \in S$. And because we've double the size of the lattice and $z_1 - z_2$ is on the bigger lattice it follows that $\frac{z_1 - z_2}{2} \in \mathcal{L}$ and we have shown that a point in our set is also in the lattice.

You can see it quite clearly in the next picture.

As already stated above if we use a simple sphere for this set we can give a bound on $\lambda_1(\mathcal{L})$ based on the volume of $\mathcal{L}$. It is known as

*Minkowski's First Theorem*and states:

\[Isn't that great?!

\lambda_1(\mathcal{L}) \leq \sqrt{n}(vol(\mathcal{L})^{1/n}.

\]

If you have now completely fallen in love with lattices but would appreciate real math instead of pictures, worry not!

You will find steps 3 - 14 on Oded Regev's course website! Enjoy!

And in case you accidentally run into him at a conference here is the picture from his website so you don't miss the opportunity to say hello.

## No comments:

## Post a Comment