## Abstract

Periodic patterns of synchrony are lattice networks whose cells are coloured according to a local rule, or balanced colouring, and such that the overall system has spatial periodicity. These patterns depict the finite-dimensional flow-invariant subspaces for all the lattice dynamical systems, in the given lattice network, that exhibit those periods. Previous results relate the existence of periodic patterns of synchrony, in *n*-dimensional Euclidean lattice networks with nearest neighbour coupling architecture, with that of finite coupled cell networks that follow the same colouring rule and have all the couplings bidirectional. This paper addresses the relation between periodic patterns of synchrony and finite bidirectional coloured networks. Given an *n*-dimensional Euclidean lattice network with nearest neighbour coupling architecture, and a colouring rule with *k* colours, we enumerate all the periodic patterns of synchrony generated by a given finite network, or graph. This enumeration is constructive and based on the automorphisms group of the graph.

## 1. Introduction

*Lattice networks* are coupled cell networks whose spatial positions of the cells, or copies of a dynamical system, form a lattice . Each cell is connected to a set of neighbours such that the global structure, called the *lattice dynamical system*, has the symmetries of . See Stewart *et al.* (2003), Golubitsky *et al.* (2005) and the review paper by Golubitsky & Stewart (2006) for the general theory of coupled cell systems, Antoneli *et al.* (2005, 2007) for the particular case of lattice dynamical systems and §1*a*, below, for examples.

There are finite-dimensional flow-invariant subspaces of the lattice dynamical system that depend only on the lattice network and do not vary with specific properties of the dynamical system in each cell. Any of these subspaces is represented by a *pattern of synchrony*, a classification of the cells into *k* classes, or colours, such that the colour of each cell rules the colours of its neighbours. These are called *balanced k-colourings* and, for a nearest neighbour coupling architecture, each balanced colouring is described by a

*k*×

*k*matrix, or

*colouring rule*.

There are several results concerning patterns of synchrony in lattice networks. We refer, for example, to Golubitsky *et al.* (2004) and Wang & Golubitsky (2005) for the enumeration of two-colour patterns of synchrony in planar lattice networks. In these papers, periodicity is a common feature and there is no colouring rule corresponding uniquely to non-periodic patterns. Moreover, Antoneli *et al.* (2005) study *k*-colour patterns of synchrony in *n*-dimensional Euclidean lattices and their results show that, considering sufficiently extensive couplings, spatial periodicity always appears. Here *Euclidean* stands for lattices that are generated by a set of vectors with equal norm.

In this article, we consider periodic patterns of synchrony with *k* colours, for *n*-dimensional Euclidean lattice networks. The periodicity is spatial, along *n* non-collinear directions, and the lattice networks have *nearest neighbour coupling architecture*.

Fixing a colouring rule and a Euclidean lattice network , with nearest neighbour coupling architecture, Dias & Pinho (2009, theorem 5.4) establish an if and only if result between the existence of a periodic balanced colouring of and that of a finite bidirectional network with the same colouring rule and specific properties. These properties concern the graph associated with the finite network and its decomposition into factors that are identifiable with the nearest neighbours of the origin, in the lattice. Thus, a homomorphism is defined between the paths in the coloured lattice network and those in the finite network.

This result suggests the classification of periodic patterns of synchrony based on finite bidirectional coupled cell networks, which we describe as a three-step method.

To enumerate all the different colouring rules with

*k*colours and respecting the number of neighbours fixed by the architecture of the lattice network. For the particular case of nearest neighbour coupling architecture, if each element in the lattice network has*v*nearest neighbours, this step corresponds to the enumeration of*k*×*k*matrices with entries in**Z**^{+}_{0}and whose rows sum to*v*that are not the same up to permutations in**S**_{k}.For each colouring rule, to enumerate all the finite bidirectional networks with valence

*v*and a balanced colouring that are not related by symmetries. Given one of the finite bidirectional networks, it is possible to construct an infinite number of other finite bidirectional networks that would generate exactly the same patterns of synchrony. To avoid redundant cases we define the*root networks*, the smallest networks that can describe the particular relations between coloured cells that characterize the different patterns of synchrony.For each root network, to enumerate all the periodic patterns of synchrony that it generates.

In this article, we address the second and third steps. Our main results solve the third step.

Theorem 5.2 states the number of periodic patterns of synchrony, generated by a root network, for **Z**^{n} lattices, and gives a least upper bound for the remaining lattice networks, with nearest neighbour coupling architecture. The enumeration of periodic patterns of synchrony, given a root network with *m* cells, rests on the enumeration of the order *m* Abelian subgroups of the automorphism group for the graph associated with the network that act transitively on the set of cells and are not related by symmetries. In the example below, we illustrate this step, referring to the results that are proved in the paper.

Theorem 5.1 establishes the correspondence between equivalence classes of the decompositions of root networks and equivalence classes of periodic patterns of synchrony, clarifying the role of the decompositions not related by a symmetry in the construction of different periodic patterns of synchrony. The definition of equivalence classes is a major tool in the enumeration problem, preventing us from considering, for example, a planar pattern of synchrony and its reflection in a line, as two different cases.

### (a) Structure of the paper

We continue the introduction with an example illustrating the enumeration method and applying our main results. In §2, we present the basic concepts and notation on coupled cell networks and balanced colourings. We also define (§2*a*) equivalence classes of coloured networks, either finite networks or lattice networks, whose elements are related by symmetries.

The restrictions imposed by the fixed colouring rule on the finite bidirectional networks, based on Dias & Pinho (2009), are summarized in §3. We define root networks in §3*a*, after the statement of important results on the decompositions of a finite bidirectional network, or graph, and on the relation between the possible decompositions and the automorphisms group of the graph (see proposition 3.9).

In §4, we describe the procedures to generate periodic patterns of synchrony from finite bidirectional networks, derived by Dias & Pinho (2009). These procedures depend on suitable decompositions of the graph that corresponds to the finite bidirectional network. Corollary 4.6 states that every periodic pattern of synchrony can be generated by a root network.

Our main results, theorems 5.1 and 5.2, are stated in §5 and proved in §6.

### (b) Example

Consider the matrix *A*=(*a*_{ij}) with valence *v*=4
1.1
and let it describe a three-colouring rule of the cells of a four-regular graph in the following way: the colours are indexed by and each cell of colour *i* is connected to *a*_{ij} cells of colour *j*. Thus, *A* can be a three-colouring rule for coupled cell networks with valence 4 that are identical-edge, homogeneous and bidirectional (IEHB), either finite networks or lattice networks (see figure 1).

Let *ξ* be the colouring function, having the set of cells as domain, and range . By Dias & Pinho (2009, lemmas 4.3 and 4.8), the proportion of cells for each colour is given by the coordinates of the probability left eigenvector of *A* corresponding to the eigenvalue *v*=4, **p**^{T}=(1/5,2/5,2/5). Thus, the smallest IEHB networks with this colouring rule have five cells. Consider the IEHB network with set of cells , with adjacency matrix
and colour the cells using the colouring function *ξ*(*c*_{1})=1, *ξ*(*c*_{2})=*ξ*(*c*_{3})=2 and *ξ*(*c*_{4})=*ξ*(*c*_{5})=3. See figure 1, where the colours 1, 2 and 3 are, respectively, black, white and grey, and denote the network by *G*_{B}.

*Question.* Let be the lattice network defined by the planar lattice and the couplings between each cell and its four nearest neighbours (figure 2). The question we pose now is the following: how many different periodic colourings of the lattice network based on *G*_{B} and having the colouring rule *A* can we construct? Using the results of Dias & Pinho (2009, §§4 and 5), we perceive that the answer to this question depends on the number of ways of decomposing *G*_{B} into cycles and of associating these cycles with the directions of the lattice. In this paper, we show that the answer is based on the subgroups of Aut(*B*) with given properties.

*Symmetries.* In enumerating the periodic colourings of , we identify colourings that are related by symmetries of the colouring rule *A* and by Euclidean symmetries leaving invariant.

The matrix *A* commutes with the matrix
corresponding to the permutation *μ*=(1)(23) that swaps colours 2 and 3, so *μ*·*ξ* is another colouring with the colouring rule *A*. In fact, *μ* is the only non-trivial permutation of **S**_{3} such that *M*_{μ} commutes with *A*. We denote by the set of permutations that preserve the colouring rule *A*.

Denote by **P**_{ξ} the set of permutations of cells with the same colour that leave the colouring *ξ* invariant and, thus, do not change the colouring rule. Since there is one cell with colour 1 and there are two cells with each one of the two remaining colours, **P**_{ξ}=**S**_{1}×**S**_{2}×**S**_{2}.

Therefore, the network *G*_{B} defines an equivalence class of eight networks that have the same colouring rule *A*
where *λ* is either (*τ*,Id_{3}) or (*τ*,*μ*), for *τ*∈**P**_{ξ} and *I**d*_{3},*μ*∈**P**_{A}. We compute the elements of explicitly
*Enumeration.* The group of automorphisms of *G*_{B}, that is, the group of permutation matrices that commute with *B*, is *Γ*=**S**_{5}. This group has the following transitive subgroups of order *m*=5:
However, some of these subgroups are conjugate by elements of ,

Therefore, up to symmetries in , the only five-order transitive subgroups of the group of automorphisms of *G*_{B} are *Γ*_{1} and *Γ*_{4}. Moreover, they are Abelian subgroups and intersect **P**_{ξ} only in the trivial permutation, which ensures that *G*_{B} is a root network (see definition 3.10). From the main result of this paper (theorem 5.2), it follows that, up to symmetries, *G*_{B} generates exactly two different periodic colourings of the lattice network , having the colouring rule *A* and a fundamental domain (the set of cells that repeat periodically) with five cells, the number of cells of *G*_{B}. Specifically, each one of the two subgroups *Γ*_{1} and *Γ*_{4} leads to one balanced colouring of the lattice, as we now describe.

We refer to Dias & Pinho (2009, §1) for a step-by-step example on the decomposition into cycles of a finite bidirectional network, and on the association of these cycles with directions of the lattice.

