On packing of Minkowski balls. I

Nikolaj M. Glazunov

Glushkov Institute of Cybernetics NASU, Kiev,

Institute of Mathematics and Informatics Bulgarian Academy of Sciences

Email<EMAIL_ADDRESS>

Abstract.

We investigate lattice packings of Minkowski balls. By the results of the
proof of Minkowski conjecture about the critical determinant we devide
Minkowski balls on 3 classes: Minkowski balls, Davis balls and Chebyshev-Cohn
balls. We investigate lattice packings of these balls on planes with varieng
Minkowski metric and search among these packings the optimal packings. In this
paper we prove that the optimal lattice packing of the Minkowski, Davis, and
Chebyshev-Cohn balls is realized with respect to the sublattices of index two
of the critical lattices of corresponding balls.

Keywords: lattice packing, Minkowski ball, Minkowski metric, critical lattice,
optimal lattice packing.

2020 Mathematics Subject Classification: 11H06, 52C05

Thanks. The author is deeply grateful to the Bulgarian Academy of Sciences,
the Institute of Mathematics and Informatics of the Bulgarian Academy of
Sciences, Professor P. Boyvalenkov for their support. The author was supported
by Simons grant 992227.

##  1 Introduction

A system of equal balls in $n$-dimensional space is said to form a packing, if
no two balls of the system have any inner points in common.

Lately the remarkable results in resolving the problem of optimal packing of
balls in $8$ and $24$-dimensional real Euclidean spaces have been obtained [1,
2].

In this research, acknowledged by the Fields medal, optimal packings are
constructed on lattices.

Our considerations connect with Minkowski conjecture [3, 5, 6, 7, 8, 12, 16,
17, 18] and use results of its proof. Corresponding results and conjectures is
most simply stated in terms of geometric lattices and critical lattices [4, 3,
9, 10]. The last are important partial case of geometric lattices. We
investigate lattice packings of Minkowski balls, Davis balls and Chebyshev-
Cohn balls on planes with varying Minkowski metric and search among these
packings the optimal packings. The packing problem is studied on classes of
lattices related to the problem of the theory of Diophantine approximations
considered by H. Minkowski [3] for the case of the plane. For some other
selected problems and results of the theory Diophantine approximations see for
instance [13] and references therein. The naming of balls is connecting with
results of investigating of Minkowski conjecture on critical determinant and
its justification is given below. In this paper we prove that the optimal
lattice packing of the Minkowski, Davis, and Chebyshev-Cohn balls is realized
with respect to the sublattices of index two of the critical lattices of
corresponding balls.

##  2 Minkowski conjecture, its proof and Minkowski balls

Let

$|\alpha x+\beta y|^{p}+|\gamma x+\delta y|^{p}\leq
c\cdot|\det(\alpha\delta-\beta\gamma)|^{p/2},$

be a diophantine inequality defined for a given real $p>1$; hear
$\alpha,\beta,\gamma,\delta$ are real numbers with
$\alpha\delta-\beta\gamma\neq 0.$

H. Minkowski in his monograph [3] raise the question about minimum constant
$c$ such that the inequality has integer solution other than origin. Minkowski
with the help of his theorem on convex body has found a sufficient condition
for the solvability of Diophantine inequalities in integers not both zero:

$c={\kappa_{p}}^{p},\kappa_{p}=\frac{{\Gamma(1+\frac{2}{p})}^{1/2}}{{\Gamma(1+\frac{1}{p})}}.$

But this result is not optimal, and Minkowski also raised the issue of not
improving constant $c$. For this purpose Minkowski has proposed to use the
critical determinant.

Recall the definitions [9].

Let $\mathcal{R}$ be a set and $\Lambda$ be a lattice with base

$\\{a_{1},\ldots,a_{n}\\}$

in ${\mathbb{R}}^{n}.$

A lattice $\Lambda$ is admissible for body $\mathcal{R}$
(${\mathcal{R}}-$admissible) if ${\mathcal{R}}\bigcap\Lambda=\emptyset$ or
$0.$

Let $\overline{\mathcal{R}}$ be the closure of ${\mathcal{R}}$. A lattice
$\Lambda$ is strictly admissible for $\overline{\mathcal{R}}$ (
$\overline{\mathcal{R}}-$strictly admissible) if
$\overline{\mathcal{R}}\bigcap\Lambda=\emptyset$ or $0.$

Let

$d(\Lambda)=|\det(a_{1},\ldots,a_{n})|$

be the determinant of $\Lambda.$

