Since \(w\le s/1000\) and \(w\le (n-s)/1000\), for opposite edges the bands lie within \(n/250\) of their edges. For adjacent edges a common point at distances \(r_1,r_2{\gt}0\) from the two edge lines would satisfy \(r_1{\lt}0.002\, r_2\) and \(r_2{\lt}0.002\, r_1\). On \(\{ -8{\lt}x{\lt}0\} \) one has \(0{\gt}d{\gt}-8w\ge -n/250\). The diameter bound follows from \(|d|\le 8w\le n/250\) in each closed band. The changed set of an elementary operation lies in the closed band of its changed interval, and the central region lies in \(S\).

Because both thresholds \(-7\) and \(-7/2\) lie in \(C\) intervals of both words, the two words agree on each interval.

With \(m=\min (s,n-s)\) at \(y\), one has \(w=m/1000\) and \(|d|\le m\), hence \(d_{\mathcal V}(y)\le m\). If \(|y-z|{\lt}m/5000\), the parallel and normal coordinates move by less than \(m/5000\), and \(w\) is \(10^{-3}\)-Lipschitz, so \(|\beta '(w(s_z)-w(s_y))|\le 8m/(5\cdot 10^{6})\). Then \(d_z{\lt}\beta w(s_y)+m/5000\le \beta ' w(s_z)-m/2000+m/5000+8m/(5\cdot 10^6)\), and symmetrically at \(\alpha '\).

With \(u=\min (y_1,n-y_1)\) and \(v=\min (y_2,n-y_2)\), the four conditions \(d\ge w\) give \(v\ge u/1000\) and \(u\ge v/1000\). The nearest corner is at distance \(\max (u,v)\le 1000\min (u,v)\), so a point within \(a_0\min (n,d_{\mathcal V}(y))\) of \(y\) is within \(\min (u,v)/5\) of \(y\) and lies in \((0,n)^2\).

The set \(\{ f_b\ne f_a\} \) lies in the closed band of the changed interval, which is closed. If \(|y-z|{\lt}a_0\min \{ n,d_{\mathcal V}(y)\} \), the conical band estimate puts \(z\) in the open band of the surrounding sector, where \(f_s\) equals \(P_\circ \).

A boundary point of \(Y\) is an endpoint of the edge, where the bound is immediate, or satisfies \(d=-7w\) or \(d=-\tfrac 72w\) with \(0{\lt}s{\lt}n\). If \(y\) lies outside the exterior band \(\{ -8{\lt}x{\lt}0\} \), then \(d_{\mathcal V}(y)\le d_{\mathcal V}(z)+|y-z|\) and \(d_{\mathcal V}(z)\le m_z=\min (s_z,n-s_z)\); a distance below \(a_0d_{\mathcal V}(y)\) is then below \(m_z/2000\), which keeps \(y\) in that band because \(-7m_z/1000\le d_z\le -\tfrac 72m_z/1000\) and \(w\) is \(10^{-3}\)-Lipschitz. If \(y\) lies in one of the closed auxiliary bands \(\{ -6\le x\le -4\} \) or \(\{ -3\le x\le -1\} \), the conical band estimate places \(z\) in the open bands \(\{ -\tfrac {13}2{\lt}x{\lt}-\tfrac 72\} \) or \(\{ -\tfrac 72{\lt}x{\lt}-\tfrac 12\} \), neither of which meets the two boundary curves.

On the band of \(e\), the bands of the completed edges are absent by the band disjointness. Where \(x{\lt}0\) the point lies in the exterior neighboring square; where \(0{\lt}x{\lt}1\) it lies in the open square and outside the central region; where \(1{\lt}x{\lt}2\) it lies in the central region, since for every other edge it lies in the open square and outside that edge’s band, so its normal ratio there is at least \(2\). The exchange is Lemma 45.1.4 on the band, and the identity off it. A point of the open square outside the central region lies in the band \(\{ 0{\lt}x\le 1\} \) of some edge, where the final word is \(B\); a point outside the closed square lies in no band or in the part \(x{\lt}0\) of a band, where the final word is \(C_e\).

Translation is a homeomorphism, so it commutes with closures and boundaries, and \(|(y-o)-(z-o)|=|y-z|\). The set of points at distance at least \(c\) from \(y\) is closed.

The guides of an edge construction are obtained from one guide of their sheet by replacing the band of the edge by a word, so they have the properties assumed in Theorems 45.1.6, 45.1.7 and 45.1.8: such a guide carries its word on the band, two such guides of one sheet agree off the band, and the starting main word is \(C_e\) on \(\{ -8{\lt}x{\lt}0\} \); the starting guide of the central birth is \(A\) on the open square. Lemma 45.1.10 identifies these guides with the guides reached by the schedule. The diameter bound is Lemma 45.1.2. The exchange changes the main guide from the starting guide to the guide with the main word, and the auxiliary guide to the starting main guide on \(Y\), so it changes only points of \(Y\) where the two sheets differ; these are not common \(C_e\). The closure of \(Y\) lies in the closed band \(\{ -7\le x\le -7/2\} \), of diameter at most \(n\) by Lemma 45.1.2, and Lemma 45.1.12 translates all estimates to \(S\).

Inside the open square the final guide is \(B\) by Lemma 45.1.10; outside the closed square it is the starting block guide, and there the block index differs from \(S\). For the level transition, \(\lfloor x/(2n)\rfloor =\lfloor \lfloor x/n\rfloor /2\rfloor \) and a block lies in the root square of \(2M\) blocks per side if and only if its parent lies in that of \(M\) blocks. The words use only \(A\), \(B\), \(C_e\), which are values of the starting guide or the final label.

In block coordinates a cell center still has half-odd integer coordinates, and so do \(s\) and \(d\) for every edge. Thus \(d\ne 0\) and \(d\ne w(s)\) because \(1000d\) is an integer while \(1000\, w(s)=\min (s,n-s)\) is a half-odd integer, so Lemmas 45.1.10 and 45.1.14 apply.

If \(f_1=f_2\) near \(p\), then \(f_1(p+\varepsilon v)=f_2(p+\varepsilon v)\) for all small \(\varepsilon {\gt}0\), so \(f_1'(p)=f_2'(p)\). Off the closure of the set where \(f_1\ne f_2\) the two labellings agree near every point. A constant labelling reads itself. All estimates of Theorem 45.1.13 are stated for closures, which can only shrink.

Along a ray \(\varepsilon \mapsto p+\varepsilon v\) the coordinates, the parallel and normal coordinates of an edge, and the band width \(w(s)=10^{-3}\min (s,n-s)\) agree for small \(\varepsilon {\gt}0\) with affine functions \(a+b\varepsilon \). Such a function has, for small \(\varepsilon {\gt}0\), a constant sign: that of \(a\) if \(a\ne 0\), and that of \(b\) otherwise. Hence every strict inequality between such functions, and every bound \(x{\lt}t\) on the normal ratio \(x=d/w(s)\), is eventually decided; the floor \(\lfloor a+b\varepsilon \rfloor \) is eventually \(\lfloor a\rfloor \) if \(b\ge 0\) and \(\lceil a\rceil -1\) if \(b{\lt}0\). The bands, the central region, the sup squares and the blocks are finite Boolean combinations of such conditions, and a guide is a finite choice among them. Two readings agree, since both are the eventual label.

In the edge coordinates of a square of side \(n\), the interface curve \(x=t\) of a band is \(1000\, d=t\min (s,n-s)\), a union of two segments on lines with normals \((\pm t,1000)\) or \((1000,\pm t)\), and \(w(s)=0\) only on the lines \(s=0\) and \(s=n\). The edges, the sides of the treated squares and the grid lines are lines with \(t=0\), and near every point only two grid lines in each direction can occur. A strict inequality between continuous functions is locally constant where the two sides differ; the bound \(d/w(s){\lt}t\) is locally constant where \(w(s)\ne 0\) and \(d\ne t\, w(s)\); the integer part of a continuous function is locally constant where the function is not an integer. The guides are finite Boolean combinations and choices among such conditions, and the thresholds of the bands and of the words of the construction lie in \(T\). A line not parallel to \(v\) meets the ray \(p+\varepsilon v\) in at most one point, so for generic \(v\) and small \(\varepsilon {\gt}0\) the point \(p+\varepsilon v\) avoids the walls, where the guide is locally constant; with the eventual label of Lemma 45.1.17 it lies in the open chamber of that label.

Every guide named in the statement is the block guide or a guide of the repainting of \(S\), so its sampled guide exists by Lemma 45.1.19. A sampled guide reads the guide of the schedule after \(v\), so Lemma 45.1.16 applies.

Homogenization only removes changed positions, only inside the treated squares, and only removes other-label positions. A point of the closure of the remaining changed region lies outside the open treated squares, so \(d_{\mathcal V}(y)\ge t\) and \(\min (n,d_{\mathcal V}(y))\ge t\), and Theorem 45.1.13 gives the bound.

Of three distinct labels at least one differs from the given label. With \(Q=\max \{ t,\min (n,d_{\mathcal V}(y))\} \ge t\), the floor gives \(|y-c|\ge a_0Q\) at the vertex \(c\), hence \(|y-x|\ge a_0Q-2\epsilon _0t\ge a_0Q-\tfrac {a_0}2t\ge \tfrac {a_0}2Q\).

With \(\delta =|x-c|\) one has \(Q_x\le Q_c+\delta \) and \(g(x)\ge g(c)-\delta \), so \(g(x)\ge aQ_x-(a+1)\delta \ge aQ_x-2\epsilon _0(a+1)t\ge aQ_x-\tfrac a2Q_x\). A true vertex of either sheet lies in the closure of the noncommon-\(C_e\) positions, so it has the floor of Lemma 45.1.21.

A preconnected set missing the boundary of \(Y\) is covered by the disjoint open sets \(\operatorname {int}Y\) and the complement of \(\overline Y\), so it lies in one of them; closed squares and segments are convex. By Lemma 45.1.23 every point of an outer hole square is at distance at least \(\tfrac {a_0}2t{\gt}0\) from \(\partial Y\). The segment from \(x\) to a point \(z\) on the other side meets \(\partial Y\) at some \(w\) with \(|x-w|+|w-z|=|x-z|\).

Closures at \(c\) depend only on a neighborhood of \(c\). In the first case a point outside \(\overline{\{ f\ne g\} }\) has a neighborhood where the guides agree, and a point of \(U\) has one where both take only two values. In the second, a point of \(U\) has only the incident label \(C\), and a point off \(\partial Y\) lies in the interior of \(Y\) or of its complement. In the third, a point of \(U\) has only the incident label \(P\), a point off \(\overline U\) has a neighborhood where homogenization does nothing, and homogenization adds at most the label \(P\) to the incident labels.

By the logarithmic floor of Lemma 45.1.21, the homogenized surrounding guide is \(P_\circ \) on the open neighborhood of radius \(a_0t\) of the remaining changed region. On that neighborhood both guides take only the values \(P_\circ \) and the inserted label (off the changed region they agree with the surrounding guide, and on it they carry the operation’s words outside the treated squares), so the first part of Lemma 45.1.26 applies. For the exchange, a point within \(a_0t\) of \(\partial Y\) that is not common \(C_e\) would contradict the floor, so the second part applies. A point within \(2\epsilon _0t{\lt}a_0t\) of a retained true vertex is closer to it than any point of the closed change.

Of three distinct incident labels at most one is the placeholder. An incident label is a value of the guide, and the block labels of a level are described by Lemma 45.1.14. The current main guide agrees with the starting guide outside the closed square and outside the outer band of \(e\), and the starting guide is \(C_e\) on the neighboring block across \(e\), which reaches outside that band.

For three compact sets without a common point, \(\max (|y_1-y_2|,|y_1-y_3|)\) attains a positive minimum on their product; take a third of the smallest of these minima over the finitely many triples. For the parameters, apply this in the product space, where points with the same parameter are at the distance of their second coordinates. For the guide, take \(F_c\) the closure of the region of \(c\) in \(W\) with the open inner holes removed; a common point of three of them would be a true vertex outside every inner hole.

Being outside an open square is the non-strict inequality \(r\le |y-h|\), which is closed in the pair \((r,y)\); with \(r\in [r_0,r_1]\) and \(y\in W\) the joint sets are compact. Three of them with distinct labels have no common point, since a common point \(y\) would be a true vertex with \(r_0\le r\le |y-h|{\lt}r_0\) for some \(h\); the parametric form of Lemma 45.1.29, minimized over the finitely many templates and pushed forward by the similarity (which multiplies all sup distances by \(s\)), gives \(\nu \).

Rounding each coordinate down to the net places every point within \(u\) of \(u\mathbb Z^2\), and the net coordinates within \(\rho +u\) of a coordinate of the center form an interval of at most \(2(\rho +u)/u+1\) integers.

If \(n\le t\) the ratio is \(\epsilon _0\); otherwise it is \(\epsilon _0t/n\), which lies between \(\epsilon _0/K_0\) and \(\epsilon _0\), while comparing \(\min (2n,t)\) with \(\min (n,t)\) in the two cases \(n\le t\) and \(t\le n\) gives the resizing bounds.

Near a point whose first coordinate is not a multiple of \(n\), the first block index is constant and the second takes at most two values, so at most two labels occur; similarly for the second coordinate. Off the closed block \(S\) the two guides agree near the point. A grid corner in the closed block is one of its corners, and a grid corner differing by at least \(2\) or by \(-1\) in a block index is at distance at least \(n\) in that coordinate.

Distinct grid corners differ by at least \(1\) in some block index. On \(\sigma \le n/2\) one has \(w=\sigma /1000\). On the curve \(|d|=|\alpha |\sigma /1000{\lt}\sigma \), so the distance from the endpoint is \(\sigma \). The two rim points differ only in \(d\), by \(|\alpha -\alpha '|t/1000\).

A normal word is constant just below every point and from the point on, so near a point it takes at most two values. Inside the open band of an edge a guide carrying a word therefore takes at most two labels near each point. On the curve \(x=-8\), away from the endpoints, the word is \(C_e\) and the guide beyond the band is the label \(C_e\) of the neighboring block. On the curve \(x=2\) the word of the main sheet is \(B\), and the curve lies in the open central region and off the closed bands of the other edges, so the guide beyond the band is \(B\) as well; the auxiliary sheet is \(C_e\) on both sides. Off the closed band nothing changes. The closure of the central region meets the boundary of the square only at its corners, so near any other point of that closure the guide takes only \(A\) and \(B\). The corners of the square are grid corners, a block guide takes at most two labels near every other point, and distinct grid corners are at distance at least \(n\) by Lemma 45.1.34.

A word is constant near every point other than its interfaces, and the interfaces of the main and auxiliary words are integers from \(-6\) to \(1\); the boundary of the central region lies on the curves \(x=1\). For a point on a grid line, the line is within \(t{\lt}n/2\) of the corner, so it passes through the corner, and the point is the midpoint of a side of the rim. For a point on a curve of an edge, its normal coordinate is at most \(6\cdot 10^{-3}\min (s,n-s)\) in absolute value, so the corner has normal coordinate \(0\) and parallel coordinate \(0\) or \(n\); the straight-ray chart of Lemma 45.1.34 then places the point at parallel distance \(t\) and normal coordinate \(kt/1000\). Distinct pattern points on one side differ by at least \(t/1000\) along it, and points on different sides differ by at least \((1-6/1000)t\) in one coordinate.

By Lemma 45.1.26 a true vertex of the homogenized guide is an old true vertex off the closed treated squares, a grid corner by Lemma 45.1.35, or a point of a treated rim with two incident labels, in the rim pattern by Lemma 45.1.36. Two rim points about one corner are separated by the pattern. Otherwise the two points belong to distinct grid corners, at distance at least \(n\), and each lies within \(t\) of its corner, so they are at distance at least \(n-2t{\gt}t/1000\). A point of the region of a label in a reading is a limit of points of that region in the guide, so a true vertex of a reading is a true vertex of the guide; readings exist by Lemma 45.1.17.

Scaling by \(1/n\) carries the bands, their normal ratios and the central region of the block of side \(n\) to those of the unit square, so every unmodified guide is an unmodified guide of the repainting of the unit square composed with the scaling. Relabelling commutes with replacing a band by a word and with the central birth, so near the corner the guide is the relabelling by the window labels of an unmodified guide of one reference repainting, whose labels are the nine blocks around \((0,0)\) and the final label. On the unit square the bands, the normal ratios, the central region and the block guide are conical about each corner within distance \(1/2\), by the straight-ray charts of Lemma 45.1.34; so are the unmodified guides, and the scale \(t/n{\lt}1/8\) can be replaced by \(1/32\). The reference repainting has finitely many unmodified guides, since a guide after completed edges depends only on which edges are completed. Choosing for each label-equality type a representative map of the finitely many slots expresses the guide near \(v\) as an injective relabelling of one of finitely many templates; since injective relabellings and similarities preserve true vertices, Lemma 45.1.30 applies. Near one corner of \(\mathcal M\) the other treated squares are at distance more than \(n-5t{\gt}3t\), so homogenizing on all of them agrees with homogenizing on its square alone within distance \(4t\) of the corner, which contains the working set and the holes.

In units of \(s\) about a grid corner, a block guide is the block guide of side one whose labels are those of a fixed square window of blocks, so it is an injective relabelling of one of finitely many templates (one for each label-equality type of the window), to which Lemma 45.1.30 and Lemma 45.1.32 apply for the radius ratios; when \(n{\lt}t\) the radius \(h_n=\epsilon _0n\) and \(h_{2n}=\epsilon _0\min (2n,t)\) lie between \(\epsilon _0n\) and \(2\epsilon _0n\). Since \(h_n\le h_{2n}\), a configuration with some holes resized has larger holes than the one with all radii \(h_n\).

A reading takes only values of the labelling. If a guide agrees on an open square about \(c\) with \(u\mapsto \sigma (T((u-c)/s))\) for a template \(T\), then every reading of the guide after \(v\) agrees there with \(u\mapsto \sigma (T'((u-c)/s))\) for the reading \(T'\) of \(T\) after \(v\), since \((u+\varepsilon v-c)/s=(u-c)/s+(\varepsilon /s)v\). The templates of the point treatment and of the block guides are eventually constant along rays, so they have readings after \(v\). They are also constant off walls on lines with normals in the finite set \(\mathcal N\). Let \(v\) and \(w\) lie strictly on the same side of each line through the origin with normal in \(\mathcal N\). For a point \(p\) and small \(\varepsilon {\gt}0\), the segment from \(p+\varepsilon v\) to \(p+\varepsilon w\) stays near \(p\) and avoids the walls that miss \(p\); a wall through \(p\) with normal \(N\) meets it only where \(N\cdot ((1-a)v+aw)=0\) for some \(a\in [0,1]\), which is impossible because \(N\cdot v\) and \(N\cdot w\) have the same sign. So the template is locally constant along the segment, hence constant on it, and its readings after \(v\) and after \(w\) agree. A template therefore has at most one reading for each choice of sides of the finitely many wall directions, and only finitely many readings after generic displacements, so the compactness argument of Lemma 45.1.30 applies to these finitely many readings of the finitely many templates.

A reading of a block guide carries the label of a block on the open interior of that block, so a grid corner lies in the closure of the label of each of its four blocks. Let three points of a footprint outside the holes carry three labels. Move them by the displacement, by less than \(\min (r-2\delta ,s-2\delta )/4\); the moved points are pairwise closer than \(s\), so their block indices differ by at most one in each coordinate. Three distinct labels need three distinct blocks among the four blocks about one grid corner, and two of them are diagonal to each other. That corner is a true vertex, and it lies within \(2\delta \) plus the displacement of a footprint point, hence within \(r\) and within \(s\) of it. So the corner is a hole center and the footprint point lies in its hole, a contradiction. For the resizings, \(s=2n\) and the smallest radius is \(h_n=\epsilon _0n\), so \(\nu \le \nu _1\) gives \(2\cdot 2\nu n\le \epsilon _0n/2{\lt}h_n\) and \(2\cdot 2\nu n\le n/2{\lt}2n\). A true vertex within \(2n\) of the working set lies within \(4n\) of the corner. Holes of radius \(h_{2n}\ge h_n\) only enlarge the excluded set.

The hole radius satisfies \(h_n\ge \epsilon _0n/\max (K_0,1)\) by Lemma 45.1.32, so \(\nu \le \nu _3\) gives \(2\nu n\le h_n/2{\lt}h_n\) and \(2\nu n\le n/2{\lt}n\), and Theorem 45.1.41 gives the two-owner condition with footprint radius \(\nu n\). The separation \(3u+4r{\lt}n\), the patch count and \(18\le b\) are those of Theorem 45.10.11. The source-bounded rewrite gives the same circuit with at most \(2b\) pair sources in each monomial.

A half-odd number is at distance at least \(1/2\) from every integer.

The scale \(j\) contributes \(4^{k-j}\) squares and \((2^{k-j}+1)^2\le 4\cdot 4^{k-j}\) junctions, and \(3\sum _{i{\lt}k+1}4^i+1=4^{k+1}\) by induction. Finally \(4^k=(2^k)^2{\lt}4L^2\).

The first two claims follow from the position of the address in its block and \(2^{j'}\le 2\cdot 2^j\). For adjacent blocks, the interval of a block or of its parent contains the block’s own interval, and the two blocks’ intervals touch, so the second claim applies with \(g=0\). For the count, \(r\mapsto r+1\) maps the meeting blocks injectively into \([\lfloor V/b\rfloor ,\lfloor U/b\rfloor +1]\).

In one coordinate, with \(b=2^{j'}\ge 2^{j-1}\) and \(g\le c\, 2^j\), the blocks of side \(b\) meeting \([2^jr-g,2^j(r+1)+g]\) number at most \(\lfloor U/b\rfloor +2-\lfloor V/b\rfloor \) by Lemma 45.1.46, and \(b\lfloor U/b\rfloor \le U\le V+2^j+2g{\lt}b(\lfloor V/b\rfloor +1)+b(4c+2)\) bounds this by \(4c+4\). A junction coordinate within distance \(g\) of the interval lies in such a block. There are at most two scales \(j'\in \{ j-1,j\} \), so the near squares and the near junctions number at most \(2(4c+4)^2\) each. Finally, the gates of the party are distributed over the at most \(4(4c+4)^2\) near repaintings and junction resizes, at most \(G\) to each.

A block label of the level is the placeholder, the new label of the block, or the old label of its parent, and the new labels do not occur at the start nor the old ones at the end of the level; injectivity of the party assignment identifies the party. Near a grid corner \((nu,nv)\), within distance \(n/2\), every point lies in one of the four blocks with indices \(u-1\) or \(u\) and \(v-1\) or \(v\), so every incident label is one of their labels.

A party of side \(2^j\) owning a block adjacent to a square of scale \(j\) has index within one of the square’s in each coordinate, so the closed intervals touch. For a square of scale \(j-1\), a block adjacent to it has a parent with index \(\lfloor q/2\rfloor \), and \(2\lfloor q/2\rfloor \le q\le 2\lfloor q/2\rfloor +1\) gives touching intervals again. A junction resize using the party \((j,r,s)\) has scale \(j\) and indices \(u,v\) with \(r\le u\le r+2\) and \(s\le v\le s+2\), so the corner is within \(2^j\) of the closed interval of the block, and there are at most nine such junctions. By the proof of Theorem 45.1.48 with \(c=0\), at most \(2\cdot 4^2=32\) repaintings use the party, so its gates are distributed over at most \(41\) events, at most \(G\) to each, and number at most \(64G\).

The schedule sorts the scheduled events by their position in the level order, so it contains each of them once. A bulk operation lists its homogenizations, one for each of its \(m\) marks and \(\sigma \) sheets, then the operation, then the removals, so it has \(2m\sigma +1\) changes: nine for the central birth and for the exchange, and five for each other bulk operation. An edge has one initialization, three auxiliary births, the exchange and four main steps, so \(1+15+9+20=45\) changes, and a large-scale repainting has \(9+4\cdot 45=189\); a direct repainting and a resize have one change. The only initializations are those of the edges, one for each, so an event has at most four. The schedule of changes lists the changes of each event in turn, and each event occurs once, so at most \(189\) changes belong to an event and the length is at most \(189\) times the number of squares and junctions, and the number of initializations at most four times that number. Finally Theorem 45.1.45 with \(M=189\) gives \(3\cdot 189\, (\# \text{squares}+\# \text{junctions})\le 80\cdot 189\, L^3\).

On the lens the band coordinate lies in \((-7,-7/2)\), where the starting main word and the word \(C\mid A\mid B\mid C\) both take the value \(C\); off the lens the auxiliary word \(C\mid B\mid A\mid C\mid A\mid B\mid C\) with interfaces \(-6,\dots ,-1\) agrees with that word. By Lemma 45.1.35 the auxiliary guide takes at most two labels near every point other than the endpoints of its edge, and such a point is not a true vertex. Translation is a homeomorphism, so it carries true vertices to true vertices and preserves their number. Each initialization contributes at most two holes, and by Theorem 45.1.53 there are at most four initializations for each square and junction. Finally Theorem 45.1.45 with \(M=8\) gives \(3\cdot 8\, (\# \text{squares}+\# \text{junctions})\le 640\, L^3\), so three times the number of frozen holes is at most \(640L^3\le 3\cdot 214\, L^3\), and the number of frozen holes is at most \(214L^3\).

A block of side \(2^j\) with index \(r{\lt}2^{k-j}\) ends at \(2^j(r+1)\le 2^j\cdot 2^{k-j}=2^k\). The parties at a square are its block party and, for a non-root square, its placeholder, since a square is determined by its scale and block indices. The count follows from Theorem 45.1.45. During the repainting of \(S\), the label of a square \(Q\) is held by the block party of \(Q\), and a square is recovered from its label, so distinct squares give distinct block parties; the placeholder label is held by the placeholder party of \(S\), which is not a block party. A block of the root square at level \(2^j\) has indices below \(2^{k-j}\), and its parent has scale \(j+1\le k\) and indices below \(2^{k-j-1}\).

By Lemma 45.1.14 every such value is the new label of the block or a block label of the level. The new label of a block of the root square is the label of a square of the hierarchy, and so is every block label of the level other than the placeholder, by Theorem 45.1.56.

Homogenizing, placing and reading after a displacement take values among the values of the guide and the new label. The map from labels to parties is injective on the placeholder and the labels of the squares of the hierarchy, by Theorem 45.1.56.

A party used by the repainting of a square \(S\) of scale \(j\) owns a block of side \(2^j\) adjacent to \(S\) or its parent, or is the placeholder of \(S\); by Lemma 45.1.46 its address is within \(3\cdot 2^{j+1}\) of the address of \(S\) in each coordinate, and its scale is \(j\) or \(j+1\). A party used by the resize at a junction of scale \(j\) owns one of the four blocks at the corner, so its address is within \(3\cdot 2^{j+1}\) of the address of a fixed block there. The triangle inequality gives \(12\cdot 2^j\).

Since \(na-n{\lt}y{\lt}nb+n\) implies \(a-1{\lt}y/n{\lt}b+1\) and hence \(a-1\le \lfloor y/n\rfloor \le b\), evaluating each coordinate with \(a=b=u\) near a corner and with \(a=r\), \(b=r+1\) near the closed block gives both claims.

An outer hole square of positive radius is a neighbourhood of its centre, so an incident label there, in particular a tag holder, is a label on the footprint. A point of the footprint of a resize lies in one of the four blocks at the corner, and a point of the footprint of a direct repainting lies in a block adjacent to the square or in the square itself, by Theorem 45.1.61. The party labelling such a block is identified by Theorem 45.1.50; at the end of a pass only the parties of the blocks themselves occur.

The hole radius at scale \(m\) is at most \(\epsilon _0m\), and the new radius of a resize is at most the old one. The set to be covered lies in the closed square of radius \(2\epsilon _0\, 2^j\) about the corner, or of radius \((1/2+2\epsilon _0)n\) about the centre of \(S\), and Lemma 45.1.31 gives a net of mesh \(u\) with the stated number of patches and with centres within \(u\) of the covered set. An outer patch square is then within \(3u\) of a point of the covered set, and every point of the covered set is within \(2\epsilon _0m\) of the corner or of the closed square \(S\). Since \(2\epsilon _0+3\nu {\lt}1\), the footprint lies within sup distance \(2^j\) of the corner, or \(n\) of the closed square \(S\).

By Theorem 45.1.62 every gate in which the party participates is one of an event that uses the party, and Theorem 45.1.51 bounds the number of such gates by \(64G\).

A point of the band \(\{ -8{\lt}x{\lt}2\} \) of an edge lies in the closed square when \(x\ge 0\), and otherwise within \(8w(s)\le n/250\) of the edge. The treated squares of radius \(t\le n/2\) are centred at corners of the square, and the central region lies in the open square. The labels \(A\) and \(C_e\) are values of the starting guide at the centre of the square and at distance \(n/2\) across the edge \(e\). Each guide of the schedule is obtained from the starting guide or from the uniform guide \(C_e\) by finitely many changes, on the central region or on a band, to labels among \(A\), \(B\), \(C_e\), and a change inside the neighbourhood of radius \(n/2\) to local labels preserves locality. The lens \(\{ -7{\lt}x{\lt}-7/2\} \) lies in the band, and on it each exchanged sheet takes the values of the other sheet, which are local labels.

The final label is the new party of the square. A value of the starting guide within sup distance \(2^{j'}\) of the closed square is the label of a block whose indices differ from \((r,s)\) by at most one in each coordinate, and such a label is used by the repainting by Theorem 45.1.62. A party of the patch data is a label of its old or new guide on its footprint, hence a local label.

Lemma 45.1.31 gives a net of mesh \(u\) over the set to be covered, with centres within \(u\) of it, so an outer patch square lies within \(3u\) of the covered set. For a point treatment the covered set lies within \((1+2\epsilon _0)t\) of \(c\), and \((1+2\epsilon _0+3\nu )t{\lt}2t\le n\). For a bulk step the covered set is the neighbourhood of radius \(3n/4\) of the square, which contains the changed set by Theorem 45.1.66 and the affected outer holes, and \(3n/4+3\nu n\le n\).

By Theorems 45.1.62 and 45.1.67 every gate in which the party participates is one of an event that uses the party, and Theorem 45.1.51 bounds the number of such gates by \(64G\).

For a block party this is Theorem 45.1.51, or Theorem 45.1.69 for the patch data. A placeholder party participates only in gates of one event, at most \(G\le 64G\). Along the schedule, Theorem 45.1.53 gives at most \(189\) changes for each event.

The bounds of Definition 45.1.1.1 are the four items of the proposition. Theorem 45.15.82 gives a protocol with these bounds from the adaptive patch constraint of Proposition 4.1, which holds by Theorem 45.11.8.

Here \(\nu _2=1/600000000\) and \(\nu _3=1/2400000\). Since \(\nu _2\le \nu _1\) and \(\nu _2\le 1/20000\), both bounds hold.

This is the explicit form of Theorem 45.15.82, whose hypothesis holds by Theorem 45.11.8. The schedule has at most \(5040L^3\) changes, so with the initial and final changes the protocol has at most \(5042L^3\) changes, and it has fewer than \(11L^2\) parties. Each frozen auxiliary frame has at most two holes, hence at most \(10080L^3\) holes in all, and each change has reference error at most \((2b+1)L^{-20}\). Each gate is a small-patch rewrite with at most \(GL^{k_K}\) monomials and coefficient sum at most \(GL^{k_K}\).

The changes are contractions, \(\lVert r_0\rVert =1\), and the circuit and reference vectors agree at the first stage, so the first item is Theorem 45.7.1.2 with \(C_{\rm ch}=C_N\) and \(C_{\rm step}=C_{\rm hole}=C_E\). The second is the address bound of item 3 applied to the two endpoints of a link. For the last, the participation of a party is the number of nonprivate gates of all changes in which it participates, and Theorem 45.1.51 bounds it.

As in the proof of Theorem 45.1.1.5, the hypotheses of Theorem 45.7.1.2 hold with \(C_{\rm ch}=C_N\) and \(C_{\rm step}=C_{\rm hole}=C_E\), and Theorem 45.7.1.3 gives both estimates.

A set containing two specified elements has cardinality at most two.

The cardinality of a finite union is at most the sum of the constituent cardinalities, so \(|A_S|\le \sum _{e\in S}|E_e|\le 2|S|\).

The union bound gives \(|\Gamma (A)|\le \sum _{p\in A}|G(p)|\le b|A|\).

The two finite-union bounds give \(|\Gamma (A_S)|\le b|A_S|\le 2b|S|\).

Since \(e\in S\), the party \(a_e\) belongs to \(A_S\); since \(a_e\in P_{o(e)}\), the gate \(o(e)\) belongs to \(\Gamma (A_S)\).

Any party in \(P_g\cap A\) would place \(g\) in \(\Gamma (A)\), a contradiction.

The off-diagonal ordered pairs map two-to-one onto unordered pairs, giving \(|U(P)|=n(n-1)/2=\binom n2\).

The map is injective. Every distinct unordered pair containing \(p\) has a unique other endpoint in \(P\setminus \{ p\} \).

Adding the cardinalities of the disjoint star and sample summands gives \(n-1+\binom n2\), which is monotone in \(n\).

The star contribution is at most the whole star size \(|P|-1\). The sample contribution is exactly \(|P|-1\).

A star label lies in \(P\setminus \{ r\} \), and a sample label has both endpoints in \(P\).

Star labels exclude the root; sample labels are off-diagonal.

The injection \(t\mapsto (g,t)\) preserves cardinality, including after filtering by party incidence.

The gate tag gives \(g\in G\), and gate-local endpoint locality gives \(V(\ell )\subseteq P_g\).

Membership in \(\mathcal L\) places the link label in \(T(P_g,r_g)\), where the gate-local count gives \(|V(\ell )|=2\).

For an incident link the original gate tag belongs to \(G\), and locality puts \(p\) in that gate’s participant set.

Each participating gate contributes at most \(2(b-1)\) links incident to \(p\). Taking their union gives \(|I(p)|\le \sum _{g\in G(p)}|\mathcal L_g(p)|\le 2b(b-1)\).

Distributing the product of the two finite sums yields the double sum.

The coefficient product is at most \(B^{2|\Gamma (A_S)|}\le B^{4b|S|}\), and the physical-entry product is at most \(d^{2|A_S|}\le d^{4|S|}\), so multiplying the two bounds and collecting the common exponent \(|S|\) gives \((B^{4b}d^4)^{|S|}\).

Raising each monomial bound to its nonnegative integer power and multiplying adds the exponents of \(L\).

At each incident star both labels are \(\kappa _g\).

If \(p=r_g\) this is the definition of \(\kappa _g\). Otherwise \((g,\mathrm{star},p)\) is a star edge, and consistency at its two endpoints gives \(\xi _p(g)=\eta _{(g,\mathrm{star},p)}=\xi _{r_g}(g)\).

A star edge is determined by consistency at its root, and a sample edge is determined by the definition of \(j_s\).

Either endpoint choice reads \(\eta _\ell \).

By the definition of the shared assignment, the sample edge of \(s\) reads \(j_s\).

Regrouping the gate product by the fibers of \(g\mapsto r_g\) gives the equality because every active gate has a unique root.

The identity matrix on each edge forces its two endpoint labels to coincide, and reindexing the remaining diagonal assignments by one label per edge makes the endpoint reader yield \(\eta _p\).

With every bond matrix equal to the identity, the network is the plain contraction of the local tensors (Corollary 45.6.9). The factorization of its flattening across \(S\) (Theorem 45.6.6) sums over the labels of the crossing edges, which gives (11). Matrix rank is bounded by the number of columns of the left factor, namely \(|K_S|\), which gives (12).

The input-fixed local tensor is \(A_{p,z}(\eta ,x_p)=A_p(\eta ;(x_p,z_p))\). Its identity-bond contraction is exactly \(\sigma (x,z)\). Apply Theorem 45.3.29 to these tensors on the same tagged star and sample links. The local sums and the coefficient at each chosen root stay inside their original tensors. No normalization or injectivity condition is required.

Expanding the product of the local sums in (10) via (9) makes the consistency indicators restrict the sum to globally consistent configurations. Reindexing by the bijection with \((\kappa ,j)\) and applying the shared-sample identity together with the root-coefficient product identity then gives the display.

Evaluating both sides at \((x,y)\), distributing the finite matrix sums and scalar multiplication, and applying the entrywise identity gives the operator equality.

The two cardinalities follow directly from the two cases in the definition of \(D_\ell \).

A star edge inherits the given bound at its active gate, and a sample edge has dimension \(k\).

Specializing the rectangular matrix identity to the complete ket/bra alphabet and the stated coefficient function gives the claim.

Every summand of the contraction in Definition 38.9.7.3 contains exactly one factor \(A_p\).

The product bijection \(\prod _e\vartheta _e\) changes variables in the finite contraction sum. By (18), each transformed local factor is the corresponding factor in (10) at the prescribed physical coordinates. Their products and hence their sums agree.

The endpoints of each oriented link give precisely its participating set. The links whose source or target is \(p\) therefore correspond bijectively to \(I(p)\), with every gate and kind label retained.

The distributed incidence bound gives \(|I(p)|\le 2b(b-1)\) for every party, so the degree comparison bounds the network degree by \(2b(b-1)\).

The inverse reads each carrying party:

Since \(a_{r_v}=v\), the identities \(\Psi \Phi (x)=x\) and \(\Phi \Psi (y)_{r_v}=y_{r_v}\) follow from the inverse equations for \(f_{r_v}\). At every other party, both coordinates lie in the same subsingleton alphabet, so \(\Phi \Psi (y)_p=y_p\) there as well.

Let \(w_i\) be an orthonormal basis of right singular vectors of \(M=AB^{\mathsf T}\), and let \(u_i\) be the normalized images \(Mw_i\) when \(Mw_i\ne 0\). The \(i\)th singular value of \(M\) is \(\langle u_i, A(B^{\mathsf T}w_i)\rangle =\langle A^{*}u_i, B^{\mathsf T}w_i\rangle \), so by the Cauchy–Schwarz inequality it is at most \(\lvert \langle A^{*}u_i, B^{\mathsf T}w_i\rangle \rvert \le \lVert A^{*}u_i\rVert \, \lVert B^{\mathsf T}w_i\rVert \). Summing over \(i\) and applying the Cauchy–Schwarz inequality gives \(\lVert M\rVert _1\le (\sum _i\lVert A^{*}u_i\rVert ^2)^{1/2}(\sum _i\lVert B^{\mathsf T}w_i\rVert ^2)^{1/2} \le \lVert A\rVert _2\lVert B\rVert _2\).

Let \(Q\) be the orthogonal projection onto the first \(\min (k,n)\) right singular vectors of \(M\), where \(n\) is the number of columns. Then \(\lVert M-MQ\rVert _2^2=\sum _{j{\gt}k}s_j^2\), where \(s_1\ge s_2\ge \cdots \ge 0\) are the singular values of \(M\). Since the singular values are nonincreasing, \((k+1)s_{k+1}\le \sum _j s_j\) and \(\sum _{j{\gt}k}s_j^2\le s_{k+1}\sum _j s_j\), so \((k+1)\sum _{j{\gt}k}s_j^2\le (\sum _j s_j)^2=\lVert M\rVert _1^2\).

Induct on the vertex subset by adding one vertex at a time. Contracting the edges between two disjoint vertex subsets amounts to multiplying their partial contractions, reshaped as matrices with the shared edges as the contracted index, so submultiplicativity \(\lVert AB\rVert _2\le \lVert A\rVert _2\lVert B\rVert _2\) preserves the norm bound. A single vertex has no self-loops and thus has norm \(\lVert A_v\rVert \le 1\), while the empty subset has norm \(1\).

By Theorem 45.6.5, the partial contractions \(A\) on \(T\) and \(B\) on \(V\setminus T\) satisfy \(\lVert A\rVert _2\le 1\) and \(\lVert B\rVert _2\le 1\). Grouping the edges between \(T\) and \(V\setminus T\) into a single column index writes the reshaping of \(Z\) as \(AB^{\mathsf T}\), so Lemma 45.6.2 gives \(\lVert AB^{\mathsf T}\rVert _1\le \lVert A\rVert _2\lVert B\rVert _2\le 1\).

For each \(v\in V\), applying Lemma 45.6.3 to the reshaping across \(\{ v\} \) and \(V\setminus \{ v\} \) yields an orthogonal projection \(Q_v\) of rank at most \(k\) on \(\mathbb C^{P_v}\) with \(\lVert Z-Q_v Z\rVert \le 1/\sqrt{k+1}\le 1/\sqrt{k}\), and \(Q_v Z=Z\) whenever \(|P_v|\le 1\). Because the projections \(Q_v\) act on distinct tensor factors, they commute and have operator norm at most \(1\), so telescoping over \(v\in G\) gives \(\lVert Z-Z_k\rVert \le |G|/\sqrt k\). Since \(\lVert Z_k\rVert \le \lVert Z\rVert \le 1\), every coefficient of \(Z_k\) in the orthonormal product basis has modulus at most \(1\).

Theorems 45.6.5 and 45.6.6 give \(\lVert Z\rVert \le 1\) and the nuclear-norm bound across every bipartition of \(V\). A vertex with no open legs has \(|P_v|=1\), so the set \(G\) of vertices with nonempty open-leg groups contains every \(v\) with \(|P_v|{\gt}1\), and Lemma 45.6.7 gives the truncation.

When every edge matrix is the identity and the graph has no self-loops, the network contraction coincides with the coordinate contraction, and the vertex norms agree, so the whole-group tensor bound applies directly.

The left side is the sum of the squared moduli of all matrix entries of \(E\), which is the squared Hilbert–Schmidt norm \(\lVert E\rVert _2^2\). The Hilbert–Schmidt norm is at most the trace norm.

Let \(S\) be the set of indices with \(a_z\ne 0\); it is nonempty and \(\sum _{z\in S}|a_z|^2=1\). If every \(z\in S\) had \(\lVert f_z\rVert ^2{\gt}\eta ^2|a_z|^2\), summing over \(S\) would give \(\eta ^2{\lt}\sum _{z\in S}\lVert f_z\rVert ^2\le \eta ^2\), a contradiction.

The reverse triangle inequality gives \(|\lVert w\rVert -1|\le \eta {\lt}1\), so \(w\ne 0\). Then \(\lVert w/\lVert w\rVert -w\rVert =|1-\lVert w\rVert |\le \eta \), and the triangle inequality through \(w\) gives the bound \(2\eta \). For the second statement put \(w=v/a\), so that \(w-\Omega =f/a\) has norm at most \(\eta \). Since \(v/\lVert v\rVert =(a/|a|)\, w/\lVert w\rVert \), the phase \(e^{i\theta }=a/|a|\) transfers the bound.

Setting \(E=\sigma -|\Omega \rangle \langle \Omega |\), \(f_z=E|z\rangle \), and \(a_z=\langle \Omega | z \rangle \), Theorem 45.7.1 gives \(\sum _z\lVert f_z\rVert ^2\le \eta ^2\), while \(\sum _z|a_z|^2=\lVert \Omega \rVert ^2=1\). Theorem 45.7.2 then selects \(z\) with \(a_z\ne 0\) and \(\lVert f_z\rVert \le \eta |a_z|\). The column satisfies \(\sigma |z\rangle =f_z+a_z\Omega \), and Theorem 45.7.3 completes the proof.

Applying the vector statement to \(\sigma \) and identifying the selected column with the fixed-input contraction coordinate by coordinate gives the result.

Applying the vector statement to \(\sigma \) selects the column; fixing inputs leaves every bond dimension unchanged, and the state of the fixed-input tensor is the selected column.