The elements of the subgroup *Γ*_{1}=〈(*c*_{1}*c*_{2}*c*_{3}*c*_{4}*c*_{5})〉 are associated with the decomposition of *G*_{B} into two networks with valence 2, shown in figure 3*a*. If we associate the permutation *σ*_{1} with the direction of *l*_{1}=(1,0) and the permutation *σ*_{2} with the direction of *l*_{2}=(0,1), then we can cover the lattice network with the cells *c*_{1} to *c*_{5}, obtaining the periodic colouring presented in figure 4*a*, which inherits the colouring rule *A*.

The elements of the subgroup *Γ*_{4}=〈(*c*_{1}*c*_{2}*c*_{4}*c*_{5}*c*_{3})〉 are associated with the decomposition of *G*_{B} presented in figure 3*b*. Following the procedure described for *Γ*_{1}, above, we obtain the periodic colouring presented in figure 4*b*, which also has the colouring rule *A*.

Using Dias & Pinho (2009, lemma 4.2), it is easy to check that there is no other five-cell network, with colouring rule *A*, whose group of automorphisms has five-order transitive and Abelian subgroups. Again, our main result (theorem 5.2) implies that the colourings in figure 4 are the only periodic colourings of the given lattice network, which have the colouring rule *A* and five cells in the fundamental domain.

## 2. Coupled cell networks and balanced colourings

We will consider the special case of identical-edge homogeneous networks where all the couplings are bidirectional, that is, regular graphs. Thus, although we refer to the general definition of coupled cell networks with a countable number of cells in Antoneli *et al.* (2005), we will use some nomenclature from graph theory.

## Definition 2.1.

An IEHB coupled cell network *G* is a regular graph and consists of

— a countable set of cells, or vertices,

— a countable set of bidirectional arrows, or undirected edges,

— the finite set I(

*c*) of the edges incident with , whose fixed cardinality is called*valence*or degree, v=#I(*c*), for all , and— the finite family V (

*c*) of the cells coupled, or adjacent, to , where repetition of elements is allowed. By (iii) we have #V (*c*)=v, for all .

These networks are denoted by . If is finite and *B* is the adjacency matrix of the graph, then we also use the notation .

## Example 2.2.

The network of figure 1 in §1 is an example of an IEHB network of five cells and valence 4.

We define below a lattice network, which is a particular case of an IEHB coupled cell network, where cells are disposed on a lattice and are coupled to a set of neighbours such that the overall graph structure is invariant by the group of symmetries of the lattice.

An * n-dimensional lattice* is a set , where the

*n*elements

*l*

_{1},…,

*l*

_{n}∈

**R**

^{n}, the

*generators of the lattice*, are linearly independent.

Let |*l*| denote the Euclidean norm of *l*∈**R**^{n}. The countable set of the possible Euclidean distances of to the origin have elements *r*_{0},*r*_{1},*r*_{2},… such that *r*_{0}=0 and *r*_{i}<*r*_{i+1} for all *i*∈**N**.

## Definition 2.3.

Given any , its *nearest neighbours* are indexed by
and form the set . Since and |−*l*|=|*l*|, the nearest neighbours exist in symmetric pairs and is an even number. Therefore, there are elements such that

## Definition 2.4.

An *n*-dimensional lattice is called *Euclidean* if .

If is a Euclidean lattice then we can choose such that . It follows, in particular, the connectedness of the lattice network.

We define an *n*-dimensional lattice network with nearest neighbour coupling architecture, a special case of the definition given by Antoneli *et al.* (2005, definition 2.5) for more general architectures.

## Definition 2.5.

An *n-dimensional lattice network with nearest neighbour coupling architecture* (*NN lattice network*) consists of

— an

*n*-dimensional Euclidean lattice ,— an IEHB coupled cell network whose cells are indexed by , and

— the cells adjacent to any form the set , whose even cardinality—the valence, or degree—is a geometric property of and equals .

## Definition 2.6.

A *coloured coupled cell network*, denoted by , is a coupled cell network , whose cells are coloured with *k* different colours. Let the colours be indexed by the set . The *k-colouring ξ of the network G* is the function
where ξ(*c*) is the colour of cell *c*.

Let be the canonical basis of **R**^{k}. By the isomorphism *i*↔**e**_{i} between and , the above definition of colouring is equivalent to the next one, in vector notation

Unless otherwise stated, all the vectors are column vectors.

Below we present a matrix formulation for the concept of balanced colouring. This is equivalent, for the class of IEHB networks, to the general definition of balanced colouring given by Golubitsky *et al.* (2005, §4).

## Definition 2.7.

Let *A*=(a_{ij}) be a *k*×*k* irreducible matrix with non-negative integer entries and such that, for each row, the entries sum to *v*. Let be a coloured IEHB coupled cell network, with colours indexed by the set . We say that ξ is a *balanced colouring with the k-colouring matrix A* if, for , the following holds: each cell with colour *i* is coupled to a_{ij} cells with colour *j*. Equivalently
For the particular case of an NN lattice network , with nearest neighbours indexed by , the above equation is

When we refer to the adjacency matrix *B* of a network , we are assuming that we have fixed an ordering of the set . Unless otherwise stated, given a *k*-colouring *ξ* of *G*_{B}, with the colours indexed by , we enumerate the cells of by

## Example 2.8.

Figures 1 and 4 show balanced colourings with the three-colouring matrix for three IEHB networks.

## Remark 2.9.

