What The Dual?

The dual lattice is:

Spiritually, it serves a very similar role to the orthogonal complement for linear spaces:

The difference accounts for the “discrete” structure of lattices vs the continuous nature of linear subspaces:

1. Lattices have full rank over $\RR$, hence $\Lperp = \{0\}$ is uninteresting.
2. Lattices require integer combinations and so we need to capture that instead somehow.

Orthogonal Complements

The reason why the orthogonal complement is useful, is that it in some ways captures “everything outside” the original space $\Sspace$, i.e. the “complement space”, everything else.

Because the world is made of everything inside a space, and everything outside of it, with nothing in-between, $\RR^n = \Sspace \oplus \Sperp$, to check that some $\vx \in \RR^n$ is in $\Sspace$, you can check that it has no “component” in $\Sperp$, by “measuring” it with $\langle \cdot, \vv \rangle$ for every $\vv$ in the dual $\Sperp$, i.e. check that it is orthogonal to the orthogonal complement of $\Sspace$:

And instead of checking against all of $\Sperp$ you can check against a basis $\Bp$ for $\Sperp$:

This is advantageous, because, for instance, testing membership of $\Sspace$ otherwise requires Gaussian elimination, which takes cubic time.

Additionally, the complement dual basis also allows checking if you are almost in the space $\Sspace$, by checking that you are almost not in the dual $\Sperp$, i.e. part of $\vx$ which is in $\Sperp$ is small: if $\ip{\vx}{\Bpi{i}}$ is small, relative to $\nrm{\vx}, \nrm{\Bpi{i}}$ then you are almost orthogonal to every vector in the complement space, which means that if you write $\vx$ in the basis $\Bas, \Bp$ (which span the whole space):

Then the coefficients $\vcp$ of $\Bp$ are small, so see this:

If the complement basis $\Bp$ is also orthogonal, i.e. $\langle \Bpi{i}, \Bpi{j} \rangle = 0$ for all $i \neq j$, then:

So if the vectors in $\Bp$ “small” and (almost) orthogonal, then so is $\ve = \Bp \vcp \in \RR^n$, which means $\vx = \Bas \vc + \ve$ lies close to $\Sspace$: by the triangle inequality, $\nrm{\Bp \vcp} \leq \sum_i |c^\perp_i| \cdot \nrm{\Bpi{i}}$.

Remember: this requires $\Bp$ to have short vectors, sounds familiar?

Dual Lattices

The same intuition applies to the dual of a lattice:

Again, you don’t need to check all of $\Ldual$, a basis $\Bd$ for $\Ldual$ suffices:

Again, nice, because it makes checking if you are in a lattice easy. In a vector space, every basis is more/less interchangeable: you can simply rescale the basis elements to make them “short” without it affecting the vector space. That is, famously, not the case for lattices: some bases are nicer than others and you can’t easily make a “bad basis” with:

• Large vectors, very “skewed” vectors.

Into a “nice basis” with:

• Short vectors, almost orthogonal vectors.

The good/bad distinction is exactly the same that decides if the basis $\Bp$ of the orthogonal complement $\Sperp$ able to test “proximity” to the space $\Sspace$ or not: there we also needed a “good basis”, but producing a “good basis” for a linear space is trivially easy because of its continuous nature (which enables Gaussian elimination). Completely analogously, the following is true: $\ip{\vx}{\Bdi{i}}$ is almost an integer (i.e. small in $\RR / \ZZ$) if $\vx$ is close to the lattice $\Lat$ as long as $\Bd$ has short vectors.

To see this, let $\vx \in \Lat$, $\vv \in \Ldual$ and let $\ve$ be “small/short”, then:

Where $k \in \ZZ$.

By Cauchy–Schwarz, $|\ip{\ve}{\vv}| \leq \nrm{\ve} \cdot \nrm{\vv}$. Now $\ve$ is short, i.e. $\vx + \ve$ is close to a lattice point, but when is $\nrm{\vv}$ short for the basis vectors $\vv$ of $\Bd$?

If we have a good basis $\Bas$ for $\Lat$, where the basis elements are almost orthogonal, i.e. $\ip{\Bi{i}}{\Bi{j}}$ is small whenever $i \neq j$, then we can also get a good basis for the dual lattice i.e. every $\nrm{\Bdi{j}}$ is as short as it can be, namely $\approx 1 / \nrm{\Bi{j}}$.

The Dual Basis

The dual lattice for $\Lgen{\Bas}$ has basis $\Bd$ with the property that:

$\implies$: Anything in $\Lgen{\Bd}$ lies in $\Ldual$:

Since every $\vv \in \Lgen{\Bas}$ is an integer combination of $\Bas$ and every $\vx \in \Lgen{\Bd}$ is an integer combination of $\Bd$.

$\impliedby$: Conversely, anything that lies in $\Ldual$ also lies in $\Lgen{\Bd}$:

Let $\vx \in \Ldual$, we can write $\vx$ in the basis $\Bd$ since it has full rank over $\RR^n$.

$$\vx = \sum_i a_i \cdot \Bdi{i}$$

For some $\va \in \RR^n$. We can then consider:

$$\ip{\vx}{\Bi{j}} = \sum_i a_i \cdot \ip{\Bdi{i}}{\Bi{j}} = a_j$$

Since $\vx \in \Ldual$, we have $\forall \vv \in \Lgen{\Bas}. \ip{\vv}{\vx} \in \ZZ$, but $\Bi{j}$ is also clearly in $\Lgen{\Bas}$ so by letting $\vv = \Bi{j}$ we see that $a_j$ is actually an integer and we just wrote $\vx$ as an integer combination of $\Bd$.

Finding $\Bd$

The dual basis $\Bd$ pairs one-to-one with the basis elements in $\Bas$: if you fix $n-1$ vectors $\Bi{1}, \ldots, \Bi{j-1}, \Bi{j+1}, \ldots, \Bi{n}$ in $\RR^n$, and require that a vector $\Bdi{j}$ is orthogonal to all of them, that fixes a unique direction for $\Bdi{j}$, the condition $\langle \Bdi{j}, \Bi{j} \rangle = 1$ then fixes the length of $\Bdi{j}$.

So when is $\Bdi{j}$ short?

Observe that $\langle \Bdi{j}, \Bi{j} \rangle = 1$ does not imply that either $\Bdi{j}$ or $\Bi{j}$ are short, just that $\Bdi{j}$ is short in the $\Bi{j}$ direction, in particular, if they point in very different directions both may be long, while $\langle \Bdi{j}, \Bi{j} \rangle$ stays 1.

If we subtract from each $\Bi{j}$ its projection onto the span of the other $\Bi{i}$:

Then we get $\Bi{j}'$, and we define the “height” of $\Bi{j}$ above the $n-1$ dimensional basis $\Bi{1}, \ldots, \Bi{j-1}, \Bi{j+1}, \ldots, \Bi{n}$ as $h_j = \nrm{\Bi{j}'}$.

Since $\Bdi{j}$ is orthogonal to every $\Bi{i}$ with $i \neq j$, it is orthogonal to their entire span, which leaves exactly one line for it to live on: the line through $\Bi{j}'$. Hence $\Bdi{j} = \lambda \cdot \Bi{j}'$ for some $\lambda \in \RR$, and since $\Bi{j} - \Bi{j}'$ lies in the span of the other basis vectors it is orthogonal to $\Bi{j}'$:

Which pins down $\lambda$, and with it the length of $\Bdi{j}$:

So $\Bdi{j}$ is short exactly when $\Bi{j}$ is almost orthogonal to the other basis vectors: subtracting the projection only ever shortens the vector, so $h_j \leq \nrm{\Bi{j}}$, with equality if and only if $\Bi{j}$ is orthogonal to all the others:

For a fixed lattice, $\det(\Lat) = \left| \det \Bas \right|$ is the same for every basis and $\det(\Lat) \leq \prod_j \nrm{\Bi{j}}$, so the lengths cannot all be made small. $\Bas$ is in turn the dual basis of $\Bd$, so the height of $\Bdi{j}$ above the other dual vectors is $1 / \nrm{\Bi{j}}$.

Written with the basis vectors as columns, the inner products $\ip{\Bdi{i}}{\Bi{j}}$ are the entries of $\Bd^\top \Bas$, so we can write the relation between the dual and the original basis as:

Bonus: Decode with The Dual

Let $\vx = \vv + \ve$ with $\vv \in \Lat$ and $\ve$ short, then by Cauchy–Schwarz:

Where the first term is an integer, in fact a very particular one: for $\vv = \sum_i c_i \cdot \Bi{i}$ with $\vc \in \ZZ^n$:

Which is the $j$-th coefficient of $\vv$ in the basis $\Bas$.

Hence if $\nrm{\ve} < h_j / 2$ for every $j$, then every $\ip{\vx}{\Bdi{j}}$ lies within $1/2$ of an integer and rounding it to the nearest integer recovers $c_j$, i.e. recovers $\vv$ itself. This is Babai’s rounding algorithm, and the radius it is guaranteed to decode is: