Strong cocycle triviality for ℤ^{2} subshifts

Oliver Jenkinson

UPR 9016 CNRS, Institut de Mathématiques de Luminy, 163 avenue de Luminy, case 907, 13288 Marseille, cedex 9, France. email : omj@iml.univ-mrs.fr

Abstract. We consider cocycles defined on two-dimensional symbolic subshifts, and develop a new approach to proving that every cocycle is trivial. Introducing the notion of semi-safe subshifts, we prove that every locally constant cocycle with values in a locally (residually finite) group is trivial, and that the corresponding transfer function is itself locally constant.

Keywords: symbolic dynamics, two-dimensional subshift, cocycle, tilings

Section 1. Introduction.

There are many striking differences between higher-dimensional subshifts and the more familiar one-dimensional subshifts. In this paper we will consider two-dimensional subshifts, that is, a collection of decorations of the integer lattice ℤ^{2} which is invariant under both horizontal and vertical translation, and is topologically closed. Each such subshift can be identified with a set of tilings of the plane, where our tile set consists of finitely many square blocks of unit size, and there are various restrictions on the allowed adjacencies. If these restrictions are given by forbidding a finite number of finite size configurations, then the tiling is said to be of finite type.

An early indication of the difficulties faced in two dimensions goes back to the work of Wang [29] and Berger [1], who considered a particular class of finite type tilings (now called Wang tiles). Wang conjectured that there existed a finite time algorithm which, for any given tile set, would determine whether it was possible to tile the whole plane. His proposed algorithm was based on a further conjecture, namely that if a tile set can tile the whole plane, then it can do so periodically. Berger showed that, in contrast to the one-dimensional case, this problem is in general undecidable. Durand [5] recently proved, however, that provided a tile set can tile the whole plane, then it can do so quasiperiodically. See Chapter 11 of [7] for more details on these problems.

Several fundamental problems regarding periodicity properties remain unsolved, in particular the relation with the complexity of the subshift (see [2], [4], [6], [23], [24], [28]).

Recent work has focused on certain remarkable properties of cocycles. For twodimensional subshifts, a cocycle is given by a pair of functions (f, g) (taking values in some group G) satisfying the cocycle equation g(x)f(τx) = g(σx)f(x) for every x in the subshift, where σ, τ denote horizontal and vertical translation respectively. This equation can be interpreted as an edge relation, ensuring that if we traverse any closed path in ℤ^{2}, evaluating f when we move horizontally, and g when we move vertically, then the product of these values is always equal to 1 ∈ G.

For one-dimensional subshifts, the collection of cocycles is large, and difficult to study. By contrast, recent work of Kammeyer [9], [10], [11], Parry [18], and Schmidt [25], [26], [27], reveals that for certain two-dimensional subshifts, the set of cocycles can be very small. The most extreme case is when, for every cocycle (f, g), the above edge relation is satisfied for the trivial reason that there exists some function h (called a transfer function), and constants c_{f}, c_{g}, such that f(x) = h(σx)c_{f}h(x)^{−1} and g(x) = h(τx)c_{g}h(x)^{−1}. In this case we say that (f, g) is trivial. Cocycle triviality tends to be associated (see Proposition 4) with positive entropy (i.e. exponential growth of complexity), though note (see [25]) that it also occurs in various zero entropy cases defined algebraically (generalisations of Ledrappier’s cellular automaton example [15]).

As well as helping to reveal combinatorial and geometric structure of a subshift, the study of cocycles is important for classification problems. If all cocycles of a given subshift are trivial, it implies that all skew product extensions are conjugate to the original subshift (see [9], [10], [11]).

In this article we give a sufficient condition to ensure the triviality of locally constant cocycles on a ℤ^{2} subshift X. We prove as well, that the corresponding transfer function must itself be locally constant (this contrasts with the one-dimensional situation, where unless the subshift is of finite type, the transfer function of a trivial locally constant cocycle is not necessarily locally constant). Our condition is that the alphabet of the subshift contains some semi-safe symbol. Roughly speaking, a symbol is semi-safe if it can be placed next to any other symbol in at least one horizontal direction and at least one vertical direction. Examples of such subshifts are the full shift, the golden mean shift, and the nearest neighbour subshifts considered by Burton & Steif [3]. We do not assume that X is of finite type. Our condition does not force the homoclinic equivalence relation of the subshift to have the n-specification condition required in [25], nor does it force the subshift to be mixing, even in the relatively benign case where X is of finite type. Our condition on the group where the cocycles take their values is a very general algebraic one, namely that it is locally (residually finite). This class includes all finite groups, abelian groups, metabelian groups, linear groups, free groups, and many other interesting classes of groups.

Our method is combinatorial, and emphasizes the way in which cocycle triviality depends on the fitting together of allowed blocks. Heuristically, the more ‘overlap’ there is between blocks (i.e. distinct blocks coinciding on sub-blocks), the more likely it is that all cocycles will be trivial. For a cocycle constant on cylinder sets of a given size, we derive a system of cocycle equations, where the variables in the equations are the values of the cocycle on these cylinder sets. The overlap between blocks allows us to express all variables in terms of a sufficiently small number of basis variables, forcing the cocycle to be trivial. The semi-safe hypothesis on X ensures we can make a canonical choice of basis variables as the size of the cylinder sets increases. In fact our method of reducing equations will work for any subshift for which all locally constant cocycles are trivial, though in general the canonical choice of basis variables may be less apparent.

The structure of this article is as follows. After some preliminary definitions and notation in section 2, we introduce semi-safe subshifts in section 3, and give several examples. In section 4 we briefly discuss the dynamical properties of semi-safe symbol subshifts. In section 5 we introduce cocycles, and in section 6 go over some relevant group theory. In section 7 we discuss the system of cocycle equations at the heart of our method. Section 8 is the key section. Here we show (Proposition 10) that a cocycle is completely determined by its values on a sufficiently small number of cylinder sets, and this leads to our main results, Theorems A and B. In section 9 we illustrate our method with a worked example.

Acknowledgments. Some of this work has appeared in my thesis [8]. I thank my Ph.D. supervisor Mark Pollicott for helpful conversations and encouragement. I am grateful to Giovanni Cutolo for advice on the group theory in section 6.

Section 2. Preliminaries.

Definition 1. Given an alphabet A = {0, …, k − 1}, k ≥ 2, with the discrete topology, we define the full shift A^{ℤ^{2}} on A to be the set of all maps x : ℤ^{2} → A. We often write x = (x_{(m,n)}) = (x_{(m,n)})_{(m,n)∈ℤ^{2}}.

A^{ℤ^{2}} is compact in the Tychonov product topology, which is induced by the metric δ given by