We consider only connected IEHB coloured networks, since the lattice networks are connected (see definitions 2.4 and 2.5) and are related to the finite networks that we deal with. It follows that given any two distinct cells of an IEHB network, there is a path between them. In particular, the colouring matrices considered are irreducible.

### (a) Equivalence classes

Given a *k*-colouring matrix *A*, or colouring rule, the enumeration of different finite coloured networks, and the enumeration of different balanced *k*-colourings of a lattice network, must avoid redundant cases.

### Definition 2.10.

Given a coupled cell network , with *m* cells and with a colouring corresponding to a *k*-colouring matrix *A*, where the set of colours is , we define

is the group of automorphisms of

*G*_{A}, where*G*_{A}denotes a*k*-cell network with adjacency matrix*A*. Thus where*M*_{μ}is the*k*×*k*permutation matrix corresponding to*μ*. If has an ordered set of*k*blocks , where each block contains the*p*_{i}cells with colour*i*, then each element in**P**_{A}is a permutation of blocks with the same size.is the group of permutations leaving invariant the sets of cells with the same colour If each block is an ordered set of

*p*_{i}cells with colour*i*, say, , then**P**_{ξ}*=***S**_{p1}×···×**S**_{pk}and any permutation*τ*=(*τ*_{1},…,*τ*_{k})*∈***P**_{ξ}, with*τ*_{i}*∈***S**_{pi}, is such that , for all .where The second component of permutes elements with the same size in the ordered set of blocks , and the first component permutes cells in each block. This semidirect sum is supported by the isomorphism Aut(

*A*)≅Aut(**P**_{ξ}*).*

Observe that in the definition above: given *μ*∈**P**_{A}, then the colouring *μ*·*ξ* such that (*μ*·*ξ*)(*c*)=*μ*(*ξ*(*c*)), for all , has the same colouring matrix *A* but swaps colours; given *τ*∈**P**_{ξ}, the colouring after permutation *τ* of cells, looks like *ξ*.

In what follows, the set of cells represents any element in the class of sets of cells such that for all . Analogously, the function , with , represents any element in the class [*ξ*] of colourings , such that, for some , we have *ξ*′(*c*)=*ξ*(*λ*·(*c*)) for all . The coloured network , with colouring matrix *A*, represents the networks such that for some .

### (b) Lattice symmetries

Now we consider the classes of colourings of lattice networks that are the same, up to symmetries.

Let be an NN coloured lattice network with *k*-colouring that corresponds to a colouring matrix *A*. Let be the symmetry group of the lattice , where **H** is the holohedry of . We denote the elements in by *γ*=(*t*,*δ*), where *t* is a translation belonging to and *δ* is an orthogonal matrix. Note that *γ*=(*t*,*δ*) transforms *x*∈**R**^{n} into *γ**x*=*t*+*δ**x* and the set is **H**-invariant.

The usual action of on the colourings is the *scalar action*

If then is the colouring after a Euclidean transformation. The function , with , represents any element in the class of colourings , such that for some *μ*∈**P**_{A} and .

### Definition 2.11.

An element is a period of if, for all *,*
The colouring is *periodic* if it has periods along n non-collinear directions. If we denote the set of its periods by
for *n* non-collinear elements , then we also say that is *-periodic.*

### Definition 2.12.

Let be an -periodic colouring with the set of periods and consider the *n*-dimensional parallelepiped . The intersection of this parallelepiped with is a set , isomorphic to the quotient . A *fundamental domain* of the colouring is its restriction to . In fact the colouring is a regular repetition of a fundamental domain, along the n non-collinear directions .

## 3. Results on IEHB networks

Lemma 3.1 presents a summary of results in Dias & Pinho (2009) concerning IEHB coupled cell networks.

## Lemma 3.1.

*Let* *be a finite IEHB coupled cell network with a k-colouring ξ, with colours in* *, and corresponding to a k-colouring matrix A=(a*_{ij}*),* *, with valence v. Let* *and let p*_{i} *be the proportion of cells with colour i, for* *. Then, the following conditions hold.*

*(*Dias & Pinho 2009*, lemma 4.2) The adjacency matrix B of the network has the following block structure:**where, for all*,—

*B*_{ij}*is an mp*_{i}*×mp*_{j}*matrix,*—

*the sum of any row of B*_{ij}*is a*_{ij},—

*, and*—

*the elements in the diagonals of B*_{ii}*are even numbers.*

*(*Dias & Pinho 2009*, lemma 4.3) The vector***p**^{T}*=(p*_{1}*,…,p*_{k}*)∈*[0,1]^{k}*is a left eigenvector of A generating the one-dimensional eigenspace that corresponds to the eigenvalue v, and the entries of A satisfy the condition**It follows, in particular, that there is a minimum number of cells**for the IEHB networks having the k-colouring matrix A. Moreover, this restricts the structure of the matrices that can be k-colouring matrices for IEHB networks.**(*Dias & Pinho 2009*, lemma 4.5) If, moreover, the valence v is even then, for**, there is a set of permutations,**such that B can be written as the sum**where M*_{σ}*denotes the m×m permutation matrix associated to σ∈Σ.*

## Lemma 3.2 *(Converse of item* (*i*) *of lemma 3.1)*.

