1
$\begingroup$

We consider the space of $n$-dimensional Euclidean lattices. Define the $i$-th successive minimum of a lattice $\Lambda$ as $ \lambda_i(L) := \min \left\{ r \in \mathbb{R}_{>0} \mid \dim_{\mathbb{R}} \operatorname{span}_{\mathbb{R}} \big( B(r) \cap L \big) \geq i \right\} , 1 \leq i \leq n.$

By considering a basis $\{a, b\}$ of $L$ with $||a||= \lambda_1(L), ||b||= \lambda_2(L),$ and the angle between $a,b$ is in $[\pi/3, \pi/2]$, it is easy to show that, in $2$ dimensions (and up to scaling and rotation), it has a fundamental set(a set of lattice representatives) $F \subseteq \mathbb{R}^2,$ defined by $F=\{(x,y) \in \mathbb{R}^2 \ | \ x^2+y^2 \geq 1, 0 \leq x \leq 1/2 \}.$

My question is, is there a similar characterisation of the fundamental set in larger dimensions? Maybe the problem gets too hard in dim. $4$ and above, but I was hoping that there would already be some existing characterisation in $3$ dimensions.

$\endgroup$
3
  • 1
    $\begingroup$ Are you assuming that your n-dimensional lattice 𝚲 is a subgroup of ℝ^n ? $\endgroup$ Commented Feb 12 at 15:02
  • $\begingroup$ @DanielAsimov: I think he is using the term lattice in the sense of a Z-submodule of $R^n$, not in the sense of discrete subgroup of cofinite volume. en.wikipedia.org/wiki/Lattice?wprov=sfti1#Mathematics $\endgroup$ Commented Feb 13 at 4:34
  • $\begingroup$ Yes I mean $\mathbb{Z}$-submodule (which is the same as additive subgroup) of $\mathbb{R}^n$, however euclidean lattices turn out to be exactly the discrete subgroups of finite covolume. $\endgroup$ Commented Feb 13 at 9:17

1 Answer 1

3
$\begingroup$