The infimum $\Delta(\mathcal{R})$ of determinants of all lattices admissible
for $\mathcal{R}$ is called the critical determinant of $\mathcal{R};$ if
there is no $\mathcal{R}-$admissible lattices then puts
$\Delta(\mathcal{R})=\infty.$

A lattice $\Lambda$ is critical if $d(\Lambda)=\Delta(\mathcal{R}).$

For the given 2-dimension region $D_{p}\subset{\mathbb{R}}^{2}=(x,y),\ p\geq
1$ :

$|x|^{p}+|y|^{p}<1,$

let $\Delta(D_{p})$ be the critical determinant of the region.

All determinants of admissible lattices of this domain that have three pairs
of points on the boundary of this domain are parametrized by the Minkowski-
Cohn moduli space of the form

$\Delta(p,\sigma)=(\tau+\sigma)(1+\tau^{p})^{-\frac{1}{p}}(1+\sigma^{p})^{-\frac{1}{p}},$
(1)

in the domain

${\mathcal{M}}:\;\infty>p>1,\;1\leq\sigma\leq\sigma_{p}=(2^{p}-1)^{\frac{1}{p}},$

of the $\\{p,\sigma\\}$-plane, where $\sigma$ is some real parameter [7, 16,
17, 18, 19].

In notations [18] next result have proved:

###### Theorem 1

[18]

