Circuit model and main result

An arithmetic circuit over a field \(K\) is a finite directed acyclic graph. Its leaves are variables or elements of \(K\). A sum gate computes a \(K\)-linear combination of its inputs, and a product gate computes their product. Fan-in and fan-out are arbitrary and finite. Gates may be shared, and a gate may occur repeatedly among another gate’s inputs; repeated occurrences at a product gate are counted with their multiplicities. Scalar coefficients on sum inputs are part of the circuit and do not require additional gates.

A \(\Sigma\Pi\Sigma\Pi\Sigma\) circuit has five computational layers, listed from output to leaves, with respective gate types \(+,\times,+,\times,+\) and a single output gate. Edges between computational gates join consecutive layers, and the bottom sums read leaves. Unary gates are allowed. In particular, no bound is placed on the number of variables in a bottom linear form.

The circuit is syntactically homogeneous if it has the following formal-degree assignment: variables have degree \(1\), constants have degree \(0\), product gates add their input degrees with multiplicity, and all inputs of a sum gate have the same degree, which is assigned to that gate. Empty sums and products, if present, compute \(0\) and \(1\) and have formal degree \(0\). Thus a zero polynomial at a gate still carries its assigned formal degree; cancellation does not reset that degree. All computations and equalities below concern formal polynomials.

We define size to be the number of vertices, including leaves. The number of computational gates excludes leaves, whereas wire size counts input occurrences. These quantities are not identified: our lower bound is on gates, and the circuit analysis also bounds the number of computational gates alone.

The model permits unrestricted bottom fan-in and support, constants, and shared subcircuits. Corollary 9 extends the \(n^{\sqrt n/400}\) lower bound to every field of characteristic zero, with the same absolute threshold. Proposition 10 gives an elementary block construction of size at most \(n^{\sqrt n+4}\) over every field for \(n\geq2\). It is homogeneous of depth four; inserting unary bottom sums makes it depth five, so the lower bound has the matching scale. Iterated matrix multiplication nevertheless has polynomial-size circuits when depth is unrestricted.

Historical context and previous bounds

Iterated matrix multiplication has long served as a test of the cost of restricting arithmetic depth. Its path expansion connects matrix products with reachability, while its polynomial-size unrestricted circuits make it a natural target for lower bounds on weaker circuit models. Nisan and Wigderson used dimensions of partial-derivative spaces to prove lower bounds for homogeneous depth-three circuits and for constant-depth set-multilinear circuits. They asked for an explicit homogeneous polynomial requiring superpolynomial size at constant depth, even at depth five (Nisan and Wigderson 1995, sec. 2.2 of the linked author journal manuscript).

Depth reduction gave this program a further motivation. Agrawal and Vinay reduced general arithmetic computation to depth four, and Koiran and Tavenas sharpened the size bounds (Agrawal and Vinay 2008; Koiran 2012; Tavenas 2015). For \(d=N^{O(1)}\), Tavenas’s theorem converts a circuit of size \(N^{O(1)}\) computing a homogeneous degree-\(d\) polynomial in \(N\) variables to a homogeneous depth-four circuit of size \(N^{O(\sqrt d)}\) (Tavenas 2015, Theorem 1 of the linked preprint). This explains the square-root scale in depth-four lower bounds and in the block construction for IMM used here.

The progress toward this scale involved several distinct restrictions. Fournier, Limaye, Malod, and Srinivasan proved IMM lower bounds with bounds on both product-layer fan-ins and, separately, for homogeneous multilinear formulas (Fournier et al. 2015, Theorems 16 and 29 of the cited author version). Kayal, Limaye, Saha, and Srinivasan removed the bottom-fan-in restriction for homogeneous depth-four formulas, obtaining an exponential lower bound over characteristic zero for a Nisan–Wigderson design family (Kayal et al. 2014, Theorem 1). Kumar and Saraf proved a \(d^{\Omega(\sqrt d)}\) lower bound for homogeneous depth-four circuits computing \(\operatorname{IMM}_{d^5,d}\), over every field (Kumar and Saraf 2017, Theorem 1.2 and Section 8.2 of the cited preprint). In another direction, Kayal, Saha, and Tavenas obtained \(w^{\Omega(\sqrt d)}\) for syntactically multilinear depth-four circuits computing \(\operatorname{IMM}_{w,d}\), without homogeneity, in the range \(d\geq\log^2 w\), over every field (Kayal et al. 2018, Theorem 1.4 and the following comparison).

At depth five, Bera and Chakrabarti proved a lower bound with a restriction on bottom support. Their Theorem 1.1 states that, for every fixed \(0\leq\mu<1/2\), there is an integer \(q=q(\mu)>0\) such that homogeneous \(\Sigma\Pi\Sigma\Pi\Sigma\) circuits computing \(\operatorname{IMM}_{d^q,d}\), with \(N=d^{2q+1}\) ambient variables and bottom fan-in at most \(N^\mu\), require \(N^{\Omega_\mu(\sqrt d)}\) gates over every field (Bera and Chakrabarti 2015, Theorem 1.1). Their precise Theorem 4.2 proves the lower bound for a restricted IMM polynomial, using the number of distinct variables feeding each bottom linear gate as its support parameter (Bera and Chakrabarti 2015, Theorem 4.2). The Kumar–Saraf and Bera–Chakrabarti bounds use different width–degree regimes from \(w=d=n\), and the latter restricts the bottom linear forms.

For a different hard family, Kumar and Saptharishi proved, over each fixed finite field \(\mathbb F_q\), \(\exp(\Omega_q(\sqrt d))\) lower bounds for homogeneous depth-five circuits without a bottom-support restriction (Kumar and Saptharishi 2017, Theorem 1). Their family is based on Nisan–Wigderson designs and lies in \(\mathrm{VNP}\). Armand, Behera, and Tavenas have since extended this finite-field approach to depth-five circuits whose top-product fan-in is bounded by a fixed polynomial in the degree \(d\), without homogeneity (Armand et al. 2026, Corollary 1.3). These finite-field theorems concern NW polynomials rather than IMM; both the field hypothesis and the exponential rate differ from those in Theorem 1.

Superpolynomial lower bounds for unrestricted-bottom depth-five circuits over characteristic zero were already established by the constant-depth results of Limaye, Srinivasan, and Tavenas (Limaye et al. 2021, 2025). We use the theorem numbering of their ECCC revision 1. Their product-depth convention counts multiplication gates on a path, so our five-layer model has product-depth two. In the low-degree regime \(d\leq(\log w)/100\), their Corollary 3 gives \(w^{\Omega(\sqrt d)}\) for homogeneous product-depth-two circuits over every field (Limaye et al. 2021, Corollary 3). Their general-circuit results also imply superpolynomial lower bounds for \(\operatorname{IMM}_{n,n}\) over \(\mathbb C\) (Limaye et al. 2021, Corollary 4 and the following discussion). Bhargav, Dutta, and Saxena improved the constant-depth exponents in the low-degree regime (Bhargav et al. 2022). Forbes subsequently established low-depth IMM lower bounds over arbitrary fields in the regime \(d=o(\log w)\) (Forbes 2024, Theorem 10).

Amireddy, Garg, Kayal, Saha, and Thankey gave a direct shifted-partials approach. For homogeneous product-depth-two formulas they obtain \(2^{-O(d)}w^{\Omega(\sqrt d)}\) when \(w=\omega(d)\), over every field (Amireddy et al. 2023, Theorem 24). The degree-dependent loss and the hypothesis \(w=\omega(d)\) prevent direct substitution of \(w=d=n\). The comparison addressed here is quantitative: we obtain the \(\sqrt n\) exponent in the balanced regime \(w=d=n\) for homogeneous five-layer circuits with unrestricted bottom linear forms.

Proof overview