*If condition (i) of lemma 3.1 holds, then G*_{B} *is an IEHB coupled cell network with a k-colouring ξ corresponding to a k-colouring matrix A=(a*_{ij}*).*

## Proof.

The result is immediate, by Aguiar *et al.* (2009, theorem 3.5). ▪

## Remark 3.3.

The results stated in item (ii) of lemma 3.1, concerning the proportions of colours **p**, are also valid for lattice networks with nearest neighbour coupling architecture (see Dias & Pinho 2009, lemma 4.8). The proportion *p*_{i} of colour is the same in the balanced *k*-colouring of a lattice network or in any other finite IEHB network that shares the same *k*-colouring matrix A. In particular, if is a periodic balanced k-colouring of a lattice network, then the numbers of cells for each colour in its fundamental domain are the components of the vector *m***p** for some *m∈***N**.

## Remark 3.4.

The result stated in item (iii) of lemma 3.1 is a consequence of the result that any finite IEHB network with even valence *v* can be decomposed into *v*/2 bidirectional networks with valence 2. As an example, we show in figure 3 two such decompositions of the network of figure 1.

Lemma 3.1 suggests the following useful definitions.

## Definition 3.5.

Let *A* be a *k*×*k* matrix with even valence *v*. We denote by the set formed by the adjacency matrices of all the finite IEHB networks having the *k*-colouring matrix *A*. Thus, all the elements satisfy conditions (i)–(iii) of lemma 3.1.

Given one matrix , each set of permutations *Σ*, defined in item (iii), is called a *decomposition of B* and we denote by the set of *all* the different decompositions of *B*.

We also define
the set of all the decompositions of all the finite IEHB networks having the *k*-colouring matrix *A*.

Finally, we define , the set of all the decompositions of *B* with commuting permutations, which is a subset of .

## Remark 3.6.

Although one matrix may correspond to several decompositions, that is, , in the converse direction, each defines only one coupled cell network *G*_{B} where . See Dias & Pinho (2009, §4.3) for more considerations on the set .

### (a) Commuting decompositions and group of automorphisms

In the rest of the article, we will be dealing with finite IEHB networks having decompositions with commuting permutations. In this section, we present some results concerning this particular class of networks and we define the subset of the *root networks*, the smallest networks that generate periodic patterns of synchrony, as described in §4.

### Remark 3.7.

Let be a finite IEHB network with a decomposition with commuting permutations, . We consider that the action of 〈*Σ*〉 on is transitive, that is, if then there exists *σ*∈〈*Σ*〉 such that *σ(c)=d*, because the network is connected and bidirectional (see remark 2.9). Moreover, since the group is Abelian it follows that *σ* is unique, the action is regular and .

Let be the group of automorphisms of a finite IEHB network *G*_{B} with *m* cells and adjacency matrix *B*
where *M*_{γ} is the *m*×*m* permutation matrix corresponding to *γ*∈*Γ*.

### Lemma 3.8.

*Let* *be a finite IEHB network with adjacency matrix B having even valence v. For* *, consider a decomposition with commuting permutations* *and let* *be the group of automorphisms of G*_{B}.

*It follows that σ*_{i}*∈ Γ for all σ*

_{i}

*∈Σ and, in particular,*

*. Moreover, for*,

*, all the permutations σ*

_{j}

*∈Σ belong to the group of automorphisms of M*

_{i}.

### Proof.

The last statement holds since, for any ,
if the permutations *σ*_{i} and *σ*_{j} commute.

For the adjacency matrix *B* and for any , we have, by item (iii) of lemma 3.1,
▪

In the next proposition, we use the following notation: if is a finite IEHB coupled cell network, say , and is the group Aut(*G*_{B}), then we denote by the set of all the Abelian subgroups of *Γ* acting transitively on (and so with order *m*).

### Proposition 3.9.

*Let* *be a finite IEHB coupled cell network with* *and* *. Assume that B has even valence. Then there is a one-to-one correspondence between* *, the set of commuting decompositions of G*_{B}*, and*
*where 〈Σ*_{Γi}〉=*Γ*_{i}.

*Moreover, for any λ∈***S**_{m} *and for any* *, we have*
3.1

### Proof.

If and then the *m* commuting permutations *γ*_{1},…,*γ*_{m}∈*Γ*_{i}, defined by the transitive (regular) action of *Γ*_{i} on (as a subset of **R**^{m}), are such that the set of *m*×*m* matrices associated to these permutations, {*M*_{γ1},…,*M*_{γm}}, is a basis for the linear maps from **R**^{m} to **R**^{m} commuting with the natural permutation action of *Γ*_{i} on **R**^{m}.

Thus, since there are *unique* non-negative integers *a*_{1},…,*a*_{m} such that , which defines one decomposition , by lemma 3.1. Since *Σ*_{Γi} includes all the couplings in *Σ* and *G*_{B} has a directed path between any two cells, the group *Σ*_{Γi} must be transitive and, thus, 〈*Σ*_{Γi}〉=*Γ*_{i}.

