Ellipsoids and lattices: an enclosure problem.

Question

$E \subset {\mathbb R}^2$ is an ellipse of area $1$ centered at the origin that contains no other point with integer coordinates. Is there a matrix $A \in SL(2,{\mathbb Z})$ such that the ellipse $A(E)$ is contained in a disc of radius 10?

Hopefully, this is really easy and it is only my ignorance in "reduction theory" (or other similar techniques) that is at the heart of my difficulties.

More generally, given an ellipsoid $E$ of unit volume in ${\mathbb R}^n$ centered at the origin and containing no other point with integer coordinates, I'm interested in a good upper estimate of the size of the ball in which I can enclose $A(E)$ for some matrix $A \in SL(n,{\mathbb Z})$.

Answer 1

Yes, such $A$ exists, and the radius can be much smaller than $10$; indeed radius $2^{1/2}$ suffices regardless of the area of $E$.

Write the ellipse $A(E)$ as $ax^2+bxy+cy^2 \leq 1$. By reduction theory of binary quadratic forms, we can choose the ${\rm SL}_2({\bf Z})$ transformation $A$ to obtain coefficients satisfying $|b| \leq a \leq c$. But $a \geq 1$ because $(x,y)=(1,0)$ is not in the interior of the ellipse. Hence $$ Q(x,y) \geq a(x^2 - |xy| + y^2) \geq x^2 - |xy| + y^2 \geq \frac12(x^2+y^2) $$ for all $x,y \in \bf R$. Therefore $A(E)$ is contained in the disc $\frac12(x^2+y^2) \leq 1$ of radius $2^{1/2}$, QED.

Equality holds only for $a=|b|=c=1$, in which case the ellipse has area $2\pi/\sqrt{3}$; for an ellipse of area $1$ one can improve the bound slightly using the condition $4ac-b^2=4\pi$, but the best $r$ is still somewhat larger than $1$.

There exist similar bounds in higher dimension $n$, but naturally it gets harder to compute or estimate them as $n$ grows, especially once $n>8$ and the shape of the cone of (say) Minkowski-reduced forms isn't known. (NB Minkowski reduction must give some bound for each $n$, but probably not the best bound once we go far enough beyond $n=2$.)

Answer 2

This is an addition to Noam's answer. In higher dimensions the same type of reasoning---using explicit conditions on the coefficients of reduced quadratic forms---is not feasible. Nevertheless, it is possible to prove the following result:

Theorem. Let $E \subset \mathbb{R^n}$ be an $n$-dimensional ellipsoid centered at the origin and containing no other integer point. There exists a transformation $T \in GL(n,\mathbb{Z})$ such that $T(E)$ is contained in the ball of radius $$ \left(\frac{3}{2}\right)^{(n-1)(n-2)/2} \frac{2^n}{\epsilon_n}\sqrt{n^{n-1}} $$ centered at the origin.

Here $\epsilon_n$ is the volume of the unit ball of dimension $n$.

This theorem follows easily from the following two results:

Theorem. Given a positive-definite $n \times n$ matrix $A = (a_{ij})$, there exists a unimodular integer matrix $U$ such that the matrix $A' = (a'_{ij})$ defined by $A' := U^t A U$ satisfies the following inequality: $$ \left(\frac{2}{3}\right)^{(n-1)(n-2)} \left(\frac{\epsilon_n}{2^n}\right)^2 \leq \frac{\det(A')}{a'_{11} a'_{22} \cdots a'_{nn}} . $$

Theorem. If $A = (a_{ij})$ is a positive-definite $n \times n$ matrix, then for every $x \in \mathbb{R}^n$ we have that $$ \frac{\det(A)}{n^{n-1}a_{11} a_{22} \cdots a_{nn}} \sum a_{ii} x_i^2 \leq \sum a_{ij} x_i x_j \leq n \sum a_{ii} x_i^2 . $$

The first of these two results is an important theorem of Minkowski on the reduction of positive quadratic forms (see Theorem 3 in page 69 of Lekkerkerker), while the second is an improved version of Lemma 4 in page 43 of Siegel's Lectures on Quadratic Forms.