Proof. [item:1]. If \(2x-t = 2y-s\) for some \(t,s\in T_d\), then \(2(x-y)=t-s\). But \(t-s\) has coordinates in \(\{-1,0,1\}\), hence cannot equal a nonzero even vector (that is, a vector in \(2\mathbb{Z}^d\)). Therefore \(t=s\) and \(x=y\).

[item:2]. Modulo \(2\) we have \(2y\equiv 0\) and \(2y-e_i\equiv e_i\), hence \[p\in\bigcup_y K_y \iff p \bmod 2 \in T_d.\]

For a plaquette \(B=x+T_d\) the \((d+1)\) residues are \((x\bmod 2)+T_d\), so the number of points of \(B\) lying in \(\bigcup_y K_y\) is \((d+1)\) iff \(x\) is even, \(2\) iff \(x\) has exactly one or two odd coordinates and otherwise \(0\).

Thus we get cases [item:intersection:c], [item:intersection:b], [item:intersection:a]. If \(x=2u{\in2\mathbb{Z}^d}\), then \[2u\in K_u,\qquad 2u+e_i\in K_{u+e_i}\;(i=1,\dots, d),\] so \(2u+T_d\) meets \(K_u,K_{u+e_1},\dots,K_{u+e_d}\). By [item:1]. of the proof, the intersections of \(2x+T_d\) with each of these inverted plaquettes are disjoint, so they consist of one point each.

If \(x = 2u-e_i\), then \(x+T_d\) has two common points \(\{2u,2u-e_i\}\) with \(K_{u}\). By [item:1]. of the proof, \(x+T_d\) has no intersection with any \(K_v\) for \(v\in\mathbb{Z}^d\setminus\{u\}\).

If \(x=2u-e_i-e_j\) for \(i\neq j\), then \(x+T_d\) has two common points \(\{2u-e_i,2u-e_j\}\) with \(K_u\). By [item:1]. of the proof, there \(x+T_d\) has no intersection with any \(K_v\) for \(v\in\mathbb{Z}^d\setminus\{u\}\).

In the other cases, \(x\) and \(x+e_i\) have at least two odd coordinates, so cannot belong to an inverted plaquette. ◻

Proof. [item:intersect2:1]. It suffices to consider a simplex of the form \(\Lambda_{d,m}\). Suppose \(T_d+x\) has a nonempty intersection with \(\Lambda_{d,m}\) but is not contained in \(\Lambda_{d,m}\). There are two cases.

Assume \(x\in \Lambda_{d,m}\). Then \(x_1+\dots+x_d = m\) (otherwise \(x+e_i\in \Lambda_{d,m}\) for all \(i\)), and therefore \[(T_d+x)\cap\Lambda_{d,m} = \{x\}.\]

Assume \(x\notin \Lambda_{d,m}\) and \(x+e_i\in \Lambda_{d,m}\) for some \(i\). Then \(x_i = -1\), and \[(T_d+x)\cap \Lambda_{d,m} = \{x+e_i\}.\]

[item:intersect2:2]. This is immediate from [item:intersect2:1]., since the plaquette \(T_d+x\) is precisely \(x+\Lambda_{d,1}\). ◻

Proof of Theorem 4. If \(U_k=x+\Lambda_{d,m}\) then \(U_{k+1}=x'+\Lambda_{d,m'}\) with \(m'=2m+3d\) and \(x'=2x-2(e_1+\dots+e_d)\). We obtain by induction \(U_k=\Lambda_{d,3d(2^k-1)}-2(2^k-1)(e_1+\dots+e_d)\subset B_k\), and we are done by Proposition 5. ◻

Proof. \(\mathcal{T}\) intersects \(U_k\), so toggling \(\mathcal{T}\) must turn off at least one ON lamp of \(W\) in \(U_k\); otherwise we would only turn lamps on and hence would get \(|(W\mathbin{\mathpalette\triangle\relax}\mathcal{T})\cap U_k|>k\). Thus, \(\mathcal{T}\) intersects \(U'_{k}\), because \(W\subset U'_k\). Then, by the definition of \(U_k\), we get \(\mathcal{T}\subset U_k\).

Since \(d+1\geqslant 3\), applying \(\mathcal{T}\) must switch off at least two ON lamps of \(W\). Each inverted plaquette contains at most one ON lamp, so \(\mathcal{T}\) intersects at least two iip. This forces case [item:intersection:c] of Lemma 1: applying \(\mathcal{T}\) changes lamps in \((d+1)\) inverted plaquettes of the form \(K_x,K_{x+e_1},K_{x+e_2},\dots, K_{x+d}\).

Since \(U_{k-1}\) is a simplex, Lemma 3 implies \[|(x+T_d)\cap U_{k-1}| \in\{0, 1,d+1\}.\] The only case compatible with our assumptions is the third one. In this case, all \((d+1)\) inverted plaquettes intersecting \(\mathcal{T}\) are iip. ◻

Proof. Clearly, \(W_i\) is critical.