δ(x, y) = \{ \begin{matrix}0 & if x = y \\ 2^{− min\{|m|+|n|:x_{(m,n)}≠y_{(m,n)}\}} & otherwise \end{matrix} .

The horizontal and vertical shift maps σ, τ : A^{ℤ^{2}} → A^{ℤ^{2}} are defined by

(σ(x))_{(m,n)} = x_{(m+1,n)} , (τ(x))_{(m,n)} = x_{(m,n+1)} .

A non-empty closed subset X ⊆ A^{ℤ^{2}} is called a subshift if σ(X) = X and τ(X) = X.

Definition 2. For M, N ∈ ℕ and (m_{0}, n_{0}) ∈ ℤ^{2} we define the rectangle

R_{(m_{0},n_{0})}(M, N) = {m_{0}, …, m_{0} + M − 1} × {n_{0}, …, n_{0} + N − 1}.

If the basepoint (m_{0}, n_{0}) is unimportant, we simply write R(M, N).

For N ∈ ℕ we define

\begin{matrix}S_{N} = & \{1 − N, …, N − 1\} × \{1 − N, …, N − 1\}, \\ T_{N} = & \{1 − N, …, N\} × \{1 − N, …, N\}, \\ F_{N} = & \{1 − N, …, N\} × \{1 − N, …, N − 1\}, \\ G_{N} = & \{1 − N, …, N − 1\} × \{1 − N, …, N\}. \end{matrix}

For F ⊆ F′ ⊆ ℤ^{2} we define π_{F} : A^{F′} → A^{F} to be the projection map which restricts each element of A^{F′} to the set F. Often we choose F′ = ℤ^{2}.

Given F ⊆ ℤ^{2}, we say an element of A^{F} is a decoration of F. A decoration B of a rectangle R ⊂ ℤ^{2} is called a block. Such a block B is globally allowed by a subshift X if there exists some x ∈ X with π_{R}(x) = B. In this case we also say that B extends to a point of X, that x is an extension of B, and that B appears in x. The shift invariance of X means that a block B is globally allowed if and only if the corresponding decoration of all translated rectangles is also allowed.

No generality is lost by making the following assumption about all subshifts X, which just ensures the corresponding alphabet A is of minimal size.

Assumption. Every symbol a ∈ A extends to a point of X.

Given a subshift X ⊆ A^{ℤ^{2}} and a globally allowed block B ∈ A^{R}, where R = R_{(m_{0},n_{0})}(M, N), we define

[B] = [B]_{(m_{0},n_{0})} = {x ∈ X : π_{R}(x) = B}.

We say [B] is a cylinder set of size R. If we want to make explicit the block B we will write

[B] = [ \begin{matrix}B_{(m_{0},n_{0}+N−1)} & … & B_{(m_{0}+M−1,n_{0}+N−1)} \\ ⋮ & & ⋮ \\ B_{(m_{0},n_{0})} & … & B_{(m_{0}+M−1,n_{0})} \end{matrix} ]_{(m_{0},n_{0})} .  (1)

Sometimes the basepoint (m_{0}, n_{0}) will be clear from the context, in which case we omit the subscript from the right hand square bracket. For a fixed rectangle the corresponding family of cylinder sets (all non-empty by definition) gives a finite partition of X.

Definition 3. If F ⊆ ℤ^{2} is finite, and P ⊆ A^{F}, then

X = X_{(F,P)} = {x ∈ A^{ℤ^{2}} : π_{F} (σ^{m}τ^{n}(x)) ∈ P ∀(m, n) ∈ ℤ^{2}}  (2)

is called the subshift of finite type defined by F and P. We call P the set of locally allowed decorations of F.

If X_{F,P} is a subshift of finite type, we say a block B ∈ A^{R} is locally allowed if π_{F′∩R}(B) ∈ π_{F′∩R}(P) for each translation F′ = F + (i, j) which intersects the rectangle R. Every globally allowed block is locally allowed, but the converse is not necessarily true. Moreover, and in contrast to the case for one-dimensional subshifts of finite type, in general there exists no finite time algorithm for determining whether a given locally allowed block is globally allowed. Consequently there exists no finite time algorithm for determining whether a given subshift of finite type is the empty set or not. Further discussion of these ‘extension’ and ‘emptiness’ problems can be found in Berger [1], Kitchens & Schmidt [14], Robinson [22] and Wang [29].

Definition 4. Let A = {0, …, k −1}, and suppose M_{H}, M_{V} are k ×k zero-one matrices. We define the matrix subshift X ⊆ A^{ℤ^{2}} by

X = {x ∈ A^{ℤ^{2}} : M_{H}(x_{(m,n)}, x_{(m+1,n)}) = 1, M_{V} (x_{(m,n)}, x_{(m,n+1)}) = 1 ∀(m, n) ∈ ℤ^{2}} .

Section 3. Semi-safe symbol subshifts.

Definition 5. For a subshift X ⊆ A^{ℤ^{2}}, a symbol a ∈ A is called a safe symbol if every globally allowed block can be extended to a point of X by decorating the rest of ℤ^{2} with the symbol a. If such a symbol exists then X is called a safe symbol subshift.

There are several possible weaker definitions of a safe symbol, where we only require that the symbol extends globally allowed blocks in two directions (one horizontal direction and one vertical direction). First we introduce some notation to describe certain semiinfinite regions of ℤ^{2}.

Definition 6. Let R = {M^{−}, …, M^{+}} × {N^{−}, …, N^{+}} ⊂ ℤ^{2} be a rectangle. We define the following regions relative to R. {(m, n) ∈ ℤ^{2} : m < M^{−} and N^{−} ≤ n ≤ N^{+}} is the West strip of R. {(m, n) ∈ ℤ^{2} : m > M^{+} and N^{−} ≤ n ≤ N^{+}} is the East strip of R. {(m, n) ∈ ℤ^{2} : n < N^{−} and M^{−} ≤ m ≤ M^{+}} is the South strip of R. {(m, n) ∈ ℤ^{2} : n > N^{+} and M^{−} ≤ m ≤ M^{+}} is the North strip of R. {(m, n) ∈ ℤ^{2} : m ≤ M^{+} and n ≤ N^{+}} is the SouthWest quadrant of R. {(m, n) ∈ ℤ^{2} : m ≥ M^{−} and n ≤ N^{+}} is the SouthEast quadrant of R. {(m, n) ∈ ℤ^{2} : m ≥ M^{−} and n ≥ N^{−}} is the NorthEast quadrant of R. {(m, n) ∈ ℤ^{2} : m ≤ M^{+} and n ≥ N^{−}} is the NorthWest quadrant of R.

Note that R is not a subset of any of its strips, but is a subset of each of its quadrants.

Lemma 1. Let X ⊆ A^{ℤ^{2}} be a subshift, and let a ∈ A. Fix ‘Vert’ to mean either ‘North’ or ‘South’. Fix ‘Horiz’ to mean either ‘East’ or ‘West’. The following three conditions are equivalent.

(a) For any rectangle R = {M^{−}, …, M^{+}} × {N^{−}, …, N^{+}} ⊂ ℤ^{2}, and any globally allowed block B ∈ A^{R}, there exists x ∈ X which is an extension of B and which decorates the Horiz strip of R with all a’s, and there exists y ∈ X which is an extension of B and which decorates the Vert strip of R with all a’s.

(b) For any rectangle R = {M^{−}, …, M^{+}} × {N^{−}, …, N^{+}} ⊂ ℤ^{2}, and any globally allowed block B ∈ A^{R}, there exists x ∈ X which decorates the rest (i.e. all except R) of the VertHoriz quadrant of R with all a’s.

(c) For any rectangle R = {M^{−}, …, M^{+}} × {N^{−}, …, N^{+}} ⊂ ℤ^{2}, and any globally allowed block B ∈ A^{R}, there exists y ∈ X which decorates all of ℤ^{2} except the quadrant diagonally opposite the VertHoriz quadrant of R with all a’s.

Proof. Throughout the proof we will assume, without loss of generality, that the vertical direction is South, and the horizontal direction is West.

(a) ⇒ (b) Let B be a globally allowed block with corresponding rectangle R = {M^{−}, …, M^{+}} × {N^{−}, …, N^{+}}. Let x ∈ X be an extension of B which decorates the West strip of R with all a’s. For each M ∈ ℕ, define the rectangle R_{M} = {M^{−} − M, …, M^{+}} × {N^{−}, …, N^{+}}, and the block B_{M} = π_{R_{M}} (x). Let y_{M} ∈ X be an extension of B_{M} which decorates the South strip of R_{M} with all a’s. So y_{M} decorates the region

C_{M} = {(m, n) ∈ ℤ^{2} : M^{−} − M ≤ m ≤ M^{+}, n ≤ N^{+}} \ R

with all a’s. Now the union of all the C_{M}’s is the whole of the SouthWest quadrant except R. So compactness of X means we can choose a convergent subsequence y_{M_{i}} whose limit y decorates all of the SouthWest quadrant (except R) with a’s.

(b) ⇒ (c) Let B be a globally allowed block with corresponding rectangle R = {M^{−}, …, M^{+}} × {N^{−}, …, N^{+}}. Let x ∈ X be any extension of B. For each M ∈ ℕ, define the rectangle R^{M} = {M^{−}, …, M^{+} + M} × {N^{−}, …, N^{+} + M}, and the (globally allowed) block B^{M} = π_{R^{M}} (x). Let y^{M} be an extension of B^{M} which decorates the rest (i.e. all except R^{M}) of the SouthWest quadrant of R^{M} with all a’s. We note that the union (over all M) of such regions is the complement of the NorthEast quadrant of R. Compactness of X means we can choose a convergent subsequence y^{M_{i}} whose limit y decorates all of ℤ^{2}, except the NorthEast quadrant of R, with a’s.

(c) ⇒ (a) Immediate. □

Definition 7. A symbol a ∈ A is called a semi-safe symbol for a subshift X ⊆ A^{ℤ^{2}} if it satisfies the equivalent conditions in Lemma 1. We say it is of direction VertHoriz, where ‘Vert’=‘North’ or ‘South’, and ‘Horiz’=‘East’ or ‘West’. If such a symbol exists, we say X is a semi-safe symbol subshift.

Clearly a safe symbol subshift is semi-safe in all directions.

Lemma 2. Let X ⊆ A^{ℤ^{2}} be a semi-safe symbol subshift, with semi-safe symbol a. Define the fixed point \underline{a} ∈ A^{ℤ^{2}} by \underline{a}_{(m,n)} = a for all (m, n) ∈ ℤ^{2}. Then \underline{a} ∈ X.

Proof. Since the symbol a is allowed, and X is semi-safe, then there exists y ∈ X which decorates some quadrant (the SouthWest, say) with all a’s. But X is closed and shift invariant, so that \underline{a} = lim_{n→∞}(στ)^{n}(y) ∈ X. □

Examples.

1. The full shift A^{ℤ^{2}} on any finite alphabet A is a safe symbol subshift, with every a ∈ A a safe symbol. Here every block is globally allowed. In particular, the horizontal language (i.e. the set of blocks of unit height) consists of all words on the alphabet A. Similarly for the vertical language (i.e. the set of blocks of unit width).

2. The matrix subshift X ⊂ {0, 1}^{ℤ^{2}} defined by

M_{H} = M_{V} = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )

is a safe symbol subshift, with safe symbol 0. This is known as the golden mean subshift. The horizontal language consists of all words on the alphabet {0, 1} which do not contain 11 as a subword. Similarly for the vertical language.

3. The matrix subshift X ⊂ {0, 1}^{ℤ^{2}} defined by

M_{H} = M_{V} = ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} )

is not a safe symbol subshift, but is a semi-safe symbol subshift. The symbol 0 is a semi-safe symbol, of type SouthWest. The symbol 1 is also a semi-safe symbol, of type NorthEast. The horizontal language consists of all words on the alphabet {0, 1} which do not contain 10 as a subword. Similarly for the vertical language.

4. The matrix subshift X ⊂ {0, 1, 2, 3}^{ℤ^{2}} defined by

M_{H} = M_{V} = ( \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \end{matrix} )

is not a safe symbol subshift, but is a semi-safe symbol subshift. The symbol 0 is a semi-safe symbol of type SouthWest. The horizontal language consists of all words on the alphabet {0, 1, 2, 3} which do not contain any of the subwords 10, 13, 20, 21, 31, 32. Similarly for the vertical language.

Section 4. Dynamical properties.

Definition 8. Let X ⊆ A^{ℤ^{2}} be a subshift. Given an element x ∈ X, we define its basin of attraction B(x) to be the set of all y ∈ X for which there exists (M, N) ∈ ℤ^{2} and a sequence n_{i} → ∞ such that (σ^{M}τ^{N})^{n_{i}}(y) → x as i → ∞. We say that x is attractive if B(x) is dense in X. If such an x ∈ X exists we say the subshift X is attractive.

Lemma 3. Suppose X ⊆ A^{ℤ^{2}} is a semi-safe symbol subshift. Then X is attractive.

Proof. Without loss of generality let us assume that the semi-safe symbol a is of direction SouthWest. By Lemma 2 we know the fixed point \underline{a} ∈ X. We will show that \underline{a} is attractive.

Suppose y ∈ X. For any N ≥ 1, define the block B_{N} = π_{S_{N}} (y). By condition (b) of Lemma 1 there exists y_{N} ∈ X which decorates the rest (i.e. all except S_{N}) of the SouthWest quadrant of S_{N} with all a’s. Then each y_{N} ∈ B(\underline{a}), since (σ^{−1}τ^{−1})^{n}(y_{N}) → \underline{a} as n → ∞. But y_{N} → y as N → ∞. Therefore B(\underline{a}) is dense in X. □

Definition 9. Let X ⊆ A^{ℤ^{2}} be a subshift. The topological entropy of X is defined by

h(X) = lim_{N→∞} \frac{1}{|T_{N}|} log |π_{T_{N}} (X)| ,

where | · | denotes the cardinality of a set.

Proposition 4. Every safe symbol subshift of finite type X ⊆ A^{ℤ^{2}} has positive topological entropy.

Proof. If X = X_{F,P} then (by a recoding if necessary) we may assume that F = {0, 1}^{2}. Let a ∈ A be a safe symbol. For all b ∈ A the following blocks begin to P:

\begin{matrix}a & a \\ a & a \end{matrix} , \begin{matrix}a & a \\ a & b \end{matrix} , \begin{matrix}a & a \\ b & a \end{matrix} , \begin{matrix}a & b \\ a & a \end{matrix} , \begin{matrix}b & a \\ a & a \end{matrix} .

Given the 2N × 2N square T_{N}, we want to estimate |π_{T_{N}} (X)|, the number of globally allowed decorations of T_{N}. Let us assume that N = 3M for some M ∈ ℕ. Then we can divide T_{N} into 4M^{2} squares of size 3 × 3, in the obvious way. We can decorate the central coordinate of each 3 × 3 square arbitrarily, and then decorate the rest of T_{N} with the safe symbol a, to obtain a block B. By decorating the rest of ℤ^{2} with the safe symbol a, we obtain a point x ∈ A^{ℤ^{2}}. We see that in fact x ∈ X, since each π_{F} (σ^{m}τ^{n}(x)) is in the form of one of the above five blocks.

So each such decoration gives an element of π_{T_{N}} (X). But there are |A|^{4M^{2}} such decorations. Therefore

h(X) = lim_{M→∞} \frac{1}{|T_{3M}|} log |π_{T_{3M}} (X)|

≥ lim_{M→∞} \frac{1}{(36M^{2})} log |A|^{4M^{2}} = \frac{1}{9} log |A| > 0. □

Section 5. Cocycles.