The proof uses a derivative-based linear-algebraic measure. Dimensions of partial-derivative spaces were used by Nisan and Wigderson (Nisan and Wigderson 1995); shifted partial derivatives were developed in work of Kayal (Kayal 2012) and Gupta, Kamath, Kayal, and Saptharishi (Gupta et al. 2014). We define the operator needed here directly and prove its estimates.

Partition the matrix layers into two groups containing \(k\) and \(m\) layers, where \(k+m=n\) and \(m-k\) is of order \(\sqrt n\). Let \(V\) and \(U\) be the corresponding variable sets. For a homogeneous polynomial \(g\) of degree \(n\), let \(g_{[k,m]}\) be the sum of its monomials having degree \(k\) in \(V\) and degree \(m\) in \(U\). Replace its \(V\)-variables by partial derivatives and its \(U\)-variables by multiplication operators. On polynomials of fixed bidegree \((a,b)\) this gives a linear map \[F_g=g_{[k,m]}(\partial_V,U)\] into polynomials of bidegree \((a-k,b+m)\). We choose \(a,b\) of order \(n^{5/2}\), write \(D\) for the dimension of the source, and use \(R(g)=\mathop{\mathrm{rank}}F_g\) as the complexity measure. Differentiation in \(V\) commutes with multiplication in \(U\); the full substitution therefore respects products, while the finite map is linear in \(g\) and its rank is subadditive. Section 2 gives the definitions and parameters.

We first bound the rank of a circuit in Section 3. For a product of homogeneous factors, resolve each factor into its possible \(V\)-degrees. Apply first those factors whose \(V\)-degree exceeds their proportional share \(ke/n\) for a factor of degree \(e\). Their composition passes through a smaller intermediate polynomial space, which bounds its rank. The distance of each proportional share from the integers controls the sum over all such decompositions. These are the same integer-degree discrepancies that underlie the residue method of Amireddy, Garg, Kayal, Saha, and Thankey (Amireddy et al. 2022, Definition 2.1 and Lemma 3.1); here they control intermediate homogeneous dimensions. If all factor degrees are small, these distances give the required saving. If some factor has large degree, expand just one such factor into its bottom products of linear forms. This costs at most one additional factor of the circuit size. Proposition 3 gives, for a size-\(S\) circuit, \[R(g)\leq 2S^2D\exp(C\sqrt n)\,n^{-\sqrt n/100}\] with an absolute constant \(C\).

The opposite estimate uses the paths in matrix multiplication. Section 4 arranges the two groups of layers in a balanced order, with no adjacent \(V\)-layers. Declare the monomials \(z^M/\sqrt{M!}\) orthonormal, where \(M\) is an exponent vector and \(M!\) is the product of its coordinate factorials. In these bases, differentiation and multiplication have coefficients given by square roots of exponents and their successors. For \(g=\operatorname{IMM}_{n,n}\), the first two trace moments of \(F_g^*F_g\) become weighted counts of paths and quadruples of paths. Exact factorial moments for uniform weak compositions compare these weights with independent geometric random variables. We verify the coefficient signs needed for that comparison.