Using the argument above for the group of automorphisms 〈*Σ*〉={*γ*_{1},…,*γ*_{m}}, we conclude that if 〈*Σ*′〉=〈*Σ*〉 then the sum decomposition of *B* is the same as above and *Σ*′=*Σ*, and so *Ψ* is well defined. Trivially the function is one to one and surjectivity follows from the fact that any defines an element in , since , by lemma 3.8, and (see remark 3.7).

Equation (3.1) is equivalent to
where *Γ*′=〈*Σ*′〉 and *Γ*′′=〈*Σ*′′〉 are elements of . It can be seen immediately that 〈*λ**Σ*′*λ*^{−1}〉=*λ*〈*Σ*′〉*λ*^{−1}. In the converse direction, suppose that 〈*Σ*′′〉=*λ*〈*Σ*′〉*λ*^{−1} for some *λ*∈**S**_{m} and let *σ* be any element in *Σ*′. For any , the cells *c* and *d*=*σ*(*c*) are coupled and, thus, *γ*(*c*) and *γ*(*d*) are also coupled for any *γ*∈*Γ*′′, since . In particular, *γ*=*λ**σ**λ*^{−1} preserves the couplings of the cycle, or the set of cycles, defined by *σ*. Therefore, *λ**Σ*′*λ*^{−1} is a commuting decomposition of *G*_{B} and, by the first statement of this proposition, the only decomposition that generates the group *Γ*′′. ▪

### Definition 3.10.

Let be a finite coloured IEHB coupled cell network with and let be the corresponding group of automorphisms. Assume that *B* has even valence and that *ξ* is a balanced colouring. Let be the set of all the Abelian subgroups of *Γ* acting transitively on (and so with order *m*) and let **P**_{ξ} be the group of permutations acting on that preserve the colours of the cells, following definition 2.10. If and
then we say that *G*_{B} is a *root network*. By the proposition above, we conclude that, for root networks,

### Example 3.11.

In the example of §1a, consider the coloured network *G*_{B} of figure 1 and its corresponding **P**_{ξ}. Since the five-order transitive subgroups of the group of automorphisms of *G*_{B} intersect **P**_{ξ} only in the trivial permutation, *G*_{B} is a root network.

## 4. Balanced colourings in lattices

Let *A* be a *k*-colouring matrix with fixed valence *v*, where *v* is even. For , let (recall definition 3.5). Let be an *n*-dimensional NN lattice network where is a Euclidean lattice with the nearest neighbours indexed by , where *v*/2≥*n*. Suppose that

the permutations commute:

*σ*_{i}○*σ*_{j}=*σ*_{j}○*σ*_{i}for all , where ○ denotes the composition,

and let *ϕ*_{τ} be a function
associated to a permutation *τ* of the elements in , such that the following conditions are verified:

related inverse elements:

*ϕ*_{τ}(*l*_{i})=*σ*_{τ(i)}and for all , andconsistency: for

*v*/2>*n*, if , with , then .

Since the lattice is Euclidean, the set generates the Abelian group that we denote by . Analogously, the set , with commuting permutations (condition (i) above), generates an Abelian group that we denote by 〈*Σ*〉.

## Definition 4.1 (Dias & Pinho 2009).

Let and *Σ* be such that there exists *ϕ≡ϕ*_{τ} satisfying conditions (i)–(iii) above. The function *ϕ* induces the homomorphism
such that *Φ(l)=ϕ(l)* for all . From the definition of *Φ*, it follows that *Φ* is an epimorphism, that is, .

Then we say that and *Σ* are *identifiable* or *identifiable by Φ* and we use the notation
knowing that, for all ,

—

*σ*_{l}*○σ*_{g}*=σ*_{g}*○σ*_{l}*;*—

*;*—

*σ*_{l+g}*=σ*_{l}*○σ*_{g}, if .

The following definitions structure the sets of decompositions according to the property of being identifiable with a given .

## Definition 4.2.

Let be an *n*-dimensional NN lattice network where is a Euclidean lattice with and let *A* be a *k*-colouring matrix. For , we define the set of all the decompositions of *B* that are identifiable with. Thus
If *Σ* and are identifiable by *Φ* then we say that *by Φ*.

Notice that, if *n=v*/2 then for all *B*.

We also define the subset of

## Remark 4.3.

The set has all the decompositions of the coloured network *G*_{B} that generate periodic colourings of , as stated in theorem 4.4. Since is the union of all the sets such that the colouring matrix of *G*_{B} is *A*, it follows that is the set of all the decompositions of finite IEHB networks that generate periodic colourings of with the colouring matrix *A*.

The results of §5 of this paper describe , given and the matrices *A* and . In what follows we use statements from Dias & Pinho (2009, theorems 5.3 and 5.4), as well as some results appearing in the proofs of these theorems. In theorem 4.4, we present these results in a useful way and we establish new properties of the objects involved.

## Theorem 4.4.

*Let* *be an NN Euclidean lattice network and let A be a k×k colouring matrix with valence* .

*There is a periodic balanced colouring* *with the k-colouring matrix A if and only if there is a finite coloured IEHB coupled cell network* *, where ξ is a balanced colouring, having adjacency matrix* *and with a decomposition* *by Φ, such that*
4.1

*where*

*is a function satisfying Π(l+g)=σ*

_{g}

*(Π(l)) where σ*

_{g}

*=Φ(g), for all*.

