# Independent sets
in discrete tori of odd sidelength

Patrick Arras and Felix Joos  Universität Heidelberg, Institut für Informatik,
Im Neuenheimer Feld 205, 69120 Heidelberg, Germany
<EMAIL_ADDRESS>
###### Abstract.

It is a well known result due to Korshunov and Sapozhenko that the hypercube
in $n$ dimensions has $(1+o(1))\cdot 2\sqrt{e}\cdot 2^{2^{n-1}}$ independent
sets. Jenssen and Keevash investigated in depth Cartesian powers of cycles of
fixed even lengths far beyond counting independent sets. They wonder to which
extent their results extend to cycles of odd length, where not even the
easiest case, counting independent sets in Cartesian powers of the triangle,
is known. In this paper, we make progress on their question by providing a
lower bound, which we believe to be tight. We also obtain a less precise lower
bound for the number of independent sets in Cartesian powers of arbitrary odd
cycles and show how to approach this question both with the cluster expansion
method as well as more directly with isoperimetric inequalities.

The research leading to these results was partially supported by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) – 428212407.

##  1\. Introduction

The hypercube $\mathbb{Z}_{2}^{n}$ is arguably among the most well-
investigated graphs because it is one of the very few explicitly constructable
graphs that are (very) sparse. In this paper, we focus on counting independent
sets. Korshunov and Sapozhenko [15] showed that there are $(1+o(1))\cdot
2\sqrt{e}\cdot 2^{2^{n-1}}$ independent sets in the hypercube. Observe that
hypercubes are bipartite graphs where each partition class has $2^{n-1}$
vertices. Hence there are $2\cdot 2^{2^{n-1}}-1$ independent sets that are a
subset of one of the partition classes, which already reveals the majority of
all independent sets. Roughly a $(\sqrt{e}-1)/\sqrt{e}$-fraction of all
independent sets contain vertices from both partition classes. Among those,
essentially all contain only very few vertices from one class and many from
the other. This is due to the fact that selecting some vertices in one class
excludes many more vertices (the neighbours of these vertices) in the other
class from being in the independent set. This structural fact plays a dominant
role in essentially all considerations regarding the number of independent
sets or colourings in Cartesian powers of graphs. Estimating the number of
neighbours of sets of vertices is another prominent topic on its own and is
captured under the umbrella of _vertex-isoperimetric inequalities_.

The problem of calculating the number of independent sets in
$\mathbb{Z}_{2}^{n}$ has been revisited and extended by many researchers [1,
3, 6, 10, 11, 14, 16]; in particular, there are also results regarding the
number of proper $q$-colourings in $\mathbb{Z}_{2}^{n}$ [5, 13]. Most
recently, Jenssen and Keevash [9] investigated the topic in great depth.
Instead of the hypercube only, they consider Cartesian powers of even cycles,
where they treat the complete graph on two vertices as the cycle on two
vertices. Then their results contain the hypercube. These graphs are usually
known as $n$-dimensional discrete tori, which we denote as
$\mathbb{Z}_{m}^{n}$ (if the base graph is a cycle of length $m$). Their
results include a way to calculate asymptotically sharp formulas for both the
number of independent sets and the number of proper $q$-colourings in tori
$\mathbb{Z}_{m}^{n}$ with $m$ even. To this end, they utilize the cluster
expansion approach from statistical physics. This method is well-established
in the field and has been exploited to answer many similar questions, most
recently in [2, 12].

Jenssen and Keevash [9] ask whether their results extend to tori that stem
from cycles of odd length. They however note that not even the number of
independent sets is asymptotically known for Cartesian powers of a triangle.
Here we make progress in answering their question and also point out why these
cases may be much more complex than the previously investigated ones.

######  Theorem 1.1.

There are at least $(1-o(1))\cdot 3\cdot 2^{n-1}\cdot
2^{3^{n-1}}\cdot\exp((3/2)^{n-1})$ independent sets in $\mathbb{Z}_{3}^{n}$.

The bound in Theorem 1.1 deserves some explanation. There are $3\cdot 2^{n-1}$
maximum independent sets (this is nontrivial; see Lemma 3.4) of order
$3^{n-1}$. Hence there are about $3\cdot 2^{n-1}\cdot 2^{3^{n-1}}$ subsets of
these sets (again, this is nontrivial, because these sets overlap; see Lemma
3.5). For the hypercube, the subsets of the two maximum independents sets give
up to a factor of $\sqrt{e}$ the correct count. For $\mathbb{Z}_{3}^{n}$,
there is a correction term of (at least) $\exp((3/2)^{n-1})$; that is, for
$\mathbb{Z}_{3}^{n}$ only a double exponentially small fraction of the
independent sets are a subset of some maximum independent set. We conjecture
that the bound in Theorem 1.1 is asymptotically tight.

The method we use for the proof of Theorem 1.1 does not work for odd
$m\geqslant 5$. Nonetheless, we are able to determine the number of maximum
independent sets in $\mathbb{Z}_{m}^{n}$ for all odd $m$. Additionally, we
provide an alternative approach that yields the following lower bound.

######  Theorem 1.2.

There are at least $2^{\lfloor m/2\rfloor
m^{n-1}}\cdot\exp((1-o(1))(m/2)^{n-1})$ independent sets in
$\mathbb{Z}_{m}^{n}$ for $m\geqslant 3$ odd.

In order to arrive at a sensible conjecture of how higher order terms in this
asymptotic behaviour might look like, we also adapt the cluster expansion
approach to our setting and calculate some initial terms.

As indicated already before, a key tool in determining the number of
independent sets in discrete tori are appropriate isoperimetric inequalities
for independent sets. We prove the following inequality, which appears to us
to be of general interest. For simplicity, consider the tori
$\mathbb{Z}_{3}^{n}$. As it turns out, these graphs are $3$-colourable and
each colour class of each $3$-colouring is of size $3^{n-1}$. Denote the three
colour classes (of some 3-colouring) by
$\mathcal{E}(0),\mathcal{E}(1),\mathcal{E}(2)$. We consider
$A\subseteq\mathcal{E}(0)$ and give a lower bound for the number of neighbours
of $A$ in $\mathcal{E}(1)$ (or $\mathcal{E}(2)$). Similar considerations can
also be made for $\mathbb{Z}_{m}^{n}$ with $m\geqslant 5$ odd.

To this end, define $\mathcal{E}_{m}^{n}(p)$ as the set of all vertices
$v=(v_{1},\ldots,v_{n})$ in $\mathbb{Z}_{m}^{n}$ that satisfy
$\sum_{i=1}^{n}v_{i}\equiv p$ mod $m$. Our isoperimetric inequalities then
take the following form.

######  Theorem 1.3.

For $m,n\in\mathbb{N}$ with $m\geqslant 3$ odd and $\ell\coloneqq\lfloor
m/2\rfloor$, consider $p\in\mathbb{Z}_{m}$ and
$A\subseteq\mathcal{E}_{m}^{n}(p)$. Setting $\alpha\coloneqq\lvert
A\rvert/m^{n-1}$, we then have

$\lvert N_{n}(A,\mathcal{E}_{m}^{n}(p\pm 1))\rvert\geqslant\lvert
A\rvert\left(1+\frac{1-\alpha}{\sqrt{\ell^{3}mn}}\right)\,.$

We remark that our inequalities are of the same type as needed for bipartite
tori. Unfortunately, for $\mathbb{Z}_{3}^{n}$ it seems crucial to prove an
appropriate lower bound for the number of neighbours in $\mathcal{E}(2)$ of an
independent set $A\subseteq\mathcal{E}(0)\cup\mathcal{E}(1)$. Here, it is
important that $A$ is independent in $\mathbb{Z}_{3}^{n}$, and incorporating
this condition appears to us as a significant complication. Finding such an
inequality would be very desirable.

The paper is structured as follows. We first fix some further notation in
Section 2. In Section 3 we prove Theorems 1.1 and 1.2. The more general
approach via cluster expansion is introduced in Section 4, and Section 5 deals
with the proof of Theorem 1.3.

##  2\. Preliminaries

Let $\mathcal{I}(G)$ denote the set of all _independent_ sets in the graph
$G$, that is all $I\subseteq V(G)$ such that $E(G[I])=\emptyset$. For
$k\in\mathbb{N}_{0}$, we also define
$\mathcal{I}_{k}(G)\coloneqq\\{I\in\mathcal{I}(G)\colon\lvert I\rvert=k\\}$.
Moreover, let $\mathcal{I}^{*}(G)\coloneqq\\{I\in\mathcal{I}(G)\colon\lvert
I\rvert\geqslant\lvert I^{\prime}\rvert\text{ for all
}I^{\prime}\in\mathcal{I}(G)\\}$ be the set of all _maximum_ independent sets
in $G$. For a vertex set $X\subseteq V(G)$, we write
$N_{G}(X)\coloneqq\bigcup_{x\in X}N_{G}(x)\setminus X$ for the _neighbourhood_
of $X$. If $Y\subseteq V(G)$ is another set, then we denote the neighbourhood
of $X$ in $Y$ as $N_{G}(X,Y)\coloneqq N_{G}(X)\cap Y$.

Let $[k]\coloneqq\\{1,\ldots,k\\}$. We are interested in $n$-dimensional
discrete tori $\mathbb{Z}_{m}^{n}$ with odd sidelength $m$. These graphs can
be defined by $V(\mathbb{Z}_{m}^{n})\coloneqq\\{0,1,\ldots,m-1\\}^{n}$ and

$\displaystyle E(\mathbb{Z}_{m}^{n})\coloneqq\\{uv\mid\text{there is
}j\in[n]\text{ such that }u_{j}$ $\displaystyle=v_{j}\pm 1\text{ mod }m$
$\displaystyle\text{ and }u_{i}$ $\displaystyle=v_{i}\text{ for all
}i\in[n]\setminus\\{j\\}\\}\,.$

All our arguments will eventually examine the limit as $n\to\infty$. For the
sake of brevity, we utilize the Landau notation $o(h(n))$ to denote any
function $j(n)$ satisfying $j(n)/h(n)\to 0$ as $n\to\infty$. This is mainly
used in statements of the form $f(n)\geqslant(1-o(1))g(n)$ to express that $g$
is an asymptotic lower bound for $f$ or as $f(n)=(1\pm o(1))g(n)$ to say that
both $f(n)\geqslant(1-o(1))g(n)$ and $f(n)\leqslant(1+o(1))g(n)$ hold.
Similarly, we write $O(h(n))$ to denote any $j(n)$ with
$\limsup_{n\to\infty}j(n)/h(n)<\infty$.

We will also make use of a standard probability tool that, depending on the
context, is known as either the FKG inequality [4] or the Harris inequality
[8]. In its most basic form, it asserts the following.

######  Lemma 2.1.

Let $k\in\mathbb{N}$ and consider the probability space
$(\\{0,1\\}^{k},\mathcal{F},\mathbb{P})$. Define the partial order $\leqslant$
on $\\{0,1\\}^{k}$ by $x^{\prime}\leqslant x$ if $x^{\prime}_{i}\leqslant
x_{i}$ for all $i\in[k]$. An event $A\in\mathcal{F}$ is called _decreasing_ if
$x^{\prime}\leqslant x$ and $x\in A$ imply $x^{\prime}\in A$. Then for any two
decreasing events $A,B\in\mathcal{F}$, we have $\mathbb{P}[A\cap
B]\geqslant\mathbb{P}[A]\mathbb{P}[B]$.

##  3\. Lower bounds

In this section, we prove the asymptotic lower bounds on
$\lvert\mathcal{I}(\mathbb{Z}_{m}^{n})\rvert$ in Theorems 1.1 and 1.2, where
$\mathcal{I}(G)$ refers to the set of independent sets in a graph $G$. We
begin with the more detailed estimate for
$\lvert\mathcal{I}(\mathbb{Z}_{3}^{n})\rvert$ in Theorem 1.1. The principal
idea behind our argument is a modification of the simplified approach used by
Sapozhenko [17] for proving the lower bound of
$\lvert\mathcal{I}(\mathbb{Z}_{2}^{n})\rvert\geqslant(1-o(1))\cdot
2\sqrt{e}\cdot 2^{2^{n-1}}$ in the hypercube, as presented by Galvin [7] in
his expository note. Recall that the hypercube possesses a unique bipartition
into two maximum independent sets. Now choose one of them as the _majority
side_ $I$ of the independent set to be constructed and select a relatively
small independent set $A$ of $k$ _defect vertices_ on the _minority side_
$\overline{I}$. Then combine $A$ with a relatively large set $B\subseteq
I\setminus N_{\mathbb{Z}_{2}^{n}}(A,I)$ to form an independent set $A\cup
B\in\mathcal{I}(\mathbb{Z}_{2}^{n})$. Essentially, the argument then comes
down to proving that this process produces all but a negligible fraction of
independent sets in the hypercube.

We would like to follow a similar strategy for $\mathbb{Z}_{m}^{n}$ with $m$
odd. We again start by selecting a maximum independent set
$I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$ as the majority side. For odd $m$,
however, there is more than two choices: We observe in Lemmas 3.2 and 3.4 that
all maximum independent sets in $\mathbb{Z}_{m}^{n}$ look the same,
partitioning $V(\mathbb{Z}_{m}^{n})$ into $m$ partition classes and selecting
$\ell\coloneqq\lfloor m/2\rfloor$ pairwise non-adjacent ones of these classes.
This part is actually true for all odd $m$ and thus is stated in full
generality.

