# Toda Equations and Piecewise Polynomiality for Mixed Double Hurwitz Numbers

I. P. Goulden  Department of Combinatorics & Optimization, University of
Waterloo, Canada<EMAIL_ADDRESS>,  Mathieu Guay-Paquet  LaCIM,
Université du Québec à Montréal, Canada<EMAIL_ADDRESS>and
Jonathan Novak  Department of Mathematics, Massachusetts Institute of
Technology, USA<EMAIL_ADDRESS>
###### Abstract.

This article introduces _mixed double Hurwitz numbers_ , which interpolate
combinatorially between the classical double Hurwitz numbers studied by
Okounkov and the monotone double Hurwitz numbers introduced recently by
Goulden, Guay-Paquet and Novak. Generalizing a result of Okounkov, we prove
that a certain generating series for the mixed double Hurwitz numbers solves
the $2$-Toda hierarchy of partial differential equations. We also prove that
the mixed double Hurwitz numbers are piecewise polynomial, thereby
generalizing a result of Goulden, Jackson and Vakil.

##  1\. Introduction

Consider the right Cayley graph of the symmetric group $S(d)$, as generated by
the full conjugacy class of transpositions. This is a ${d\choose 2}$-regular
graded graph with levels $L_{0},L_{1},\dots,L_{d-1}$, where $L_{k}$ is the set
of permutations with $d-k$ cycles. Each level $L_{k}$ decomposes as the
disjoint union of those conjugacy classes in $S(d)$ labelled by Young diagrams
with $d-k$ rows.

Let us introduce an edge labelling of the Cayley graph by marking each edge
corresponding to the transposition $\tau=(s\ t)$ with $t$, the larger of the
two elements interchanged by $\tau$. This edge labelling was used by Stanley
[20] and Biane [1] to study various connections between permutations, parking
functions, and noncrossing partitions111Stanley and Biane use $s$ as the edge
label instead of $t$, but this is a minor difference..

Given integers $k,l\geq 0$ and partitions $\alpha,\beta\vdash d$, let
$W^{k,l}(\alpha,\beta)$ denote the number of $(k+l)$-step walks

$\sigma=\rho\underbrace{(s_{1}\ t_{1})\dots(s_{k}\
t_{k})}_{k}\underbrace{(s_{k+1}\ t_{k+1})\dots(s_{k+l}\ t_{k+l})}_{l}$

on the Cayley graph beginning in the conjugacy class $C_{\alpha}$ and ending
in the conjugacy class $C_{\beta}$ which satisfy

$t_{1}\leq\dots\leq t_{k}.$

In words, this monotonicity condition states that the labels of the edges
traversed in the first $k$ steps of the walk form a weakly increasing
sequence.

While elementary to define, the numbers $W^{k,l}(\alpha,\beta)$ are related to
some rather sophisticated mathematics. Let
$z,t,u,a_{1},a_{2},\dots,b_{1},b_{2},\dots$ be commuting indeterminates, and
form the generating function

$\mathbf{W}(z,t,u,A,B)=1+\sum_{d=1}^{\infty}\frac{z^{d}}{d!}\sum_{k,l=0}^{\infty}t^{k}\frac{u^{l}}{l!}\sum_{\alpha,\beta\vdash
d}W^{k,l}(\alpha,\beta)p_{\alpha}(A)p_{\beta}(B),$

where $p_{\alpha}(A)$ and $p_{\beta}(B)$ denote the power-sum symmetric
functions in the variables $A=\\{a_{1},a_{2},\dots\\}$ and
$B=\\{b_{1},b_{2},\dots\\}$, respectively. The series

$\mathbf{H}(z,t,u,A,B)=\log\mathbf{W}(z,t,u,A,B)$

is a well-defined element of $\mathbb{Q}[[z,t,u,A,B]]$. Set

$H^{k,l}(\alpha,\beta)=\bigg{[}z^{d}t^{k}\frac{u^{l}}{l!}p_{\alpha}(A)p_{\beta}(B)\bigg{]}\mathbf{H}(z,t,u,A,B),$

where $[X]Y$ denotes the coefficient of the term $X$ in a series $Y$.

The numbers $H^{0,l}(\alpha,\beta)$ were first studied by Okounkov [13], who
called them the _double Hurwitz numbers_. By a classical construction due to
Hurwitz — the monodromy construction — $H^{0,l}(\alpha,\beta)$ is a weighted
count of degree $d$ branched covers of the Riemann sphere by a compact,
connected Riemann surface such that the covering map has profile $\alpha$ over
$0$, $\beta$ over $\infty$, and simple ramification over each of the $l$th
roots of unity. The Riemann-Hurwitz formula determines the genus of the
covering surface in terms of the ramification data of the covering map:

$g=\frac{l+2-\ell(\alpha)-\ell(\beta)}{2}.$

Verifying and extending a conjecture of Pandharipande [18] in Gromov-Witten
theory, Okounkov proved that the generating function $\mathbf{H}(z,0,u,A,B)$
is a solution of the $2$-Toda hierarchy of Ueno and Takasaki. The $2$-Toda
hierarchy is a countable collection of partial differential equations, each of
which yields a recurrence relation satisfied by the double Hurwitz numbers. A
construction of the Toda hierarchy may be found in [15, §4]. Kazarian and
Lando [12] subsequently showed that, when combined with the ELSV formula [4],
Okounkov’s result yields a streamlined proof of the Kontsevich-Witten theorem
relating intersection theory in moduli spaces of curves to integrable
hierarchies.

Goulden, Jackson and Vakil [10] gave an alternative interpretation of the
double Hurwitz number $H^{0,l}(\alpha,\beta)$ as counting lattice points in a
certain integral polytope. As a consequence of this interpretation and
Ehrhart’s theorem, it was shown in [10] that, after a simple rescaling,
$H^{0,l}(\alpha,\beta)$ is a piecewise polynomial function of the parts of
$\alpha$ and $\beta$, when $\ell(\alpha)$ and $\ell(\beta)$ are held fixed.
Detailed structural properties of this piecewise polynomial behaviour were
postulated in [10], and subsequently shown to hold by Johnson [11] using the
combinatorics of the infinite wedge representation of $\mathfrak{gl}(\infty)$.
Shadrin, Spitz and Zvonkine [19] have recently generalized double Hurwitz
numbers to the setting of the completed cycle theory introduced by Okounkov
and Pandharipande [14]. It is shown in [19] that piecewise polynomiality of
double Hurwitz numbers with completed cycle insertions follows from a suitable
modification of Johnson’s arguments.

The _monotone double Hurwitz numbers_ $H^{k,0}(\alpha,\beta)$ were introduced
by the present authors in [6], where it was shown that they are the
combinatorial objects underlying the asymptotic expansion of the Harish-
Chandra-Itzykson-Zuber integral, an important special function in random
matrix theory. Structural properties of the monotone single Hurwitz numbers
$H^{k,0}(\alpha)=H^{k,0}(\alpha,1^{d})$ were studied in detail in [7, 8],
where it was shown that they enjoy a high degree of structural similarity with
the classical single Hurwitz numbers $H^{0,l}(\alpha)=H^{0,l}(\alpha,1^{d})$.

In this article, we extend the theorems of Okounkov and Goulden-Jackson-Vakil
to the more general setting of the _mixed double Hurwitz numbers_
$H^{k,l}(\alpha,\beta)$, which interpolate between the classical double
Hurwitz numbers ($k=0$) and the monotone double Hurwitz numbers ($l=0$).

######  Theorem 1.

The generating function $\mathbf{H}$ is a solution of the $2$-Toda hierarchy.

######  Theorem 2.

The mixed double Hurwitz numbers are piecewise polynomial.

##  2\. Toda equations

Let us group the transposition generators of $S(d)$ into a matrix,

$T=\begin{bmatrix}(1\ 2)&(1\ 3)&\dots&(1\ d)\\\ {}&(2\ 3)&\dots&(2\ d)\\\
{}&{}&\ddots&\vdots\\\ {}&{}&{}&(d-1\ d)\end{bmatrix}.$

Denote by

$\displaystyle J_{2}$ $\displaystyle=(1\ 2)$ $\displaystyle J_{3}$
$\displaystyle=(1\ 3)+(2\ 3)$ $\displaystyle\vdots$ $\displaystyle J_{d}$
$\displaystyle=(1\ d)+(2\ d)+\dots+(d-1\ d),$

the column sums of this matrix, viewed as elements of the group algebra
$\mathbb{Q}S(d)$. These elements commute. Set $J_{1}:=0$, and introduce the
multiset

$\Xi_{d}=\\{\\{J_{1},\dots,J_{d},0,0,\dots\\}\\}.$

Let $\Lambda$ denote the $\mathbb{Q}$-algebra of symmetric functions. We will
consider the evaluation of the complete symmetric function $h_{\mu}\in\Lambda$
indexed by the $(k,l)$-hook Young diagram $\mu=(k,1^{l})$ on the alphabet
$\Xi_{d}$. From the definition of the complete symmetric functions, we have

$\displaystyle h_{(k,1^{l})}(\Xi_{d})$
$\displaystyle=h_{k}(\Xi_{d})h_{1}(\Xi_{d})^{l}$
$\displaystyle=\bigg{(}\sum_{2\leq t_{1}\leq\dots\leq t_{k}\leq
d}J_{t_{1}}\dots J_{t_{k}}\bigg{)}\bigg{(}\sum_{t=2}^{d}J_{t}\bigg{)}^{l}$
$\displaystyle=\bigg{(}\sum_{2\leq t_{1}\leq\dots\leq t_{k}\leq
d}\bigg{(}\sum_{s_{1}<t_{1}}(s_{1}\
t_{1})\bigg{)}\dots\bigg{(}\sum_{s_{k}<t_{k}}(s_{k}\
t_{k})\bigg{)}\bigg{)}\bigg{(}\sum_{2\leq t\leq d}\sum_{s<t}(s\
t)\bigg{)}^{l}$ $\displaystyle=\sum_{\begin{subarray}{c}t_{1},\dots
t_{k+l}=2\\\ t_{1}\leq\dots\leq t_{k}\\\ s_{i}<t_{i}\end{subarray}}^{d}(s_{1}\
t_{1})\dots(s_{k}\ t_{k})(s_{k+1}\ t_{k+1})\dots(s_{k+l}\ t_{k+l}).$

Thus

$W^{k,l}(\alpha,\beta)=[C_{(1^{d})}]C_{\alpha}h_{(k,1^{l})}(\Xi_{d})C_{\beta},$

where we have identified each conjugacy class in $S(d)$ with the formal sum of
its elements in $\mathbb{Q}S(d)$. In other words, $W^{k,l}(\alpha,\beta)$ is
the normalized character of $C_{\alpha}h_{(k,1^{l})}(\Xi_{d})C_{\beta}$ in the
regular representation of $\mathbb{Q}S(d)$.

The columns sums of $T$ are known as the _Jucys-Murphy elements_ of
$\mathbb{Q}S(d)$. It was observed by Jucys and Murphy (see [3] for a proof)
that $e_{r}(\Xi_{d})$, the $r$th elementary symmetric function evaluated on
the alphabet of Jucys-Murphy elements, is precisely the sum of the
permutations on level $L_{r}$ of the Cayley graph:

$e_{r}(\Xi_{d})=\sum_{\begin{subarray}{c}\mu\vdash d\\\
\ell(\mu)=d-r\end{subarray}}C_{\mu}.$

In particular, $e_{r}(\Xi_{d})$ belongs to the center $Z(d)$ of
$\mathbb{Q}S(d)$. Since $\Lambda=\mathbb{Q}[e_{1},e_{2},\dots]$, the
substitution $f\mapsto f(\Xi_{d})$ defines a specialization
$\Lambda\rightarrow Z(d)$. In fact, since the levels of the Cayley graph
generate $Z(d)$, this specialization is surjective [5].

Since $C_{\alpha}h_{(k,1^{l})}(\Xi_{d})C_{\beta}$ belongs to the centre of
$\mathbb{Q}S(d)$, we can calculate its character in the regular representation
using the Fourier transform. Let $(V^{\lambda},\rho^{\lambda}),\ \lambda\vdash
d$, be pairwise non-isomorphic irreducible representations of
$\mathbb{Q}S(d)$, so that the map

$\sigma\mapsto(\rho^{\lambda}(\sigma):\lambda\vdash d)$

defines an algebra isomorphism

$\mathbb{Q}S(d)\rightarrow\bigoplus_{\lambda\vdash
d}\operatorname{End}V^{\lambda}.$

The normalized character of $C_{\alpha}h_{(k,1^{l})}(\Xi_{d})C_{\beta}$ in the
regular representation of $\mathbb{Q}S(d)$ is thus

$\displaystyle[C_{(1^{d})}]C_{\alpha}h_{(k,1^{l})}(\Xi_{d})C_{\beta}$
$\displaystyle=\sum_{\lambda\vdash
d}\operatorname{Tr}\rho^{\lambda}(C_{\alpha}h_{(k,1^{l})}(\Xi_{d})C_{\beta})\frac{\dim
V^{\lambda}}{d!}$ $\displaystyle=\sum_{\lambda\vdash
d}\operatorname{Tr}\rho^{\lambda}(C_{\alpha})\rho^{\lambda}(h_{(k,1^{l})}(\Xi_{d}))\rho^{\lambda}(C_{\beta})\frac{\dim
V^{\lambda}}{d!}$ $\displaystyle=\sum_{\lambda\vdash
d}\operatorname{Tr}\omega^{\lambda}(C_{\alpha})\omega^{\lambda}(h_{(k,1^{l})}(\Xi_{d}))\omega^{\lambda}(C_{\beta})\frac{(\dim
V^{\lambda})^{2}}{d!},$

where, for any $C\in Z(d)$, we denote by $\omega^{\lambda}(C)$ the unique
eigenvalue of the scalar operator
$\rho^{\lambda}(C)\in\operatorname{End}V^{\lambda}$, i.e.
$\rho^{\lambda}(C)=\omega^{\lambda}(C)I_{V^{\lambda}}$. The eigenvalue
$\omega^{\lambda}(C)$ is known as the _central character_ of $C$ in the
representation $(V^{\lambda},\rho^{\lambda})$.

