# Extremal problem for 2-dimensional lattices

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?

• I can improve the lower bound from $\sqrt{\tfrac{4}{3}} \approx 1.155$ to $\tfrac{4}{3} \approx 1.333$. Identify $B$ and $B^{\ast}$ with $\mathbb{R}^2$ and identify $L$ and $L^{\ast}$ with $\mathbb{Z}^2$. Let the norm on $B$ have unit ball the hexagon with vertices $\pm (1/2,1)$, $\pm (1, 1/2)$ and $\pm (1/2, -1/2)$. The unit ball in $B^{\ast}$ is the hexagon with vertices $\pm (2/3, 2/3)$, $\pm (-2/3,4/3)$ and $\pm (4/3,-2/3)$. I get that $\lambda_1(L) = \tfrac{4}{3}$ and $\lambda_2(L^{\ast}) = 1$. Jun 22, 2023 at 14:41
• I can achieve $1.5$. Identify $L$ and $L^{\ast}$ with $\mathbb{Z}^2$ and let $B$ have unit ball the parallelogram with vertices $\pm (1.5,0)$ and $\pm (0.75,1.5)$. Note that the lattice points inside this parallelogram are $(0,0)$, $(\pm 1,0)$, $(0,\pm 1)$ and $\pm (1,1)$ but that the lattice points in the strict interior are only $(0,0)$, $(\pm 1,0)$, showing that $\lambda_2(B)=1$. I believe that $\lambda_1(B^{\ast}) = 1.5$. Furthermore, I think I can prove this is optimal. I'll try to write up my thoughts over the weekend. Jun 24, 2023 at 2:37

$$\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$$.

• Awsome! Here your convention is to work with $\lambda_2(L)\lambda_1(L^\ast)$. How big is the difference between $\lambda_1(L)$ and $\lambda_2(L)$ for this extremal lattice? Jun 27, 2023 at 8:31
• For this particular lattice, $\lambda_1(L) = 2/3$ (because shrinking $P$ by $2/3$ still includes $\pm (1,0)$, so $\lambda_1(L) \lambda_1(L^{\ast}) = 1$. I suspect that the optimal value of $\lambda_1(L) \lambda_1(L^{\ast})$ is $4/3$, using the hexagon I posted as a comment earlier. Jun 27, 2023 at 13:35
• Wait a minute, but Mahler seems to say otherwise: $\lambda_1(L)\lambda_1(L^\ast)$ reaches $\sqrt2$. A colleague sent me an explanation of how this follows from Mahler's '48 paper. Jun 27, 2023 at 13:39
• Okay, I guess I'm wrong, I'm not claiming to have a proof for the $\lambda_1(L) \lambda_1(L^{\ast})$ optimum. I'd be curious to see the example that achieves $\sqrt{2}$. Jun 27, 2023 at 13:50
• I sent you Averkov's explanation via email. Jun 27, 2023 at 13:58