*Moreover, the set of periods of* *is* *, and Π has set of periods ker(Φ), which verifies* .

## Proof.

First suppose that there is a periodic balanced colouring , with the colouring matrix *A*, and denote by the set of periods of . Then, by the proof of theorem 5.4 in Dias & Pinho (2009), there is a finite IEHB network as described and, in particular, there is one IEHB network with , the number of cells in a fundamental domain of .

Conversely, let be a finite IEHB coupled cell network with a balanced colouring *ξ*, having adjacency matrix and with a decomposition by *Φ*. By Dias & Pinho (2009, theorem 5.3), this ensures the existence of a function with the property *Π*(*l*+*g*)=*σ*_{g}(*Π*(*l*)), where *σ*_{g}=*Φ*(*g*), for all . By the proof of theorem 5.4 in Dias & Pinho (2009), it follows that there is a periodic balanced colouring with the colouring matrix *A* and such that condition (4.1) is verified.

To prove the last statements of the theorem, let . If *t*∈*P*_{Φ}, with *τ*_{t}=*Φ*(*t*)∈**P**_{ξ}, then for any we have
by equation (4.1). Therefore, . Conversely, let and let *τ*_{t}=*Φ*(*t*). Thus , for all , which is equivalent to *ξ*[*τ*_{t}(*Π*(*l*))]=*ξ*(*Π*(*l*)), for all . It follows that *ξ*(*τ*_{t}(*c*))=*ξ*(*c*) for all and, by definition of **P**_{ξ}, *t*∈*P*_{Φ}.

For the function *Π*, let *t*∈ker(*Φ*). Thus *σ*_{t}=*ϵ* and *Π*(*l*+*t*)=*ϵ*(*Π*(*l*))=*Π*(*l*) for all , that is, *t* is a period of the function *Π*. Conversely, let *t* be a period of *Π* with *Φ*(*t*)=*τ*_{t}. For all , we have *Π*(*l*+*t*)=*Π*(*l*) or, equivalently, *τ*_{t}(*Π*(*l*))=*Π*(*l*). Therefore, *τ*_{t}(*c*)=*c* for all and *τ*_{t}=*ϵ*, which implies *t*∈ker(*Φ*). Note that , by the definition of *Φ*, and , since the action of 〈*Σ*〉 on is regular (recall remark 3.7). ▪

### (a) The generating root networks and root decompositions

In theorem 4.4, we construct a periodic balanced colouring of a lattice network from a balanced colouring of a finite IEHB network. If *G*_{B} has *m* cells and is not a root network, then has non-trivial elements and *G*_{B} can give origin, by the decomposition *Σ*, to a periodic balanced colouring of the lattice network with *m*/*r* cells in a fundamental domain, for some *r*∈**N**. However, by the next corollary, the same pattern can be obtained from a root network with *m*/*r* cells.

### Definition 4.5.

Let be an NN Euclidean lattice network and let *A* be a *k×k* colouring matrix with valence . Let be a periodic balanced colouring with the *k*-colouring matrix *A* and consider the notation defined in theorem 4.4. If then we say that *Σ is a root decomposition of* and that the root network *G*_{B}*generates*.

### Corollary 4.6.

*Let* *be an NN Euclidean lattice network and let A be a k×k colouring matrix with valence* *. Every periodic balanced colouring* *, with set of periods* *, can be generated by a root network* *with a root decomposition* *. In this case, the number of cells in a fundamental domain of* *is* .

### Proof.

Let be a periodic balanced colouring, with the colouring matrix *A*, and the set of periods . Then, by the proof of theorem 5.4 in Dias & Pinho (2009), there is a finite IEHB network with a colouring *ξ* and satisfying the conditions of theorem 4.4, such that , the number of cells in a fundamental domain of . We now show that . By definition, and, by theorem 4.4, , which is equal to . Thus, and the result follows. ▪

### Corollary 4.7.

*Let* *be an NN Euclidean lattice network. Let* *be a root network that generates a balanced colouring* *with set of periods* *and consider the notation of theorem 4.4. Then Π has set of periods*

*and, for any set*

*of representatives of the cosets of*

*, we have that*

*, by the isomorphism*

*, and we can define a one-to-one function*

*where*

*for any*

*such that*

*. As a consequence,*4.2

### Proof.

By the proof of corollary 4.6, the function *Π* has the set of periods . Given some let . Thus, there is an such that . We have , which is equivalent to , leading to the result. ▪

Recalling lemma 3.8, we also have the following.

### Corollary 4.8.

*Let* *be an NN Euclidean lattice network. If* *is a root network and generates a periodic balanced colouring* *, then the group of automorphisms of B has an Abelian and transitive subgroup 〈 Σ〉, of order*

*, where*

*is a root decomposition of*.

## 5. Statement of the main results

## Theorem 5.1.

*Let* *be an NN lattice network and let A be a k×k matrix with non-negative entries and valence* *. Let* *and* *be two periodic balanced colourings of the lattice with root decompositions, respectively, Σ and Σ′.*

*The colourings* *and* *are the same up to symmetries*
*if and only if their root decompositions are also the same, up to symmetries*