The central character of any conjugacy class $C_{\mu}$ is given, in terms of
the usual character

$\chi^{\lambda}_{\mu}=\operatorname{Tr}\rho^{\lambda}(\sigma),\quad\sigma\in
C_{\mu},$

by the formula

$\omega^{\lambda}(C_{\mu})=|C_{\mu}|\frac{\chi^{\lambda}_{\mu}}{\dim
V^{\lambda}}.$

The central character of any symmetric function $f$ evaluated on $\Xi_{d}$ is
simply

$\omega^{\lambda}(f(\Xi_{d}))=f(\operatorname{Cont}_{\lambda}),$

the evaluation of $f$ on the multiset of contents of the Young diagram
$\lambda$. This remarkable result is due to Jucys and Murphy, see [3] for a
proof.

Recalling that the Schur functions have the expansion

$s_{\lambda}=\ \sum_{\mu\vdash
d}\frac{|C_{\mu}|}{d!}\chi^{\lambda}_{\mu}p_{\mu},$

where $\lambda\vdash d$, the generating function $\mathbf{W}$ may be rewritten
as follows:

$\displaystyle\mathbf{W}(z,t,u,A,B)$
$\displaystyle=1+\sum_{d=1}^{\infty}\frac{z^{d}}{d!}\sum_{k,l=0}^{\infty}t^{k}\frac{u^{l}}{l!}\sum_{\alpha,\beta,\lambda\vdash
d}W^{k,l}(\alpha,\beta)p_{\alpha}(A)p_{\beta}(B)$
$\displaystyle=1+\sum_{d=1}^{\infty}\frac{z^{d}}{d!}\sum_{k,l=0}^{\infty}t^{k}\frac{u^{l}}{l!}\sum_{\alpha,\beta,\lambda\vdash
d}\bigg{(}\frac{1}{d!}\sum_{\lambda\vdash
d}|C_{\alpha}|\chi^{\lambda}_{\alpha}h_{(k,1^{l})}(\operatorname{Cont}_{\lambda})|C_{\beta}|\chi^{\lambda}_{\beta}\bigg{)}p_{\alpha}(A)p_{\beta}(B)$
$\displaystyle=1+\sum_{d=1}^{\infty}z^{d}\sum_{k,l=0}^{\infty}t^{k}\frac{u^{l}}{l!}\sum_{\lambda\vdash
d}h_{(k,1^{l})}(\operatorname{Cont}_{\lambda})\bigg{(}\sum_{\alpha\vdash
d}\frac{|C_{\alpha}|}{d!}\chi^{\lambda}_{\alpha}p_{\alpha}(A)\bigg{)}\bigg{(}\sum_{\beta\vdash
d}\frac{|C_{\beta}|}{d!}\chi^{\lambda}_{\beta}p_{\beta}(B)\bigg{)}$
$\displaystyle=1+\sum_{d=1}^{\infty}z^{d}\sum_{k,l=0}^{\infty}t^{k}\frac{u^{l}}{l!}\sum_{\lambda\vdash
d}h_{(k,1^{l})}(\operatorname{Cont}_{\lambda})s_{\lambda}(A)s_{\lambda}(B)$
$\displaystyle=1+\sum_{d=1}^{\infty}z^{d}\sum_{\lambda\vdash
d}s_{\lambda}(A)s_{\lambda}(B)\bigg{(}\sum_{k=0}^{\infty}t^{k}h_{k}(\operatorname{Cont}_{\lambda})\bigg{)}\bigg{(}\sum_{l=0}^{\infty}\frac{u^{l}}{l!}h_{1}(\operatorname{Cont}_{\lambda})^{l}\bigg{)}$
$\displaystyle=\sum_{\lambda\in\mathcal{Y}}Y(\lambda)s_{\lambda}(A)s_{\lambda}(B).$

Here $\mathcal{Y}$ is the set of all Young diagrams (including the empty
diagram) and

$Y(\lambda)=Y(\lambda;z,t,u)=\prod_{\Box\in\lambda}\frac{ze^{c(\Box)u}}{1-c(\Box)t},$

where for any Young diagram $\lambda$ and cell $\Box$ in $\lambda$, $c(\Box)$
denotes the content of this cell, i.e. its column index less its row index. By
convention, an empty product equals $1$.

In order to complete the proof of Theorem 1, we appeal to the following result
of Orlov and Scherbin [17], and Carrell [2].

######  Theorem 3.

Let $\\{y_{k}:k\in\mathbb{Z}\\}$ be a set of variables indexed by the
integers, and set

$Y(\lambda)=\prod_{\Box\in\lambda}y_{c(\Box)}$

for each $\lambda\in\mathcal{Y}$. The series

$\log\bigg{(}\sum_{\lambda\in\mathcal{Y}}Y(\lambda)s_{\lambda}(A)s_{\lambda}(B)\bigg{)}$

is a solution of the $2$-Toda lattice hierarchy in the variables
$p_{1}(A),p_{2}(A),\dots$ and $p_{1}(B),p_{2}(B),\dots$.

Solutions of the Toda equations of the form described in Theorem 3 are known
as _diagonal content-product solutions_. Our computations above show that the
generating function

$\mathbf{H}(z,t,u,A,B)=\log\vec{\mathbf{W}}(z,t,u,A,B)$

of the mixed double Hurwitz numbers is a diagonal content-product solution,
with

$y_{k}=y_{k}(z,t,u)=\frac{ze^{ku}}{1-kt}.$

In particular, Okounkov’s generating function $\mathbf{H}(z,0,u,A,B)$ for the
classical double Hurwitz numbers is the diagonal content product solution with

$y_{k}=ze^{ku},$

while the generating function $\mathbf{H}(z,t,0,A,B)$ for the monotone double
Hurwitz numbers is the diagonal content product solution with

$y_{k}=\frac{z}{1-kt}.$

##  3\. Piecewise polynomiality

To prove Theorem 2, let us begin by formulating precisely the relationship
between the numbers $W^{k,l}(\alpha,\beta)$ and $H^{k,l}(\alpha,\beta)$. To
this end, consider the generating functions $\mathbf{W}$ and $\mathbf{H}$ as
elements of $\mathbb{Q}[[t,u,A,B]][[z]]$ by writing

$\mathbf{W}(z)=1+\sum_{d=1}^{\infty}\frac{z^{d}}{d!}\mathbf{W}_{d}(t,u,A,B),\quad\mathbf{H}(z)=\sum_{d=1}^{\infty}\frac{z^{d}}{d!}\mathbf{H}_{d}(t,u,A,B),$

where, for each $d\geq 1$,

$\begin{split}\mathbf{W}_{d}(t,u,A,B)&=\sum_{k,l=0}^{\infty}t^{k}\frac{u^{l}}{l!}\sum_{\alpha,\beta\vdash
d}W^{k,l}(\alpha,\beta)p_{\alpha}(A)p_{\beta}(B)\\\
\mathbf{H}_{d}(t,u,A,B)&=d!\sum_{k,l=0}^{\infty}t^{k}\frac{u^{l}}{l!}\sum_{\alpha,\beta\vdash
d}H^{k,l}(\alpha,\beta)p_{\alpha}(A)p_{\beta}(B).\end{split}$

Then, by the exponential formula, we have

$\mathbf{W}_{d}(t,u,A,B)=\sum_{r=1}^{d}\ \sum_{P_{1}\sqcup\dots\sqcup P_{r}}\
\prod_{j=1}^{r}|P_{j}|!\mathbf{H}_{|P_{j}|}(t,u,A,B)$

for each $d\geq 1$, as an identity in $\mathbb{Q}[[t,u,A,B]]$. In this
identity, the inner sum is over partitions $P_{1}\sqcup\dots\sqcup P_{r}$ of
$\\{1,\dots,d\\}$ into $r$ disjoint nonempty sets. Equating the coefficient of
$t^{k}\frac{u^{l}}{l!}$ on either side of this identity, we obtain

$\displaystyle\sum_{\alpha,\beta\vdash
d}W^{k,l}(\alpha,\beta)p_{\alpha}(A)p_{\beta}(B)=\sum_{r=1}^{d}\
\sum_{P_{1}\sqcup\dots\sqcup P_{r}}\
\prod_{j=1}^{r}|P_{j}|!\sum_{\zeta^{j},\eta^{j}\vdash|P_{j}|}H^{k,l}(\zeta^{j},\eta^{j})p_{\eta^{j}}(A)p_{\zeta^{j}}(B),$

for each $d\geq 1$ and $k,l\geq 0$, as an identity in $\mathbb{Q}[[A,B]]$.
Note that the sum on the right hand side depends only on the overall block
structure of the set partition $P_{1}\sqcup\dots\sqcup P_{r}$, and not on the
internal structure of the individual blocks. We can thus replace the right
hand side by a sum over integer partitions,

$\sum_{\alpha,\beta\vdash
d}W^{k,l}(\alpha,\beta)p_{\alpha}(A)p_{\beta}(B)=\sum_{\theta\vdash
d}c_{\theta}\sum_{\begin{subarray}{c}(\zeta^{1},\dots,\zeta^{\ell(\theta)})\\\
\zeta^{j}\vdash\theta_{j}\end{subarray}}\sum_{\begin{subarray}{c}(\eta^{1},\dots,\eta^{\ell(\theta)})\\\
\eta^{j}\vdash\theta_{j}\end{subarray}}\bigg{(}\prod_{j=1}^{\ell(\theta)}H^{k,l}(\zeta^{j},\eta^{j})\bigg{)}p_{\zeta^{1}\cup\dots\cup\zeta^{\ell(\theta)}}(A)p_{\eta^{1}\cup\dots\cup\eta^{\ell(\theta)}}(B),$

where the coefficient $c_{\theta}$ is given by

$c_{\theta}=|f^{-1}(\theta)|\prod_{i=1}^{\ell(\theta)}\theta_{i}!$

and $f$ denotes the surjection

$P_{1}\sqcup\dots\sqcup P_{r}\mapsto\bigg{(}\max_{1\leq j\leq
r}|P_{j}|,\dots,\min_{1\leq j\leq r}|P_{j}|\bigg{)}$

from set partitions of $\\{1,\dots,d\\}$ onto integer partitions of $d$. The
internal sums run over sequences of partitions whose $j$th element is a
partition of the $j$th part of $\theta$, and if $(\mu^{1},\dots,\mu^{k})$ is
any sequence of partitions then $\mu^{1}\cup\dots\cup\mu^{k}$ denotes the
partition obtained by arranging the parts of $\mu^{1},\dots,\mu^{k}$ in weakly
decreasing order.

Extracting the coefficient of $p_{\alpha}(A)p_{\beta}(B)$ on each side of the
above identity in $\mathbb{Q}[[A,B]]$, we obtain the numerical identity

$W^{k,l}(\alpha,\beta)=\sum_{\theta\vdash
d}c_{\theta}\sum_{\begin{subarray}{c}(\zeta^{1},\dots,\zeta^{\ell(\theta)})\\\
\zeta^{j}\vdash\theta_{j}\\\
\zeta^{1}\cup\dots\cup\zeta^{\ell(\theta)}=\alpha\end{subarray}}\
\sum_{\begin{subarray}{c}(\eta^{1},\dots,\eta^{\ell(\theta)})\\\
\eta^{j}\vdash\theta_{j}\\\
\eta^{1}\cup\dots\cup\eta^{\ell(\theta)}=\beta\end{subarray}}\prod_{j=1}^{\ell(\theta)}H^{k,l}(\zeta^{j},\eta^{j}).$

The sum on the right hand side receives non-zero contributions from Young
diagrams $\theta$ whose rows can be obtained by gluing together rows of
$\alpha$, and by gluing together rows of $\beta$. This is possible if and only
if, for each row $\theta_{k}$ of $\theta$, there exist subsets
$I_{k},J_{k}\subseteq\\{1,\dots,d\\}$ such that

(3.1) $\sum_{i\in I_{k}}\alpha_{i}=\sum_{j\in J_{k}}\beta_{j}=\theta_{k}.$

In the case of the one-row Young diagram $\theta=(d)$, the required sets are
simply $I_{1}=J_{1}=\\{1,\dots,d\\}$, so we have

$W^{k,l}(\alpha,\beta)=d!H^{k,l}(\alpha,\beta)+\dots,$

where the ellipsis stands for contributions from Young diagrams $\theta$ that
have at least two rows. These contributions are zero unless the constraint 3.1
is met for each row of $\theta$. We thus conclude that $W^{k,l}(\alpha,\beta)$
and $H^{k,l}(\alpha,\beta)$ typically agree, up to a factor of $d!$.

We can give a geometric interpretation of the above as follows. Fix two
positive integers $m$ and $n$ and consider the convex region

$\mathfrak{R}_{m,n}=\\{(x_{1},\dots,x_{m},y_{1},\dots,y_{n}):x_{1}\geq\dots\geq
x_{m}>0,\ y_{1}\geq\dots\geq y_{n}>0,\
\sum_{i=1}^{m}x_{i}=\sum_{j=1}^{n}y_{j}\\}$

in Euclidean space $\mathbb{R}^{m+n}$. Pairs of partitions $(\alpha,\beta)$
such that

$|\alpha|=|\beta|,\quad\ell(\alpha)=m,\quad\ell(\beta)=n$

may be identified with lattice points in $\mathfrak{R}_{m,n}$ via

$(\alpha,\beta)\mapsto(\alpha_{1},\dots,\alpha_{m},\beta_{1},\dots,\beta_{n}).$

Given proper nonempty subsets $I\subset\\{1,\dots,m\\}$ and
$J\subset\\{1,\dots,n\\}$, define a hyperplane $\mathfrak{W}_{IJ}$ in
$\mathbb{R}^{m+n}$ by

$\mathfrak{W}_{IJ}=\\{(x_{1},\dots,x_{m},y_{1},\dots,y_{n})\in\mathbb{R}^{m+n}:\sum_{i\in
I}x_{i}=\sum_{j\in J}y_{j}\\}.$

The hyperplanes $\mathfrak{W}_{IJ}$, as $I$ ranges over proper nonempty
subsets of $\\{1,\dots,m\\}$ and $J$ ranges over proper nonempty subsets of
$\\{1,\dots,n\\}$, constitute the _resonance arrangement_ of [11]. A chamber
$\mathfrak{c}$ of the resonance arrangement is a connected component of the
complement of a hyperplane $\mathfrak{W}_{IJ}$ in $\mathfrak{R}_{m,n}$. On any
chamber $\mathfrak{c}$ of the resonance arrangement, we have that