Definition 10. Given a subshift X ⊆ A^{ℤ^{2}} and a group G we say f : X → G is locally constant if there exists some finite subset E ⊂ ℤ^{2} such that

π_{E}(x) = π_{E}(y) ⇒ f(x) = f(y).  (3)

Any such E is called a set of active coordinates for f.

Definition 11. Let G be a group, and X ⊆ A^{ℤ^{2}} a subshift. For locally constant f, g : X → G we say the pair (f, g) is a (G-valued) cocycle on X if for all x ∈ X,

f(τx)g(x) = g(σx)f(x).  (4)

This cocycle is called trivial if there exist c_{f}, c_{g} ∈ G and a continuous function h : X → G (called the transfer function) such that for all x ∈ X,

f(x) = h(σx)c_{f} h(x)^{−1} and g(x) = h(τx)c_{g} h(x)^{−1}.  (5)

Remark. If X is a semi-safe symbol subshift, then it contains a fixed point \underline{a} (see Lemma 2). If (f, g) is a G-valued cocycle on X then (4) implies that f(\underline{a}) and g(\underline{a}) commute. Moreover, if (f, g) is trivial, then (5) implies that the constants c_{f}, c_{g} also commute.

Definition 12. For a given semi-safe symbol subshift X, let V denote the set of all (locally constant) cocycles. Let V′ ⊂ V be the subset consisting of those trivial cocycles whose transfer function is locally constant. A cocycle (f, g) is said to be of degree N if the active coordinates of f lie in F_{N} and the active coordinates of g lie in G_{N}. Let V_{N} = V_{N}(X) denote the set of cocycles of degree N. Let V′_{N} = V′_{N}(X) be the subset of V_{N} consisting of trivial cocycles with locally constant transfer function. Note that such a transfer function must necessarily have active coordinates in S_{N}. If \underline{a} ∈ X is the fixed point decorated solely by the semi-safe symbol, and i, j ∈ G satisfy ij = ji, then define

V_{N}(i, j) = \{(f, g) ∈ V_{N} : f(\underline{a}) = i, g(\underline{a}) = j\},
V′_{N}(i, j) = \{(f, g) ∈ V′_{N} : f(\underline{a}) = i, g(\underline{a}) = j\}.

Note that

⋃_{N} V_{N} = V, ⋃_{N} V′_{N} = V′, ⋃_{ij=ji} V_{N}(i, j) = V_{N}, ⋃_{ij=ji} V′_{N}(i, j) = V′_{N},

and that all these sets are subsets of the group H = G^{|π_{F_{N}} (X)|} × G^{|π_{G_{N}} (X)|}. If G is abelian then the various sets are in fact subgroups of H, while if G is (the additive group of) a field then they are vector subspaces of H.

Lemma 5. Let X be a semi-safe symbol subshift, and suppose that (f, g) ∈ V′ is a trivial locally constant G-valued cocycle on X, for some group G. Suppose h, h′ : X → G are both locally constant transfer functions for (f, g). Then there exists b ∈ G such that h(z) = h′(z)b for all z ∈ X.

Proof. We may assume the semi-safe symbol is of direction SouthWest. Since h, h′ are both locally constant, we may assume their active coordinates both lie in the square S_{N} for some N ≥ 1. If \underline{a} ∈ X is the fixed point decorated solely by the semi-safe symbol, then there is a dense subset B ⊂ X of points z such that (σ^{−1}τ^{−1})^{i}(z) → \underline{a} as i → ∞. So for each z ∈ B there exists M_{z} ∈ ℕ such that if i ≥ M_{z} then the square block π_{S_{N}} ((σ^{−1}τ^{−1})^{i}(z)) is decorated solely by the semi-safe symbol. It follows that

h((σ^{−1}τ^{−1})^{i}(z)) = h(\underline{a}) and h′((σ^{−1}τ^{−1})^{i}(z)) = h′(\underline{a}) for all i ≥ M_{z}.  (6)

Now since (f, g) is trivial, there are commuting pairs of constants c_{f}, c_{g} and d_{f}, d_{g} such that

f(z) = h(σz)c_{f} h(z)^{−1} , g(z) = h(τz)c_{g} h(z)^{−1},
f(z) = h′(σz)d_{f} h′(z)^{−1} , g(z) = h′(τz)d_{g} h′(z)^{−1}.

This implies that

h(σ^{m}τ^{n}z)c_{f}^{m}c_{g}^{n}h(z)^{−1} = h′(σ^{m}τ^{n}z)d_{f}^{m}d_{g}^{n}h′(z)^{−1} for all (m, n) ∈ ℤ^{2}.  (7)

Setting m = n = −M_{z}, and writing γ = c_{f}c_{g}, δ = d_{f}d_{g}, we obtain

h(\underline{a})γ^{−M_{z}}h(z)^{−1} = h′(\underline{a})δ^{−M_{z}}h′(z)^{−1}.

Rearranging this equation gives

h′(z)^{−1}h(z) = δ^{M_{z}}h′(\underline{a})^{−1}h(\underline{a})γ^{−M_{z}}.  (8)

In equation (7) we can also set m = n = −(M_{z} + 1), and by the same process we obtain

h′(z)^{−1}h(z) = δ^{M_{z}+1}h′(\underline{a})^{−1}h(\underline{a})γ^{−(M_{z}+1)}.  (9)

Equating (8) and (9), then left-multiplying by δ^{−M_{z}} and right-multiplying by γ^{M_{z}}, gives us

δh′(\underline{a})^{−1}h(\underline{a})γ^{−1} = h′(\underline{a})^{−1}h(\underline{a}),

and by induction we deduce

δ^{j}h′(\underline{a})^{−1}h(\underline{a})γ^{−j} = h′(\underline{a})^{−1}h(\underline{a}) for all j ≥ 0.

In particular, for all z ∈ B we have

δ^{M_{z}}h′(\underline{a})^{−1}h(\underline{a})γ^{−M_{z}} = h′(\underline{a})^{−1}h(\underline{a}).  (10)

Substituting (10) into (8) gives

h′(z)^{−1}h(z) = h′(\underline{a})^{−1}h(\underline{a}) for all z ∈ B.

So the continuous function z ↦ h′(z)^{−1}h(z) is constant on the dense set B, and is therefore constant on all of X. The result follows. □

Section 6. The algebraic argument.

In this section we develop the algebraic machinery underpinning our combinatorial technique, introducing those classes of groups to which our main Theorems A and B apply.

Fix a free group F_{m} of rank m. Let x_{1}, …, x_{m} be a basis for F_{m}. Let w = (w_{1}, …, w_{n}) be an n-tuple of elements (words) of F_{m}, such that w_{1}, …, w_{n} generate F_{m} (so n ≥ m).

For any group Γ we define w^{∗} : Γ^{m} → Γ^{n} by

w^{∗}(g_{1}, …, g_{m}) = (w_{1}(g_{1}, …, g_{m}), …, w_{n}(g_{1}, …, g_{m})).

Let S(w, Γ) = S(m, w, Γ) denote Image(w^{∗}) ⊂ Γ^{n}.

We now define a notion of dimension for certain subsets of Γ^{n}, and a class of groups which behave well with respect to this notion.

Definition 13. Suppose A ⊂ Γ^{n} is equal to S(m, w, Γ) for free group F_{m} and n-tuple w as above. We say A has dimension m over Γ if such an equality cannot hold for any number smaller than m.