In what follows we denote by **Z**^{n} the *n*-dimensional lattice generated by the *n* vectors in the canonical basis of **R**^{n}. Note that **Z**^{n} is a Euclidean lattice. For this lattice network, with nearest neighbour coupling architecture, we have *v*/2=*n* and one element, with , is identifiable with if and only if the permutations commute.

We recall the notation used in proposition 3.9: if is a finite IEHB network and *Γ* is the group of automorphisms of *G*_{B}, we denote by the set of all Abelian subgroups of *Γ* acting transitively on .

## Theorem 5.2.

*Let* *be an NN lattice network and let A be a k×k matrix with non-negative entries and valence* *. Let* *be a finite IEHB network with a balanced colouring ξ corresponding to A. Up to symmetries in* *, let r be the number of different groups* *, whose intersection with* **P**_{ξ} *is {ϵ}. Then G*_{B} *generates, at most, r different periodic balanced colourings of* *, that is, colourings that are not the same up to symmetries. These correspond to the root decompositions* *that are also in* *. If* *then G*_{B} *generates exactly r different periodic balanced colourings.*

## Example 5.3.

Returning to the example in §1a, we have the planar square lattice , the colouring rule *A*, given by equation (1.1), and the coloured network *G*_{B}, with valence 4, of figure 1. By theorem 5.2, *G*_{B} generates exactly two periodic colourings in (figure 4), since the number of different elements in is 2.

## 6. Proof of the main results

## Proof of theorem 5.1.

Let and be two periodic balanced colourings of , where . By corollary 4.6, there are root decompositions *Σ* and *Σ*′, corresponding to and , respectively, that are identifiable with . Let *Φ* and *Φ*′ be the underlying homomorphisms, and let *Π* and *Π*′ be the corresponding functions referred to in theorem 4.4.

Suppose that for some *μ*∈**P**_{A} and some . Thus
6.1

First we show that, if is the set of periods of colouring (and of function *Π*, by corollary 4.7), then the periods of (and of function *Π*′, *idem*) form the set . For all and for all , we have , whose right-hand side equals , by equation (6.1), and whose left-hand side equals
This proves the statement on the periods. One consequence is that fundamental domains for both colourings have the same number of cells and, by corollary 4.6, the same holds for corresponding generating root networks. Thus, we can consider generating root networks associated with and having the same set of cells and the same colouring function *ξ*, which defines the group **P**_{ξ}.

Expression (6.1) implies
Using the function defined in corollary 4.7, we have, for all
Therefore, by item (iii) of definition 2.10, there is some *τ*∈**P**_{ξ} such that

For all , we have and, using , with (see corollary 4.7) and the properties of the periods, it follows that

Let *g* be any element of with *σ*_{g}=*Φ*(*g*). Thus, for all , we have *Π*′(*γ*·(*l*+*g*))=*λ*(*Π*(*l*+*g*)), which implies *Π*′(*γ*·*l*+*δ**g*)=(*λ*°*σ*_{g})(*Π*(*l*)). Since *δ* is in the holohedry of , we have and, since *Σ*′ and are identifiable, there is one element *σ*′_{δg}=*Φ*′(*δ**g*)∈*Σ*′. With this notation, the left-hand side of the last expression equals *σ*′_{δg}(*Π*′(*γ*·*l*))=(*σ*′_{δg}°*λ*)(*Π*(*l*)) and, for all , (*σ*′_{δg}°*λ*)(*c*)=(*λ*°*σ*_{g})(*c*), implying *σ*′_{δg}=*λ*°*σ*_{g}°*λ*^{−1} for all

In the converse direction, suppose that *Σ*′=*λ**Σ**λ*^{−1} for some Thus, there is some bijection such that, for all ,
Since *Σ* and *Σ*′ are identifiable with , the conditions in definition 4.1 must be satisfied, ensuring that *T* has a linear extension . Moreover, *δ* is orthogonal, as we now show, implying that *δ*∈**H**, the holohedry of . Let be a set of generators of . Therefore, the set also generates and the determinants of the two matrices whose columns are the generating vectors must verify the equation that proves the orthogonality of *δ*
since both determinants correspond to the oriented *n*-dimensional content, or generalized volume, of the parallelepiped spanned by a set of generating vectors, which is an invariant of the lattice.

Therefore, for all
6.2
Let be such that *Π*′(*t*)=*λ*(*Π*(0)). Therefore, and
▪

## Proof of theorem 5.2.

By proposition 3.9, the enumeration of balanced colourings of the lattice , having *G*_{B} as a generating root network, corresponds to the enumeration of the elements having the property and such that the corresponding decompositions *Σ*_{Γi} belong to . By theorem 5.1, two balanced colourings that are not related by symmetries have different root decompositions, up to symmetries. The result follows, by statement (3.1) of proposition 3.9, ensuring that two root decompositions are related by a symmetry if they generate two subgroups of the automorphism group that are related by the same symmetry. ▪

## Acknowledgements

Research by A.P.S.D. and E.M.P. was supported in part by Centro de Matemática da Universidade do Porto (CMUP) financed by FCT through the programmes POCTI and POSI, with Portuguese and European Community structural funds. E.M.P. was supported by FCT Grant SFRH/BPD/29975/2006.

## Footnotes

- Received July 31, 2009.
- Accepted October 15, 2009.

- © 2009 The Royal Society