$W^{k,l}(\alpha,\beta)=d!H^{k,l}(\alpha,\beta)$

for all lattice points $(\alpha,\beta)\in\mathfrak{c}$.

Theorem 2 claims that for each chamber $\mathfrak{c}$ there exists a
polynomial $p_{\mathfrak{c}}^{k,l}$ in $m+n$ variables such that

$H^{k,l}(\alpha,\beta)=p^{k,l}_{\mathfrak{c}}(\alpha_{1},\dots,\alpha_{m},\beta_{1},\dots,\beta_{n})$

for all lattice points $(\alpha,\beta)\in\mathfrak{c}$. From the above
discussion and Section 2, we know that $H^{k,l}(\alpha,\beta)$ is given by the
character formula

(3.2)
$H^{k,l}(\alpha,\beta)=\frac{|C_{\alpha}|}{d!}\frac{|C_{\beta}|}{d!}\sum_{\lambda\vdash
d}\chi^{\lambda}_{\alpha}h_{(k,1^{l})}(\operatorname{Cont}_{\lambda})\chi^{\lambda}_{\beta},\quad
d=|\alpha|=|\beta|,$

on any chamber of the resonance arrangement. In order to deduce Theorem 2 from
this character formula, we appeal to a recent result of Shadrin, Spitz and
Zvonkine [19] which asserts the piecewise polynomiality of a general class of
sums of the above form.

Let $\mathbb{C}^{\mathcal{Y}}$ denote the algebra of all functions
$\mathcal{Y}\rightarrow\mathbb{C}$. Following Olshanski [16, Proposition 2.4],
we define the algebra $\mathbb{A}$ of _regular functions_ on Young diagrams to
be the subalgebra of $\mathbb{C}^{\mathcal{Y}}$ generated by the functions

$\lambda\mapsto f(\operatorname{Cont}_{\lambda}),\quad f\in\Lambda,$

together with the function $\lambda\mapsto|\lambda|$. Consider the transform

$S:\mathbb{C}^{\mathcal{Y}}\rightarrow\mathbb{C}^{\mathcal{Y}\times\mathcal{Y}}$

from functions on Young diagrams to functions on pairs of Young diagrams
defined by

$S^{f}(\alpha,\beta)=\frac{|C_{\alpha}|}{d!}\frac{|C_{\beta}|}{d!}\sum_{\lambda\vdash
d}\chi^{\lambda}_{\alpha}f(\lambda)\chi^{\lambda}_{\beta},$

where $d=|\alpha|=|\beta|$. This definition assumes that $\alpha,\beta$ have
the same size; if $|\alpha|>|\beta|$ or vice versa, complete the smaller
diagram by adding unicellular rows. The result of Shadrin, Spitz and Zvonkine
that we need may be stated as follows: if $f\in\mathbb{A}$ is a regular
function, then $S^{f}$ is piecewise polynomial with respect to the resonance
arrangement.

######  Theorem 4.

Given a regular function $f\in\mathbb{A}$, positive integers $m$ and $n$, and
a chamber $\mathfrak{c}$ of the resonance arrangement in $\mathfrak{R}_{m,n}$,
there exists a polynomial $p^{f}_{\mathfrak{c}}$ in $m+n$ variables such that

$S^{f}(\alpha,\beta)=p^{f}_{\mathfrak{c}}(\alpha_{1},\dots,\alpha_{m},\beta_{1},\dots,\beta_{n})$

for all lattice points $(\alpha,\beta)\in\mathfrak{c}$.

From the character formula 3.2, we see that Theorem 2 follows by applying
Theorem 4 with $f$ the regular function

$\lambda\mapsto h_{(k,1^{l})}(\operatorname{Cont}_{\lambda}).$

## References

  * [1] P. Biane, Parking functions of types A and B, Electron. J. Combin. 9 (2002), #N7.
  * [2] S. R. Carrell, Diagonal solutions to the $2$-Toda hierarchy, Math. Res. Lett., to appear.
  * [3] P. Diaconis, C. Greene, Applications of Murphy’s elements, Stanford University Technical Report No. 335, Sept. 1989.
  * [4] T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein, Hurwitz numbers and intersections on moduli spaces of curves, Invent. Math. 146 (2001), 297-327.
  * [5] H. K. Farahat, G. Higman, The centres of symmetric group rings, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 250(1261) (1959), 212-221.
  * [6] I. P. Goulden, M. Guay-Paquet, J. Novak, Monotone Hurwitz numbers and the HCIZ integral, arXiv:1107.1015.
  * [7] I. P. Goulden, M. Guay-Paquet, J. Novak, Monotone Hurwitz in genus zero, Canad. J. Math, in press.
  * [8] I. P. Goulden, M. Guay-Paquet, J. Novak, Polynomiality of monotone Hurwitz in higher genera, Adv. Math. 238 (2013), 1-23.
  * [9] I. P. Goulden, D. M. Jackson, The KP hierarchy, branched covers, and triangulations, Adv. Math. 219 (2008), 932-951.
  * [10] I. P. Goulden, D. M. Jackson, R. Vakil, Towards the geometry of double Hurwitz numbers, Adv. Math. 198 (2005), 43-92.
  * [11] P. Johnson, Double Hurwitz numbers via the infinite wedge, arXiv:1008.3266.
  * [12] M. Kazarian, S. Lando, An algebro-geometric proof of Witten’s conjecture, J. Amer. Math. Soc. 20(4) (2007), 1079-1089.
  * [13] A. Okounkov, Toda equations for Hurwitz numbers, Math. Res. Lett. 7 (2000), 447-453.
  * [14] A. Okounkov, R. Pandharipande, Gromov-Witten theory, Hurwitz theory, and completed cycles, Ann. Math. 163 (2006), 517-560.
  * [15] A. Okounkov, R. Pandharipande, The equivariant Gromov-Witten theory of $\mathbf{P}^{1}$, Ann. Math. 163 (2006), 561-605.
  * [16] G. Olshanski, Plancherel averages: remarks on a paper by Stanley, Electron. J. Combin. 17 (2010), #R43.
  * [17] A. Yu. Orlov, D. M. Scherbin, Hypergeometric solutions of soliton equations, Theoretical and Mathematical Physics 128(1) (2001), 906-926.
  * [18] R. Pandharipande, The Toda equations and the Gromov-Witten theory of the Riemann sphere, Lett. Math. Phys. 53 (2000), 59-74.
  * [19] S. Shadrin, L. Spitz, D. Zvonkine, On double Hurwitz numbers with completed cycles, J. London Math. Soc., to appear.
  * [20] R. P. Stanley, Parking functions and noncrossing partitions, Electron. J. Combin. 4(2) (1997), #R20.


# A proof of finite crystallization via stratification

Manuel Friedrich  Department of Mathematics, Friedrich-Alexander Universität
Erlangen-Nürnberg. Cauerstr. 11, D-91058 Erlangen, Germany, & Mathematics
Münster, University of Münster, Einsteinstr. 62, D-48149 Münster, Germany
<EMAIL_ADDRESS>and  Leonard Kreutz  Department of Mathematical
Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA
<EMAIL_ADDRESS>
###### Abstract.

We devise a new technique to prove two-dimensional crystallization results in
the square lattice for finite particle systems. We apply this strategy to
energy minimizers of configurational energies featuring two-body short-ranged
particle interactions and three-body angular potentials favoring bond-angles
of the square lattice. To each configuration, we associate its bond graph
which is then suitably modified by identifying chains of successive atoms.
This method, called _stratification_ , reduces the crystallization problem to
a simple minimization that corresponds to a proof via slicing of the
isoperimetric inequality in $\ell^{1}$. As a byproduct, we also prove a
fluctuation estimate for minimizers of the configurational energy, known as
the $n^{3/4}$-law.

###### Key words and phrases:

Crystallization, square lattice, atomic interaction potentials,
stratification, edge isoperimetric inequality

##  1\. Introduction

At low temperature, atoms and molecules typically arrange themselves into
crystalline order. Tackling this phenomenon by using mathematical models
consists in proving or disproving that ground states of particle systems for
certain configurational energies with interatomic interactions exhibit
crystalline order. This issue, referred to as the crystallization problem [5],
has attracted a great deal of attention in the physics and mathematics
community. By now, various mathematically rigorous crystallization results are
available both for systems with a fixed, _finite_ number of atoms, and in the
so-called _thermodynamic limit_ dealing with the infinite particle limit. The
reader is referred to [5, 24] for a general overview and also to [33] for a
detailed account of available results. The goal of this paper is to revisit
the problem of finite crystallization in dimension two, and to present a novel
and substantially different proof strategy.

We consider a model where configurations are identified with the respective
positions of atoms $\\{x_{1},\ldots,x_{n}\\}$ in the plane with an associated
configurational energy $\mathcal{E}(\\{x_{1},\ldots,x_{n}\\})$ comprising
classical interaction potentials. More specifically,
$\mathcal{E}=\mathcal{E}_{2}+\mathcal{E}_{3}$ decomposes into
$\mathcal{E}_{2}$ and $\mathcal{E}_{3}$ describing two- and three-body
interactions, respectively. The two-body interaction potential
$\mathcal{E}_{2}$ is short-ranged and attractive-repulsive favoring atoms
sitting at some specific reference distance. For $\mathcal{E}_{3}\equiv 0$ and
for a specific choice of $\mathcal{E}_{2}$, namely the so-called _sticky disc
potential_ , crystallization in the triangular lattice has been proved by
Heitmann & Radin [29] (see also [36, 42] for generalizations) and recently
revisited in [13], via an approach from discrete differential geometry. If
instead $\mathcal{E}_{3}$ is active satisfying specific quantitative
assumptions, optimal geometries can be identified as the square or the
hexagonal lattice [33, 35], depending on whether $\mathcal{E}_{3}$ favors
triples of particles forming angles which are multiples of $\frac{\pi}{2}$ or
$\frac{2\pi}{3}$, respectively. Besides crystallization, fine
characterizations of ground-state geometries are available by proving the
emergence of hexagonal or square macroscopic Wulff shapes for growing particle
numbers [2, 9, 10, 22]. We also refer to related rigorous crystallization
results for particle systems involving different types of atoms [4, 7, 38, 20,
21, 23] and to [25, 26, 37, 41] for a nonexhaustive list of results in
dimension one.

Although the exact realization of the proof of each result is different
depending on the used potentials and the underlying optimal geometry, all
proofs follow the very same strategy, originally devised in [28, 29]. One
associates a planar graph to the configuration where vertices and edges
correspond to particles and bonds, respectively. The graph is then separated
into the boundary and bulk atoms. The _boundary energy_ (roughly, the number
of bonds at the boundary of the configuration) is carefully estimated by
geometric arguments involving the angles between atoms and relying on the sum
of interior angles in planar polygons. Moreover, by means of Euler’s formula
for planar graphs a connection between the number of bonds and atoms in the
configuration is derived. Then, the essential idea of the proof lies in an
induction argument over the number of particles: one removes a _bond graph
layer_ , i.e., the boundary atoms of the configuration, and by induction
hypothesis one uses information of the remaining configuration consisting of
less atoms. The approach in [13] is different in the sense that it endows the
bond graph with a suitable notion of discrete combinatorial curvature and uses
a discrete version of the Gauss-Bonnet theorem from differential geometry.
However, it still vitally hinges on specific geometric arguments and the
induction method over bond graph layers.

It appears to be challenging to generalize this strategy to problems beyond
the setting described above. On the one hand, it is hardly conceivable to
extend the delicate estimates on the boundary energy to particle systems in
three dimensions where surfaces have a much richer structure. On the other
hand, the induction method over bond graph layers is often not flexible enough
to handle more general situations such as particles systems with two types of
atoms with prescribed ratio since this ratio might not be preserved by
removing a bond graph layer.

In this work, we propose a new strategy to tackle finite crystallization
problems which does not use the induction method over bond graph layers and
comes along without arguments from the theory of planar graphs and discrete
differential geometry such as Euler’s formula or Gauss-Bonnet. It relies on an
idea that we call _stratification_. In this paper, we present our technique
for the model by Mainini, Piovano, & Stefanelli [33] and reprove finite
crystallization in the square lattice, see Theorem 2.1. We are confident,
however, that the strategy carries over to other lattices as well, such as the
triangular [13, 29] and the hexagonal [35] lattice.

As observed in [33], ground states correspond to configurations minimizing a
specific edge perimeter of the configuration, essentially counting the number
of missing bonds of atoms having less than four bonds. For ground-state
competitors, the bond graph can be locally interpreted as a deformed version
of $\mathbb{Z}^{2}$, apart from possible defects in the lattice, see
Definition 3.1. Therefore, we can identify chains of atoms in the bond graph
where the angle between three successive atoms is near to $\pi$, called
_strata_. Strata can be _open_ , where the first and the last atom of the
stratum lie at the boundary of the configuration, or they can be _closed_
forming a closed cycle. In contrast to open strata, closed strata do not
contribute to the edge perimeter. Therefore, for a correct estimate, we aim at
excluding the existence of closed strata. To this end, we observe that, due to
the cycle structure of closed strata, there need to exist angles deviating
from $\pi$ and thus contributing to the three-body energy $\mathcal{E}_{3}$.
Given specific quantitative assumptions on the potentials similar to the ones
in [33], the contribution of $\mathcal{E}_{3}$ is large enough to allow us to
erase a bond from the stratum to turn it into an open stratum. This procedure
is made precise in Lemma 3.7 and referred to as _stratification_. Once all
strata are open, the graph satisfies specific properties (see Lemmas 3.3 and
3.6) which reduce our crystallization problem to a simple argument related to
an edge isoperimetric inequality on the square lattice. (Compare to [33] for a
problem on $\mathbb{Z}^{2}$, and see also [6, 27] for some related classical
issues in Discrete Mathematics.)