$\Delta(D_{p})=\left\\{\begin{array}[]{lc}\Delta(p,1),\;1\leq p\leq 2,\;p\geq
p_{0},\\\ \Delta(p,\sigma_{p}),\;2\leq p\leq p_{0};\\\ \end{array}\right.$

here $p_{0}$ is a real number that is defined unique by conditions
$\Delta(p_{0},\sigma_{p})=\Delta(p_{0},1),\;2,57<p_{0}<2,58,\;p_{0}\approx
2,5725$.

###### Remark 1

We will call $p_{0}$ the Davis constant.

###### Corollary 1

${\kappa_{p}}={\Delta(D_{p})}^{-\frac{p}{2}}.$

From Theorem (1) in notations [18, 19] we deduce the following corollary:

###### Corollary 2

([18, 19])

${\Delta^{(0)}_{p}}=\Delta(p,{\sigma_{p}})=\frac{1}{2}{\sigma}_{p},\;{\sigma}_{p}=(2^{p}-1)^{1/p},$
${\Delta^{(1)}_{p}}=\Delta(p,1)=4^{-\frac{1}{p}}\frac{1+\tau_{p}}{1-\tau_{p}},\;2(1-\tau_{p})^{p}=1+\tau_{p}^{p},\;0\leq\tau_{p}<1.$

For their critical lattices respectively
$\Lambda_{p}^{(0)},\;\Lambda_{p}^{(1)}$ next conditions satisfy:
$\Lambda_{p}^{(0)}$ and $\Lambda_{p}^{(1)}$ are two $D_{p}$-admissible
lattices each of which contains three pairs of points on the boundary of
$D_{p}$ with the property that

$(1,0)\in\Lambda_{p}^{(0)},\;(-2^{-1/p},2^{-1/p})\in\Lambda_{p}^{(1)},$

(under these conditions the lattices are uniquely defined).

##  3 Minkowski balls and the density of the packing of $2$-dimensional
Minkowski balls

Let $p_{0}\in{\mathbb{R}}$ be the Davis constant such that $2,57<p_{0}<2,58$.

We consider balls of the form

$D_{p}:\;|x|^{p}+|y|^{p}\leq 1,\;p\geq 1,$

and call balls with the conditions

$|x|^{p}+|y|^{p}\leq 1,\;2>p>1,$

the Minkowski balls in two dimension and correspondingly the circles with the
condition

$|x|^{p}+|y|^{p}=1,\;2>p>1$

the Minkowski circles in two dimension.

Limiting Minkowski circle in two dimension: $|x|+|y|=1$

Davis balls in two dimension: $|x|^{p}+|y|^{p}\leq 1$ for $p_{0}>p\geq 2$

Davis circles in two dimension: $|x|^{p}+|y|^{p}=1$ for $p_{0}>p\geq 2$

Chebyshev-Cohn balls in two dimension: $|x|^{p}+|y|^{p}\leq 1$ for $p\geq
p_{0}$

Chebyshev-Cohn circles in two dimension: $|x|^{p}+|y|^{p}=1$ for $p\geq p_{0}$

Limiting Chebyshev-(Cohn) ball in two dimension:

$||x,y||_{\infty}=\max(|x|,|y|).$

Recall the definition of a packing lattice [1, 2, 9, 10]. We will give it for
$n$-dimensional Minkowski balls $D_{p}^{n}$ in ${\mathbb{R}}^{n}$.

###### Definition 1

Let $\Lambda$ be a full lattice in ${\mathbb{R}}^{n}$ and
$a\in{\mathbb{R}}^{n}$. In the case if it is occurs that no two of balls
$\\{D_{p}^{n}+b,b\in\Lambda+a\\}$ have inner points in common, the collection
of balls $\\{D_{p}^{n}+b,b\in\Lambda+a\\}$ is called a
$(D_{p}^{n},\Lambda)$-packing, and $\Lambda$ is called a packing lattice of
$D_{p}^{n}$.

Recall also that if $\alpha\in{\mathbb{R}}$ and $D_{p}^{n}$ is a ball than
$\alpha D_{p}^{n}$ is the set of points $\alpha x,x\in D_{p}^{n}$.

In some cases we will consider interiors of balls $D_{p}=D_{p}^{2}$ (open
balls) which we will denoted as $ID_{p}$.

From the considerations of Minkowski and other authors [3, 4, 9, 10, 19], the
following statements can be deduced (for the sake of completeness, we present
the proof of Proposition 1).

Denote by $V(D_{p})$ the volume (area) of $D_{p}$.

###### Proposition 1

[9, 10]. A lattice $\Lambda$ is a packing lattice of $D_{p}$ if and only if it
is admissible lattice for $2D_{p}$.

Proof (contrary proof). First, note that one can take an open ball $ID_{p}$
and use the notion of strict admissibility. Suppose that $\Lambda$ is not
strictly admissible for $2ID_{p}$. Then $2ID_{p}$ contains a point $a\neq 0$
of $\Lambda$. Then the two balls $ID_{p}$ and $ID_{p}+a$ contain the point
$\frac{1}{2}a$ in common. So $\Lambda$ is not a packing lattice of $D_{p}$.
Suppose now that $\Lambda$ is not a packing lattice of $D_{p}$. Then there
exist two distinct points $b_{1},b_{2}\in\Lambda$ and a point $c$ such that
$c\in ID_{p}+b_{1}$ and $c\in ID_{p}+b_{2}$. Hence there are points
$a_{1},a_{2}\in ID_{p}$ such that $c=a_{1}+b_{1}=a_{2}+b_{2}$. So
$b_{1}-b_{2}=a_{2}-a_{1}\in ID_{p}$, whereas $b_{1}-b_{2}\neq 0$ and
$b_{1}-b_{2}\in\Lambda$. Therefore $\Lambda$ is not (strictly) admissible
lattice.

###### Proposition 2

[9, 10]. The dencity of a $(D_{p},\Lambda)$-packing is equal to
$V(D_{p})/d(\Lambda)$ and it is maximal if $\Lambda$ is critical for $2D_{p}$.

##  4 On packing Minkowski balls, Davis balls and Chebyshev-Cohn balls on the
plane

Let us consider possible optimal lattice packings of these balls and their
connection with critical lattices.

At first give lattices of trivial optimal lattice packings for the limiting
(asymptotic) cases at the points $p=1$ and $\infty$ ”infinity” (the latter
corresponds to the classical Chebyshev balls) and as the introductory example
the optimal packing of two-dimensional unit balls.

###### Proposition 3

The lattice

$\Lambda_{1}^{(1)}=\\{(\frac{1}{2},\frac{1}{2}),(0,1)\\}$

is the critica lattice for $D_{1}$. Limiting case of Minkowski balls for $p=1$
gives the optimal sublattice of index two of the lattice
$\Lambda_{1}^{(1)}$-lattice packing with the density $1$. The centers of the
Minkowski balls in this case are at the vertices of the sublattice of index
two of the lattice $\Lambda_{1}^{(1)}$.

Proof. Recall that a critical lattice for $D_{1}$ is a lattice $\Lambda$ which
is $D_{1}$-admissible and which has determinant $d(\Lambda)=\Delta(D_{1})$.
The lattice $\Lambda_{1}^{(1)}$ is $D_{1}$-admissible. We have
$\Delta(D_{1})=\frac{1}{2}$ and $d(\Lambda_{1}^{(1)})=\frac{1}{2}$. Minkowski
balls for $p=1$ are congruent squares. Hance we have the optimal the
sublattice of index two of the lattice $\Lambda_{1}^{(1)}$ packing of the
squares with the density $1$.

###### Proposition 4

The lattice

$\Lambda_{\infty}^{(1)}=\\{(1,1),(0,1)\\}$

is the critica lattice for $D_{\infty}$. Limiting case of Minkowski balls for
$p=\infty$ gives the optimal of the density $1$ packing with respect to the
sublattice of index two of the critical lattice $\Lambda_{\infty}^{(1)}$. The
centers of the Minkowski balls in this case are at the vertices of the
sublattice of index two of the lattice $\Lambda_{\infty}^{(1)}$.

Proof. The lattice $\Lambda_{\infty}^{(1)}$ is $D_{\infty}$-admissible. We
have $\Delta(D_{\infty})=1$ and $d(\Lambda_{\infty}^{(1)}=1$. Minkowski balls
for $p=\infty$ are congruent squares. Hance we have the optimal the sublattice
of index two of the lattice $\Lambda_{\infty}^{(1)}$ packing of the squares
with the density $1$.

###### Proposition 5

The lattice

$\Lambda_{2}^{(0)}=\\{(1,0),(\frac{1}{2},\frac{\sqrt{3}}{2})\\}$

is the critica lattice for $D_{2}$. The lattice packing of Davis balls for
$p=2$ gives the optimal of the density $\approx 0.91$ packing with respect to
the sublattice of index two of the critical lattice $\Lambda_{2}^{(0)}$. The
centers of the Minkowski balls in this case are at the vertices of the
sublattice of index two of the lattice $\Lambda_{2}^{(0)}$.

Proof. As in Proposition (3) a critical lattice for $D_{2}$ is a lattice
$\Lambda$ which is $D_{2}$-admissible and which has determinant
$d(\Lambda)=\Delta(D_{2})$. The lattice $\Lambda_{2}^{(0)}$ is
$D_{2}$-admissible. We have $\Delta(D_{2})=\frac{\sqrt{3}}{2}$ and
$d(\Lambda_{2}^{(0)})=\frac{\sqrt{3}}{2}$. So sublattice of index two of the
lattice $\Lambda_{2}^{(0)}$ is the hexagonal lattice. Next, we use the
following classical results [14, 15]: the optimal sphere packing of dimension
2 is the hexagonal lattice (honeycomb) packing with the density $\approx
0.91$.

###### Proposition 6

If $\Lambda$ is the critical lattice of the Minkowski ball $D_{p}$ than the
sublattice $\Lambda_{2}$ of index two of the critical lattice is the critical
lattice of $2D_{p}$. (Examples for $n=1,2,\infty$ above). Here we give the
proof of the Proposition 6.

Proof. Since the Minkowski ball $D_{p}$ is symmetric about the origin and
convex, then $2D_{p}$ is convex and symmetric about the origin [9, 10].

When parametrizing admissible lattices $\Lambda$ having three pairs of points
on the boundary of the ball $D_{p}$, the following parametrization is used [7,
17, 18, 19]:

$\Lambda=\\{((1+\tau^{p})^{-\frac{1}{p}},\tau(1+\tau^{p})^{-\frac{1}{p}}),(-(1+\sigma^{p})^{-\frac{1}{p}},\sigma(1+\sigma^{p})^{-\frac{1}{p}})\\}$
(2)

where

$0\leq\tau<\sigma,\;0\leq\tau\leq\tau_{p}.$

$\tau_{p}$ is defined by the equation
$2(1-\tau_{p})^{p}=1+\tau_{p}^{p},\;0\leq\tau_{p}<1.$

$1\leq\sigma\leq\sigma_{p},\;\sigma_{p}=(2^{p}-1)^{\frac{1}{p}}.$

Admissible lattices of the form (2) for doubled Minkowski balls $2D_{p}$ have
a representation of the form

$\Lambda_{2D_{p}}=\\{2((1+\tau^{p})^{-\frac{1}{p}},2\tau(1+\tau^{p})^{-\frac{1}{p}}),(-2(1+\sigma^{p})^{-\frac{1}{p}},2\sigma(1+\sigma^{p})^{-\frac{1}{p}})\\}$
(3)

Hence the Minkowski-Cohn moduli space for these admissible lattices has the
form

$\Delta(p,\sigma)_{2D_{p}}=4(\tau+\sigma)(1+\tau^{p})^{-\frac{1}{p}}(1+\sigma^{p})^{-\frac{1}{p}},$
(4)

in the same domain

${\mathcal{M}}:\;\infty>p>1,\;1\leq\sigma\leq\sigma_{p}=(2^{p}-1)^{\frac{1}{p}},$

Consequently, the critical determinants of doubled Minkowski balls have a
representation of the form

${\Delta^{(0)}_{p}}(2D_{p})=\Delta(p,{\sigma_{p}})_{2D_{p}}=2\cdot{\sigma}_{p},\;{\sigma}_{p}=(2^{p}-1)^{1/p},$
${\Delta^{(1)}_{p}}(2D_{p})=\Delta(p,1))_{2D_{p}}=4^{1-\frac{1}{p}}\frac{1+\tau_{p}}{1-\tau_{p}},\;2(1-\tau_{p})^{p}=1+\tau_{p}^{p},\;0\leq\tau_{p}<1.$

And these are the determinants of the sublattices of index 2 of the critical
lattices of the corresponding Minkowski balls.

###### Theorem 2

The optimal lattice packing of the Minkowski, Davis, and Chebyshev-Cohn balls
is realized with respect to the sublattices of index two of the critical
lattices

$(1,0)\in\Lambda_{p}^{(0)},\;(-2^{-1/p},2^{-1/p})\in\Lambda_{p}^{(1)}.$

Proof. By Proposition 6 the critical lattice of $2D_{p}$ is the sublattice of
index two of the critical lattice of Minkowski ball $D_{p}$ . So it is the
admissible lattice for $2D_{p}$ and by Proposition 1 is packing lattice of
$D_{p}$. By Proposition 2 the corresponding lattice packing has maximal
density and so is optimal.

###### Remark 2

This result concerns the packing of unit balls and spheres in complete normed
(Banach) spaces of dimension 2.

## References

  * [1] Viazovska M.S. The sphere packing problem in dimension 8, Ann. of Math. (2) 185, no. 3, 991–1015, (2017).
  * [2] H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, and M. Viazovska, The sphere packing problem in dimension 24, Ann. of Math. (2) 185, no. 3, 1017–1033, (2017).
  * [3] H. Minkowski, Diophantische Approximationen, Leipzig: Teubner (1907).
  * [4] H. Minkowski, Geometrie der Zahlen, Berlin–Leipzig: Teubner (1910).
  * [5] L.J. Mordell, Lattice points in the region $|Ax^{4}|+|By^{4}|\geq 1,$ J. London Math. Soc. 16 , 152–156 (1941).
  * [6] C. Davis, Note on a conjecture by Minkowski, J. London Math. Soc., 23, 172–175 (1948).
  * [7] H. Cohn, Minkowski’s conjectures on critical lattices in the metric $\\{|\xi|^{p}+|\eta|^{p}\\}^{{1}/{p}},$ Annals of Math., 51, (2), 734–738 (1950).
  * [8] G. Watson, Minkowski’s conjecture on the critical lattices of the region $|x|^{p}+|y|^{p}\leq 1\;$, (I), (II), Jour. London Math. Soc., 28, (3, 4), 305–309, 402–410 (1953).
  * [9] Cassels J. W. S., An Introduction to the Geometry of Numbers, Springer, NY, 1997.
  * [10] Lekkerkerker C.G., Geometry of Numbers, NorthHolland, 1969.
  * [11] A. Malyshev, Application of computers to the proof of a conjecture of Minkowski’s from geometry of numbers. I, Zap. Nauchn. Semin. LOMI, 71, 163–180 (1977).
  * [12] A. Malyshev, Application of computers to the proof of a conjecture of Minkowski’s from geometry of numbers. II, Zap. Nauchn. Semin. LOMI, 82, 29–32 (1979).
  * [13] Andersen N., Duke W., On a theorem of Davenport and Schmidt, Acta Arithmetica 198, 37-75, 2021.
  * [14] Feges Toth, Uber einen geometrischen Satz, Math. Z., 46, 79-83, 1940.
  * [15] A. Thue, Uber die dichteste, Norske Vid. Selsk. Skr., no. 1, 1-9, 1910.
  * [16] N. Glazunov, A. V. Malyshev, On Minkowski’s critical determinant conjecture,Kibernetika, No. 5, 10–14 (1985).
  * [17] N. Glazunov, A. Malyshev. The proof of Minkowski‘s conjecture concerning the critical determinant of the region $|x|^{p}+|y|^{p}<1$ near $p=2,$(in Russian), Doklady Akad. Nauk Ukr.SSR ser.A, 7 .P.9–12 (1986).
  * [18] N. Glazunov, A. Golovanov, A. Malyshev, Proof of Minkowski’s hypothesis about the critical determinant of $|x|^{p}+|y|^{p}<1$ domain, Research in Number Theory 9. Notes of scientific seminars of LOMI. 151 Leningrad: Nauka. 40–53 (1986).
  * [19] Glazunov N.M. On A. V. Malyshev’s approach to Minkowski’s conjecture concerning the critical determinant of the region $|x|^{p}+|y|^{p}<1$ for $p>1$, Chebyshevskii Sb., Volume 17, Issue 4, 185–193, 2016.