In order to leave the maximum number of vertices in $I\setminus
N_{\mathbb{Z}_{m}^{n}}(A,I)$ as potential members of $B$, we would like to
select the $k$ defect vertices of $A$ in a way that minimizes $\lvert
N_{\mathbb{Z}_{m}^{n}}(A,I)\rvert$. One quickly finds that since $I$ comprises
$\ell$ of the $m$ partition classes, the minority side $\overline{I}$ must
contain two adjacent classes. As the vertices in these classes have the least
neighbours in $I$, choosing $A$ as an independent set in the graph
$H_{n}\subseteq\mathbb{Z}_{m}^{n}$ induced by these two classes is optimal.

Finally, this is again combined with a set $B\subseteq I\setminus
N_{\mathbb{Z}_{m}^{n}}(A,I)$ to form an independent set $A\cup
B\in\mathcal{I}(\mathbb{Z}_{m}^{n})$. When calculating the exact numbers, our
lower bound suggests that for $m=3$, the number of defects $k$ is essentially
Poisson-distributed with parameter $\lambda=(m/2)^{n-1}$. Additionally,
prescribing a minimum size for $B$ guarantees that starting out with different
maximum independent sets $I$ leads to different independent sets $A\cup B$, so
no set in $\mathcal{I}(\mathbb{Z}_{m}^{n})$ is counted multiple times. We then
obtain the desired asymptotic lower bound by summing over a sufficiently large
range of $k$ around $\lambda$.

As our first step, Lemmas 3.1, 3.2, 3.3 and 3.4 examine the size, number, and
structure of maximum independent sets in $\mathbb{Z}_{m}^{n}$ for $m$ odd.

######  Lemma 3.1.

For $m,n\in\mathbb{N}$ with $m\geqslant 2$ and $\ell\coloneqq\lfloor
m/2\rfloor$, every $I\in\mathcal{I}(\mathbb{Z}_{m}^{n})$ satisfies $\lvert
I\rvert\leqslant m^{n-1}\ell$.

###### Proof.

We proceed by induction on $n$. For $n=1$, the statement is trivial. Suppose
that for some $n>1$, every $I^{\prime}\in\mathcal{I}(\mathbb{Z}_{m}^{n-1})$
satisfies $\lvert I^{\prime}\rvert\leqslant m^{n-2}\ell$, and let
$I\in\mathcal{I}(\mathbb{Z}_{m}^{n})$ be arbitrary. Partition
$V(\mathbb{Z}_{m}^{n})$ into $V_{q}\coloneqq\\{v\in
V(\mathbb{Z}_{m}^{n})\colon v_{n}=q\\}$ for $q\in\mathbb{Z}_{m}$ and observe
that each $\mathbb{Z}_{m}^{n}[V_{q}]$ is isomorphic to $\mathbb{Z}_{m}^{n-1}$.
In particular, this partitions $I$ into $m$ subsets $I_{q}=I\cap V_{q}$, which
inherit the independence of $I$ and are thus isomorphic to independent sets
$I_{q}^{\prime}\in\mathcal{I}(\mathbb{Z}_{m}^{n-1})$. By the induction
hypothesis, these satisfy $\lvert I_{q}\rvert=\lvert
I_{q}^{\prime}\rvert\leqslant m^{n-2}\ell$ and as there are $m$ of them, we
obtain $\lvert I\rvert=\sum_{q\in\mathbb{Z}_{m}}\lvert I_{q}\rvert\leqslant
m^{n-1}\ell$. ∎

######  Lemma 3.2.

For $m,n\in\mathbb{N}$ with $m\geqslant 3$ odd, the map
$\iota_{n}\colon\mathbb{Z}_{m}\times\\{\pm
1\\}^{n-1}\to\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$ defined by

$\displaystyle\iota_{n}(q,\varepsilon_{1},\ldots,{}$
$\displaystyle\varepsilon_{n-1})$ $\displaystyle\coloneqq\Bigg{\\{}$
$\displaystyle v\in V(\mathbb{Z}_{m}^{n})\colon
v_{1}+\sum_{i=1}^{n-1}\varepsilon_{i}v_{i+1}\in\\{q,q+2,\ldots,q+m-3\\}\mod
m\Bigg{\\}}$

is well-defined and injective.

###### Proof.

We start by showing that $\iota_{n}$ is well-defined. For this, let $uv$ be an
arbitrary edge in $\mathbb{Z}_{m}^{n}$. Note that this means that $u,v$ only
differ in one coordinate, and only by 1 mod $m$. Therefore, the sums
$u_{1}+\sum_{i=1}^{n-1}\varepsilon_{i}u_{i+1}$ and
$v_{1}+\sum_{i=1}^{n-1}\varepsilon_{i}v_{i+1}$ only differ by 1 mod $m$ and as
the values $q,q+2,\ldots,q+m-3$ have pairwise differences of at least 2 mod
$m$, any $I\in\operatorname{im}(\iota_{n})$ can contain at most one of $u,v$.
Since $uv\in E(\mathbb{Z}_{m}^{n})$ was arbitrary, this proves
$\operatorname{im}(\iota_{n})\subseteq\mathcal{I}(\mathbb{Z}_{m}^{n})$.