Definition 14. A group Γ is called field-like if for all m, n ∈ ℕ, n ≥ m, and for all m-dimensional subsets S, S′ ⊂ Γ^{n}, S ⊂ S′ if and only if S′ ⊂ S.

Definition 15. Suppose X is some property of groups. We say a group Γ is residually X if for all 1 ≠ g ∈ Γ there exists a normal subgroup N_{g} such that g ∉ N_{g} and Γ/N_{g} satisfies X.

Definition 16. Suppose X is some property of groups. We say a group Γ is locally (residually X) if all of its finitely generated subgroups are residually X.

Proposition 6. Every locally (residually finite) group is field-like.

Proof. First we characterise the class of field-like groups. As above we let x_{1}, …, x_{m} be a basis for the free group F_{m} of rank of m, and w = (w_{1}, …, w_{n}) be an n-tuple of words of F_{m} which generate F_{m}.

Since w_{1}, …, w_{n} generate F_{m}, there are words ŵ_{1}, …, ŵ_{m} on n symbols such that ŵ_{i}(w) = x_{i} for each i ∈ {1, …, m}.

Define ŵ : Γ^{n} → Γ^{m} by

ŵ(g_{1}, …, g_{n}) = (ŵ_{1}(g_{1}, …, g_{n}), …, ŵ_{m}(g_{1}, …, g_{n})).

Note that ŵ ∘ w^{∗} : Γ^{m} → Γ^{m} is the identity map, where w^{∗} is as above. In particular, w^{∗} is injective.

If we choose another n-tuple v = (v_{1}, …, v_{n}) of generators of F, then the set S(v, Γ) and the maps v^{∗}, v̂ can be defined similarly.

Now S(w, Γ) is contained in S(v, Γ) if and only if w^{∗} = v^{∗} ∘ v̂ ∘ w^{∗}. This is because if g ∈ Γ^{m} satisfies w^{∗}(g) = v^{∗}(h) for some h ∈ Γ^{m}, then h = v̂ ∘ v^{∗}(h) = v̂ ∘ w^{∗}(g). Applying v^{∗} to both sides gives v^{∗}(h) = v^{∗} ∘ v̂ ∘ w^{∗}(g), which implies w^{∗}(g) = v^{∗} ∘ v̂ ∘ w^{∗}(g).

So for fixed n-tuples w and v, the class Y (w, v) of groups Γ for which S(w, Γ) is contained in S(v, Γ) is defined by a set of equations between values of words. Thus Y (w, v) is a variety of groups (see Robinson [21], page 56). Let Z(w, v) be the class of groups Γ such that S(w, Γ) is contained in S(v, Γ) if and only if the reverse inclusion holds. If Z denotes the intersection of Z(w, v) over all possible n-tuples w, v then Z is precisely the class of field-like groups.

Now if Γ is a finite group then we have |S(w, Γ)| = |S(v, Γ)| = |Γ|^{m}. Thus S(w, Γ) ⊂ S(v, Γ) if and only if S(v, Γ) ⊂ S(w, Γ). So any finite group belongs to the class Z(w, v).

Now since Y (w, v) and Y (v, w) are both varieties, it follows that any group which is locally (residually in Z(w, v)) is itself in Z(w, v) (see Robinson [21], page 57). So any group which is locally (residually finite) belongs to Z(w, v). Since w, v were arbitrary, the result follows. □

The class of locally (residually finite) groups is discussed in Chapter 9 of Robinson [20]. The following classes of groups are all locally (residually finite).

(a) All finite groups.

(b) All abelian groups.

(c) All metabelian groups (i.e. those soluble groups of derived length at most two). This class includes all abelian groups.

(d) All locally (polycyclic-by-finite) groups. This class contains all metabelian groups. A group Γ is polycyclic if there is a chain of normal subgroups 1 = Γ_{0}◁ Γ_{1}◁ ⋯◁ Γ_{n} = Γ such that each quotient Γ_{i+1}/Γ_{i} is cyclic. A group is polycyclic-by-finite if it has a polycyclic normal subgroup of finite index. A group is locally (polycyclic-by-finite) if all its finitely generated subgroups are polycyclic-by-finite. The fact that this class of groups is locally (residually finite) is a consequence of the Jategaonkar-Roseblade Theorem (see Theorem 6.6 in Passman [19]).

(e) All groups of matrices over finitely generated integral domains are residually finite, and hence locally (residually finite) (see chapter 4 of Wehrfritz [30]).

(f) All free groups (see Robinson [21], page 158).

Proposition 7. If F is a field, then any matrix group M(F) over F is locally (residually finite). Thus in particular any linear Lie group is locally (residually finite).

Proof. Suppose H is a finitely generated subgroup of M(F). Choose a finite set B of generators of H, and let C be the set of all elements of F that appear as entries of elements of B. Let R be the subring of F generated by C. Then H can be regarded as a group of matrices over the finitely generated integral domain R, and is therefore residually finite by (d) above. Thus M(F) is locally (residually finite). □

Section 7. The system of cocycle equations.

For a fixed rectangle R = R_{(m_{0},n_{0})}, the family of non-empty cylinder sets [B] determines a finite partition of the subshift X. It follows that if some function φ : X → ℝ is locally constant, with active coordinates lying in R, then φ is completely determined by its values on the (finite number of) cylinder sets of size R. The value of φ on such a cylinder set [B] of size R is called the variable (or φ-variable) corresponding to [B], and will be denoted by

φ[B] = \{B\}_{φ} = \{ \begin{matrix}B_{(m_{0},n_{0}+N−1)} & … & B_{(m_{0}+M−1,n_{0}+N−1)} \\ ⋮ & & ⋮ \\ B_{(m_{0},n_{0})} & … & B_{(m_{0}+M−1,n_{0})} \end{matrix} \}_{φ} .  (11)

This notation will only ever be used in the context of a cocycle (f, g) and transfer function h. Since the size of the active coordinates rectangle is different for each of these functions, we will sometimes omit the subscript from the right hand bracket in (11) without causing any ambiguity.

Note the difference between the notation in (1) and in (11). Square brackets will denote the cylinder set itself, and curly brackets will denote the value of a function on the cylinder set.

Lemma 8. Suppose (f, g) ∈ V_{N}(X), where X ⊆ A^{ℤ^{2}} is a subshift. The |π_{F_{N}} (X)| f-variables and |π_{G_{N}} (X)| g-variables satisfy a system of |π_{T_{N}} (X)| equations. In each equation there are two f-variables and two g-variables.

Proof. Since (f, g) is of degree N, each of the four functions in the cocycle equation has active coordinates in the square T_{N}. Let the block

C = \begin{matrix}C_{1−N,N} & … & … & C_{N,N} \\ ⋮ & & & ⋮ \\ ⋮ & & & ⋮ \\ C_{1−N,1−N} & … & … & C_{N,1−N} \end{matrix}

be a globally allowed decoration of T_{N}, and let [C] be the corresponding cylinder set.

We now consider the cocycle equation fτ.g = gσ.f, restricted to the set [C], which can be written explicitly as

\{ \begin{matrix}C_{1−N,N} & … & … & C_{N,N} \\ ⋮ & & & ⋮ \\ C_{1−N,2−N} & … & … & C_{N,2−N} \end{matrix} \}_{f} \{ \begin{matrix}C_{1−N,N} & … & C_{N−1,N} \\ ⋮ & & ⋮ \\ ⋮ & & ⋮ \\ C_{1−N,1−N} & … & C_{N−1,1−N} \end{matrix} \}_{g}