At each layer, a contributing quadruple has one of two pairing patterns. A change of pattern forces four vertex labels to agree and reduces the number of choices by a factor of \(n\). Section 5 sums the resulting weights, treating isolated corrections and the two endpoints explicitly. The balanced order controls the weight accumulated along each run of one pattern. The trace inequality \[\mathop{\mathrm{rank}}H\geq\frac{(\mathop{\mathrm{tr}}H)^2}{\mathop{\mathrm{tr}}(H^2)} \qquad(H\ne0\text{ positive semidefinite})\] then yields \(R(\operatorname{IMM}_{n,n})\geq D\exp(-C'\sqrt n)\), as stated in Proposition 6. Section 6 compares the two rank estimates and proves the field extension and matching upper bound.

The operator and its homogeneous spaces

Let \(K\) be a field, and let \(V,U\) be disjoint finite sets of variables, of cardinalities \(v,u\ge1\). For a variable set \(E\) and an integer \(t\ge0\), write \(\mathcal H_E(t)=K[E]_t\) for the vector space of homogeneous polynomials of degree \(t\). Its dimension is \[h(|E|,t),\qquad h(r,t)=\binom{r+t-1}{t}.\] For \(Q\in K[V,U]\), let \[T_Q=Q(\partial_V,U)\] be the operator on \(K[V,U]\) obtained by replacing each variable in \(V\) by its formal partial derivative and each variable in \(U\) by multiplication by that variable. These operators commute because the two variable sets are disjoint. Thus \(T_{Q_1Q_2}=T_{Q_1}T_{Q_2}\). This identity holds over every field.

Fix integers \(k,m\ge0\), \(a\ge k\), and \(b\ge0\). If \(g\) is homogeneous of degree \(k+m\), denote its component of \(V\)-degree \(k\) and \(U\)-degree \(m\) by \(g_{[k,m]}\). Define the finite-dimensional map \[ F_g=g_{[k,m]}(\partial_V,U): \mathcal H_V(a)\otimes\mathcal H_U(b) \longrightarrow \mathcal H_V(a-k)\otimes\mathcal H_U(b+m), \qquad R(g)=\mathop{\mathrm{rank}}F_g. \tag{2}\] The source dimension is \(D=h(v,a)h(u,b)\). Projection to a bidegree and operator substitution are both linear, so \[R(g_1+g_2)\le R(g_1)+R(g_2),\qquad R(cg)=R(g)\quad(c\in K\setminus\{0\}).\] Also \(R(0)=0\). The multiplicative identity for \(T_Q\) does not assert multiplicativity of \(g\mapsto F_g\): the latter includes a fixed bidegree projection. We will first decompose products into their bidegree components and then use multiplicativity of \(T_Q\) on each contribution.

Choosing the degrees

We now choose the spaces in (2) for degree-\(n\) polynomials on the \(n\) matrix layers. Throughout the proof \(n\) is sufficiently large, and all implicit constants and thresholds are absolute. Let \(s\) be the largest integer at most \(\sqrt n\) having the same parity as \(n\), and put \[ \begin{gathered} k=\frac{n-s}{2},\qquad m=\frac{n+s}{2},\qquad \rho=\frac{k}{m},\qquad \lambda=\frac{k}{n} =\frac{\rho}{1+\rho},\\ v=kn^2,\qquad u=mn^2,\qquad a=\left\lceil\frac{v}{\sqrt n-1}\right\rceil, \qquad \alpha=\frac{a}{a+v},\\ b=\left\lceil\frac{u\alpha^\rho}{1-\alpha^\rho}\right\rceil, \qquad \beta=\frac{b}{b+u},\qquad q=\alpha^{(1+\rho)/2},\qquad D=h(v,a)h(u,b). \end{gathered} \tag{3}\] For now assign any \(k\) full matrix layers to \(V\) and the other \(m\) layers to \(U\). Each layer retains all its \(n^2\) variables, including variables absent from the endpoint entry of the matrix product. Section 4 will specify their order when bounding the rank of \(\operatorname{IMM}_{n,n}\) from below.

The small excess \(m-k=s\) makes the slope \(\lambda\) slightly less than \(1/2\). For small positive even factor degrees \(e\), this moves \(\lambda e\) away from the integers; Section 3 quantifies the resulting rank saving. The definitions of \(a,b\) balance the dimension decrease caused by differentiation against the dimension increase caused by multiplication. Without the ceiling in the definition of \(b\), we would have \(\beta=\alpha^\rho\) and \(\alpha^k\beta^{-m}=1\). We record the rounding estimates explicitly, as their errors must stay small after many factors are combined.

The estimate \(q\le n^{-2/5}\) will suffice for the main power savings. The sharper \(q=O(n^{-1/2})\) will be essential when summing the smaller errors contributed by even factor degrees.

Products and intermediate dimensions

For a positive integer \(e\), define \[H_e=\sum_{i=0}^{e}q^{|i-\lambda e|}.\] These quantities account for all choices of bidegree in a product.

The quantities \(H_e\) use the same integer-degree discrepancies as the residue method of Amireddy, Garg, Kayal, Saha, and Thankey (Amireddy et al. 2022, Definition 2.1 and Lemma 3.1). In the present argument they control the dimensions of the intermediate homogeneous spaces through which the differentiation–multiplication operator factors.

The cost of integer degrees

The product estimate is effective because \(\lambda e\) is usually separated from the integers. Small even degrees require particular care: their separation can tend to zero, so a constant loss for each factor would be too large. We bound their combined error instead.

Put \[d_e=\mathop{\mathrm{dist}}(\lambda e,\mathbb Z),\qquad t_0=\frac{n}{4s}.\]

These estimates control a product of factors below \(t_0\) regardless of their coefficients. A factor of degree at least \(t_0\) will instead supply many linear factors through its bottom-layer expansion.

From gates to products

Occupation moments

A uniformly chosen basis vector of \(\mathcal H_V(a)\otimes\mathcal H_U(b)\) has two independent exponent vectors: one is uniform among weak compositions of \(a\) into \(v\) parts, and the other among weak compositions of \(b\) into \(u\) parts. We compare their moments with those of independent geometric variables. For an integer \(d\ge0\), write \[(z)_d=z(z-1)\cdots(z-d+1),\qquad r^{\overline d}=r(r+1)\cdots(r+d-1),\] with both empty products equal to one.

The comparison is termwise and does not assert independence of the coordinates of \(M\). We apply it separately in the two groups. By Lemma 2, total orders at most \(2n\) satisfy the lower-bound hypothesis, and their combined logarithmic loss is \[ O\left(\frac{n^2}{a}+\frac{n^2}{v} +\frac{n^2}{b}+\frac{n^2}{u}\right) =O(n^{-1/2}). \tag{18}\]

The first trace

In the chosen orthonormal bases, differentiation and multiplication act by \[\partial_i\frac{z^M}{\sqrt{M!}} =\sqrt{M_i}\frac{z^{M-\mathbf e_i}}{\sqrt{(M-\mathbf e_i)!}}, \qquad z_i\frac{z^M}{\sqrt{M!}} =\sqrt{M_i+1}\frac{z^{M+\mathbf e_i}}{\sqrt{(M+\mathbf e_i)!}}.\] The derivative is zero when \(M_i=0\); its displayed expression is used only when \(M_i\ge1\). Here \(\mathbf e_i\) is the coordinate unit vector. In particular, repeated differentiation of order \(d\) has coefficient \(\sqrt{(M_i)_d}\), with no additional factorial divisor.

Index a domain basis vector by the combined exponent vector \(M\) on \(V\cup U\), with totals \(a\) and \(b\) in the two groups. The summand of \(F_f\) corresponding to a path \(P\) shifts this vector by \[\epsilon_P =-\sum_{t:\,V}\mathbf e_{E_t(P)} +\sum_{t:\,U}\mathbf e_{E_t(P)}\] with coefficient \[ c_P(M) =\left( \prod_{t:\,V}M_{E_t(P)} \prod_{t:\,U}(M_{E_t(P)}+1) \right)^{1/2}. \tag{19}\] A shift requiring a negative occupation contributes zero. We extend the coefficient notation by zero to invalid input indices as well. Different layers have disjoint coordinates, so a path never repeats a coordinate. Moreover, the shifts \(\epsilon_P\) are distinct: a shift specifies the coordinate in every layer and hence every vertex of \(P\).

Consequently different paths from the same input reach different output indices. Summing the squared entries of \(F_f\) gives the exact identity \[T=D\sum_P\mathbb E\left[ \prod_{t:\,V}M_{E_t(P)} \prod_{t:\,U}(M_{E_t(P)}+1) \right],\] where the expectation is over the uniform domain indices. Every polynomial inside this expectation has nonnegative falling-factorial coefficients. Under independent geometric occupations of means \(A\) and \(B\), its expectation is \(\mu\). Lemma 7 and (18) therefore imply \[ T\ge Dn^L\mu\exp(-O(n^{-1/2}))>0. \tag{20}\] The inactive endpoint coordinates are included in the uniform compositions and in \(v,u\) throughout; they introduce no additional factor into this calculation.

Four paths in the second trace

The matrix entries of \(F_f\) in these bases are real and nonnegative. An entry of \(F_f^*F_f\) indexed by \(M,M'\) is the sum of \(c_P(M)c_Q(M')\) over pairs of paths satisfying \(M+\epsilon_P=M'+\epsilon_Q\). Squaring its entries and summing yields \[ \begin{split} T_2 &=D\,\mathbb E_M \sum_{\substack{P,Q,R,S:\ \epsilon_P-\epsilon_Q=\epsilon_R-\epsilon_S}} c_P(M)c_Q(M')c_R(M)c_S(M'),\\[-2pt] &\hspace{34mm} M'=M+\epsilon_P-\epsilon_Q. \end{split} \tag{21}\] The zero convention handles invalid indices. There is no additional sum over \(M'\), because \(M,P,Q\) determine it.

The condition on four paths holds separately in each layer. Denoting their four coordinates in that layer by \(p,q,r,s\), respectively, it is \(\mathbf e_p-\mathbf e_q=\mathbf e_r-\mathbf e_s\). If this difference is zero, then \(p=q\) and \(r=s\). Otherwise its positive and negative coordinates force \(p=r\) and \(q=s\), with \(p\ne q\). Thus there are exactly two types: \[\begin{array}{c|l} \mathcal N & p=q=i,\quad r=s=j,\\ \mathcal D & p=r=i,\quad q=s=j,\quad i\ne j. \end{array}\] The all-equal case belongs to \(\mathcal N\). For each compatible quadruple, the four-coefficient product in (21) is a product over layers of the following polynomials: \[ \begin{array}{c|cc} &\mathcal N&\mathcal D\\ \hline V&M_iM_j&M_i(M_j+1)\\ U&(M_i+1)(M_j+1)&(M_i+1)M_j. \end{array} \tag{22}\] Indeed, the shift from \(M\) to \(M'\) is zero in type \(\mathcal N\). In a \(V\) layer of type \(\mathcal D\) it is \(-\mathbf e_i+\mathbf e_j\), so the two coefficients at \(M\) contribute \(M_i\) and the two at \(M'\) contribute \(M_j+1\). In a \(U\) layer of type \(\mathcal D\) the shift is \(\mathbf e_i-\mathbf e_j\), giving \((M_i+1)M_j\) instead.

These polynomial formulas also account for invalid indices. In type \(\mathcal D\), a negative coordinate of \(M'\) requires \(M_i=0\) in a \(V\) layer or \(M_j=0\) in a \(U\) layer, and the corresponding table entry vanishes. In type \(\mathcal N\), an unavailable derivative makes \(M_iM_j\) zero. Since different layers use distinct coordinates, these exhaust the possible failures. Thus the product in (22) equals the zero-extended contribution.

When \(i=j\) in type \(\mathcal N\), the required expansions are \[z^2=(z)_2+(z)_1, \qquad (z+1)^2=(z)_2+3(z)_1+1.\] All other table entries are products of \((z)_1\) and \((z)_1+1\) on distinct coordinates. Hence every product of local entries has nonnegative falling-factorial coefficients, with order at most \(2k\) in \(V\) and \(2m\) in \(U\). Lemma 7 bounds its expectation by the expectation for independent geometric occupations.

For a geometric variable \(Z\) of mean \(G\), \(\mathbb EZ^2=2G^2+G\) and \(\mathbb E(Z+1)^2=2G^2+3G+1\). Dividing the geometric expectations in each \(V\) layer by \(A^2\) and in each \(U\) layer by \((1+B)^2\), we obtain \[ \begin{array}{c|cc} &\mathcal N&\mathcal D\\ \hline V&1+\alpha^{-1}\mathbf1_{\{i=j\}}&\alpha^{-1}\\ U&1+\beta\mathbf1_{\{i=j\}}&\beta. \end{array} \tag{23}\] Here \((A+1)/A=\alpha^{-1}\) and \(B/(B+1)=\beta\). For example, the repeated-coordinate \(V\) entry is \((2A^2+A)/A^2=1+\alpha^{-1}\), so the repeated factorial contribution has been retained. The product of the normalizing factors over all layers is \(\mu^2\).

A sum over pairing types

Assign to a compatible quadruple its type word \(\tau\in\{\mathcal N,\mathcal D\}^n\). For each such word, enlarge its class of quadruples by dropping the inequalities \(i\ne j\) at all \(\mathcal D\) layers. Keep their weights equal to \(\alpha^{-1}\) and \(\beta\) as in (23). These are assigned weights on the newly admitted tuples, not their geometric occupation moments. Every original tuple retains its weight, and every new weight is nonnegative, so this enlargement gives an upper bound.

Equality of matrix-entry coordinates equates the path labels at both ends of that layer. The relaxed equalities can therefore be counted independently at every internal vertex. A layer of type \(\mathcal N\) pairs the paths as \(\{P,Q\},\{R,S\}\), while a layer of type \(\mathcal D\) pairs them as \(\{P,R\},\{Q,S\}\). At a vertex between layers of the same type, there are two free labels in \([n]\). At a vertex between different types the two pairings together identify all four labels, leaving one free label. These give \(n^2\) and \(n\) choices, respectively, as illustrated in Figure 1. The two external vertex labels are fixed to \(1\). Every independent choice at the internal vertices gives four paths, because all matrix entries are available, and every relaxed quadruple arises uniquely this way. The set of assignments is therefore a Cartesian product over internal vertices. If \[w(\tau)=\#\{t\in\{1,\ldots,n-1\}:\tau_t\ne\tau_{t+1}\},\] the number of assignments is exactly \(n^{2L-w(\tau)}\).

For a layer \(t\) of type \(\mathcal N\), let \(h_t\) be the number of its end vertices that are internal and lie between two layers of type \(\mathcal N\). At each of these vertices the two free labels are independent and uniform in \([n]\), so they agree with probability \(1/n\). At an external vertex or an interface between different types the labels already agree. Consequently the two coordinates \(i,j\) of this \(\mathcal N\) layer agree with probability \(n^{-h_t}\).

The end-vertex sets of different \(V\) layers are disjoint, because no two \(V\) layers are adjacent in (12). Under the uniform distribution on the Cartesian product of relaxed vertex assignments, the equality events just described are therefore independent for the \(\mathcal N\) layers in \(V\). Their average weight is \[\prod_{t:\,\tau_t=\mathcal N,\ t\text{ in }V} (1+\alpha^{-1}n^{-h_t}).\] For each \(\mathcal N\) layer in \(U\) we instead bound its weight pointwise by \(1+\beta\), so no independence assertion for these layers is needed.

Write \(d_V(\tau)\) and \(d_U(\tau)\) for the numbers of \(\mathcal D\) layers in \(V\) and \(U\), respectively, and put \(N_V(\tau)=\{t:t\text{ is in }V,\ \tau_t=\mathcal N\}\). Combining the occupation comparison, the relaxed assignment count, and the preceding weight estimates proves \[ \frac{T_2}{Dn^{2L}\mu^2} \le (1+\beta)^m \sum_{\tau\in\{\mathcal N,\mathcal D\}^n} n^{-w(\tau)}\alpha^{-d_V(\tau)}\beta^{d_U(\tau)} \prod_{t\in N_V(\tau)} (1+\alpha^{-1}n^{-h_t}). \tag{24}\] Since \(\beta\le2/\sqrt n\), the factor \((1+\beta)^m\) is \(\exp(O(\sqrt n))\). It remains to prove the same bound for the word sum in (24). Lemma 8 establishes this using the spacing of the \(V\) layers and the balanced schedule.