In contrast to uniqueness of Wulff shapes for continuum crystalline
isoperimetric problems, minimizers for a finite number of particles $n$ are in
general not unique. For different lattices in 2D, it has been shown that there
are arbitrarily large $n$ with ground-state configurations deviating from the
hexagonal or square macroscopic Wulff shape by a number of $n^{3/4}$-particles
[9, 10, 33, 39]. Later, this analysis as been extended to the cubic lattice in
higher dimensions [32, 34]. The proof of such maximal asymptotic deviation,
also known as _maximal fluctuation estimate_ , relies on careful rearrangement
techniques for atoms at the boundary and edge-isoperimetric inequalities. In
our setting of the square lattice, we can immediately reobtain this so-called
$n^{3/4}$-law as a mere byproduct of our crystallization proof, see Theorem
2.2. Our argument is similar to [33] with the interesting difference however
that our strategy can be applied even if configurations are not subset of
$\mathbb{Z}^{2}$. We also mention the complementary approach [8], yet
restricted to subsets of periodic lattices, where maximal fluctuation
estimates are derived via a quantitative version of the edge isoperimetric
inequality, based on the quantitative version of the anisotropic isoperimetric
inequality proved in [16].

One goal of our work is to revisit finite crystallization results and to
suggest a substantially different proof strategy which does not use the
induction method over bond graph layers and comes along without arguments from
the theory of planar graphs and discrete differential geometry. Besides
providing, to our view, a simpler and more direct proof of known results, our
main motivation is that our techniques seem promising to tackle more
challenging crystallization problems. For example, we expect that our approach
can contribute to understand finite crystallization in three dimensions or
crystallization for double-bubble problems [11, 12, 19] (configuration with
two types of atoms).

Let us highlight that our proof strategy is tailor-made for the problem of
finite crystallization. Concerning the thermodynamic limit, i.e., as the
number of particles tends to infinity, other techniques are used and allow to
prove results under less restrictive assumptions on the potentials. We refer
to [3, 14, 15, 40] for results in the plane and to some few available rigorous
results [17, 18] in three dimensions.

The article is organized as follows. In Section 2 we introduce our setting and
state the main results. Section 3 is devoted to the concept of stratification
and in Section 4 we prove our main results. We close the introduction with
basic notation. The Euclidian distance between a point $x\in\mathbb{R}^{d}$
and a set $A\subset\mathbb{R}^{d}$ is denoted by ${\rm dist}(A,x)$. By $\\#A$
we denote the cardinality of a set $A$. By $B_{r}(x)$ we indicate the open
ball with center $x\in\mathbb{R}^{d}$ and radius $r>0$, and simply write
$B_{r}$ if $x=0$. We define the ceil function by $\lceil
t\rceil:=\min\\{z\in\mathbb{Z}\colon z\geq t\\}$ for $t\in\mathbb{R}$.

##  2\. Setting and main results

We consider particle systems in two dimensions, and model their interaction by
classical potentials in the frame of Molecular Mechanics [1, 30]. Indicating
the configuration of particles by
$C_{n}=\\{x_{1},\ldots,x_{n}\\}\subset\mathbb{R}^{2}$, we define its energy by

$\displaystyle\mathcal{F}(C_{n})=\frac{1}{2}\sum_{i\neq
j}v_{2}(|x_{i}-x_{j}|)+\frac{1}{2}\sum_{i,j,k}v_{3}(\theta_{i,j,k})\,,$ (2.1)

where the second sum runs over triples $(i,j,k)$ and $\theta_{i,j,k}$ denotes
the angle formed by the vectors $x_{j}-x_{i}$ and $x_{k}-x_{i}$ (counted
clockwisely). The factor $\frac{1}{2}$ accounts for double counting of bonds
and angles. In the following, for simplicity we denote the angle formed by the
vectors $x-y$ and $z-y$ by $\theta_{x,y,z}$. We fix
$0<\varepsilon<\varepsilon_{0}$ for $\varepsilon_{0}<\frac{\pi}{6}$ specified
in Lemma 3.2. The two-body potential
$v_{2}\colon[0,+\infty)\to{\mathbb{R}}\cup\\{+\infty\\}$ satisfies

  * ($\rm i_{2}$)

$\min_{r\geq 0}v_{2}(r)=v_{2}(1)=-1$ and $v_{2}(r)>-1$ if $r\neq 1$;

  * ($\rm ii_{2}$)

There exists $1<r_{0}<\sqrt{2}$ such that $v_{2}(r)=0$ for all $r\geq r_{0}$;

  * ($\rm iii_{2}$)

For all $r\in[0,1-\varepsilon]$ it holds that $v_{2}(r)>\varepsilon^{-1}$.

The three-body potential $v_{3}\colon[0,2\pi]\to\mathbb{R}$ satisfies

  * ($\rm i_{3}$)

$v_{3}(\theta)=v_{3}(2\pi-\theta)$ for all $\theta\in[0,2\pi]$;

  * ($\rm ii_{3}$)

$v_{3}(k\pi/2)=0$ for $k=1,2,3$ and $v_{3}(\theta)>0$ if
$\theta\notin\\{\pi/2,\pi,3\pi/2\\}$;

  * ($\rm iii_{3}$)

$v_{3}(\theta)\geq\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}4(\pi/6-\varepsilon)^{-1}\,|\theta-\pi|$
for all $\theta\in[\pi-\varepsilon,\pi+\varepsilon]$ with equality only if
$\theta=\pi$;

  * ($\rm iv_{3}$)

$\theta\notin[\pi/2-\varepsilon,\pi/2+\varepsilon]\cup[\pi-\varepsilon,\pi+\varepsilon]\cup[3\pi/2-\varepsilon,3\pi/2+\varepsilon]\implies
v_{3}(\theta)>\frac{4}{(1-\varepsilon)^{2}}(\sqrt{2}+\frac{1}{2})^{2}$ .

We briefly comment on the assumptions. Condition ($\rm i_{2}$) on a unique
minimum (here normalized to $1$) is natural, e.g., it is valid for Lennard-
Jones-type potentials. Assumption ($\rm ii_{2}$) states that $v_{2}$ has
compact support. In particular, it ensures that for configurations
$C_{n}\subset\mathbb{Z}^{2}$ only atoms at distance $1$ interact. These atoms
are usually referred to as _nearest neighbors_ in the literature. Eventually,
($\rm iii_{2}$) prevents clustering of points. In fact, along with ($\rm
ii_{2}$) it shows Definition 3.1(i) in the proof of Lemma 3.2 below. Condition
($\rm i_{3}$) ensures that the potential $v_{3}$ does not depend on how
(clockwise or counter-clockwise) bond angles are measured, and ($\rm ii_{3}$)
guarantees that for $C_{n}\subset\mathbb{Z}^{2}$ there is no contribution
stemming from the three-body interaction. Slope conditions similar to ($\rm
iii_{3}$) have been used in [20, 21, 33, 35] in order to obtain
crystallization on the square or hexagonal lattice. Let us mention that in the
other works the condition is needed at _all_ minimum points of $v_{3}$,
whereas here only at $\pi$. As a consequence, the potential is necessarily
non-smooth at $\pi$. We also point out that in this work the focus lies on a
new proof strategy and all appearing specific numerical constants are chosen
for computational simplitcity rather than optimality. The two potentials are
illustrated in Figure 1.

$v_{2}(r)$$r$$r_{0}$$1$$-1$$v_{3}(\theta)$$\theta$$\pi/2$$3\pi/2$$2\pi$$\pi$
Figure 1. The potentials $v_{2}$ and $v_{3}$.

We now state the main theorems of the paper.

######  Theorem 2.1 (Crystallization).

For each $C_{n}\in(\mathbb{R}^{2})^{n}$, it holds that

$\displaystyle\mathcal{F}(C_{n})\geq-2n+\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\lceil
2\sqrt{n}\rceil$ (2.2)

with equality only if $C_{n}\subset\mathbb{Z}^{2}$ (up to a rigid motion).

Some configurations of minimal energy are depicted in Figure 2.

######  Theorem 2.2 ($n^{3/4}$-law).

There exists $c>0$ such that for all $n\in\mathbb{N}$ it holds that each
ground state $C_{n}$, up to a rigid motion, satisfies

$\\#\big{(}C_{n}\triangle S_{n}\big{)}\leq cn^{3/4},$

where
$S_{n}:=[1,\lceil\sqrt{n}\rceil]^{2}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\cap\mathbb{Z}^{2}$.

Let us note that the scaling is sharp: the construction in [21, Section 3.2]
shows that there exists a sequence $(n_{k})_{k\in\mathbb{N}}$ with
$n_{k}\to+\infty$ and corresponding ground states $C_{n_{k}}$ such that, up to
applying any rigid motion to $C_{n_{k}}$, it holds that

$\displaystyle\\#\big{(}C_{n_{k}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\triangle
S_{n_{k}}\big{)}\geq cn_{k}^{3/4}$

for some $c>0$.

$n=9$$n=26$$n=30$ Figure 2. Configurations of minimal energy for different
cardinality.

##  3\. Stratification

After a short preliminary on graph theory, this section is devoted to the main
technique of this paper: modification of bond graphs, called stratification.

###  3.1. Bond graph

We denote by $G=(V,E)$ a graph, where $V\subset\mathbb{R}^{2}$ indicates the
set of vertices and $E\subset\\{\\{x,y\\}\colon x,y\in V\text{ and }x\neq
y\\}$ is the set of edges. For $x\in V$, we denote the neighborhood with
respect to $G$ by

$\displaystyle\mathcal{N}(x,E):=\\{y\in V\colon\\{x,y\\}\in E\\}\,.$

Given $G=(V,E)$ we define

$\displaystyle F(G)=F_{\mathrm{bond}}(G)+F_{\mathrm{ex}}(G)\,,$

where