\(\mathcal{T}_1\) and \(\mathcal{T}_2\) both intersect \(U_k\); otherwise we could shorten the chain. By Lemma 4, it follows that \(\mathcal{T}_1\) and \(\mathcal{T}_2\) are spread plaquettes. In particular, they are contained in \(U'_k\), which proves 3.

If \(\mathcal{T}_1 = \mathcal{T}_2\), then \(W_{i-1} = W_{i+1}\) and we can again shorten the chain. Therefore, \(\mathcal{T}_1\) and \(\mathcal{T}_2\) are disjoint, proving 1. Indeed, distinct spread plaquettes are disjoint by [item:1]. of Lemma 1, which applies to spread plaquettes by symmetry.

We may apply \(\mathcal{T}_1\) and \(\mathcal{T}_2\) in the opposite order: consider the chain \[\mathbb{W}'\mathrel{\vcenter{:}}=(W_0, W_1, \dots, W_{i-1}, W', W_{i+1}, \dots, W_n).\] If \(|W'\cap U_k| < k\), then \(\mathbb{W}'\) is a good chain and this contradicts the minimality of \(\mathbb{W}\). Therefore, \(|W'\cap U_k| \geqslant k\). Since \(\mathcal{T}_1\) and \(\mathcal{T}_2\) are disjoint, \[|W_i\cap U_k| + |W'\cap U_k| = |W_{i-1}\cap U_k| + |W_{i+1}\cap U_k|.\] The left-hand side is at least \(2k\), while the right-hand side is at most \(2k\). Therefore, the only possibility is \[|W_{i-1}\cap U_k|=|W_{i+1}\cap U_k|=|W'\cap U_k|=k.\] This proves 2.

Next, \(|\mathcal{R}(W')\cap U_{k-1}| \leqslant|W'\cap U_{k}| = k\), so \(\mathbb{W}'\) is also a minimal good chain, proving 5. If \(|\mathcal{R}(W')\cap U_{k-1}| < |W'\cap U_{k}|\), we again contradict the minimality of \(\mathbb{W}\). Hence, \(|\mathcal{R}(W')\cap U_{k-1}| = k\), so \(W'\) is critical, proving 4. ◻

Proof of Proposition 5. We proceed by induction on \(k\). The base cases \(k=0,1\) are straightforward, using the assumption \(d\geqslant 2\). Fix \(k>1\). Assume the statement holds for \(k-1\), and let us prove it for \(k\).

Our goal is to show that no good chain exists. Suppose, for the sake of contradiction, that there exists a good chain \(\mathbb{W} = (W_0,\dots,W_n)\) that we may assume minimal.

Define \[V_i \mathrel{\vcenter{:}}= \mathcal{R}(W_i).\] Then \(V_0\) consists of the single point \(O\). Moreover, \(V_n\cap U_{k-1}=\varnothing\), because if \(x\in U_{k-1}\) then \(K_x\subseteq U'_k\subset U_k\), so \(W_n\) has no ON lamps in \(K_x\).

By Lemma 2, the sequence \((V_0,\dots,V_n)\) is a chain. By the induction hypothesis (applied to the chain \((V_0,\dots,V_n)\) and size parameter \(k-1\)), there exists an index \(i\) such that \[|V_i\cap U_{k-1}| \geqslant k.\] Then \(|V_i\cap U_{k-1}| = k\), as otherwise \(|W_i\cap U_k| > k\).

Since \(|V_0\cap U_{k-1}|=1\) and \(V_n\cap U_{k-1}=\varnothing\), we can choose an index \(t\) such that \[|V_{t-1}\cap U_{k-1}| < k \quad \text{and} \quad |V_t\cap U_{k-1}| = k.\] Since \(|W_t\cap U_k| \geqslant|V_t\cap U_{k-1}|\) and \(|W_t\cap U_k| \leqslant k\), the only possibility is \(|W_t\cap U_k| = k\).

Set \(\mathcal{T}_1\mathrel{\vcenter{:}}= W_t\mathbin{\mathpalette\triangle\relax}W_{t-1}\) and \(\mathcal{T}_2\mathrel{\vcenter{:}}= W_t\mathbin{\mathpalette\triangle\relax}W_{t+1}\). Then, by Lemma 5, \(\mathcal{T}_1\) and \(\mathcal{T}_2\) are spread plaquettes, and moreover \[|W_{t-1}\cap U_k|=|W_{t+1}\cap U_k|= k.\]

If the dimension \(d\) is even, we immediately obtain a contradiction with \(|W_t\cap U_k|=k\), since the plaquette toggles an odd number of lamps. For odd \(d\), we need a more delicate argument.

As in Lemma 5, set \(W'\mathrel{\vcenter{:}}= W_{t-1}\mathbin{\mathpalette\triangle\relax}\mathcal{T}_2\). By Lemma 5, we have \(|W'\cap U_k| = k\). We will contradict the minimality of the original chain if we can show that \(|\mathcal{R}(W')\cap U_{k-1}| < |W'\cap U_k|\).

Since \(W_t\) is critical, all its ON lamps lie inside iip. By Lemma 4, \(\mathcal{T}_1\) contains no points outside iip. Therefore, all ON lamps of \(W_{t-1} = W_t\mathbin{\mathpalette\triangle\relax}\mathcal{T}_1\) also lie inside iip. At the same time, we know that \(|V_{t-1}\cap U_{k-1}| < |W_{t-1}\cap U_k|\). Hence, in some iip \(K_u\) the configuration \(W_{t-1}\) has at least two ON lamps. It is easy to see that there are exactly two, since applying \(\mathcal{T}_1\) changes the number of ON lamps in \(K_u\) by exactly \(1\), as \(\mathcal{T}_1\) is a spread plaquette touching \(K_u\).

For \(i=1,2\) set \(\mathcal{S}_i=\{x\in\mathbb{Z}^d:K_x\cap\mathcal{T}_i\neq\varnothing\}\), and note by Lemma 1 that each \(\mathcal{S}_i\) is a plaquette. Since \(W_t = W_{t-1}\mathbin{\mathpalette\triangle\relax}\mathcal{T}_1\) is critical, we have \(u \in \mathcal{S}_1\); otherwise \(W_t\) would also contain two ON lamps inside \(K_u\). From Lemma 5 we know that \(W' = W_{t-1}\mathbin{\mathpalette\triangle\relax}\mathcal{T}_{2}\) is also critical. Thus, by the same reasoning, \(u\in \mathcal{S}_2\).

Therefore, \(W_{t-1}\) contains two ON lamps inside \(K_u\); denote them by \(\ell_1\in\mathbb{Z}^d\) and \(\ell_2\in\mathbb{Z}^d\). Up to reordering, we may assume \(\ell_i\) lies in \(\mathcal{T}_i\) for \(i=1,2\), and there are no other intersections of \(\mathcal{T}_i\) with \(K_u\). Then \(W_t\) contains exactly one ON lamp inside \(K_u\), namely \(\ell_2\), while \(W'\cap K_u=\{\ell_1\}\), and \(W_{t+1}\) contains no ON lamps inside \(K_u\).

We now consider two cases.

Case 1. Assume that the configuration \(W_{t+1}\) is not critical. We apply to \(W_{t+1}\) the same reasoning as above for \(W_{t-1}\). The configuration \(W_{t+1}\) has exactly \(k\) ON lamps inside \(U'_k\), so in some iip \(K_v\) two lamps must be lit. As before, we obtain \(v\in \mathcal{S}_1\cap \mathcal{S}_2\). Moreover, \(v\neq u\), because \(W_{t+1}\) has no ON lamps inside \(K_u\). Therefore \(|\mathcal{S}_1\cap\mathcal{S}_2|\geqslant 2\), contradicting Lemma 3.

Case 2. Assume that the configuration \(W_{t+1}\) is critical. Set \[\mathcal{T}_3\mathrel{\vcenter{:}}= W_{t+2}\mathbin{\mathpalette\triangle\relax}W_{t+1}.\] Apply Lemma 5 at index \(i = t+1\). We obtain \(\mathcal{T}_2\neq \mathcal{T}_3\), and a minimal good chain \[\mathbb{W}''\mathrel{\vcenter{:}}=(W_0,\dots, W_{t-1}, W_t, W_t\mathbin{\mathpalette\triangle\relax}\mathcal{T}_3, W_{t+2}, \dots, W_n)\] Apply Lemma 5 again, this time to the sequence \(\mathbb{W}''\) at index \(t\). We obtain yet another minimal good chain \[\mathbb{W}'''\mathrel{\vcenter{:}}=(W_0,\dots, W_{t-1}, W_{t-1}\mathbin{\mathpalette\triangle\relax}\mathcal{T}_3, W_t\mathbin{\mathpalette\triangle\relax}\mathcal{T}_3, W_{t+2}, \dots, W_n).\]

In addition, \(\mathcal{T}_1\neq \mathcal{T}_3\) (otherwise \(\mathbb{W}\) would not have been minimal), and the configuration \(W_{t-1}\mathbin{\mathpalette\triangle\relax}\mathcal{T}_3\) is critical. Recall that \(W_{t-1}\) has ON lamps \(\ell_i\in K_u\cap\mathcal{T}_i\), for \(i=1,2\). Neither of these lamps lies in \(\mathcal{T}_3\), since distinct spread plaquettes are disjoint. Therefore, the configuration \(W_{t-1}\mathbin{\mathpalette\triangle\relax}\mathcal{T}_3\) cannot be critical, because it still contains at least two ON lamps inside \(K_u\).

This contradiction completes the inductive step and hence the proof of the proposition. ◻

Proof. This follows directly from the fact that a translate \(a+T_d\) corresponds to the Laurent monomial \(x^a\) multiplied by \(1+x_1+\cdots+x_d\), while summation of configurations modulo \(2\) corresponds to addition in \(R_d\). ◻

Proof. We prove the statement by induction on \(d\).

Base case: \(d=2\). This case is proved, for instance, in Arenas-Carmona08?*Lemma 5.6. For the reader’s convenience, we recall one possible argument.

The Newton polytope of a Laurent polynomial is the convex hull of its support. Under multiplication of Laurent polynomials, Newton polytopes add by Minkowski summation. The Newton polytope of \(1+x_1+x_2\) is the triangle \(\operatorname{conv}(T_2)\). Hence Proposition 6 implies that every admissible set \(X\subset\mathbb{Z}^2\) has

1. an edge with outer normal \(-e_2\);

2. an edge with outer normal \(-e_1\);

3. an edge with outer normal \(e_1+e_2\).

It follows at once that if \(|X|\leqslant 3\), then \(X\) is homothetic to \(T_2\) with an integral scaling factor. After translating \(X\), we may assume that \[X = \{(0,0), (a,0), (0,a)\}\] for some positive integer \(a\). It remains to show that \(a\) is a power of \(2\). Set \[P(x_1,x_2)=1+x_1^a+x_2^a.\] Since \(P\) is divisible by \(1+x_1+x_2\), the polynomial \(P(x_1,1+x_1)\) must vanish identically. Over \(\mathbb{F}_2\), \[0=P(x_1,1+x_1) = 1+x_1^a+(1+x_1)^a = \sum_{i=1}^{a-1}\binom{a}{i}x_1^i.\] Thus all intermediate binomial coefficients \(\binom{a}{i}\), \(1\leqslant i\leqslant a-1\), are even. By Kummer’s theorem, equivalently by Lucas’ theorem, this is possible only when \(a\) is a power of \(2\). Hence \(X\) is a large plaquette.

Induction step. Assume that the lemma has already been proved in dimension \(d-1\), we prove it in dimension \(d\).

Let \(X\subset\mathbb{Z}^d\) be admissible. Translating \(X\), we may assume that the minimum first coordinate among points of \(X\) is \(0\). Consider the Laurent polynomial \[P(x_1,\dots,x_d) = \sum_{(t_1,\dots,t_d)\in X}\prod_{i=1}^d x_i^{t_i}.\] By Proposition 6, \[P(x_1,\dots,x_d) = (1+x_1+\dots+x_d)Q(x_1,\dots,x_d)\] for some Laurent polynomial \(Q\).

Let \(b\) be the minimum exponent of \(x_1\) among the nonzero monomials of \(Q\). Since the minimum exponent of \(x_1\) among the monomials of \(P\) is \(0\), we have \(b=0\). Write \[Q=Q_1+Q_2,\] where all monomials of \(Q_1\) have \(x_1\)-degree \(0\), and all monomials of \(Q_2\) have strictly positive \(x_1\)-degree. Then \[P_0\mathrel{\vcenter{:}}= Q_1(1+x_2+x_3+\dots+x_d)\] is precisely the sum of all monomials of \(P\) with \(x_1\)-degree \(0\). Therefore \(P_0\) has at most \(d+1\) monomials. If \(P_0\) had exactly \(d+1\) monomials, then, since \(|X|\leqslant d+1\), we would have \(P=P_0\). This is impossible: the Newton polytope of \(P_0\) has dimension at most \(d-1\), whereas every nonzero multiple of \(1+x_1+\dots+x_d\) has \(d\)-dimensional Newton polytope.

Thus \(P_0\) has at most \(d\) monomials. The support of \(P_0\) is an admissible set in \(\mathbb{Z}^{d-1}\), so by the induction hypothesis, \[P_0 = x_2^{t_2}\cdots x_d^{t_d} \left(1+x_2^{2^k}+\dots+x_d^{2^k}\right)\] for some integers \(t_2,\dots,t_d\) and some integer \(k\geqslant 0\). In particular, \(P_0\) has exactly \(d\) nonzero monomials, and \(P\) has exactly \(d+1\) nonzero monomials. At this point we have also proved that, in dimension \(d\), there are no nonempty admissible sets of cardinality strictly smaller than \(d+1\).

Proof. We argue by induction on \(|X|\).

By Lemma 6, the smallest possible cardinality of a nonempty admissible set is \(d+1\). In that case \(X\) is a large plaquette. If \(\alpha\in X\), then all other \(d\) points of \(X\) are at \(\rho\)-distance \(1\) from \(\alpha\), and the left-hand side of 11 is exactly \(d\). This proves the base case.

Now assume that \(|X|>d+1\). Translating \(X\), we may suppose \(\alpha=0\in X\). We also assume that \(X\) contains a point with at least one odd coordinate. Indeed, if all coordinates of all points of \(X\) are even, then we may divide all coordinates by their largest common power of \(2\). The resulting set remains admissible, and the left-hand side of 11 does not increase.

Call the following \(d(d+1)\) points near: \[\alpha\pm e_i, \qquad \alpha\pm(e_i-e_j), \qquad 1\leqslant i<j\leqslant d.\] These points have \(\rho\)-distance \(1\) from \(\alpha\).

Case 1. Suppose that at least two near points belong to \(X\). Each of them contributes \(1\) to the sum in 11 , so the desired inequality follows immediately.

Case 2. Suppose that \(d=2\) and exactly one near point belongs to \(X\). Denote this point by \(\beta\). Choose a point \(\gamma\) such that \[\{\alpha,\beta,\gamma\}\] is a plaquette. Then \(\gamma\) is also near, and \(\gamma\notin X\).

Set \[X' = X \mathbin{\mathpalette\triangle\relax}\{\alpha,\beta,\gamma\},\] where \(\mathbin{\mathpalette\triangle\relax}\) denotes symmetric difference. Then \(X'\) is admissible, \(|X'|<|X|\), and \(\gamma\in X'\). By the induction hypothesis, \[\sum_{x\in X\setminus\{\alpha,\beta\}} \lambda_2^{\rho(x,\gamma)-1} = \sum_{y\in X'\setminus\{\gamma\}} \lambda_2^{\rho(y,\gamma)-1} \geqslant 2.\] Since \(\rho(\gamma,\alpha)=1\), we have \[\rho(x,\alpha)\leqslant\rho(x,\gamma)+1\] for every \(x\). Hence, \[\sum_{x\in X\setminus\{\alpha\}} \lambda_2^{\rho(x,\alpha)-1}\geqslant 1+ \sum_{x\in X\setminus\{\alpha,\beta\}} \lambda_2^{\rho(x,\alpha)-1} \geqslant 1+ \lambda_2 \sum_{x\in X\setminus\{\alpha,\beta\}} \lambda_2^{\rho(x,\gamma)-1} \geqslant 1+2\lambda_2 >2.\]

Case 3. Suppose either that \(d=2\) and no near point belongs to \(X\), or that \(d>2\) and at most one near point belongs to \(X\). If such a near point exists, denote it by \(\beta\).

Let \(\mathcal{I}=\{0,1\}^d\) be the set of all binary strings of length \(d\). Partition \(\mathbb{Z}^d\) into \(2^d\) parity classes, denoted by \(\mathbb{Z}_I^d\) for all \(I\in\mathcal{I}\). Put \[X_I \mathrel{\vcenter{:}}= (X\setminus\{\alpha=0\})\cap \mathbb{Z}_I^d.\] For \(I\in\mathcal{I}\), define \[S_I \mathrel{\vcenter{:}}= \sum_{x\in X_I} \lambda_d^{\rho(x,0)-1}.\] Define \(\mathbf{0}=00\dots 0\in\mathcal{I}\). Among the sums \(S_I\) with \(I\neq \mathbf{0}\), choose a maximal one and denote it by \(S_J\). If \(S_J=0\), then all points of \(X\) have all coordinates even, contrary to our reduction above. Therefore \(S_J>0\).

Choose \(\gamma\) as in Claim 7. Let \(\mathcal{I}_\gamma\subset\mathcal{I}\) be the set of parity classes represented by the points of \(\gamma-T_d\). This set consists of the parity vector of \(\gamma\) and the \(d\) parity vectors obtained from it by flipping exactly one coordinate. In particular, \(|\mathcal{I}_\gamma|=d+1\), and \(\mathbf{0}\in\mathcal{I}_\gamma\). Also, by construction, \(J\notin\mathcal{I}_\gamma\).

Recalling the renormalisation map \(\mathcal{R}\) from 10 , set \[Y=\mathcal{R}(X-\gamma).\] By Lemma 2, \(Y\) is admissible. Since \[|X\cap(\gamma-T_d)|=1,\] we have \(0\in Y\).

For every \(y\in Y\), \[\gamma+2y-T_d\] contains an odd number of points of \(X\). Choose one of these points and denote it by \(\tau(y)\). The sets \(\gamma+2y-T_d\) are pairwise disjoint for distinct \(y\) by Lemma 1, so the points \(\tau(y)\) are pairwise distinct.

For \(I\in\mathcal{I}_\gamma\), define \(Y_I=\{y\in Y\setminus\{0\}\mid\tau(y)\in X_I\}\), so we have \[|Y_I|\leqslant|X_I|\] for every \(I\in\mathcal{I}\). Moreover, \(Y_I\) is empty unless \(I\in\mathcal{I}_\gamma\). In particular, \(Y_J\) is empty. Since \(S_J>0\), we have \(|X_J|>0\), and therefore \(|Y|<|X|\). Thus the induction hypothesis applies to \(Y\): \[\sum_{y\in Y\setminus\{0\}} \lambda_d^{\rho(y,0)-1} \geqslant 2.\]

We now compare the contributions of \(Y\) and \(X\). If \(\tau(y)\in X_{\mathbf{0}}\), then \[\rho(\tau(y),0)\leqslant\rho(y,0).\] If \(\tau(y)\notin X_{\mathbf{0}}\), then \[\rho(\tau(y),0)\leqslant\rho(y,0)+1.\] Consequently, \[S_{\mathbf{0}} \geqslant \sum_{y\in Y_{\mathbf{0}}} \lambda_d^{\rho(y,0)-1},\] and for every \(I\in\mathcal{I}_\gamma\setminus\{\mathbf{0}\}\), \[S_I \geqslant \lambda_d \sum_{y\in Y_I} \lambda_d^{\rho(y,0)-1}.\]

Since \(S_J\) is maximal among all \(S_I\) with \(I\neq\mathbf{0}\), and since \(J\notin\mathcal{I}_\gamma\), we get \[\begin{align} \sum_{x\in X\setminus\{\alpha\}} \lambda_d^{\rho(x,\alpha)-1} &\geqslant \sum_{I\in\mathcal{I}_\gamma}S_I+S_J \\ &\geqslant S_{\mathbf{0}} + \frac{d+1}{d} \sum_{I\in\mathcal{I}_\gamma\setminus\{\mathbf{0}\}}S_I \\ &\geqslant \sum_{y\in Y_{\mathbf{0}}} \lambda_d^{\rho(y,0)-1} + \frac{d+1}{d} \sum_{I\in\mathcal{I}_\gamma\setminus\{\mathbf{0}\}} \lambda_d \sum_{y\in Y_I} \lambda_d^{\rho(y,0)-1}. \end{align}\] By our choice \(\lambda_d=d/(d+1)\), the last expression equals \[\sum_{I\in\mathcal{I}_\gamma}\sum_{y\in Y_I}\lambda_d^{\rho(y,0)-1}=\sum_{y\in Y\setminus\{0\}} \lambda_d^{\rho(y,0)-1}.\] Therefore \[\sum_{x\in X\setminus\{\alpha\}} \lambda_d^{\rho(x,\alpha)-1} \geqslant \sum_{y\in Y\setminus\{0\}} \lambda_d^{\rho(y,0)-1} \geqslant 2.\] The lemma follows. ◻

Proof. Let \(S_0\) be the face of the simplex consisting of points whose first coordinate is zero. Then \[|S_0|=\binom{n+d-1}{d-1}.\]

Subsets of \(\Lambda_{d,n}\) form a vector space over \(\mathbb{F}_2\), and admissible sets form a linear subspace. It is enough to show that the codimension of this subspace is at most \(|S_0|\). For this, we show that any lamp configuration can be transformed, by symmetric differences with plaquettes, into a configuration supported inside \(S_0\).

For any point \(x\in\Lambda_{d,n}\setminus S_0\), the plaquette \(x-e_1+T_d\) is contained entirely in \(\Lambda_{d,n}\). Hence one can switch off any lamp with positive first coordinate without affecting lamps whose first coordinate is at least that of \(x\). Proceeding in decreasing order of the first coordinate transforms the configuration into one supported in \(S_0\). ◻

Proof. Put \(r\mathrel{\vcenter{:}}=\lfloor c\ln n\rfloor\). We may assume that \(r\geqslant 1\). Choose \(k\) such that \[2^{k-1}\leqslant n<2^k.\] Consider the quotient map \[\pi\colon\mathbb{Z}^d\to \mathbb{Z}^d/2^k\mathbb{Z}^d.\] Since \(\pi\) does not identify distinct points of \(\Lambda_{d,n}\), it is enough to prove that \[|\pi(A)|\leqslant n^{3c\ln(4d)-c\ln c}.\] Under \(\pi\), all long vectors divisible by \(2^k\) map to zero. Consider the set of \[m\mathrel{\vcenter{:}}=1+kd(d+1)\] vectors \[V\mathrel{\vcenter{:}}=\{0\}\cup\left\{\pm2^a e_i\mid 1\leqslant i\leqslant d,\;0\leqslant a<k\right\} \cup\left\{\pm2^a(e_i-e_j)\mid 1\leqslant i<j\leqslant d,\;0\leqslant a<k\right\}.\] Clearly, \(|\pi(A)|\) is at most the number of ways to choose \(r\) elements from \(V\) with repetitions. Therefore \[\binom{m+r-1}{r} \leqslant\frac{(m+r)^r}{(r/e)^r} \leqslant\left(e\left(1+\frac{m}{r}\right)\right)^{c\ln n} = n^{c\left(1+\ln\left(1+\frac{m}{r}\right)\right)}.\] A routine estimate gives \[1+\frac{m}{r} \leqslant\frac{4(d+1)^2}{c}.\] After a further harmless simplification, we obtain \[|\pi(A)|\leqslant n^{3c\ln(4d)-c\ln c}.\qedhere\] ◻

Proof. Choose \(c_d>0\) sufficiently small so that, for all relevant \(n\), \[n^{3c_d\ln(4d)-c_d\ln c_d}<\frac{n+d}{d}.\] Equivalently, \[n^{3c_d\ln(4d)-c_d\ln c_d}\binom{n+d-1}{d-1}<|\Lambda_{d,n}|.\]

Put \(r=\lfloor c_d\ln n\rfloor\). We first construct an \(r\)-separated subset of \(\Lambda_{d,n}\) of cardinality \[\binom{n+d-1}{d-1}+1.\] Add points greedily. If no more than \(\binom{n+d-1}{d-1}\) points have already been chosen, Lemma 9 and the inequality above ensure that there is still a point of \(\Lambda_{d,n}\) outside all \(\rho\)-balls of radius \(r\) around the chosen points.

By Lemma 8, this \(r\)-separated set contains a nonempty admissible subset. Any subset of an \(r\)-separated set is again \(r\)-separated. ◻

Proof. By Corollary 1, there exists an admissible \((c_d\ln n)\)-separated subset \(X\subset \Lambda_{d,n}\) with \(|X|\leqslant C_d n^{d-1}\). Put \[r=c_d\ln n.\] Let \(|X|=m\), and write \[X=\{x_1,\dots,x_m\}.\] For each \(i\), define \[U_i\mathrel{\vcenter{:}}=\{y\in\mathbb{Z}^d\mid \rho(y,x_i)<r/3\}.\] The sets \(U_i\) are pairwise disjoint.

Let \[X=X_0,X_1,\dots,X_T=\varnothing\] be any sequence of configurations such that the symmetric difference of any two consecutive configurations is a plaquette. We do not require the intermediate configurations to be contained in \(\Lambda_{d,n}\).

Say that a configuration \(X_t\) behaves unusually inside \(U_j\) if \[|X_t\cap U_j|\leqslant 1 \qquad\text{and}\qquad X_t\cap U_j\neq \{x_j\}.\] Initially, the configuration behaves usually inside every \(U_j\), whereas the final configuration behaves unusually inside every \(U_j\). Hence, there is an index \(t\) such that \(X_{t-1}\) behaves usually inside all \(U_j\), while \(X_t\) behaves unusually inside at least one \(U_j\). This index \(j\) is unique, since a single plaquette cannot intersect two distinct sets \(U_j\) and \(U_{j'}\) when \(r\) is large enough. Without loss of generality, assume that \(j=1\).

Put \[X' = X_t \mathbin{\mathpalette\triangle\relax}X.\] Then \(X'\) is admissible, \(x_1\in X'\), and \[|X'\cap U_1|\leqslant 2.\] By Lemma 7, \[\sum_{y\in X'\setminus\{x_1\}} \lambda_d^{\rho(x_1,y)-1}\geqslant 2, \qquad \lambda_d=\frac{d}{d+1}.\] Inside \(U_1\), the set \(X'\setminus\{x_1\}\) contains at most one point, whose contribution to the sum is at most \(1\). Therefore, the points of \(X'\setminus U_1\) contribute at least \(1\) to the sum. Each such point contributes at most \(\lambda_d^{r/3-1}\), and hence \[|X'|\geqslant\lambda_d^{1-r/3} = C'_d\left(1+\frac{1}{d}\right)^{r/3} \geqslant n^{\alpha_d}\] for a suitable constant \(\alpha_d>0\) depending only on \(d\).

Call a point of \(X'\) old if it belongs to \(X\), and new otherwise. Suppose that \(x_j\) is an old point of \(X'\) with \(j\neq1\). Since \(X_t\) behaves usually inside \(U_j\), and \(x_j\notin X_t\), we must have \[|X_t\cap U_j|\geqslant 2.\] Thus, each old point other than possibly \(x_1\) forces at least two new points. Consequently, if \(O\) and \(N\) denote the numbers of old and new points in \(X'\), then \(N\geqslant 2(O-1)\), so \[N\geqslant 5(O-1)/3+N/6=3O/2+|X'|/6-5/3\geqslant 3O/2+n^{\alpha_d}/6-5/3\geqslant 3O/2+n^{\alpha_d/2},\] taking \(n\) large enough in the last inequality. ◻

Proof. [item:cyc95layer:1]. Suppose that \(|X|>0\). Choose a point \(x\in X\) with minimal \(k\)-th coordinate. Since \(x\notin S_0\), the plaquette \(x-e_k+T_d\) is entirely contained in \(\Lambda_{d,n}\), and it contains exactly one point of \(X\), namely \(x\). This contradicts the cycle condition.

[item:cyc95layer:2]. Let \(S_+\mathrel{\vcenter{:}}=\Lambda_{d,n}\setminus S_0\), that is, the set of all points whose \(k\)-th coordinate is positive. Clearly, \(X\cap S_+\) is a \((T_d,S_+)\)-cycle. By part 1, already proved above, we have \(X\cap S_+=\emptyset\), hence \(X\subseteq S_0\).

For any translate \(T'+x\) contained entirely in \(S_0\), there is a point of \(S_1\) which completes it to a translate of \(T_d\). Since this point does not belong to \(X\), it follows that \(|(T'+x)\cap X|\) is even. Therefore \(X\in \mathcal{C}_{(T',S_0)}\). ◻

Proof. We prove this by double induction: first on \(n\), and then on \(d\). The base case is \(n=0\) and arbitrary \(d\).

Let \(X\in \mathcal{C}_{d,n}\). Decompose \(\Lambda_{d,n}\) into two parts: \[\Lambda_{d,n}=S_0\sqcup S_+,\] where \(S_0\) consists of the points whose \(d\)-th coordinate is equal to \(0\), and \(S_+\) consists of all remaining points.

Observe that \(S_+\) is a translate of \(\Lambda_{d,n-1}\), while \(S_0\) is an embedding of \(\Lambda_{d-1,n}\) into \(\mathbb{Z}^d\). We assume that the induction hypothesis applies to these sets.

Case 1. Suppose that \(X\cap S_0=\emptyset\). This is impossible by part 1 of Lemma 10.

Case 2. Suppose that \(X\cap S_+=\emptyset\). Then by part 2 of Lemma 10, the set \(X\) is a \((T',S_0)\)-cycle. Applying the induction hypothesis for \(d-1\) and \(n\), we obtain \(|X|\geqslant n+1\).

Case 3. Suppose that both \(X\cap S_0\) and \(X\cap S_+\) are nonempty. Then \(X\cap S_+\) is a \((T_d,S_+)\)-cycle, and by the induction hypothesis we have \[|X\cap S_+|\geqslant n.\] Hence \(|X|\geqslant n+1\). ◻

Proof. First, let us derive a simple consequence of the condition imposed on \(t\) and \(n\).

The simplex \(\Lambda_{d-1,n}\) contains the empty cycle. It also contains a cycle of size \(n+1\), namely the set of all points whose coordinates other than the first are equal to \(0\). Hence \[G_{d-1,n}\left(t^{1/4}\right)\geqslant 1+t^{(n+1)/4},\] and therefore \[t^{(n+1)/4}\leqslant \frac{1}{4d}. \label{ineq:t}\tag{13}\]

Now we examine the geometry of the simplex \(\Lambda_{d,n}\) more closely. Partition all points of \(\Lambda_{d,n}\) into \(2^d\) subsets according to the parities of their coordinates (see Figure 3). For \(r=(r_1,\dots,r_d)\in \{0,1\}^d\), define \[\label{eq:def:Lambda:dnr} \Lambda_{d,n}^r\mathrel{\vcenter{:}}=\left\{(x_1,\dots,x_d)\in \Lambda_{d,n}\mid x_i\equiv r_i \pmod 2 \text{ for all } 1\leqslant i\leqslant d\right\}.\tag{14}\]

Then, clearly, \[\Lambda_{d,n}=\bigsqcup_{r\in \{0,1\}^d}\Lambda_{d,n}^r.\]

For each \(r\in \{0,1\}^d\), the set \(\Lambda_{d,n}^r\) looks like a simplex scaled by a factor of \(2\), with side length approximately \(n/2\). More precisely, \[\Lambda_{d,n}^r=r+2\Lambda_{d,n_r}, \label{eq:rec}\tag{15}\] where \[n_r\mathrel{\vcenter{:}}=\left\lfloor \frac{n-(r_1+\dots+r_d)}{2}\right\rfloor.\]

Formula 15 defines a bijection \[\tau_r\colon\Lambda_{d,n}^r\to\Lambda_{d,n_r}.\]

If \(X\subseteq \Lambda_{d,n}\), define \[\tau_r(X)\mathrel{\vcenter{:}}=\tau_r\left(X\cap\Lambda_{d,n}^r\right).\]

Thus, we may view a subset \(X\subseteq \Lambda_{d,n}\) as a collection of \(2^d\) subsets of the form \(\tau_r(X)\).

Consider \(1\leqslant k\leqslant d\) and \(\varepsilon\in \{0,1\}\), and define \[\label{eq:def:Lambda:dnke} \Lambda_{d,n}^{k,\varepsilon}\mathrel{\vcenter{:}}=\left\{(x_1,\dots,x_d)\in \Lambda_{d,n}\mid x_k\equiv \varepsilon \pmod 2\right\}\tag{16}\] (see Figure 3). We call subsets of \(\Lambda_{d,n}\) of this form binary layers. There are \(2d\) binary layers in total. Binary layers with the same \(k\) and different values of \(\varepsilon\) will be called complementary; the one with \(\varepsilon=0\) will be called large, and the one with \(\varepsilon=1\) small.

If in addition \(X\in \mathcal{C}_{d,n}\), then we call \(X\cap\Lambda_{d,n}^{k,\varepsilon}\) a partial cycle of type \((k,\varepsilon)\). The set of all such partial cycles is denoted by \(\mathcal{C}_{d,n}^{k,\varepsilon}\).

If \(1\leqslant k\leqslant d\) and \(\varepsilon\in \{0,1\}\), let \(R_{k,\varepsilon}\) denote the set of all binary strings of length \(d\) whose \(k\)-th coordinate is equal to \(\varepsilon\).

We will prove the following inequality: \[G_{d,n}(t)\leqslant \frac{1}{2d}\sum_{\substack{1\leqslant k\leqslant d\\ \varepsilon\in \{0,1\}}} \prod_{r\in R_{k,\varepsilon}} G_{d,n_r}\left(t^{1.5}\right). \label{eq}\tag{18}\]

Observe that this inequality immediately implies Proposition 10.

Let \(X\in \mathcal{C}_{d,n}\) be a nonzero cycle. Choose, according to Lemma 14, values of \(k\) and \(\varepsilon\) such that \[0<\left|X\cap\Lambda_{d,n}^{k,\varepsilon}\right|\leqslant |X|/2.\] Let \[Y=X\cap\Lambda_{d,n}^{k,\varepsilon}.\] We say that the cycle \(X\) is of type \((k,\varepsilon,Y)\).

In this way, we define a type for every nonzero cycle.

We now group the nonconstant terms on the left-hand side of 18 by type, and estimate the sum within each type using Lemma 13: \[G_{d,n}(t) = \sum_{X\in \mathcal{C}_{d,n}} t^{|X|} = 1+\sum_{X \text{ is of type }(k,\varepsilon,Y)} t^{|X|} \leqslant 1+\frac{1}{2d}\sum_{\substack{1\leqslant k\leqslant d\\ \varepsilon\in \{0,1\}}} \sum_{\substack{Y\in \mathcal{C}_{d,n}^{k,\varepsilon}\\ Y\neq \emptyset}} t^{1.5|Y|}.\] Equivalently, \[G_{d,n}(t) \leqslant \frac{1}{2d}\sum_{\substack{1\leqslant k\leqslant d\\ \varepsilon\in \{0,1\}}} \sum_{Y\in \mathcal{C}_{d,n}^{k,\varepsilon}} t^{1.5|Y|}.\]

Now fix \(k\) and \(\varepsilon\). Consider a partial cycle \(Y\in \mathcal{C}_{d,n}^{k,\varepsilon}\). The support of \(Y\) lies inside \[\Lambda_{d,n}^{k,\varepsilon}=\bigsqcup_{r\in R_{k,\varepsilon}} \Lambda_{d,n}^r,\] and \[t^{1.5|Y|} = \prod_{r\in R_{k,\varepsilon}} \left(t^{1.5}\right)^{|\tau_r(Y)|}.\]

By Lemma 12, all sets \(\tau_r(Y)\) are cycles in the corresponding simplices. Therefore the monomial \(t^{1.5|Y|}\) appears in the expansion of \[\prod_{r\in R_{k,\varepsilon}} G_{d,n_r}\left(t^{1.5}\right) = \prod_{r\in R_{k,\varepsilon}} \sum_{Z\in \mathcal{C}_{d,n_r}} \left(t^{1.5}\right)^{|Z|},\] namely by choosing in each factor the term corresponding to \(\tau_r(Y)\).

Different \(Y\) correspond to different such choices. Therefore, for positive \(t\), we obtain \[\sum_{Y\in \mathcal{C}_{d,n}^{k,\varepsilon}} t^{1.5|Y|} \leqslant \prod_{r\in R_{k,\varepsilon}} G_{d,n_r}\left(t^{1.5}\right),\] which completes the proof of 18 , and hence also of Proposition 10. ◻

Proof. Monotonicity is obvious. By Lemma 11, every nontrivial cycle has size at least \(n+1\), hence for \(0\leqslant t\leqslant 1\), \[G_{d,n}(t) \leqslant 1 + |\mathcal{C}_{d,n}|\, t^{n+1}.\]

It remains to estimate the total number of cycles. By part 1 of Lemma 10, a cycle is uniquely determined by its intersection with \(S_0\), and \[|S_0|\leqslant (n+1)^{d-1}.\] Therefore \[|\mathcal{C}_{d,n}| \leqslant 2^{(n+1)^{d-1}}.\qedhere\] ◻

Proof of Theorem 9. Base case: \(d=1\). We know that \[G_{1,n}(t)=1+t^{n+1}.\] Take \(a_1=6\). We must check that for \(s\geqslant 6\) and \(n\geqslant m^s\) one has \[\left(1-\frac{1}{m}\right)^{n+1} \leqslant n^{-s}.\] Using \((1-1/m)^m\leqslant e^{-1}\), it is enough to prove \[\frac{n+1}{m}\geqslant s\ln n.\] Since \(m\leqslant n^{1/s}\), it is enough to show that for \(n\geqslant m^s\geqslant 2^s\) we have \[n+1\geqslant s n^{1/s}\ln n;\] this holds for \(n=2^s\) since \(s\geqslant 6\), and also for larger \(n\) by convexity.

Induction step.

Fix \(a_{d-1}>d\) such that for all \(m\geqslant 2\), \(s\geqslant a_{d-1}\), and \(n>m^s\), one has \[G_{d-1,n}\!\left(1-\frac{1}{m}\right) < 1+n^{-s}.\]

Then, whenever \(t<1-\frac{1}{m}\) and \(n\geqslant m^{3a_{d-1}}\), we automatically have \[n \geqslant m^{3a_{d-1}} \geqslant (4m)^{a_{d-1}} \geqslant 8^d > 4d,\] and therefore \[G_{d-1,n}\left(\sqrt[4]{t}\right) \leqslant G_{d-1,n}\!\left(1-\frac{1}{4m}\right) < 1+n^{-a_{d-1}} < 1+\frac{1}{n} < 1+\frac{1}{4d}.\]

Hence the assumption of Proposition 10 is satisfied, so \[G_{d,n}(t) \leqslant \left( G_{d,\left\lfloor \frac{n-\epsilon}{2}\right\rfloor}\left(t^{1.5}\right) \right)^{2^{d-1}}\] for some \(0\leqslant \epsilon \leqslant d\). Since \(n>4d\), we have \[\left\lfloor \frac{n-\epsilon}{2}\right\rfloor \geqslant \frac{n}{4}.\]

Choose \(a_d\) large enough so that the following conditions hold: \[\begin{gather} \tag{19}a_d > 6a_{d-1};\\ \tag{20}x^{a_d\ln(1.5)/4} \geqslant 3x \cdot \ln 2 \cdot x^{3(d-1)a_{d-1}}\text{ for all }x\geqslant 2;\\ \tag{21}a_d > \frac{12}{\ln 1.5};\\ \tag{22}1.5^{x/24} \geqslant x\text{ for all }x\geqslant a_d;\\ \tag{23}x^{\ln1.5}/12 > 3\ln x\text{ for all }x\geqslant 2^{a_d};\\ \tag{24}1.5^{\frac{2}{3}x} \geqslant 3\ln 2\cdot dx\text{ for all }x\geqslant \dfrac{a_d}{8}. \end{gather}\]

These conditions will be used below. It is easy to check that each of them holds for all sufficiently large \(a_d\).

Assume now that \[t<1-\frac{1}{m},\qquad s\geqslant a_d,\qquad n\geqslant m^s.\]

We apply Proposition 10 repeatedly as long as possible. At each step, the parameter \(n\) decreases, and we may continue until \(n\) becomes smaller than \(m^{3a_{d-1}}\). The parameter \(t\) also decreases, but this does not interfere with the application of the lemma: \[\label{eq:fdn:recurrence} G_{d,n}(t) \leqslant \left(G_{d,n_1}\left(t^{1.5}\right)\right)^{2^{d-1}} \leqslant \left(G_{d,n_2}\left(t^{1.5^2}\right)\right)^{(2^{d-1})^2} \leqslant \dots \leqslant \left(G_{d,n_r}\left(t^{1.5^r}\right)\right)^{(2^{d-1})^r},\tag{25}\] where \((n_i)\) is a decreasing sequence of positive integers, with \[2 \leqslant \frac{n_i}{n_{i+1}} \leqslant 4, \qquad\text{and}\qquad n_r < m^{3a_{d-1}}.\]

This gives a lower bound on \(r\): \[r \geqslant \frac{\ln n - \ln m^{3a_{d-1}}}{\ln 4}.\]

By 19 , we have \(\ln m^{3a_{d-1}} < 0.5\ln n\), so \[r \geqslant \frac{\ln n}{4} \geqslant \frac{s\ln m}{4} \geqslant \frac{s}{8}. \label{neq:r}\tag{26}\]

By Lemma 15, for any \(0<\lambda<1\) we have \[G_{d,n_r}(\lambda) \leqslant 1 + 2^{(n_r+1)^{d-1}} \lambda^{n_r+1}\leqslant 1 + 2^{(m^{3a_{d-1}})^{d-1}}{\lambda},\] so 25 gives \[G_{d,n}(t) \leqslant \left( 1 + 2^{m^{3(d-1)a_{d-1}}} \, t^{1.5^r} \right)^{(2^{d-1})^r}.\]

We want to check that this is at most \(1+n^{-s}\).

If \(k\) is a positive integer and \(0 \leqslant 2kx<1\), then \[(1+x)^k \leqslant 1+2kx,\] which is easily proved by induction. So it is enough to verify \[2\cdot2^{m^{3(d-1)a_{d-1}}}\cdot t^{1.5^r}\cdot \left(2^{d-1}\right)^r < n^{-s}.\]

Taking logarithms, this becomes \[\ln 2 \cdot m^{3(d-1)a_{d-1}} + (\ln t)\cdot 1.5^r + \ln 2 \cdot (1+r(d-1)) < -s\ln n.\]

Since \(t<1-\frac{1}{m}\), we have \(\ln t < -\frac{1}{m}\). We also have \(r\geqslant \frac{s}{8} \geqslant 1\). Thus, it is enough to prove \[\label{eq:poly} \ln 2 \cdot m^{3(d-1)a_{d-1}} + s\ln n + \ln 2 \cdot dr < \frac{1.5^r}{m}.\tag{27}\]

To do this, we show that each of the three terms on the left is at most \(\frac{1.5^r}{3m}\).

1. By 26 and 20 , \[\label{eq:poly:1} 1.5^r \geqslant m^{s\ln1.5/4} \geqslant m^{a_d\ln1.5/4} \geqslant 3m\cdot \ln 2 \cdot m^{3(d-1)a_{d-1}}.\tag{28}\]

2. By 26 and 21 , \[\label{eq:2:a} \frac{r}{3} \geqslant \frac{s\ln m}{12}\geqslant\frac{a_d\ln m}{12}\geqslant\frac{\ln m}{\ln 1.5}.\tag{29}\] Again by 26 and 22 , we have \[\label{eq:2:b} 1.5^{r/3} \geqslant 1.5^{s/24} \geqslant s.\tag{30}\] By 26 and 23 , we also have \[\label{eq:2:c} \frac{r}{3} \geqslant \frac{\ln n}{12}\geqslant\frac{\ln(3\ln n)}{\ln 1.5}.\tag{31}\] Putting 29 , 30 and 31 together, we get \[\label{eq:poly:2} 3ms\ln n \leqslant 1.5^r.\tag{32}\]

3. By 29 , 26 and 24 , we have \[\label{eq:poly:3} 1.5^r \geqslant m\cdot1.5^{2r/3}\geqslant 3m\ln 2\cdot dr.\tag{33}\]

The desired 27 follows directly from 28 , 32 and 33 . ◻

Proof of the lower bound of Theorem 2. The lower bound holds for general even \(d\geqslant 2\). For \(\varepsilon>0\) small enough (depending on \(d\)), consider \(\beta>1/\varepsilon^2\) and an integer \(k\) such that \(k\in(1/\varepsilon,\beta\varepsilon)\) (if it exists). We consider the torus \({\mathbb{T}} _n\) with \(n=2^k\). Set \(\Omega'={\mathbb{F}} _2^{{\mathbb{T}} _n}\), and define the mapping \[\label{eq:def:Phi} \Phi\colon\Omega_{{\mathbb{T}} _n}\to\Omega'\colon\sigma\mapsto\left(\frac{1-[\sigma]_{x+T_d}}{2}\right)_{x\in{\mathbb{T}} _n}.\tag{34}\] from the spin configuration to the lamp configuration. Then, recalling the definitions of \(T_d\) from 1 and \(H\) from 2 , we have \[H_{{\mathbb{T}} _n}(\sigma)=-|{\mathbb{T}} _n|+2\sum_{x\in{\mathbb{T}} _n}\Phi(\sigma)_x,\] while \(\Phi(\sigma^x)=\Phi(\sigma)+\mathbb{I}_{x-T_d}\); here and below addition takes place in \({\mathbb{F}} _2^{{\mathbb{T}} _n}\), and for a set or element \(S\) we denote by \(\mathbb{I}_S\) the characteristic function of \(S\). We then see that the image of the Glauber dynamics on \({\mathbb{T}} _n\) via \(\Phi\) is the Markov process with generator \[\label{eq:def:L:prime}\mathcal{L}'f(\omega)=\sum_{x\in{\mathbb{T}} _n}\frac{e^{-2\beta\sum_{y\in x-T_d}(1-\omega_y)}}{e^{-2\beta\sum_{y\in x-T_d}\omega_y}+e^{-2\beta\sum_{y\in x-T_d}(1-\omega_y)}}\left(f(\omega+\mathbb{I}_{x-T_d})-f(\omega)\right).\tag{35}\] We denote by \(\pi\) the product Bernoulli measure on \(\Omega'\) with parameter \[\label{eq:def:p} p=1/(1+e^{2\beta})\in\left[1/(2e^{2\beta}),e^{-2\beta}\right],\tag{36}\] which is clearly invariant for this dynamics.

Consider a central box \(B=\{-L,\dots,L\}^d\) with \(L=2^{k-2}\). Define the events \[\begin{align} \mathcal{E}_0&{}=\left\{\omega\in\Omega'\mid\forall x\in B,\omega_x=0\right\},& \mathcal{E}_1&{}=\left\{\omega\in\Omega'\mid\omega_B=\mathbb{I}_{O}\right\}. \end{align}\] Recalling Definition 1 and Theorem 4, we say that \(\omega\in\Omega'\) is good if there exists a chain \((\omega^{(i)})_{i=0}^m\) such that \(\omega^{(0)}=\omega\), \(\omega^{(m)}_B=\mathbb{I}_{O}\) and \(|\omega^{(i)}|\mathrel{\vcenter{:}}=\sum_{x\in B}\omega^{(i)}_x\leqslant k-d-4\) for all \(i\in\{0,\dots,m\}\). Let \(\mathcal{G}\) be the set of good configurations. By Theorem 4 applied to the chain \((\omega^{(m-i)}+\omega^{(m)}+\mathbb{I}_O)_{i=0}^m\), we obtain \(\mathcal{G}\cap\mathcal{E}_0=\varnothing\). Indeed, we may apply Theorem 4 to \({\mathbb{T}} _m\) rather than to \({\mathbb{Z}} ^d\) when \(m\geqslant 4+3d2^{k+1}\): consider a counterexample chain on the torus of minimal length; then all its configurations are supported in \(B_k+\{-1,0,1\}^d\), so it lifts to a chain on \({\mathbb{Z}} ^d\) that contradicts Theorem 4. Consequently, \[\mathop{\mathrm{Var}}'(\mathbb{I}_{\mathcal{G}})=\pi(\mathcal{G})(1-\pi(\mathcal{G}))\geqslant\pi(\mathcal{E}_1)\pi(\mathcal{E}_0)=p(1-p)^{2|B|-1}.\] Moreover, \[\begin{align} \mathcal{D}'\left(\mathbb{I}_{\mathcal{G}}\right)&{}=-\pi\left(\mathbb{I}_\mathcal{G}\mathcal{L}'\mathbb{I}_\mathcal{G}\right)\leqslant 2\sum_{x\in{\mathbb{T}} _n}\pi\left(\omega\in\mathcal{G}\not\ni\omega+\mathbb{I}_{x-T_d}\right)\\ &{}\leqslant 2|B+T_d|\pi\left(\sum_{x\in B}\omega_x>k-d-4-|T_d|\right) \leqslant 2|B+T_d|(p|B|)^{k-2d-4}. \end{align}\] Putting these inequalities together, we obtain \[\begin{align} \nonumber\frac{\mathop{\mathrm{Var}}'(\mathbb{I}_\mathcal{G})}{\mathcal{D}'(\mathbb{I}_\mathcal{G})}&{}\geqslant\frac{p(1-p)^{2|B|-1}}{2|B+T_d|(p|B|)^{k-2d-4}}\geqslant p^2\left(p2^{dk}\right)^{2d+4-k}\\ &{}\geqslant e^{(2-\varepsilon d\ln 2)\beta(k-2d-4)-4\beta}/4\geqslant e^{\beta k(2-\varepsilon d\ln 2)(1-\varepsilon(2d+9))}\geqslant e^{2\beta k (1-O(\varepsilon))}.\label{eq:trel:lower39} \end{align}\tag{37}\]

Recalling 5 , the proof is concluded by Lemma 16 below. ◻

Proof. Note that \(|\Omega_{{\mathbb{T}} _n}|=|\Omega'|\), that \(\Phi\) is a group homomorphism, and that \(\Omega'_{{\mathbb{T}} _n}\) is a vector space with basis \((\mathbb{I}_x)_{x\in{\mathbb{T}} _n}\). Therefore, it is enough to show that, for any \(x\in{\mathbb{T}} _n\), there exists \(\sigma\in\Omega_{{\mathbb{T}} _n}\) such that \(\Phi(\sigma)=\mathbb{I}_{x}\). By symmetry we only show this for \(x=O\). Indeed, the Sierpinski gasket configuration (see Figure 4) \[\label{eq:Sierpinski} \sigma_y=(-1)^{\binom{-\sum_{i=1}^dy_i}{-y_1,\dots,-y_d}}\tag{38}\] for \(-y\in\{0,\dots,n-1\}^d\) verifies this property for \(d\) even and \(n\) power of \(2\). ◻

Proof. Fix \(\varepsilon>0\) and finite \(\Lambda\subset{\mathbb{Z}} ^d\). We will prove (independently) in Section 3.4 that the Gibbs measure \(\mu\) is unique. Consequently, we can find \(\Lambda'\supset\Lambda+\{-1,0,1\}^d=:\Lambda_+\) large enough so that \[\sup_{\tau\in\Omega_{{\mathbb{Z}} ^d\setminus\Lambda'}}d_{\mathrm{TV}}\left(\mu^\tau_{\Lambda_+},\mu_{\Lambda_+}\right)<\varepsilon\] (\(d_{\mathrm{TV}}\) is the total variation distance, that is, half of the \(\ell^1\)-distance), where \(\mu^\tau_{\Lambda_+}\) is the marginal of \(\mu^\tau_{\Lambda'}\) on \(\Lambda_+\) and similarly for \(\mu\) instead of \(\mu^\tau_{\Lambda'}\). Note that \(\Omega\to\Omega'_\Lambda:\sigma\mapsto\Phi(\sigma)_{\Lambda}\) is local with support contained in \(\Lambda_+\) and surjective. Indeed, we may change the value at a single vertex in \(\Lambda\) by adding to \(\sigma\) a large enough Sierpiński gasket translated at that vertex (see 38 and Figure 4).

Consider the image under \(\Phi\) of the chain with generator \(\mathcal{L}_{\Lambda'}^\tau\). As above, it is a Markov chain, with invariant measure \(\pi^\tau_{\Lambda'}=\pi_{\Lambda'-T_d}(\cdot\mid\Omega'_{\Lambda',\tau})\), where \(\Omega'_{\Lambda',\tau}\subseteq\Omega'_{\Lambda'}\mathrel{\vcenter{:}}={\mathbb{F}} _2^{\Lambda'-T_d}\) is the irreducible component of \(\mathcal{L}\) induced by the boundary condition \(\tau\). In particular, \(\Omega'_{\Lambda',\tau}\) are either equal or disjoint for different \(\tau\in\Omega_{{\mathbb{Z}} ^d\setminus\Lambda'}\). By the surjectivity above, \(\bigcup_{\tau\in\Omega_{{\mathbb{Z}} ^d\setminus\Lambda'}}\Omega'_{\Lambda',\tau}=\Omega'_{\Lambda'}\), so we can find a probability measure \(\mathrm d\theta(\tau)\) on \(\Omega_{{\mathbb{Z}} ^d\setminus\Lambda'}\) such that \(\theta(\pi_{\Lambda'}^\tau)=\pi_{\Lambda'}\). Since, for any \(\tau,\tau'\in\Omega_{{\mathbb{Z}} ^d\setminus\Lambda'}\), \[d_{\mathrm{TV}}(\pi^\tau_{\Lambda},\pi^{\tau'}_{\Lambda})\leqslant d_{\mathrm{TV}}(\mu_{\Lambda+}^\tau,\mu_{\Lambda_+}^{\tau'})\leqslant 2\varepsilon,\] we deduce \[d_{\mathrm{TV}}\left(\pi_{\Lambda},\Phi(\mu)_\Lambda\right)\leqslant 2\varepsilon+\sup_{\tau\in\Omega_{{\mathbb{Z}} ^d\setminus\Lambda'}}d_{\mathrm{TV}}\left(\pi_\Lambda^\tau,\Phi(\mu)_\Lambda\right)\leqslant 2\varepsilon+\sup_{\tau\in\Omega_{{\mathbb{Z}} ^d\setminus\Lambda'}}d_{\mathrm{TV}}\left(\mu^\tau_{\Lambda_+},\mu_{\Lambda_+}\right)\leqslant 3\varepsilon.\] Therefore, \(\pi=\Phi(\mu)\). ◻

Proof of the lower bound of Theorem 1. The rest of the proof proceeds exactly as the lower bound of Theorem 2, so we only indicate the non-trivial changes.

Fix \(d\geqslant 2\) and \(\beta>0\). Let \(k=\lceil\beta/(d\ln 2)\rceil\), \(L=3d2^k\), \(B=\{-L,\dots,L\}^d\), so that \[e^{\beta}\leqslant L^d\leqslant|B|\leqslant(3L)^d\leqslant(18d)^de^{\beta}.\] Define \(\mathcal{G}\subset\Omega'\) as in the proof of Theorem 2 with chains featuring at most \(k\) lamps ON (instead of \(k-d-4\)). Then, we similarly get \[\label{eq:trel:lower} \frac{\mathop{\mathrm{Var}}'(\mathbb{I}_\mathcal{G})}{\mathcal{D}'(\mathbb{I}_\mathcal{G})}\geqslant\frac{p(1-p)^{2|B|-1}}{2|B+T_d|(p|B|)^{k-d}}\geqslant c e^{c\beta^2}\tag{39}\] for a small enough \(c=c(d)>0\). By Lemma 17 and 39 , plugging the local function \(\mathbb{I}_{\Phi^{-1}(\mathcal{G})}\) into 5 gives the desired lower bound on \(T_{\mathrm{rel}}\). ◻

Proof of the lower bound of Theorem 3. Fix \(d\geqslant 2\), \(\alpha_d\leqslant 1\) and \(n_d\) as in Theorem 8. Let \(\beta>0\) and \(n\geqslant n_d\) satisfy \(n\leqslant e^{2\beta/(5d)}\). Let \(\Lambda=-\Lambda_{d,n}\). Define the mapping \[\Phi\colon\Omega_{\Lambda}\to{\mathbb{F}} _2^{{\mathbb{Z}} ^d}\colon\sigma\mapsto\left(\frac{1-[\sigma\cdot\mathbf{1}_{{\mathbb{Z}} ^d\setminus\Lambda}]_{x+T_d}}{2}\right)_{x\in{\mathbb{Z}} ^d}.\]

By Theorem 8, let \(X\in\Omega'\) be such that any chain from \(X\) to \(\varnothing\) goes through \[\mathcal{X}\mathrel{\vcenter{:}}=\left\{X'\in\Omega'\middle|\;|X'\setminus X|\geqslant n^{\alpha_d}+3|X\setminus X'|/2\right\}.\] By Lemma 18, let \(\sigma=\Phi^{-1}(\mathbb{I}_{-X})\). Let \(\mathcal{G}\subset\Omega_\Lambda\) be the set of configurations which can be reached from \(\mathbf{1}_\Lambda\) by switching the state of one spin in \(\Lambda\) at a time without going through \(\partial\mathcal{G}\mathrel{\vcenter{:}}=\Phi^{-1}(\{\mathbb{I}_{-X'}\mid X'\in\mathcal{X}\})\). In particular, \(\sigma\not\in\mathcal{G}\ni\mathbf{1}_\Lambda\).

Thus, \[\label{eq:finite:lower:var} \mathop{\mathrm{Var}}_{\Lambda}^\mathbf{1}(\mathbb{I}_\mathcal{G})\geqslant\frac{1}{2}\min\left(\mu_\Lambda^\mathbf{1}(\mathbf{1}_\Lambda),\mu_{\Lambda}^\mathbf{1}(\sigma)\right)=\frac{\mu_\Lambda^\mathbf{1}(\sigma)}{2}.\tag{40}\] Moreover, by 2 , for \(X'\in\Omega'\), \[H_\Lambda^\mathbf{1}(\mathbf{1}_\Lambda)=-|\Lambda-T_d|=H_\Lambda^\mathbf{1}\left(\Phi^{-1}\left(\mathbb{I}_{-X'}\right)\right)-2|X'|,\] so \[\label{eq:finite:lower:mu:sigma} \mu^\mathbf{1}_\Lambda(\sigma)=\frac{e^{-2\beta|X|}}{\sum_{X'\in\Omega'}e^{-2\beta|X'|}}\geqslant\frac{e^{-2\beta|X|}}{(1+e^{-2\beta})^{|\Lambda-T_d|}}\geqslant\exp\left(-2\beta|X|-e^{-2\beta}|\Lambda-T_d|\right).\tag{41}\]

Similarly, recalling 4 , we get \[\begin{align} \nonumber\mathcal{D}_\Lambda^\mathbf{1}(\mathbb{I}_\mathcal{G})&{}\leqslant 2 \sum_{x\in\Lambda}\sum_{\sigma'\in\Omega_\Lambda}\mu_\Lambda^\mathbf{1}(\sigma')\mathbb{I}_{\sigma'\not\in\mathcal{G}\ni(\sigma')^x}\leqslant 2|\Lambda|\mu^\mathbf{1}_\Lambda(\partial\mathcal{G})=2|\Lambda|\sum_{X'\in\mathcal{X}}\mu_\Lambda^\mathbf{1}\left(\Phi^{-1}\left(\mathbb{I}_{-X'}\right)\right)\\ \nonumber&{}\leqslant 2|\Lambda|\sum_{X'\in\mathcal{X}}e^{-2\beta|X'|}\leqslant 2|\Lambda|e^{-2\beta|X|}\sum_{X'\in\mathcal{X}}e^{-2\beta(4n^{\alpha_d}/5+(|X'\setminus X|+|X\setminus X'|)/5)}\\ \nonumber&{}\leqslant 2|\Lambda|e^{-2\beta(|X|+4n^{\alpha_d}/5)}\sum_{Y\subseteq\Lambda-T_d}e^{-2\beta|Y|/5}=2|\Lambda|e^{-2\beta(|X|+4n^{\alpha_d}/5)}\left(1+e^{-2\beta/5}\right)^{|\Lambda-T_d|}\\ &{}\leqslant 2|\Lambda|\exp\left(-2\beta(|X|+4n^{\alpha_d}/5)+|\Lambda-T_d|e^{-2\beta/5}\right). \label{eq:finite:lower:D} \end{align}\tag{42}\]

Finally, recalling 5 and combining 40 , 41 and 42 , we obtain \[\begin{align} T_{\mathrm{rel}}^{\Lambda,\mathbf{1}}&{}\geqslant\frac{\exp(8\beta n^{\alpha_d}/5-|\Lambda-T_d|e^{-2\beta/5}-|\Lambda-T_d|e^{-2\beta})}{4|\Lambda|}\\&{}\geqslant\exp\left(8\beta n^{\alpha_d}/5-2^{d+1}-(d+2)\ln(2d)-2\beta/5\right)\geqslant\frac{e^{\beta n^{\alpha_d}}}{C}, \end{align}\] since \(|\Lambda|\leqslant|\Lambda-T_d|\leqslant(2n)^d\leqslant 2^de^{2\beta/5}\), taking \(C=(2d)^{d+2}e^{2^{d+1}}\). ◻

Proof of the upper bound of Theorem 2. Fix \(d=2\) and \(\beta>0\). The result follows immediately, once we prove by induction that, for \(k\geqslant 0\) \[T_{\mathrm{rel}}^{{\mathbb{T}} _{2^k}}\leqslant\left(41472\cdot e^{2\beta}\right)^{k}.\] The base case \(k=0\) is clear and uses that \(d\) is even (the dynamics is not irreducible for \(d\) odd).

Assume \(k\geqslant 1\) and let \(n=2^k\). Recall \(\Phi\) and \(p\) from 34 and 36 . As in Section 3.1, let \(\pi\) denote the product Bernoulli measure with parameter \(p\) on \(\Omega'_{{\mathbb{T}} _{n}}={\mathbb{F}} _2^{{\mathbb{T}} _n}\) and \(\mathop{\mathrm{Var}}'\) be its variance. By Lemma 16, we may reason in terms of the lamp Markov chain with generator as in 35 . For \(r=(r_1,\dots,r_d)\in\{0,1\}^d\), let \[{\mathbb{T}} ^r_n=\left\{(x_1,\dots,x_d)\in{\mathbb{T}} _n\mid\forall i\in\{1,\dots,d\},x_i=r_i\pmod 2\right\}=r+2{\mathbb{T}} _n,\] taking into account that \(n\) is even. For \(A\subseteq{\mathbb{T}} _n\) and \(\omega\in\Omega'_{{\mathbb{T}} _n}\), we write \(\omega^A=\omega+\mathbb{I}_A\). Let \[\begin{align} \mathcal{L}^rf(\omega)&{}=\sum_{x\in{\mathbb{T}} _n^r}\frac{\pi(\omega^{x-2T_d})}{\pi(\omega)+\pi(\omega^{x-2T_d})}\left(f\left(\omega^{x-2T_d}\right)-f(\omega)\right),\\ \tag{43}\mathcal{D}^r(f)&{}=\sum_{\omega\in\Omega'_{{\mathbb{T}} _n}}\sum_{x\in{\mathbb{T}} _n^r}\frac{\pi(\omega)\pi(\omega^{x-2T_d})}{\pi(\omega)+\pi(\omega^{x-2T_d})}\left(f\left(\omega^{x-2T_d}\right)-f(\omega)\right)^2=-\pi\left(f\mathcal{L}^rf\right),\\ \tag{44}T_{\mathrm{rel}}^r&{}=\left(\inf\left\{\frac{\mathcal{D}^r(\pi_{{\mathbb{T}} _n\setminus{\mathbb{T}} _n^r}(f))}{\mathop{\mathrm{Var}}'\left(\pi_{{\mathbb{T}} _n\setminus{\mathbb{T}} _n^r}(f)\right)}\middle| f\colon\Omega'_{{\mathbb{T}} _n}\to{\mathbb{R}} ,\mathop{\mathrm{Var}}'(\pi_{{\mathbb{T}} _n\setminus{\mathbb{T}} _n^r}(f))\neq0\right\}\right)^{-1}. \end{align}\]

Fix \(f\colon\Omega'_{{\mathbb{T}} _n}\to{\mathbb{R}}\). By the Poincaré inequality for independent Glauber dynamics (the Efron–Stein inequality) and 44 , we have \[\label{eq:var39}\mathop{\mathrm{Var}}'(f)\leqslant\sum_{r\in\{0,1\}^d}\pi\left(\mathop{\mathrm{Var}}'_{{\mathbb{T}} ^r_{n}}(f)\right)\leqslant\sup_{r\in\{0,1\}^d}T_{\mathrm{rel}}^{r}\sum_{r\in\{0,1\}^d}\pi\left(\mathcal{D}^r(f)\right)=T_{\mathrm{rel}}^{{\mathbb{T}} _{n/2}}\sum_{r\in\{0,1\}^d}\pi\left(\mathcal{D}^r(f)\right).\tag{45}\]

We finally seek to relate each term in \(\pi(\mathcal{D}^r(f))\) to appropriate terms featuring in \(\mathcal{D}(f)\). Consider \(r\in\{0,1\}^d\), \(x\in{\mathbb{T}} ^r_{n}\) and \(\omega\in\Omega'_{{\mathbb{T}} _n}\). Set \(\Omega''=\{\omega\in\Omega'_{{\mathbb{T}} _n}\mid\sum_{y\in x-2T_d}\omega_y\in\{2,3\}\}\). In view of the symmetry between \(\omega\) and \(\omega^{x-2T_d}\) in 43 , we may assume \(\omega\in\Omega''\). Define the configurations \(\omega=\omega^{(0)},\omega^{(1)},\omega^{(2)},\omega^{(3)}=\omega^{x-2T_d}\) as indicated in Figure 5. The Cauchy–Schwarz inequality gives \[\left(f\left(\omega^{x-2T_d}\right)-f(\omega)\right)^2\leqslant 3\sum_{i=1}^3\left(f\left(\omega^{(i)}\right)-f\left(\omega^{(i-1)}\right)\right)^2.\] Summing over \(\omega\in\Omega''\), we get \[\begin{align} \label{eq:paths} &2\sum_{\omega\in\Omega''}\frac{\pi(\omega)\pi(\omega^{x-2T_d})}{\pi(\omega)+\pi(\omega^{x-2T_d})}\left(f\left(\omega^{x-2T_d}\right)-f(\omega)\right)^2\leqslant 2\sum_{\omega\in\Omega''}\pi(\omega)\left(f\left(\omega^{x-2T_d}\right)-f(\omega)\right)^2\\ \nonumber&{}\leqslant 6\sum_{i=1}^3\sum_{\omega\in\Omega''}\pi(\omega)\left(f\left(\omega^{(i)}\right)-f\left(\omega^{(i-1)}\right)\right)^2 \underbrace{\sum_{y\in x-T_d}\mathbb{I}_{\omega^{(i-1)}=(\omega^{(i)})^{y-T_d}}}_{=1}\underbrace{ \sum_{\omega'\in \Omega'_{{\mathbb{T}} _n}}\mathbb{I}_{\omega'=\omega^{(i)}}\frac{\pi(\omega')\pi((\omega')^{y-T_d})}{\pi(\omega')\pi((\omega')^{y-T_d})}}_{=1}\\ &{}= 6 \begin{multlined}[t][\dimexpr\textwidth - \lhswidth - 0.5em] \sum_{\omega'\in\Omega'_{{\mathbb{T}} _n}}\sum_{y\in x-T_d}\left(f\left(\omega'\right)-f\left(\left(\omega'\right)^{y-T_d}\right)\right)^2\frac{\pi(\omega')\pi((\omega')^{y-T_d})}{\pi(\omega')+\pi((\omega')^{y-T_d})}\\ \times\underbrace{\sum_{i=1}^3\sum_{\omega\in\Omega''}\mathbb{I}_{\omega^{(i)}=\omega',\omega^{(i-1)}=(\omega')^{y-T_d}}\frac{\pi(\omega)(\pi(\omega')+\pi((\omega')^{y-T_d}))}{\pi(\omega')\pi((\omega')^{y-T_d})}}_{=:K(\omega,\omega',i,y)}.\end{multlined} \nonumber \end{align}\tag{46}\]

A direct inspection of Figure 5 shows that, for any \(\omega\in\Omega''\) and any \(j\in\{0,\dots,3\}\) we have \(\|\omega^{(j)}\|_1-\|\omega\|_1\leqslant 1\) (this property is specific to \(d=2\)). Consequently, \[\begin{align} \sup_{\omega'\in\Omega'_{{\mathbb{T}} _n},y\in x-T_d}K\left(\omega,\omega',i,y\right)&{}\leqslant\frac{2}{p}\sup_{\omega'\in\Omega'_{{\mathbb{T}} _n}}\sum_{i=1}^3\sum_{\omega\in\Omega''}\mathbb{I}_{\omega^{(i)}=\omega'}\\ &{}\leqslant\frac{6}{p}\left|\left\{\omega\in\Omega''\middle|\omega_{{\mathbb{T}} _n\setminus (x-T_d-T_d)}=\omega'_{{\mathbb{T}} _n\setminus(x-T_d-T_d)}\right\}\right|=\frac{6\cdot 2^6}{2p}. \end{align}\]

Combining this with 5 , 4 , 45 , 46 , we obtain \[T_{\mathrm{rel}}^{{\mathbb{T}} _n}\leqslant T_{\mathrm{rel}}^{{\mathbb{T}} _{n/2}}\cdot \frac{1152}{p}\cdot6\cdot\sup_{y\in{\mathbb{T}} _n}\left|\left\{x\in{\mathbb{T}} _n\middle| y\in x-T_d\right\}\right|=T_{\mathrm{rel}}^{{\mathbb{T}} _{n/2}}\cdot\frac{20736}{p},\] completing the induction step in view of 36 . ◻

Proof. Recalling 5 , we consider \(f\colon\Omega_{-\Lambda_{d,n}}\to{\mathbb{R}}\) and may assume that there exist \(\sigma,\sigma'\in\Omega_{-\Lambda_{d,n}}\) with \(f(\sigma)=0\leqslant f(\sigma'')\leqslant f(\sigma')=1\) for all \(\sigma''\in\Omega_{-\Lambda_{d,n}}\). In particular, \(\mathop{\mathrm{Var}}_{-\Lambda_{d,n}}^\tau(f)\leqslant 1\). On the other hand, we may fix a sequence \(\sigma^{(0)},\dots,\sigma^{(m)}\) such that \(\sigma^{(0)}=\sigma\), \(\sigma^{(m)}=\sigma'\), \(\|\sigma^{(i)}-\sigma^{(i-1)}\|_1=1\) for \(i\in\{1,\dots,m\}\) (we change one spin at a time) and \(m\leqslant|\Lambda_{d,n}|\). Then there exists \(k\in\{1,\dots,m\}\) such that \(f(\sigma^{(k)})-f(\sigma^{(k-1)})\geqslant 1/m\). Write \(\sigma^{(k)}-\sigma^{(k-1)}=2\mathbb{I}_x\), with \(\mathbb{I}_x\) the characteristic function of \(x\in-\Lambda_{d,n}\). Then \[\begin{align} \mathcal{D}^{\tau}_{-\Lambda_{d,n}}(f)&{}\overset{\eqref{eq:def:D}}\geqslant\mu_{-\Lambda_{d,n}}^\tau\left(\sigma^{(k)}\right)\mathop{\mathrm{Var}}_x(f)\left(\sigma^{(k)}\right)\geqslant\mu_{-\Lambda_{d,n}}^\tau\left(\sigma^{(k)}\right)\cdot\frac{\min(\mu^\tau_{-\Lambda_{d,n}}(\sigma^{(k)}),\mu^\tau_{-\Lambda_{d,n}}(\sigma^{(k-1)}))}{2m^2(\mu^\tau_{-\Lambda_{d,n}}(\sigma^{(k)})+\mu^\tau_{-\Lambda_{d,n}}(\sigma^{(k-1)}))} \\ &{}\overset{\eqref{eq:def:H}}\geqslant\frac{\mu^\tau_{-\Lambda_{d,n}}(\sigma^{(k)})}{2m^2(1+e^{2(d+1)\beta})}\geqslant\frac{\min\{\mu^\tau_{-\Lambda_{d,n}}(\bar\sigma)\mid\bar \sigma\in\Omega_{-\Lambda_{d,n}}\}}{4|\Lambda_{d,n}|^2e^{2(d+1)\beta}} \\ &{} \overset{\eqref{eq:def:H}}\geqslant\frac{\min_{\bar\sigma}e^{-\beta H^\tau_{-\Lambda_{d,n}}(\bar\sigma)}}{|\Omega_{-\Lambda_{d,n}}|\max_{\bar\sigma} e^{-\beta H^\tau_{-\Lambda_{d,n}}(\bar\sigma)}}\cdot\frac{1}{4|\Lambda_{d,n}|^2e^{2(d+1)\beta}}\overset{\eqref{eq:def:H}}\geqslant\frac{e^{-2\beta|-\Lambda_{d,n}-T_d|}}{|\Omega_{-\Lambda_{d,n}}|\cdot |\Lambda_{d,n}|^2\cdot4e^{2(d+1)\beta}}\\ &{}\geqslant\frac{e^{-(2\beta+2)|\Lambda_{d,n+1}|}}{4e^{2(d+1)\beta}} \end{align}\] using \(n\geqslant 1,d\geqslant 2\) in the last inequality. Plugging this into 5 and using \(n\geqslant 1,d\geqslant 2\) again, we obtain the desired inequality. ◻

Proof of the upper bound of Theorem 1. The starting point is the same high temperature expansion as in Chleboun17?*Section 4.0.1, which we recall for completeness. Fix a positive integer \(d\), \(\beta>0\) and set \(\theta=\tanh(\beta)\). For any \(u\in\{-1,1\}\), we have \[e^{\beta u}=\cosh(\beta)(1+u\theta).\] Consequently, for any finite \(\Lambda\subset{\mathbb{Z}} ^d\) and \(\tau\in\Omega_{{\mathbb{Z}} ^d\setminus\Lambda}\), we have \[\begin{align} Z^\tau_\Lambda&{}=\sum_{\sigma\in\Omega_\Lambda}\prod_{x\in\Lambda-T_d}e^{\beta[\sigma\cdot\tau]_{x+T_d}}=(\cosh(\beta))^{|\Lambda-T_d|}\sum_{X\subset\Lambda-T_d}\theta^{|X|}\sum_{\sigma\in\Omega_\Lambda}\prod_{x\in X}[\sigma\cdot\tau]_{x+T_d}\\ &{}=(\cosh(\beta))^{|\Lambda-T_d|}\sum_{X\in\mathcal{C}_{(-T_d,\Lambda-T_d)}}\theta^{|X|}\sum_{\sigma\in\Omega_\Lambda}\prod_{x\in X}[\sigma\cdot\tau]_{x+T_d}, \end{align}\]

recalling the set of \((A,B)\)-cycles \(\mathcal{C}_{A,B}\) from Section 2.3.1. We set \(\mathcal{Z}_\Lambda^\tau=Z_\Lambda^\tau2^{-|\Lambda|}(\cosh(\beta))^{-|\Lambda-T_d|}\) to obtain \[\max_{\tau\in\Omega_{{\mathbb{Z}} ^d\setminus\Lambda}}\left|\mathcal{Z}_\Lambda^\tau-1\right|\leqslant\sum_{X\in\mathcal{C}_{(-T_d,\Lambda-T_d)}\setminus\{\varnothing\}}\theta^{|X|}.\]

Recalling 6 and 12 , we get \[\max_{\tau\in\Omega_{{\mathbb{Z}} ^d\setminus (-\Lambda_{d,n})}}\big|\mathcal{Z}^\tau_{-\Lambda_{d,n}}-1\big|\leqslant G_{d,n+1}(\theta)-1\] for any positive integer \(n\).

The rest of the proof diverges from Chleboun17?. Set \(m=\lceil1/(1-\theta)\rceil\geqslant 2\) and fix a positive integer \(a_d\geqslant d^2\) such that Theorem 9 holds and \[\label{eq:nNconditions} 2^{a_d-d^2}\geqslant 4(6d)^{d(d+1)}\tag{47}\] (the latter is clearly true for \(a_d\) large enough). Then Theorem 9 gives \[\label{eq:Z:close:to:1} n\geqslant m^{a_d}\Longrightarrow \max_{\tau\in\Omega_{{\mathbb{Z}} ^d\setminus(-\Lambda_{d,n})}}\left|\mathcal{Z}^\tau_{-\Lambda_{d,n}}-1\right|\leqslant n^{-a_d}.\tag{48}\] This result will combine with the following observation.

Fix \[\begin{align} \label{eq:def:N} n&{}=m^{a_d},&N&{}=(3d)^{d+1}(n+1)^d, \end{align}\tag{49}\] so that \[\begin{align} \tag{50} N^d/(3d^d)&{}\geqslant 3^dN^{d-1}d(n+1)^d\geqslant(n+1)^d(d+1)(N+2)^{d-1}\\ \nonumber&{}\geqslant(N+2)^{2d-1}(d+1)N^{-d}\geqslant(N+2)^{2d-1}(d+1)(6d)^{-(d+1)d}n^{-d^2}\\ \tag{51}&{}\geqslant(N+1)^d(N+2)^{d-1}(d+1)4n^{-a_d}, \end{align}\] thanks to 47 in the last inequality. Let us consider the following block dynamics on a \(d\)-dimensional torus \({\mathbb{T}} ={\mathbb{T}} _L\) of side length \(L>N+1\) which we first describe via its graphical representation. Endow each \(x\in{\mathbb{T}}\) with a Poisson clock of unit rate which rings at times \(P_x\subset(0,\infty)\). When the clock at \(x\) rings, change the current configuration \(\sigma\) to \(\tau\cdot\sigma'\) with \(\tau=\sigma_{{\mathbb{T}} \setminus (x-\Lambda_{d,N})}\) and \(\sigma'\) chosen at random according to \(\mu_{x-\Lambda_{d,N}}^{\tau}\); that is, we fully resample the configuration in a simplex region conditionally on the configuration outside of it. In other words, this is the Markov process with generator and Dirichlet form given by \[\begin{align} \mathcal{L}_{\mathbb{T}} f&{}=\sum_{x\in{\mathbb{T}} }\left(\mu_{x-\Lambda_{d,N}}(f)-f\right),&\mathcal{D}_{\mathbb{T}} (f)&{}=\sum_{x\in{\mathbb{T}} }\mu_{\mathbb{T}} \left(\mathop{\mathrm{Var}}_{x-\Lambda_{d,N}}(f)\right). \end{align}\]

We next resort to the path coupling method (see Levin09?*Chapter 14). It is used to show that a Markov chain (the block dynamics we just defined) converges to its invariant measure exponentially fast. To be able to apply it, we need to couple two copies of the chain with different initial conditions in such a way that their \(\ell^1\)-distance (number of discrepancies) is contracted in expectation. By a well-known reduction, it suffices to treat initial conditions that only differ at a single site.

Consider a configuration \(\sigma\in\Omega_{\mathbb{T}}\) and \(x\in{\mathbb{T}}\). Recall that \(\sigma^x\) is the configuration that only differs from \(\sigma\) at \(x\). We construct a coupling between the Markov process \((\sigma(t))_{t\geqslant 0}\) with initial state \(\sigma\) and the one with initial state \(\sigma^x\) denoted by \((\sigma'(t))_{t\geqslant 0}\) as follows. Let \((\xi_{y,t})_{y\in{\mathbb{T}} ,t\in P_y}\) be a sequence of i.i.d.Bernoulli random variables with parameter \(1-4n^{-a_d}\). We use the same Poisson clocks \((P_y)_{y\in{\mathbb{T}} }\) for both processes. Both processes remain constant outside the clock ring times \(\bigcup_{y\in {\mathbb{T}} }P_y\). Assume the coupling is constructed until the clock ring time \(t\in P_y\) for some \(y\in{\mathbb{T}}\). Set \(\partial\Lambda=y+((-\Lambda_{d,N}+(-T_d)+T_d)\setminus(-\Lambda_{d,N}))\), \(\tau=\sigma_{{\mathbb{T}} \setminus(y-\Lambda_{d,N})}(t-)\), \(\tau'=\sigma_{{\mathbb{T}} \setminus(y-\Lambda_{d,N})}'(t-)\). If \(x\in\partial\Lambda\), fix \(z\in{\mathbb{T}}\) so that \(z-\Lambda_{d,n}\subset y-\Lambda_{d,N}\) and \(x\) is at \(\ell^1\)-distance at least 3 from \((y-\Lambda_{d,N})\setminus(z-\Lambda_{d,n})\), see Figure 6. We construct \(\sigma(t)\) and \(\sigma'(t)\) by the following rules.

1. If \(x\in {\mathbb{T}} \setminus(y-\Lambda_{d,N}+(-T_d)+T_d)\) and \(\tau^x=\tau'\), we define \(\sigma(t)=\tau\cdot\eta\) and \(\sigma'(t)=\tau'\cdot\eta\) with \(\eta\) distributed according to \(\mu^\tau_{y-\Lambda_{d,N}}=\mu^{\tau'}_{y-\Lambda_{d,N}}\). That is, if \(x\) is far from the update block, it does not influence the update.

2. If \(x\in y-\Lambda_{d,N}\) and \(\tau=\tau'\), we define \(\sigma(t)=\sigma'(t)=\tau\cdot\eta\) with \(\eta\) distributed according to \(\mu^\tau_{y-\Lambda_{d,N}}=\mu^{\tau'}_{y-\Lambda_{d,N}}\). That is, if \(x\) is inside the block and the boundary conditions coincide, the two processes coalesce.

3. If \(\tau'=\tau^x\), \(x\in\partial\Lambda\) and \(\xi_{y,t}=1\), we define \(\sigma(t)=\tau\cdot\kappa\cdot\eta\) and \(\sigma'(t)=\tau'\cdot\kappa\cdot\eta'\) with \(\kappa\) distributed according to \(\mu^\tau_{(y-\Lambda_{d,N})\setminus(z-\Lambda_{d,n})}\) and, conditionally on \(\kappa\), \((\eta,\eta')\) distributed according to \(\mu^{\tau\cdot\kappa}_{z-\Lambda_{d,n}}\otimes\mu^{\tau'\cdot\kappa}_{z-\Lambda_{d,n}}\). That is, if \(x\) is on the boundary of the block, the boundary conditions coincide except at \(x\), and we are lucky, we ensure that the two processes coincide outside the small simplex close to \(x\).

4. If \(\tau'=\tau^x\), \(x\in\partial\Lambda\) and \(\xi_{y,t}=0\), we define \(\sigma(t)=\tau\cdot\eta\) and \(\sigma'(t)=\tau'\cdot\eta'\) with \(\eta\) and \(\eta'\) independent with distributions such that the total marginals with the previous case are \(\mu^\tau_{y-\Lambda_{d,N}}\) and \(\mu^{\tau'}_{y-\Lambda_{d,N}}\). That is, if \(x\) is on the boundary of the block, the boundary conditions coincide except at \(x\), and we are unlucky, we perform the update somehow.

5. Otherwise, we define \(\sigma(t)=\tau\cdot\eta\) and \(\sigma'(t)=\tau'\cdot\eta'\) with \((\eta,\eta')\) with law \(\mu^\tau_{y-\Lambda_{d,N}}\otimes\mu^{\tau'}_{y-\Lambda_{d,N}}\). That is, in all other cases, the two processes perform the block update independently.

We note that this construction is possible, since Lemma 20 and 48 give \[\begin{align} \frac{\mathrm d\mu_{(y-\Lambda_{d,N})\setminus(z-\Lambda_{d,n})}^{\tau^x}}{\mathrm d\mu_{(y-\Lambda_{d,N})\setminus(z-\Lambda_{d,n})}^{\tau}}&{}\geqslant\frac{1-N^{-a_d}}{1+N^{-a_d}}\cdot\frac{1-n^{-a_d}}{1+n^{-a_d}}\overset{N\geqslant n}\geqslant\left(\frac{1-n^{-a_d}}{1+n^{-a_d}}\right)^2\\ &{}\geqslant(1-n^{-a_d})^4\geqslant 1-4n^{-a_d}{=\mathbb{P}(\xi_{y,t}=1)}. \end{align}\] We next claim that this coupling is contracting for the natural graph metric on \(\Omega_{\mathbb{T}}\).

By the standard technique of path coupling (see Levin09?*Theorem 14.6, which applies similarly to the continuous time setting), Lemma 21 implies that, for any probability measure \(\nu\) on \(\Omega_{\mathbb{T}}\) and \(t\geqslant 0\) \[\label{eq:dTV} d_{\mathrm{TV}}\left(\nu P^{\mathbb{T}} _t,\mu_{\mathbb{T}} \right)\leqslant W_1\left(\nu P_t^{\mathbb{T}} ,\mu_{\mathbb{T}} \right)\leqslant e^{-tN^d/(3d^d)}|{\mathbb{T}} |,\tag{52}\] where \(P_t^{\mathbb{T}}\) denotes the semi-group of \(\mathcal{L}_{\mathbb{T}}\) and \(2W_1\) is the \(\ell_1\)-Wasserstein distance and \(d_{\mathrm{TV}}\) is the total variation distance.

We next seek to compare the invariant measure \(\mu_{\mathbb{T}}\) on the torus to the semi-group \(P^{(N)}_t\) of the block dynamics on \({\mathbb{Z}} ^d\), whose Dirichlet form is given by \[\label{eq:def:DN} \mathcal{D}^{(N)}(f)=\sum_{x\in{\mathbb{Z}} ^d}\mu\left(\mathop{\mathrm{Var}}_{x-\Lambda_{d,N}}(f)\right)\tag{53}\] and whose relaxation time we denote by \(T_{\mathrm{rel}}^{(N)}\) (recall 5 ). This follows from the classical fact that, in a finite-range model, information cannot travel too fast, as we recall next.

Thanks to the range of possible values of \(L\) in Lemma 22, we conclude that \(\mu_{\mathbb{T}} (f)\) has a limit \(\mu(f)\) (as the size \(L\) of \({\mathbb{T}}\) diverges) and \(P_t^{(N)} f\) converges exponentially fast to it in \(\ell^\infty\) at rate \(N^d/(4d^d)\). In particular, the infinite volume process is ergodic, there is a unique invariant measure and therefore a unique Gibbs measure (see Liggett05?*Theorem IV.2.15). Moreover, this exponential ergodicity implies (see the remark at the end of Martinelli99?*Section 3.5) \[\label{eq:trelN:upper} T_{\mathrm{rel}}^{(N)}\leqslant 4d^d/N^d.\tag{55}\]

Furthermore, for any local function \(f\colon\Omega\to{\mathbb{R}}\) we have \[\begin{align} \label{eq:trel:small:scales}\mathop{\mathrm{Var}}(f)&{}\overset{\eqref{eq:def:trel}}\leqslant T_{\mathrm{rel}}^{(N)}\mathcal{D}^{(N)}(f)\overset{\eqref{eq:def:DN}}=T_{\mathrm{rel}}^{(N)}\sum_{x\in{\mathbb{Z}} ^d}\mu\left(\mathop{\mathrm{Var}}_{x-\Lambda_{d,N}}(f)\right)\\ \nonumber&{}\overset{\eqref{eq:def:trel}}\leqslant T_{\mathrm{rel}}^{(N)}\sum_{x\in{\mathbb{Z}} ^d}\sup_{\tau\in\Omega_{{\mathbb{Z}} ^d\setminus(-\Lambda_{d,N})}}T_{\mathrm{rel}}^{-\Lambda_{d,N},\tau}\mu\left(\mathcal{D}_{x-\Lambda_{d,N}}(f)\right)\\ \nonumber&{}\overset{\eqref{eq:def:D}}=T_{\mathrm{rel}}^{(N)}\sup_{\tau}T_{\mathrm{rel}}^{-\Lambda_{d,N},\tau}\sum_{x\in{\mathbb{Z}} ^d}\mu\left(\sum_{y\in x+\Lambda_{d,N}}\mu_{x-\Lambda_{d,N}}(\mathop{\mathrm{Var}}_y(f))\right)\\ &{}\overset{\eqref{eq:def:D}}=T_{\mathrm{rel}}^{(N)}\sup_{\tau}T_{\mathrm{rel}}^{-\Lambda_{d,N},\tau}|\Lambda_{d,N}|\mathcal{D}(f). \end{align}\tag{56}\]

Using 5 , 56 , 55 and Lemma 19, we get \[T_{\mathrm{rel}}\leqslant\frac{4d^d}{N^d}(N+1)^de^{2(\beta+1)(N+4)^d}\leqslant e^{(\beta+1)m^{C'}}\leqslant Ce^{e^{C\beta}},\] recalling 49 and \(m=\lceil 1/(1-\tanh(\beta))\rceil\geqslant 2\) and taking suitably large \(C',C>0\) depending only on \(d\) (and \(a_d\)). ◻

Proof. Consider the word \(w=a x^{-2^n} a x^{2^n}y^{-2^n} a y^{2^n}\) mentioned above, which has size \(\mathcal{O}(2^n)\) and represents the identity in \(\Gamma\). Let \(\mathcal{K}\) be a van Kampen diagram for \(w_n\), and let \((\gamma_0,\dots,\gamma_\Delta)\) be a combinatorial null-homotopy: a sequence of loops in \(\mathcal{K}\), based at the start of \(w\), such that \(\gamma_0\) is the empty loop, \(\gamma_\Delta\) in the peripheral loop reading \(w\), and each \(\gamma_i\) differs from \(\gamma_{i-1}\) by enclosing a single extra cell \(C_i\). If \(u_i\) is the word read along \(\gamma_i\) from the basepoint to the beginning of the relator \(r_i\) around \(C_i\), we obtain a corresponding expression of \(w_n\) as a product of conjugates of relators \(r=a x a x^{-1} y a y^{-1}\) and \(s=[x,y]\), \[w_n=\prod_{i=1}^\Delta u_i r_i u_i^{-1},\quad r_i\in\{r^{\pm1},s^{\pm1}\}.\] Consider now a loop \(\gamma_i\); the word read along it also represents the identity in \(\Gamma\). Consider the associated lamp configuration: follow the \(x^{\pm1},y^{\pm1}\) letters of \(\gamma_i\), and flip the lamp at the current position when an \(a\) is read. This lamp configuration \(W_i\) is admissible, and the configurations \((W_0,\dots,W_\Delta)\) form a chain. The claim now follows from Theorem 4. ◻

Proof. By Corollary 1, there exists a nonempty admissible configuration \[X=\{x_1,x_2,\dots,x_m\}\] of at most \(n\) points such that any two distinct points have \(\rho\)-distance at least \(r\), where \(r\geqslant c'\ln(n-2)\geqslant 15+c\ln n\) for some positive constants \(c,c'\), as long as \(n\) is large enough. Up to repeatedly replacing \(X\) by \(X\sqcup(X+v)\) for some \(v\in\mathbb{Z}^2\) at \(\rho\)-distance at least \(r\) from \(X-X\), we may assume \(m\geqslant n/2\).

Since \(X\) is admissible, write it as the sum of at most \(h(n)\) large plaquettes. For every \(i=1,\dots,m\), let \(M_i\) be the set of those large plaquettes in the sum that have at least one vertex at \(\rho\)-distance \(<r/3\) from \(x_i\). If \(r\geqslant 3\), then the sets \(M_i\) are pairwise disjoint.

Let \(X_i\) be the sum modulo \(2\) of all large plaquettes from \(M_i\). All other points of \(X_i\) are at \(\rho\)-distance at least \(r/3\) from \(x_i\). Applying Lemma 7 to \(X_i\) and the point \(x_i\), we obtain \[|X_i|\geqslant\frac{3}{4}\left(\frac{3}{2}\right)^{r/3} \geqslant 4 n^{\eta}, \qquad \eta\mathrel{\vcenter{:}}=\frac{c}{3}\ln\left(\frac{3}{2}\right)>0.\] This implies \[|M_i|\geqslant 2 n^{\eta}.\] Summing over \(i=1,\dots,m\) and using the disjointness of the sets \(M_i\) gives \(h(n)\geqslant 2m\,n^\eta\geqslant n^{1+\eta}\), as claimed. ◻