Flexible Placements of Periodic Graphs in the Plane

Abstract

Given a periodic graph, we wish to determine via combinatorial methods whether it has periodic embeddings in the plane that—via motions that preserve edge-lengths and periodicity—can be continuously deformed into another non-congruent embedding of the graph. By introducing NBAC-colourings for the corresponding quotient gain graphs, we identify which periodic graphs have flexible embeddings in the plane when the lattice of periodicity is fixed. We further characterise with NBAC-colourings which 1-periodic graphs have flexible embeddings in the plane with a flexible lattice of periodicity, and characterise in special cases which 2-periodic graphs have flexible embeddings in the plane with a flexible lattice of periodicity.

1 Introduction

A (bar-joint) framework in the plane is a pair $({\mathcal {G}},{\mathcal {P}})$, where ${\mathcal {G}}$ is a simple graph and ${\mathcal {P}}$ (the placement of ${\mathcal {G}}$) is a map from $V({\mathcal {G}})$ to ${\mathbb {R}}^2$.¹ By considering each edge vw as a rigid bar that restricts the distance between v and w, a natural question to ask is whether or not the structure is flexible, i.e., does there exist a continuous path in the space of placements of ${\mathcal {G}}$ that preserves the edge distances but is not a rigid body motion? If the vertex set of ${\mathcal {G}}$ is finite and the coordinates of the vector $({\mathcal {P}}(v))_{v\in V({\mathcal {G}})}$ are algebraically independent over ${\mathbb {Q}}$, then it has been proved (first by Pollaczek–Geiringer [18] and later by Laman independently [12]) that $({\mathcal {G}},{\mathcal {P}})$ is rigid (i.e., not flexible) in the plane if and only if ${\mathcal {G}}$ contains a (somewhat erroneously named) Laman graph; a graph ${\mathcal {H}}$ where $|E({\mathcal {H}})|=2|V({\mathcal {H}})|-3$ and $|E({\mathcal {H}}')|\le 2|V({\mathcal {H}}')|-3$ for all subgraphs ${\mathcal {H}}'$ of ${\mathcal {H}}$ with $|V({\mathcal {H}}')|\ge 2$. Given a graph that contains a Laman graph, there can however still exist non-generic placements that are flexible; see Fig. 1.

Fig. 1

(Left): A rigid placement of $K_2\times K_3$ in the plane. As $K_2\times K_3$ is a Laman graph, almost all placements will give a rigid framework. (Right): A flexible placement of the same graph

This raises a new question; can we use combinatorial methods to determine if a graph ${\mathcal {G}}$ has any placement that defines a flexible framework $({\mathcal {G}},{\mathcal {P}})$? This question was answered in the positive in [7], where it was proved that a finite simple graph will have flexible placements in the plane if and only if it has an NAC-colouring, a surjective red-blue edge colouring where no cycle has exactly one red edge or exactly one blue edge. Detecting whether graphs have flexible placements via NAC-colourings is a very recent area of research which utilises many different areas of algebraic geometry, including valuation theory [5,6,7,8].

We now wish to extend the method using NAC-colourings to frameworks in the plane with k-periodic symmetry, i.e., frameworks $({\mathcal {G}},{\mathcal {P}})$ where there exist a matrix $L\in M_{2\times k}({\mathbb {R}})$ and a free group action $\theta$ of ${\mathbb {Z}}^k$ on ${\mathcal {G}}$ via graph automorphisms, such that ${\mathcal {G}}$ has a finite set of vertex orbits under $\theta$ and ${\mathcal {P}}(\theta (\gamma )v)={\mathcal {P}}(v)+L\cdot \gamma$ for all $v\in V(G)$ and $\gamma \in {\mathbb {Z}}^k$; we call L the lattice of ${\mathcal {P}}$, $\theta$ the symmetry of $\mathcal G$, and ${\mathcal {P}}$ a k-periodic placement of $(\mathcal G,\theta )$. Specifically, we wish to be able to determine if a graph ${\mathcal {G}}$ with symmetry $\theta$ has a k-periodic placement ${\mathcal {P}}$ where $({\mathcal {G}},{\mathcal {P}})$ can be deformed by a motion that preserves the periodic structure of $(\mathcal G,{\mathcal {P}})$, and if such a placement does exist, be able to also determine in advance whether the motion will preserve the lattice structure of $({\mathcal {G}},{\mathcal {P}})$.

Research into the rigidity of periodic frameworks has seen much interest in the last decade. Some of the main areas of research include combinatorial characterisations of rigid periodic graphs [2, 3, 13, 16, 21], periodic graphs with unique realisations [11], rigid unit modes of periodic frameworks [17, 19], and rigidity under infinitesimal motions where the periodicity is relaxed somewhat [1, 4, 10, 14, 23].

Each k-periodic framework $({\mathcal {G}},{\mathcal {P}})$ in the plane with a given symmetry $\theta$ defines a family of gain-equivalent triples (G, p, L), where G is a $\mathbb Z^k$-gain graph and $p:V(G)\rightarrow {\mathbb {R}}^2$ is a placement of G (see Sects. 2.2 and 2.3 for definitions), and likewise, each such triple (G, p, L) will define a framework $({\mathcal {G}},{\mathcal {P}})$ with k-periodic symmetry; see [21, Sect. 2.2] for more details. As ${\mathbb {Z}}^k$-gain graphs have a finite amount of vertices but still encode all the required information needed for working with motions that preserve periodicity, we shall define a k-periodic framework in the plane to be a triple (G, p, L) for some ${\mathbb {Z}}^k$-gain graph G, and the pair (p, L) to be a placement-lattice of G; for example, see Fig. 2.

Fig. 2

(Left): A framework $({\mathcal {G}},{\mathcal {P}})$ with 2-periodic symmetry. (Right): A corresponding triple (G, p, L) with $L:=2I_2$, where $I_2$ is the $2\times 2$ identity matrix

Using the gain graph description of k-periodic frameworks, our question is now the following; can we use combinatorial methods to determine if a ${\mathbb {Z}}^k$-gain graph G has any placement-lattice that defines a flexible k-periodic framework (G, p, L)? We shall answer this in the positive for 1-periodic frameworks where the lattice is allowed to deform (see Theorem 5.1) and k-periodic frameworks where the lattice is fixed (see Theorem 4.1). We also obtain partial results for the more difficult case of 2-periodic frameworks where the lattice is allowed to deform (see Lemma 6.4, Theorems 7.5 and 7.10). To do this we shall introduce NBAC-colourings (“NBAC” being an acronym for “No Balanced Almost Circuit”), an analogue of NAC-colourings for ${\mathbb {Z}}^k$-gain graphs. We shall also characterise the various types of NBAC-colourings that are generated by different motions of a given k-periodic framework.

The outline of the paper is as follows. In Sect. 2, we shall layout some background on valuation theory, gain graphs, and periodic frameworks in both ${\mathbb {R}}^d$ and ${\mathbb {C}}^d$. In Sect. 3, we shall define NBAC-colourings and their various sub-types, including active NBAC-colourings, and utilise valuations to prove that flexibility will imply the existence of an NBAC-colouring. In Sects. 4–6, we shall apply our methods using NBAC-colourings to fixed lattice k-periodic frameworks, flexible lattice 1-periodic frameworks, and flexible lattice 2-periodic frameworks respectively, with partial results in the latter case. In Sect. 7, we shall prove that a full characterisation of ${\mathbb {Z}}^2$-gain graphs with a flexible placement-lattice is possible if we assume that our graph has at least a single loop.

2 Preliminaries

2.1 Function Fields and Valuations

We shall refer to all affine algebraic sets over ${\mathbb {C}}$ as algebraic sets, and we shall call any irreducible algebraic set a variety. For an algebraic set V in ${\mathbb {C}}^n$, we define I(V) to be the ideal of ${\mathbb {C}}^n$ that defines V. We recall that the dimension of an algebraic set is the maximal length of chains of distinct nonempty subvarieties of A. An algebraic curve is an affine variety of dimension 1.

Definition 2.1

Let V be a variety in the polynomial ring $\mathbb C[X_1, \ldots ,X_n]$. We define the coordinate ring of V to be the quotient ${\mathbb {C}}[V]:={\mathbb {C}}[X_1, \ldots ,X_n]/I(V)$ and the function field of V to be the field of fractions of ${\mathbb {C}}[V]$, denoted by ${\mathbb {C}}(V)$. Each ${{\hat{f}}}/{{\hat{g}}}\in {\mathbb {C}}(V)$ can, for any $f\in {{\hat{f}}}$ and $g\in {{\hat{g}}}$, be considered to be a partially defined function

$$\begin{aligned} f/g :V \rightarrow {\mathbb {C}},\quad x \mapsto f(x)/g(x), \end{aligned}$$

and this function is independent of the choice of f, g.

We recall that for a field extension K/k, an element $a\in K$ is transcendental over k if there is no polynomial $p\in k[X]$ with $p(a)=0$, and algebraic over k otherwise. The following useful result stems from the observation that any rational function must either be constant on a variety or take an infinite amount of values; indeed if this was not true, we would be able to construct a non-invertible element of the function field.

Lemma 2.2

Let ${\mathcal {C}}$ be an algebraic curve in $\mathbb C[X_1,\ldots ,X_n]$ and let $f\in \mathbb C[x_1,\ldots ,x_n]$. Then one of the following holds:

• (i) f takes an infinite amount of values on ${\mathcal {C}}$ and is transcendental over ${\mathbb {C}}$ when considered as an element of ${\mathbb {C}}({\mathcal {C}})$.

• (ii) f is constant on ${\mathcal {C}}$.

Definition 2.3

For a function field ${\mathbb {C}}(C)$, a function $\nu :\mathbb C(C)\rightarrow {\mathbb {Z}}\cup \{\infty \}$ is a valuation if

• (i) $\nu (x) = \infty$ if and only if $x = 0$;

• (ii) $\nu (xy) = \nu (x) + \nu (y)$;

• (iii) $\nu (x+y)\ge \min {\{\nu (x),\nu (y)\}}$, with equality if $\nu (x) \ne \nu (y)$;

• (iv) $\nu (x) = 0$ if $x \in {\mathbb {C}} \setminus \{0\}$.

The following is a useful rewording of [22, Cor. 1.1.20].

Proposition 2.4

Let ${\mathbb {C}}(C)$ be a function field and suppose $f \in {\mathbb {C}}({\mathcal {C}})$ is transcendental over ${\mathbb {C}}$. Then there exists a valuation $\nu$ of ${\mathbb {C}}({\mathcal {C}})$ with $\nu (f) >0$.

2.2 Gain Graphs

We shall briefly cover the topic of gain graphs. For a more in depth analysis of the topic for general groups, we refer the reader to [9]. We will be mainly be interested in the case when the group is an abelian free group; for more discussion on techniques often used for this specific topic, we refer the reader to [20].

Definition 2.5

A $\Gamma$-gain graph is a triple $G := (V(G),E(G), \Gamma )$, where:

• (i) V(G) is a finite set of vertices.

• (ii) $\Gamma$ is an additive abelian group with identity 0.

• (iii) $K(V(G)) := (V(G)^2\times \Gamma )/R$, where R is the equivalence relation with $(a,b,\gamma )\,R\,(c,d,\mu )$ if and only if either $a=c$, $b=d$, and $\gamma =\mu$, or $a=d$, $b=c$, and $\gamma = -\mu$.

• (iv) $E(G) \subset K(V(G))$ is a set of edges. We shall assume that there is no edge of the form (v, v, 0); we shall, however, allow E(G) to be an infinite set.

While the edges of a gain graph are not orientated, we often find it easier to assume that there is some orientation on the edges, i.e., G is directed. We may then define the gain of an edge $(v,w,\gamma )$ to be $\gamma$. We refer the reader to Fig. 3 for an example.

Fig. 3

A $\Gamma$-gain graph with $a,b,c,d \in \Gamma$. We represent any edge $(v,w,\gamma )$ by an arrow from v to w with a label $\gamma$, and we represent any edge (v, w, 0) by an undirected and unlabelled edge from v to w

A switching operation at u by $\mu$ is the map $\phi _u^\mu :K(V(G)) \rightarrow K(V(G))$ where

$$\begin{aligned} \phi _u^\mu (v,w,\gamma ) ={\left\{ \begin{array}{ll} (u,w, \gamma + \mu ) &{} \text {if } v=u,\ w \ne u,\\ (v,u, \gamma - \mu ) &{} \text {if } v \ne u,\ w = u,\\ (v,w,\gamma ) &{} \text {if } v, w \ne u \text { or } v=w=u. \end{array}\right. } \end{aligned}$$

See Fig. 4 for an example of a gain switching operation at a vertex.

Fig. 4

A switching operation at u by $\mu$

Given the switching operations $\phi _{u_1}^{\mu _1},\ldots ,\phi _{u_n}^{\mu _n}$ (where the vertices $u_1,\ldots ,u_n$ and elements $\mu _1,\ldots ,\mu _n$ need not be distinct), we define $\phi :=\phi _{u_n}^{\mu _n}\circ \cdots \circ \phi _{u_1}^{\mu _1}$ to be a gain equivalence. We say $\Gamma$-gain graphs $G,G'$ are gain-equivalent (or $G\approx G'$) if G and $G'$ are $\Gamma$-gain graphs with the same vertex set and $G'=\phi (G):=(V(G),\phi (E(G)),\Gamma )$ for some gain equivalence $\phi$. If $H\subset G$ and $H':=\phi (H)$, then we say $H'$ is the corresponding subgraph of H in $G'$. The relation $\approx$ is an equivalence relation for gain graphs.

A walk in G is an ordered set $C:=(e_1,\ldots ,e_n)$ of edges of G where $e_i=(v_i,v_{i+1},\gamma _i)$ (with $v_{n+1}=v_1$) for some $\gamma _i$; we note that we orientate each edge so we have a directed walk from $v_1$ to $v_n$. The length of a walk is the amount of edges it contains (including any repetitions). If $v_1 = v_n$ then C is a circuit. Unless specified otherwise, all walks and circuits of length n will be of the form described above. For a circuit C, we define

$$\begin{aligned} \psi (C):=\gamma _1+\gamma _2+\cdots +\gamma _n \end{aligned}$$

to be the gain of C. A circuit is balanced if $\psi (C)=0$, and unbalanced otherwise. For a connected subgraph $H\subset G$, we define the span of H to be the subgroup

$$\begin{aligned} {{\,\mathrm{span}\,}}H:=\{\psi (C):C\text { is a circuit in }H\}. \end{aligned}$$

If $\Gamma \cong {\mathbb {Z}}^k$ for some $k\in {\mathbb {N}}$, then we define ${{\,\mathrm{rank}\,}}H$ to be the rank of ${{\,\mathrm{span}\,}}H$. A connected subgraph H is balanced if ${{\,\mathrm{span}\,}}H$ is the trivial group, and unbalanced otherwise; likewise, a subgraph is balanced if every connected component is balanced and unbalanced otherwise.

Proposition 2.6

Let $G,G'$ be gain-equivalent $\Gamma$-gain graphs and $H\subset G$ be a connected subgraph. If $H'$ is the corresponding subgraph of H in G, then ${{\,\mathrm{span}\,}}H'={{\,\mathrm{span}\,}}H$.

Proof

This follows from noting that switching operations will not change the span of a circuit. $\square$

Proposition 2.7

Let G be a $\Gamma$-gain graph and $\{H_1,\ldots ,H_n\}$ a set of connected subgraphs with pairwise disjoint vertex sets. Then there exists $G'\approx G$ such that for each $i\in \{1,\ldots ,n\}$, all the edges of the corresponding subgraph $H'_i$ of $H_i$ in $G'$ have gain in ${{\,\mathrm{span}\,}}H_i$.

Proof

Choose a spanning tree $T_i$ for each $i\in \{1,\ldots ,n\}$. We note that we may choose $G' \approx G$ so that each corresponding subgraph $T'_i$ of $T_i$ in $G'$ has only trivial gain for its edges; see [21, Sect. 2.4] for a description of the method. Fix $i\in \{1,\ldots ,n\}$ and choose any $e=(v,w,\gamma )\in E(H'_i)$. Let W be the unique walk from w to v in $T_i$, and define C to be the circuit formed by the travelling along the edge e and then following the walk W. As $\psi (C)=\gamma$, then $\gamma \in {{\,\mathrm{span}\,}}H'_i$. By Proposition 2.6, ${{\,\mathrm{span}\,}}H_i={{\,\mathrm{span}\,}}H_i'$, hence $\gamma \in {{\,\mathrm{span}\,}}H_i$ as required. $\square$

2.3 Rigidity and Flexibility for k-Periodic Frameworks

Let $d\in {\mathbb {N}}$ and ${\mathbb {K}}:={\mathbb {R}}$ or ${\mathbb {C}}$. We shall define $\Vert \,{\cdot }\,\Vert ^2 :{\mathbb {K}}^d\rightarrow \mathbb K$ to be the quadratic form with

$$\begin{aligned} \bigl \Vert (x_i)_{i=1}^d \bigr \Vert ^2 := \sum _{i=1}^d x_i^2 \end{aligned}$$

for all $(x_i)_{i=1}^d\in {\mathbb {K}}^d$. For ${\mathbb {K}}={\mathbb {R}}$, the quadratic form $\Vert \,{\cdot }\,\Vert ^2$ is in fact the square of the Euclidean norm, however this is not true for ${\mathbb {K}}={\mathbb {C}}$. The isometries of $({\mathbb {K}}^d,\Vert \,{\cdot }\,\Vert ^2)$ are exactly the affine maps $x\mapsto Mx+y$, where $y\in {\mathbb {K}}^d$ and $M\in M_n({\mathbb {K}})$ is a $d\times d$ matrix where $M^TM=I_d$.

Remark 2.8

For any matrix $M\in M_{m\times n}({\mathbb {K}})$ and $x:=(x_1,\ldots ,x_n)\in {\mathbb {K}}^n$, we shall denote by $M\cdot x$ the matrix multiplication $M[x_1\ldots x_n]^T$.

We shall be using the definition of periodic frameworks, originally stated by Ross, which utilises gain graphs (see [20]), although many of our results can be adapted to fit the terminology used by Borcea and Streinu (see [2]). These two differing definitions can be seen to be identical; we refer the reader to [20, Sect. 3.1] for more details.

Definition 2.9

Let $d\in {\mathbb {N}}$ and G be a ${\mathbb {Z}}^k$-gain graph for some $1\le k\le d$. A k-periodic framework in ${\mathbb {K}}^d$ is a triple (G, p, L) such that G is a ${\mathbb {Z}}^k$-gain graph, $p:V(G)\rightarrow {\mathbb {K}}^d$, and $L\in M_{d\times k}({\mathbb {K}})$, with the assumption that if $(v,w,\gamma )\in E(G)$ then $p(v)\ne p(w)+L\cdot \gamma$. We shall define p to be a placement, L to be a lattice, and the pair (p, L) to be a placement-lattice. If L is also injective then (G, p, L) is full, and if ${\mathbb {K}}={\mathbb {R}}$ then we simply refer to (G, p, L) as a k-periodic framework.

For a given ${\mathbb {Z}}^k$-gain graph G, we define $\mathcal V^d_{{\mathbb {K}}}(G)$ to be the space of placement-lattices of G, which we shall consider to be a subspace of $\mathbb K^{d|V(G)|+dk}$. We immediately note that ${\mathcal {V}}^d_{\mathbb K}(G)$ is an open non-empty subset in the Zariski topology, and if G has an edge, it is a proper subset.

Definition 2.10

Let (G, p, L) and $(G,p',L')$ be k-periodic frameworks in ${\mathbb {K}}^d$. Then $(G,p,L) \sim (G,p',L')$ (or (G, p, L) and $(G,p', L')$ are equivalent) if for all $(v,w,\gamma )\in E(G)$,

$$\begin{aligned} \Vert p(v) - p(w) - L\cdot \gamma \Vert ^2 = \Vert p'(v) - p'(w) - L'\cdot \gamma \Vert ^2, \end{aligned}$$

(1)

and $(p,L)\sim (p',L')$ (or (p, L) and $(p',L')$ are congruent) if (1) holds for all $v,w\in V(G)$ and $\gamma \in {\mathbb {Z}}^k$; equivalently, we may define $(p,L)\sim (p',L')$ if and only if there exist a linear isometry $M\in M_d({\mathbb {K}})$ and $y\in {\mathbb {K}}^d$ such that $p'(v)=M\cdot p(v)+y$ for all $v\in V(G)$ and $L'=ML$. For any $L,L'\in M_{d\times k}({\mathbb {K}})$, we define L and $L'$ to be orthogonally equivalent (or $L\sim L'$) if for any $\gamma ,\mu \in {\mathbb {Z}}^k$,

$$\begin{aligned} (L\cdot \gamma ) \cdot (L\cdot \mu )=(L'\cdot \gamma ) \cdot (L'\cdot \mu ). \end{aligned}$$

(2)

We note that, by linearity, if (2) holds for all pairs of some basis of ${\mathbb {Z}}^k$, then it holds for all $\gamma ,\mu \in {\mathbb {Z}}^k$. Furthermore, if $(p,L) \sim (p',L')$ then $(G,p,L) \sim (G,p',L')$ and $L \sim L'$.

Definition 2.11

For a k-periodic framework (G, p, L) we define the algebraic subsets

$$\begin{aligned} {\mathcal {V}}_{{\mathbb {K}}}(G,p,L)&:=\{ (p',L') \in {\mathcal {V}}^d_{{\mathbb {K}}}(G) : (G,p',L') \sim (G,p,L)\}, \\ {\mathcal {V}}^f_{{\mathbb {K}}}(G,p,L)&:=\{ (p',L') \in {\mathcal {V}}^d_{{\mathbb {K}}}(G) : (G,p',L') \sim (G,p,L),\,L' \sim L\}. \end{aligned}$$

Definition 2.12

Let (G, p, L) be a k-periodic framework in ${\mathbb {K}}^d$. A flex of (G, p, L) is a continuous path $t\mapsto (p_t,L_t)$, $t\in [0,1]$, in ${\mathcal {V}}_{{\mathbb {K}}}(G,p,L)$. If $(p_t,L_t)\in {\mathcal {V}}^f_{{\mathbb {K}}}(G,p,L)$ for all $t\in [0,1]$ then $(p_t,L_t)$ is a fixed lattice flex. If $(p_t,L_t)\sim (p,L)$ for all $t \in [0,1]$ then $(p_t,L_t)$ is trivial.

Remark 2.13

An equivalent definition for a trivial finite flex is as follows: $(p_t,L_t)$ is a trivial flex of (G, p, L) if and only $(p_t,L_t)$ is a trivial flex of (K, p, L), where K is ${\mathbb {Z}}^k$-gain graph with vertex set V(G) and edge set $K(V(G))\setminus \{(v,v,0):v\in V(G)\}$.

Definition 2.14

Let (G, p, L) be a k-periodic framework. Then we define the following:

• (i) (G, p, L) is rigid if all flexes of (G, p, L) are trivial, and flexible otherwise.

• (ii) (G, p, L) is fixed lattice rigid if all fixed lattice flexes of (G, p, L) are trivial, and fixed lattice flexible otherwise.

Let $\phi _u^\mu$ be a switching operation of G. We define the framework switching operation at u by $\mu$ to be (by abuse of notation) the linear map $\phi _u^\mu :\mathbb K^{d|V(G)|+dk}\rightarrow {\mathbb {K}}^{d|V(G)|+dk}$, where, given $(p',L') = \phi _u^\mu (p,L)$, we have $L'=L$ and

$$\begin{aligned} p'(v) ={\left\{ \begin{array}{ll} p(u) + L\cdot \mu &{}\text { if } v=u,\\ p(v) &{}\text { otherwise}, \end{array}\right. } \end{aligned}$$

for all $v\in V^d_{{\mathbb {K}}}(G)$. We define any composition $\phi :=\phi _{u_n}^{\mu _n}\circ \cdots \circ \phi _{u_1}^{\mu _1}$ to be a gain equivalence, and define $\phi (G,p,L):=(\phi _u^\mu (G),\phi _u^\mu (p,L))$. If there exists a gain equivalence such that $(G',p',L)=\phi (G,p,L)$, then we say (G, p, L) and $(G',p',L)$ are gain-equivalent; we denote that two k-periodic frameworks (G, p, L) and $(G',p',L)$ are gain equivalent by $(G,p,L)\approx (G',p',L)$.

As each gain equivalence $\phi$ is a linear isomorphism and $\phi ({\mathcal {V}}^d_{{\mathbb {K}}}(G,p,L))={\mathcal {V}}_{\mathbb K}^d(\phi (G,p,L))$, then the sets ${\mathcal {V}}_{{\mathbb {K}}}(G,p,L)$ and ${\mathcal {V}}_{{\mathbb {K}}}(\phi (G,p,L))$ are isomorphic as algebraic sets. It follows that, given $(G,p,L)\approx (G',p',L)$, we have that (G, p, L) is (fixed lattice) rigid if and only if $(G',p',L)$ is (fixed lattice) rigid.

3 NBAC-Colourings and Flexibility in the Plane

3.1 NBAC-Colourings

Definition 3.1

Let G be a $\Gamma$-gain graph with edge colouring $\delta :E(G) \rightarrow \{\text {red}, \text {blue}\}$. We define the following:

• (i) $G^\delta _{red }:=(V(G),\{e\in E(G):\delta (e)=red \})$.

• (ii) A red component is a connected component of $G^\delta _{red }$.

• (iii) A red walk (respectively, red circuit) is a walk (respectively, circuit) where every edge is red.

• (iv) An almost red circuit is a circuit with exactly one blue edge.

• (v) $G^\delta _{blue }$, blue components, blue walks, blue circuits, and almost blue circuits are defined analogously.

• (vi) We define a component/walk/circuit to be monochromatic if it is either red or blue, and we define an almost monochromatic circuit to be any circuit that is either almost red or almost blue.

A colouring $\delta$ is an NBAC-colouring (No Balanced Almost Circuits) if it is surjective, and there are no balanced almost red circuits and no balanced almost blue circuits; see Fig. 5 for an example of an NBAC-colouring.

Fig. 5

A surjective colouring $\delta$ of a $\Gamma$-gain graph. If $\alpha \notin \langle \beta \rangle$, $\beta \notin \langle \alpha -\gamma \rangle$, and $\gamma \ne 0$, then $\delta$ is an NBAC-colouring

If $\delta$ is a colouring of G and $G'\approx G$, then by abuse of notation we shall also define $\delta$ to be a colouring for $G'$. We note that if $\delta$ is an NBAC-colouring of G, then $\delta$ is an NBAC-colouring of $G'$.

Definition 3.2

Let G be a ${\mathbb {Z}}^k$-gain graph for some $k\in \{1,2\}$, with an NBAC-colouring $\delta$. If either $G^\delta _{red }$ is balanced and G has no almost blue circuits, or $G^\delta _{blue }$ is balanced and G has no almost red circuits, then $\delta$ is a fixed lattice NBAC-colouring.

Definition 3.3

Let G be a ${\mathbb {Z}}$-gain graph with an NBAC-colouring $\delta$. If both $G^\delta _{red }$ and $G^\delta _{blue }$ are balanced, then $\delta$ is a flexible 1-lattice NBAC-colouring.

Remark 3.4

We note that if G is a ${\mathbb {Z}}$-gain graph with NBAC-colouring $\delta$, then $\delta$ can be either both a fixed lattice NBAC-colouring and a flexible 1-lattice NBAC-colouring, one or the other, or neither. We can even have that G has no NBAC-colouring that is both, but has both fixed lattice and flexible 1-lattice NBAC-colourings; see Fig. 6 for an example.

Fig. 6

All three possible NBAC-colourings of a ${\mathbb {Z}}$-gain graph up to switching the colours red and blue. The left is a fixed lattice NBAC-colouring but not a flexible 1-lattice NBAC-colouring, while the middle and right are flexible 1-lattice NBAC-colourings but not fixed lattice NBAC-colourings

Definition 3.5

Let G be a ${\mathbb {Z}}^2$-gain graph with an NBAC-colouring $\delta$. We define the following (see Fig. 7 for examples of each colouring):

• (i) If both $G^\delta _{red }$ and $G^\delta _{blue }$ are balanced, then $\delta$ is a type 1 flexible 2-lattice NBAC-colouring.

• (ii) If there exist $\alpha ,\beta \in {\mathbb {Z}}^2$ such that

  • either $\alpha ,\beta$ are linearly independent or exactly one of $\alpha ,\beta$ is equal to (0, 0),

  • ${{\,\mathrm{span}\,}}G^\delta _red$ is a non-trivial subgroup of ${\mathbb {Z}}\alpha$, or $\alpha =(0,0)$ and $G^\delta _red$ is balanced,

  • ${{\,\mathrm{span}\,}}G^\delta _blue$ is a non-trivial subgroup of ${\mathbb {Z}}\beta$, or $\beta =(0,0)$ and $G^\delta _blue$ is balanced,

  • there are no almost red circuits with gain in ${\mathbb {Z}}\alpha$, and

  • there are no almost blue circuits with gain in ${\mathbb {Z}}\beta$,

  then $\delta$ is a type 2 flexible 2-lattice NBAC-colouring.

• (iii) If there exists $\alpha \in {\mathbb {Z}}^2 \setminus \{(0,0)\}$ such that

  • ${{\,\mathrm{span}\,}}G^\delta _red$ and ${{\,\mathrm{span}\,}}G^\delta _red$ are non-trivial subgroups of ${\mathbb {Z}}\alpha$, and

  • there are no almost monochromatic circuits with gain in ${\mathbb {Z}}\alpha$,

  then $\delta$ is a type 3 flexible 2-lattice NBAC-colouring; see Fig. 7.

Fig. 7

(Left): A ${\mathbb {Z}}^2$-gain graph with a type 1 flexible 2-lattice NBAC-colouring. (Middle): A ${\mathbb {Z}}^2$-gain graph with a type 2 flexible 2-lattice NBAC-colouring ($\alpha =(1,0)$, $\beta =(0,1)$). (Right): A ${\mathbb {Z}}^2$-gain graph with a type 3 flexible 2-lattice NBAC-colouring ($\alpha =(1,0)$)

Remark 3.6

We note that if G is a ${\mathbb {Z}}^2$-gain graph with NBAC-colouring $\delta$, then the following holds:

• For distinct $i,j \in \{1,2,3\}$, $\delta$ cannot be both a type i and type j flexible 2-lattice NBAC-colouring.

• Similarly, $\delta$ cannot be both a fixed lattice NBAC-colouring and type 3 flexible 2-lattice NBAC-colouring.

• The colouring $\delta$ can, however, be both a fixed lattice NBAC-colouring and either a type 1 or 2 flexible 2-lattice NBAC-colouring; see Fig. 8 for an example of an NBAC-colouring that is both fixed lattice and type 2.

• If $H\subset G$ is not monochromatic and $\delta$ is a type k flexible 2-lattice NBAC-colouring for some $k\in \{1,2,3\}$, then $\delta$ restricted to H is a type $k'$ flexible 2-lattice NBAC-colouring for some $1\le k'\le k$; furthermore, if $k'=1<k$ then $\delta$ restricted to H will also be a fixed lattice NBAC-colouring.

Fig. 8

A ${\mathbb {Z}}^2$-gain graph with a colouring that is both a fixed lattice NBAC-colouring and a type 2 flexible 2-lattice NBAC-colouring ($\alpha =(1,0)$, $\beta =(0,0)$)

3.2 k-Periodic Frameworks in the Plane

Let G be a ${\mathbb {Z}}^k$-gain graph for $k\in \{1,2\}$, with placement $p:V(G)\rightarrow {\mathbb {R}}^2$ and lattice $L\in M_{2\times k}({\mathbb {R}})$; if $k=1$ we shall define $L_1:=L\cdot 1$ and if $k=2$ we shall define $L_1:=L\cdot (1,0)$ and $L_2:=L\cdot (0,1)$. For each $e=(v,w,\gamma )$ with $\gamma :=(\gamma _j)_{j=1}^k$, we define

$$\begin{aligned} \lambda (e):=\left\| p(v)-p(w)-\sum _{j=1}^k\gamma _jL_j\right\| \end{aligned}$$

(we note that this is well defined as (G, p, L) is a k-periodic framework in ${\mathbb {R}}^2$). We further define for each $1 \le j,l \le k$,

$$\begin{aligned} \lambda (j,l):=L_j\cdot L_l. \end{aligned}$$

We shall consider each point $(q,M)\in {\mathcal {V}}_{{\mathbb {C}}}^2(G)$ to be a point

$$\begin{aligned} \bigl ((x_v,y_v)_{v\in V(G)},(x_j,y_j)_{j=1}^k\bigr ), \end{aligned}$$

where $x_v,y_v,x_j,y_j\in {\mathbb {C}}$; the points $(x_v,y_v)$ will correspond to the coordinates of $q_v$, and the points $(x_j,y_j)$ will correspond to the coordinates of $L_j$. To help simplify things later on, we will first wish to quotient out ${\mathcal {V}}_{\mathbb C}^2(G)$ by the orientation-preserving isometries by fixing an edge ${{\tilde{e}}}=({{\tilde{v}}},{{\tilde{w}}},{\tilde{\gamma }})$. To do so, we define the algebraic set ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)\subset {\mathcal {V}}_{{\mathbb {C}}}^2(G)$ of all points where

$$\begin{aligned} x_{{{\tilde{v}}}}=y_{{{\tilde{v}}}}=0,\qquad y_{{{\tilde{w}}}}+\sum _{j=1}^k\tilde{\gamma }_jy_j=0, \end{aligned}$$

and for all $e=(v,w,\gamma )\in E(G)$,

$$\begin{aligned} \left( x_v- x_w - \sum _{j=1}^k \gamma _j x_j \right) ^{\!2}\!+\left( y_v-y_w-\sum _{j=1}^k\gamma _jy_j\right) ^{\!2}\!=\lambda (e)^2. \end{aligned}$$

(3)

We further define ${\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$ to be the algebraic subset of ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ where $x_jx_l+y_jy_l=\lambda (j,l)^2$, for each $1\le j,l\le k$.

We note that the placement-lattice (p, L) may not be contained in ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$. However, the unique k-periodic framework obtained by translating and rotating (G, p, L) so that $p_{{{\tilde{v}}}}$ lies at the origin and $p_{{{\tilde{w}}}}+L\cdot {\tilde{\gamma }}$ lies on the x-axis, will be contained in ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$. Hence, the set ${\mathcal {V}}_{\mathbb C}(G,p,L)$ is homeomorphic to

$$\begin{aligned} {\mathcal {V}}_{{\tilde{e}}}(G,p,L)\times SO (2,{\mathbb {C}})\times {\mathbb {C}}^2 \end{aligned}$$

as ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ is the set of frameworks equivalent to (G, p, L) in ${\mathbb {C}}^2$ where the edge ${\tilde{e}}$ is fixed to lie on the x-axis. Similarly, ${\mathcal {V}}^f_{{\mathbb {C}}}(G,p,L)$ is homeomorphic to

$$\begin{aligned} {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)\times SO (2,{\mathbb {C}})\times {\mathbb {C}}^2. \end{aligned}$$

It follows that, if we require it, we may assume $(p,L)\in {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$.

Given an algebraic curve ${\mathcal {C}} \subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ and any $v,w \in V(G)$, $\gamma \in {\mathbb {Z}}^k$, we define the maps

$$\begin{aligned} W^\gamma _{v,w,}|_{\mathcal {C}},Z^\gamma _{v,w}|_{\mathcal {C}} :\,{\mathcal {C}} \rightarrow {\mathbb {C}} \end{aligned}$$

by the polynomials

$$\begin{aligned} W^\gamma _{v,w} |_{\mathcal {C}}&:=\left( x_v-x_w-\sum _{j=1}^k\gamma _jx_j\right) +i\left( y_v-y_w-\sum _{j=1}^k\gamma _jy_j\right) , \\ Z^\gamma _{v,w} |_{\mathcal {C}}&:=\left( x_v-x_w-\sum _{j=1}^k\gamma _jx_j\right) -i\left( y_v-y_w-\sum _{j=1}^k\gamma _j y_j \right) . \end{aligned}$$

We further define the maps $W_j|_{{\mathcal {C}}},Z_j|_{{\mathcal {C}}} :{\mathcal {C}} \rightarrow {\mathbb {C}}$ for $1 \le j \le k$ as the polynomials

$$\begin{aligned} W_j|_{\mathcal {C}}:=x_j+iy_j,\qquad Z_j|_{\mathcal {C}}:=x_j-iy_j. \end{aligned}$$

For the case of $k=2$, we shall define for each $\gamma :=(a,b)\in {\mathbb {Z}}^2$ the maps

$$\begin{aligned} \gamma W|_{{\mathcal {C}}}:=aW_1|_{{\mathcal {C}}}+bW_2|_{{\mathcal {C}}},\qquad \gamma Z|_{{\mathcal {C}}}:=aZ_1|_{{\mathcal {C}}}+bZ_2|_{{\mathcal {C}}}. \end{aligned}$$

When there is no ambiguity regarding which algebraic curve we are observing, we shall for brevity drop the notation “$|_{\mathcal {C}}$”; for example, $W^\gamma _{v,w}|_{\mathcal {C}}$ shall be shortened to $W^\gamma _{v,w}$.

We first observe that $W^{-\gamma }_{w,v}=-W^\gamma _{v,w}$ and $Z^{-\gamma }_{w,v}=-Z^\gamma _{v,w}$. Furthermore, we note that if $e=(v,w,\gamma )\in E(G)$,

$$\begin{aligned} W^\gamma _{v,w} Z^\gamma _{v,w} = \lambda (e)^2, \end{aligned}$$

and if ${\mathcal {C}} \subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$ then

$$\begin{aligned} W_j\cdot Z_j = \lambda (j,j)^2 , \qquad W_j \cdot Z_l + W_l\cdot Z_j = 2\lambda (j,l)^2, \end{aligned}$$

for all $1 \le j,l \le k$.

3.3 Active NBAC-Colourings

Active NAC-colourings for finite simple graphs were first introduced in [8]. We shall now give an analogue of them for ${\mathbb {Z}}^k$-gain graphs.

Definition 3.7

Let (G, p, L) be a k-periodic framework in ${\mathbb {R}}^2$, $\mathcal C\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ be an algebraic curve, and $\delta$ an NBAC-colouring of G. We define $\delta$ to be an active NBAC-colouring of ${\mathcal {C}}$ if there exist a valuation $\nu$ of $\mathbb C({\mathcal {C}})$ and $\alpha \in {\mathbb {R}}$ such that for each $e\in E(G)$,

$$\begin{aligned} \delta (e)={\left\{ \begin{array}{ll} red &{}\text { if } \nu (W^\gamma _{v,w}) > \alpha , \\ blue &{}\text { if } \nu (W^\gamma _{v,w}) \le \alpha ; \end{array}\right. } \end{aligned}$$

if this is the case, we shall say that $\delta$ is the NBAC-colouring generated by $\nu$ and $\alpha$. For a k-periodic framework (G, p, L) in ${\mathbb {R}}^2$, we define $\delta$ to be an active NBAC-colouring of (G, p, L) if it is an active NBAC-colouring of an algebraic curve $\mathcal C\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$. We define $\delta$ to be an active NBAC-colouring of G if it is an active NBAC-colouring of a full k-periodic framework (G, p, L) in ${\mathbb {R}}^2$.

Remark 3.8

If $\delta$ is an active NBAC-colouring of an algebraic curve ${\mathcal {C}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ and $\delta '$ is an NBAC-colouring with $\delta '(e)\ne \delta (e)$ for all $e\in E(G)$, then $\delta '$ is also an active NBAC-colouring of ${\mathcal {C}}$; this can be shown in a similar way to the proof of [8, Lem. 1.13].

Lemma 3.9

Let (G, p, L) be a k-periodic framework in ${\mathbb {R}}^2$ and $e_1,e_2\in E(G)$, with $e_1=(v_1,w_1,\gamma _1)$ and $e_2=(v_2,w_2,\gamma _2)$. Then the map

$$\begin{aligned}&f_{e_1,e_2}:{\mathcal {V}}_{e_1}(G,p,L)\rightarrow {\mathcal {V}}_{e_2}(G,p,L),\\&\quad (q,M)\mapsto \bigl ((R_{e_2}\cdot (q(v) - q(v_2)))_{v\in V(G)},R_{e_2}M\bigr ) \end{aligned}$$

is biregular, where

$$\begin{aligned} R_{e_2}:=\frac{1}{\lambda (e_2)}\begin{bmatrix} x_{w_2} - x_{v_2}&y_{w_2} - y_{v_2}{} y_{w_2} - y_{v_2})&x_{w_2} - x_{v_2} \end{bmatrix}. \end{aligned}$$

Furthermore, for any algebraic curve ${\mathcal {C}} \subset {\mathcal {V}}_{e_1}(G,p,L)$ and any $v,w \in V(G)$, $\gamma \in {\mathbb {Z}}^k$, we have that ${\mathcal {C}}' := f_{e_1,e_2}({\mathcal {C}})$ is an algebraic curve and

$$\begin{aligned} \begin{aligned} W_{v,w}^{\gamma }|_{{\mathcal {C}}'} \circ f_{e_1,e_2}&= \frac{1}{\lambda (e_2)}W_{v,w}^{\gamma }|_{{\mathcal {C}}}\,Z_{v_2,w_2}^{\gamma _2}|_{{\mathcal {C}}},\\ Z_{v,w}^{\gamma }|_{{\mathcal {C}}'} \circ f_{e_1,e_2}&=\frac{1}{\lambda (e_2)}Z_{v,w}^{\gamma }|_{{\mathcal {C}}}\,W_{v_2,w_2}^{\gamma _2}|_{{\mathcal {C}}}. \end{aligned} \end{aligned}$$

(4)

Proof

We note that the transform $z\mapsto R_{e_2}\cdot (z-q(v_2))$ will preserve distance under $\Vert \,{\cdot }\,\Vert ^2$ in ${\mathbb {C}}^2$. It follows that $(G,f_{e_1,e_2}(q,M))$ will be an equivalent framework to (G, q, M), except now the edge $e_2$ (not $e_1$) has been fixed, with $v_2$ at the origin and $w_2$ on the y-axis, Hence $f_{e_1,e_2}(q,M)\in {\mathcal {V}}_{e_2}(G,p,L)$ for all $(q,M)\in {\mathcal {V}}_{e_1}(G,p,L)$, i.e., the map $f_{e_1,e_2}$ is well defined. It is clear that the map $f_{e_1,e_2}$ is regular. To see that $f_{e_1,e_2}$ is biregular, we note that the map $f_{e_2,e_1}$ is the inverse of $f_{e_1,e_2}$. Since $f_{e_1,e_2}$ is biregular, ${\mathcal {C}}'$ will be an algebraic curve. Equation (4) now holds by direct computation. $\square$

Proposition 3.10

Let (G, p, L) be a k-periodic framework in ${\mathbb {R}}^2$, $e_1,e_2\in E(G)$ with $e_1=(v_1,w_1,\gamma _1)$ and $e_2=(v_2,w_2,\gamma _2)$, and $\mathcal C\subset {\mathcal {V}}_{e_1}(G,p,L)$. If $\delta$ is an active NBAC-colouring of ${\mathcal {C}}$ then there exists an algebraic curve ${\mathcal {C}}'\subset {\mathcal {V}}_{e_2}(G,p,L)$ such that $\delta$ is an active NBAC-colouring of ${\mathcal {C}}'$.

Proof

Let ${\mathcal {C}}':= f_{e_1,e_2}({\mathcal {C}})$, where $f_{e_1,e_2}$ is the map defined in Lemma 3.9. Let $\nu$ be the valuation of ${\mathbb {C}}({\mathcal {C}})$ and $\alpha \in {\mathbb {R}}$ be chosen so that they generate $\delta$. Define $\nu '$ to be the valuation of ${\mathbb {C}}({\mathcal {C}}')$ where $\nu '(f) := \nu (f \circ f_{e_1,e_2})$ for each $f \in {\mathbb {C}}({\mathcal {C}}')$. By Lemma 3.9,

$$\begin{aligned} \nu '\bigl ( W_{v,w}^{\gamma }|_{{\mathcal {C}}'}\bigr )&\!\!=\nu \bigl (W_{v,w}^{\gamma }|_{{\mathcal {C}}'}\circ f_{e_1,e_2}\bigr )=\nu \biggl (\frac{1}{\lambda (e_2)}W_{v,w}^{\gamma }|_{{\mathcal {C}}}\,Z_{v_2,w_2}^{\gamma _2}|_{{\mathcal {C}}}\biggr )\\&\!\!=\nu \bigl (W_{v,w}^{\gamma }|_{{\mathcal {C}}} \bigr ) + \nu \bigl ( Z_{v_2,w_2}^{\gamma _2}|_{{\mathcal {C}}} \bigr ). \end{aligned}$$

If we define $\alpha ' := \alpha + \nu \bigl ( Z_{v_2,w_2}^{\gamma _2}|_{{\mathcal {C}}} \bigr )$, then $\nu '$ and $\alpha '$ will generate $\delta$. $\square$

Lemma 3.11

Let (G, p, L) and $(G',p',L)$ be gain equivalent frameworks with gain equivalence $\phi :{\mathcal {V}}^d_{{\mathbb {K}}}(G)\rightarrow \mathcal V^d_{{\mathbb {K}}}(G')$. If ${{\tilde{e}}}\in E(G)$ and ${\tilde{e}}' := \phi ({\tilde{e}})$, then $\phi$ is a biregular map with $\phi ({\mathcal {V}}_{{\tilde{e}}}(G,p,L))={\mathcal {V}}_{{\tilde{e}}'}(G',p',L)$. Furthermore, for any algebraic curve ${\mathcal {C}} \subset {\mathcal {V}}_{e_1}(G,p,L)$ and any $v,w \in V(G)$, $\gamma \in {\mathbb {Z}}^k$, we have that ${\mathcal {C}}' := \phi ({\mathcal {C}})$ is an algebraic curve and

$$\begin{aligned} W_{v,w}^{\gamma }|_{{\mathcal {C}}'} \circ \phi =W_{v,w}^{\gamma }|_{{\mathcal {C}}}, \qquad Z_{v,w}^{\gamma }|_{{\mathcal {C}}'} \circ \phi =Z_{v,w}^{\gamma }|_{{\mathcal {C}}}. \end{aligned}$$

(5)

Proof

As $\phi$ is a bijective map that is the restriction of an invertible linear map, it is a biregular map; hence, $\phi ({\mathcal {C}})$ is an algebraic curve. Equation (5) now follows by direct computation. $\square$

Proposition 3.12

Let G and $G'$ be gain equivalent ${\mathbb {Z}}^k$-gain graphs. Then $\delta$ is an active NBAC-colouring of G if and only if $\delta$ is an active NBAC-colouring of $G'$.

Proof

Let $\delta$ be an active NBAC-colouring of ${\mathcal {C}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ generated by the valuation $\nu$ of ${\mathbb {C}}({\mathcal {C}})$ and $\alpha \in {\mathbb {R}}$. Let $\phi$ be the gain equivalence from G to $G'$. We define the gain equivalent framework $(G',p',L):=\phi (G,p,L)$, the algebraic curve $\mathcal C':=\phi ({\mathcal {C}})$ (Lemma 3.11), and the valuation $\nu '$ of ${\mathbb {C}}({\mathcal {C}}')$ where $\nu '(f):=\nu (f\circ \phi )$ for each $f \in {\mathbb {C}}({\mathcal {C}}')$. By Lemma 3.11,

$$\begin{aligned} \nu '\bigl (W_{v,w}^{\gamma }|_{{\mathcal {C}}'}\bigr )=\nu \bigl (W_{v,w}^\gamma |_{{\mathcal {C}}'}\circ \phi \bigr )=\nu \bigl (W_{v,w}^\gamma |_{{\mathcal {C}}}\bigr ), \end{aligned}$$

thus $\nu '$ and $\alpha$ generate $\delta$ for $G'$. $\square$

3.4 Key Tools

We are now ready to outline the key tools that shall help us throughout the rest of the paper.

Lemma 3.13

Let (G, p, L) be a k-periodic framework in ${\mathbb {R}}^2$. Then the following holds:

• (i) If (G, p, L) is flexible, there exists an algebraic curve ${\mathcal {C}} \subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$.

• (ii) If (G, p, L) is fixed lattice flexible, there exists an algebraic curve ${\mathcal {C}} \subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$.

Proof

(i): If (G, p) is flexible then ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ cannot be finite. As every algebraic set that is not finite contains a variety with positive dimension and every variety with positive dimension contains an algebraic curve, the result holds. (ii): This follows by a similar method. $\square$

Lemma 3.14

Let (G, p, L) be k-periodic and ${\mathcal {C}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ be an algebraic curve. Suppose G contains a spanning tree T that contains ${{\tilde{e}}}$ and has trivial gain for all of its edges. If ${{\,\mathrm{rank}\,}}G=k$, then there exists $(v,w,\gamma )\in E(G)$ such that $W^\gamma _{v,w}$ takes an infinite amount of values on ${\mathcal {C}}$.

Proof

Suppose that for each $(v,w,\gamma )\in E(G)$, the map $W^\gamma _{v,w}$ takes a finite amount of values. By Lemma 2.2, each map $W^\gamma _{v,w}$ is constant. As $W^\gamma _{v,w}Z^\gamma _{v,w}$ is constant, $Z^\gamma _{v,w}$ is also constant. Choose any two vertices $v,w\in V(G)$ with $v\ne w$. Then there exists a unique walk $v_1,\ldots ,v_n$ from v to w in T. As

$$\begin{aligned} W^0_{v,w} = \sum _{j=1}^{n-1} W^0_{v_j,v_{j+1}}, \qquad Z^0_{v,w} = \sum _{j=1}^{n-1} Z^0_{v_j,v_{j+1}}, \end{aligned}$$

both $W^0_{v,w}$ and $Z^0_{v,w}$ are constant; furthermore, as

$$\begin{aligned} x_v - x_w = \frac{1}{2}(W^0_{v,w}+Z^0_{v,w}), \qquad y_v - y_w= \frac{i}{2}(Z^0_{v,w} - W^0_{v,w}), \end{aligned}$$

then $x_v-x_w$ and $y_v-y_w$ are also constant on ${\mathcal {C}}$. Since $x_{{\tilde{v}}},y_{{\tilde{w}}},x_{{\tilde{w}}},y_{{\tilde{v}}}$ are constant on ${\mathcal {C}}$ and both ${\tilde{v}}$ and ${\tilde{w}}$ are contained in T, both $x_v,y_v$ are constant on ${\mathcal {C}}$ for every $v \in V$ also.

Suppose $k=1$ and let $e = (v,w, \gamma )$ be any edge with $\gamma \ne 0$. By observing the maps $W^\gamma _{v,w}$ and $Z^\gamma _{v,w}$, we note that $x_1$ and $y_1$ are constant on ${\mathcal {C}}$ (since $x_v,x_w,y_v,y_w$ are all constant on ${\mathcal {C}}$). It now follows that ${\mathcal {C}}$ is a single point, contradicting that $\dim {\mathcal {C}}>0$.

Now suppose $k=2$. As ${{\,\mathrm{rank}\,}}G=k$, there exist edges $(v,w, \gamma )$ and $(v',w',\gamma ')$ such that $\gamma ,\gamma '$ are independent. By observing the maps $W^\gamma _{v,w},Z^\gamma _{v,w},W^{\gamma '}_{v',w'}, Z^{\gamma '}_{v',w'}$, we note that the polynomials

$$\begin{aligned} \begin{array}{cccc} f &{}:=\gamma _1 x_1 + \gamma _2 x_2, &{}\qquad g&{}\,:= \gamma _1 y_1 + \gamma _2 y_2,\\ f'&{}:=\gamma '_1 x_1 + \gamma '_2 x_2,&{}\qquad g'&{}:= \gamma '_1 y_1 + \gamma '_2 y_2 \end{array} \end{aligned}$$

are constant on ${\mathcal {C}}$. As both $x_1$ and $x_2$ can be formed by linear combinations of $f,f'$, both are constant on ${\mathcal {C}}$; similarly, as both $y_1$ and $y_2$ can be formed by linear combinations of $g,g'$ then both $y_1$ and $y_2$ are also constant on ${\mathcal {C}}$. It now follows that ${\mathcal {C}}$ is a single point, contradicting that $\dim {\mathcal {C}} >0$. $\square$

Lemma 3.15

Let (G, p, L) be a full k-periodic framework in ${\mathbb {R}}^2$, ${{\,\mathrm{rank}\,}}G=k$ for $k\in \{1,2\}$, and ${\mathcal {C}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ be an algebraic curve. Suppose there exists $a:=(a_1,a_2,\alpha )\in E(G)$ such that $W^\alpha _{a_1,a_2}$ takes an infinite amount of values on ${\mathcal {C}}$. Then there exists a valuation $\nu$ of ${\mathbb {C}}({\mathcal {C}})$ such that the colouring $\delta :E(G) \rightarrow \{\text {red}, \text {blue} \}$ given by

$$\begin{aligned} \delta (e) :={\left\{ \begin{array}{ll} \text {red} &{}\text { if } \nu (W^\gamma _{v,w}) >0, \\ \text {blue} &{}\text { if } \nu (W^\gamma _{v,w}) \le 0, \end{array}\right. } \end{aligned}$$

for each $e = (v,w,\gamma )$, is an NBAC-colouring of G; furthermore, $\delta ({\tilde{e}}) = \text {blue}$ and $\delta (a) = \text {red}$.

Proof

By Lemma 2.2, $W^\alpha _{a_1,a_2}$ is transcendental over ${\mathbb {C}}$, thus, by Proposition 2.4, there exists a valuation $\nu$ of ${\mathbb {C}}({\mathcal {C}})$ such that $\nu (W^\alpha _{a_1,a_2})>0$. As ${{\tilde{e}}}$ is fixed and $\lambda ({{\tilde{e}}})\ne 0$, we have $\nu \bigl (W^{\tilde{\gamma }}_{{{\tilde{v}}},{{\tilde{w}}}}\bigr ) =0$. We note that $\nu \bigl (W^\gamma _{v,w}Z^\gamma _{v,w}\bigr )=0$ for each $(v,w,\gamma )\in E(G)$ since $W^\gamma _{v,w}Z^\gamma _{v,w}$ is constant, hence $\nu (W^\gamma _{v,w})=-\nu (Z^\gamma _{v,w})$.

Let $\delta :E(G)\rightarrow \{\text {red},\text {blue}\}$ be as described in the statement of the lemma for the valuation $\nu$. It follows that a is red and ${{\tilde{e}}}$ is blue, thus $\delta$ is surjective. Suppose there exists a balanced almost red circuit C of length n in G with $\delta (e_n)=\text {blue}$. Then

$$\begin{aligned} \nu (W^{\gamma _n}_{v_1,v_n})= \nu \!\left( \sum _{j=1}^{n-1} W^{\gamma _j}_{v_j,v_{j+1}} \right) \ge \min {\bigl \{\nu \bigl (W^{\gamma _j}_{v_j,v_{j+1}}\bigr ): j=1,\ldots , n-1 \bigr \}}>0, \end{aligned}$$

however this contradicts that $\nu \bigl (W^{\gamma _n}_{v_1,v_n}\bigr )\le 0$. Now suppose instead that C is a balanced almost blue circuit with $\delta (e_n)=\text {red}$. Then

$$\begin{aligned} \nu \bigl (Z^{\gamma _n}_{v_1,v_{n}}\bigr )= \nu \!\left( \sum _{j=1}^{n-1} Z^{\gamma _j}_{v_j,v_{j+1}} \right) \ge \min {\bigl \{\nu \bigl (Z^{\gamma _j}_{v_j,v_{j+1}}\bigr ):j=1,\ldots ,n-1\bigr \}} \ge 0, \end{aligned}$$

however this contradicts that $\nu \bigl (Z^{\gamma _n}_{v_1,v_{n}}\bigr ) < 0$. $\square$

Definition 3.16

For any two edges $e_1,e_2$ of a k-periodic framework (G, p, L) in ${\mathbb {R}}^2$ with $e_i:=(v_i,w_i,\gamma _i)$ for each $i\in \{1,2\}$, we define the angle function of $e_1,e_2$ to be the map

$$\begin{aligned}&A_{e_1,e_2}:{\mathcal {V}}_{{\mathcal {C}}}^2(G)\rightarrow {\mathbb {C}},\\&\quad (p',L')\mapsto (p'(v_1)-p'(w_1)-L'\cdot \gamma _1)\cdot (p'(v_2)-p'(w_2)-L'\cdot \gamma _2). \end{aligned}$$

Remark 3.17

For any ${\tilde{e}} \in E(G)$ and any algebraic curve ${\mathcal {C}} \subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$,

$$\begin{aligned} A_{e_1,e_2}|_{{\mathcal {C}}} =\frac{1}{2} \bigl ( W_{v_1,w_1}^{\gamma _1}Z_{v_2,w_2}^{\gamma _2} + Z_{v_1,w_1}^{\gamma _1}W_{v_2,w_2}^{\gamma _2}\bigr ). \end{aligned}$$

Furthermore, if $(p,L)\sim (p',L')$, then $A_{e_1,e_2}(p,L)=A_{e_1,e_2}(p',L')$; this is since linear isometries of $({\mathbb {C}}^2,\Vert \,{\cdot }\,\Vert ^2)$ will preserve the bilinear form associated to $\Vert \,{\cdot }\,\Vert ^2$.

Lemma 3.18

Let (G, p, L) be a k-periodic framework in ${\mathbb {R}}^2$ for $k\in \{1,2\}$, ${\mathcal {C}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ be an algebraic curve, and $e_1,e_2\in E(G)$, with $e_j:=(v_j,w_j,\gamma _j)$ for $j\in \{1,2\}$. If $\delta (e_1)=\delta (e_2)$ for all active NBAC-colourings of ${\mathcal {C}}$, then $A_{e_1,e_2}|_{{\mathcal {C}}}$ is constant.

Proof

As $A_{e_1,e_2}$ is invariant for congruent placement-lattices, by Proposition 3.10, we may assume ${\tilde{e}} = e_1$. We note the map

$$\begin{aligned} (p',L') \mapsto p'(v_1)-p'(w_1) - L'\cdot \gamma _1 \end{aligned}$$

(6)

is constant on ${\mathcal {C}}$, and $W^{\gamma _1}_{v_1,w_1}$ is constant also. Suppose $A_{e_1,e_2}|_{{\mathcal {C}}}$ is not constant, then as (6) is constant,

$$\begin{aligned} (p',L') \mapsto p'(v_2)-p'(w_2) - L'\cdot \gamma _2 \end{aligned}$$

is not constant on ${\mathcal {C}}$. This in turn implies that $W^{\gamma _2}_{v_2,w_2}$ takes an infinite amount of values over ${\mathcal {C}}$. By Lemma 3.15, there exists an active NBAC-colouring $\delta$ of ${\mathcal {C}}$ with $\delta (e_1)\ne \delta (e_2)$. $\square$

Lemma 3.19

Let (G, p, L) be a k-periodic framework in ${\mathbb {R}}^2$ for $k \in \{1,2\}$ and ${\tilde{e}},e_1,e_2 \in E(G)$. If $A_{e_1,e_2}$ takes an infinite amount of values on ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ then there exists an algebraic curve ${\mathcal {C}} \subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ such that $A_{e_1,e_2}|_{{\mathcal {C}}}$ is not constant.

Proof

As $A_{e_1,e_2}$ takes an infinite amount of values on ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$, there exists a variety ${\mathcal {V}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ and points $(p',L'),(p'',L'')\in {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ such that $A_{e_1,e_2}(p',L')\ne A_{e_1,e_2}(p'',L'')$. By [15, Lem., p. 56], there exists an algebraic curve ${\mathcal {C}}$ that contains $(p',L')$ and $(p'',L'')$. $\square$

Proposition 3.20

Let (G, p, L) be a k-periodic framework in ${\mathbb {R}}^2$ for $k \in \{1,2\}$ and ${\tilde{e}},e_1,e_2 \in E(G)$. Then $\delta (e_1) = \delta (e_2)$ for all active NBAC-colourings $\delta$ of (G, p, L) if and only if $A_{e_1,e_2}$ takes only finitely many values on ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$.

Proof

Suppose $\delta (e_1)=\delta (e_2)$ for all active NBAC-colourings $\delta$ of (G, p, L). By Lemma 3.18, $A_{e_1,e_2}|_{{\mathcal {C}}}$ is constant for any algebraic curve ${\mathcal {C}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$. By Lemma 3.19, it follows that $A_{e_1,e_2}$ takes only a finite amount of values on ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$.

Suppose there exist an algebraic curve ${\mathcal {C}}$ and active NBAC-colouring $\delta$ of ${\mathcal {C}}$ generated by $\nu , \alpha$, such that $\delta (e_1) \ne \delta (e_2)$. Let $e_j = (v_j,w_j,\gamma _j)$ for $j \in \{1,2\}$. Without loss of generality we may assume $\nu \bigl (W_{v_1,w_1}^{\gamma _1}\bigr ) \le \alpha < \nu \bigl (W_{v_2,w_2}^{\gamma _2}\bigr )$. We now note

$$\begin{aligned} \nu (A_{e_1,e_2}|_{{\mathcal {C}}})=\nu \bigl (W_{v_1,w_1}^{\gamma _1}Z_{v_2,w_2}^{\gamma _2}+Z_{v_1,w_1}^{\gamma _1}W_{v_2,w_2}^{\gamma _2}\bigr )=\nu \bigl (W_{v_1,w_1}^{\gamma _1}\bigr )-\nu \bigl (W_{v_2,w_2}^{\gamma _2}\bigr )<0, \end{aligned}$$

thus $A_{e_1,e_2}|_{{\mathcal {C}}}$ must be transcendental over ${\mathbb {C}}$ when considered as an element of ${\mathcal {C}}({\mathbb {C}})$. It follows from Proposition 2.4 that $A_{e_1,e_2}$ takes an infinite amount of values on ${\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ as required. $\square$

We shall end this section by defining a graph operation we shall use later in Lemmas 5.4 and 6.4.

Definition 3.21

Let (G, p, L) be a k-periodic framework in ${\mathbb {R}}^2$ and $\gamma \in {\mathbb {Z}}^k$ be a non-zero element. We define a k-periodic framework $(G',p',L)$ in ${\mathbb {R}}^2$ to be a vertex addition of (G, p, L) at $v_1$ by $\gamma$ if

$$\begin{aligned} V(G'):= V(G)\cup \{v_0\},\qquad E(G'):=E(G)\cup \{(v_0,v_1,0),(v_0,v_1,\gamma )\} \end{aligned}$$

and $p'(v)=p(v)$ for all $v\in V(G)$; see Fig. 9.

Remark 3.22

The graph operation that takes G to $G'$ in the vertex addition described above is the first of the two gain-preserving Henneberg moves; we refer the reader to [16] for more information.

Fig. 9

A vertex addition of (G, p, L) at $v_1$ by $\gamma$

Lemma 3.23

Let (G, p, L) be a k-periodic framework in ${\mathbb {R}}^2$ with non-trivial flex $(p_t,L_t)$, $t\in [0,1]$. Assume that $\Vert L_t\cdot \gamma \Vert \ne 0$ for all $t \in [0,1]$. Then there exists a vertex addition $(G',p',L)$ of (G, p, L) at $v_1$ by $\gamma$ with non-trivial flex $(p_t',L_t)$ such that $p'_t$ restricted to V(G) is the placement $p_t$ for each $t \in [0,1]$.

Proof

As [0, 1] is compact, we may choose $r>0$ such that $r > \Vert L_t\cdot \gamma \Vert /2$ for all $t \in [0,1]$. By our choice of r, there exist for each $t\in [0,1]$ exactly two points that satisfy the equation

$$\begin{aligned} \Vert z - p_t(v_1)\Vert ^2 = \Vert z - p_t(v_1) + L\cdot \gamma \Vert ^2 = r^2. \end{aligned}$$

(7)

As $(p_t,L_t)$ is continuous, it follows that there exists a continuous path $z_t:[0,1] \rightarrow {\mathbb {R}}^2$ that satisfies (7). We now set $p'_t(v) := p_t$ for all $v \in V(G)$ and $p'_{v_0} := z_t(v_0)$. $\square$

4 Characterising Fixed Lattice Flexible Frameworks

In this section we shall prove the following result.

Theorem 4.1

Let G be a connected ${\mathbb {Z}}^k$-gain graph for $k\in \{1,2\}$. Then there exists a placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a fixed lattice flexible full k-periodic framework if and only if either

• (i) G has a fixed lattice NBAC-colouring, or

• (ii) G is balanced.

We shall first need to prove four results: Lemma 4.3 for $k=1$, Lemma 4.6 for $k=2$, and Lemmas 4.7 and 4.8 for any $k\in \{1,2\}$. The latter two will also explicitly show how to construct a fixed lattice flexible framework when either G has a fixed lattice NBAC-colouring or is balanced.

4.1 Necessary Conditions for Fixed Lattice Flexibility

Lemma 4.2

Let (G, p, L) be a full 1-periodic framework in ${\mathbb {R}}^2$ where G is connected and unbalanced, and let ${\mathcal {C}} \subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$ be an algebraic curve. Then every active NBAC-colouring of ${\mathcal {C}}$ is a fixed lattice NBAC-colouring.

Proof

Let $\delta$ be an active NBAC-colouring of ${\mathcal {C}}$ generated by the valuation $\nu$ and $\alpha \in {\mathbb {R}}$. As $\mathcal C\subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$, we have $W_1Z_1=\Vert L\cdot 1\Vert ^2$. Since $W_1Z_1$ is constant, then $\nu (W_1)=-\nu (Z_1)$. We shall assume $\nu (W_1)>\alpha$ as the proof for the case $\nu (W_1) \le \alpha$ follows by a similar method.

Suppose there exists an almost red circuit C of length n in G with $\delta (e_n)=blue$. As $\delta$ is an NBAC-colouring, we must have that $\gamma : = \psi (C) \ne 0$. It then follows that

$$\begin{aligned} \nu (W^{\gamma _n}_{v_1,v_n})&\!\!=\nu \!\left( \sum _{j=1}^{n-1} W^{\gamma _j}_{v_j,v_{j+1}}+\gamma W_1\right) \\&\!\!\ge \min {\bigl \{\nu \bigl (W^{\gamma _j}_{v_j,v_{j+1}}\bigr ), \nu (W_1) : j =1, \ldots , n-1 \bigr \}} >\alpha , \end{aligned}$$

however this contradicts that $\nu \bigl (W^{\gamma _n}_{v_1,v_n}\bigr ) \le \alpha$. Now suppose there exists an unbalanced blue circuit C of length n in G with $\gamma : =\psi (C)$. We note

$$\begin{aligned} \nu (-\gamma Z_1)=\nu \!\left( \sum _{j=1}^nZ^{\gamma _j}_{v_j,v_{j+1}}\right) \ge \min {\bigl \{\nu \bigl (Z^{\gamma _j}_{v_j,v_{j+1}}\bigr ):j=1, \ldots , n \bigr \}}\ge \alpha , \end{aligned}$$

contradicting that $\nu (Z_1) <\alpha$. $\square$

We are now ready to prove our first necessity lemma.

Lemma 4.3

Let (G, p, L) be a full 1-periodic framework in ${\mathbb {R}}^2$. If (G, p, L) is fixed lattice flexible then either G has an active fixed lattice NBAC-colouring, G is balanced, or G is disconnected.

Proof

Suppose G is unbalanced and connected. It follows from Proposition 2.7 that we may assume G contains a spanning tree T where every edge has trivial gain and ${{\tilde{e}}}\in T$, since by Proposition 3.12, if an equivalent graph to G has an active NBAC-colouring then so does G. By Lemma 3.13 (ii), there exists an algebraic curve ${\mathcal {C}}\subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$. By Lemma 3.14, there exists $a:=(a_1,a_2,\alpha )\in E(G)$ such that $W^\alpha _{a_1,a_2}$ is not constant on $\mathcal C$. By Lemma 3.15, there exists an active NBAC-colouring $\delta$ of ${\mathcal {C}}$, thus by Lemma 4.2, $\delta$ is a fixed lattice NBAC-colouring as required. $\square$

Lemma 4.4

Let (G, p, L) be a full 2-periodic framework in ${\mathbb {R}}^2$, ${\mathcal {C}} \subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$ be an algebraic curve, and suppose the function field ${\mathbb {C}}({\mathcal {C}})$ has valuation $\nu$. Then the following holds:

• (i) $\nu (W_1) = - \nu (Z_1)$, $\nu (W_2) = - \nu (Z_2)$, and $\nu (W_1\cdot Z_2 + W_2 \cdot Z_1) = 0$.

• (ii) $\nu (W_1) = \nu (W_2)$ and $\nu (Z_1) = \nu (Z_2)$.

• (iii) For all $\gamma \in {\mathbb {Z}}^2$, $\nu (\gamma Z) = - \nu (\gamma W)$.

• (iv) For any $\gamma \in {\mathbb {Z}}^2$ and $\alpha \in {\mathbb {R}}$, if $\nu (W_1) >\alpha$, then $\nu (\gamma W) >\alpha$, and if $\nu (W_1) \le \alpha$, then $\nu (\gamma W) \le \alpha$.

Proof

(i): As ${\mathcal {C}} \subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$ then

$$\begin{aligned} W_1 Z_1 = \lambda (1,1)^2,\ \quad W_2 Z_2 = \lambda (2,2)^2, \quad \ W_1\cdot Z_2 + W_2\cdot Z_1 = 2\lambda (1,2)^2, \end{aligned}$$

thus all are non-zero and constant. Since $\nu (f) = 0$ for all non-zero and constant $f\in {\mathbb {C}}({\mathcal {C}})$, the result follows.

(ii): We see that

$$\begin{aligned} \nu (W_1\cdot Z_2 + W_2\cdot Z_1) \ge \min {\{ \nu (W_1) - \nu (W_2), \nu (W_2) - \nu (W_1)\}} \end{aligned}$$

with equality if $\nu (W_1)\ne \nu (W_2)$. If $\nu (W_1)\ne \nu (W_2)$, then $\nu (W_1\cdot Z_2+W_2\cdot Z_1)<0$, contradicting that $\nu (W_1\cdot Z_2 + W_2\cdot Z_1) = 0$, thus $\nu (W_1) = \nu (W_2)$ (and similarly $\nu (Z_1)=\nu (Z_2)$).

(iii): Let $\gamma := (\gamma _1, \gamma _2)$ and define

$$\begin{aligned} g :=(\gamma _1 W_1 + \gamma _2 W_2) (\gamma _1 Z_1 + \gamma _2 Z_2)&=\gamma _1^2 W_1 Z_1+ \gamma _2^2 W_2 Z_2 + \gamma _1 \gamma _2 (W_1 Z_2 + W_2 Z_1)\\&=(\gamma _1 x_1 + \gamma _2 x_2)^2 + (\gamma _1 y_1 + \gamma _2 y_2)^2 . \end{aligned}$$

As $W_1 Z_1$, $W_2 Z_2$, and $W_1 Z_2 + W_2 Z_1$ are all constant (since ${\mathcal {C}} \subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$), then g is constant. We further note that if $g = 0$ then the vectors $(x_1,y_1)$ and $(x_2,y_2)$ are linearly dependent for all points in ${\mathcal {C}}$. As this would contradict that (G, p, L) is full, we have $\nu (g) = 0$. The required equality will now follow.

(iv): Let $\gamma := (\gamma _1, \gamma _2)$. By (i) and (ii), $\nu (W_1)=\nu (W_2)$. If $\nu (W_1) >\alpha$, then

$$\begin{aligned} \nu (\gamma _1 W_1 + \gamma _2 W_2)\ge \min {\{ \nu (W_1) , \nu (W_2)\}} > \alpha , \end{aligned}$$

while if $\nu (W_1) \le \alpha$, then by (iii),

$$\begin{aligned} \nu (\gamma _1 W_1 + \gamma _2 W_2)&= - \nu (\gamma _1 Z_1+\gamma _2Z_2)\le -\min {\{\nu (Z_1),\nu (Z_2)\}}\\&=\max {\{ \nu (W_1) , \nu (W_2)\}}\le \alpha . \end{aligned}$$

$\square$

Lemma 4.5

Let (G, p, L) be a full 2-periodic framework in ${\mathbb {R}}^2$ where G is connected graph with ${{\,\mathrm{rank}\,}}G=2$, and let $\mathcal C\subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$ be an algebraic curve. Then every active NBAC-colouring of ${\mathcal {C}}$ is a fixed lattice NBAC-colouring.

Proof

Let $\delta$ be an active NBAC-colouring of ${\mathcal {C}}$ with corresponding valuation $\nu$ and non-zero $\alpha \in {\mathbb {R}}$. By Lemma 4.4, (i) and (ii), $\nu (W_1)=\nu (W_2)$, $\nu (Z_1)=-\nu (W_1)$, and $\nu (Z_2)=-\nu (W_2)$. We shall assume $\nu (W_1) >\alpha$ as the proof for the case $\nu (W_1)\le \alpha$ follows by a similar method.

Suppose there exists an almost red circuit C of length n in G with $\gamma := \psi (C)$ and $\delta (e_n)=\text {blue}$. Then

$$\begin{aligned} W^{\gamma _n}_{v_1,v_n} = \sum _{j=1}^{n-1} W^{\gamma _j}_{v_j,v_{j+1}} + \gamma W. \end{aligned}$$

By Lemma 4.4 (iv),

$$\begin{aligned} \nu (W^{\gamma _n}_{v_1,v_n})\ge \min {\bigl \{ \nu \bigl (W^{\gamma _j}_{v_j,v_{j+1}}\bigr ),\gamma W:j=1,\ldots ,n-1\bigr \}}>\alpha , \end{aligned}$$

however this contradicts that $\nu \bigl (W^{\gamma _n}_{v_1,v_n}\bigr )\le \alpha$. Now suppose there exists an unbalanced blue circuit C of length n in G with $\gamma := \psi (C)$. We note

$$\begin{aligned} \nu (-\gamma Z)=\nu \!\left( \sum _{j=1}^{n} Z^{\gamma _j}_{v_j,v_{j+1}} \right) \ge \min {\bigl \{\nu \bigl (Z^{\gamma _j}_{v_j,v_{j+1}}\bigr ) : j =1, \ldots , n \bigr \}} \ge \alpha . \end{aligned}$$

However, by Lemma 4.4, (iii) and (iv), we have $\nu (-\gamma Z) <\alpha$, a contradiction. $\square$

We are now ready to prove our final necessity lemma.

Lemma 4.6

Let (G, p, L) be a full 2-periodic framework in ${\mathbb {R}}^2$. If (G, p, L) is fixed lattice flexible then either G has an active fixed lattice NBAC-colouring, G is balanced, or G is disconnected.

Proof

Suppose ${{\,\mathrm{rank}\,}}G =1$ and G is connected. We note that any 2-periodic framework with rank 1 is fixed lattice flexible if and only if it is fixed lattice flexible when considered as a 1-periodic framework. By Lemma 4.3, G has an active fixed lattice NBAC-colouring.

Suppose ${{\,\mathrm{rank}\,}}G=2$ and G is connected. It follows from Propositions 2.7 and 3.12 that we may assume G contains a spanning tree T where every edge has trivial gain and ${{\tilde{e}}}\in T$. By Lemma 3.13 (ii), there exists an algebraic curve ${\mathcal {C}}\subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$. By Lemma 3.14, there exists $a:=(a_1,a_2,\alpha )\in E(G)$ such that $W^\alpha _{a_1,a_2}$ is not constant on $\mathcal C$. By Lemma 3.15, there exists an active NBAC-colouring $\delta$ of ${\mathcal {C}}$, and by Lemma 4.5, $\delta$ is a fixed lattice NBAC-colouring as required. $\square$

4.2 Constructing Fixed Lattice Flexible Frameworks

Lemma 4.7

Let G be a connected ${\mathbb {Z}}^k$-gain graph for $k\in \{1,2\}$. If G has a fixed lattice NBAC-colouring $\delta$, then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is fixed lattice flexible.

Proof

The proof for $k=1$ is identical to that for $k=2$ except we have $L:=[c\;0]^T$ for some irrational $c>0$. Due to this, we shall only prove the case for $k=2$.

We may assume without loss of generality that $G^\delta _{red }$ is balanced; furthermore, by Proposition 2.7, we may assume all edges of $G^\delta _{red }$ have trivial gain. Let $R_1,\ldots ,R_n$ be the red connected components and $B_1,\ldots ,B_m$ be the blue connected components. As $\delta$ is an NBAC-colouring, there exists a blue edge ${{\tilde{e}}}\in E(G)$; by reordering the blue components we may assume the end points of ${{\tilde{e}}}$ lie in $B_1$.

Choose any two points $c_1,c_2 >0$ so that $Ac_1 + Bc_2 \notin {\mathbb {Z}}$ for all $A,B \in {\mathbb {Z}} \setminus \{0\}$; it is sufficient that the set $\{c_1,c_2\}$ is algebraically independent over ${\mathbb {Q}}$. We define the placement-lattice (p, L) of G with

$$\begin{aligned} p(v) := (x,y),\qquad L:=\begin{bmatrix}c_1 &{}\quad 0 \\ 0 &{}\quad c_2\end{bmatrix} \end{aligned}$$

for $v \in V(R_x) \cap V(B_y)$. We shall now prove (G, p, L) is a well-defined k-periodic framework.

Suppose there exists a red edge $e:=(v,w,\gamma )\in E(G)$ such that $p(v)=p(w)+L\cdot \gamma$. As e is red then $\gamma =(0,0)$, thus $p(v)=p(w)$. It follows that for some $1\le x\le n$ and $1\le y\le m$, we have $v,w\in V(R_x)\cap V(B_y)$, thus there exists a blue path $(e_1,\ldots ,e_n)$ that starts at w and ends at v. We note, however, that $(e_1,\ldots ,e_n,e)$ is an almost blue circuit, contradicting that $\delta$ is a fixed-lattice NBAC-colouring.

Now suppose there exists a blue edge $e:=(v,w,\gamma )\in E(G)$ with $\gamma =(\gamma _1,\gamma _2)$ such that $p(v)=p(w)+L\cdot \gamma$, then $p(v)=p(w)+(\gamma _1c_1,\gamma _2c_2)$. By our choice of $c_1,c_2$ we must have $\gamma _1=\gamma _2=0$, thus $p(v)=p(w)$. This implies that for some $1\le x \le n$ and $1\le y\le m$, we have $v,w\in V(R_x)\cap V(B_{y})$, and there exists a red path $(e_1,\ldots ,e_n)$ that starts at w and ends at v. We note, however, that $(e_1,\ldots ,e_n,e)$ is a balanced almost red circuit (since all red edges have trivial gain), contradicting that $\delta$ is an NBAC-colouring. It now follows that (G, p, L) is a full k-periodic framework.

Define the motion $(p_t,L_t)$, $t\in [0,1]$, where for $p(v)=(x,y)$,

$$\begin{aligned} p_t(v):=(x+y\sin t,y\cos t), \end{aligned}$$

and $L_t=L$. Choose any $t \in [0,1]$ and $e=(v,w,\gamma )\in E(G)$, with $\gamma =(\gamma _1,\gamma _2)$, $p(v)=(x,y)$ and $p(w)=(x',y')$. Suppose $\delta (e)=red$. Then $x'=x$ and $\gamma =(0,0)$ (as all red edges have trivial gain), and it follows that

$$\begin{aligned} \Vert p_t(v)-p_t(w)-L_t\cdot \gamma \Vert ^2=((y-y')\sin t)^2+((y-y')\cos t)^2=(y-y')^2. \end{aligned}$$

Now suppose $\delta (e) = blue$. Then $y'=y$ and we note that

$$\begin{aligned} \Vert p_t(v)-p_t(w) - L_t\cdot \gamma \Vert ^2=(x-x'+\gamma _1c_1)^2+(\gamma _2c_2)^2. \end{aligned}$$

It follows that $(G,p_t,L_t)\sim (G,p,L)$ for all $t\in [0,1]$, thus $(p_t,L_t)$ is a fixed lattice flex of (G, p, L). As the edge ${{\tilde{e}}}$ is fixed then $(p_t,L_t)$ is non-trivial, thus (G, p, L) is fixed lattice flexible as required. We refer the reader to Fig. 10 for an example of the construction described. $\square$

Fig. 10

(Left): A ${\mathbb {Z}}^2$-gain graph G with a fixed lattice NBAC-colouring. (Right): The constructed full 2-periodic framework (G, p, L) in ${\mathbb {R}}^2$. We note that even though we place (2) and (7) at the same point in ${\mathbb {R}}^2$, $p(2)\ne p(7)+L\cdot (1,1)$

Lemma 4.8

Let G be a ${\mathbb {Z}}^k$-gain graph for $k\in \{1,2\}$. If G is balanced, then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is fixed lattice flexible.

Proof

By Proposition 2.7, we may assume every edge of G has trivial gain. Choose any injective map p and any full lattice L. We may now define the fixed lattice flex $(p_t,L_t)$ for $t \in [0,1]$, where $p_t = p$ and

$$\begin{aligned} L_t =\begin{bmatrix}\cos t &{}\quad -\sin t \\ \sin t &{}\quad \cos t\end{bmatrix}L. \end{aligned}$$

$\square$

We may now combine the results of this section to prove Theorem 4.1

Proof of Theorem 4.1

If (G, p, L) is a fixed lattice flexible full k-periodic framework, then by Lemma 4.3 if $k=1$ or Lemma 4.6 if $k=2$, either G has a fixed lattice NBAC-colouring or G is balanced.

If G has a fixed lattice NBAC-colouring, then by Lemma 4.7, there exists a fixed lattice flexible full k-periodic framework (G, p, L) in ${\mathbb {R}}^2$. If G is balanced, then by Lemma 4.8, there exists a fixed lattice flexible full k-periodic framework (G, p, L) in $\mathbb R^2$.$\square$

5 Characterising Flexible 1-Periodic Frameworks

In this section we shall prove the following theorem.

Theorem 5.1

Let G be a connected ${\mathbb {Z}}$-gain graph. Then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 1-periodic framework if and only if either:

• (i) G has a fixed lattice NBAC-colouring,

• (ii) G has a flexible 1-lattice NBAC-colouring, or

• (iii) G is balanced.

Fortunately, much of the required work has been dealt with in Sect. 4, since fixed lattice flexible 1-periodic frameworks are a subclass of flexible 1-periodic frameworks. Due to this, we only need to prove two results: a necessity lemma that proves a flexible 1-periodic framework will have one of the required properties (see Lemma 5.2), and a construction lemma to prove that we can construct a flexible 1-periodic framework given a graph with a flexible 1-lattice NBAC-colouring (see Lemma 5.7).

5.1 Necessary Conditions for 1-Periodic Flexibility

Lemma 5.2

Let (G, p, L) be a 1-periodic framework in ${\mathbb {R}}^2$ with edge $(v,w,\gamma )\in E(G)$ for some $\gamma \ne 0$, $\mathcal C\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ be an algebraic curve, and $\nu$ a valuation of ${\mathbb {C}}({\mathcal {C}})$. Suppose $x_v-x_w$ and $y_v-y_w$ are constant on ${\mathcal {C}}$. Then $W_{v,w}^\gamma$ is constant if and only if ${\mathcal {C}}\subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$.

Proof

We note that $W_{v,w}^\gamma$ is constant if and only if $Z_{v,w}^\gamma$ is also constant as $W_{v,w}^\gamma Z_{v,w}^\gamma$ is constant. As $x_v-x_w$ and $y_v-y_w$ are constant then $W_{v,w}^\gamma$ and $Z_{v,w}^\gamma$ are constant if and only if both $x_1+iy_1$ and $x_1-iy_1$ are constant, which in turn is equivalent to both $x_1,y_1$ being constant. The result now follows. $\square$

Lemma 5.3

Let (G, p, L) be a full 1-periodic framework in ${\mathbb {R}}^2$. Suppose that (G, p, L) is flexible, G is connected and unbalanced, and G contains a pair of parallel edges ${\tilde{e}},{\tilde{f}}$. Then G either has an active fixed lattice NBAC-colouring where ${\tilde{e}},{\tilde{f}}$ are of the same colour, or G has an active flexible 1-lattice NBAC-colouring where ${\tilde{e}},{\tilde{f}}$ are of opposite colours.

Proof

We may assume ${{\tilde{e}}}$ and ${{\tilde{f}}}$ are the pair of parallel edges on ${{\tilde{v}}},{{\tilde{w}}}$, with $\psi ({{\tilde{f}}})=\mu \ne 0$. It follows from Propositions 2.7 and 3.12 that we may assume G contains a spanning tree T where every edge has trivial gain and ${{\tilde{e}}}\in T$. By Lemma 3.13 (ii), there exists an algebraic curve ${\mathcal {C}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$.

Suppose ${\mathcal {C}}\subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$. By Lemma 4.3, G has an active fixed lattice NBAC-colouring $\delta$. By Lemma 5.2, we note that we must have $\delta ({\tilde{e}})= \delta ({\tilde{f}})$. Now suppose ${\mathcal {C}} \not \subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$. By Lemma 5.2, $W_{{\tilde{v}},{\tilde{w}}}^{\mu }$ is not constant on ${\mathbb {C}}({\mathcal {C}})$. Let $\nu$ be the valuation of $\mathbb C({\mathcal {C}})$ and $\delta$ the NBAC-colouring given by Lemma 3.15 with $a := {\tilde{f}}$. By our choice of valuation, $\nu (W_{{\tilde{v}},{\tilde{w}}}^0) = 0$ and $\nu (W_{{\tilde{v}},{\tilde{w}}}^\mu ) > 0$; it follows immediately that $\nu (Z_{{\tilde{v}},{\tilde{w}}}^0) = 0$ and $\nu (Z_{{\tilde{v}},{\tilde{w}}}^\mu ) < 0$ as both $W_{{\tilde{v}},{\tilde{w}}}^0 Z_{{\tilde{v}},{\tilde{w}}}^0$ and $W_{{\tilde{v}},{\tilde{w}}}^\mu Z_{{\tilde{v}},{\tilde{w}}}^\mu$ are constant. As $\mu W_1 = W_{{\tilde{v}},{\tilde{w}}}^0 - W_{{\tilde{v}},{\tilde{w}}}^\mu$ then $\nu (W_1) = \nu (W_{{\tilde{v}},{\tilde{w}}}^0) = 0$. Similarly, as $\mu Z_1 = Z_{{\tilde{v}},{\tilde{w}}}^0 - Z_{{\tilde{v}},{\tilde{w}}}^\mu$ then $\nu (Z_1) = \nu (Z_{{\tilde{v}},{\tilde{w}}}^\mu ) <0$.

Suppose G has an unbalanced monochromatic circuit C of length n. If C is red, then

$$\begin{aligned} \nu (W_1) = \nu ( - \psi (C)W_1)= \nu \!\left( \sum _{j=1}^n W^{\gamma _j}_{v_j,v_{j+1}}\!\right) \ge \min {\bigl \{ \nu \bigl (W^{\gamma _j}_{v_j,v_{j+1}}\bigr ) : 1\le j \le n \bigr \}}>0, \end{aligned}$$

contradicting that $\nu (W_1) = 0$. If C is blue, then

$$\begin{aligned} \nu (Z_1) = \nu ( - \psi (C)Z_1)=\nu \!\left( \sum _{j=1}^n Z^{\gamma _j}_{v_j,v_{j+1}}\!\right) \ge \min {\bigl \{\nu \bigl (Z^{\gamma _j}_{v_j,v_{j+1}}\bigr ) : 1\le j \le n \bigr \}} \ge 0, \end{aligned}$$

contradicting that $\nu (Z_1) < 0$. It now follows that $\delta$ is an active flexible 1-lattice NBAC-colouring. $\square$

We are now ready to state our necessity lemma.

Lemma 5.4

Let (G, p, L) be a full 1-periodic framework in ${\mathbb {R}}^2$. If (G, p, L) is flexible then G either has an active fixed lattice NBAC-colouring, an active flexible 1-lattice NBAC-colouring, G is balanced, or G is disconnected.

Proof

We may suppose G is connected and unbalanced. If G contains a pair of parallel edges then the result holds by Lemma 5.3, thus we shall also assume that G does not contain a pair of parallel edges.

By Lemma 3.23, there exists a vertex addition $(G',p',L)$ of (G, p, L) at $v_1$ by 1 such that $(G',p',L)$ has a non-trivial not fixed lattice flex; we shall define these new edges by ${\tilde{e}}, {\tilde{f}}$, with $\psi ({\tilde{e}})=0$ and $\psi ({\tilde{f}})=1$. As $G'$ contains a pair of parallel edges then by Lemma 5.3, either $G'$ has an active flexible 1-lattice NBAC-colouring $\delta '$ with $\delta '({\tilde{e}})=blue$ and $\delta '({\tilde{f}})=red$, or $G'$ has an active fixed lattice NBAC-colouring $\delta ''$ with $\delta ''({\tilde{e}}) =\delta ''({\tilde{f}})=blue$.

Suppose $G'$ has a colouring $\delta '$ as described above. Let $\delta$ be the colouring of G with $\delta (e) := \delta '(e)$ for all $e \in E(G)$. We note that $\delta$ is a flexible 1-lattice NBAC-colouring if and only if $\delta '$ is not monochromatic on the subgraph G of $G'$. As G is unbalanced, $\delta '$ cannot be monochromatic on G, thus $\delta$ is a flexible 1-lattice NBAC-colouring of G.

Now suppose $G'$ has a colouring $\delta ''$ as described above. Let $\delta$ be the colouring of G with $\delta (e):=\delta ''(e)$ for all $e\in E(G)$. We note that $\delta$ is a fixed lattice NBAC-colouring if and only if $\delta '$ is not monochromatic on the subgraph G of $G'$. If $\delta '$ is monochromatic on G, then as $\delta '({{\tilde{e}}})=\delta '({{\tilde{f}}})=blue$ and G is unbalanced, we must have $\delta (G)=blue$, however this would contradict that $\delta '(G')=\{red ,blue \}$. It now follows that $\delta$ is a fixed lattice NBAC-colouring of G. $\square$

5.2 Constructing Flexible Frameworks from Flexible 1-Lattice NBAC-Colourings

Lemma 5.5

Let G be a ${\mathbb {Z}}$-gain graph with a flexible 1-lattice NBAC-colouring. Then there exists $G' \approx G$ such that each blue edge has trivial gain and no red edge has trivial gain.

Proof

As $G^\delta _{blue }$ is balanced, by Proposition 2.7, we may suppose all blue edges of G have trivial gain. Let $B_1,\ldots , B_n$ be the blue components of G and choose $\mu \in {\mathbb {N}}$ such that $\mu >|\gamma |$ for all $(v,w,\gamma )\in E(G)$. We now define

$$\begin{aligned} G' := \left( \prod _{i=1}^n \prod _{v \in B_i} \phi _v^{i\mu }\right) (G). \end{aligned}$$

We first note that any blue edge of $G'$ will have trivial gain since both of its ends will lie in the same blue component. Choose a red edge $(v,w,\gamma ) \in E(G)$ and suppose $v \in B_i$ and $w \in B_j$. We note that

$$\begin{aligned} \left( \prod _{i=1}^n\prod _{v\in B_i}\phi _v^{i\mu }\right) (v,w,\gamma )=\phi _v^{i\mu }\circ \phi _w^{j\mu }(v,w,\gamma )=(v,w,\gamma +(i-j)\mu ). \end{aligned}$$

As $\mu >|\gamma |$ and $i-j\in {\mathbb {Z}}$, then $\gamma + (i-j)\mu =0$ if and only if $\gamma = 0$ and $i=j$. If $v,w \in B_i$ and $\gamma =0$ then there would exist a balanced almost blue circuit as v, w are connected by a blue path and all blue edges of G have trivial gain, thus $\gamma + (i-j)\mu \ne 0$ as required. $\square$

Lemma 5.6

Let H be a balanced ${\mathbb {Z}}$-gain graph. Then there exists a placement q of H in ${\mathbb {Z}}$ such that for all $(v,w,\gamma )\in E(H)$, $q(w)-q(v)=2\gamma$.

Proof

We may suppose without loss of generality that H is connected. Choose a spanning tree T of H. It is immediate that we may choose a placement q of T that satisfies the condition $q(w)-q(v) =2\gamma$ for all $(v,w,\gamma )\in E(T)$. Choose an edge $e=(a,b,\mu )\in E(H)\setminus E(T)$, then there exists a path $(e_1,\ldots ,e_{n-1})$ in T with $e_i=(v_i,v_{i+1},\gamma _i)$, $v_1=b$ and $v_n=a$. As H is balanced, $\psi (e_1,\ldots ,e_{n-1})=-\mu$, thus by our choice of q,

$$\begin{aligned} q(b) - q(a)= -\left( \sum _{i=1}^{n-1}q(v_{i+1}) - q(v_i) \right) = -2\psi (e_1,\ldots ,e_{n-1})= 2\mu . \end{aligned}$$

$\square$

We our now ready to prove our construction lemma.

Lemma 5.7

Let G be a ${\mathbb {Z}}$-gain graph with a flexible 1-lattice NBAC-colouring $\delta$. Then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 1-periodic framework.$\square$

Proof

By Lemma 5.5, we may assume all blue edges of G have trivial gain and all red edges have non-trivial gain. Let $R_1,\ldots ,R_n$ be the red components of G and define $E_j$ to be the set of edges $(v,w,\gamma )$ in $G^\delta _{red }$ with $v,w\in R_j$. By Lemma 5.6, for each $R_j$ there exists a placement $q_j$ in ${\mathbb {R}}$ where $q_j(w)-q_j(v)=2\gamma$ for all $(v,w,\gamma ) \in E_j$. We now define for each $t \in [0,2\pi ]$ the full placement-lattice $(p_t,L_t)$ of G in ${\mathbb {R}}^2$, with

$$\begin{aligned} p_t(v) := ( q_j(v), j ), \qquad L_t \cdot 1:= (-2 + \cos t, \sin t) \end{aligned}$$

for $v \in R_j$ and $t \in [0,2\pi ]$. We shall denote $(p,L) := (p_0,L_0)$.

To see that (p, L) is a well-defined placement-lattice, choose any $e=(v,w,\gamma )$ and suppose that $p(v)=p(w)+L\cdot \gamma$. It follows that $v,w\in R_j$ and $q_j(v)-q_j(w)=\gamma$. If $\delta (e)=red$ then $\gamma \ne 0$, however this contradicts that $q_j(v)-q_j(w)=-2\gamma$. Suppose $\delta (e)=blue$. Since every blue edge has trivial gain, $\gamma =0$. As $v,w \in R_j$, there exists a red path $(e_1,\ldots ,e_{n-1})$ with $e_j=(v_j,v_{j+1},\gamma _j)\in E_j$, $v_1=w$ and $v_n=v$. Since $q_j(v)=q_j(w)$, we have $\sum _{j=1}^{n-1}\gamma _j=0$. However, this implies $(e_1,\ldots ,e_{n-1},e)$ is a balanced almost red circuit, contradicting that $\delta$ is an NBAC-colouring.

Choose any $e = (v,w,\gamma )$. If $\delta (e)=blue$ then $\gamma = 0$. As $p_t=p$ then for each $t\in [0,2\pi ]$,

$$\begin{aligned} \Vert p_t(v) - p_t(w) - L_t\cdot \gamma \Vert ^2=\Vert p(v)-p(v)\Vert ^2. \end{aligned}$$

If $\delta (e)=red$ then $v,w \in R_j$, thus for each $t\in [0,2\pi ]$,

$$\begin{aligned} \Vert p_t(v) - p_t(w) - L_t\cdot \gamma \Vert ^2&=({-}(q_j(w) - q_j(v) )+ 2 \gamma - \gamma \cos t )^2 + (\gamma \sin t)^2 \\&= \gamma ^2. \end{aligned}$$

It follows that $(p_t,L_t)$ is a flex of (G, p, L) as required. We refer the reader to Fig. 11 for an example of the construction. $\square$

Fig. 11

(Left): A ${\mathbb {Z}}$-gain graph with a flexible 1-lattice NBAC-colouring. (Right): The constructed full 1-periodic framework in ${\mathbb {R}}^2$

We are now ready to prove the main theorem of this section.

Proof of Theorem 5.1

Suppose (G, p, L) is flexible. By Lemma 5.4, either G is balanced, G has a fixed lattice NBAC-colouring, or G has a flexible 1-periodic NBAC-colouring. If G is balanced, then by Lemma 4.8, G has a flexible full placement-lattice in ${\mathbb {R}}^2$. If G has a fixed lattice NBAC-colouring, then by Lemma 4.7, G has a flexible full placement-lattice in ${\mathbb {R}}^2$. If G has a flexible 1-lattice NBAC-colouring, then by Lemma 5.7, G has a flexible full placement-lattice in ${\mathbb {R}}^2$. $\square$

6 Characterising Flexible 2-Periodic Frameworks

Unlike with 1-periodic frameworks, a full characterisation of ${\mathbb {Z}}^2$-gain graphs with flexible 2-periodic full placements in the plane via NBAC-colourings is unknown. We would conjecture the following.

Conjecture 1

Let G be a connected ${\mathbb {Z}}^2$-gain graph. Then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 2-periodic framework if and only if either:

• (i) G has a type 1 flexible 2-lattice NBAC-colouring,

• (ii) G has a type 2 flexible 2-lattice NBAC-colouring,

• (iii) G has a type 3 flexible 2-lattice NBAC-colouring,

• (iv) G has a fixed lattice NBAC-colouring, or

• (v) ${{\,\mathrm{rank}\,}}G<2$.

We are able to obtain the required necessity lemma and most of the required construction lemmas, however a construction of a flexible full 2-periodic framework from a type 3 flexible 2-lattice NBAC-colouring is still currently unknown. In this section we shall, however, outline some partial results regarding ${\mathbb {Z}}^2$-gain graphs, in particular, Lemmas 6.4, 6.5, 6.8, and 6.11. We shall discuss some other possible conjectures at the end of the section, and later in Sect. 7 we shall obtain analogues of Theorem 5.1 for certain types of graphs; see Theorems 7.5 and 7.8.

6.1 Necessary Conditions for 2-Periodic Flexibility

For any $\gamma =(a,b)\in {\mathbb {Z}}^2$, we recall the notation $\gamma W:=aW_1+bW_2$ and $\gamma Z:=aZ_1+bZ_2$.

Lemma 6.1

Let (G, p, L) be a 2-periodic framework in ${\mathbb {R}}^2$ with edge $(v,w,\gamma )\in E(G)$ for some $\gamma =(\gamma _1,\gamma _2)\ne (0,0)$, ${\mathcal {C}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ be an algebraic curve, and $\nu$ a valuation of ${\mathbb {C}}({\mathcal {C}})$. Suppose $x_v-x_w$ and $y_v-y_w$ are constant on ${\mathcal {C}}$. If $W_{v,w}^\gamma$ is constant then

$$\begin{aligned} (\gamma _1 x_1 + \gamma _2 x_2)^2 + (\gamma _1 y_1 + \gamma _2 y_2)^2 \end{aligned}$$

is constant.

Proof

We note that $W_{v,w}^\gamma$ is constant if and only if $Z_{v,w}^\gamma$ is also constant as $W_{v,w}^\gamma Z_{v,w}^\gamma$ is constant. As $x_v-x_w$ and $y_v-y_w$ are constant, both $(\gamma _1x_1+\gamma _2x_2)+i(\gamma _1y_1+\gamma _2y_2)$ and $(\gamma _1x_1+\gamma _2x_2)-i(\gamma _1y_1 + \gamma _2 y_2)$ are constant. The result now follows from the observation that $(a+ib)(a-ib)=a^2+b^2$. $\square$

Lemma 6.2

Let (G, p, L) be a full 2-periodic framework in ${\mathbb {R}}^2$ and ${\mathcal {C}} \subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ be an algebraic curve. Suppose the function field ${\mathbb {C}}({\mathcal {C}})$ has valuation $\nu$ and for some $\mu \in {\mathbb {Z}}^2 \setminus \{(0,0)\}$,

$$\begin{aligned} \nu (\mu W)=0,\qquad \nu (\mu Z) < 0. \end{aligned}$$

Then one of the following cases holds:

• (i) For all $\gamma \in {\mathbb {Z}}^2\setminus \{(0,0) \}$,

  $$\begin{aligned} \nu (\gamma W)\le 0,\qquad \nu (\gamma Z)<0. \end{aligned}$$

• (ii) There exist $\alpha ,\beta \in {\mathbb {Z}}^2$, at least one non-zero, such that for all $\gamma \in {\mathbb {Z}}^2\setminus ({\mathbb {Z}}\alpha \cup {\mathbb {Z}}\beta )$,

  $$\begin{aligned} \nu (\gamma W)\le 0,\qquad \nu (\gamma Z)<0, \end{aligned}$$

  for all $\gamma \in {\mathbb {Z}}\alpha \setminus \{(0,0)\}$,

  $$\begin{aligned} \nu (\gamma W)>0,\qquad \nu (\gamma Z)<0, \end{aligned}$$

  and for all $\gamma \in {\mathbb {Z}} \beta \setminus \{(0,0)\}$,

  $$\begin{aligned} \nu (\gamma W)\le 0,\qquad \nu (\gamma Z)\ge 0. \end{aligned}$$

• (iii) There exists $\alpha \in {\mathbb {Z}}^2\setminus \{(0,0)\}$ such that for all $\gamma \in {\mathbb {Z}}^2\setminus {\mathbb {Z}}\alpha$,

  $$\begin{aligned} \nu (\gamma W)\le 0,\qquad \nu (\gamma Z)<0, \end{aligned}$$

  and for all $\gamma \in {\mathbb {Z}}\alpha \setminus \{(0,0)\}$,

  $$\begin{aligned} \nu (\gamma W)>0,\qquad \nu (\gamma Z)\ge 0. \end{aligned}$$

Proof

Choose $\lambda \in {\mathbb {Z}}^2$ so that $\mu$ and $\lambda$ are linearly independent.

If $\nu ( \mu W) \ne \nu (\lambda W)$, then we note that for all $\gamma \in {\mathbb {Z}}^2\setminus \{(0,0)\}$ with $\gamma =a\mu +b\lambda$,

$$\begin{aligned} \nu (\gamma W)=\nu ((a\mu +b\lambda )W)=\min {\{\nu ( \mu W),\nu (\lambda W)\}}\le 0; \end{aligned}$$

similarly, if $\nu ( \mu Z) \ne \nu (\lambda Z)$, then $\nu (\gamma Z) <0$ for all $\gamma \in {\mathbb {Z}}^2$.

If $\nu (\mu W)=\nu (\lambda W)$, then there can exist $\alpha \in {\mathbb {Z}}^2\setminus \{(0,0)\}$ that is pairwise independent with $\mu$ and $\lambda$ such that $\nu (\alpha W) >0$. We note that $\alpha$ is unique up to scalar multiplication, as if there exists $\gamma \in {\mathbb {Z}}^2\setminus {\mathbb {Z}}\alpha$ such that $\nu (\gamma W)>0$ also, then we may choose $A,B\in {\mathbb {R}}$ such that $A\alpha +B\gamma =\mu$, and note

$$\begin{aligned} \nu ( \mu W) \ge \min {\{\nu (\alpha W), \nu (\gamma W) \}}>0, \end{aligned}$$

contradicting that $\nu (\mu W)=0$. Likewise, if $\nu (\mu Z)=\nu (\lambda Z)$, then there can exist at most one $\beta \in {\mathbb {Z}}^2\setminus \{0\}$ such that $\nu (\beta Z)\ge 0$.

We now check the cases:

• Suppose $\nu ( \mu W) \ne \nu (\lambda W)$ and $\nu ( \mu Z) \ne \nu (\lambda Z)$.

  • Case (i) holds if $\nu (\lambda W) , \nu (\lambda Z)<0$.

  • Case (ii) holds if $\nu (\lambda W)<0 < \nu (\lambda Z)$ or $\nu (\lambda Z)<0 < \nu (\lambda W)$.

  • Case (iii) holds if $\nu (\lambda W) , \nu (\lambda Z) > 0$.

• Suppose $\nu ( \mu W) = \nu (\lambda W)$ and $\nu ( \mu Z) \ne \nu (\lambda Z)$.

  • Case (i) holds if $\alpha$ does not exist and $\nu ( \mu Z) < 0$.

  • Case (ii) holds otherwise.

• Suppose $\nu ( \mu W) \ne \nu (\lambda W)$ and $\nu ( \mu Z) = \nu (\lambda Z)$.

  • Case (i) holds if $\nu ( \mu W) < 0$ and $\beta$ does not exist.

  • Case (ii) holds otherwise.

• Suppose $\nu ( \mu W) = \nu (\lambda W)$ and $\nu ( \mu Z) = \nu (\lambda Z)$.

  • Case (i) holds if $\alpha , \beta$ do not exist.

  • Case (ii) holds if $\alpha$ exists and $\beta$ does not exist, $\alpha$ does not exist and $\beta$ exists, or if $\alpha , \beta$ exist and $\alpha \ne \beta$.

  • Case (iii) holds if $\alpha , \beta$ exist and $\alpha = \beta$.$\square$

Lemma 6.3

Let (G, p, L) be a full 2-periodic framework in ${\mathbb {R}}^2$ and ${\mathcal {C}}\subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$ be an algebraic curve. Further, suppose G contains a pair of parallel edges $(v,w,\gamma )$ and $(v,w,\gamma ')$ such that $\gamma -\gamma ' =(\lambda _1,\lambda _2)$ and

$$\begin{aligned} (\lambda _1 x_1 + \lambda _2 x_2)^2 + (\lambda _1 y_1 + \lambda _2 y_2)^2 \end{aligned}$$

is not constant on ${\mathcal {C}}$. Then one of the following holds:

• (i) G has an active type 1 flexible 2-lattice NBAC-colouring,

• (ii) G has an active type 2 flexible 2-lattice NBAC-colouring, or

• (iii) G has an active type 3 flexible 2-lattice NBAC-colouring.

Proof

By our choice of ${\tilde{e}}$, we may assume ${\tilde{e}}$ and ${\tilde{f}}$ are the pair of parallel edges on ${{\tilde{v}}},{{\tilde{w}}}$, with $\psi ({{\tilde{f}}})=\mu$ for some $\mu =(\mu _1,\mu _2)\in \mathbb Z^2\setminus \{(0,0)\}$. It follows from Propositions 2.7 and 3.12 that we also may assume G contains a spanning tree T where every edge has trivial gain and ${\tilde{e}} \in T$. Since $\mu$ is the difference in gains of ${\tilde{e}},{\tilde{f}}$, then

$$\begin{aligned} (\mu _1 x_1 + \mu _2 x_2)^2 + (\mu _1 y_1 + \mu _2 y_2)^2 \end{aligned}$$

is not constant. By Lemma 6.1, $W_{{\tilde{v}},{\tilde{w}}}^{\mu }$ is not constant on ${\mathbb {C}}({\mathcal {C}})$. Let $\nu$ be the valuation of ${\mathbb {C}}({\mathcal {C}})$ and $\delta$ be the active NBAC-colouring given by Lemma 3.15 with $a:={\tilde{f}}$.

We note that $\nu (W_{{{\tilde{v}}},{{\tilde{w}}}}^0)=0$ and $\nu (W_{\tilde{v},{{\tilde{w}}}}^\mu )>0$. As $\mu W=W_{{\tilde{v}},{\tilde{w}}}^0-W_{{\tilde{v}},{\tilde{w}}}^\mu$,

$$\begin{aligned} \nu (\mu W)=\nu ( W_{{\tilde{v}},{\tilde{w}}}^0)=0. \end{aligned}$$

Similarly, as $\mu Z = Z_{{\tilde{v}},{\tilde{w}}}^0 - Z_{{\tilde{v}},{\tilde{w}}}^\mu$ then

$$\begin{aligned} \nu (\mu Z)=\nu ( Z_{{\tilde{v}},{\tilde{w}}}^\mu ) < 0. \end{aligned}$$

Let case (i), case (ii), and case (iii) refer to the three possibilities given by Lemma 6.2. We shall now proceed to prove that case (i) implies G has a type 1 flexible 2-lattice NBAC-colouring, case (ii) implies G has either a type 1 or type 2 flexible 2-lattice NBAC-colouring, and case (iii) implies G has either a type 1, type 2, or a type 3 flexible 2-lattice NBAC-colouring.

(Case (i) holds): Suppose G has an unbalanced monochromatic circuit C of length n and define $\gamma :=\psi (C)$. If C is red, then

$$\begin{aligned} \nu (\gamma W)=\nu \!\left( -\sum _{j=1}^n W^{\gamma _j}_{v_j,v_{j+1}}\right) \ge \min {\bigl \{\nu \bigl (W^{\gamma _j}_{v_j,v_{j+1}}\bigr ):1\le j \le n\bigr \}}>0, \end{aligned}$$

contradicting that $\nu (\gamma W) \le 0$. If C is blue, then

$$\begin{aligned} \nu (\gamma Z)=\nu \!\left( -\sum _{j=1}^n Z^{\gamma _j}_{v_j,v_{j+1}} \right) \ge \min {\bigl \{\nu \bigl (Z^{\gamma _j}_{v_j,v_{j+1}}\bigr ):1\le j \le n\bigr \}}\ge 0, \end{aligned}$$

contradicting that $\nu (\gamma Z)<0$. It now follows that $\delta$ is a type 1 flexible 2-lattice NBAC-colouring.

(Case (ii) holds): Let C be an unbalanced monochromatic circuit of length n with $\gamma :=\psi (C)$. If C is red and $\gamma \notin {\mathbb {Z}}\alpha$, then

$$\begin{aligned} \nu (\gamma W)= \nu \!\left( - \sum _{j=1}^n W^{\gamma _j}_{v_j,v_{j+1}} \right) \ge \min {\bigl \{ \nu \bigl (W^{\gamma _j}_{v_j,v_{j+1}}\bigr ):1\le j \le n\bigr \}} >0, \end{aligned}$$

contradicting that $\nu (\gamma W) \le 0$. Likewise, if C is blue and $\gamma \notin {\mathbb {Z}}\beta$, then

$$\begin{aligned} \nu (\gamma Z)= \nu \! \left( - \sum _{j=1}^n Z^{\gamma _j}_{v_j,v_{j+1}} \right) \ge \min {\bigl \{\nu \bigl (Z^{\gamma _j}_{v_j,v_{j+1}}\bigr ):1\le j \le n \bigr \}}\ge 0, \end{aligned}$$

contradicting that $\nu (\gamma Z)<0$.

Now let C be an almost monochromatic circuit of length n where $\delta (e_n) \ne \delta (e_i)$ for all $i \in \{1,\ldots ,n-1\}$. If C is almost red and $\psi (C) = c\alpha$ for some $c \in {\mathbb {Z}}$, then

$$\begin{aligned} \nu \bigl (W_{v_{1},v_{n}}^{\gamma _{n}}\bigr )&\!\!= \nu \!\left( \sum _{j=1}^{n-1} W^{\gamma _j}_{v_j,v_{j+1}} + c \alpha W \right) \\&\!\!\ge \min {\bigl \{\nu \bigl (\alpha W), \nu (W^{\gamma _j}_{v_j,v_{j+1}}\bigr ) : 1\le j \le n-1 \bigr \}}>0, \end{aligned}$$

contradicting that $\nu \bigl (W_{v_{1},v_{n}}^{\gamma _{n}}\bigr )\le 0$. Similarly, if C is almost blue and $\psi (C) = c\beta$ for some $c \in {\mathbb {Z}}$, then

$$\begin{aligned} \nu \bigl (Z_{v_{1},v_{n}}^{\gamma _{n}}\bigr )&\!\!= \nu \!\left( \sum _{j=1}^{n-1} Z^{\gamma _j}_{v_j,v_{j+1}} + c \beta Z \right) \\&\!\!\ge \min {\bigl \{\nu (\beta Z), \nu \bigl (Z^{\gamma _j}_{v_j,v_{j+1}}\bigr ) : 1\le j \le n-1 \bigr \}} >0, \end{aligned}$$

contradicting that $\nu \bigl (Z_{v_{1},v_{n}}^{\gamma _{n}}\bigr )\le 0$.

It now follows that if G has no unbalanced monochromatic circuits then $\delta$ is a type 1 flexible 2-lattice NBAC-colouring, and if G has an unbalanced monochromatic circuit then $\delta$ is a type 2 flexible 2-lattice NBAC-colouring.

(Case (iii) holds): Let C be an unbalanced monochromatic circuit of length n with $\gamma :=\psi (C)\notin {\mathbb {Z}}\alpha$. If C is red, then

$$\begin{aligned} \nu (\gamma W)=\nu \!\left( -\sum _{j=1}^nW^{\gamma _j}_{v_j,v_{j+1}}\right) \ge \min {\bigl \{\nu \bigl (W^{\gamma _j}_{v_j,v_{j+1}}\bigr ):1\le j\le n\bigr \}}>0, \end{aligned}$$

contradicting that $\nu (\gamma W) \le 0$. Likewise, if C is blue, then

$$\begin{aligned} \nu (\gamma Z)= \nu \!\left( - \sum _{j=1}^n Z^{\gamma _j}_{v_j,v_{j+1}} \right) \ge \min {\bigl \{\nu \bigl (Z^{\gamma _j}_{v_j,v_{j+1}}\bigr ):1\le j\le n\bigr \}}\ge 0, \end{aligned}$$

contradicting that $\nu (\gamma Z) < 0$.

Now let C be an almost monochromatic circuit of length n where $\psi (C) := c\alpha$ for some $c \in {\mathbb {Z}}$ and $\delta (e_n) \ne \delta (e_i)$ for all $i \in \{1,\ldots ,n-1\}$. If C is almost red, then

$$\begin{aligned} \nu \bigl (W_{v_{1},v_{n}}^{\gamma _{n}}\bigr )&\!\!=\nu \!\left( \sum _{j=1}^{n-1} W^{\gamma _j}_{v_j,v_{j+1}} + c \alpha W \right) \\&\!\!\ge \min {\bigl \{\nu (\alpha W),\nu \bigl (W^{\gamma _j}_{v_j,v_{j+1}}\bigr ):1\le j \le n-1 \bigr \}}>0, \end{aligned}$$

contradicting that $\nu \bigl (W_{v_{1},v_{n}}^{\gamma _{n}}\bigr )\le 0$. Similarly, if C is almost blue, then

$$\begin{aligned} \nu \bigl (Z_{v_{1},v_{n}}^{\gamma _{n}}\bigr )&\!\!= \nu \! \left( \sum _{j=1}^{n-1} Z^{\gamma _j}_{v_j,v_{j+1}} + c \alpha Z \right) \\&\!\!\ge \min {\bigl \{\nu (\alpha Z), \nu \bigl (Z^{\gamma _j}_{v_j,v_{j+1}}\bigr ) : 1\le j \le n-1 \bigr \}} >0, \end{aligned}$$

contradicting that $\nu \bigl (Z_{v_{1},v_{n}}^{\gamma _{n}}\bigr )\le 0$.

It now follows that if G has no unbalanced monochromatic circuits then $\delta$ is a type 1 flexible 2-lattice NBAC-colouring, if G only has unbalanced monochromatic circuits for a single colour then $\delta$ is a type 2 flexible 2-lattice NBAC-colouring, and if G has unbalanced monochromatic circuits for both colours then $\delta$ is a type 3 flexible 2-lattice NBAC-colouring. $\square$

We are now ready for our necessity lemma.

Lemma 6.4

Let (G, p, L) be a full 2-periodic framework in ${\mathbb {R}}^2$. If (G, p, L) is flexible then one of the following holds:

• (i) G has an active type 1 flexible 2-lattice NBAC-colouring,

• (ii) G has an active type 2 flexible 2-lattice NBAC-colouring,

• (iii) G has an active type 3 flexible 2-lattice NBAC-colouring,

• (iv) G has an active fixed lattice NBAC-colouring,

• (v) ${{\,\mathrm{rank}\,}}G<2$, or

• (vi) G is disconnected.

Proof

Suppose ${{\,\mathrm{rank}\,}}G= 2$ and G is connected. Choose any ${\tilde{e}} \in E(G)$. By Lemma 3.13 (ii), there exists an algebraic curve ${\mathcal {C}} \subset {\mathcal {V}}_{{\tilde{e}}}(G,p,L)$. We now have three possible outcomes:

• (a) ${\mathcal {C}} \subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$.

• (b) G contains a pair of parallel edges $(v,w,\gamma )$ and $(v,w,\gamma ')$ such that $\gamma -\gamma '=(\lambda _1,\lambda _2)$ and

  $$\begin{aligned} (\lambda _1 x_1 + \lambda _2 x_2)^2 + (\lambda _1 y_1 + \lambda _2 y_2)^2 \end{aligned}$$

  is not constant on ${\mathcal {C}}$.

• (c) Possibilities (a) and (b) do not hold.

(Possibility (a) holds): If $\mathcal C\subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$ then by Lemma 4.3, G has an active fixed lattice NBAC-colouring.

(Possibility (b) holds): By Lemma 6.3, G has either an active type 1, type 2, or type 3 flexible 2-lattice NBAC-colouring.

(Possibility (c) holds): As ${\mathcal {C}}\not \subset {\mathcal {V}}^f_{{\tilde{e}}}(G,p,L)$, we may choose $\mu := (\mu _1,\mu _2) \in {\mathbb {Z}}^2$ such that

$$\begin{aligned} (\lambda _1x_1 + \lambda _2 x_2)^2 + (\lambda _1 y_1 + \lambda _2 y_2)^2 \end{aligned}$$

is not constant. By Lemma 3.23, there exists a vertex addition $(G',p',L)$ of (G, p, L) at $v_1$ by $\lambda$ such that $(G',p',L)$ has a non-trivial not fixed lattice flex. As (b) holds for $(G',p',L)$, then by Lemma 6.3, $G'$ has an active type k flexible 1-lattice NBAC-colouring $\delta '$ for some $k\in \{1,2,3\}$.

Suppose $G'$ has a colouring $\delta '$ as described above. Let $\delta$ be the colouring of G with $\delta (e):=\delta '(e)$ for all $e\in E(G)$. We note that $\delta$ is an active type $k'$ flexible 2-lattice NBAC-colouring for some $k'\in \{1,2,3\}$ if and only if $\delta '$ is not monochromatic on the subgraph G of $G'$. As ${{\,\mathrm{rank}\,}}G=2$ and $\delta '$ is a type k flexible 2-lattice NBAC-colouring, $\delta '$ is not monochromatic on G, thus G has an active type $k'$ flexible 2-lattice NBAC-colouring for some $k'\in \{1,2,3\}$. $\square$

6.2 Constructing Flexible Frameworks: Low Rank Graphs

Our first construction lemma is the simplest one, as the framework is not connected.

Lemma 6.5

Let G be a ${\mathbb {Z}}^2$-gain graph. If ${{\,\mathrm{rank}\,}}G<2$ then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is flexible.

Proof

If ${{\,\mathrm{rank}\,}}G=0$ then this holds by Lemma 4.7, so we may suppose ${{\,\mathrm{rank}\,}}G=1$, i.e., ${{\,\mathrm{span}\,}}G={\mathbb {Z}}\alpha$ for some non-zero $\alpha \in {\mathbb {Z}}^2$. By Proposition 2.7, we may assume every edge of G has gain in ${\mathbb {Z}}\alpha$. Choose any injective map p, any full lattice L, and any element $\beta \in {\mathbb {Z}}^2$ that is linearly independent of $\alpha$. We may now define the fixed lattice flex $(p_t,L_t)$ for $t\in [0,2\pi ]$, where $p_t=p$ and

$$\begin{aligned} L_t\cdot \alpha :=L\cdot \alpha ,\qquad L_t\cdot \beta :=(1+t)L\cdot \beta . \end{aligned}$$

$\square$

6.3 Constructing Flexible Frameworks: Type 1 Flexible 2-Lattice NBAC-Colourings

We recall that a type 1 flexible 2-lattice NBAC-colouring is an NBAC-colouring $\delta$ where all monochromatic circuits are balanced.

Lemma 6.6

Let G be a ${\mathbb {Z}}^2$-gain graph with a type 1 flexible 2-lattice NBAC-colouring. Then there exists $G' \approx G$ such that each blue edge has trivial gain and no red edge has trivial gain.

Proof

The proof follows a similar method as Lemma 5.5. $\square$

Lemma 6.7

Let H be a balanced ${\mathbb {Z}}^2$-gain graph with no multiple edges and no loops. Then there exists a placement q of H in ${\mathbb {Z}}^2$ such that for all $(v,w,\gamma )\in E(H)$, $q(w)-q(v)=2\gamma$.

Proof

The proof follows the same method as Lemma 5.6. $\square$

We are now ready for our construction lemma for type 1 flexible 2-lattice NBAC-colourings. We note that it is essentially the same as the construction given in Lemma 5.7.

Lemma 6.8

Let G be a ${\mathbb {Z}}^2$-gain graph with a type 1 flexible 2-lattice NBAC-colouring $\delta$. Then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 2-periodic framework.

Proof

By Lemma 6.6, we may assume all blue edges of G have trivial gain and all red edges have non-trivial gain. Let $R_1,\ldots ,R_n$ be the red components of G and define $E_j$ to be the set of edges $(v,w,\gamma )$ in $G^\delta _{red }$ with $v,w \in R_j$. By Lemma 6.7, for each $R_j$ there exists a placement $q_j$ in ${\mathbb {R}}^2$ where $q_j(w)-q_j(v)=2\gamma$ for all $(v,w,\gamma )\in E_j$. By applying translations to each of the placements $q_j$, we may assume that for any blue edge $(v,w,0)\in E(G)$ with $v\in R_j$, $w\in R_k$ and $j\ne k$, we have $q_j(v)\ne q_k(w)$. We now define for each $t \in [0,2\pi ]$ the full placement-lattice $(p_t,L_t)$ of G in ${\mathbb {R}}^2$, with

$$\begin{aligned} L_t \cdot (1,0):= (-2 + \cos t, \sin t), \qquad L_t \cdot (0,1):= (\sin t, -2 - \cos t) \end{aligned}$$

and $p_t(v) := q_j(v)$ for $v \in R_j$. We shall denote $(p,L) := (p_0,L_0)$.

To see that (p, L) is a well-defined placement-lattice, choose any $e=(v,w,\gamma )$ with $\gamma =(\gamma _1,\gamma _2)$ and suppose that $p(v)=p(w)+L\cdot \gamma$. If $\delta (e)=red$, then $\gamma \ne (0,0)$ and $v,w\in R_j$ for some j. It follows that

$$\begin{aligned} -L\cdot \gamma =q_j(w)-q_j(v)=2\gamma . \end{aligned}$$

However as $-L\cdot \gamma = (\gamma _1, 3 \gamma _2)$, then $-L\cdot \gamma =2\gamma$ if and only if $\gamma =(0,0)$, contradicting that all red edges have non-trivial gain. If $\delta (e)=blue$, then $\gamma =(0,0)$. By our choice of placements $\{q_i:1\le i\le n\}$, we must have $v,w\in R_j$ for some j; furthermore, as $\gamma =(0,0)$ then $q_j(v)=q_j(w)$. Let $(e_1,\ldots ,e_{n-1})$ be a red path from w to v with $e_j=(v_j,v_{j+1},\gamma _j)\in E_j$, $v_1=w$ and $v_n=v$. Since $q_j(v)=q_j(w)$, we have $\sum _{j=1}^{n-1}\gamma _j=0$. However, this implies $(e_1,\ldots ,e_{n-1},e)$ is a balanced almost red circuit, contradicting that $\delta$ is a type 1 flexible 2-lattice NBAC-colouring.

Choose any edge $e=(v,w,\gamma )$ with $\gamma =(\gamma _1,\gamma _2)$. If $\delta (e)=blue$ then $\gamma =0$. As $p_t=p$ then for each $t\in [0,2\pi ]$,

$$\begin{aligned} \Vert p_t(v) - p_t(w) - L_t\cdot \gamma \Vert ^2 = \Vert p(v) - p(v) - L\cdot \gamma \Vert ^2. \end{aligned}$$

If $\delta (e) = red$ then $v,w \in R_j$, thus for each $t \in [0, 2 \pi ]$,

$$\begin{aligned} \Vert p_t(v) - p_t(w) - L_t\cdot \gamma \Vert ^2&=(\gamma _1 \cos t + \gamma _2 \sin t)^2 + (\gamma _1 \sin t - \gamma _2 \cos t)^2\\&=\gamma _1^2 + \gamma _2^2 \end{aligned}$$

It follows that $(p_t,L_t)$ is a flex of (G, p, L), as required. We refer the reader to Fig. 12 for an example of the construction. $\square$

Fig. 12

(Left): A ${\mathbb {Z}}^2$-gain graph with a type 1 flexible 2-lattice NBAC-colouring. (Right): The constructed full 2-periodic framework in ${\mathbb {R}}^2$

6.4 Constructing Flexible Frameworks: Type 2 Flexible 2-Lattice NBAC-Colourings

We recall that a type 2 flexible 2-lattice NBAC-colouring is an NBAC-colouring $\delta$ where there exist $\alpha ,\beta \in \mathbb Z^2$ such that:

• either $\alpha ,\beta$ are linearly independent or exactly one of $\alpha ,\beta$ is equal to (0, 0),

• ${{\,\mathrm{span}\,}}G^\delta _red$ is a non-trivial subgroup of ${\mathbb {Z}}\alpha$, or $\alpha =(0,0)$ and $G^\delta _red$ is balanced,

• ${{\,\mathrm{span}\,}}G^\delta _blue$ is a non-trivial subgroup of ${\mathbb {Z}}\beta$, or $\beta =(0,0)$ and $G^\delta _blue$ is balanced,

• there are no almost red circuits with gain in ${\mathbb {Z}}\alpha$, and

• there are no almost blue circuits with gain in ${\mathbb {Z}}\beta$.

Lemma 6.9

Let G be a ${\mathbb {Z}}^2$-gain graph and $\delta$ a type 2 flexible 2-lattice NBAC-colouring of G with $\alpha ,\beta$ as described previously. Suppose $\alpha \ne (0,0)$. Then there exists $G'\approx G$ such that each red edge has gain $a\alpha +b\beta$ for some $a,b\in {\mathbb {Z}}$ with $a\ne 0$, and each blue edge has gain $c\beta$ for some $c\in {\mathbb {Z}}$.

Proof

As ${{\,\mathrm{span}\,}}G^\delta _{blue }={\mathbb {Z}}\beta$, by Proposition 2.7, we may suppose all blue edges of G have gain in ${\mathbb {Z}}\beta$. Let $B_1,\ldots ,B_n$ be the blue components of G and choose $N\in {\mathbb {N}}$ such that $N>|a|$ for all $(v,w,\gamma )\in E(G)$ with $\gamma =a\alpha + b \beta$. We now define the gain equivalent graph

$$\begin{aligned} G' := \left( \prod _{i=1}^n \prod _{v \in B_i} \phi _v^{iN \alpha }\right) (G). \end{aligned}$$

We first note that any blue edge of $G'$ will have gain in $\mathbb Z\beta$ since both of its ends will lie in the same blue component. Choose a red edge $(v,w,\gamma )\in E(G)$ with $\gamma = a\alpha + b \beta$ and suppose $v \in B_i$ and $w \in B_j$. We note that

$$\begin{aligned} \left( \prod _{i=1}^n \prod _{v \in B_i} \phi _v^{iN \alpha } \right) (v,w,\gamma )&\!\!=\phi _v^{iN \alpha } \circ \phi _w^{jN \alpha }(v,w,\gamma )\\&\!\!=(v,w,(N(i-j) + a) \alpha + b \beta ). \end{aligned}$$

As $N >|a|$ and $i-j \in {\mathbb {Z}}$, we have $N(i-j)+a=0$ if and only if $a = 0$ and $i=j$. If this holds, then as $v,w\in B_i$, we can define an almost blue circuit containing v with red edge $(v,w,b\beta )$ and gain in ${\mathbb {Z}}\beta$ (as every blue edge has gain in ${\mathbb {Z}}\beta$), contradicting that $\delta$ is a type 2 flexible 2-lattice NBAC-colouring. It now follows that $a \ne 0$ as required. $\square$

Lemma 6.10

Let $\alpha ,\beta \in {\mathbb {Z}}^2$ be linearly independent and let H be a ${\mathbb {Z}}^2$-gain graph where ${{\,\mathrm{span}\,}}H$ is a subgroup of ${\mathbb {Z}}\alpha$. Then there exists a placement q of H in ${\mathbb {Z}}$ such that for all $(v,w,a \alpha +b \beta )\in E(H)$, $q(v) - q(w) = b$.

Proof

Define the ${\mathbb {Z}}$-gain graph $H'$ with vertex set $V(H') := V(H)$ and edge set

$$\begin{aligned} E(H') := \{ (v,w,b\beta ) : (v,w,a \alpha + b\beta ) \in E(H) \}; \end{aligned}$$

we delete any loops with trivial gain that may arrive, and note that multiple edges may become a single edge. By Lemma 5.6, we may define a placement $q'$ of $H'$ in ${\mathbb {Z}}$ such that $q'(v) - q'(w) = -2 b$ for all $(v,w,b\beta ) \in E(H')$. We now define q to be the placement of H where $q(v) := -q'(v)/2$. $\square$

We are now ready for our construction lemma for type 2 flexible 2-lattice NBAC-colourings.

Lemma 6.11

Let G be a ${\mathbb {Z}}^2$-gain graph with a type 2 flexible 2-lattice NBAC-colouring $\delta$. Then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 2-periodic framework.

Proof

Without loss of generality we may assume ${{\,\mathrm{span}\,}}G^\delta _{red }={\mathbb {Z}}\alpha$ and ${{\,\mathrm{span}\,}}G^\delta _{blue }={\mathbb {Z}}\beta$, with $\alpha \ne (0,0)$. If $\beta =(0,0)$ then $\delta$ is a fixed-lattice NBAC-colouring and the result holds by Lemma 4.6, thus we may assume $\alpha ,\beta$ are linearly independent.

By Lemma 6.9, we may assume all red edges have gain $a \alpha + b\beta$ for some $a,b\in {\mathbb {Z}}$ with $a\ne 0$, and all blue edges have gain $c\beta$ for some $c\in {\mathbb {Z}}$. Let $R_1,\ldots ,R_n$ be the red components of G and define $E_j$ to be the set of edges $(v,w,\gamma )$ in $G^\delta _{red }$ with $v,w\in R_j$. By Lemma 6.10, for each $R_j$ there exists a placement $q_j$ in ${\mathbb {R}}$ where $q_j(v)-q_j(w)=b$ for all $(v,w,\gamma )\in E_j$ with $\gamma =a\alpha +b\beta$. We now define for each $t\in [0,2\pi ]$ the full placement-lattice $(p_t,L_t)$ of G in ${\mathbb {R}}^2$ with

$$\begin{aligned} L_t \cdot \alpha := (\sin t, \cos t), \qquad L_t \cdot \beta := (1,0) \end{aligned}$$

and $p_t(v) := (q_j(v),j)$ for $v \in R_j$. We shall denote $(p,L) := (p_0,L_0)$.

To see that (p, L) is a well-defined placement-lattice, choose any $e=(v,w,\gamma )$ and suppose that $p(v)=p(w)+L\cdot \gamma$. If $\delta (e)=red$, then $\gamma = a\alpha + b \beta$ for some $a,b\in {\mathbb {Z}}\setminus \{0\}$ and $v,w\in R_j$ for some j. We note

$$\begin{aligned} p(v) = (q_j(v),j) = (q_j(w) + b, j + a) = p(w) + L\cdot \gamma , \end{aligned}$$

which implies $a=0$, a contradiction. If $\delta (e)=blue$, then $\gamma =b\beta$ for some $b \in {\mathbb {Z}}$. If $v\in R_j$ and $w\in R_k$ then

$$\begin{aligned} p(v) = (q_j(v),j) = (q_k(w) + b, k) = p(w) + L\cdot \gamma , \end{aligned}$$

therefore $j=k$. Let $P:=(e_1,\ldots ,e_{n-1})$ be a red path from w to v with $e_i = (v_i,v_{i+1}, \gamma _i) \in E_j$, $v_1=w$, $v_n=v$, $\gamma _i= a_i \alpha + b_i \beta$. Define $C := (e_1,\ldots ,e_{n-1}, e)$. As

$$\begin{aligned} b = q_j(v)-q_j(w) = \sum _{i=1}^{n-1}(q_j(v_{i+1}) - q_j(v_{i})) = - \sum _{i=1}^{n-1} b_i, \end{aligned}$$

we have $\psi (C) = a \alpha$ for some $a \in {\mathbb {Z}}$. This contradicts that $\delta$ is a type 2 flexible 2-lattice NBAC-colouring, as C is an almost red circuit with $\psi (C) \in {\mathbb {Z}} \alpha$.

Choose any edge $e = (v,w,\gamma )$ with $\gamma = a \alpha + b \beta$. If $\delta (e) = blue$ then $a = 0$. As $p_t = p$ and $L_t\cdot \beta =(1,0)$, $\Vert p_t(v) - p_t(w) - L_t\cdot \gamma \Vert ^2$ is constant. If $\delta (e) = red$ then $v,w \in R_j$, thus for each $t\in [0,2\pi ]$,

$$\begin{aligned} \Vert p_t(v) - p_t(w) - L_t\cdot \gamma \Vert ^2 =(q_j(v)- q_j(w) - b - a \cos t)^2 + (a \sin t)^2 = a^2. \end{aligned}$$

It follows that $(p_t,L_t)$ is a flex of (G, p, L) as required. We refer the reader to Fig. 13 for an example of the construction. $\square$

Fig. 13

(Left): A ${\mathbb {Z}}^2$-gain graph with a type 2 flexible 2-lattice NBAC-colouring ($\alpha = (1,0)$, $\beta = (0,1)$). (Right): The constructed full 2-periodic framework in ${\mathbb {R}}^2$

6.5 Conjectures Regarding Type 3 Flexible 2-Lattice NBAC-Colourings

We recall that an NBAC-colouring $\delta$ of a ${\mathbb {Z}}^2$-gain graph G is a type 3 flexible 2-lattice NBAC-colouring if there exists $\alpha \in {\mathbb {Z}}^2\setminus \{(0,0)\}$ such that

• ${{\,\mathrm{span}\,}}G^\delta _red$ and ${{\,\mathrm{span}\,}}G^\delta _red$ are non-trivial subgroups of ${\mathbb {Z}}\alpha$, and

• there are no almost monochromatic circuits with gain in ${\mathbb {Z}}\alpha$.

It is an open question whether the existence of a type 3 flexible 2-lattice NBAC-colouring implies the existence of a flexible placement of a ${\mathbb {Z}}^2$-gain graph in ${\mathbb {R}}^2$. As this is the case for all other types of flexible 2-lattice NBAC-colourings, we would conjecture the following.

Conjecture 2

Let G be a ${\mathbb {Z}}^2$-gain graph with type 3 flexible 2-lattice NBAC-colouring. Then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 2-periodic framework.

All examples of ${\mathbb {Z}}^2$-gain graphs with a type 3 flexible 2-lattice NBAC-colouring discovered so far will also have either a type 1 or type 2 flexible 2-lattice NBAC-colouring, a fixed lattice NBAC-colouring, or have a low rank. Due to this, we would also conjecture the following.

Conjecture 3

Let G be a ${\mathbb {Z}}^2$-gain graph with type 3 flexible 2-lattice NBAC-colouring. Then G has either a type 1 or type 2 flexible 2-lattice NBAC-colouring, G has a fixed lattice NBAC-colouring, or ${{\,\mathrm{rank}\,}}G<2$.

If Conjecture 2 is true, then by Lemmas 6.4, 6.8, 6.11, 4.7, and 6.5, we can deduce that Conjecture 1 would be also true. If Conjecture 3 is true, then we obtain the slightly stronger result.

Conjecture 4

Let G be a connected ${\mathbb {Z}}^2$-gain graph. Then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 2-periodic framework if and only if either:

• (i) G has a type 1 flexible 2-lattice NBAC-colouring,

• (ii) G has a type 2 flexible 2-lattice NBAC-colouring,

• (iii) G has a fixed lattice NBAC-colouring, or

• (iv) ${{\,\mathrm{rank}\,}}G<2$.

7 Special Cases of Flexible 2-Periodic Frameworks

We shall now focus on 2-periodic frameworks with loops. With this added assumption, we can fully characterise whether a ${\mathbb {Z}}^2$-gain graph has a flexible placement-lattice by observing the graph’s NBAC-colourings.

7.1 2-Periodic Frameworks with Loops

Lemma 7.1

Let (G, p, L) be a k-periodic framework in ${\mathbb {K}}^d$ and suppose G has a loop $(w,w,\alpha )$. If $G'$ is the ${\mathbb {Z}}^k$-gain graph with

$$\begin{aligned} V(G') := V(G), \qquad E(G') :=E(G) \cup \{ (v,v,c \alpha ) : v \in V(G),\,c \in {\mathbb {N}}\}, \end{aligned}$$

then

$$\begin{aligned} {\mathcal {V}}_{{\mathbb {K}}}(G',p,L) = {\mathcal {V}}_{{\mathbb {K}}}(G,p,L). \end{aligned}$$

Proof

First note that ${\mathcal {V}}_{{\mathbb {K}}}(G',p,L)\subset \mathcal V_{{\mathbb {K}}}(G,p,L)$. Choose any placement-lattice $(p',L')\in {\mathcal {V}}_{{\mathbb {K}}}(G,p,L)$. As $(w,w,\alpha ) \in E(G)$, then

$$\begin{aligned} \Vert L'\cdot \alpha \Vert ^2 = \Vert p'(w) - p'(w) - L'\cdot \alpha \Vert ^2 = \Vert p(w) - p(w) - L\cdot \alpha \Vert ^2 = \Vert L\cdot \alpha \Vert ^2. \end{aligned}$$

We note that for any $v \in V(G)$ and non-zero $c \in {\mathbb {Z}}$,

$$\begin{aligned} \Vert p'(v) - p'(v) - L'\cdot c\alpha \Vert ^2&\!\!= c^2 \Vert L'\cdot \alpha \Vert ^2 = c^2 \Vert L\cdot \alpha \Vert ^2\\&\!\!= \Vert p(v) - p(v) - L\cdot c\alpha \Vert ^2, \end{aligned}$$

thus $(p',L') \in {\mathcal {V}}_{{\mathbb {K}}}(G',p,L)$ as required. $\square$

Lemma 7.2

Let G be a connected ${\mathbb {Z}}^2$-gain graph and suppose that there exists some $\alpha \in {\mathbb {Z}}^2\setminus \{(0,0)\}$ such that for every vertex $v \in V(G)$ and $c \in {\mathbb {N}}$, we have $(v,v,c \alpha ) \in E(G)$. If $\delta$ is an NBAC-colouring of G, then every loop with gain $c\alpha$ for some $c \in {\mathbb {N}}$ is of the same colour.

Proof

We first note that every loop at a vertex must have the same colour. To see this, suppose there exists a loop $(v,v, c\alpha )$ for some integer $c>1$, where $\delta (v,v,n\alpha ) \ne \delta (v,v,\alpha )$. This would imply the circuit

$$\begin{aligned} \bigl ( \overbrace{(v,v,-\alpha ),\ldots ,(v,v,-\alpha )}^{\text {{ c} times}} , (v,v,c\alpha )\bigr ) \end{aligned}$$

is balanced and almost monochromatic, contradicting that $\delta$ is an NBAC-colouring.

Suppose not all loops are of the same colour. As G is connected, there must exist distinct vertices $v,w\in V(G)$ connected by an edge $(v,w,\gamma )$ where $\delta (v,v,\alpha )\ne \delta (w,w,\alpha )$. Without loss of generality we may assume $\delta (v,v,\alpha )=\delta (v,w,\gamma )$. The circuit

$$\begin{aligned} ( (v,w,\gamma ) ,(w,w,\alpha ), (w,v,-\gamma ), (v,v,-\alpha ) ) \end{aligned}$$

is balanced and almost monochromatic, contradicting that $\delta$ is an NBAC-colouring. $\square$

Lemma 7.3

Let G be a connected ${\mathbb {Z}}^2$-gain graph. Suppose that there exists some $\alpha \in {\mathbb {Z}}^2\setminus \{(0,0)\}$ such that for every vertex $v\in V(G)$ and $c\in {\mathbb {N}}$, we have $(v,v,c\alpha )\in E(G)$. Then there are no type 1 or type 3 flexible 2-lattice NBAC-colourings of G.

Proof

Suppose there exists an NBAC-colouring $\delta$ of G that is either a type 1 or type 3 flexible 2-lattice NBAC-colouring. As one of $G^\delta _{red }$ or $G^\delta _{blue }$ must contain a loop (and thus be unbalanced), $\delta$ must be a type 3 flexible 2-lattice NBAC-colouring. By Lemma 7.3, every loop of the form $(v,v,c \gamma )$ has the same colour, and without loss of generality we shall assume they are all red. We note immediately that there cannot be any unbalanced blue circuits; indeed, if C was a blue circuit containing v with gain $c\alpha$, then the circuit formed by C followed by $(v,v,-c\alpha )$ will be balanced and almost blue. However this implies ${{\,\mathrm{rank}\,}}G^\delta _{blue }=0$, contradicting that $\delta$ is a type 3 flexible 2-lattice NBAC-colouring. $\square$

Lemma 7.4

Let G be a connected ${\mathbb {Z}}^2$-gain graph with a loop. Then there are no active type 1 or type 3 flexible 2-lattice NBAC-colourings of G.

Proof

Let $(w,w,\alpha )$ be a loop of G. By Lemma 7.1, we may assume that for every vertex $v\in V(G)$ and $c\in {\mathbb {N}}$, we have $(v,v,c \alpha )\in E(G)$. The result now follows from Lemma 7.3. $\square$

We may now prove a special case of Conjecture 2.

Theorem 7.5

Let G be a connected ${\mathbb {Z}}^2$-gain graph with a loop. Then there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 2-periodic framework if and only if either:

• (i) G has a type 2 flexible 2-lattice NBAC-colouring,

• (ii) G has a fixed lattice NBAC-colouring,

• (iii) ${{\,\mathrm{rank}\,}}G=1$.

Proof

Suppose there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 2-periodic framework. Since G contains a loop, ${{\,\mathrm{rank}\,}}G\ge 1$. By Lemmas 6.4 and 7.4, either G has an active type 2 flexible 2-lattice NBAC-colouring, G has an active fixed lattice NBAC-colouring, or ${{\,\mathrm{rank}\,}}G=1$.

Now suppose that either G has a type 2 flexible 2-lattice NBAC-colouring, G has a fixed lattice NBAC-colouring, or ${{\,\mathrm{rank}\,}}G=1$. Then by Lemmas 6.11, 4.7, or 6.5, there exists a full placement-lattice (p, L) of G in ${\mathbb {R}}^2$ such that (G, p, L) is a flexible full 2-periodic framework. $\square$

7.2 Scissor Flexes

We now define a special class of flexes.

Definition 7.6

Let $(p_t,L_t)$ be a flex of a 2-periodic framework (G, p, L) in ${\mathbb {R}}^2$. If there exist linearly independent $\alpha ,\beta \in {\mathbb {Z}}^2$ such that $\Vert L_t\cdot \alpha \Vert ^2$ and $\Vert L_t\cdot \beta \Vert ^2$ are constant but $(L_t\cdot \alpha )\cdot (L_t\cdot \beta )$ is not constant, then $(p_t,L_t)$ is a scissor flex.

If ${{\,\mathrm{rank}\,}}G<2$, then it can be seen that some placement-lattice of G will have a scissor flex. We shall show in Theorem 7.10 that we can characterise the $\mathbb Z^2$-gain graphs with scissor flexes by their NBAC-colouring. We first prove the following lemmas.

Lemma 7.7

Let G be a connected ${\mathbb {Z}}^2$-gain graph and $\alpha ,\beta \in {\mathbb {Z}}^2$ be linearly independent. Suppose that $(v,v,c\alpha ),(v,v,c\beta )\in E(G)$ for all $v\in V(G)$ and $c \in {\mathbb {N}}$. If $\delta$ is an NBAC-colouring of G then either:

• (i) All loops of G are in the same colour.

• (ii) All loops of G with gain in ${\mathbb {Z}}\alpha$ are red (respectively, blue), all loops of G with gain in ${\mathbb {Z}}\beta$ are blue (respectively, red), and all loops of G have gain in ${\mathbb {Z}}\alpha \cup {\mathbb {Z}}\beta$.

Proof

By Lemma 7.2 we have (without loss of generality) two possibilities:

• (a) All loops with gain in ${\mathbb {Z}} \alpha \cup {\mathbb {Z}} \beta$ are red.

• (b) All loops with gain in ${\mathbb {Z}} \alpha$ are red and all loops with gain in ${\mathbb {Z}} \beta$ are blue.

Suppose (a) holds. If G only has loops with gain $\gamma \in {\mathbb {Z}}\alpha \cup {\mathbb {Z}}\beta$, then (i) holds. Suppose G has a loop $l:=(v,v,\gamma )$ with $\gamma \notin {\mathbb {Z}}\alpha \cup \mathbb Z\beta$. Let $a,b\in {\mathbb {Z}}\setminus \{0\}$ be any pair where $c\gamma =a\alpha +b\beta$ for some $c>0$. If $\delta (l)=blue$ then we note that the circuit

$$\begin{aligned} \bigl ((v,v,-a \alpha ),(v,v,-a \beta ),\overbrace{ l, \ldots , l}^{c \text { times}}\bigr ) \end{aligned}$$

is balanced and almost red, contradicting that $\delta$ is an NBAC-colouring. Hence $\delta (l)=red$ and (i) holds.

Suppose (b) holds but G has a loop $l :=(v,v,\gamma )$ with $\gamma \notin {\mathbb {Z}} \alpha \cup {\mathbb {Z}} \beta$. Choose $a,b\in {\mathbb {Z}}$ such that $c\gamma = a \alpha + b \beta$ for some $c>0$. If $\delta (l) = blue$ then the circuit

$$\begin{aligned} C:=\bigl ( (v,v,-a \alpha ),(v,v,-a \beta ),\overbrace{ l, \ldots , l}^{c \text { times}}\bigr ) \end{aligned}$$

is balanced and almost blue, while if $\delta (l) = red$ then C is balanced and almost red. As both possibilities contradict that $\delta$ is an NBAC-colouring, then no such loop may exist and (ii) holds. $\square$

Lemma 7.8

Let G be a connected ${\mathbb {Z}}^2$-gain graph with loops $l_\alpha := (v,v,\alpha )$, $l_\beta :=(v,v,\beta )$, where $\alpha$ and $\beta$ are linearly independent. Then all active NBAC-colourings of G with $\delta (l_\alpha )\ne \delta (l_\beta )$ are type 2 flexible 2-lattice NBAC-colourings.

Proof

Let $\delta$ be an active NBAC-colouring of G with $\delta (l_\alpha )\ne \delta (l_\beta )$. Without loss of generality, we may assume $\delta (l_\alpha )=red$ and $\delta (l_\beta )=blue$. By Lemma 7.1, we may assume that $(v,v,c \gamma ) \in E(G)$ for all $v \in V(G)$ and $c \in {\mathbb {N}}$, where $\gamma \in \{\alpha ,\beta \}$. By Lemma 7.7, all loops with gain in ${\mathbb {Z}} \alpha$ are red, all loops with gain in ${\mathbb {Z}}\beta$ are blue, and there are no loops with gain $\gamma \notin {\mathbb {Z}} \alpha \cup {\mathbb {Z}} \beta$.

Suppose there exists a red circuit C containing v with $\psi (C)=a\alpha + b \beta$. If $a,b\ne 0$, then the circuit formed from C followed by $(v,v,-a \alpha ),(v,v,-a \beta )$ is balanced and almost red, while if $a=0$, $b\ne 0$, then the circuit formed from C followed by $(v,v,-a \beta )$ is balanced and almost red. As both contradict that $\delta$ is an NBAC-colouring of G, then $\psi (C) \in {\mathbb {Z}} \alpha$. We similarly note that for any blue circuit $C'$, $\psi (C')\in {\mathbb {Z}}\beta$.

Let C be an almost monochromatic circuit of length n where $\delta (e_n) \ne \delta (e_i)$ for all $i \in \{1,\ldots ,n-1\}$. If C is almost red and $\psi (C) = c \alpha$ for some $c \in {\mathbb {Z}}$, then

$$\begin{aligned} ( e_1, \ldots ,e_n, (v_1,v_1,-c \alpha )) \end{aligned}$$

is a balanced almost red circuit, contradicting that $\delta$ is an NBAC-colouring. If C is almost blue and $\psi (C)=c\beta$ for some $c\in {\mathbb {Z}}$, then

$$\begin{aligned} ( e_1, \ldots ,e_n, (v_1,v_1,-c \beta )) \end{aligned}$$

is a balanced almost blue circuit, contradicting that $\delta$ is an NBAC-colouring. It now follows that $\delta$ is a type 2 flexible 2-lattice as required. $\square$

Lemma 7.9

Let G be a connected ${\mathbb {Z}}^2$-gain graph with loops $l_\alpha :=(v,v,\alpha )$, $l_\beta :=(v,v,\beta )$, where $\alpha$ and $\beta$ are linearly independent. If $\delta (l_\alpha )=\delta (l_\beta )$ for all active NBAC-colourings of G, then for any 2-periodic framework (G, p, L), every non-trivial flex of (G, p, L) is a fixed-lattice flex.

Proof

Let (G, p, L) be a flexible 2-periodic framework with a flex $(p_t,L_t)$, $t \in [0,1]$. Since we have loops $l_\alpha , l_\beta \in E(G)$, it follows that $\Vert L_t\cdot \alpha \Vert ^2 =\Vert L\cdot \alpha \Vert ^2$ and $\Vert L_t\cdot \beta \Vert ^2 =\Vert L\cdot \beta \Vert ^2$ for all $t \in [0,1]$. For each $t \in [0,1]$ we have

$$\begin{aligned} (L\cdot \alpha )\cdot (L\cdot \beta )&=(p(v) - p(v)-L\cdot \alpha )\cdot (p(v) - p(v) - L\cdot \beta ),\\ (L_t\cdot \alpha )\cdot (L_t\cdot \beta )&=(p_t(v)-p_t(v)-L_t\cdot \alpha )\cdot (p_t(v) - p_t(v) - L_t\cdot \beta ). \end{aligned}$$

By Proposition 3.20 and the continuity of the flex $(p_t,L_t)$, we must have $(L\cdot \alpha )\cdot (L\cdot \beta )=(L_t\cdot \alpha )\cdot (L_t\cdot \beta )$ for all $t\in [0,1]$. It now follows that $L_t\sim L$ for all $t\in [0,1]$ as required. $\square$

Theorem 7.10

Let G be a connected ${\mathbb {Z}}^2$-gain graph with ${{\,\mathrm{rank}\,}}G=2$. Then there exists a full 2-periodic framework (G, p, L) in ${\mathbb {R}}^2$ with a scissor flex if and only if either:

• (i) G has a type 2 flexible 2-lattice NBAC-colouring, or

• (ii) G has a type 1 flexible 2-lattice NBAC-colouring where, for some linearly independent pair $\alpha ,\beta \in {\mathbb {Z}}^2$, there are no almost red circuits of G with gain in ${\mathbb {Z}} \alpha$ and there are no almost blue circuits of G with gain in ${\mathbb {Z}}\beta$.

Proof

If G has a type 2 flexible 2-lattice NBAC-colouring, then there exists a full 2-periodic framework (G, p, L) with a scissor flex by Lemma 6.11. Suppose G has a type 1 flexible 2-lattice NBAC-colouring $\delta$ with no almost red circuits with gain in ${\mathbb {Z}}\alpha$ and no almost blue circuits with gain in ${\mathbb {Z}}\beta$. We note that if we add the loops $(v,v,\alpha )$ and $(v,v,\beta )$ to G to form the graph $G'$, then we can extend $\delta$ to a type 2 flexible 2-lattice NBAC-colouring $\delta '$ of $G'$ by setting $\delta '(v,v,\alpha )=red$ and $\delta '(v,v,\beta )=blue$. A full 2-periodic framework $(G',p,L)$ with a scissor flex can now be constructed by Lemma 6.11. We finish by noting that (G, p, L) will also have a scissor flex as required.

Now suppose there exists a full 2-periodic framework (G, p, L) with a scissor flex $(p_t,L_t)$; we shall assume that $\alpha ,\beta \in {\mathbb {Z}}^2$ are linearly independent gains where $\Vert L_t\cdot \alpha \Vert ^2$ and $\Vert L_t\cdot \beta \Vert ^2$ are both constant. Choose any $v\in V(G)$ and define $G'$ to be the ${\mathbb {Z}}^2$-gain graph formed from G by adding the loops $l_\alpha :=(v,v,\alpha )$ and $l_\beta :=(v,v,\beta )$. We note that $(p_t,L_t)$ is a flex of $(G',p,L)$ also, hence as ${{\,\mathrm{rank}\,}}G'=2$, we have that $G'$ has an active NBAC-colouring by Lemma 6.4.

If all active NBAC-colourings $\delta '$ of $G'$ have $\delta '(l_\alpha )=\delta '(l_\beta )$, then by Lemma 7.9, $(G',p,L)$ is fixed lattice flexible, a contradiction. It follows that $G'$ has an active NBAC-colouring $\delta '$ with $\delta '(l_\alpha )\ne \delta '(l_\beta )$. By Lemma 7.8, $\delta '$ is a type 2 flexible 2-lattice NBAC-colouring. If we define $\delta$ to be the restriction of $\delta '$ to G, then $\delta$ is a type k flexible 2-lattice NBAC-colouring for some $k\in \{1,2\}$, as ${{\,\mathrm{rank}\,}}G=2$ and $\delta '$ cannot be monochromatic on any subgraph of rank 2. We finish by noting that if $\delta$ is a type 1 flexible 2-lattice NBAC-colouring, then (with respect to $\delta$) there are no almost red circuits of G with gain in $\mathbb Z\alpha$ and there are no almost blue circuits of G with gain in ${\mathbb {Z}}\beta$. $\square$