Extremal problem for 2-dimensional lattices

Question

Given a lattice $L$ in a Banach space $(B,\|\;\|)$, one denotes by $\lambda_1(L)$ the least norm of a nonzero element in $L$, and by $\lambda_k$ the least $\lambda$ such that there is a linearly independent set of $k$ elements in $L$ each of which has norm at most $\lambda$. Denote by $L^\ast$ the dual lattice in the dual Banach space, equipped with the norm $\|\;\|^\ast$. Let $b=\dim B$. The product $\lambda_1(L,\|\;\|)\,\lambda_b(L^\ast,\|\;\|^\ast)$ is scale-invariant. For Euclidean lattices, it is not hard to show that the maximal value of $\lambda_1(L)\,\lambda_2(L^\ast)$ for $b=2$ is $\sqrt{\frac43}$ (the Hermite constant in this dimension). What is the maximal value for general lattices in 2-dimensional Banach space? Using the John ellipsoid, one can get an upper bound of $\sqrt{\frac83}$, but is it optimal?

Answer 1

$\def\ZZ{\mathbb{Z}}\def\RR{\mathbb{R}}$The answer is $1.5$.

We'll always take the underlying lattices of $L$ and $L^{\ast}$ to be $\ZZ^2$, and the underlying vector spaces of $B$ and $B^{\ast}$ to be $\RR^2$, with the standard pairing between them. To visualize the norm on $B$, we'll draw the closed ball of radius $1$, which will call $K$.

$K$ will always be a compact, convex, centrally symmetric region and, conversely, given any compact, convex, centrally symmetric region, there is a unique norm with that region as the unit ball. Our optimal solution will turn out to be to take $K=P$, where $P$ is the parallelogram with vertices at $\pm (1.5,0)$ and $\pm (0.75, 1.5)$. The figure below depicts $P$, and the lattice points within $P$.

We will abbreviate $\lambda_2(B,L)$ to $\lambda_2$ and $\lambda_1(B^{\ast}, L^{\ast})$ to $\lambda_1$.

We'll always normalize $\lambda_2=1$. This means that the lattice points inside $K$ span $\RR^2$, but the lattice points inside $(1-\epsilon) K$ for any $K$ only span a $1$ dimensional space. Let's verify that this is true for $P$: The lattice points in $P$ are $(0,0)$, $\pm (1,0)$, $\pm (0,1)$ and $\pm (1,1)$, spanning $\RR^2$, but the lattice points in the interior of $P$ are only $(0,0)$, $\pm (1,0)$, lying on the $x$-axis.

Now, we need to understand how to visualize $\lambda_1(B^{\ast}, L^{\ast})$. For any nonzero $w \in B^{\ast} = \RR^2$, by definition, we have $|w^{\ast}|^{\ast} = \max_{z \in K} \langle w^{\ast} ,z \rangle$. And $\lambda_1(B^{\ast}, L^{\ast}) = \min_{w^{\ast} \in L^{\ast} \setminus (0,0)} |w^{\ast}|^{\ast}$. So, putting it together, $\lambda_1$ is the minimum, over all nonzero integer vectors $(x^{\ast}, y^{\ast})$, of the maximum of $x^{\ast} x + y^{\ast} y$ for $(x,y) \in K$. (Twice this quantity is called the "lattice width" of $K$.)

Let's compute that we get $1.5$ for $K=P$. The inner product with $\pm (0,1)$ is maximized at $\pm (0.75,1.5)$, so $\lambda_1$ is at most $1.5$. Taking lattice vectors of the form $(0,y^{\ast})$ would just give $1.5 |y^{\ast}| \geq 1.5$. If we use a lattice vector $(x^{\ast}, y^{\ast})$ with $x^{\ast} \neq 0$, then the inner product with $\pm (1.5,0)$ is $1.5 |x^{\ast}| \geq 1.5$. So, for every nonzero lattice vector $w^{\ast}$, the maximum of $\langle w^{\ast}, \ \rangle$ on $P$ is at last $1.5$.

We also note that we always have $\lambda_1 \geq 1$ as, for any nonzero lattice vector $w^{\ast}$, the inner product of $w^{\ast}$ with the lattice points in $K$ will be an integer, and this integer can't always be $0$, since the lattice points in $K$ don't lie on a line.

Now, we need to verify that we can't do better than $1.5$ for some other $K$. By our normalization of $\lambda_2(B,L)$ to $1$, all the lattice points in the interior of $K$ lie on a line; we will always take that line to be the $x$-axis.

Claim 1: $K$ cannot contain a lattice point of the form $(x,y)$ for $y \geq 3$, nor can it contain a lattice point of the form $(x,2)$ with $x$ even.

Proof: If $K$ contained $\pm (x,y)$ and $\pm (1,0)$, then it would contain their convex hull, which has area $2y \geq 6$. Then, by Minkowski's theorem, there would be a nonzero lattice point $(x', y')$ in the interior of this hull. This point would have to have $y' \neq 0$, and would lie in the interior of $K$, contradicting our normalization $\lambda_2=1$. Also, if $K$ contains $(x,2)$ with $x$ even, then $(x/2, 1)$ is in the interior of $K$, causing the same contradiction. $\square$

Claim 2: Suppose that $K$ contains a lattice point of the form $(x,2)$ with $x$ odd. Then $\lambda_1= 1$.

