7
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Jun 22, 2023 at 14:41
  • $\begingroup$ 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. $\endgroup$ Jun 24, 2023 at 2:37

1 Answer 1

3
+50
$\begingroup$

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

enter image description here

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

enter image description here

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Jun 27, 2023 at 8:31
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2023 at 13:35
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2023 at 13:39
  • $\begingroup$ 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}$. $\endgroup$ Jun 27, 2023 at 13:50
  • $\begingroup$ I sent you Averkov's explanation via email. $\endgroup$ Jun 27, 2023 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.