= \{ \begin{matrix}C_{2−N,N} & … & C_{N,N} \\ ⋮ & & ⋮ \\ ⋮ & & ⋮ \\ C_{2−N,1−N} & … & C_{N,1−N} \end{matrix} \}_{g} \{ \begin{matrix}C_{1−N,N−1} & … & … & C_{N,N−1} \\ ⋮ & & & ⋮ \\ C_{1−N,1−N} & … & … & C_{N,1−N} \end{matrix} \}_{f} .

□

Example. Let X = {0, 1}^{ℤ^{2}} be the full shift on two symbols, and suppose (f, g) ∈ V_{2}(X). So the cocycle equation gives a system of 2^{16} = 65536 equations in 2^{12} + 2^{12} = 8192 variables. For example the block

C = 0 1 1 0 1 1 1 0 1 0 1 1 0 1 0 0

gives rise to the equation

\{ \begin{matrix}0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{matrix} \} \{ \begin{matrix}0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} \} = \{ \begin{matrix}1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{matrix} \} \{ \begin{matrix}1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \end{matrix} \} .

Section 8. The dynamic argument.

Proposition 9. Let G be a group, and X ⊆ A^{ℤ^{2}} a semi-safe symbol subshift. For any i, j ∈ G satisfying ij = ji, the set V′_{N}(i, j) has dimension |π_{S_{N}} (X)| − 1 over G.

Proof. The transfer function h of a cocycle in V′_{N}(i, j) is only unique up to a constant (see Lemma 5). Once we have specified h(\underline{a}), where \underline{a} ∈ X is the fixed point decorated solely by the semi-safe symbol, equation (5) gives us the constants c_{f}, c_{g} ∈ G in terms of i, j, and h(\underline{a}). Since i, j commute, then so do c_{f}, c_{g}. We have complete freedom in the choice of the remaining |π_{S_{N}} (X)| − 1 h-variables, and now we have completely specified our trivial cocycle. □

Proposition 10. Let G be a group, and X ⊆ {0, 1}^{ℤ^{2}} a semi-safe symbol subshift. For any i, j ∈ G satisfying ij = ji, the set V_{N}(i, j) has dimension |π_{S_{N}} (X)| − 1 over G.

Proof. By Proposition 9 we know the dimension of V_{N}(i, j) is at least |π_{S_{N}} (X)| − 1. We now show that a judicious choice of |π_{S_{N}} (X)| − 1 variables is sufficient to parametrise V_{N}(i, j).

Without loss of generality let us assume that 0 is the semi-safe symbol, and is of direction SouthWest.

Suppose (f, g) ∈ V_{N}(i, j). We immediately deduce that the value of f (resp. g) on the cylinder set containing the fixed point \underline{0} is i (resp. j). These will be the first of our basis variables. We will fix |π_{S_{N}} (X)| − 1 more basis variables, and then show that the values of all variables can be deduced from the |π_{S_{N}} (X)| + 1 basis variables.

We choose the extra basis variables to be all f-variables of the form

\{ \begin{matrix}0 & ⋆ & … & ⋆ \\ ⋮ & ⋮ & & ⋮ \\ 0 & ⋆ & … & ⋆ \end{matrix} \}_{f}

(i.e. the values of f on all those cylinder sets of size F_{N} whose left-hand column is decorated by the semi-safe symbol 0). Since the block consisting of all zeros was already in the basis, this indeed gives us |π_{S_{N}} (X)| − 1 new basis variables. This is because (by shift invariance) there are |π_{S_{N}} (X)| globally allowed ways of decorating the translated square S_{N} + (1, 0) (i.e. of filling in the asterisks in the above diagram). Since 0 is a SouthWest safe symbol, we can decorate the left hand column of F_{N} with all 0’s, and the resulting block will correspond to a non-empty cylinder set.

Our method of proof is as follows. By Lemma 8 we know that each globally allowed block C of size T_{N} gives an equation in four variables. Starting with our basis variables (the ‘known’ variables) we choose an appropriate block C (i.e. one for which exactly 3 of the variables f([C]), fτ([C]), g([C]), gσ([C]) are known). Using the cocycle equation on [C] we obtain an expression for the previously unknown variable in terms of the known variables. We now include this variable in the set of known variables.

We repeat the process. As the number of known variables increases, it becomes easier to find appropriate blocks C.

The above discussion is valid for any finite alphabet A. From now on, however, we use the fact that A = {0, 1}. In the proof of Proposition 11 we indicate the minor modifications necessary for larger alphabets.

For A = {0, 1} we claim that the following statement P (r) is true for all r ≥ 0.

All variables whose decorations contain r 1’s can be expressed in terms of those basis variables whose decorations contain ≤ r 1’s.

Clearly if P (r) is true for all r ≥ 0 then all variables are expressible in terms of the |π_{S_{N}} (X)| + 1 basis variables (since every variable contains r 1’s, for some 0 ≤ r ≤ 2N(2N − 1)), and we will have proved the proposition.

We will prove the statement P (r) by induction on r.

Clearly P (0) is true, since the f-variable consisting of all 0’s and the g-variable consisting of all 0’s are both basis variables.

Let our inductive hypothesis be that P (j) is true for j = 0, 1, …, r − 1. We will show this implies that P (r) is true.

Suppose we know all the basis variables with ≤ r 1’s. By the inductive hypothesis this implies we know all variables with j 1’s, for j = 0, 1, …, r − 1. So in total the known variables are:

1. All variables with strictly less than r 1’s.

2. All basis variables with r 1’s.

First we will deduce those g-variables with r 1’s. Let B be the (2N − 1) × 2N block corresponding to an arbitrary g-variable {B} with r 1’s. Let J be the largest rectangular sub-block of B which has at least one 1 in its right-hand column (so possibly J = B). Note that J also has r 1’s.

Consider the block J on its own, and then add columns of zeros to its left (possible since 0 is a semi-safe symbol of type SouthWest) until we have a block of size (2N −1)×2N. Call this block B_{0}. Note that B_{0} has r 1’s as well.

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 J The Block B  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  J The Block B_{0}

Now add one further column of zeros to the left of B_{0} to make a 2N × 2N square block C_{0}. Let B′_{0} denote the (2N − 1) × 2N block obtained by removing the right-hand column of C_{0}. Since J has at least one 1 in its right-hand column then B′_{0} contains strictly less than r 1’s.

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 0 0 0 0 0 0 0 0 0  B_{0} The Block C_{0}  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} B′_{0} The Block C_{0}

Now consider the cocycle equation on the cylinder set [C_{0}].

Both f-variables have their left-hand column full of 0’s, thus they are basis variables. Moreover, they both have ≤ r 1’s. Therefore they are known variables.

The g-variable {B′_{0}} contains strictly less than r 1’s, and therefore is a known variable (by the inductive hypothesis).

Thus the only unknown variable is the g-variable {B_{0}}. The cocycle equation therefore allows us to deduce {B_{0}}, which we now consider a known variable.

If B_{0} = B then we are done. Otherwise we can remove a column of zeros from the left of B_{0}, and add a column of zeros to the right, to obtain a (2N − 1) × 2N block B_{1}.

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  J The Block B_{0}  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  0 0 0 0 0 0 0 0 0 J The Block B_{1} 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Let C_{1} denote the 2N × 2N square block obtained by adding a column of 0’s to the left of B_{1}. Note that the (2N −1)×2N block obtained by removing the right-hand column of C_{1} is precisely B_{0}.

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 0 0 0 0 0 0 0 0 0  B_{1} The Block C_{1}  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} B_{0} The Block C_{1}