Even for dimension $3$, a fundamental domain in the sense you describe will be quite hard to work with (Edit: writing it down actually isn't too bad, see the end of the answer). It's often simpler instead to to classify lattices not by a choice of basis but rather by their Gram matrix, namely the (symmetric, positive-definite) matrix of pairwise dot products. This information uniquely characterizes a basis up to orthogonal transformation, so you can recover a lattice with basis (up to rotation/reflection) from a Gram matrix.

To illustrate the usefulness of this approach, suppose we take $(x,y)$ in the set $F$ you defined above. The lattice with basis $(1,0),(x,y)$ will have a Gram matrix $\begin{pmatrix} 1 & x \\ x & x^2+y^2\end{pmatrix}$. From this we can see that for lattices coming from $F$ (and their scalar multiples), their Gram matrices $\begin{pmatrix} a & b \\ b & c\end{pmatrix}$ satisfy certain linear inequalities in the entries: $0\leq 2b\leq a\leq c$. Contrast that with the quadratic constraints on the basis vectors themselves.

One generalization of this notion to arbitrary dimension is Minkowski reduction (see e.g. Donaldson's Minkowski Reduction of Integral Matrices section 2.4). Every lattice has a basis whose Gram matrix is Minkowski-reduced, and while the basis itself will not be unique (automorphisms of the lattice preserve the Gram matrix), if there exists a basis for which all the inequalities are strict, then the Gram matrix is uniquely determined up to replacing some basis vectors $b_i$ with $-b_i$. So the space of Minkowski-reduced Gram matrices gives a complete classification of lattices in $\mathbb{R}^n$ modulo orthogonal transformation, up to negating basis vectors and some issues involving the boundaries of the region.

Unfortunately, even writing down the set of all necessary inequalities is hard in large dimensions. But it is doable in small dimensions. Let $A=\begin{pmatrix} a_{11}&\cdots& a_{1n}\\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{pmatrix}$ be a Gram matrix.

Let $n\leq 4$. Then $A$ is the Gram matrix of a Minkowski-reduced basis if and only if the following conditions all hold: for each $k=1,\ldots n$ and each vector $\mathbf{x}\in \{-1,0,1\}^n$, if at least one of $x_k,\ldots,x_n$ is nonzero, then we have $\mathbf{x}^T A\mathbf{x}\geq a_{kk}$.

For instance, say $n=2$: from $k=1$ and $\mathbf{x}=(0,1)$ we get the condition $a_{22}\geq a_{11}$, and from $k=2$ and $\mathbf{x}=(1,\pm 1)$ we get the condition $a_{11}\pm 2a_{12}+a_{22}\geq a_{22}$, which implies $|2a_{12}|\leq a_{11}$. (All other $k$ and $\mathbf{x}$ end up giving redundant conditions.) By replacing $b_2$ with $-b_2$ if necessary, we can ensure $a_{12}\geq 0$, and so this exactly recovers the conditions described above.

If we do the same for $n=3$, we obtain the conditions $$0<a_{11}\leq a_{22} \leq a_{33},\qquad |2a_{23}|\leq a_{22},\qquad |2a_{12}|,\, |2a_{13}|\leq a_{11},$$ $$a_{12} +a_{13}-a_{23},\, a_{12} -a_{13}+a_{23},\, -a_{12} +a_{13}+a_{23},\, -a_{12} -a_{13}-a_{23} \leq\frac12(a_{11}+a_{22})$$ (see e.g. Rousseau's On Gauss's proof of Seeber's Theorem equations (1)-(3)). As before, we can negate $b_2$ and/or $b_3$ if necessary to ensure $a_{12},\,a_{23}\geq 0$; these inequalities then define a fundamental domain for the space of lattices.

Edit: Going from here to a region expressed in terms of basis vectors is straightforward. First we have to account for scaling and rotation: we can always transform the first basis vector to $(1,0,0)$, and then by rotation around the $(1,0,0)$ axis we can make the second basis vector take the form $(v,w,0)$. The third basis vector then has the form $(x,y,z)$, and we can compute the Gram matrix $$A=\begin{pmatrix} 1 & v & x \\ v & v^2 + w^2 & v x + w y \\ x & v x + w y & x^2 + y^2 + z^2 \end{pmatrix}.$$ Then we just need to ensure this basis is Minkowski-reduced. In other words, a fundamental domain for the space of lattices in $\mathbb{R}^3$ is given by $(v,w,x,y,z)\in\mathbb{R}^5$ satisfying the following conditions: $$1\leq v^2+w^2 \leq x^2+y^2+z^2,$$ $$0\leq 2(vx+wy)\leq v^2+w^2,\qquad 0\leq 2v\leq 1,\qquad -1\leq 2x\leq 1,$$ \begin{align*} v+x-(v x + w y),\, v -x+(v x + w y) &\leq\frac12(v^2+w^2+1),\\ -v +x+(v x + w y),\, -v-x-(v x + w y) &\leq\frac12(v^2+w^2+1). \end{align*} The fact that this fundamental domain is 5-dimensional means that unfortunately it doesn't have a nice "picture" like the space of 2-d lattices does. In general, the fundamental domain for lattices in $\mathbb{R}^n$ modulo scaling and orthogonal transformations will have dimension $\binom{n+1}{2}-1$. Even though this region does exist, in practice it's much easier to work with the Gram matrices because there are a lot more tools available to work with linear inequalities than with nonlinear inequalities.

$\endgroup$
5
  • $\begingroup$ Thanks, I wasn't exactly asking for a characterisation in terms of successive minima or sth, but rather any useful way to describe the fundamental set, in the same way you did. Though, with my limited experience, I find it a bit confusing that I cannot find any sort of result on the fundamental set in higher dimensions (or even an effort to characterise the dimension 3 case in the "messy" way, in case it would be illuminating in any way); unless the problem is completely intractable, it seems to me that it could be useful in some lattice contexts. $\endgroup$ Commented Feb 12 at 14:27
  • 1
    $\begingroup$ It actually isn't too hard to characterize the dimension 3 case even in terms of basis vectors - I just edited my answer to explain how (and also to mention why people don't typically use this in practice even if it is available). $\endgroup$ Commented Feb 12 at 18:07
  • 1
    $\begingroup$ It's also worth mentioning that the complexity of Minkowski reduction explodes as the dimension increases: even just for n=7 the Minkowski reduced locus is defined by over 90,000 inequalities (see here for example). $\endgroup$ Commented Feb 12 at 18:10
  • 2
    $\begingroup$ Just a remark: the shortest length vectors realizing $\lambda_i(L), i=1,\ldots, n$ may not be a basis for the lattice. So one could potentially describe a different fundamental domain of vectors realizing the successive minima (and their Gram matrix). See mathscinet.ams.org/mathscinet/article?mr=2478088 $\endgroup$ Commented Feb 13 at 5:24
  • $\begingroup$ @JonathanLove thank you so much for the edit! $\endgroup$ Commented Feb 13 at 9:20

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.