$\displaystyle F_{\mathrm{bond}}(G)=\sum_{x\in V}(4-\\#\mathcal{N}(x,E))\,$

is the bond energy and

$\displaystyle F_{\mathrm{ex}}(G)=\sum_{\\{x,y\\}\in
E}(v_{2}(|x-y|)+1)+\sum_{\\{x,y\\},\\{y,z\\}\in E}v_{3}(\theta_{x,y,z})$

the excess energy. For $V^{\prime}\subset V$, we also define the localized
elastic energy by

$\displaystyle F_{\mathrm{ex}}(V^{\prime})=F_{\mathrm{ex}}(G[V^{\prime}])\,,$
(3.1)

where $G[V^{\prime}]$ is the (vertex) induced subgraph of $V^{\prime}$ in $G$,
that is $G[V^{\prime}]=(V^{\prime},E^{\prime})$ with
$E^{\prime}=\\{\\{x,y\\}\in E\colon x,y\in V^{\prime}\\}$.

We will identify each $C_{n}\subset\mathbb{R}^{2}$ with its _natural bond
graph_ $G_{\mathrm{nat}}=(V,E_{\mathrm{nat}})$, where $V=C_{n}$ and the
_natural edges_ are given by

$\displaystyle E_{\mathrm{nat}}=\\{\\{x,y\\}\colon x,y\in C_{n},|x-y|\leq
r_{0}\\}\,,$ (3.2)

for $r_{0}>0$ as given in ($\rm{ii}_{2}$). This definition is motivated by the
relation to (2.1), namely

$\displaystyle 2\mathcal{F}(C_{n})=-4n+F(G_{\mathrm{nat}})\,.$ (3.3)

In Subsection 3.2 below, we will successively modify $E_{\mathrm{nat}}$ to a
smaller set of edges $E\subset E_{\mathrm{nat}}$.

######  Definition 3.1.

We say that $G=(V,E)$ is _$\varepsilon$ -regular_ if:

  * (i)

If $\\{x,y\\}\in E$, then

$\displaystyle|x-y|\geq 1-\varepsilon\,;$

  * (ii)

If $\theta$ is a bond angle, then

$\displaystyle\theta\in[\pi/2-\varepsilon,\pi/2+\varepsilon]\cup[\pi-\varepsilon,\pi+\varepsilon]\cup[3\pi/2-\varepsilon,3\pi/2+\varepsilon]\,.$

Note that, if $G_{\mathrm{nat}}=(V,E_{\mathrm{nat}})$ is
$\varepsilon$-regular, then it is easy to see that $G=(V,E)$ is
$\varepsilon$-regular for all $E\subset E_{\mathrm{nat}}$.

######  Lemma 3.2.

There exists $\varepsilon_{0}>0$ such that the following holds true: if
$v_{2}$, $v_{3}$ satisfy ($\rm{i}_{2}$)–($\rm{iii}_{2}$) and
($\rm{i}_{3}$)–($\rm{iv}_{3}$) for some $0<\varepsilon<\varepsilon_{0}$ and if
$C_{n}$ is a minimizer of (2.1), then its natural bond graph
$G_{\mathrm{nat}}=(V,E_{\mathrm{nat}})$ is $\varepsilon$-regular. Moreover, it
holds that $\\#\mathcal{N}(x,E_{\mathrm{nat}})\leq 4$ for all $x\in V$.

Analogous properties have been derived in [33, Propostion 2.1] and [40, Lemma
2.2]. However, as our assumptions on the potentials are slightly different, we
include a sketch of the proof for the reader’s convenience in Appendix A. For
the remainder of this paper, we assume that $\varepsilon_{0}>0$ is chosen
small enough such that Lemma 3.2 holds true and that $v_{2}$, $v_{3}$ satisfy
($\rm{i}_{2}$)–($\rm{iii}_{2}$) and ($\rm{i}_{3}$)–($\rm{iv}_{3}$) for some
$0<\varepsilon<\varepsilon_{0}$.

###  3.2. Stratified bond graph

Given $G=(V,E)$, we say that $\gamma=(x_{1},\ldots,x_{N})$ with $x_{i}\in V$
for all $i=1,\ldots,N$ is a _straight path_ if $N\geq 2$ and the following
holds:

  * (i)

$\\{x_{i},x_{i+1}\\}\in E$ for all $i=1,\ldots,N-1\,$;

  * (ii)

$\theta_{i}\in[\pi-\varepsilon,\pi+\varepsilon]$ for all $i\in 2,\ldots,N-1$,
where $\theta_{i}=\theta_{x_{i+1},x_{i},x_{i-1}}$;

  * (iii)

$\\{x_{i},x_{i+1}\\}\neq\\{x_{j},x_{j+1}\\}$ for all $i,j=1,\ldots,N-1$,
$j\neq i$.

(If $N=2$, (ii) and (iii) are empty.) The set of straight paths is denoted by

$\displaystyle\Gamma(G):=\\{\gamma\text{ straight path}\\}\,.$

We drop $G$ and write $\Gamma$ if no confusion arises. If $\gamma\in\Gamma$
and $x_{1}=x_{N}$, we say that $\gamma$ is _closed_ and otherwise that
$\gamma$ is _open_. In the following, we add some strata for degenerate points
which will be convenient for Lemma 3.3. Specifically, we define

$\displaystyle\begin{split}&V_{i}:=\\{x\in
V\colon\\#\mathcal{N}(x,E)=i\\}\text{ for $i=0,\ldots,4$\,,}\\\
&V_{2}^{\pi}:=\\{x\in
V_{2}\colon\theta_{x_{1},x,x_{2}},\in[\pi-\varepsilon,\pi+\varepsilon]\text{
where }\mathcal{N}(x,E)=\\{x_{1},x_{2}\\}\\}\,.\end{split}$ (3.4)

Note that in the second definition, one could equally use the angle
$\theta_{x_{2},x,x_{1}}$ as
$\theta_{x_{2},x,x_{1}}=2\pi-\theta_{x_{1},x,x_{2}}$. If $x\in V_{0}$ we set
$s(x)=\\{(x),(x)\\}$, if $x\in V_{1}\cup V_{2}^{\pi}$ we set $s(x)=\\{(x)\\}$,
and we define the _set of strata_ by

$\displaystyle\mathcal{S}(G):=\mathcal{S}_{\Gamma}\cup\bigcup_{x\in V_{0}\cup
V_{1}\cup V_{2}^{\pi}}s(x),\quad\text{ where
}\mathcal{S}_{\Gamma}:=\\{\gamma\in\Gamma\colon\gamma\text{ is a maximal
element w.r.t.}\subseteq\\}\,.$ (3.5)

We drop $G$ and write $\mathcal{S}$ if no confusion arises. Some closed, open,
and degenerate strata are illustrated in Figure 3. Adding the degenerate
stratum $(x)$ with one element twice for $V_{0}$ and once for $V_{1}\cup
V_{2}^{\pi}$ has no geometrical interpretation but is merely convenient to
relate the overall number of strata to $F_{\rm bond}$. More precisely,
denoting by $l(s):=\\#s$ the length of $s\in\mathcal{S}$, we have the
following.

$x\in V_{1}$$x\in V_{0}$$x\in V_{2}^{\pi}$ Figure 3. Illustration of some
strata in the bond graph of $G$.

######  Lemma 3.3.

(Properties of graphs only containing open paths) Let $G=(V,E)$ be an
$\varepsilon$-regular graph. Assume that all $\gamma\in\Gamma$ are open. Then,
the following holds:

  * (i)

$\sum_{s\in\mathcal{S}}l(s)=2n$;

  * (ii)

$F_{\rm bond}(G)=\sum_{x\in V}(4-\\#\mathcal{N}(x,E))=2\\#\mathcal{S}$.

###### Proof.

We prove the two statements in separate steps.
(i) Since all $\gamma\in\Gamma$ are open, by definitions (3.4) and (3.5), each
$x\in V$ belongs to exactly two $s\in\mathcal{S}$. Indeed, each $x\in
V\setminus(V_{0}\cup V_{1}\cup V_{2}^{\pi})$ lies in exactly two elements of
$\mathcal{S}_{\Gamma}$. (It cannot be contained only in one as this would
contradict the openness of straight paths.) Each $x\in V_{1}\cup V_{2}^{\pi}$
lies in exactly one element of $\mathcal{S}_{\Gamma}$ and $x\in V_{0}$ is not
contained in any element of $\mathcal{S}_{\Gamma}$. The definition of $s(x)$
for $x\in V_{0}\cup V_{1}\cup V_{2}^{\pi}$ implies that each $x\in V$ belongs
to exactly two $s\in\mathcal{S}$. Hence, (i) follows.
(ii) We prove the statement by induction over $m=\\#E$. It is clearly true for
$m=0$ since, by definition of (3.5), $x\in V\implies x\in V_{0}$ and thus

$\displaystyle\\#\mathcal{S}=2\\#V=\frac{1}{2}\sum_{x\in
V}(4-\\#\mathcal{N}(x,\emptyset))=\frac{1}{2}\sum_{x\in
V}(4-\\#\mathcal{N}(x,E))\,.$

Let now $\\#E=m\geq 1$ and let $s=\\{x_{1},\ldots,x_{N}\\}\in\mathcal{S}$ be
arbitrary. Consider $\hat{E}:=E\setminus\\{x_{1},x_{2}\\}$ and the
corresponding graph $\hat{G}=(V,\hat{E})$. Then, $\\#\hat{E}=m-1$ and thus, by
the induction hypothesis,

$\displaystyle\sum_{x\in
V}(4-\\#\mathcal{N}(x,\hat{E}))=2\\#{\mathcal{S}}(\hat{G})\,,$

where ${\mathcal{S}}(\hat{G})$ is the set of strata of $\hat{G}$, defined in
(3.5). Note that
${\mathcal{S}}(\hat{G})=(\mathcal{S}\cup\\{(x_{1})\\}\cup\\{(x_{2},\ldots,x_{N})\\})\setminus
s$ and thus $\\#{\mathcal{S}}(\hat{G})=\\#\mathcal{S}+1$. As
$\\#\mathcal{N}(x_{i},E)=\\#\mathcal{N}(x_{i},\hat{E})+1$ for $i=1,2$, we have

$\displaystyle\sum_{x\in V}(4-\\#\mathcal{N}(x,E))=-2+\sum_{x\in
V}(4-\\#\mathcal{N}(x,\hat{E}))=-2+2\\#{\mathcal{S}}(\hat{G})=2\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\\#\mathcal{S}\,.$

This concludes the proof. ∎

We proceed with two definitions and a lemma on graphs with small angle excess.

######  Definition 3.4 (Angle excess).

Given $\gamma=\\{x_{1},\ldots,x_{N}\\}\in\Gamma$, we define the _angle excess_
by

$\displaystyle\theta_{\mathrm{ex}}(\gamma):=\sum^{N-1}_{i=2}|\theta_{i}-\pi|\,,\quad\text{where
$\theta_{i}=\theta_{x_{i+1},x_{i},x_{i-1}}$}\,.$

######  Definition 3.5 (Orthogonal strata).

Let $s\in\mathcal{S}$. We define the _set of orthogonal strata_ to $s$ by

$\displaystyle\mathcal{S}^{\perp}(s)=\\{s^{\prime}\in\mathcal{S}\setminus\\{s\\}\colon
s\cap s^{\prime}\neq\emptyset\\}\,.$

A stratum $s\in\mathcal{S}$ and its orthogonal strata are illustrated in
Figure 4.

$s^{\prime}$$s$ Figure 4. The stratum $s$, in red, and its orthogonal strata
$\mathcal{S}^{\perp}(s)$ in green. One $s^{\prime}\in\mathcal{S}^{\perp}(s)$
is encircled.

######  Lemma 3.6.

(Small angle excess) Let $G=(V,E)$ be an $\varepsilon$-regular graph. The
following implications hold true:

  * (i)

If
$\displaystyle\max_{\gamma\in\Gamma}\theta_{\mathrm{ex}}(\gamma)<\frac{3\pi}{2}-\varepsilon$,
then all $s\in\Gamma$ are open;

  * (ii)

If
$\displaystyle\max_{\gamma\in\Gamma}\theta_{\mathrm{ex}}(\gamma)<\frac{\pi}{2}-\varepsilon$,
then $\\#\mathcal{S}^{\perp}(s)=l(s)$ for all $s\in\mathcal{S}$;

  * (iii)

If
$\displaystyle\max_{\gamma\in\Gamma}\theta_{\mathrm{ex}}(\gamma)<\frac{\pi}{6}-\varepsilon$,
then $s_{1}\cap s_{2}=\emptyset$ for all
$s_{1},s_{2}\in\mathcal{S}^{\perp}(s)$ and for all $s\in\mathcal{S}$.

###### Proof.

We first introduce some notation that will be used throughout the proof. Let
$p=\\{x_{1},\ldots,x_{N}\\}$ be such that the edges
$e_{i}=\\{x_{i},x_{i+1}\\}$, $i=1,\ldots,N-1$, form a closed polygon. We
denote by $\theta(e_{i},e_{i+1})$ the interior angle formed by the edges
$e_{i}$ and $e_{i+1}$, $i=1,\ldots,N-1$, with the convention $e_{1}=e_{N}$. By
the interior angle sum of polygons it holds

$\displaystyle\sum_{i=2}^{N}(\theta(e_{i-1},e_{i})-\pi)=-2\pi\,.$ (3.6)

For the reader’s convenience, the proof of the three different statements is
aided by Figure 5.

$x_{1}=x_{N}$Step 1$x_{i_{1}}$$x_{i_{2}}$Step 2$y$$x_{i_{1}}$$x_{i_{2}}$Step 3
Figure 5. The three cases discussed in Steps 1–3.

Step 1.(Proof of (i)) Assume by contradiction that
$\theta_{\mathrm{ex}}(\gamma)<\frac{3\pi}{2}-\varepsilon$ for all
$\gamma\in\Gamma$ and that there exists $\gamma\in\Gamma$ closed. Let
$\gamma=\\{x_{1},\ldots,x_{N}\\}\in\Gamma$ be a minimal (w.r.t. set inclusion)
closed path. The edges $e_{i}=\\{x_{i},x_{i+1}\\}$, $i=1,\ldots,N-1$, form a
closed polygon. Therefore, by (3.6) and the triangle inequality, we have
$\theta_{\mathrm{ex}}(\gamma)+|\theta(e_{N-1},e_{1})-\pi|\geq 2\pi$. Since
$|\theta(e_{N-1},e_{1})-\pi|\leq\frac{\pi}{2}+\varepsilon$ by Definition
3.1(ii), this yields a contradiction and concludes Step 1.
Step 2.(Proof of (ii)) Assume by contradiction that
$\theta_{\mathrm{ex}}(\gamma)<\frac{\pi}{2}-\varepsilon$ for all
$\gamma\in\Gamma$ and that there exists
$s=\\{x_{1},\ldots,x_{N}\\}\in\mathcal{S}$ with
$\\#\mathcal{S}^{\perp}(s)<l(s)$. This implies that $N\geq 2$. Moreover, there
exists $s^{\prime}\in\mathcal{S}^{\perp}(s)$ and $1\leq i_{1}<i_{2}\leq N$
such that $\\{x_{i_{1}},x_{i_{2}}\\}\subset s^{\prime}\cap s$. Let us consider
$\gamma\subset s^{\prime}$ connecting $x_{i_{1}}$ and $x_{i_{2}}$ such that
$\gamma\cap s=\\{x_{i_{1}},x_{i_{2}}\\}$. We now consider
$p=\\{y_{1},\ldots,y_{M}\\}=\phi\cup\gamma$, where $\phi:=\\{x_{i_{1}},\ldots
x_{i_{2}}\\}\subset s$, and observe that its edges $e_{i}$, $i=1,\ldots,M-1$,
form a closed polygon. Let $y_{j}=x_{i_{1}}$ and $y_{k}=x_{i_{2}}$. Note that
$|\theta(e_{j-1},e_{j})-\pi|,|\theta(e_{k-1},e_{k})-\pi|\leq\frac{\pi}{2}+\varepsilon$
by Definition 3.1(ii). Identity (3.6) applied to $p$ implies
$\sum_{i=2}^{M}(\theta(e_{i-1},e_{i})-\pi)=-2\pi$. Furthermore,
$\phi,\gamma\in\Gamma$ and therefore we obtain

$\displaystyle 2\pi=\left|\sum_{i=2}^{M}(\theta(e_{i-1},e_{i})-\pi)\right|$
$\displaystyle\leq|\theta(e_{j-1},e_{j})-\pi|+|\theta(e_{k-1},e_{k})-\pi|+\underset{i\neq\\{j,k\\}}{\sum_{i=2}^{M}}|\theta(e_{i-1},e_{i})-\pi|$
$\displaystyle\leq\pi+2\varepsilon+\underset{i\neq\\{j,k\\}}{\sum_{i=2}^{M}}|\theta(e_{i-1},e_{i})-\pi|=\pi+2\varepsilon+\theta_{\mathrm{ex}}(\gamma)+\theta_{\mathrm{ex}}(\phi)\,.$

This implies that $\theta_{\mathrm{ex}}(\gamma)\geq\pi/2-\varepsilon$ or
$\theta_{\mathrm{ex}}(\phi)\geq\pi/2-\varepsilon$ and yields therefore a
contradiction.
Step 3.(Proof of (iii)) Assume by contradiction that
$\theta_{\mathrm{ex}}(\gamma)<\pi/6-\varepsilon$ for all $\gamma\in\Gamma$ and
that there exists $s\in\mathcal{S}$ and $s_{1},s_{2}\in\mathcal{S}^{\perp}(s)$
such that $s_{1}\cap s_{2}\neq\emptyset$. Writing $s=\\{x_{1},\ldots,x_{N}\\}$
there exists $i_{1}<i_{2}$ such that $s_{1}\cap s=\\{x_{i_{1}}\\}$ and
$s_{2}\cap s=\\{x_{i_{2}}\\}$. (Due to Step 2, there is only one point of
intersection between $s_{i}$ and $s$.) Again by Step 2, there holds
$\\{y\\}=s_{1}\cap s_{2}$ for some $y\in V$. Denote by
$\gamma_{1}=\\{y_{1},\ldots,y_{l_{1}}\\}\subset s$ the path connecting
$x_{i_{1}}$ with $x_{i_{2}}$,
$\gamma_{2}=\\{y_{l_{1}},\ldots,y_{l_{2}}\\}\subset s_{2}$ the path connecting
$x_{i_{2}}$ with $y$, and by
$\gamma_{3}=\\{y_{l_{2}},\ldots,y_{l_{3}}\\}\subset s_{1}$ the path connecting
$y$ with $x_{i_{1}}$. Note that $\gamma_{i}\in\Gamma$ for $i=1,2,3$. We set
$p=\gamma_{1}\cup\gamma_{2}\cup\gamma_{3}$ and observe that the edges of $p$
form a closed polygon. Equation (3.6) applied for $p$ implies
$\sum_{i=2}^{l_{3}}(\theta(e_{i-1},e_{i})-\pi)=-2\pi$. Note that
$|\theta(e_{l_{k}-1},e_{l_{k}})-\pi|\leq\frac{\pi}{2}+\varepsilon$ for all
$k=1,2,3$ by Definition 3.1(ii). Therefore, we obtain

$\displaystyle
2\pi=\left|\sum_{i=2}^{l_{3}}(\theta(e_{i-1},e_{i})-\pi)\right|$
$\displaystyle\leq\sum_{k=1}^{3}|\theta(e_{l_{k}-1},e_{l_{k}})-\pi|+\underset{i\neq\\{l_{1},l_{2},l_{3}\\}}{\sum_{i=2}^{l_{3}}}\left|\theta(e_{i-1},e_{i})-\pi\right|$
$\displaystyle\leq\frac{3\pi}{2}+3\varepsilon+\sum_{k=1}^{3}\theta_{\mathrm{ex}}(\gamma_{k})\,.$

This implies that there exists $k\in\\{1,2,3\\}$ such that
$\theta_{\mathrm{ex}}(\gamma_{k})\geq\pi/6-\varepsilon$, a contradiction. ∎

We now come to the stratification of bond graphs. The following lemma allows
to reduce the problem of crystallization to a purely geometric problem of
minimizing the number of strata in graphs containing only open strata with
small angle excess.

######  Lemma 3.7.

(Construction of a graph with small angle excess) Let $G=(V,E)$ be
$\varepsilon$-regular. Then, there exists $G_{\mathrm{o}}=(V,E_{\mathrm{o}})$
with $E_{\mathrm{o}}\subset E$ such that

  * (i)

$\max_{\gamma\in\Gamma(G_{\mathrm{o}})}\theta_{\mathrm{ex}}(\gamma)<\frac{\pi}{6}-\varepsilon$
;

  * (ii)

$G_{\mathrm{o}}$ satisfies

$\displaystyle F(G)\geq
F_{\mathrm{bond}}(G_{\mathrm{o}})\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\,$

with equality only if $E=E_{\mathrm{o}}$, $|x-y|=1$ for all $x\in V$,
$y\in\mathcal{N}(x,E)$, and $\theta\in\\{\pi/2,\pi,3\pi/2\\}$ for all bond
angles $\theta$.

###### Proof.

We construct $G_{\mathrm{o}}=(V,E_{\mathrm{o}})$ by iteratively erasing edges.
We start by setting $G^{0}=(V,E)$ and we suppose that $G^{k}=(V,E^{k})$ is
already given. We construct $G^{k+1}=(V,E^{k+1})$ by suitably modifying the
set of edges $E^{k}$. If (i) is satisfied, we may stop. Thus, we assume that
there exists $\gamma\in\Gamma(G_{k})$ such that
$\theta_{\mathrm{ex}}(\gamma)\geq\pi/6-\varepsilon$. Let
$\gamma_{k}\in\Gamma(G_{k})$ be minimal (w.r.t. set inclusion) such that
$\theta_{\mathrm{ex}}(\gamma_{k})\geq\pi/6-\varepsilon$, i.e.,
$\gamma_{k}=\\{x_{1},x_{2},\ldots,x_{N-1},x_{N}\\}$ and
$\hat{\gamma}_{k}:=\\{x_{2},\ldots,x_{N-1}\\}$ satisfies
$\theta_{\mathrm{ex}}(\hat{\gamma}_{k})<\pi/6-\varepsilon$. We define
$E^{k+1}:=E^{k}\setminus(\\{x_{1},x_{2}\\}\cup\\{x_{N-1},x_{N}\\})$ and
$G^{k+1}=(V,E^{k+1})$. Then,

$\displaystyle\sum_{x\in V}(4-\\#\mathcal{N}(x,E^{k+1}))=4+\sum_{x\in
V}(4-\\#\mathcal{N}(x,E^{k}))\,.$ (3.7)

Additionally, due to ($\rm iii_{3}$), with $L:=4(\pi/6-\varepsilon)^{-1}>0$ we
have

$\displaystyle\sum_{j=2}^{N-1}v_{3}(\theta_{j})>L\sum_{j=2}^{N-1}|\theta_{j}-\pi|\geq
L(\pi/6-\varepsilon)=4\,.$ (3.8)

Therefore, due to (3.7) and (3.8), we have that

$\displaystyle
F_{\mathrm{ex}}(\gamma_{k})+F_{\mathrm{bond}}(G^{k})>F^{\mathrm{bond}}(G^{k+1})\,,$
(3.9)

where $F_{\mathrm{ex}}(\gamma_{k})$ is defined in (3.1). Since $G=(V,E)$ is
finite, the procedure terminates for some $K\in\mathbb{N}$ and we set
$G_{\mathrm{o}}:=(V,E^{K})$. By construction, $G_{\mathrm{o}}$ satisfies (i).
It remains to show (ii). Note that, due to the minimal selection of
$\gamma_{k}\in\Gamma$, once $\gamma_{k}$ is selected this way, we will not
select any $\gamma^{\prime}\subset\gamma_{k}$ in any successive step $j>k$.
Thus, using (3.9) and the previous observation, we have

$\displaystyle\begin{split}F_{\mathrm{ex}}(G)+F_{\mathrm{bond}}(G)&=F_{\mathrm{ex}}(G^{0})+E_{\mathrm{bond}}(G^{0})\geq\sum_{k=0}^{K-1}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}F_{\mathrm{ex}}(\gamma_{k})+E_{\mathrm{bond}}(G^{0})\\\
&\geq F_{\mathrm{bond}}(G^{K})=F_{\mathrm{bond}}(G_{\mathrm{o}})\,\end{split}$
(3.10)

with strict inequality whenever $K\geq 1$. In particular, if equality holds in
(3.10), we have that $G_{\mathrm{o}}=G$. This necessarily gives
$F_{\mathrm{ex}}(G)=0$ which implies that $|x-y|=1$ for all $x\in
V,y\in\mathcal{N}(x,E)$, and $\theta\in\\{\pi/2,\pi,3\pi/2\\}$ for all bond
angles by ($\rm{i}_{2}$) and ($\rm{ii}_{3}$). This concludes the proof. ∎

##  4\. Proof of the main results

This section is devoted to the proofs of Theorems 2.1–2.2.

###  4.1. Crystallization

We will show that the minimum of $F$ is given by $2\lceil 2\sqrt{n}\rceil$,
and that it is attained by subsets of $\mathbb{Z}^{2}$. In view of (3.3), this
shows Theorem 2.1. Recall the definition of $G_{\mathrm{nat}}$ in (3.2). We
first state the following upper bound.

######  Lemma 4.1.

(Upper bound) Let $C_{n}$ be a minimizer of (2.1). Then, $G_{\mathrm{nat}}$
satisfies

$\displaystyle F(G_{\mathrm{nat}})\leq 2\lceil 2\sqrt{n}\rceil\,.$

###### Proof.

The statement is obtained by direct construction of configurations $C_{n}$
with $C_{n}\subset\mathbb{Z}^{2}$ satisfying the energy bound. We refer to
[33, Section 4] for details, see also Figure 2. ∎

The core of the proof now consists in proving a lower bound.

###### Proof of Theorem 2.1.

Let $C_{n}$ be a minimizer of (2.1). Then $G_{\mathrm{nat}}$ is
$\varepsilon$-regular by Lemma 3.2. We denote by
$G_{\mathrm{o}}=(V,E_{\mathrm{o}})$ the graph obtained in Lemma 3.7. The graph
$G_{\mathrm{o}}$ is also $\varepsilon$-regular and satisfies

$\displaystyle\max_{\gamma\in\Gamma(G_{o})}\theta_{\mathrm{ex}}(\gamma)<\pi/6-\varepsilon\,.$
(4.1)

The main part of the proof consists in verifying

$\displaystyle F_{\mathrm{bond}}(G_{\mathrm{o}})\geq 2\lceil 2\sqrt{n}\rceil.$
(4.2)

Once (4.2) is proven, we conclude as follows. First, (2.2) holds due to Lemma
3.7(ii) and (3.3). To characterize the equality case, we get from Lemma 3.7
that $G=G_{\mathrm{o}}$, that all bond lengths are $1$, and all bond angles
lie in $\\{\pi/2,\pi,3/2\pi\\}$. This shows that each connected component (in
the sense of graph theory) of $G$ lies in a rotated and shifted version of
$\mathbb{Z}^{2}$. If there existed more than one connected component, one
could obtain a modified configuration with an additional bond. This
contradicts minimality, and we therefore obtain $V\subset\mathbb{Z}^{2}$ after
a rigid motion.

We now show (4.2). In the following, we write $\mathcal{S}$ in place of
$\mathcal{S}(G_{\mathrm{o}})$ for simplicity. By Lemma 4.1, Lemma 3.3(ii), and
Lemma 3.7 we have that

$\displaystyle 2\\#\mathcal{S}=F_{\mathrm{bond}}(G_{\mathrm{o}})\leq 2\lceil
2\sqrt{n}\rceil\,.$ (4.3)

Furthermore, by Lemma 3.3(i) we have

$\displaystyle\sum_{s\in\mathcal{S}}l(s)=2n\,.$

Hence, there exists $s_{0}\in\mathcal{S}$ such that

$\displaystyle
l(s_{0})=\max_{s\in\mathcal{S}}l(s)\geq\frac{1}{\\#\mathcal{S}}\sum_{s\in\mathcal{S}}l(s)\geq\frac{2n}{\lceil
2\sqrt{n}\rceil}\,.$ (4.4)

Recall Definition 3.5 and define
$l^{v}:=\max_{s\in\mathcal{S}^{\perp}(s_{0})}l(s)$ and
$s^{v}\in\mathrm{argmax}_{s\in\mathcal{S}^{\perp}(s_{0})}l(s)$. We claim that

$\displaystyle\\#(\mathcal{S}^{\perp}(s_{0})\cup\mathcal{S}^{\perp}(s^{v}))=\\#\mathcal{S}^{\perp}(s_{0})+\\#\mathcal{S}^{\perp}(s^{v})=l(s_{0})+l^{v}.$
(4.5)

In fact, by (4.1) and Lemma 3.6(ii) we have that
$\\#\mathcal{S}^{\perp}(s_{0})=l(s_{0})$,
$\\#\mathcal{S}^{\perp}(s^{v})=l^{v}$ and, by Lemma 3.6(iii), if
$s\in\mathcal{S}^{\perp}(s_{0})$, then $s\notin\mathcal{S}^{\perp}(s^{v})$
(and vice versa). This yields (4.5). We set
$\mathrm{span}(s_{0})=\bigcup_{s^{\prime}\in\mathcal{S}^{\perp}(s_{0})}s^{\prime}\subseteq
V$ and we consider two cases:

  * (a)

$\mathrm{span}(s_{0})=V$;

  * (b)

$\mathrm{span}(s_{0})\subsetneq V$;

_Proof in case (a):_ Due to (4.5), we get

$\displaystyle\\#\mathcal{S}\geq\\#(\mathcal{S}^{\perp}(s_{0})\cup\mathcal{S}^{\perp}(s_{v}))=l^{v}+l(s_{0})\,.$

Now, since $\mathrm{span}(s_{0})=V$, we have in particular that $l(s_{0})\cdot
l^{v}\geq n$ and therefore, noting that $\lceil t\rceil<t+1$ we obtain by
Lemma 3.3(ii)

$\displaystyle F_{\mathrm{bond}}(G_{\mathrm{o}})=2\\#\mathcal{S}\geq
2(l(s_{0})+l^{v})\geq 2\left(l(s_{0})+\frac{n}{l(s_{0})}\right)\geq
4\sqrt{n}>2\lceil 2\sqrt{n}\rceil-2\,.$ (4.6)

Since $2\\#\mathcal{S}\in 2\mathbb{N}$, the previous estimate yields the claim
(4.2) in case (a).
_Proof in case (b):_ We claim that in this case we have that

$\displaystyle\\#\mathcal{S}\geq l^{v}+l(s_{0})+1\,.$ (4.7)

In fact, by definition, there exists $x\in V\setminus\mathrm{span}(s_{0})$.
Due to Lemma 3.6(iii), for $s,s^{\prime}\in\mathcal{S}^{\perp}(s^{v})$ we have
that $s\cap s^{\prime}=\emptyset$, and thus there exists at most one $s\in
S^{\perp}(s^{v})$ such that $s\cap\\{x\\}\neq\emptyset$. We also note that
$s^{\prime}\cap\\{x\\}=\emptyset$ for all
$s^{\prime}\in\mathcal{S}^{\perp}(s_{0})$. Since for all $x\in V$ there exist
two strata $s,s^{\prime}$ such that $x\in s,s^{\prime}$ (see proof of Lemma
3.3(i)), there exists at least one stratum
$s\notin\mathcal{S}^{\perp}(s_{0})\cup S^{\perp}(s^{v})$. Therefore (4.7)
follows.

We denote by
$\mathcal{S}^{\mathrm{a}}:=\mathcal{S}\setminus(\mathcal{S}^{\perp}(s_{0})\cup\mathcal{S}^{\perp}(s^{v}))$
and observe that by (4.3) and (4.5) it holds that

$\displaystyle\\#\mathcal{S}^{\mathrm{a}}=\\#\mathcal{S}-l^{v}-l(s_{0})\leq\lceil
2\sqrt{n}\rceil-l^{v}-l(s_{0})\,.$

Now, by Lemma 3.6(ii) and the choice of $s_{0}$, see (4.4), and $s^{v}$
respectively, we have $\\#\mathcal{S}^{\perp}(s_{0})=l(s_{0})$,
$\\#\mathcal{S}^{\perp}(s^{v})=l^{v}$, $l(s)\leq l(s_{0})$ for all
$s\in\mathcal{S}$, and $l(s)\leq l^{v}$ for all
$s\in\mathcal{S}^{\perp}(s_{0})$. Due to Lemma 3.3(i) and
$\mathcal{S}^{\perp}(s_{0})\cap\mathcal{S}^{\perp}(s^{v})=\emptyset$, we get

$\displaystyle 2l(s_{0})\cdot l^{v}+l(s_{0})(\lceil
2\sqrt{n}\rceil-l^{v}-l(s_{0}))\geq\sum_{s\in\mathcal{S}^{\perp}(s_{0})}l(s)+\sum_{s\in\mathcal{S}^{\perp}(s^{v})}l(s)+\sum_{s\in\mathcal{S}^{a}}l(s)=\sum_{s\in\mathcal{S}}l(s)=2n\,,$

and thus

$\displaystyle l^{v}\geq\frac{2n}{l(s_{0})}+l(s_{0})-\lceil 2\sqrt{n}\rceil.$

This together with Lemma 3.3(ii), (4.5), and $\lceil t\rceil<t+1$ implies

$\displaystyle F_{\mathrm{bond}}(G_{\mathrm{o}})$ $\displaystyle\geq
2(l^{v}+l(s_{0})+\\#\mathcal{S}^{\mathrm{a}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0})\geq
2\left(\frac{2n}{l(s_{0})}+2l(s_{0})-\lceil
2\sqrt{n}\rceil+\\#\mathcal{S}^{\mathrm{a}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\right)\geq
2\left(4\sqrt{n}-\lceil
2\sqrt{n}\rceil+\\#\mathcal{S}^{\mathrm{a}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\right)$
$\displaystyle>2\left(2\lceil 2\sqrt{n}\rceil-\lceil
2\sqrt{n}\rceil+\\#\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathcal{S}^{\mathrm{a}}-2\right)=2\lceil
2\sqrt{n}\rceil+2(\\#\mathcal{S}^{\mathrm{a}}-2)\,.$

Again, since
$2(l^{v}+l(s_{0})+\mathcal{S}^{\mathrm{a}})\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\in
2\mathbb{N}$ and, $\\#\mathcal{S}^{\mathrm{a}}\geq 1$ by (4.5)–(4.7), the
claim (4.2) follows also in case (b). This finishes the proof.

Finally, we make the following observation: the argument along with Lemma
3.7(ii) also shows that $\\#\mathcal{S}^{\mathrm{a}}\geq 2$ would induce that
$G$ is not a ground state. From this and (4.7) we deduce

$\displaystyle\\#\mathcal{S}=l^{v}+l(s_{0})+1$ (4.8)

for the number of strata of a ground state $G$ with
$\mathrm{span}(s_{0})\subsetneq V$. ∎

Estimate (4.6) is related to proving an isoperimetric inequality with respect
to the $l^{1}$-perimeter via slicing. We present a corresponding argument in
the continuum setting in Appendix B.

###  4.2. The $n^{3/4}$-law

We close with a fluctuation estimate for minimizers.

###### Proof of Theorem 2.2.

Clearly, it is enough to prove the statement for $n\geq n_{0}$ for some
$n_{0}\in\mathbb{N}$. We use the notation of the previous proof. In
particular, we choose $s_{0}$ and $l^{v}$ as done before (4.5). As each $x\in
V$ belongs to exactly two strata, by (4.3) we find that
$l(s_{0})=\max_{s\in\mathcal{S}}l(s)\leq\lceil 2\sqrt{n}\rceil$. We start by
noting that

$\displaystyle l(s_{0})\cdot l^{v}\geq n-\lceil 2\sqrt{n}\rceil.$ (4.9)

Indeed, if $\mathrm{span}(s_{0})=V$, we have $l(s_{0})\cdot l^{v}\geq n$.
Otherwise, in view of (4.8), the span missed exaclty one stratum, consisting
of at most $\lceil 2\sqrt{n}\rceil$ points.

Now, by (4.4), (4.5), and (4.9) we compute for $n$ sufficiently large

$\displaystyle 4\sqrt{n}+2\geq 2\lceil 2\sqrt{n}\rceil$
$\displaystyle=F(G)=2\\#\mathcal{S}\geq 2\big{(}l(s_{0})+l^{v}\big{)}\geq
2l(s_{0})+2\frac{n-\lceil 2\sqrt{n}\rceil}{l(s_{0})}$ $\displaystyle\geq
2l(s_{0})+2\frac{n}{l(s_{0})}-\frac{(2\sqrt{n}+1)^{2}}{n}\geq
2l(s_{0})+2\frac{n}{l(s_{0})}-5\,.$

This yields

$2l(s_{0})^{2}-(4\sqrt{n}+7)l(s_{0})+2n\leq 0\,.$

Therefore

$x_{-}\leq l(s_{0})\leq x_{+}\,,$

where

$x_{\pm}=\frac{4\sqrt{n}+7\pm\sqrt{(4\sqrt{n}+7)^{2}-16n}}{4}\,.$

Then, a short computation yields

$\displaystyle\sqrt{n}-cn^{1/4}\leq l(s_{0})\leq\sqrt{n}+cn^{1/4}$ (4.10)

for some universal $c>0$ large enough. Using again (4.9) and $l^{v}\leq
l(s_{0})$, we also find

$\displaystyle\sqrt{n}-cn^{1/4}\leq l^{v}\leq\sqrt{n}+cn^{1/4}$ (4.11)

for a larger $c>0$. In view of (4.8), we get that, up to a translation and up
to one stratum, $C_{n}$ is contained in the rectangular subset of
$\mathbb{Z}^{2}$ defined by

$R_{n}:=\big{\\{}(k_{1},k_{2})\colon\,k_{1}\in\\{1,\ldots,l(s_{0})\\},\ \
k_{2}\in\\{1,\ldots l^{v}\\}\big{\\}}\,.$

As each stratum consists of at most $\lceil 2\sqrt{n}\rceil$ points, we get

$\displaystyle\\#(C_{n}\setminus R_{n})\leq\lceil 2\sqrt{n}\rceil\,.$ (4.12)

Note that (4.10)–(4.11) imply

$\\#(R_{n}\triangle S_{n})\leq cn^{3/4}.$

Thus, recalling (4.12), to conclude it now suffices to prove that

$\displaystyle l(s_{0})\cdot l^{v}-n\leq
5\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\sqrt{n}$

for some $c>0$. Assume by contradiction that $l(s_{0})\cdot
l^{v}-n>5\sqrt{n}$. Then, since $l(s_{0})\leq\lceil 2\sqrt{n}\rceil$, we get

$\displaystyle 4\sqrt{n}+2$ $\displaystyle\geq 2\lceil
2\sqrt{n}\rceil=2\\#\mathcal{S}\geq
2\big{(}l(s_{0})+l^{v}\big{)}>2l(s_{0})+2\frac{n}{l(s_{0})}+2\frac{5\sqrt{n}}{l(s_{0})}\geq
2l(s_{0})+2\frac{n}{l(s_{0})}+\frac{5}{2}$

for $n$ large enough. Since $2l(s_{0})+2\frac{n}{l(s_{0})}\geq 4\sqrt{n}$, we
obtain a contradiction. This concludes the proof. ∎

## Acknowledgements

This work was supported by the DFG project FR 4083/3-1 and by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s
Excellence Strategy EXC 2044 -390685587, Mathematics Münster:
Dynamics–Geometry–Structure.

##  Appendix A Proof of Lemma 3.2

###### Proof of Lemma 3.2.

Let $C_{n}$ be a minimizer of (2.1). For simplicity, we write $G=(V,E)$
instead of $G_{\mathrm{nat}}=(V,E_{\mathrm{nat}})$ for the associated natural
bond graph.
Step 1. In this step, we show Definition 3.1(i), that is

$\displaystyle|x-y|\geq 1-\varepsilon\text{ for all }\\{x,y\\}\in E\,.$ (A.1)

Define

$\displaystyle M:=\max_{x\in\mathbb{R}^{2}}\\#(V\cap
B_{\frac{1}{2}(1-\varepsilon)}(x))\,.$ (A.2)

It suffices to show $M=1$. Let $x_{0}\in\mathbb{R}^{2}$ be a maximizer. After
translation of $V$, it is not restrictive to assume that $x_{0}=0$. By
assumption ($\rm{iii}_{2}$) we have

$\displaystyle\underset{\\{x,y\\}\in E}{\sum_{x,y\in
B_{\frac{1}{2}(1-\varepsilon)}}}v_{2}(|x-y|)\geq\frac{1}{2\varepsilon}M(M-1)\,.$
(A.3)

Consider the annulus
$A_{\varepsilon}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}:=B_{\frac{1}{2}(1-\varepsilon)+\sqrt{2}}\setminus
B_{\frac{1}{2}(1-\varepsilon)}\subset B_{\frac{1}{2}+\sqrt{2}}$. There exists
$N\in\mathbb{N}$ and $\\{z_{i}\\}_{i=1}^{N}\subset\mathbb{R}^{2}$ such that
for all $0<\varepsilon\leq\frac{1}{2}$

$\displaystyle A_{\varepsilon}\subset
B_{\frac{1}{2}+\sqrt{2}}\subset\bigcup_{i=1}^{N}B_{\frac{1}{4}}(z_{i})\subset\bigcup_{i=1}^{N}B_{\frac{1}{2}(1-\varepsilon)}(z_{i})\,.$

Thus, recalling (A.2), we have

$\displaystyle\\#(V\cap
A_{\varepsilon})\leq\\#\left(V\cap\bigcup_{i=1}^{N}B_{\frac{1}{2}(1-\varepsilon)}(z_{i})\right)\leq\sum_{i=1}^{N}\\#\left(V\cap
B_{\frac{1}{2}(1-\varepsilon)}(z_{i})\right)\leq NM\,.$ (A.4)

By (A.4), the definition of $M$, and ($\rm i_{2}$), ($\rm ii_{2}$) we have

$\displaystyle\underset{\\{x,y\\}\in E}{\sum_{x\in
B_{\frac{1}{2}(1-\varepsilon)},y\in
A_{\varepsilon}}}v_{2}(|x-y|)\geq-1\cdot\\#\\{(x,y)\colon x\in V\cap
B_{\frac{1}{2}(1-\varepsilon)},y\in V\cap A_{\varepsilon}\\}\geq-NM^{2}\,.$
(A.5)

We write $V\cap B_{\frac{1}{2}(1-\varepsilon)}=\\{x_{i}\\}_{i=1}^{M}$ and
consider a competitor $\hat{V}$ (with associated natural bond graph $\hat{G}$)
given by

$\displaystyle\hat{V}=(V\setminus
B_{\frac{1}{2}(1-\varepsilon)})\cup\bigcup_{i=1}^{M}\\{x_{i}+\tau_{i}\\}\,,$

where $\tau_{i}\in\mathbb{R}^{2}$ are chosen such that

$\displaystyle\mathrm{dist}(x_{i}+\tau_{i},\hat{V}\setminus\\{x_{i}+\tau_{i}\\})\geq\sqrt{2}\text{
for all }i=1,\ldots,M\,.$ (A.6)

By (A.6), ($\rm ii_{2}$), and the optimality of $G$ we have

$\displaystyle F(G)\leq F(\hat{G})$ $\displaystyle\leq
F(G)-\underset{\\{x,y\\}\in E}{\sum_{x,y\in
B_{\frac{1}{2}(1-\varepsilon)}}}v_{2}(|x-y|)-2\underset{\\{x,y\\}\in
E}{\sum_{x\in B_{\frac{1}{2}(1-\varepsilon)},y\in
A_{\varepsilon}}}v_{2}(|x-y|)\,.$ (A.7)

Now, using (A.7), (A.3), and (A.5), we obtain

$\displaystyle\frac{1}{2\varepsilon}M(M-1)\leq\underset{\\{x,y\\}\in
E}{\sum_{x,y\in
B_{\frac{1}{2}(1-\varepsilon)}}}v_{2}(|x-y|)\leq-2\underset{\\{x,y\\}\in
E}{\sum_{x\in B_{\frac{1}{2}(1-\varepsilon)},y\in
A_{\varepsilon}}}v_{2}(|x-y|)\leq 2NM^{2}\,.$

For $\varepsilon>0$ small enough ($\varepsilon<\frac{1}{8N}$ suffices), this
inequality can only be true for $M=1$. This yields (A.1) and concludes Step 1.
Step 2. In this step we prove Definition 3.1(ii), i.e., all bond angles
satisfy

$\displaystyle\theta\in[\pi/2-\varepsilon,\pi/2+\varepsilon]\cup[\pi-\varepsilon,\pi+\varepsilon]\cup[3\pi/2-\varepsilon,3\pi/2+\varepsilon]\,.$
(A.8)

In particular, for $\varepsilon<\frac{1}{10}\pi$, we then also have
$\\#\mathcal{N}(x,E)\leq 4$ for all $x\in V$ since all bond angles at $x\in V$
sum up to $2\pi$. To see (A.8), we first of all claim that

$\displaystyle\\#\mathcal{N}(x,E)\leq
4\frac{\left(\sqrt{2}+\frac{1}{2}\right)^{2}}{(1-\varepsilon)^{2}}\text{ for
all }x\in V\,.$ (A.9)

This follows by Step 1 and, due to ($\rm{ii}_{2}$), by the fact that
$B_{\frac{1}{2}(1-\varepsilon)}(y)\subset B_{\sqrt{2}+\frac{1}{2}}(x)$ for all
$y\in\mathcal{N}(x,E)$. More precisely,

$\displaystyle\big{(}\sqrt{2}+\tfrac{1}{2}\big{)}^{2}\pi=|B_{\sqrt{2}+\frac{1}{2}}(x)|\geq\sum_{y\in\mathcal{N}(x,E)}|B_{\frac{1}{2}(1-\varepsilon)}(y)|\geq\frac{1}{4}(1-\varepsilon)^{2}\pi\,\\#\mathcal{N}(x,E)\,,$

i.e., (A.9) holds. Now, (A.8) follows. In fact, if $x$ has a bond angle that
does not satisfy (A.8) we could define
$\hat{V}=(V\setminus\\{x\\})\cup\\{x+\tau\\}$ for some $\tau\in\mathbb{R}^{2}$
such that $\mathrm{dist}(x+\tau,\hat{V}\setminus\\{x+\tau\\})\geq\sqrt{2}$.
Then, by ($\rm i_{2}$), ($\rm iv_{3}$), and (A.9) we obtain a contradiction to
the minimality of $G$. Summarizing, with the choice
$\varepsilon_{0}:=\min\\{\frac{1}{10}\pi,\frac{1}{8N}\\}$, the statement
holds. ∎

##  Appendix B Proof of isoperimetric inequalities in $l^{1}$ via slicing

In this short excursion, we show how isoperimetric inequalities with respect
to the $l^{1}$-perimeter can be obtained by a slicing argument similar to the
one used in case (a) of the proof of Theorem 2.1. Indeed, our main proof was
inspired by such an argument. We present it directly in any space dimension
$d\geq 1$. First, given $m\in\mathbb{N}$ and $x\in\mathbb{R}^{m}$ we denote by
$|x|_{1}=\sum_{k=1}^{m}|x_{k}|$ its $l^{1}$-norm. Now, for a set of finite
perimeter $E\subset\mathbb{R}^{d}$, see [31], we introduce the _$l^{1}$
-perimeter_ by

$P^{d}_{l^{1}}(E)=\int_{\partial^{*}E}|\nu_{E}|_{1}\,{\rm
d}\mathcal{H}^{d-1},$

where $\nu_{E}$ denotes the measure theoretical outer normal of
$\partial^{*}E$.

######  Theorem B.1.

For each set of finite perimeter $E\subset\mathbb{R}^{d}$, $d\geq 1$, it holds
that

$P^{d}_{l^{1}}(E)\geq 2d(\mathcal{L}^{d}(E))^{1-1/d}.$

A proof of this result via slicing hinges on the following lemma, for which we
use the notation

$E_{t}=E\cap\\{(x^{\prime},t)\colon
x^{\prime}\in\mathbb{R}^{d-1}\\}\quad\quad\text{for all $t\in\mathbb{R}$}\,.$
(B.1)

######  Lemma B.2.

Suppose that $E\subset\mathbb{R}^{d}$ is a bounded set of finite perimeter.
Then,

$P^{d}_{l^{1}}(E)\geq\int_{\mathbb{R}}P^{d-1}_{l^{1}}(E_{t})\,{\rm
d}t+2\sup_{t\in\mathbb{R}}\mathcal{H}^{d-1}(E_{t}).$ (B.2)

We postpone the proof of the lemma to the end.

###### Proof of Theorem B.1.

We prove the statement by induction. The case $d=1$ is clear as each set
$E\subset\mathbb{R}$ with finite volume satisfies $P^{1}_{l^{1}}(E)\geq 2$.
Suppose that the statement holds for $d-1$ and consider
$E\subset\mathbb{R}^{d}$. Then, by Lemma B.2 and the induction hypothesis we
have

$\displaystyle P^{d}_{l^{1}}(E)$
$\displaystyle\geq\int_{\mathbb{R}}P^{d-1}_{l^{1}}(E_{t})\,{\rm
d}t+2\sup_{t\in\mathbb{R}}\mathcal{H}^{d-1}(E_{t})$
$\displaystyle\geq\int_{\mathbb{R}}2(d-1)\big{(}\mathcal{H}^{d-1}(E_{t})\big{)}^{1-1/(d-1)}\,{\rm
d}t+2\sup_{t\in\mathbb{R}}\mathcal{H}^{d-1}(E_{t})\,.$

Using the shorthand $M:=\sup_{t\in\mathbb{R}}\mathcal{H}^{d-1}(E_{t})$ and
integrating over the slices $E_{t}$ we get

$\displaystyle
P^{d}_{l^{1}}(E)\geq\int_{\mathbb{R}}2(d-1)M^{-1/(d-1)}\mathcal{H}^{d-1}(E_{t})\,{\rm
d}t+2M=2(d-1)M^{-1/(d-1)}\mathcal{L}^{d}(E)+2M\,.$

By optimizing with respect to $M$ we get $M=(\mathcal{L}^{d}(E))^{1-1/d}$, and
thus we conclude

$P^{d}_{l^{1}}(E)\geq 2d(\mathcal{L}^{d}(E))^{1-1/d}\,.$

∎

###### Proof of Lemma B.2.

We start by splitting the $l^{1}$-perimeter into

$P_{l^{1}}(E)=\int_{\partial^{*}E}|\nu_{E}|_{1}\,{\rm
d}\mathcal{H}^{d-1}=\int_{\partial^{*}E}(|\nu^{\prime}_{E}|_{1}+|(\nu_{E})_{d}|)\,{\rm
d}\mathcal{H}^{d-1},$ (B.3)

where
$\nu^{\prime}_{E}=((\nu_{E})_{1},\ldots,(\nu_{E})_{d-1})\in\mathbb{R}^{d-1}$.
Introducing the function

$\bar{g}=\frac{|\nu^{\prime}_{E}|_{1}}{\sqrt{1-|(\nu_{E})_{d}|^{2}}}\quad\text{
on $\partial^{*}E$}\,,$

the coarea formula, see [31, (18.25)], implies

$\int_{\partial^{*}E}|\nu^{\prime}_{E}|_{1}\,{\rm
d}\mathcal{H}^{d-1}=\int_{\partial^{*}E}\bar{g}\,\sqrt{1-(\nu_{E})_{d}^{2}}\,{\rm
d}\mathcal{H}^{d-1}=\int_{\mathbb{R}}\int_{(\partial^{*}E)_{t}}\bar{g}\,{\rm
d}\mathcal{H}^{d-2}{\rm d}t=\int_{\mathbb{R}}P^{d-1}_{l^{1}}(E_{t})\,{\rm
d}t,$ (B.4)

where in the last step we used the fact that
$\frac{1}{\sqrt{1-(\nu_{E})_{d}^{2}}}\nu_{E}^{\prime}\in\mathbb{R}^{d-1}$ is a
unit normal to $E_{t}$. On the other hand, using the notation
$(\partial^{*}{E})^{x^{\prime}}:=\partial^{*}E\cap\\{(x^{\prime},t):t\in\mathbb{R}\\}$
for $x^{\prime}\in\mathbb{R}^{d-1}$, by slicing properties of $BV$-functions,
we obtain

$\int_{\partial^{*}E}|(\nu_{E})_{d}|\,{\rm
d}\mathcal{H}^{d-1}=\int_{\mathbb{R}^{d-1}}\mathcal{H}^{0}\big{(}(\partial^{*}{E})^{x^{\prime}}\big{)}\,{\rm
d}\mathcal{H}^{d-1}(x^{\prime})\geq
2\sup_{t\in\mathbb{R}}\mathcal{H}^{d-1}(E_{t}),$ (B.5)

where we used that for $\mathcal{H}^{1}$-a.e. $t\in\mathbb{R}$ and
$\mathcal{H}^{d-1}$-a.e. $x^{\prime}$ with $(x^{\prime},t)\in E_{t}$ we have
$\mathcal{H}^{0}((\partial^{*}{E})^{x^{\prime}})\geq 2$. Combining the two
estimates (B.4)–(B.5), the desired results follows from (B.3). ∎

## References

  * [1] N.L. Allinger.  Molecular structure: understanding steric and electronic effects from molecular mechanics.  John Wiley & Sons  (2010).
  * [2] Y. Au Yeung, G. Friesecke, B. Schmidt.  Minimizing atomic configurations of short range pair potentials in two dimensions: crystallization in the Wulff-shape.  Calc. Var. Partial Differential Equations  44 (2012), 81–100.
  * [3] L. Bétermin, L. De Luca, M. Petrache.  Crystallization to the square lattice for a two-body potential.  Arch. Ration. Mech. Anal.  240 (2021), 987–1053.
  * [4] L. Bétermin, H. Knüpfer, F. Nolte.  Crystallization of one-dimensional alternating two-component systems.  J. Stat. Phys.  2 (2020), 803–815.
  * [5] X. Blanc, M. Lewin.  The crystallization conjecture: a review.  EMS Surv. Math. Sci.  2 (2015), 255–306.
  * [6] B. Bollobas, I. Leader.  Edge-isoperimetric inequalities in the grid.  Combinatorica  11 (1991), 299–314.
  * [7] D. C. Brydges, P. A. Martin.  Coulomb systems at low density: A review.  J. Stat. Phys.  96 (1999), 1163–1330.
  * [8] M. Cicalese, G. P. Leonardi. Maximal fluctuations on periodic lattices: an approach via quantitative Wulff inequalities.  Comm. Math. Phys.  375 (2020), 1931–1944.
  * [9] E. Davoli, P. Piovano, U. Stefanelli.  Wulff shape emergence in graphene.  Math. Models Methods Appl. Sci. (M3AS)  26 (2016), 12:2277–2310.
  * [10] E. Davoli, P. Piovano, U. Stefanelli.  Sharp $n^{3/4}$ law for the minimizers of the edge-isoperimetric problem in the triangular lattice.  J. Nonlin. Sci.  27 (2017), 627–660.
  * [11] P. Duncan, R. O’Dwyer, E. B. Procaccia. An elementary proof for the double bubble problem in $\ell^{1}$ norm. Preprint 2020, arXiv:2008.07767.
  * [12] P. Duncan, R. O’Dwyer, E. B. Procaccia. Discrete $\ell^{1}$ Double Bubble solution is at most ceiling +2 of the continuous solution. Preprint 2021, arXiv:2109.11879.
  * [13] L. De Luca, G. Friesecke.  Crystallization in two dimensions and a discrete Gauss–Bonnet Theorem.  J. Nonlinear Sci.  28 (2017), 69–90.
  * [14] W. E, D. Li.  On the crystallization of 2D hexagonal lattices.  Comm. Math. Phys.  286 (2009), 1099–1140.
  * [15] B. Farmer, S. Esedoḡlu, P. Smereka.  Crystallization for a Brenner-like potential.  Comm. Math. Phys.  349 (2017), 1029–1061.
  * [16] A. Figalli, F. Maggi, A. Pratelli.  A mass transportation approach to quantitative isoperimetric inequalities.  Inventiones mathematicae  182 (2010),167–211.
  * [17] L. Flatley, M. Taylor, A. Tarasov, F. Theil.  Packing twelve spherical caps to maximize tangencies.  J. Comput. Appl. Math.  254 (2013), 220–225.
  * [18] L. Flatley, F. Theil.  Face-centered cubic crystallization of atomistic configurations.  Arch. Ration. Mech. Anal.  218 (2015), 363–416.
  * [19] M. Friedrich, W. Górny, U. Stefanelli. The double-bubble problem on the square lattice. Preprint 2021, arXiv:2109.01697.
  * [20] M. Friedrich, L. Kreutz.  Crystallization in the hexagonal lattice for ionic dimers.  Math. Models Methods Appl. Sci. (M3AS)  29 (2019), 1853–1900.
  * [21] M. Friedrich, L. Kreutz.  Finite crystallization and Wulff shape emergence for ionic compounds in the square lattice.  Nonlinearity  33 (2020), 1240–1296.
  * [22] M. Friedrich, L. Kreutz, B. Schmidt.  Emergence of rigid polycrystals from atomistic systems with Heitmann-Radin sticky disk energy.  Arch. Ration. Mech. Anal.  240 (2021), 627–698.
  * [23] M. Friedrich, U. Stefanelli.  Crystallization in a one-dimensional periodic landscape.  J. Stat. Phys. (2020),  179 (2020), 485–501.
  * [24] G. Friesecke, F. Theil.  Molecular geometry optimization, models. In the Encyclopedia of Applied and Computational Mathematics, B. Engquist (Ed.), Springer, 2015.
  * [25] C. S. Gardner, C. Radin.  The infinite-volume ground state of the Lennard-Jones potential.  J. Stat. Phys.  20 (1979), 719–724.
  * [26] G. C. Hamrick, C. Radin.  The symmetry of ground states under perturbation.  J. Stat. Phys.  21 (1979), 601–607.
  * [27] F. Harary, H. Harborth.  Extremal animals.  J. Combin. Inform. and System Sci.  1 (1976), 1–8.
  * [28] H. Harborth. Solution to Problem 664A. Elem. Math. 29 (1974), 14–15.
  * [29] R. Heitman, C. Radin.  Ground states for sticky disks.  J. Stat. Phys.  22 (1980), 281–287.
  * [30] E. G. Lewars.  Computational Chemistry. 2nd edition, Springer, 2011.
  * [31] F. Maggi.  Sets of finite perimeter and geometric variational problems: an introduction to Geometric Measure Theory  135, Cambridge University Press, 2012.
  * [32] E. Mainini, P. Piovano, B. Schmidt, U. Stefanelli.  $N^{3/4}$ law in the cubic lattice.  J. Stat. Phys.  176 (2019), 1480–1499.
  * [33] E. Mainini, P. Piovano, U. Stefanelli.  Finite crystallization in the square lattice.  Nonlinearity  27 (2014), 717–737.
  * [34] E. Mainini, B. Schmidt. Maximal Fluctuations Around the Wulff Shape for Edge-Isoperimetric Sets in $\mathbb{Z}^{d}$: A Sharp Scaling Law.  Comm. Math. Phys.  380 (2020), 947–971.
  * [35] E. Mainini, U. Stefanelli.  Crystallization in carbon nanostructures.  Comm. Math. Phys.  328 (2014), 545–571.
  * [36] C. Radin.  The ground state for soft disks.  J. Stat. Phys.  26 (1981), 365–373.
  * [37] C. Radin.  Classical ground states in one dimension.  J. Stat. Phys.  35 (1983), 109–117.
  * [38] C. Radin.  Crystals and quasicrystals: a continuum model.  Comm. Math. Phys.  105 (1986), 385–390.
  * [39] B. Schmidt.  Ground states of the 2D sticky disc model: fine properties and $N^{3/4}$ law for the deviation from the asymptotic Wulff-shape.  J. Stat. Phys.  153 (2013), 727–738.
  * [40] F. Theil.  A proof of crystallization in two dimensions.  Comm. Math. Phys.  262 (2006), 209–236.
  * [41] W. J. Ventevogel, B. R. A. Nijboer.  On the configuration of systems of interacting atom with minimum potential energy per particle.  Phys. A  98 (1979), 274–288.
  * [42] H. J. Wagner. Crystallinity in two dimensions: a note on a paper of C. Radin. J. Stat. Phys. 33, (1983), 523–526.