Now consider the cocycle equation on the cylinder set [C_{1}]. Both f-variables have their left-hand column full of 0’s, thus they are basis variables. Moreover, they both have ≤ r 1’s. Therefore they are known variables. The g-variable {B_{0}} is also now a known variable. The cocycle equation therefore allows us to deduce the previously unknown g-variable {B_{1}}.

In the same way we can continue to define (2N − 1) × 2N blocks B_{2}, B_{3}, B_{4} … and 2N × 2N square blocks C_{2}, C_{3}, C_{4} . . .. The cocycle equation on [C_{i}] always allows us to deduce the variable {B_{i}}, since {B_{i−1}} is known, and the two f-variables are also known. Eventually some B_{i} is equal to our original block B, so we have deduced the g-variable {B}. Since {B} was an arbitrary g-variable with r 1’s, we can consider all such variables to now be known.

Now in a similar way we will deduce all f-variables with r 1’s. Let {D} be an unknown f-variable with r 1’s, and with corresponding 2N × (2N − 1) block D (so the left-hand column of D does not consist solely of zeros). Let K be the largest rectangular sub-block of D which has at least one 1 in its top row (so possibly K = D). Note that K also has r 1’s.

Consider the block K on its own, and then add rows of zeros to its bottom until we have a block of size 2N × (2N − 1). Call this block D_{0}. Note that D_{0} has r 1’s as well.

Now add one further row of zeros to the bottom of D_{0} to make a 2N × 2N square block E_{0}. Let D′_{0} denote the 2N × (2N − 1) block obtained by removing the top row of E_{0}. Since K has at least one 1 in its top row then D′_{0} contains strictly less than r 1’s.

Now consider the cocycle equation on the cylinder set [E_{0}]. Both g-variables are known, by our previous discussion in this proof. The f-variable {D′_{0}} is also known, since it contains strictly less than r 1’s. Thus the cocycle equation allows us to deduce the previously unknown variable {D_{0}}, which we now consider a known variable.

If D_{0} = D then we are done. Otherwise we can remove a row of zeros from the bottom of D_{0} and add a row of zeros to the top, to obtain a 2N × (2N − 1) block D_{1}. Let E_{1} denote the 2N × 2N square block obtained by adding a row of 0’s to the bottom of D_{1}. Note that the 2N × (2N − 1) block obtained by removing the top row of E_{1} is precisely D_{0}.

Now consider the cocycle equation on the cylinder set [E_{1}]. Both g-variables are known, and the f-variable {D_{0}} is also now a known variable. The cocycle equation therefore allows us to deduce the previously unknown f-variable {D_{1}}.

In the same way we can continue to define 2N × (2N − 1) blocks D_{2}, D_{3}, D_{4} … and 2N × 2N square blocks E_{2}, E_{3}, E_{4} . . .. The cocycle equation on [E_{i}] always allows us to deduce the variable {D_{i}}, since {D_{i−1}} is known, and the two g-variables are also known. Eventually some D_{i} is equal to our original block D, so we have deduced the f-variable {D}. Since {D} was an arbitrary (non-basis) f-variable with r 1’s, we can consider all such variables to now be known.

Therefore all variables (both f-variables and g-variables) with r 1’s can be deduced from those basis variables with ≤ r 1’s. This completes the induction, and the proposition is proved. □

We now generalise Proposition 10 to semi-safe symbol subshifts with larger alphabets.

Proposition 11. Let G be a group, and X ⊆ A^{ℤ^{2}} a semi-safe symbol subshift. For any i, j ∈ G satisfying ij = ji, the set V_{N}(i, j) has dimension |π_{S_{N}} (X)| − 1 over G.

Proof. Suppose A = {0, …, k−1}. As in Proposition 10, let us assume that the symbol 0 is the semi-safe symbol, and that it is of direction SouthWest.

The case k = 2 was dealt with in Proposition 10. The method of proof for the general case is almost the same. The only difference is that we must use induction more carefully on the number of symbols of each type appearing in a variable.

As before, we deduce all variables consisting of 0’s and 1’s from those basis variables consisting of 0’s and 1’s. The method is to use induction on the number of 1’s in each variable. Now we introduce the symbol 2. That is, we consider variables containing only the symbols 0, 1 and 2. Using induction on the number of 2’s appearing in such variables, we eventually deduce all variables containing only 0, 1 and 2. We continue in this manner, introducing one new symbol at a time, until eventually we are able to deduce all variables, thus completing the proof.

(We remark that this proof amounts to putting a lexicographic ordering on the set of k-tuples \underline{r} = (r_{0}, r_{1}, …, r_{k−1}), where r_{i} is the number of times the symbol i occurs in a variable. We formulate a statement P (\underline{r}) analogous to the statement P (r) in Proposition 10, then prove it using induction on \underline{r}). □

Theorem A. Let G be a field-like group, and X ⊆ A^{ℤ^{2}} a semi-safe symbol subshift. Then every locally constant cocycle (f, g) on X is a trivial cocycle. The corresponding transfer function is itself locally constant.

Proof. By Propositions 9 and 11 we know that V′_{N}(i, j) and V_{N}(i, j) have the same dimension, for all i, j ∈ G with ij = ji, and for all N ∈ ℕ. Moreover V′_{N}(i, j) is a subset of V_{N}(i, j), so since G is field-like then in fact V′_{N}(i, j) = V_{N}(i, j). Taking the union over all pairs of commuting elements i, j gives that every cocycle of degree N is trivial, and that the corresponding transfer function has active coordinates in S_{N}. Taking the union over all N ∈ ℕ gives the result. □

Since every locally (residually finite) group is field-like we immediately deduce the following result.

Theorem B. Let G be a locally (residually finite) group, and X ⊆ A^{ℤ^{2}} a semi-safe symbol subshift. Then every locally constant cocycle (f, g) on X is a trivial cocycle. The corresponding transfer function is itself locally constant.

Section 9. An example : the full shift.

Let X = {0, 1}^{ℤ^{2}} be the full shift on two symbols. Both 0 and 1 are safe symbols, but for this example we will use 0 as our safe symbol. In particular, we will consider 0 as a semi-safe symbol of direction SouthWest. Let (f, g) be a locally constant cocycle on X, where the active coordinates of f and g lie in the rectangles {0, 1, 2} × {0, 1} and {0, 1} × {0, 1, 2} respectively. Note that these rectangles are not of the form F_{N} or G_{N}, but are of a convenient size to illustrate the proof of Proposition 10, without introducing unnecessary computation. (F_{1} and G_{1} are too small to show why we need the rectangles J and K, whereas if we use F_{2} and G_{2} then we already have 2^{9} = 512 basis variables). Suppose also that f (resp. g) takes the value i (resp. j) on the cylinder set containing the fixed point \underline{0}, where i, j commute.

If (f, g) were a trivial cocycle, its transfer function h would have active coordinates in the square {0, 1}^{2} ⊂ ℤ^{2}. Since there are 2^{4} globally allowed decorations of {0, 1}^{2}, the set of such transfer functions is 2^{4} +1 = 17 dimensional. However the choice of the commuting elements i, j ∈ G determines the value of the constants c_{f}, c_{g}, so the set of trivial cocycles of this size, and with the prescribed values on the fixed point \underline{0}, is of dimension 15.

Therefore to prove the cocycle triviality of X (for cocycles with active coordinates in the above rectangles), we will fix 15 basis variables, combine them with the two basis variables corresponding to the fixed point \underline{0}, and deduce all other f- and g-variables from these.