Proof: Making an affine transformation, we can normalize $x$ to $1$. Since $K$ contains $(1, 0)$ as well as $(1,2)$, it must contain the midpoint $(1,1)$. Since $(1,1)$ is not on the $x$-axis, it is on the boundary of $K$. So $(1,2)$ and $(1,1)$ are on the boundary of $K$ and $(1,0)$ is in $K$. This means that $K$ lies in the half space $x \leq 1$, showing that $\lambda_1 \leq 1$. $\square$.

So, if we want to get $\lambda_1$ larger than $1$, we can assume that $K$ does not contain any lattice points of the form $(x,y)$ for $y \geq 2$.

Let the line $y=1$ intersect $K$ on the line segment from $(x_1, 1)$ to $(x_2, 1)$.

Claim 3: If there is an integer $j$ with $x_1 < j < x_2$, then $\lambda_1=1$.

Proof: The lattice point $(j,1)$ must be on the boundary of $K$. The support line to $\partial K$ at $(j,1)$ must be the line $y=1$, since any other line would exclude one of $(x_1, 1)$ or $(x_2, 1)$. So $K$ lies in the half space $y \leq 1$, showing that $\lambda_1 \leq 1$. $\square$.

Thus, we can assume that there is no integer between $x_1$ and $x_2$ and hence there is some integer $j$ with $j \leq x_1 \leq x_2 \leq j+1$. Using an affine symmetry, we can assume that $j=0$. Now, replace $K$ by the convex hull of $K \cup \{ \pm (0, 1), \pm (1,1) \}$. This makes $K$ larger, so it potentially increases $\lambda_1$, but it doesn't add any new lattice points to $K$, so $\lambda_2$ stays the same. So we may assume that $\{ \pm (0, 1), \pm (1,1) \}$ are contained in $\partial K$. To summarize, we have now reduced to the case that the lattice points of $K$ are of the form $(0,0)$, $\pm (1,0)$, $\pm (2,0)$, ..., $\pm (k,0)$, $\pm (0,1)$ and $\pm (1,1)$, with $\pm (0,1)$ and $\pm (1,1)$ on $\partial K$.

Now, draw parallel support lines to $K$ passing through $\pm (0,1)$, and another pair of parallel support lines passing through $\pm (1,1)$. We note that the first pair of lines has slope between $0$ and $1$, and the second pair has negative slope. These lines enclose a parallelogram, call it $Q$, containing $K$. Write $(x_1, y_1)$ for the vertex of $Q$ on the lines through $(0,1)$ and $(1,1)$, and $(x_2, y_2)$ for the vertex on the lines through $(0,-1)$ and $(1,1)$; the other two vertices are $(-x_1, -y_1)$ and $(-x_2, -y_2)$. Note, by our computations about slopes, that $(x_1, y_1)$ is in the interior of the triangle $T$ with vertices $(0,1)$, $(1,1)$, $(1,2)$.

We claim that replacing $K$ with $Q$ leaves $\lambda_2$ unchanged and, since $Q$ is larger than $K$, this replacement weakly increases $\lambda_1$. To see that replacing $K$ by $Q$ leaves $\lambda_2$ unchanged, we must think about the lattice points in $Q$. Since $(x_1, y_1)$ is inside the triangle $T$, the whole parallelogram $Q$ lies in the strip $|y|<2$, so there are no new lattice points of the form $(x,y)$ with $|y| \geq 2$, and there are also no new lattice points on the lines $y = \pm 1$. There might be new lattice points on $y=0$, but this won't change $\lambda_2$.

Thus, from now on, we can assume that $K = Q$, a parallelogram with vertices at $\pm (x_1, y_1)$ and $\pm (x_2, y_2)$, with $(1,0)$ on the line segment from $(x_1, y_1)$ to $-(x_2, y_2)$ and $(1,1)$ on the line segment from $(x_1, y_1)$ to $(x_2, y_2)$. We note that $(x_1, y_1)$ determines $(x_2, y_2)$: the point $(x_2, y_2)$ is the intersection of the lines $\overline{(x_1, y_1) (1,1)}$ and $\overline{(-x_1, -y_1) (0,-1)}$. We compute $$(x_2, y_2) =( \frac{2 x_1^2 - x_1 y_1 - x_1}{y_1-1}, -2 x_1 + y_1 ).$$

Now, $\lambda_1$ is the minimum over nonzero lattice vectors $w^{\ast}$ of the maximum, on $Q$, of $\langle w^{\ast}, \ \rangle$. We consider the three values $(0,1)$, $(1,0)$ and $(1,-1)$ for $w^{\ast}$, giving $y_1$, $x_2$ and $x_2-y_2$ respectively. Plugging in the above formulas for $(x_2, y_2)$ in terms of $(x_1, y_1)$, we get $$\min(y_1, \frac{2 x_1^2 -x_1 y_1 - x_1}{y_1-1}, \frac{2 x_1^2-3x_1 y_1 +y_1^2 + x_1-y_1}{y_1-1} )$$ as an upper bound for $\lambda_1$.

Putting all three quantities equal to $1.5$ gives the line $y_1=1.5$ and two conics. In the figure below, I've drawn the triangle $T$ with black edges, and the line and conics in red. Insisting that $\lambda_1 \geq 1.5$ means that the point $(x_1, y_1)$ must lie above the red line and below the two conics. As you can see, the only place that this happens is at the triple intersection $(x_1, y_1) = (0.75, 1.5)$, where $\lambda_1 = 1.5$.