To see that each set in $\operatorname{im}(\iota_{n})$ is indeed a maximum
independent set, partition $\mathbb{Z}_{m}^{n}$ into $V_{w}\coloneqq\\{v\in
V(\mathbb{Z}_{m}^{n})\colon(v_{2},\ldots,v_{n})=w\\}$ for all $w\in
V(\mathbb{Z}_{m}^{n-1})$. Observe that for any
$(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\in\mathbb{Z}_{m}\times\\{\pm
1\\}^{n-1}$, all vertices $v\in V_{w}$ produce the same sum
$\sum_{i=1}^{n-1}\varepsilon_{i}v_{i+1}$, so
$v_{1}+\sum_{i=1}^{n-1}\varepsilon_{i}v_{i+1}$ will cycle through all possible
values $0,\ldots,m-1$ mod $m$ as $v$ cycles through $V_{w}$. Irrespective of
$q$, exactly $\ell\coloneqq\lfloor m/2\rfloor$ of these values belong to
$\\{q,q+2,\ldots,q+m-3\\}$, which shows that
$\lvert\iota_{n}(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\cap
V_{w}\rvert=\ell$ for all $w\in V(\mathbb{Z}_{m}^{n-1})$. It is now easy to
see that

$\lvert\iota_{n}(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\rvert=\sum_{w\in
V(\mathbb{Z}_{m}^{n-1})}\lvert\iota_{n}(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\cap
V_{w}\rvert=m^{n-1}\ell$

and
$\iota(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$
follows by Lemma 3.1.

To see that $\iota_{n}$ is injective, let
$(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\neq(q^{\prime},\varepsilon^{\prime}_{1},\ldots,\varepsilon^{\prime}_{n-1})$.
If $q\neq q^{\prime}$, then $q-q^{\prime}\mod m\in\\{1,\ldots,m-1\\}$. Without
loss of generality, let $q-q^{\prime}\mod m$ be odd, otherwise swap the roles
of $(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})$ and
$(q^{\prime},\varepsilon^{\prime}_{1},\ldots,\varepsilon^{\prime}_{n-1})$ and
observe that $m$ being odd implies that $q^{\prime}-q\equiv
m-(q-q^{\prime})\mod m\in\\{1,\ldots,m-1\\}$ has a different parity than
$q-q^{\prime}\mod m$. Then
$(q,0,\ldots,0)\in\iota_{n}(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})$, but
$(q,0,\ldots,0)\notin\iota_{n}(q^{\prime},\varepsilon^{\prime}_{1},\ldots,\varepsilon^{\prime}_{n-1})$,
and so
$\iota_{n}(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\neq\iota_{n}(q^{\prime},\varepsilon^{\prime}_{1},\ldots,\varepsilon^{\prime}_{n-1})$.

If $q=q^{\prime}$, we may assume by symmetry that
$\varepsilon_{1}\neq\varepsilon^{\prime}_{1}$. Consider the vertex
$v\coloneqq(q-1,1,0,\ldots,0)\in V(\mathbb{Z}_{m}^{n})$. Then
$v_{1}+\sum_{i=1}^{n-1}\varepsilon_{i}v_{i+1}=q-1+\varepsilon_{1}$, while
$v_{1}+\sum_{i=1}^{n-1}\varepsilon^{\prime}_{i}v_{i+1}=q-1+\varepsilon^{\prime}_{1}$.
As $\varepsilon_{1}\neq\varepsilon^{\prime}_{1}\in\\{\pm 1\\}$, one of these
values is $q\in\\{q,q+2,\ldots,q+m-3\\}$ and the other is
$q-2\notin\\{q,q+2,\ldots,q+m-3\\}$. Consequently $v$ belongs to exactly one
of the sets $\iota_{n}(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})$ and
$\iota_{n}(q^{\prime},\varepsilon^{\prime}_{1},\ldots,\varepsilon^{\prime}_{n-1})$,
which shows that
$\iota_{n}(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\neq\iota_{n}(q^{\prime},\varepsilon^{\prime}_{1},\ldots,\varepsilon^{\prime}_{n-1})$.
∎

######  Lemma 3.3.

For $m,n\in\mathbb{N}$ with $m\geqslant 3$ odd, consider
$x=(q,\varepsilon_{1},\ldots,\varepsilon_{n-1}),x^{\prime}=(q^{\prime},\varepsilon^{\prime}_{1},\ldots,\varepsilon^{\prime}_{n-1})\in\mathbb{Z}_{m}\times(\pm
1)^{n-1}$. Then $\iota_{n}(x)\cap\iota_{n}(x^{\prime})=\emptyset$ implies
$q^{\prime}\equiv q\pm 1\mod m$ and $\varepsilon_{j}=\varepsilon_{j}^{\prime}$
for all $j\in[n-1]$.

###### Proof.

Suppose $\iota_{n}(x)\cap\iota_{n}(x^{\prime})=\emptyset$. Without loss of
generality, assume that $q-q^{\prime}\mod m\in\\{0,\ldots,m-1\\}$ is even,
otherwise swap the roles of $x$ and $x^{\prime}$ and observe that $m$ being
odd implies that $q^{\prime}-q\mod m\in\\{0,\ldots,m-1\\}$ has a different
parity than $q-q^{\prime}\mod m$. Now consider the vertex
$u\coloneqq(q,0,\ldots,0)\in V(\mathbb{Z}_{m}^{n})$. Since it obviously
belongs to $\iota_{n}(x)$, it must not belong to $\iota_{n}(x^{\prime})$ by
assumption, so
$u_{1}+\sum_{i=1}^{n-1}\varepsilon^{\prime}_{i}u_{i+1}=q=q^{\prime}+(q-q^{\prime})\notin\\{q^{\prime},q^{\prime}+2,\ldots,q^{\prime}+m-3\\}$
mod $m$. Subtracting $q^{\prime}$, this excludes $0,2,\ldots,m-3$ as possible
values for the even number $q-q^{\prime}\mod m\in\\{0,\ldots,m-1\\}$, leaving
only $q-q^{\prime}\equiv m-1$ mod $m$ and thus, $q^{\prime}\equiv q+1\mod m$.

Now if $\varepsilon_{1}\neq\varepsilon^{\prime}_{1}$, consider the vertex
$v\coloneqq(q-1,\varepsilon_{1},0,\ldots,0)\in V(\mathbb{Z}_{m}^{n})$. Then
$v_{1}+\sum_{i=1}^{n-1}\varepsilon_{i}v_{i+1}=q-1+\varepsilon_{1}^{2}=q\in\\{q,q+2,\ldots,q+m-3\\}$
mod $m$ and
$v_{1}+\sum_{i=1}^{n-1}\varepsilon^{\prime}_{i}v_{i+1}=q-1-\varepsilon_{1}^{2}=q-2\in\\{q+1,q+3,\ldots,q+m-2\\}=\\{q^{\prime},q^{\prime}+2,\ldots,q^{\prime}+m-3\\}$
mod $m$. This means that $v\in\iota_{n}(x)\cap\iota_{n}(x^{\prime})$. By
symmetry, the same conclusion also holds if
$\varepsilon_{j}\neq\varepsilon^{\prime}_{j}$ for some $j\in[n-1]$. Hence
$\iota_{n}(x)\cap\iota_{n}(x^{\prime})=\emptyset$ implies that
$\varepsilon_{j}=\varepsilon^{\prime}_{j}$ for all $j\in[n-1]$. ∎

######  Lemma 3.4.

For $m,n\in\mathbb{N}$ with $m\geqslant 3$ odd, the map $\iota_{n}$ from Lemma
3.2 is a bijection.

###### Proof.

We again write $\ell\coloneqq\lfloor m/2\rfloor$. It only remains to show that
$\iota_{n}$ is surjective. Recall that while proving its well-definedness in
Lemma 3.2, we already showed that $\lvert I\rvert=m^{n-1}\ell$ for every
$I\in\operatorname{im}(\iota_{n})\subseteq\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$,
so the upper bound on the size of independent sets in Lemma 3.1 is indeed
attained for every $n$. We thus know that every
$I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$ has $\lvert I\rvert=m^{n-1}\ell$.

We proceed by induction on $n$. For $n=1$, the statement is trivial. Suppose
that for some $n>1$, the function $\iota_{n-1}$ is a bijection, and let
$I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$ be arbitrary. Partition
$V(\mathbb{Z}_{m}^{n})$ into $V_{q}\coloneqq\\{v\in
V(\mathbb{Z}_{m}^{n})\colon v_{n}=q\\}$ for $q\in\mathbb{Z}_{m}$ and define
the isomorphisms
$\phi_{q}\colon\mathbb{Z}_{m}^{n}[V_{q}]\to\mathbb{Z}_{m}^{n-1},\,v\mapsto(v_{1},\ldots,v_{n-1})$.
We denote the independent set $\phi_{q}(I\cap V_{q})$ as
$I_{q}\in\mathcal{I}(\mathbb{Z}_{m}^{n-1})$ and observe that trivially,
$\lvert I\rvert=\sum_{q\in\mathbb{Z}_{m}}\lvert I_{q}\rvert$. However, the
sets $I_{q}$ can have at most $m^{n-2}\ell$ vertices by Lemma 3.1, so in order
to achieve $\lvert I\rvert=m^{n-1}\ell$, they must all be maximum independent
sets in $\mathbb{Z}_{m}^{n-1}$. The induction hypothesis therefore guarantees
that each $I_{q}$ has a preimage under $\iota_{n-1}$, which we will denote as
$x_{q}\coloneqq\iota_{n-1}^{-1}(I_{q})\in\mathbb{Z}_{m}\times\\{\pm
1\\}^{n-2}$. We refer to its first component as $p_{q}\in\mathbb{Z}_{m}$.

We now claim the following:

Except for the first component, all $x_{q}$ are identical. The first
components satisfy $p_{q}=p_{0}+q(p_{1}-p_{0})$ mod $m$ for all
$q\in\mathbb{Z}_{m}$.

Let us first prove that $\\{p_{q-1},p_{q+1}\\}=\\{p_{q}-1,p_{q}+1\\}$ mod $m$
for every $q\in\mathbb{Z}_{m}$. It is easy to see that
$\iota_{n-1}(x_{q})=I_{q}$ and $\iota_{n-1}(x_{q-1})=I_{q-1}$ must be disjoint
as otherwise, $u\in I_{q}\cap I_{q-1}$ for some $u\in V(\mathbb{Z}_{m}^{n-1})$
implies $(u,q),(u,q-1)\in I$ and contradicts $I$ being independent. Similarly,
$I_{q}\cap I_{q+1}=\emptyset$. So Lemma 3.3 guarantees that all $x_{q}$ are
identical except for their first component, for which
$\\{p_{q-1},p_{q+1}\\}\subseteq\\{p_{q}-1,p_{q}+1\\}$ mod $m$ must hold.

For a proof by contradiction, assume that $p_{q-1}=p_{q+1}=p_{q}-1$ mod $m$.
Partition $V(\mathbb{Z}_{m}^{n})$ into $V_{w}\coloneqq\\{v\in
V(\mathbb{Z}_{m}^{n})\colon(v_{1},\ldots,v_{n-1})=w\\}$ for all $w\in
V(\mathbb{Z}_{m}^{n-1})$. Observe that
$\mathbb{Z}_{m}^{n}[V_{w}]\cong\mathbb{Z}_{m}^{1}$ for all $w\in
V(\mathbb{Z}_{m}^{n-1})$. Consider now
$\tilde{w}\coloneqq(p_{q}-2,0,\ldots,0)$. We immediately observe that
$p_{q}-2\notin\\{p_{q},p_{q}+2,\ldots,p_{q}+m-3\\}$, so
$\tilde{w}\notin\iota_{n-1}(x_{q})=I_{q}=\phi_{q}(I\cap V_{q})$ and
$(\tilde{w},q)\notin I$. However, we also see that
$p_{q}-2\notin\\{p_{q}-1,p_{q}+1,\ldots,p_{q}+m-4\\}$, so
$\tilde{w}\notin\iota_{n-1}(x_{q\pm 1})=I_{q\pm 1}=\phi_{q\pm 1}(I\cap V_{q\pm
1})$ and neither $(\tilde{w},q-1)$ nor $(\tilde{w},q+1)$ belong to $I$. But
then $I\cap V_{\tilde{w}}$ must be an independent set in the path
$\mathbb{Z}_{m}^{n}[V_{\tilde{w}}]\setminus\\{(\tilde{w},q-1),(\tilde{w},q),(\tilde{w},q+1)\\}$
on $m-3$ vertices and can thus have at most $\lvert I\cap
V_{\tilde{w}}\rvert\leqslant(m-3)/2<\ell$ vertices. Summing $\lvert I\cap
V_{w}\rvert$ over all $w\in V(\mathbb{Z}_{m}^{n-1})$ then yields $\lvert
I\rvert=\sum_{w\in V(\mathbb{Z}_{m}^{n-1})}\lvert I\cap
V_{w}\rvert<m^{n-1}\ell$ in contradiction to
$I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$. The same contradiction arises when
assuming $p_{q-1}=p_{q+1}=p_{q}+1$ mod $m$ and considering
$\tilde{w}\coloneqq(p_{q}-1,0,\ldots,0)\in V(\mathbb{Z}_{m}^{n-1})$ instead.
This proves that $\\{p_{q-1},p_{q+1}\\}=\\{p_{q}-1,p_{q}+1\\}$ mod $m$ for
every $q\in\mathbb{Z}_{m}$.

The equality $p_{q}=p_{0}+q(p_{1}-p_{0})$ mod $m$ is trivially true for
$q\in\\{0,1\\}$. In general, it follows by induction on $q$: Suppose that for
some $q>0$ the claim is true for $q-1$ and $q$. Then
$\\{p_{q-1},p_{q+1}\\}=\\{p_{q}-1,p_{q}+1\\}=\\{p_{0}+q(p_{1}-p_{0})-1,p_{0}+q(p_{1}-p_{0})+1\\}$.
Recalling that $p_{1}-p_{0}\in\\{\pm 1\\}$ by Lemma 3.3, this set is exactly
$\\{p_{0}+(q-1)(p_{1}-p_{0}),p_{0}+(q+1)(p_{1}-p_{0})\\}$ and as
$p_{q-1}=p_{0}+(q-1)(p_{1}-p_{0})$ by the induction hypothesis, we must have
$p_{q+1}=p_{0}+(q+1)(p_{1}-p_{0})$. This concludes the proof of the claim
above.

Finally, we show in the following that for
$x_{0}=(p_{0},\varepsilon_{1},\ldots,\varepsilon_{n-2})$ and
$\varepsilon_{n-1}\coloneqq p_{0}-p_{1}\in\\{\pm 1\\}$ mod $m$, we have
$\iota_{n}(p_{0},\varepsilon_{1},\ldots,\varepsilon_{n-1})=I$. We prove this
equality for the respective intersections with $V_{q}=\\{v\in
V(\mathbb{Z}_{m}^{n})\colon v_{n}=q\\}$ for all $q\in\mathbb{Z}_{m}$. So let
$q\in\mathbb{Z}_{m}$ and $v\in V_{q}$ be arbitrary. Then by definition of
$\iota_{n}$, we have
$v\in\iota_{n}(p_{0},\varepsilon_{1},\ldots,\varepsilon_{n-1})\cap V_{q}$ if
and only if

$\displaystyle v_{1}+\sum_{i=1}^{n-1}\varepsilon_{i}v_{i+1}$
$\displaystyle={}$ $\displaystyle
v_{1}+\sum_{i=1}^{n-2}\varepsilon_{i}v_{i+1}+q(p_{0}-p_{1})\in\\{p_{0},p_{0}+2,\ldots,p_{0}+m-3\\}\mod
m\,.$ (3.1)

On the other hand, we have $v\in I\cap V_{q}$ if and only if
$(v_{1},\ldots,v_{n-1})\in\phi_{q}(I\cap V_{q})=I_{q}=\iota_{n-1}(x_{q})$ by
definition of $\phi_{q}$. Also note that by the claim above, $x_{0}$ and
$x_{q}$ share all but their first components, so
$x_{q}=(p_{q},\varepsilon_{1},\ldots,\varepsilon_{n-1})$. This means that
$v\in I\cap V_{q}$ is equivalent to

$v_{1}+\sum_{i=1}^{n-2}\varepsilon_{i}v_{i+1}\in\\{p_{q},p_{q}+2,\ldots,p_{q}+m-3\\}\mod
m\,.$

We can now use our claim to replace $p_{q}$ by
$p_{0}+q(p_{1}-p_{0})=p_{0}-q(p_{0}-p_{1})$. Adding $q(p_{0}-p_{1})$ to both
sides of this relation, we obtain exactly the condition in (3). This shows
that $\iota_{n}(x_{0},\varepsilon_{n-1})\cap V_{q}=I\cap V_{q}$ for all
$q\in\mathbb{Z}_{m}$ and so indeed, $\iota_{n}(x_{0},\varepsilon_{n-1})=I$
holds. As $I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$ was chosen arbitrarily,
this concludes the proof that $\iota_{n}$ is surjective and thus, a bijection.
∎

For $m=3$, we can establish an upper bound on the size of the intersection of
two maximum independent sets. Limiting this overlap is crucial to ensure that
the process described above yields different independent sets $A\cup B$ when
starting with different maximum independent sets $I$, which leads to the
factor of $3\cdot 2^{n-1}$ in the lower bound.

######  Lemma 3.5.

For $n\in\mathbb{N}$, let $I,I^{\prime}\in\mathcal{I}^{*}(\mathbb{Z}_{3}^{n})$
be distinct. Then $\lvert I\cap I^{\prime}\rvert\leqslant 3^{n-2}$.

###### Proof.

Let $(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\coloneqq\iota_{n}^{-1}(I)$
and
$(q^{\prime},\varepsilon^{\prime}_{1},\ldots,\varepsilon^{\prime}_{n-1})\coloneqq\iota_{n}^{-1}(I^{\prime})$.
Suppose $v\in I\cap I^{\prime}$, then adding and subtracting the conditions
for $v\in I$ and $v\in I^{\prime}$ yields

$2v_{1}+\sum_{i=1}^{n-1}(\varepsilon_{i}+\varepsilon^{\prime}_{i})v_{i+1}=q+q^{\prime}\mod
3\quad\text{and}\quad\sum_{i=1}^{n-1}(\varepsilon_{i}-\varepsilon^{\prime}_{i})v_{i+1}=q-q^{\prime}\mod
3\,.$

Let
$J_{+}\coloneqq\\{0\\}\cup\\{i\in[n-1]\colon\varepsilon_{i}=\varepsilon^{\prime}_{i}\\}$
and
$J_{-}\coloneqq\\{i\in[n-1]\colon\varepsilon_{i}=-\varepsilon^{\prime}_{i}\\}$.
Then this is equivalent to $2\sum_{i\in J_{+}}v_{i+1}=q+q^{\prime}$ mod $3$
and $2\sum_{i\in J_{-}}v_{i+1}=q-q^{\prime}$ mod $3$. Multiplying both
equations by $2=-1$ mod $3$, we get

$\sum_{i\in J_{+}}v_{i+1}=-q-q^{\prime}\mod 3\quad\text{and}\quad\sum_{i\in
J_{-}}v_{i+1}=-q+q^{\prime}\mod 3\,.$

Observe that trivially, $J_{+}\neq\emptyset$ and let $j_{+}\coloneqq\max
J_{+}$. Now suppose that that $J_{-}=\emptyset$. This immediately implies
$\varepsilon_{i}=\varepsilon^{\prime}_{i}$ for all $i$ and, by the second
equation above, also that $q=q^{\prime}$. Thus,
$\iota_{n}^{-1}(I)=\iota_{n}^{-1}(I^{\prime})$ in contradiction to $I\neq
I^{\prime}$. So $J_{-}$ is also nonempty and we can let $j_{-}\coloneqq\max
J_{-}$. Then for each of the $3^{n-2}$ ways to choose the entries $v_{i+1}$
for $i\in\\{0,1,\ldots,n-1\\}\setminus\\{j_{+},j_{-}\\}$, there is at most one
choice for $v_{j_{+}+1}$ and $v_{j_{-}+1}$ (namely
$v_{j_{+}+1}=-q-q^{\prime}-\sum_{i\in J_{+}\setminus\\{j_{+}\\}}v_{i+1}$ mod
$3$ and $v_{j_{-}+1}=-q+q^{\prime}-\sum_{i\in
J_{-}\setminus\\{j_{-}\\}}v_{i+1}$ mod $3$) such that $v$ is in $I\cap
I^{\prime}$. This proves that $\lvert I\cap I^{\prime}\rvert\leqslant
3^{n-2}$. ∎

This concludes our analysis of maximum independent sets in
$\mathbb{Z}_{m}^{n}$. We now turn our attention to the selection of defects
from the subgraph $H_{n}$. Here, we observe that we can essentially assume the
defects to be chosen independently as long as their number is small compared
to the square root of the number of vertices available in $H_{n}$.

######  Lemma 3.6.

For every $n\in\mathbb{N}$, let $M_{n},K_{n}\in\mathbb{N}$ and $H_{n}$ be a
graph on $M_{n}$ vertices such that $(\Delta(H_{n})+1)K_{n}^{2}\leqslant
o(M_{n})$. Then for every $k\leqslant K_{n}$, we have

$\lvert\mathcal{I}_{k}(H_{n})\rvert\geqslant(1-o(1))\frac{M_{n}^{k}}{k!}\,.$

###### Proof.

Let $\varepsilon>0$ and choose $n$ large enough to guarantee
$(\Delta(H_{n})+1)K_{n}^{2}\leqslant\varepsilon M_{n}$. Now select $k$
vertices from $H_{n}$ one after the other, excluding from the choices for the
$(i+1)$-th vertex the $i$ vertices chosen in previous steps as well as the at
most $\Delta(H_{n})i$ vertices adjacent to any vertex chosen in previous
steps. This ensures that the union of all vertices chosen is a set in
$\mathcal{I}_{k}(H_{n})$, but every such set is produced exactly $k!$ times.
Having at least $M_{n}-(\Delta(H_{n})+1)i$ choices for the $(i+1)$-th vertex,
we find that

$\lvert\mathcal{I}_{k}(H_{n})\rvert\geqslant\frac{1}{k!}\prod_{i=0}^{k-1}(M_{n}-(\Delta(H_{n})+1)i)=\frac{M_{n}^{k}}{k!}\prod_{i=0}^{k-1}\left(1-\frac{(\Delta(H_{n})+1)i}{M_{n}}\right)\,.$

Now we use the fact that $i\leqslant k\leqslant K_{n}$ and
$(\Delta(H_{n})+1)K_{n}/M_{n}\leqslant\varepsilon/K_{n}$ to obtain

$\prod_{i=0}^{k-1}\left(1-\frac{(\Delta(H_{n})+1)i}{M_{n}}\right)\geqslant\prod_{i=0}^{k-1}\left(1-\frac{\varepsilon}{K_{n}}\right)\geqslant\left(1-\frac{\varepsilon}{K_{n}}\right)^{K_{n}}\geqslant
1-\varepsilon$

by the Bernoulli inequality. ∎

Finally, we will also use the following two immediate consequences of
Chebyshev’s inequality, applying it to a symmetric binomial and a Poisson
distribution, respectively. Together, they allow us to bring the final lower
bound into a closed form.

######  Lemma 3.7.

For all $\varepsilon>0$, there exists an $n_{0}\in\mathbb{N}$ such that for
all $n\geqslant n_{0}$ and all $y\in\mathbb{N}$, the following holds:

$2^{-y}\sum_{b=y/2-n\sqrt{y/4}}^{y/2+n\sqrt{y/4}}\begin{pmatrix}y\\\
b\end{pmatrix}\geqslant 1-\varepsilon\,.$

######  Lemma 3.8.

For all $\varepsilon>0$, there exists an $n_{0}\in\mathbb{N}$ such that for
all $n\geqslant n_{0}$ and all $\lambda>0$, the following holds:

$\exp(-\lambda)\sum_{k=\lambda-n\sqrt{\lambda}}^{\lambda+n\sqrt{\lambda}}\frac{\lambda^{k}}{k!}\geqslant
1-\varepsilon\,.$

We can now combine all of this to prove the desired asymptotic lower bound of
at least $(1-o(1))\cdot 3\cdot 2^{n-1}\cdot 2^{3^{n-1}}\cdot\exp((3/2)^{n-1})$
independent sets in $\mathbb{Z}_{3}^{n}$.

###### Proof of Theorem 1.1.

Let
$x\coloneqq(q,\varepsilon_{1},\ldots,\varepsilon_{n-1})\in\mathbb{Z}_{3}\times\\{\pm
1\\}^{n-1}$ be arbitrary and set $I\coloneqq\iota_{n}(x)$ as well as
$U\coloneqq\\{v\in V(\mathbb{Z}_{3}^{n})\colon
v_{1}+\sum_{i=1}^{n-1}\varepsilon_{i}v_{i+1}\in\\{q-2,q-1\\}\mod
3\\}=V(\mathbb{Z}_{3}^{n})\setminus I$. Now consider the graph
$H_{n}\coloneqq\mathbb{Z}_{3}^{n}[U]$ on $M_{n}\coloneqq 2\cdot 3^{n-1}$
vertices. It is easy to see that $H_{n}$ is $n$-regular, so we have
$\Delta(H_{n})=n$. Let $\lambda\coloneqq(3/2)^{n-1}$ and
$K_{n}\coloneqq\lambda+n\sqrt{\lambda}$. Then we immediately observe that
$(\Delta(H_{n})+1)K_{n}^{2}\leqslant
O(n\lambda^{2})=O(n(9/4)^{n})=o(3^{n})=o(M_{n})$. Selecting any
$k\in[\lambda-n\sqrt{\lambda},K_{n}]$, we thus have
$\lvert\mathcal{I}_{k}(H_{n})\rvert\geqslant(1-o(1))\frac{M_{n}^{k}}{k!}$ by
Lemma 3.6.

Now consider some set $A\in\mathcal{I}_{k}(H_{n})$. As every vertex in
$A\subseteq U$ has exactly $n$ edges to $I$, we have $\lvert
N_{\mathbb{Z}_{3}^{n}}(A,I)\rvert\leqslant n\lvert A\rvert=nk$. Let
$y\coloneqq 3^{n-1}-nk$ and select some $B\in I\setminus
N_{\mathbb{Z}_{3}^{n}}(A,I)$ with $\lvert
B\rvert\in[y/2-n\sqrt{y/4},y/2+n\sqrt{y/4}]$. Then $A\cup
B\in\mathcal{I}(\mathbb{Z}_{3}^{n})$ by construction and the number of
distinct such $A\cup B$ is at least

$\displaystyle\sum_{k=\lambda-n\sqrt{\lambda}}^{\lambda+n\sqrt{\lambda}}\lvert\mathcal{I}_{k}(H_{n})\rvert\sum_{b=y/2-n\sqrt{y/4}}^{y/2+n\sqrt{y/4}}\begin{pmatrix}y\\\
b\end{pmatrix}$
$\displaystyle\geqslant(1-o(1))\sum_{k=\lambda-n\sqrt{\lambda}}^{\lambda+n\sqrt{\lambda}}\frac{M_{n}^{k}\cdot
2^{y}}{k!}$ $\displaystyle=(1-o(1))\cdot
2^{3^{n-1}}\sum_{k=\lambda-n\sqrt{\lambda}}^{\lambda+n\sqrt{\lambda}}\frac{(2\cdot
3^{n-1})^{k}\cdot 2^{-nk}}{k!}$ $\displaystyle=(1-o(1))\cdot
2^{3^{n-1}}\sum_{k=\lambda-n\sqrt{\lambda}}^{\lambda+n\sqrt{\lambda}}\frac{\lambda^{k}}{k!}$
$\displaystyle\geqslant(1-o(1))\cdot
2^{3^{n-1}}\exp\left(\left(\tfrac{3}{2}\right)^{n-1}\right)$

by Lemmas 3.7 and 3.8.

As $I\in\mathcal{I}^{*}(\mathbb{Z}_{3}^{n})$ was arbitrary, we can actually
obtain the $\lvert\mathcal{I}^{*}(\mathbb{Z}_{3}^{n})\rvert$-fold of this
bound, which is exactly the desired statement, if we can show that an
independent set $A\cup B$ produced by the above process starting from
$I\in\mathcal{I}^{*}(\mathbb{Z}_{3}^{n})$ cannot also be written as
$A^{\prime}\cup B^{\prime}$ produced starting from
$I^{\prime}\in\mathcal{I}^{*}(\mathbb{Z}_{3}^{n})\setminus\\{I\\}$. For a
proof by contradiction, suppose this were false and $A\cup B=A^{\prime}\cup
B^{\prime}$. Then we would have

$\lvert I\cap I^{\prime}\rvert\geqslant\lvert B\cap
B^{\prime}\rvert\geqslant\lvert B\rvert-\lvert A^{\prime}\rvert\geqslant
y/2-n\sqrt{y/4}-K_{n}\geqslant 3^{n-1}/2-o(3^{n})$

and could ensure $\lvert I\cap I^{\prime}\rvert\geqslant 3^{n-1}/3=3^{n-2}$ by
choosing $n$ sufficiently large. This, however, contradicts Lemma 3.5 and thus
finishes the proof. ∎

A first natural guess would be to assume that the cases $m\geqslant 5$ can be
treated similarly as for $m=3$. However, for most independent sets, the number
of defects becomes so large that when choosing them as an independent subset
of the graph $H_{n}$ induced by two adjacent partition classes, we cannot
essentially ignore the edges between these two classes anymore. In the
terminology of Lemma 3.6, this graph $H_{n}$ has $M_{n}=2m^{n-1}$ vertices,
while we need to allow defect sets of size up to $K_{n}\geqslant(m/2)^{n-1}$.
This violates the assumption $(\Delta(H_{n})+1)K_{n}^{2}\leqslant o(M_{n})$ of
Lemma 3.6 for $m\geqslant 5$.

For general odd $m$, we therefore only derive a less precise lower bound. Its
proof relies on the following lemma, which functions as a rough lower bound on
the number of independent sets $A$ in the graph $H=H_{n}$.

######  Lemma 3.9.

Let $H$ be a graph and $\lambda\in(0,1/2]$. Then for
$p\coloneqq\lambda/(1+\lambda)$, we have

$\sum_{A\in\mathcal{I}(H)}\lambda^{\lvert
A\rvert}\geqslant\frac{(1-p^{2})^{\lvert E(H)\rvert}}{(1-p)^{\lvert
V(H)\rvert}}\geqslant\exp\left(p\lvert V(H)\rvert-2p^{2}\lvert
E(H)\rvert\right)\,.$

###### Proof.

Consider the random subset $X\subseteq V(H)$ that arises from selecting every
vertex of $H$ independently with probability $p$. We calculate the probability
of $X$ being independent in two different ways. On the one hand, we have

$\displaystyle\mathbb{P}[X\in\mathcal{I}(H)]=\sum_{A\in\mathcal{I}(H)}\mathbb{P}[X=A]$
$\displaystyle=\sum_{A\in\mathcal{I}(H)}p^{\lvert A\rvert}(1-p)^{\lvert
V(H)\rvert-\lvert A\rvert}$ $\displaystyle=(1-p)^{\lvert
V(H)\rvert}\sum_{A\in\mathcal{I}(H)}\left(\frac{p}{1-p}\right)^{\lvert
A\rvert}\,.$

Observe that $p/(1-p)=\lambda$. On the other hand, we can also consider all
the edges $uv\in E(H)$ and calculate the probability that for none of them,
both endpoints belong to $X$. This yields

$\displaystyle\mathbb{P}[X\in\mathcal{I}(H)]=\mathbb{P}\left[\bigcap_{uv\in
E(H)}\\{u\in X\wedge v\in X\\}^{c}\right]$ $\displaystyle\geqslant\prod_{uv\in
E(H)}(1-\mathbb{P}[u\in X\wedge v\in X])$ $\displaystyle=(1-p^{2})^{\lvert
E(H)\rvert}\,,$

where we have fixed an enumeration of $V(H)=\\{v_{1},\ldots,v_{k}\\}$ and
identified $X\subseteq V(H)$ with $x\in\\{0,1\\}^{k}$ defined by $x_{i}=1$ if
$v_{i}\in X$, so we can repeatedly apply Lemma 2.1. Note that the partial
order $\leqslant$ on $\\{0,1\\}^{k}$ is just the subset relation and for all
$E\subseteq E(H)$, the event $\bigcap_{uv\in E}\\{u\in X\wedge v\in X\\}^{c}$
is decreasing. Combining both observations proves the first statement claimed.

In order to obtain the second inequality, we note that $p,p^{2}\in(0,1/2)$
since $0<p<\lambda$. This allows us to use the geometric series to calculate

$\frac{1}{1-p}=\sum_{i=0}^{\infty}p^{i}\geqslant\sum_{i=0}^{\infty}\frac{p^{i}}{i!}=e^{p}$

and also bound $\ln\left((1-p^{2})^{\lvert E(H)\rvert}\right)=\lvert
E(H)\rvert\ln(1-p^{2})$ from below using

$\ln(1-p^{2})=\sum_{k=1}^{\infty}(-1)^{k+1}\frac{(-p^{2})^{k}}{k}=-\sum_{k=1}^{\infty}\frac{p^{2k}}{k}\geqslant-\sum_{k=1}^{\infty}p^{2k}=-\frac{p^{2}}{1-p^{2}}\geqslant-2p^{2}\,.$

This finishes the proof. ∎

We are now ready to prove Theorem 1.2. Recall that we need to show that for
$n,m\in\mathbb{N}$ with $m$ odd and $\ell\coloneqq\lfloor m/2\rfloor$, we have

$\lvert\mathcal{I}(\mathbb{Z}_{m}^{n})\rvert\geqslant 2^{\ell
m^{n-1}}\exp\left((1-o(1))\left(\frac{m}{2}\right)^{n-1}\right)\,.$

###### Proof of Theorem 1.2.

Fix a maximum independent set $I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$ and
let $H\subseteq\mathbb{Z}_{m}^{n}$ be the subgraph induced by the two adjacent
partition classes in $\overline{I}$. We can obviously obtain a set of pairwise
distinct independent sets in $\mathbb{Z}_{m}^{n}$ by considering all
combinations $A\cup B$ of $A\in\mathcal{I}(H)$ and $B\subseteq I\setminus
N_{\mathbb{Z}_{m}^{n}}(A,I)$. As $\lvert
N_{\mathbb{Z}_{m}^{n}}(A,I)\rvert\leqslant\sum_{a\in A}\lvert
N_{\mathbb{Z}_{m}^{n}}(a,I)\rvert\lvert A\rvert=n\lvert A\rvert$, we obtain

$\lvert\mathcal{I}(\mathbb{Z}_{m}^{n})\rvert\geqslant\sum_{A\in\mathcal{I}(H)}2^{\lvert
I\setminus
N_{\mathbb{Z}_{m}^{n}}(A,I)\rvert}\geqslant\sum_{A\in\mathcal{I}(H)}2^{\ell
m^{n-1}-n\lvert A\rvert}=2^{\ell
m^{n-1}}\sum_{A\in\mathcal{I}(H)}(2^{-n})^{\lvert A\rvert}\,.$

We now apply Lemma 3.9 with $\lambda\coloneqq 2^{-n}$ and $p\coloneqq
2^{-n}/(1+2^{-n})$, which satisfies $(1-o(1))2^{-n}\leqslant p\leqslant
2^{-n}$. We observe that $\lvert V(H)\rvert=2m^{n-1}$ and $\lvert
E(H)\rvert=nm^{n-1}$, so we obtain

$\sum_{A\in\mathcal{I}(H)}(2^{-n})^{\lvert A\rvert}\geqslant\exp\left(p\lvert
V(H)\rvert-2p^{2}\lvert E(H)\rvert\right)=\exp\left(2pm^{n-1}(1-pn)\right)\,.$

The statement follows from $2pm^{n-1}\geqslant(1-o(1))(m/2)^{n-1}$ and
$pn\leqslant n2^{-n}\leqslant o(1)$. ∎

Note that in contrast to Theorem 1.1, the lower bound in Theorem 1.2 does not
contain a factor of $m\cdot 2^{n-1}$ representing the choice of
$I\in\mathcal{I}(\mathbb{Z}_{m}^{n})$ anymore. This is due to the fact that
$m\cdot 2^{n-1}=o(\exp((m/2)^{n}))$, so the lost factor is anyway smaller than
the error allowed in Theorem 1.2.

##  4\. Cluster Expansion

One of the most powerful tools for counting independent sets is the cluster
expansion from statistical physics. In particular, it is often able to yield
much more detailed asymptotic formulas for the number of independent sets in a
graph. Since the method is quite well-established, we omit the technical
details and instead focus on how to employ this method in the current setting.
We first introduce the polymer model $\mathcal{P}(\mathbb{Z}_{m}^{n},I)$ and
establish its connection to $\lvert\mathcal{I}(\mathbb{Z}_{m}^{n})\rvert$,
before we direct our attention to the clusters and actually calculate some
initial terms of the cluster expansion.

###  4.1. The polymer model

Let $G$ be a graph and fix an independent set $I\in\mathcal{I}(G)$. We say
that a set $S\subseteq\overline{I}\coloneqq V(G)\setminus I$ is _$(2,I)$
-linked_ if $G[S\cup N_{G}(S,I)]$ is connected. We define the following
_polymer model_ $\mathcal{P}(G,I)$: A _polymer_ is a $(2,I)$-linked subset of
$\overline{I}$ that is independent in $G$. Two polymers $S,T$ are _compatible_
if $S\cup T$ is independent in $G$, but not $(2,I)$-linked. We also write this
as $S\sim T$. The _weight_ of a polymer $S$ is defined as $w(S)\coloneqq
2^{-\lvert N_{G}(S,I)\rvert}$.

For every polymer model $\mathcal{P}$, one can consider the associated
_partition function_
$Z_{\mathcal{P}}\coloneqq\sum_{\mathcal{S}}\prod_{S\in\mathcal{S}}w(S)$, where
the sum is over all sets $\mathcal{S}$ of pairwise compatible polymers. In the
case of the polymer model $\mathcal{P}=\mathcal{P}(G,I)$ defined above, this
partition function is actually counting independent sets in $G$.

######  Lemma 4.1.

Let $G$ be a graph and $I\in\mathcal{I}(G)$. Then
$\lvert\mathcal{I}(G)\rvert=2^{\lvert I\rvert}Z_{\mathcal{P}(G,I)}$.

###### Proof.

For every independent set in $G$, there is exactly one way to write it as the
union $A\cup B$ of $A\in\mathcal{I}(G[\overline{I}])$ and $B\subseteq
I\setminus N_{G}(A,I)$. This yields

$\lvert\mathcal{I}(G)\rvert=\sum_{A\in\mathcal{I}(G[\overline{I}])}2^{\lvert
I\rvert-\lvert N_{G}(A,I)\rvert}=2^{\lvert
I\rvert}\sum_{A\in\mathcal{I}(G[\overline{I}])}2^{-\lvert
N_{G}(A,I)\rvert}\,.$

Our next goal is to show that there is a one-to-one correspondence between
independent sets $A\in\mathcal{I}(G[\overline{I}])$ and sets $\mathcal{S}$ of
pairwise compatible polymers, which enables us to sum over all such sets
$\mathcal{S}$ instead. If $G$ is bipartite and $I,\overline{I}$ are its
partition classes (as is usually the case in the literature on
$\mathbb{Z}_{m}^{n}$ with even $m$), this is straightforward. Meanwhile, our
setting allows edges inside of $\overline{I}$ and thus requires the more
delicate polymer definition above. Therefore, a formal proof of the desired
correspondence seems warranted to us.

To this end, consider the following two functions that map independent sets
$A\in\mathcal{I}(G[\overline{I}])$ to sets $\mathcal{S}$ of pairwise
compatible polymers and vice-versa: Given an independent set
$A\in\mathcal{I}(G[\overline{I}])$, decompose the graph $G[A\cup N_{G}(A,I)]$
into its $\ell\geqslant 0$ connected components $C_{1},\ldots,C_{\ell}$ and
define $\Phi(A)\coloneqq\\{V(C_{i})\cap\overline{I}\mid i\in[\ell]\\}$. Given
a set $\mathcal{S}$ of pairwise compatible polymers, define
$\Psi(\mathcal{S})\coloneqq\bigcup_{S\in\mathcal{S}}S$.

######  Claim 4.2.

The functions $\Phi$ and $\Psi$ are well-defined and the inverse of each
other.

###### Proof of the claim.

Let $A\in\mathcal{I}(G[\overline{I}])$ be arbitrary and
$C_{1},\ldots,C_{\ell}$ be the connected components of $G[A\cup N_{G}(A,I)]$.
Since $(A\cup N_{G}(A,I))\cap\overline{I}=A$, we find that the $S_{i}\coloneqq
V(C_{i})\cap\overline{I}$ partition $A$. On the one hand, this immediately
proves that $\Psi(\Phi(A))=A$. On the other hand, this also guarantees that
the $S_{i}$ inherit from $A$ that they are subsets of $\overline{I}$ that are
independent in $G$. By construction, each $G[S_{i}\cup N_{G}(S_{i},I)]=C_{i}$
is connected, so the $S_{i}$ are indeed $(2,I)$-linked and thus polymers.

In order to see that the $S_{i}$ are also pairwise compatible, note that
$S_{i}\cup S_{j}\subseteq A$ must be independent in $G$ and thus assume that
it is still $(2,I)$-linked. This means that $G[S_{i}\cup N_{G}(S_{i},I)\cup
S_{j}\cup N_{G}(S_{j})]$ is connected and thus belongs to the same connected
component $C_{i}=C_{j}$ of $G[A\cup N_{G}(A,I)]$. As desired, $i=j$ follows.
This shows that $\Phi$ is indeed well-defined.

For the inverse direction, let $\mathcal{S}$ be a set of pairwise compatible
polymers. Then each $S\in\mathcal{S}$ is a subset of $\overline{I}$ that is
independent in $G$. Their union must therefore also be a subset of
$\overline{I}$. If it were not independent, there would be $u,v$ in distinct
$S,T\in\mathcal{S}$ with $uv\in E(G)$. However, then $S\cup T$ would not be
independent and $S,T$ would therefore not be compatible, a contradiction. This
proves that $\Psi$ is well-defined.

In order to see that $\Phi(\Psi(\mathcal{S}))=\mathcal{S}$, first note that by
compatibility, both $\Phi(\Psi(\mathcal{S}))$ and $\mathcal{S}$ partition
$A\coloneqq\Psi(\Phi(\Psi(\mathcal{S})))=\Psi(\mathcal{S})$. It therefore
suffices to show that every $S\in\mathcal{S}$ is a subset of some
$S^{\prime}\in\Phi(A)$ and vice-versa:

  * •

Let $S\in\mathcal{S}$ be arbitrary. By its $(2,I)$-linkedness, $G[S\cup
N_{G}(S,I)]$ is a connected subgraph of $G[A\cup N_{G}(A,I)]$ and must
therefore belong to a single connected component of $G[A\cup N_{G}(A,I)]$.
This shows that the intersection $(S\cup N_{G}(S,I))\cap\overline{I}=S$ is
contained in some element of $\Phi(A)$.

  * •

On the other hand, consider some connected component $C$ of $G[A\cup
N_{G}(A,I)]$ and suppose $C\cap\overline{I}$ intersects with multiple polymers
in $\mathcal{S}$. Let $S,T\in\mathcal{S}$ be two such polymers, which by
connectedness of $C$, can be chosen such that $S\cup N_{G}(S,I)$ and $T\cup
N_{G}(T,I)$ are adjacent in $G$. As $I$ is independent, any connecting edge is
either between $S$ and $T$ or establishes an intersection of $N_{G}(S,I)$ and
$N_{G}(T,I)$. Either way, it contradicts $S$ and $T$ being compatible.

This shows that $\Phi(\Psi(\mathcal{S}))=\mathcal{S}$ and thus finishes the
proof of the claim. ∎

The $(2,I)$-linkedness of every $S\in\Phi(A)$ now guarantees that the
$N_{G}(S,I)$ partition $N_{G}(A,I)$. This allows us to write

$2^{-\lvert N_{G}(A,I)\rvert}=2^{-\sum_{S\in\Phi(A)}\lvert
N_{G}(S,I)\rvert}=\prod_{S\in\Phi(A)}2^{-\lvert
N_{G}(S,I)\rvert}=\prod_{S\in\Phi(A)}w(S)\,.$

Having established in Claim 4.2 that $\Phi$ bijectively maps independent sets
$A\in\mathcal{I}(G[\overline{I}])$ to sets $\mathcal{S}$ of pairwise
compatible polymers, we conclude that

$\sum_{A\in\mathcal{I}(G[\overline{I}])}2^{-\lvert
N_{G}(A,I)\rvert}=\sum_{A\in\mathcal{I}(G[\overline{I}])}\prod_{S\in\Phi(A)}w(S)=\sum_{\mathcal{S}}\prod_{S\in\mathcal{S}}w(S)=Z_{\mathcal{P}(G,I)}\,,$

which finishes the proof. ∎

###  4.2. Cluster expansion

Let $\mathcal{P}$ be a polymer model with compatibility relation $\sim$. A
_cluster_ of $\mathcal{P}$ is a vector $\Gamma=(S_{1},S_{2},\ldots,S_{k})$ of
$k\geqslant 1$ (not necessarily distinct) polymers of $\mathcal{P}$ such that
the corresponding _incompatibility graph_ $H_{\Gamma}=([k],\\{ij\colon
S_{i}\not\sim S_{j}\\})$ is connected. The _size_ of a cluster
$\Gamma=(S_{1},S_{2},\ldots,S_{k})$ is defined as
$\lVert\Gamma\rVert\coloneqq\sum_{i=1}^{k}\lvert S_{i}\rvert$. Let
$\mathcal{C}(\mathcal{P})$ denote the (infinite) set of all clusters and write
$\mathcal{C}_{r}(\mathcal{P})\coloneqq\\{\Gamma\in\mathcal{C}(\mathcal{P})\colon\lVert\Gamma\rVert=r\\}$.
We now define the _Ursell function_ of a graph $H$ as

$\phi(H)\coloneqq\frac{1}{\lvert
V(H)\rvert!}\sum_{\begin{subarray}{c}\text{spanning, connected}\\\
\text{subgraphs $F\subseteq H$}\end{subarray}}(-1)^{\lvert E(F)\rvert}\,.$

With this, we can write the logarithm of the partition function
$Z_{\mathcal{P}}$ as the following formal power series, which is also known as
the _cluster expansion_ of $\mathcal{P}$:

$\log
Z_{\mathcal{P}}=\sum_{r=1}^{\infty}L_{r}(\mathcal{P})\qquad\text{with}\qquad
L_{r}(\mathcal{P})\coloneqq\sum_{\begin{subarray}{c}\Gamma\in\mathcal{C}_{r}(\mathcal{P})\\\
\Gamma=(S_{1},\ldots,S_{k})\end{subarray}}\phi(H_{\Gamma})\prod_{i=1}^{k}w(S_{i})\,.$

We apply this to $\mathcal{P}=\mathcal{P}(\mathbb{Z}_{m}^{n},I)$, choosing an
arbitrary maximum independent set $I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$.
This requires us to figure out the different types of clusters that exist in
this model as well as calculate their contribution to the cluster expansion.
For small $r$, this is straightforward enough to do.

######  Theorem 4.3.

For $n,m\in\mathbb{N}$ with $m\geqslant 5$ odd and
$I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$, we have

$\displaystyle L_{1}(\mathcal{P}(\mathbb{Z}_{m}^{n},I))=m^{n-1}\bigg{(}$
$\displaystyle 2\cdot 2^{-n}+\frac{m-3}{2}\cdot 2^{-2n}\bigg{)}$
$\displaystyle L_{2}(\mathcal{P}(\mathbb{Z}_{m}^{n},I))=m^{n-1}\bigg{(}$
$\displaystyle\big{(}n^{2}-2n-1\big{)}\cdot
2^{-2n}+\big{(}3n^{2}-n\big{)}\cdot 2^{-3n}$
$\displaystyle{}+\bigg{(}\frac{3m-12}{2}n^{2}+\frac{7-2m}{2}n-\frac{m-3}{4}\bigg{)}\cdot
2^{-4n}\bigg{)}\,.$

###### Proof.

By symmetry, it suffices to consider $I=\iota_{n}(1,1,\ldots,1)$. Let
$\mathcal{P}\coloneqq\mathcal{P}(\mathbb{Z}_{m}^{n},I)$ be the corresponding
polymer model and write $\mathcal{E}(p)\coloneqq\\{v\in
V(\mathbb{Z}_{m}^{n})\colon\sum_{i=1}^{n}v_{i}=p\mod m\\}$ for
$p\in\mathbb{Z}_{m}$. This means that
$I=\mathcal{E}(1)\cup\mathcal{E}(3)\cup\ldots\cup\mathcal{E}(m-2)$, while
$\overline{I}=\mathcal{E}(0)\cup\mathcal{E}(2)\cup\ldots\cup\mathcal{E}(m-1)$.
Note that vertices in $X\coloneqq\mathcal{E}(0)\cup\mathcal{E}(m-1)$ have $n$
neighbours in $I$, whereas vertices in $Y\coloneqq\overline{I}\setminus X$
have $2n$ neighbours in $I$.

For size $1$, each cluster $\Gamma=(\\{v\\})\in\mathcal{C}_{1}(\mathcal{P})$
consists of a one single-vertex polymer and has $\phi(H_{\Gamma})=1$.
Consequently, there are $2\cdot m^{n-1}$ clusters with $v\in X$ and weight
$1\cdot 2^{-n}$ as well as $\frac{m-3}{2}\cdot m^{n-1}$ clusters with $v\in Y$
and weight $1\cdot 2^{-2n}$.

For size $2$, there are nine different types of clusters
$\Gamma=(\\{v\\},\\{w\\})\in\mathcal{C}_{2}(\mathcal{P})$ that consist of two
single-vertex polymers. Their incompatibility graph $H_{\Gamma}$ is a single
edge, so $\phi(H_{\Gamma})=-\frac{1}{2}$ for all of them.

  1. (1)

$v\in X$ and $w=v$: $2\cdot m^{n-1}$ clusters of weight $-\frac{1}{2}\cdot
2^{-2n}$.

  2. (2)

$v\in Y$ and $w=v$: $\frac{m-3}{2}\cdot m^{n-1}$ clusters of weight
$-\frac{1}{2}\cdot 2^{-4n}$.

  3. (3)

$v\in\mathcal{E}(0)$ and $w=v-e_{i}$ or $v\in\mathcal{E}(m-1)$ and $w=v+e_{i}$
for $i\in[n]$: $2\cdot m^{n-1}\cdot n$ clusters of weight $-\frac{1}{2}\cdot
2^{-2n}$.

  4. (4)

$v\in X$ and $w=v+e_{i}-e_{j}$ for $i\neq j\in[n]$: $2\cdot m^{n-1}\cdot
n(n-1)$ clusters of weight $-\frac{1}{2}\cdot 2^{-2n}$.

  5. (5)

$v\in Y$ and $w=v+e_{i}-e_{j}$ for $i\neq j\in[n]$: $\frac{m-3}{2}\cdot
m^{n-1}\cdot n(n-1)$ clusters of weight $-\frac{1}{2}\cdot 2^{-4n}$.

  6. (6)

$v\in\mathcal{E}(0)\cup\mathcal{E}(m-3)$ and $w=v+2e_{i}$ or
$v\in\mathcal{E}(2)\cup\mathcal{E}(m-1)$ and $w=v-2e_{i}$ for $i\in[n]$:
$4\cdot m^{n-1}\cdot n$ clusters of weight $-\frac{1}{2}\cdot 2^{-3n}$.

  7. (7)

$v\in\mathcal{E}(2)\cup\ldots\cup\mathcal{E}(m-5)$ and $w=v+2e_{i}$ or
$v\in\mathcal{E}(4)\cup\ldots\cup\mathcal{E}(m-3)$ and $w=v-2e_{i}$ for
$i\in[n]$: $(m-5)\cdot m^{n-1}\cdot n$ clusters of weight $-\frac{1}{2}\cdot
2^{-4n}$.

  8. (8)

$v\in\mathcal{E}(0)\cup\mathcal{E}(m-3)$ and $w=v+e_{i}+e_{j}$ or
$v\in\mathcal{E}(2)\cup\mathcal{E}(m-1)$ and $w=v-e_{i}-e_{j}$ for $i\neq
j\in[n]$: $4\cdot m^{n-1}\cdot\frac{n(n-1)}{2}$ clusters of weight
$-\frac{1}{2}\cdot 2^{-3n}$.

  9. (9)

$v\in\mathcal{E}(2)\cup\ldots\cup\mathcal{E}(m-5)$ and $w=v+e_{i}+e_{j}$ or
$v\in\mathcal{E}(4)\cup\ldots\cup\mathcal{E}(m-3)$ and $w=v-e_{i}-e_{j}$ for
$i\neq j\in[n]$: $(m-5)\cdot m^{n-1}\cdot\frac{n(n-1)}{2}$ clusters of weight
$-\frac{1}{2}\cdot 2^{-4n}$.

The remaining clusters $\Gamma=(\\{v,w\\})\in\mathcal{C}_{2}(\mathcal{P})$
consist of a single two-vertex polymer and thus satisfy $\phi(H_{\Gamma})=1$.
In fact, all such polymers $\\{v,w\\}$ correspond to two clusters
$(\\{v\\},\\{w\\})$ and $(\\{w\\},\\{v\\})$ of the same type in the list
above. It is easy to see that for clusters $(\\{v\\},\\{w\\})$ of type (1),
(2), and (3), the union of their vertices is not a two-vertex polymer in
$\mathcal{P}$. For all the other types, however, $(\\{v,w\\})$ is indeed a
valid cluster in $\mathcal{C}_{2}(\mathcal{P})$. We thus obtain the number of
these clusters by dividing the number above by $2$. The weights can be
calculated by replacing $-\frac{1}{2}$ by $1$ and adding a factor of $2$ for
every shared neighbour of $v$ and $w$ in $I$.

  1. (4)

$v$ and $w$ share $v+e_{i}$ if $v\in\mathcal{E}(0)$ or $v-e_{j}$ if
$v\in\mathcal{E}(m-1)$: $m^{n-1}\cdot n(n-1)$ clusters of weight $2\cdot
2^{-2n}$.

  2. (5)

$v$ and $w$ share $v+e_{i}$ and $v-e_{j}$: $\frac{m-3}{4}\cdot m^{n-1}\cdot
n(n-1)$ clusters of weight $4\cdot 2^{-4n}$.

  3. (6)

$v$ and $w$ share $v+e_{i}$ if $v\in\mathcal{E}(0)\cup\mathcal{E}(m-3)$ or
$v-e_{i}$ if $v\in\mathcal{E}(2)\cup\mathcal{E}(m-1)$: $2\cdot m^{n-1}\cdot n$
clusters of weight $2\cdot 2^{-3n}$.

  4. (7)

$v$ and $w$ share $v+e_{i}$ if
$v\in\mathcal{E}(2)\cup\ldots\cup\mathcal{E}(m-5)$ or $v-e_{i}$ if
$v\in\mathcal{E}(4)\cup\ldots\cup\mathcal{E}(m-3)$: $\frac{m-5}{2}\cdot
m^{n-1}\cdot n$ clusters of weight $2\cdot 2^{-4n}$.

  5. (8)

$v$ and $w$ share $v+e_{i}$ and $v+e_{j}$ if
$v\in\mathcal{E}(0)\cup\mathcal{E}(m-3)$ or $v-e_{i}$ and $v-e_{j}$ if
$v\in\mathcal{E}(2)\cup\mathcal{E}(m-1)$: $2\cdot
m^{n-1}\cdot\frac{n(n-1)}{2}$ clusters of weight $4\cdot 2^{-3n}$.

  6. (9)

$v$ and $w$ share $v+e_{i}$ and $v+e_{j}$ if
$v\in\mathcal{E}(2)\cup\ldots\cup\mathcal{E}(m-5)$ or $v-e_{i}$ and $v-e_{j}$
if $v\in\mathcal{E}(4)\cup\ldots\cup\mathcal{E}(m-3)$: $\frac{m-5}{2}\cdot
m^{n-1}\cdot\frac{n(n-1)}{2}$ clusters of weight $4\cdot 2^{-4n}$.

Grouping by exponent of the $2^{-n}$-term and simplifying yields both
formulas. ∎

Note that every vertex in $\overline{I}$ has either $n$ or $2n$ edges to $I$,
so every polymer $S$ has weight $w(S)\leqslant 2^{-\lvert S\rvert n}$ and
every cluster $\Gamma\in\mathcal{C}_{r}(\mathcal{P})$ contributes at most
$O(2^{-rn})$ to $\log Z_{\mathcal{P}}$. For small $r$, the number of clusters
in $\mathcal{C}_{r}(\mathcal{P})$ is obviously bounded by $O(p_{r}(n)\cdot
m^{n})$ for some polynomial $p_{r}$, so the terms
$L_{r}(\mathcal{P}(\mathbb{Z}_{m}^{n},I))$ with $m/2^{r}<1$ become negligible
as $n\to\infty$. In order to establish convergence of the cluster expansion,
however, one has to make the same argument for arbitrarily large $r$. Since we
are unable to achieve this, the approach above only yields a conjecture on
which clusters are relevant, but falls short of a proof.

In the case of $m\in\\{5,7\\}$, we have $m/2^{3}<1$, so only clusters of size
at most $2$ should be relevant. It is also sensible to assume that starting
with distinct maximum independent sets
$I,I^{\prime}\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$ will again result in
$A\cup B\neq A^{\prime}\cup B^{\prime}$ for all but a negligible fraction of
combinations of $A\in\mathcal{I}(G[\overline{I}])$ and $B\in I\setminus
N_{G}(A,I)$ as well as $A^{\prime}\in\mathcal{I}(G[\overline{I^{\prime}}])$
and $B^{\prime}\in I^{\prime}\setminus N_{G}(A^{\prime},I^{\prime})$.
Therefore, the calculation in Theorem 4.3 together with Lemmas 3.4 and 4.1
naturally leads to the following conjecture.

######  Conjecture 4.4.

$\displaystyle\lvert\mathcal{I}(\mathbb{Z}_{5}^{n})\rvert$
$\displaystyle=(1\pm o(1))\cdot 5\cdot 2^{n-1}\cdot 2^{2\cdot
5^{n-1}}\cdot\exp\left(\left(\frac{5}{2}\right)^{n-1}+\frac{n^{2}-2n}{4}\left(\frac{5}{4}\right)^{n-1}\right)$
$\displaystyle\lvert\mathcal{I}(\mathbb{Z}_{7}^{n})\rvert$
$\displaystyle=(1\pm o(1))\cdot 7\cdot 2^{n-1}\cdot 2^{3\cdot
7^{n-1}}\cdot\exp\left(\left(\frac{7}{2}\right)^{n-1}+\frac{n^{2}-2n+1}{4}\left(\frac{7}{4}\right)^{n-1}\right)\,.$

##  5\. Isoperimetric inequalities

The reasoning behind the proof of the upper bound in [7] is actually quite
similar to the initial argument of Lemma 4.1: Having fixed a (maximum)
independent set $I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$, every independent
set in $\mathbb{Z}_{m}^{n}$ can be partitioned into its intersections $A,B$
with $\overline{I}$ and $I$, respectively. Since both inherit independence in
$\mathbb{Z}_{m}^{n}$, the former is a set
$A\in\mathcal{I}(\mathbb{Z}_{m}^{n}[\overline{I}])$. By independence of $I$,
any $B\subseteq I$ is automatically independent, but once $A$ is known, $B$
must also satisfy $B\subseteq I\setminus N_{\mathbb{Z}_{m}^{n}}(A,I)$, leaving
exactly $2^{\lvert I\rvert-\lvert N_{\mathbb{Z}_{m}^{n}}(A,I)\rvert}$ choices.
For $m\geqslant 3$ odd and $\ell\coloneqq\lfloor m/2\rfloor$, we have already
established in Section 3 that all $I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$
have the same structure, so it suffices to only look at one representative.
With the notation of Lemma 3.2, we choose
$I_{0}\coloneqq\iota_{n}(0,1,\ldots,1)$. Also using
$\lvert\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})\rvert=m\cdot 2^{n-1}$ and $\lvert
I\rvert=\ell m^{n-1}$ from Section 3, we therefore immediately observe that

$\lvert\mathcal{I}(\mathbb{Z}_{m}^{n})\rvert\leqslant\sum_{I\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})}\sum_{A\in\mathcal{I}(\mathbb{Z}_{m}^{n}[\overline{I}])}2^{\lvert
I\rvert-\lvert N_{\mathbb{Z}_{m}^{n}}(A,I)\rvert}\leqslant m\cdot 2^{n-1}\cdot
2^{\ell
m^{n-1}}\cdot\sum_{A\in\mathcal{I}(\mathbb{Z}_{m}^{n}[\overline{I_{0}}])}2^{-\lvert
N_{\mathbb{Z}_{m}^{n}}(A,I_{0})\rvert}\,.$

It remains to bound the sum on the right from above. For this, we require a
lower bound on the neighbourhood size of certain independent sets $A$. At its
core, this is asking for an isoperimetric inequality in the graph
$\mathbb{Z}_{m}^{n}$, that is some lower bound on $\lvert
N_{\mathbb{Z}_{m}^{n}}(A)\rvert$ in terms of $\lvert A\rvert$. Fixing all but
one coordinate, $\lvert N_{\mathbb{Z}_{m}^{n}}(A)\rvert\geqslant\lvert
A\rvert$ is trivial to obtain. In order to make progress towards an upper
bound, however, guaranteeing that this neighbourhood is actually slightly
larger than $A$ (for $A$ not too large) seems necessary. It is worth noting
that proving such an inequality is also the crucial step in establishing
convergence of the cluster expansion, since we again need to limit how many
independent sets $A$ can contribute a weight of $w(A)=2^{-\lvert
N_{\mathbb{Z}_{m}^{n}}(A,I)\rvert}$ to $\log
Z_{\mathcal{P}(\mathbb{Z}_{m}^{n},I)}$.

In the following, we will prove an isoperimetric inequality that constitutes
first progress towards an upper bound for $\mathcal{I}(\mathbb{Z}_{m}^{n})$
with $m\geqslant 3$ odd, but unfortunately is not strong enough yet. Our proof
adapts the approach of [9, Lemma 6.1] to the case of odd sidelength. Since in
the construction of the abovementioned maximum independent set
$I_{0}=\iota_{n}(0,1,\ldots,1)\in\mathcal{I}^{*}(\mathbb{Z}_{m}^{n})$,
vertices $v\in V(\mathbb{Z}_{m}^{n})$ are classified according to the value of
$\sum_{i=1}^{n}v_{i}$ mod $m$, it is helpful to refer to this number as the
_class_ $\operatorname{cls}(v)$ of $v$. This partitions
$V(\mathbb{Z}_{m}^{n})$ into $\mathcal{E}_{m}^{n}(p)\coloneqq\\{v\in
V(\mathbb{Z}_{m}^{n})\colon\operatorname{cls}(v)=p\\}$ for
$p\in\mathbb{Z}_{m}$. Note that with this notation, we have
$I_{0}=\mathcal{E}_{m}^{n}(0)\cup\mathcal{E}_{m}^{n}(2)\cup\ldots\cup\mathcal{E}_{m}^{n}(m-3)$.

For the sake of simplicity, we write $N_{n}$ instead of
$N_{\mathbb{Z}_{m}^{n}}$. For arbitrary subsets $A\subseteq
V(\mathbb{Z}_{m}^{n})$ and $q\in\mathbb{Z}_{m}$, we define
$A_{q}\coloneqq\\{v\in V(\mathbb{Z}_{m}^{n-1})\colon(v,q)\in A\\}$ and hence
obviously $\lvert A\rvert=\sum_{q\in\mathbb{Z}_{m}}\lvert A_{q}\rvert$. The
following lemma is the central step in our induction.

######  Lemma 5.1.

For $m,n\in\mathbb{N}$ with $m\geqslant 3$ odd, consider
$p,q\in\mathbb{Z}_{m}$ and $A\subseteq\mathcal{E}_{m}^{n}(p)$. Then

$\lvert N_{n}(A,\mathcal{E}_{m}^{n}(p\pm
1))_{q}\rvert\geqslant\max\left\\{\lvert
N_{n-1}(A_{q},\mathcal{E}_{m}^{n-1}(p-q\pm 1))\rvert,\lvert A_{q\mp
1}\rvert\right\\}\,.$

###### Proof.

By symmetry, it suffices to prove the statement for
$N_{n}(A,\mathcal{E}_{m}^{n}(p+1))_{q}$. We show that in fact, this set
contains both $N_{n-1}(A_{q},\mathcal{E}_{m}^{n-1}(p-q+1))$ and $A_{q-1}$.

For the first part, let $v\in N_{n-1}(A_{q},\mathcal{E}_{m}^{n-1}(p-q+1))$ be
arbitrary. Then there is $u\in A_{q}$ such that $uv\in
E(\mathbb{Z}_{m}^{n-1})$. This means that $(u,q)(v,q)\in
E(\mathbb{Z}_{m}^{n})$, so $(v,q)\in N_{n}(A)$. Furthermore,
$\operatorname{cls}(v)=p-q+1$ implies
$\operatorname{cls}((v,q))=\operatorname{cls}(v)+q=p+1$, so $(v,q)\in
N_{n}(A,\mathcal{E}_{m}^{n}(p+1))$ and $v\in
N_{n}(A,\mathcal{E}_{m}^{n}(p+1))_{q}$ follows.

For the second part, let $v\in A_{q-1}$ be arbitrary. Then $(v,q-1)\in A$, so
$(v,q)\in N_{n}(A)$. Furthermore, $\operatorname{cls}((v,q-1))=p$ because of
$(v,q-1)\in A\subseteq\mathcal{E}_{m}^{n}(p)$ implies
$\operatorname{cls}((v,q))=\operatorname{cls}((v,q-1))+1=p+1$, so $(v,q)\in
N_{n}(A,\mathcal{E}_{m}^{n}(p+1))$ and $v\in
N_{n}(A,\mathcal{E}_{m}^{n}(p+1))_{q}$ follows. ∎

We shall also use two further easy observations.

######  Lemma 5.2.

Let $m\in\mathbb{N}$ and $\delta>0$. Suppose
$\alpha_{0},\ldots,\alpha_{m-1}\in\mathbb{R}$ such that
$\alpha_{q-1}\leqslant\alpha_{q}+\delta$ for all $q\in\mathbb{Z}_{m}$. Then
their mean $\alpha\coloneqq\sum_{q\in\mathbb{Z}_{m}}\alpha_{q}/m$ satisfies
$\alpha_{q}\in[\alpha-\frac{m-1}{2}\delta,\alpha+\frac{m-1}{2}\delta]$ for all
$q\in\mathbb{Z}_{m}$. The same conclusion also holds if
$\alpha_{q+1}\leqslant\alpha_{q}+\delta$ for all $q\in\mathbb{Z}_{m}$.

###### Proof.

It suffices to only prove the case $\alpha_{q-1}\leqslant\alpha_{q}+\delta$ as
for $\alpha_{q+1}\leqslant\alpha_{q}+\delta$, we can consider the sequence
defined by $\alpha^{\prime}_{q}\coloneqq\alpha_{-q}$ instead. So let
$q\in\mathbb{Z}_{m}$ be arbitrary and observe that inductively,
$\alpha_{q-r}\leqslant\alpha_{q}+r\delta$ holds for all $r\geqslant 0$
(reading the indices of $\alpha_{i}$’s modulo $m$). Now calculate

$\alpha=\sum_{\tilde{q}\in\mathbb{Z}_{m}}\frac{\alpha_{\tilde{q}}}{m}=\sum_{r=0}^{m-1}\frac{\alpha_{q-r}}{m}\leqslant\sum_{r=0}^{m-1}\frac{\alpha_{q}+r\delta}{m}=\alpha_{q}+\frac{\delta}{m}\sum_{r=0}^{m-1}r=\alpha_{q}+\frac{m-1}{2}\delta\,.$

Reordering the assumption also guarantees that
$\alpha_{q+1}\geqslant\alpha_{q}-\delta$ for all $q\in\mathbb{Z}_{m}$, which
inductively yields $\alpha_{q+r}\geqslant\alpha_{q}-r\delta$ for all
$r\geqslant 0$. This allows us to obtain the inverse estimate
$\alpha=\sum_{r=0}^{m-1}\frac{\alpha_{q+r}}{m}\geqslant\alpha_{q}-\frac{\delta}{m}\sum_{r=0}^{m-1}r=\alpha_{q}-\frac{m-1}{2}\delta$
as well. Taken together, we have shown that
$\lvert\alpha-\alpha_{q}\rvert\leqslant\frac{m-1}{2}\delta$ for all
$q\in\mathbb{Z}_{m}$, which is equivalent to
$\alpha_{q}\in[\alpha-\frac{m-1}{2}\delta,\alpha+\frac{m-1}{2}\delta]$. Since
$q\in\mathbb{Z}_{m}$ was chosen arbitrary, this finishes the proof. ∎

######  Lemma 5.3.

Let $a<b$ and $g\colon[a,b]\to\mathbb{R}$ be concave. Then among all multisets
$X$ with $m\in\mathbb{N}$ elements and $\sum_{x\in X}x=m\frac{a+b}{2}$, the
minimum value of $\sum_{x\in X}g(x)$ is achieved by $\ell\coloneqq\lfloor
m/2\rfloor$ copies of $a$, $\ell$ copies of $b$, and at most one copy of
$\frac{a+b}{2}$.

###### Proof.

Concavity implies that whenever $X$ contains two values $x,y$ with
$a<x\leqslant y<b$, letting $\varepsilon\coloneqq\min\\{x-a,b-y\\}$ and
replacing $x,y$ by $x-\varepsilon$ and $y+\varepsilon$ does not increase
$\sum_{x\in X}g(x)$, while leaving $\sum_{x\in X}x$ unchanged. Inductively, we
arrive at a minimizer $X$ that contains at most one value that is neither $a$
nor $b$. Straightforward calculation then shows that it must be the one
claimed in the statement. ∎

We are now ready to prove the isoperimetric inequality. It verifies that when
we consider a set $A$ in one partition class $\mathcal{E}_{m}^{n}(p)$ and its
neighbours in one of the adjacent partition classes, then there are at least
$\frac{1-\alpha}{C_{m}\sqrt{n}}\lvert A\rvert$ additional neighbours apart
from the trivial $\lvert A\rvert$ many, where $\alpha\coloneqq\lvert
A\rvert/m^{n-1}$ is the relative size of $A\subseteq\mathcal{E}_{m}^{n}(p)$
and the constant $C_{m}\coloneqq\sqrt{\ell^{3}m}$ with $\ell\coloneqq\lfloor
m/2\rfloor$ does not depend on $A$ or $n$.

###### Proof of Theorem 1.3.

By symmetry, it suffices to prove the statement for
$N_{n}(A,\mathcal{E}_{m}^{n}(p+1))$. We proceed by induction on $n$. For
$n=1$, every class consists of a single vertex, so either $\lvert
A\rvert=\lvert N_{1}(A,\mathcal{E}_{m}^{n}(p+1))\rvert=0$ or $\lvert
A\rvert=1$, $\lvert N_{1}(A,\mathcal{E}_{m}^{n}(p+1))\rvert=1$, and
$\alpha=1$. In both cases, the inequality holds. So let $n>1$ and define
$\delta\coloneqq m\alpha(1-\alpha)/\sqrt{\ell^{3}mn}$. It is easy to see that
$A_{q}\subseteq\mathcal{E}_{m}^{n-1}(p-q)$ for every $q\in\mathbb{Z}_{m}$
because of $A\subseteq\mathcal{E}_{m}^{n}(p)$. In order to apply the induction
hypothesis to $A_{0},\ldots,A_{m-1}$, let $\alpha_{q}\coloneqq\lvert
A_{q}\rvert/m^{n-2}$ and distinguish two cases:

_Case 1:_ There is $\tilde{q}\in\mathbb{Z}_{m}$ such that
$\alpha_{\tilde{q}-1}\geqslant\alpha_{\tilde{q}}+\delta$.

We use Lemma 5.1 and the induction hypothesis to obtain the estimate

$\lvert N_{n}(A,\mathcal{E}_{m}^{n}(p+1))_{q}\rvert\geqslant\lvert
N_{n-1}(A_{q},\mathcal{E}_{m}^{n-1}(p-q+1))\rvert\geqslant\lvert A_{q}\rvert$

for all $q\in\mathbb{Z}_{m}\setminus\\{\tilde{q}\\}$. For $\tilde{q}$ itself,
we calculate

$\lvert N_{n}(A,\mathcal{E}_{m}^{n}(p+1))_{\tilde{q}}\rvert\geqslant\lvert
A_{\tilde{q}-1}\rvert=\alpha_{\tilde{q}-1}m^{n-2}\geqslant(\alpha_{\tilde{q}}+\delta)m^{n-2}=\lvert
A_{\tilde{q}}\rvert+\delta m^{n-2}\,.$

Summing up all these inequalities and plugging in the definition of $\delta$,
we obtain as desired

$\displaystyle\lvert
N_{n}(A,\mathcal{E}_{m}^{n}(p+1))\rvert=\sum_{q\in\mathbb{Z}_{m}}\lvert
N_{n}(A,\mathcal{E}_{m}^{n}(p+1))_{q}\rvert$
$\displaystyle\geqslant\sum_{q\in\mathbb{Z}_{m}}\lvert
A_{q}\rvert+\frac{m\alpha(1-\alpha)}{\sqrt{\ell^{3}mn}}m^{n-2}$
$\displaystyle=\lvert
A\rvert\left(1+\frac{1-\alpha}{\sqrt{\ell^{3}mn}}\right)\,.$

_Case 2:_ We have $\alpha_{q-1}<\alpha_{q}+\delta$ for all
$q\in\mathbb{Z}_{m}$.

Here, Lemma 5.2 implies that all $\alpha_{q}$ are within at most $\ell\delta$
of their mean, which is precisely
$\sum_{q\in\mathbb{Z}_{m}}\alpha_{q}/m=\sum_{q\in\mathbb{Z}_{m}}\lvert
A_{q}\rvert/m^{n-1}=\lvert A\rvert/m^{n-1}=\alpha$. So,
$\alpha_{q}\in[\alpha-\ell\delta,\alpha+\ell\delta]$ holds for all
$q\in\mathbb{Z}_{m}$. According to Lemma 5.1 and the induction hypothesis, we
can now bound

$\displaystyle\lvert
N_{n}(A,\mathcal{E}_{m}^{n}(p+1))\rvert=\sum_{q\in\mathbb{Z}_{m}}\lvert
N_{n}(A,\mathcal{E}_{m}^{n}(p+1))_{q}\rvert$
$\displaystyle\geqslant\sum_{q\in\mathbb{Z}_{m}}\lvert
N_{n-1}(A_{q},\mathcal{E}_{m}^{n-1}(p-q+1))\rvert$
$\displaystyle\geqslant\sum_{q\in\mathbb{Z}_{m}}\lvert
A_{q}\rvert\left(1+\frac{1-\alpha_{q}}{\sqrt{\ell^{3}m(n-1)}}\right)$
$\displaystyle=\lvert
A\rvert+\frac{m^{n-2}}{\sqrt{\ell^{3}m(n-1)}}\sum_{q\in\mathbb{Z}_{m}}\alpha_{q}(1-\alpha_{q})\,.$
(5.1)

Defining the function $g(\alpha)\coloneqq\alpha(1-\alpha)$ on the interval
$[\alpha-\ell\delta,\alpha+\ell\delta]$, we have to minimize the sum
$\sum_{q\in\mathbb{Z}_{m}}g(\alpha_{q})$ subject to the condition
$\sum_{q\in\mathbb{Z}_{m}}\alpha_{q}=m\alpha$. As $g$ is concave, Lemma 5.3
guarantees that choosing $\alpha_{0},\ldots,\alpha_{m-1}$ as $\ell$ copies of
$\alpha-\ell\delta$, $\ell$ copies of $\alpha+\ell\delta$, and one copy of
$\alpha$ itself yields the minimal value, which we calculate as

$\sum_{q\in\mathbb{Z}_{m}}g(\alpha_{q})\geqslant\ell
g(\alpha-\ell\delta)+g(\alpha)+\ell
g(\alpha+\ell\delta)=mg(\alpha)-2\ell^{3}\delta^{2}\,.$

In order to determine the relative significance of the error term
$-2\ell^{3}\delta^{2}$, we continue as follows:

$\frac{mg(\alpha)-2\ell^{3}\delta^{2}}{mg(\alpha)}=1-\frac{2\ell^{3}m^{2}\alpha^{2}(1-\alpha)^{2}}{mg(\alpha)2\ell^{3}mn}=1-\frac{2g(\alpha)}{n}\geqslant
1-\frac{1}{2n}\geqslant\sqrt{1-\frac{1}{n}}=\sqrt{\frac{n-1}{n}}\,.$

Here, the two inequalities follow from the fact that the maximum of $g$ on
$[0,1]\ni\alpha$ is $g(1/2)=1/4$ as well as the fact that
$(1-1/(2n))^{2}=1-1/n+1/(4n^{2})\geqslant 1-1/n$. Finally, we plug this into
inequality (5) to obtain as desired

$\displaystyle\lvert N_{n}(A,\mathcal{E}_{m}^{n}(p+1))\rvert$
$\displaystyle\overset{\mathclap{(\ref{eq: case-2})}}{\geqslant}\lvert
A\rvert+\frac{m^{n-2}}{\sqrt{\ell^{3}m(n-1)}}\sum_{q\in\mathbb{Z}_{m}}g(\alpha_{q})$
$\displaystyle\geqslant\lvert A\rvert+\frac{m^{n-2}\cdot
mg(\alpha)}{\sqrt{\ell^{3}m(n-1)}}\sqrt{\frac{n-1}{n}}$ $\displaystyle=\lvert
A\rvert\left(1+\frac{1-\alpha}{\sqrt{\ell^{3}mn}}\right)\,.$

This concludes the proof. ∎

Obviously, this also establishes a lower bound on the total number of
neighbours of $A$, irrespective of their class, as applying Theorem 1.3 to
both $p+1$ and $p-1$ yields double the bound. More generally, we can choose
$A$ as an arbitrary subset of pairwise non-adjacent partition classes, which
are automatically independent. This leads to the following corollary.

######  Corollary 5.4.

Let $P\in\mathcal{I}(\mathbb{Z}_{m}^{1})$ be an independent set in the
$m$-cycle and $A\subseteq\bigcup_{p\in P}\mathcal{E}_{m}^{n}(p)$. Setting
$\alpha_{p}\coloneqq\lvert A\cap\mathcal{E}_{m}^{n}(p)\rvert/m^{n-1}$, we have

$\lvert N_{\mathbb{Z}_{m}^{n}}(A)\rvert\geqslant\lvert A\rvert+\max_{p\in
P}\lvert
A\cap\mathcal{E}_{m}^{n}(p)\rvert+\frac{m^{n-1}}{\sqrt{\ell^{3}mn}}\sum_{p\in
P}\alpha_{p}(1-\alpha_{p})\,.$

###### Proof.

It is easy to see that $\lvert N_{\mathbb{Z}_{m}^{1}}(P)\rvert\geqslant\lvert
P\rvert+1$. Now let $Q\coloneqq N_{\mathbb{Z}_{m}^{1}}(P)$ and for each $q\in
Q$ choose $p_{q}\in N_{\mathbb{Z}_{m}^{1}}(q,P)$. This can obviously be done
such that $\\{p_{q}\colon q\in Q\\}=P$, choosing the $p\in P$ with maximal
$\alpha_{p}$ twice. We then apply Theorem 1.3 to find that

$\displaystyle\lvert
N_{\mathbb{Z}_{m}^{n}}(A\cap\mathcal{E}_{m}^{n}(p_{q}),\mathcal{E}_{m}^{n}(q))\rvert$
$\displaystyle\geqslant\lvert
A\cap\mathcal{E}_{m}^{n}(p_{q})\rvert\left(1+\frac{1-\alpha_{p_{q}}}{\sqrt{\ell^{3}mn}}\right)$
$\displaystyle=\lvert
A\cap\mathcal{E}_{m}^{n}(p_{q})\rvert+\frac{m^{n-1}}{\sqrt{\ell^{3}mn}}\alpha_{p_{q}}(1-\alpha_{p_{q}})$

for every $q\in Q$. As these sets are disjoint, adding up the inequalities
yields

$\displaystyle\lvert N_{\mathbb{Z}_{m}^{n}}(A)\rvert$
$\displaystyle\geqslant\sum_{q\in Q}\lvert
N_{\mathbb{Z}_{m}^{n}}(A\cap\mathcal{E}_{m}^{n}(p_{q}),\mathcal{E}_{m}^{n}(q))\rvert$
$\displaystyle\geqslant\sum_{q\in Q}\lvert
A\cap\mathcal{E}_{m}^{n}(p_{q})\rvert+\frac{m^{n-1}}{\sqrt{\ell^{3}mn}}\sum_{q\in
Q}\alpha_{p_{q}}(1-\alpha_{p_{q}})\,.$ (5.2)

We recall that the $p_{q}$ were chosen in a way that guarantees that every
$p\in P$ is chosen at least once. This means that $\sum_{q\in
Q}\alpha_{p_{q}}(1-\alpha_{p_{q}})\geqslant\sum_{p\in
P}\alpha_{p}(1-\alpha_{p})$. Moreover, the $p\in P$ with largest $\alpha_{p}$
is chosen twice. This means that $\sum_{q\in Q}\lvert
A\cap\mathcal{E}_{m}^{n}(p_{q})\rvert$ contains $\max_{p\in P}\lvert
A\cap\mathcal{E}_{m}^{n}(p)\rvert$ twice, and so $\sum_{q\in Q}\lvert
A\cap\mathcal{E}_{m}^{n}(p_{q})\rvert\geqslant\lvert A\rvert+\max_{p\in
P}\lvert A\cap\mathcal{E}_{m}^{n}(p)\rvert$. Plugging both observations into
(5) yields the desired statement. ∎

In order to see how this is different from the isoperimetric inequality needed
to deduce an upper bound on $\lvert\mathcal{I}(\mathbb{Z}_{m}^{n})\rvert$,
consider the arguably easiest case $m=3$. While Theorem 1.3 examines sets $A$
in, say, $\mathcal{E}_{3}^{n}(1)$, we would actually need to consider
independent sets
$A\subseteq\overline{I_{0}}=\mathcal{E}_{3}^{n}(1)\cup\mathcal{E}_{3}^{n}(2)$
and maintain an isoperimetric inequality of the form

$\lvert N_{\mathbb{Z}_{3}^{n}}(A,\mathcal{E}_{3}^{n}(0))\rvert\geqslant\lvert
A\rvert\big{(}1+f(n,\lvert A\rvert/\lvert\overline{I_{0}}\rvert)\big{)}\,.$

Using the independence of $A\subseteq\overline{I_{0}}$, one easily observes
that $\lvert A\rvert/\lvert\overline{I_{0}}\rvert\leqslant 1/2$ and might thus
be tempted to hope that $f(n,\lvert A\rvert/\lvert\overline{I_{0}}\rvert)$
depends on $\lvert A\rvert/\lvert\overline{I_{0}}\rvert$ only by involving a
factor of $1-2\lvert A\rvert/\lvert\overline{I_{0}}\rvert$. There is, however,
the following counterexample: Let $A\coloneqq\overline{I_{0}}\cap I_{1}$ be
the intersection of $\overline{I_{0}}$ with a different maximum independent
set, for example $I_{1}\coloneqq\iota_{n}(0,-1,1,\ldots,1)$. Then $\lvert
A\rvert/\lvert\overline{I_{0}}\rvert=1/3$ by the argument of Lemma 3.5, but
the neighbourhood of $A$ in $I_{0}$ does not include $I_{0}\cap I_{1}$, so
$\lvert N_{\mathbb{Z}_{3}^{n}}(A,I_{0})\rvert=2\cdot 3^{n-2}=\lvert A\rvert$.
Yet, we still believe there is a constant $C$ such that every independent set
$A\subseteq\overline{I_{0}}$ satisfies

$\lvert N_{\mathbb{Z}_{3}^{n}}(A,\mathcal{E}_{3}^{n}(0))\rvert\geqslant\lvert
A\rvert\left(1+\frac{1-3\lvert
A\rvert/\lvert\overline{I_{0}}\rvert}{C\sqrt{n}}\right)\,.$

Unfortunately, we did not succeed in proving such a statement with the
approach outlined in Theorem 1.3.

##  6\. Concluding remarks

In this paper, we make progress on a question of Jenssen and Keevash [9] about
the number of independent sets in Cartesian powers of the triangle. We
elaborate on several properties which illustrate that estimating this number
may be much harder than the bipartite cases (including the hypercube) that
have been considered so far; one reason being the more complex isoperimetric
inequality that is needed.

We establish in Theorem 1.1 a lower bound on the number of independent sets in
$\mathbb{Z}_{3}^{n}$, which we conjecture to be asymptotically tight. Clearly,
it would be desirable to prove that this bound is indeed tight, but even
finding an isoperimetric inequality as described after Theorem 1.3 would be
interesting.

For Cartesian powers of larger odd cycles, we provide a less precise lower
bound on the number of independent sets. Moreover, we show how to approach
this question with the cluster expansion method by calculating initial terms
for $\mathbb{Z}_{5}^{n}$ and $\mathbb{Z}_{7}^{n}$. More precise asymptotics
and further progress towards an upper bound would again be highly desirable.

## Acknowledgements

We would like to thank Matthew Jenssen for many valuable ideas and discussions
as well as for introducing us to the cluster expansion method.

## References

  * [1] J. Balogh, R. I. Garcia, and L. Li, _Independent sets in the middle two layers of Boolean lattice_ , J. Combin. Theory Ser. A 178 (2021), 105341, 24 pages.
  * [2] C. Carlson, E. Davies, N. Fraiman, A. Kolla, A. Potukuchi, and C. Yap, _Algorithms for the ferromagnetic Potts model on expanders_ , 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 344–355.
  * [3] J. Engbers and D. Galvin, _$H$ -coloring tori_, J. Combin. Theory Ser. B 102 (2012), 1110–1133.
  * [4] C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre, _Correlation inequalities on some partially ordered sets_ , Comm. Math. Phys. 22 (1971), 89–103.
  * [5] D. Galvin, _On homomorphisms from the Hamming cube to ${\bf Z}$_, Israel J. Math. 138 (2003), 189–213.
  * [6] by same author, _A threshold phenomenon for random independent sets in the discrete hypercube_ , Combin. Probab. Comput. 20 (2011), 27–51.
  * [7] by same author, _Independent sets in the discrete hypercube_ , arXiv:1901.01991 (2019).
  * [8] T. E. Harris, _A lower bound for the critical probability in a certain percolation process_ , Math. Proc. Cambridge Philos. Soc. 56 (1960), 13–20.
  * [9] M. Jenssen and P. Keevash, _Homomorphisms from the torus_ , arXiv:2009.08315 (2020).
  * [10] M. Jenssen and W. Perkins, _Independent sets in the hypercube revisited_ , J. Lond. Math. Soc. (2) 102 (2020), 645–669.
  * [11] M. Jenssen, W. Perkins, and A. Potukuchi, _Independent sets of a given size and structure in the hypercube_ , Combin. Probab. Comput. 31 (2022), 702–720.
  * [12] by same author, _Approximately counting independent sets in bipartite graphs via graph containers_ , Random Structures Algorithms 63 (2023), 215–241.
  * [13] J. Kahn and J. Park, _The number of 4-colorings of the Hamming cube_ , Israel J. Math. 236 (2020), 629–649.
  * [14] by same author, _The number of maximal independent sets in the Hamming cube_ , Combinatorica 42 (2022), 853–880.
  * [15] A. D. Korshunov and A. A. Sapozhenko, _The number of binary codes with distance $2$_, Problemy Kibernet. 40 (1983), 111–130.
  * [16] J. Park, _Note on the number of balanced independent sets in the Hamming cube_ , Electron. J. Combin. 29 (2022), Paper No. 2.34, 9 pages.
  * [17] A. A. Sapozhenko, _The number of antichains in ranked partially ordered sets_ , Diskret. Mat. 1 (1989), 74–93, Russian; translation in Discrete Math. Appl., 1 (1991), 35–58.