The total list of 17 basis variables is as follows (grouped according to the number of times the symbol 1 occurs in them).

\{ \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} \} , \{ \begin{matrix}0 & 0 \\ 0 & 0 \\ 0 & 0 \end{matrix} \} ,

\{ \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix} \} , \{ \begin{matrix}0 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} \} , \{ \begin{matrix}0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} \} , \{ \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix} \} ,

\{ \begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \end{matrix} \} , \{ \begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \end{matrix} \} , \{ \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} \} , \{ \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} \} , \{ \begin{matrix}0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix} \} , \{ \begin{matrix}0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix} \} ,

\{ \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \end{matrix} \} , \{ \begin{matrix}0 & 1 & 0 \\ 0 & 1 & 1 \end{matrix} \} , \{ \begin{matrix}0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} \} , \{ \begin{matrix}0 & 1 & 1 \\ 0 & 1 & 0 \end{matrix} \} ,

\{ \begin{matrix}0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} \} .

As in Proposition 10, we start by deducing all g-variables with one 1. To do this we only need use those basis variables with one 1 or no 1’s.

For example, suppose we want to deduce the variable

\{B\} = \{ \begin{matrix}0 & 0 \\ 1 & 0 \\ 0 & 0 \end{matrix} \} .

We first define the blocks

B_{0} = 0 0 0 1 0 0 and C_{0} = 0 0 0 0 0 1 0 0 0 .

The cocycle equation on the cylinder set [C_{0}] is

\{ \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix} \} \{ \begin{matrix}0 & 0 \\ 0 & 0 \\ 0 & 0 \end{matrix} \} = \{ \begin{matrix}0 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix} \} \{ \begin{matrix}0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} \} .

Since three of these variables are in the basis, we may deduce the unknown variable {B_{0}}. Now define the block

C_{1} = 0 0 0 0 1 0 0 0 0 .

The cocycle equation on the cylinder set [C_{1}] is

\{ \begin{matrix}0 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} \} \{B_{0}\} = \{B\} \{ \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix} \} .

The two f-variables are in the basis, and we have just deduced the variable {B_{0}}. Therefore we can deduce the variable {B}, as required.

In a similar way we can deduce all those g-variables containing one 1. Having done that, we can then deduce all the f-variables with one 1 (there are only two of these to deduce, since the four others are basis variables).

For example the variable

\{ \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} \}

is deduced by considering the cocycle equation on the cylinder set corresponding to the block

1 0 0 0 0 0 0 0 0 .

So now all variables containing at most 1 are considered to be ‘known’. These known variables, together with the basis variables containing two 1’s, are sufficient to deduce all variables containing two 1’s. Continuing in this way we can deduce all variables containing at most four 1’s. The remaining variables (i.e. those containing either five or six 1’s) can then be deduced immediately.

For example the f-variable

\{ \begin{matrix}1 & 1 & 1 \\ 1 & 0 & 1 \end{matrix} \}

is deduced by considering the cocycle equation on the cylinder set corresponding to the block

1 1 1 1 0 1 0 0 0 ,

since the other 3 variables all contain at most four 1’s.

References

[1] R. Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. No. 66, (1966).

[2] V. Berthé and L. Vuillon, Suites doubles de basse complexité, preprint, 1999.

[3] R. M. Burton and J. E. Steif, Nonuniqueness of measures of maximal entropy for subshifts of finite type, Ergod. Th. & Dyn. Sys., 14 (1994), 213–235.

[4] J. Cassaigne, Double sequences with complexity mn + 1, J. Auto. Lang. Comb., to appear.

[5] B. Durand, Tilings and quasiperiodicity, Theoret. Comput. Sci., 221 (1999), 61–75.

[6] C. Epifanio, P. Mignosi, M. Koskas, On a conjecture on bidimensional words, preprint, 1999.

[7] B. Grünbaum and G. C. Shephard, Tilings and Patterns, W. H. Freeman and Company, New York, 1987.

[8] O. Jenkinson, Conjugacy rigidity, cohomological triviality, and barycentres of invariant measures, Ph.D. Thesis, Warwick University.

[9] J. W. Kammeyer, A complete classification of two-point extensions of a multidimensional Bernoulli shift, J. Analyse Math., 54 (1990), 113–163.

[10] J. W. Kammeyer, A classification of the isometric extensions of a multidimensional Bernoulli shift, Ergod. Th. & Dyn. Sys., 12 (1992), 267–282.

[11] J. W. Kammeyer, A classification of the finite extensions of a multidimensional Bernoulli shift, Trans. Amer. Math. Soc., 335 (1993), 443–457.

[12] A. Katok and R. J. Spatzier, Differential rigidity of hyperbolic abelian actions, MSRI preprint, (1992).

[13] A. Katok and K. Schmidt, The cohomology of expansive ℤ^{d}-actions by automorphisms of compact, abelian groups, Pacific J. Math., 170 (1995), 105–142.

[14] B. Kitchens and K. Schmidt, Periodic points, decidability, and Markov subgroups, Lecture Notes In Mathematics, 1342, pp. 440–454, Springer-Verlag, 1988.

[15] F. Ledrappier, Un champ Markovien peut être d’entropie nulle et mélangeant, C. R. Acad. Sci. Paris, Sér. A 287 (1978), 561–562.

[16] N. G. Markley and M. E. Paul, Matrix subshifts for ℤ^{ν} symbolic dynamics, Proc. London Math. Soc. 43 (1981), 251–272.

[17] S. Mozes, A zero entropy, mixing of all orders tiling system, Symbolic dynamics and its applications (New Haven, CT, 1991), 319–325, Contemp. Math., 135, Amer. Math. Soc., Providence, RI, 1992.

[18] W. Parry, Instances of cohomological triviality and rigidity, Ergod. Th. & Dyn. Sys., 15 (1995), 685–696.

[19] D. S. Passman, Group rings of polycyclic groups, Group Theory: essays for Philip Hall, pp. 207–256, (ed. K. W. Gruenberg and J. E. Roseblade), Academic Press, 1984.

[20] D. J. S. Robinson, Finiteness Conditions and Generalized Soluble Groups, Part 2, Springer-Verlag, Berlin, Heidelberg, New York, 1972.

[21] D. J. S. Robinson, A Course in the Theory of Groups, Springer-Verlag, New York, Heidelberg, Berlin, 1982.

[22] R. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math. 12 (1971), 177–209.

[23] J. W. Sander, R. Tijdeman, The complexity of functions on lattices, Theoret. Comput. Sci., to appear.

[24] J. W. Sander, R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices, Theoret. Comput. Sci., to appear.

[25] K. Schmidt, The cohomology of higher-dimensional shifts of finite type, Pacific J. Math., 170 (1995), 237–269.

[26] K. Schmidt, Cohomological rigidity of algebraic ℤ^{d} actions, Ergod. Th. & Dyn. Sys., 15 (1995), 759–805.

[27] K. Schmidt, Tilings, fundamental cocycles and fundamental groups of symbolic ℤ^{d}- actions, Ergod. Th. & Dyn. Sys., 18 (1998), 1473–1525.

[28] L. Vuillon, Cominatoire des motifs d’une suite sturmienne bidimensionnelle, Theoret. Comput. Sci., 209 (1998), 261–285.

[29] H. Wang, Proving theorems by pattern recognition II, Bell System Tech. J. 40 (1961), 1–41.

[30] B. A. F. Wehrfritz, Infinite Linear Groups, Springer-Verlag, Berlin, Heidelberg, New York, 1973.