The local loop lemma

Abstract

We prove that an idempotent operation generates a loop from a strongly connected digraph containing directed closed walks of all lengths under very mild (local) algebraic assumptions. Using the result, we reprove the existence of weakest non-trivial idempotent equations, and that a finite strongly connected digraph of algebraic length 1 compatible with a Taylor operation has a loop.

1 Introduction

Theorems that give a loop in a directed graph (digraph) under certain algebraic and structural assumptions play an important role in universal algebra and the constraint satisfaction problem. One example of such a “loop lemma” is the following one.

Theorem 1.1

(loop lemma) [1, 2]. If a finite digraph ${\mathbb {G}}$

• is weakly connected,

• is smooth (has no sources and no sinks),

• has algebraic length 1 (cannot be homomorphically mapped to a directed cycle of length at least 2) and

• is compatible with a Taylor operation,

then ${\mathbb {G}}$ contains a loop (a vertex adjacent to itself).

The consequences of this loop lemma include the following.

• [2] If a digraph ${\mathbb {G}}$ has no sources and no sinks, and ${\mathbb {G}}$ has a component that cannot be homomorphically mapped to a directed cycle of length at least 2, then the constraint satisfaction problem over ${\mathbb {G}}$ is NP-complete. This was an influential result generalizing the Hell-Nešetřil dichotomy for undirected graphs [8]. See [3] for a survey on the algebraic approach to constraint satisfaction problems.

• [9] Every locally-finite Taylor algebra has a term operation s satisfying $s(r,a,r,e) = s(a,r,e,a)$. Taylor algebras are of major significance in universal algebra, especially in tame congruence theory and in the study of Maltsev conditions. The fact that locally finite Taylor algebras can be characterized by such a simple condition was utterly unexpected in universal algebra, and a similar condition was later found for infinite Taylor algebras [10].

• [1] Every finite Taylor algebra ${\mathbf {A}}$ has cyclic terms of all prime number arities bigger than $|{\mathbf {A}}|$. This indirect application of the loop lemma ranks among the strongest characterizations of finite Taylor algebras.

The modern proof [1] of the loop lemma above requires idempotency of ${\mathbf {A}}$ and is based on absorption. An operation f is said to be idempotent if $f(x,x,\ldots ,x)=x$ for any x. The definition of absorption is slightly more complex. Let A be a set, X, Y subsets of A, and f an idempotent n-ary operation on A. We say that XabsorbsY with respect to f if, for any coordinate $i=0,\ldots ,n-1$ and any elements $x_0,x_1,\ldots ,x_{i-1},y,x_{i+1},\ldots ,x_{n-1}\in A$ such that $y\in Y$ and each $x_j\in X$, we have

$$\begin{aligned} f(x_0,x_1,\ldots ,x_{i-1},y,x_{i+1},\ldots ,x_{n-1})\in X. \end{aligned}$$

Another loop lemma based on absorption, which was used for the proof that there exist weakest non-trivial idempotent equations [10] and which drops the finiteness assumption, has the following form.

Theorem 1.2

Let ${\mathbb {G}}$ be an undirected graph that contains an odd cycle and is compatible with an idempotent operation f. Assume that for every non-isolated node $x\in {\mathbb {G}}$, the set of neighbors of x absorbs $\{x\}$ with respect to f. Then ${\mathbb {G}}$ has a loop.

The absorption assumption in Theorem 1.2 is not particularly strong. It is weaker than compatibility with a near unanimity operation, or absorption of the diagonal by the edges of ${\mathbb {G}}$, see Proposition 4.5 in [10]. On the other hand, it still requires some form of homogeneity – it has to be satisfied for every non-isolated node x, and there is further universal quantifier in the definition of absorption. The idea that such level of homogeneity may not be necessary was expressed by the following question in [10].

Question 1.3

Let ${\mathbb {G}}$ be an undirected graph, containing a cycle of odd length with an element a. Moreover, let f be an idempotent operation compatible with ${\mathbb {G}}$ such that the neighborhood of the node a absorbs $\{a\}$ with respect to f. Does ${\mathbb {G}}$ necessarily contain a loop?

Progress in this direction was made before. L. Barto has found a proof for finite graph ${\mathbb {G}}$, and also a general proof in the case of a cycle of length 3 was found. The main result of this paper is a version of the loop lemma under significantly weaker assumptions than the original question. This makes our “local loop lemma” one of the strongest, even among finite loop lemmata.

Theorem 1.4

(local loop lemma). Consider a set A, operation $t:A^n\rightarrow A$, a digraph ${\mathbb {G}}$ on A, and vertices $\alpha _{i,j}\in {\mathbb {G}}$ for $i,j\in \{0,\ldots ,n-1\}$ such that

• (1) t is idempotent,

• (2) ${\mathbb {G}}$ is compatible with t,

• (3) ${\mathbb {G}}$ is either a strongly connected digraph containing directed closed walks of all lengths starting with two, or ${\mathbb {G}}$ is an undirected connected non-bipartite graph,

• (4) for every $i \in \{0,\ldots ,n-1\}$, there is a ${\mathbb {G}}$-edge

  $$\begin{aligned} \alpha _{i,i} \rightarrow t(\alpha _{i,0}, \alpha _{i,1}, \ldots , \alpha _{i,n-1}). \end{aligned}$$

Then ${\mathbb {G}}$ contains a loop.

Proof of the positive answer to Question 1.3

Consider an element $x\in A$ in an odd cycle such that the neighborhood of x absorbs $\{x\}$. Then the component of x is closed under t (see Corollary 2.6 for detailed explanation), so we can restrict to that component. Item (4) is satisfied by putting $\alpha _{i,i} = x$ and $\alpha _{i,j}=y$ otherwise, where y is any element in the neighborhood of x. Then $t(y,\ldots ,y,x,y,\ldots ,y)$ is in the neighborhood by absorption, so

$$\begin{aligned} \alpha _{i,i} = x \rightarrow t(y,\ldots ,y,x,y,\ldots ,y) = t(\alpha _{i,0},\ldots ,\alpha _{i,n-1}). \end{aligned}$$

$\square$

Note that the absorption approach is not the only existing one used to tackle loop lemmata. The oldest method is based mostly on performing pp-definitions and pp-interpretations. This resulted in older, weaker versions of Theorem 1.1, see [6, 8], but also provided a state-of-the-art version of loop lemma for oligomorphic clones [4]. The most recent technique is based on a correspondence of certain loop lemmata with Maltsev conditions, see [7, 11, 12]. However, none of the available methods are local enough for our purposes. We have chosen a different approach, a blindly straightforward one. We provide a description of what exactly to plug into a star-power of the operation t to get a loop. Yet, such an approach appears to be among the most efficient ones.

1.1 Outline

In Section 2 we give proper definitions of the terms used, alongside with notation for finite sequences that will be used in the main proof. In Section 3 we prove our main result, Theorem 1.4. In Section 4, we prove a stronger local version of the existence of a weakest non-trivial equations, the main result from [10]. In Section 5, we obtain further strengthening of Theorem 1.4 that yields a version of Theorem 1.1 with a slightly stronger relational assumption (that ${\mathbb {G}}$ be a strongly connected digraph) but slightly weaker algebraic assumptions. In Section 6, we discuss possible further generalizations of the main result.

2 Preliminaries and notation

2.1 Words, integer intervals

Consider a set ${\mathcal {A}}$ representing an alphabet. By a word, we mean a finite sequence of elements in ${\mathcal {A}}$. The set of all words in the alphabet ${\mathcal {A}}$ of length n is denoted by ${\mathcal {A}}^n$. For manipulation with words, we use a Python-like syntax.

• ${\mathbf {x}} = [a_0, a_1, \ldots , a_{n-1}]$ represents a word of length n, The length of ${\mathbf {x}}$ is denoted by $|{\mathbf {x}}|$.

• Elements of the word ${\mathbf {x}}$ can be extracted using an index in square brackets after the word, that is ${\mathbf {x}}[i] = a_i$. The first position is indexed by zero. By a position in a word we mean an integer that represents a valid index.

• Words can be concatenated using symbol $+$, that is

  $$\begin{aligned} {[}a_0,\ldots ,a_{n-1}]+[b_0,\ldots ,b_{m-1}] = [a_0,\ldots ,a_{n-1},b_0,\ldots ,b_{n-1}]. \end{aligned}$$

• For $0\le i\le j\le n$ we define a subword

  $$\begin{aligned} {\mathbf {x}}[i:j] = [a_i, a_{i+1}, \ldots , a_{j-1}]. \end{aligned}$$

  This syntax is known in Python as slice notation. Notice that the interval includes i and does not include j, so then ${\mathbf {x}}[i:j] + {\mathbf {x}}[j:k] = {\mathbf {x}}[i:k]$ and $|{\mathbf {x}}[i:j]| = j-i$ for $0\le i\le j\le k\le |{\mathbf {x}}|$.

• If i or j is omitted, the boundaries of the word are used.

  $$\begin{aligned} {\mathbf {x}}[i:] = [a_i, \ldots , a_{n-1}], \quad {\mathbf {x}}[:j] = [a_0,\ldots ,a_{j-1}] \end{aligned}$$

• Inspired by the slice notation, we use single [i : j] to represent an integer interval. That is $[i:j] = \{i,i+1,\ldots ,j-1\}$, where i, j can be arbitrary integers. Notice that i is included in that interval while j is not. If i is omitted, it is meant implicitly as zero, that is $[:n] = \{0,1,\ldots ,n-1\}$. The set of all integers is denoted by ${\mathbb {Z}}$.

A word ${\mathbf {x}}$ is said to be periodic with a period $k\ge 1$, or briefly k-periodic, if ${\mathbf {x}}[i] = {\mathbf {x}}[i+k]$ whenever both i and $i+k$ are valid indices. Alternatively, ${\mathbf {x}}\in {\mathcal {A}}^n$ is k-periodic if $k\ge n$ or ${\mathbf {x}}[:n-k] = {\mathbf {x}}[k:]$. A 1-periodic word is also called a constant word. In our proof, we use the following well-known property of periodic words.

Proposition 2.1

(Periodicity lemma). Let a, b be positive integers and ${\mathbf {x}}$ be a word of length at least $a+b-\gcd (a,b)$. If ${\mathbf {x}}$ is both a-periodic and b-periodic, then it is also $\gcd (a,b)$-periodic.

Corollary 2.2

Let ${\mathbf {x}}$ be a word and $k\ge 2$ be the shortest period of ${\mathbf {x}}$. If ${\mathbf {y}}$ is a subword of ${\mathbf {x}}$ such that $|{\mathbf {y}}|\ge 2k-2$, then k is the shortest period of ${\mathbf {y}}$.

Proof The word ${\mathbf {y}}$ is k-periodic. To obtain a contradiction, let $k' \le k-1$ be another period of ${\mathbf {y}}$. Since $|{\mathbf {y}}|\ge k'+k-1$, the word ${\mathbf {y}}$ is $\gcd (k,k')$-periodic. Since $|{\mathbf {y}}|\ge k$ and ${\mathbf {y}}$ is a subword of the k-periodic word ${\mathbf {x}}$, we have that ${\mathbf {x}}$ is $\gcd (k,k')$-periodic, which contradicts the minimality of k. $\square$

2.2 Operations, star powers

For a given n-ary operation t and a non-negative integer k we recursively define the k-th star power of t, denoted $t^{*k}$, to be $n^k$-ary operation given by

$$\begin{aligned}&t^{*0}(x) = x, \\&t^{*(k+1)}(x_0,\ldots ,x_{n^{k+1}-1}) \\&\quad = t(t^{*k}(x_0,\ldots ,x_{n^k-1}),\ldots , t^{*k}(x_{(n-1)n^k},\ldots ,x_{n^{k+1}-1})). \end{aligned}$$

We consider variables in star powers as being indexed by words in $[:n]^k$, where the left-most letters corresponds to the outer-most position in the composition tree. More precisely, a substitution of variables in a star power $t^{*k}$ is represented by a function $f:[:n]^{k}\rightarrow A$. If $k=0$, then $t^{*0}(f) = f([])$. Otherwise, we can compute $t^{*k}(f)$ by

$$\begin{aligned} t^{*k}(f) = t\bigl (t^{*k}(f_0), t^{*k}(f_1), \ldots , t^{*k}(f_{n-1})\bigr ) \text { or } t^{*k}(f) = t^{*(k-1)}(f'), \end{aligned}$$

where $f_i, f':[:n]^{k-1}$ are defined by

$$\begin{aligned} f_i({\mathbf {x}}) = f([i]+{\mathbf {x}})\text { and } f'({\mathbf {x}}) = t\bigl (f({\mathbf {x}}+[0]), f({\mathbf {x}}+[1]), \ldots , f({\mathbf {x}}+[n-1])\bigr ). \end{aligned}$$

2.3 Equations

An equation in a signature $\Sigma$ is a pair of terms in $\Sigma$ written as $t_0 \approx t_1$. An equational condition${\mathcal {C}}$ is a system of equations in a fixed signature $\Sigma$. An algebra ${\mathbf {A}}$ (in any signature) is said to satisfy an equational condition ${\mathcal {C}}$ if it is possible to assign some term operations in ${\mathbf {A}}$ to the symbols in $\Sigma$ so that all the equations in ${\mathcal {C}}$ hold for any choice of variables in ${\mathbf {A}}$.

Equational conditions are thoroughly studied in universal algebra in the form of strong Maltsev conditions (equational conditions consisting of finitely many equations) and Maltsev conditions (an infinite disjunction of strong Maltsev conditions). Of particular interest are Taylor equations since every idempotent algebra satisfying a non-trivial Maltsev condition also have a term satisfying some Taylor system of equations. A Taylor system of equations is any system of n equations using an n-ary symbol t of the following form.

$$\begin{aligned} t(x,?,?,\ldots ,?,?)&\approx t(y,?,?,\ldots ,?,?), \\ t(?,x,?,\ldots ,?,?)&\approx t(?,y,?,\ldots ,?,?), \\&\vdots \\ t(?,?,?,\ldots ,?,x)&\approx t(?,?,?,\ldots ,?,y), \\ t(x,x,x,\ldots ,x,x)&\approx x, \end{aligned}$$

where each question mark stands for either x or y. A Taylor operation is any operation satisfying some Taylor system of equations. A quasi Taylor system of equations is a Taylor system of equations without the last one requiring idempotency. For our proofs, we enumerate the first n (quasi) Taylor equations from top to bottom by integers from 0 to $n-1$. For more background on universal algebra, we refer the reader to [5]. Note that it was recently proved [10] that the property of an algebra having a Taylor term can be characterized by a strong Maltsev condition. We reprove this fact in Section 4.

2.4 Relations, digraphs

An n-ary relation on a set A is any subset of $A^n$. A relation R is said to be compatible with an m-ary operation t, if for any words ${\mathbf {r}}_0, {\mathbf {r}}_1, \ldots , {\mathbf {r}}_{m-1}\in R$, the the result of $t({\mathbf {r}}_0, {\mathbf {r}}_1, \ldots , {\mathbf {r}}_{m-1})$ is in R as well, where the operation t is applied to ${\mathbf {r}}_0,\ldots {\mathbf {r}}_{m-1}$ component-wise. A relation is said to be compatible with an algebra ${\mathbf {A}}$ if it is compatible with all basic operations of ${\mathbf {A}}$, or algebraically, if it is a subuniverse of an algebraic power ${\mathbf {A}}^n$. Notice that if a relation R is compatible with an algebra ${\mathbf {A}}$, it is compatible with all term operations in ${\mathbf {A}}$. In particular, if R is compatible with an operation t, then R is compatible with any star power of t.

A relational structure ${\mathbb {R}} = (A,R_0,R_1\ldots )$ on A is the set A together with a collection of relations $R_0, R_1 \ldots$ on A. An algebra ${\mathbf {A}}$, or an operation t on A is compatible with a relational structure ${\mathbb {R}}$ on A, if ${\mathbf {A}}$, or t, is compatible with all the relations in ${\mathbb {R}}$.

A digraph ${\mathbb {G}} = (V,E)$ is a relational structure with a single binary relation. If the set E of edges is symmetric, we call ${\mathbb {G}}$ an undirected graph. Given a digraph ${\mathbb {G}} = (V,E)$, we usually denote the edges by $u\rightarrow v$ instead of $[u,v]\in E$. By a n-walk from $v_0$ to $v_n$, or simply a walk, we mean a sequence (word) of vertices in the digraph

$$\begin{aligned}{}[v_0, v_1, \ldots , v_n] \end{aligned}$$

such that $v_i\rightarrow v_{i+1}$ for all $i\in [:n]$. While we use most of the notation we have for words also for walks, we redefine a length of a walk to be n, that is one less than the length of the appropriate word of vertices. A closed walk of length n, or closed n-walk, is an n-walk ${\mathbf {w}}$ such that ${\mathbf {w}}[0] = {\mathbf {w}}[n]$.

The n-th relational power ${\mathbb {G}}^{\circ n}$ of a digraph ${\mathbb {G}}$ is a digraph with the same set of vertices, and $u\rightarrow v$ in ${\mathbb {G}}^{\circ n}$ if and only if there is a n-walk in ${\mathbb {G}}$ from u to v. Notice that if a digraph ${\mathbb {G}}$ is compatible with an algebra ${\mathbf {A}}$, any relational power of ${\mathbb {G}}$ is compatible with ${\mathbf {A}}$ as well.

A digraph is said to be strongly connected, if there is a walk from u to v for any pair of vertices u, v. We say that a digraph has an algebraic length 1 if it cannot be homomorphically mapped to a directed cycle of length greater than one.

We finish this section by proving some basic combinatorial properties of strongly connected digraphs of algebraic length 1.

Proposition 2.3

Let u be a vertex in a strongly connected digraph ${\mathbb {G}}$ with algebraic length 1. Then there are directed closed walks containing u of any sufficiently large length.

Proof First, observe that if all closed walks in ${\mathbb {G}}$ are divisible by some $n\ge 2$ and ${\mathbb {G}}$ is strongly connected, then ${\mathbb {G}}$ can be homomorphically mapped to the directed cycle of length n.

Therefore, since ${\mathbb {G}}$ has algebraic length 1, there are some closed walks ${\mathbf {c}}_0, \ldots {\mathbf {c}}_{k-1}$ such that the greatest common divisor of the lengths of the closed walks equals one. Let ${\mathbf {w}}_i$ denote a walk from u to ${\mathbf {c}}_i[0]$ and ${\mathbf {w}}'_i$ denote a walk from ${\mathbf {c}}_i[0]$ to u for every $i\in [:k]$. There is a closed walk starting in u of any length of the form

$$\begin{aligned}&|{\mathbf {w}}_0| + x_0|{\mathbf {c}}_0| + |{\mathbf {w}}'_0| + |{\mathbf {w}}_1| + x_1|{\mathbf {c}}_1| + |{\mathbf {w}}'_1| + \ldots \\&\quad \quad + |{\mathbf {w}}_{k-1}| + x_{k-1}|{\mathbf {c}}_{k-1}| + |{\mathbf {w}}'_{k-1}|, \end{aligned}$$

where $x_0,x_1,\ldots ,x_{k-1}$ stands for any non-negative integer coefficients. Since $\gcd (|{\mathbf {c}}_0|,\ldots ,|{\mathbf {c}}_{k-1}|)=1$, this number can reach every sufficiently large integer. $\square$

Proposition 2.4

If ${\mathbb {G}}$ is a finite strongly connected digraph with algebraic length 1, then there is an integer K such that there is a k-walk from $v_0$ to $v_1$ for any $v_0,v_1\in {\mathbb {G}}$ and $k\ge K$.

Proof Let $d(v_0, v_1)$ denote the length of the shortest walk from $v_0$ to $v_1$. Let d be the largest $d(v_0,v_1)$ among all pairs of vertices $v_0, v_1\in {\mathbb {G}}$. Fix an element $u\in {\mathbb {G}}$. By Proposition 2.3, there is a length C such that there is a closed c-walk from u to u of any length $c\ge C$. Thus the choice $K = d+C+d$ works for any pair $v_0, v_1$ since

$$\begin{aligned} k \ge K = d+C+d \ge d(v_0,u) + C + d(u, v_1). \end{aligned}$$

$\square$

Proposition 2.5

Let t be an idempotent n-ary operation compatible with a digraph ${\mathbb {G}}$. Let ${\mathbb {H}}\subseteq {\mathbb {G}}$ be a strongly connected component of ${\mathbb {G}}$ that has an algebraic length 1. Then ${\mathbb {H}}$ is closed under t.

Proof Fix a vertex $u\in {\mathbb {H}}$. By Proposition 2.3, there is a length C such that there are closed c-walks from u to u of any length $c\ge C$. Consider any $v_0,\ldots ,v_{n-1}\in {\mathbb {H}}$. We prove that there is a walk from u to $t(v_0,\ldots ,v_{n-1})$.

Let ${\mathbf {w}}_i$ denote a walk from u to $v_i$. There are also walks from u to $v_i$ of a fixed length

$$\begin{aligned} k = C + \max (|{\mathbf {w}}_0|, |{\mathbf {w}}_1|, \ldots , |{\mathbf {w}}_n|). \end{aligned}$$

Therefore, there is a k-walk from u to $t(v_0,\ldots ,v_{n-1})$ in ${\mathbb {G}}$ since t is idempotent and ${\mathbb {G}}^{\circ k}$ if compatible with t. The existence of the walk in the other direction is analogous. Hence $t(v_0,\ldots ,v_{n-1})\in {\mathbb {H}}$. Since $v_0,\ldots ,v_{n-1}$ can be chosen arbitrarily, ${\mathbb {H}}$ is closed under t. $\square$

Corollary 2.6

Let ${\mathbb {H}}$ be a non-bipartite connected component of an undirected graph ${\mathbb {G}}$ compatible with an idempotent operation t. Then ${\mathbb {H}}$ is closed under the operation t.

3 Proof of the local loop lemma

We prove the local loop lemma in the following form.

Theorem 3.1

(local loop lemma). Consider a set A, operation $t:A^n\rightarrow A$, a digraph ${\mathbb {G}}$ on A, and vertices $\alpha _{i,j}$ of ${\mathbb {G}}$ for $i,j\in \{0,\ldots ,n-1\}$ such that

• (1) t is idempotent,

• (2) ${\mathbb {G}}$ is compatible with t,

• (3) ${\mathbb {G}}$ is a strongly connected digraph containing closed walks of all lengths greater that one,

• (4) for every $i \in \{0,\ldots ,n-1\}$, there is a ${\mathbb {G}}$-edge

  $$\begin{aligned} \alpha _{i,i} \rightarrow t(\alpha _{i,0}, \alpha _{i,1}, \ldots , \alpha _{i,n-1}). \end{aligned}$$

Then ${\mathbb {G}}$ contains a loop.

Theorem 3.1 differs from Theorem 1.4 in item (3), where Theorem 1.4 allows also an undirected connected non-bipartite graph. We start by showing how Theorem 1.4 follows from Theorem 3.1,

Proof of Theorem 1.4

If ${\mathbb {G}}$ has closed walks of all lengths greater than one, we get a loop directly by Theorem 3.1. Assume that it does not, thus ${\mathbb {G}}$ is an undirected connected non-bipartite graph. Therefore, there is a cycle of odd length in ${\mathbb {G}}$. Let us denote the smallest odd length of such a cycle by l. To obtain a contradiction, assume that there is no loop in ${\mathbb {G}}$, hence $l\ge 3$. Observe that ${\mathbb {G}}$ contains closed walks of all lengths $l'\ge l-1$. There are closed walks of any even length—simply pick any edge [a, b], and construct the walk $[a,b,a,b,\ldots ,a]$. For constructing a closed walk of an odd length greater than $l-1$, start with a closed walk of length l around a cycle of length l and append a walk from the even case.

Consider the graph ${\mathbb {G}}' = {\mathbb {G}}^{\circ (l-2)}$. By minimality of l, ${\mathbb {G}}'$ does not have a loop. Since $l-2$ is an odd number and ${\mathbb {G}}$ is undirected, the edges of ${\mathbb {G}}^{\circ (l-2)}$ form a superset of the edge set of ${\mathbb {G}}$, hence ${\mathbb {G}}'$ satisfies item (4) of Theorem 3.1 about the $\alpha _{i,j}$. Compatibility of ${\mathbb {G}}'$ with t, that is item (2), follows from basic properties of relational powers. Since ${\mathbb {G}}$ contains a closed walk of every length greater than $l-2$, the digraph ${\mathbb {G}}'$ contains a closed walk of any length greater than 1. Therefore, by Theorem 3.1, there is a loop in ${\mathbb {G}}'$ corresponding to a closed walk of length $l-2$ in ${\mathbb {G}}$ which contradicts the minimality of l. $\square$

The proof of Theorem 3.1 relies on the following technical proposition.

Proposition 3.2

Let n be a positive integer and ${\mathcal {A}}$ denote [ : n]. Consider a strongly connected digraph ${\mathbb {G}}$ that contains closed walks of all lengths, and let $\alpha _{i,j}$ be any vertices of ${\mathbb {G}}$. Then there is a positive integer N and a mapping $f:{\mathcal {A}}^N \rightarrow G$ (substitution to the star power) such that for any ${\mathbf {x}}\in {\mathcal {A}}^N$ one of the following cases hold:

• (1) there is $i\in {\mathcal {A}}$ such that $f({\mathbf {x}}) = \alpha _{i,i}$ and

  $$\begin{aligned} \forall j\in {\mathcal {A}}:f({\mathbf {x}}[1:]+[j]) = \alpha _{i,j}, \end{aligned}$$

• (2) for every $i\in {\mathcal {A}}$, there is an ${\mathbb {G}}$-edge

  $$\begin{aligned} f({\mathbf {x}}) \rightarrow f({\mathbf {x}}[1:]+[i]). \end{aligned}$$

Proof of Theorem 3.1

Take the substitution function $f:{\mathcal {A}}^N\rightarrow {\mathbb {G}}$ given by Proposition 3.2. Based on that, we define two functions $f_0, f_1:{\mathcal {A}}^{N+1}\rightarrow {\mathbb {G}}$. We set $f_0({\mathbf {x}}) = f({\mathbf {x}}[:N])$ and $f_1({\mathbf {x}}) = f({\mathbf {x}}[1:])$. Let

$$\begin{aligned} f'_0({\mathbf {x}})&= t(f_0({\mathbf {x}}+[0]), \ldots , f_0({\mathbf {x}}+[n-1])),\\ f'_1({\mathbf {x}})&= t(f_1({\mathbf {x}}+[0]), \ldots , f_1({\mathbf {x}}+[n-1])). \end{aligned}$$

By the idempotency of t, the functions $f'_0$ and f are identical. Therefore

$$\begin{aligned} t^{*(N+1)}(f_0)&= t^{*N}(f'_0) = t^{*N}(f)\\&= t(t^{*N}(f),t^{*N}(f),\ldots ,t^{*N}(f)) = t^{*(N+1)}(f_1) \end{aligned}$$

We claim that there is an edge from $t^{*(N+1)}(f_0)$ to $t^{*(N+1)}(f_1)$. We verify the edge by checking for an edge from $f'_0({\mathbf {x}})$ to $f'_1({\mathbf {x}})$ for any ${\mathbf {x}}\in {\mathcal {A}}^N$. We analyze the two cases of the behavior of f on ${\mathbf {x}}$.

• (1) If there is $i\in {\mathcal {A}}$ such that $f({\mathbf {x}}) = \alpha _{i,i}$ and $f({\mathbf {x}}[1:]+[j]) = \alpha _{i,j}$ for all $j\in {\mathcal {A}}$, then $f'_0({\mathbf {x}}) = f({\mathbf {x}}) = \alpha _{i,i}$ and

  $$\begin{aligned} f'_1({\mathbf {x}}) = t(f({\mathbf {x}}[1:]+[0]), \ldots , f({\mathbf {x}}[1:]+[n-1])) = t(\alpha _{i,0},\ldots ,\alpha _{i,n-1}), \end{aligned}$$

  so there is an edge $f'_0({\mathbf {x}}) \rightarrow f'_1({\mathbf {x}})$ by the definition of $\alpha _{i,j}$.

• (2) If there is an edge

  $$\begin{aligned} f_0({\mathbf {x}}+[i]) = f({\mathbf {x}}) \rightarrow f({\mathbf {x}}[1:]+[i]) = f_1({\mathbf {x}}+[i]) \end{aligned}$$

  for every $i\in {\mathcal {A}}$, then by compatibility of t and ${\mathbb {G}}$, there is an edge $f'_0({\mathbf {x}}) \rightarrow f'_1({\mathbf {x}})$.

So there is an edge from $f'_0({\mathbf {x}})$ to $f'_1({\mathbf {x}})$ for any ${\mathbf {x}}\in {\mathcal {A}}^N$, consequently there is an edge from $t^{*(N+1)}(f_0)$ to $t^{*(N+1)}(f_1)$ and since $t^{*(N+1)}(f_0) = t^{*(N+1)}(f_1)$, it forms the desired loop. $\square$

Proposition 3.2 will be proved in the following two subsections. In Section 3.1 we explicitly define the function f, in Section 3.2 we prove that the function f satisfes the required properties. Before that, we reduce the problem to a finite case.

Lemma 3.3

Let ${\mathbb {G}}$ be a strongly connected digraph that contains a closed walk of every length greater than one. Let A be a finite set of vertices in ${\mathbb {G}}$. Then there is a finite subdigraph ${\mathbb {G}}'\subseteq {\mathbb {G}}$ that is strongly connected and contains a closed walk of every length greater than 1 and all elements of A.

Proof We start with a finite subdigraph ${\mathbb {G}}_0\subseteq {\mathbb {G}}$ with algebraic length one – it suffices to put any two coprime closed walks of ${\mathbb {G}}$ into ${\mathbb {G}}_0$ and connect them. Thus there is a length C such that ${\mathbb {G}}_0$ contains a closed c-walk for any $c\ge C$. We construct ${\mathbb {G}}'$ by adding the following edges and nodes into ${\mathbb {G}}_0$:

• one closed walk of every length in the interval [2 : C],

• all the vertices in A,

• paths connecting the elements in previous items to a fixed node in ${\mathbb {G}}_0$ and vice versa.

These are finitely many edges and vertices in total. The final ${\mathbb {G}}'$ is therefore finite while it meets the required criteria. $\square$

3.1 Construction of the substitution f

In this section, we construct a witness to the Proposition 3.2. In particular, we consider the digraph ${\mathbb {G}}$, positive integer n and vertices $\alpha _{i,j}$ and define an appropriate integer N and a function $f:{\mathcal {A}}^N\rightarrow {\mathbb {G}}$, where ${\mathcal {A}}$ denotes [ : n]. By Lemma 3.3, we can assume that ${\mathbb {G}}$ is finite. Consequently, we can use Proposition 2.4 and get K such that $K\ge 2$ and there are k-walks from $v_0$ to $v_1$ for any $v_0,v_1\in {\mathbb {G}}$ and $k\ge K$. For every $v_0,v_1,k$, we fix such a walk and denote it by ${\text {walk}}(v_0,v_1,k)$. We define the length N as $N=L+W+R$ (left, window, right), where

• $W = 3K-3$,

• $M = 2(K-1)\cdot n^W + (K-1)$.

• $R = M+K-1$,

• $L = R+K-2$,

The overall idea is to evaluate $f({\mathbf {x}})$ primarily by the “window” ${\mathbf {x}}[L:L+W]$, or to investigate the neighborhood of this window, if necessary. We start with constructing a priority function$\pi :{\mathcal {A}}^W\rightarrow {\mathbb {Z}}$ and a value function$\nu :{\mathcal {A}}^W\rightarrow {\mathbb {G}}$ of the following properties.

• (1) If ${\mathbf {w}} = [i,\ldots ,i]$ is a constant word, then $\nu ({\mathbf {w}}) = \alpha _{i,i}$ and $\pi ({\mathbf {w}}) = 0$.

• (2) If ${\mathbf {w}}$ is periodic with the shortest period $k \in [2:K]$, then $\pi ({\mathbf {w}})=R$ and there is a closed k-walk $[v_0,v_1,\ldots ,v_k]$ in ${\mathbb {G}}$ such that

  $$\begin{aligned} \nu ({\mathbf {w}}[i:]+{\mathbf {w}}[:i]) = v_i \end{aligned}$$

  for every $i\in [:n]$.

• (3) If ${\mathbf {w}}[:W-1]$ is constant but ${\mathbf {w}}$ is not, then $\pi ({\mathbf {w}}) = R$.

• (4) If ${\mathbf {w}}$ is not periodic with a period smaller than K and ${\mathbf {w}}[:W-1]$ is not constant, then $\pi ({\mathbf {w}})$ is negative.

• (5) $\pi$ is “injective on negative values”, that is, whenever $\pi ({\mathbf {w}}_0) = \pi ({\mathbf {w}}_1) < 0$, then ${\mathbf {w}}_0 = {\mathbf {w}}_1$.

The construction of such functions is straightforward. To satisfy conditions 1 and 3 we simply set the appropriate values of $\pi$ and $\nu$. Items 4 and 5 can be satisfied since there are infinitely many negative numbers and just finitely many possible words of length W. Finally, to meet the condition 2, for all $k\in [2:K]$, we partition the words with the smallest period k into groups that differ by a cyclic shift. Any such group can be arranged as ${\mathbf {w}}_0, {\mathbf {w}}_1, \ldots , {\mathbf {w}}_{k-1}$ where ${\mathbf {w}}_i = {\mathbf {w}}_0[i:] + {\mathbf {w}}_0[:i]$. For every such a group, we find a closed k-walk $[v_0,v_1\ldots ,v_k]$ in ${\mathbb {G}}$ and set $\nu ({\mathbf {w}}_i) = v_i$, $\pi ({\mathbf {w}}_i) = R$.

Now consider a word ${\mathbf {x}}\in {\mathcal {A}}^N$ of length N. Positions $p\in [:N-W+1]$ represent valid indices of subwords ${\mathbf {x}}[p:p+W]$ of length W. We define values $\nu _{{\mathbf {x}}}:[:N-W+1]\rightarrow {\mathbb {G}}$ and priorities $\pi _{{\mathbf {x}}}:[:N-W+1]\rightarrow {\mathbb {Z}}$ of such positions by

$$\begin{aligned} \nu _{{\mathbf {x}}}(p) = \nu ({\mathbf {x}}[p:p+W]),\quad \pi _{{\mathbf {x}}}(p) = \pi ({\mathbf {x}}[p:p+W]) \end{aligned}$$

with the following exceptions if ${\mathbf {x}}[p:p+W]$ is constant.

• Let $q\in [p:N-W+1]$ be the right-most position such that ${\mathbf {x}}[p:q+W]$ is constant. We redefine $\pi _{{\mathbf {x}}}(p)$ to be $\min (q-p, R-1)$ instead of zero.

• If $p \in [1:L+1]$, ${\mathbf {x}}[p-1:p-1+W+R]$ is a constant word $[i,\ldots ,i]$ and ${\mathbf {x}}[p-1+W+R] = j$, we redefine $\nu _{{\mathbf {x}}}(p)$ to be $\alpha _{i,j}$ instead of $\alpha _{i,i}$.

Based on the priority function $\pi _{{\mathbf {x}}}:[:N-W+1]\rightarrow {\mathbb {Z}}$, we define local maxima. A position $p\in [:N-W+1]$ is called a local maximum in ${\mathbf {x}}\in {\mathcal {A}}^N$ if either $\pi _{{\mathbf {x}}}(p)=R$, or $p\in [K-1:N-W-(K-1)+1]$ and $\pi _{{\mathbf {x}}}(p)\ge \pi _{{\mathbf {x}}}(q)$ whenever $|p-q| < K$.

We are finally ready to construct the function $f:{\mathcal {A}}^N \rightarrow {\mathbb {G}}$. If L is a local maximum in ${\mathbf {x}}$, we simply set $f({\mathbf {x}}) = \nu _{{\mathbf {x}}}(L)$. Otherwise, we find the closest local maxima to L from both sides. In particular let $p<L$ be the right-most local maximum before L, and let $q>L$ be the left-most local maximum after L. We claim that these positions exist and that $q-p\ge K$, these claims are proved in the following subsection. In that case we set

$$\begin{aligned} f({\mathbf {x}}) = {\text {walk}}(\nu _{{\mathbf {x}}}(p), \nu _{{\mathbf {x}}}(q), q-p)[L-p]. \end{aligned}$$

3.2 Proofs

In this section, we fill in the missing proofs in the construction. In particular, we prove the following.

• It is possible to find a local maximum on both sides of the position L in any ${\mathbf {x}}\in {\mathcal {A}}^N$ (Corollary 3.11).

• If L is not a local maximum and p, q are local maxima such that $p<L<q$, then $q-p\ge K$ (Corollary 3.6).

• The constructed mapping f meets the criteria given by Proposition 3.2 (Proposition 3.15).

Lemma 3.4

Let $p < q$ be local maxima in ${\mathbf {x}}$ such that $q-p < K$. Then $\nu _{{\mathbf {x}}}(p) = \nu _{{\mathbf {x}}}(q)\ge R-1$ and the subword ${\mathbf {x}}[p:q+W]$ is periodic with a period strictly less than K.

Proof Since both p, q are local maxima, $\nu _{{\mathbf {x}}}(p) = \nu _{{\mathbf {x}}}(q)$. First we prove that $\nu _{{\mathbf {x}}}(p)\ge 0$. To obtain a contradiction, suppose that $\nu _{{\mathbf {x}}}(p) < 0$. Then ${\mathbf {x}}[p:p+W] = {\mathbf {x}}[q:q+W]$ by injectivity of the function $\nu$ on negative values. Hence ${\mathbf {x}}[p:q+W]$ is periodic with a period $q-p < K$. This contradicts the hypothesis that $\nu _{{\mathbf {x}}}(p) < 0$.

Therefore $\nu _{{\mathbf {x}}}(p) \ge 0$, and both subwords ${\mathbf {w}}_0 = {\mathbf {x}}[p:p+W-1]$ and ${\mathbf {w}}_1 = {\mathbf {x}}[q:q+W-1]$ are periodic with periods less than K, let us denote their shortest periods $k_0$, $k_1$ respectively. Their intersection ${\mathbf {w}} = {\mathbf {x}}[q:p+W-1]$ has length at least

$$\begin{aligned} (W-1)-(K-1) = (K-1)+(K-1)-1 \ge k_0+k_1-\gcd (k_0, k_1), \end{aligned}$$

so it is $\gcd (k_0, k_1)$-periodic by Proposition 2.1. Since $|{\mathbf {w}}|\ge \max (k_0,k_1)$ and the subwords ${\mathbf {w}}_0$, ${\mathbf {w}}_1$ are $k_0$-periodic or $k_1$-periodic, they are uniquely determined by ${\mathbf {w}}$. Therefore, the whole subword ${\mathbf {x}}[p:q+W-1]$ is $\gcd (k_0, k_1)$-periodic and $\gcd (k_0, k_1) = k_0 = k_1$.

If ${\mathbf {x}}[p:q+W-1]$ is not constant, then $k_0 \ge 2$, and ${\mathbf {w}}_1$ is not constant. Since $\nu _{{\mathbf {x}}}(q)\ge 0$, the word ${\mathbf {x}}[q:q+W]$ is then periodic with a period less that K. By the same reasoning as above, the shortest period of ${\mathbf {x}}[q:q+W]$ is $k_0$ and the whole subword ${\mathbf {x}}[p:q+W]$ is $k_0$-periodic.

Otherwise, if ${\mathbf {x}}[p:q+W-1]$ is constant, then $R > \nu _{{\mathbf {x}}}(p) = \nu _{{\mathbf {x}}}(q)$, so ${\mathbf {x}}[q:q+W]$ is constant, and the whole subword ${\mathbf {x}}[p:q+W]$ is constant. Thus $\nu _{{\mathbf {x}}}(p) = \min (R-1, \nu _{{\mathbf {x}}}(q) + q-p)$, so $\nu _{{\mathbf {x}}}(p) = \nu _{{\mathbf {x}}}(q) = R-1$. $\square$

Corollary 3.5

Let $p_0,p_1$ be local maxima in a word ${\mathbf {x}}$ such that $p_0 \ge p_1+2$ and there is no other local maximum in the interval $[p_0+1:p_1]$. Then $p_1-p_0\ge K$.

Proof Conversely suppose that $p_1-p_0 < K$. By Lemma 3.4, ${\mathbf {x}}[p_0:p_1+W]$ is periodic with a period strictly less than K and $\pi _{{\mathbf {x}}}(p_0) = \pi _{{\mathbf {x}}}(p_1) \ge R-1$. If ${\mathbf {x}}[p_0:p_1+W]$ is constant, then $\pi _{{\mathbf {x}}}(p_0+1) = R-1$, otherwise $\pi _{{\mathbf {x}}}(p_0+1) = R$. In both cases, $p_0+1$ is a local maximum in the interval $[p_0+1:p_1]$ contrary to the hypotheses. $\square$

Corollary 3.6

Let ${\mathbf {x}}\in {\mathcal {A}}^N$ be a word such that L is not a local maximum in ${\mathbf {x}}$, and let p, q be local maxima such that $p<L<q$. Then $q-p\ge K$.

Lemma 3.7

Let $p\in [K-1:N-W-(K-1)+1]$ be such that ${\mathbf {x}}[p:p+W]$ is constant. If p is not a local maximum, then one of the following scenarios happen.

• (1) $\pi _{{\mathbf {x}}}(p) < R-1$ and ${\mathbf {x}}[p-1] = {\mathbf {x}}[p]$,

• (2) there is a local maximum $q > p$ such that $q-p < K$, ${\mathbf {x}}[p:q+W-1]$ is constant and different from ${\mathbf {x}}[q+W-1]$.

Proof Since p is not a local maximum, there is a position q such that $|p-q| < K$ and $\nu _{{\mathbf {x}}}(q) > \nu _{{\mathbf {x}}}(p)\ge 0$, hence ${\mathbf {x}}[q:q+W-1]$ is periodic with a period smaller than K. The subword ${\mathbf {x}}[q:q+W-1]$ has an intersection with the constant subword ${\mathbf {x}}[p:p+W]$ of length at least $(W-1)-(K-1) = 2K-3\ge K-1$. Therefore by periodicity, ${\mathbf {x}}[q:q+W-1]$ is constant as well.

We analyze two cases by the position of q.

• (1) If $q < p$, then $q+W-1 \in [p:p+W]$, so ${\mathbf {x}}[q:q+W]$ is still constant. Therefore $\pi _{{\mathbf {x}}}(q)\le R-1$, and consequently $\pi _{{\mathbf {x}}}(p) < R-1$. Moreover ${\mathbf {x}}[p] = {\mathbf {x}}[p-1]$ and we get the scenario (1).

• (2) If $q > p$, we show that ${\mathbf {x}}[q+W-1]$ differs from the constant on ${\mathbf {x}}[q:q+W-1]$, so the scenario (2) happens. If it did not, the whole subword ${\mathbf {x}}[p:q+W]$ would be constant, and $\nu _{{\mathbf {x}}}(p) = \min (R-1, \nu _{{\mathbf {x}}}(q) + q-p)$ would contradict $v_{{\mathbf {x}}}(q)> \nu _{{\mathbf {x}}}(p)$.

$\square$

Corollary 3.8

Let $p\in [K-1:N-W-(K-1)+1]$ be a position such that the subword ${\mathbf {x}}[p:p+W+(K-1)]$ is constant. Assume that ${\mathbf {x}}[p] \ne {\mathbf {x}}[p-1]$ or $\nu _{{\mathbf {x}}}(p) = R-1$. Then p is a local maximum.

Lemma 3.9

Consider positions $p_0, p_1\in [K-1:N-W+1]$ in a word ${\mathbf {x}}$ such that $p_1-p_0 \ge M$. If ${\mathbf {x}}[p_0:p_1+W]$ is not constant, there is a local maximum in ${\mathbf {x}}$ in the interval $[p_0:p_1+1]$.

Proof If there is no position $q\in [p_0:p_0+2(K-1)\cdot n^W+1]$ such that ${\mathbf {x}}[q:q+W]$ is constant, we find the local maximum by the following process. We start with the position $q_0 = p_0+(K-1)n^W$. While $q_i$ is not a local maximum, we find $q_{i+1}$ such that $|q_{i+1} - q_i| \le K-1$ and $\pi _{{\mathbf {x}}}(q_{i+1}) > \pi _{{\mathbf {x}}}(q_i)$. Observe that the positions $q_1, q_2, \ldots , q_{n^W}$ cannot escape the interval $[p_0:p_0+2(K-1)\cdot n^W+1]$. On the other hand, the process cannot have more than $n^W$ steps since the values $\pi _{{\mathbf {x}}}(p_i)$ form an increasing sequence which is made of at most $n^W$ negative values and one non-negative value R. So we will get to the local maximum eventually.

If there is a position $q\in [p:p+2(K-1)\cdot n^W+1]$ such that ${\mathbf {x}}[q:q+W]$ is constant, we find $q_0, q_1$ such that $p_0\le q_0\le q \le q_1 \le p_1$ and ${\mathbf {x}}[q_0:q_1+W]$ is the largest possible constant subword. If $q_1 < p_1$, then $\pi _{{\mathbf {x}}}(q_1+1) = R$, hence $q_1+1$ is a local maximum in $[p_0:p_1+1]$. Assume otherwise that $q_1 = p_1$. Since ${\mathbf {x}}[p_0:p_1+W]$ is not constant, we have $q_0 > p_0$. Since $p_1-q_0\ge M - 2(K-1)\cdot n^W = K-1$, $q_0$ is the desired local maximum by Corollary 3.8. $\square$

Corollary 3.10

Consider a position $p\in [K-1:L+2]$ in a word ${\mathbf {x}}$. Then there is a local maximum in the interval $[p:p+(R-1)+1]$.

Proof If ${\mathbf {x}}[p:p+R-1+W]$ is not constant, there is a local maximum by Lemma 3.9 since $R-1 \ge M$. If ${\mathbf {x}}[p:p+R-1+W]$ is constant, then $\nu _{{\mathbf {x}}}(p) = R-1$ and p is a local maximum by Corollary 3.8. $\square$

Corollary 3.11

Let ${\mathbf {x}}\in {\mathcal {A}}^N$ be a word such that L is not a local maximum in ${\mathbf {x}}$. Then there are a local maxima p, q in ${\mathbf {x}}$ such that $p<L<q$.

Proof We find p in the interval $[L-R+1:L+1]$ and q in the interval $[L:L+R]$ by Corollary 3.10. $\square$

Now, we are going to prove that the constructed mapping f satisfies the conditions given by Proposition 3.2. For that purpose, we investigate how functions $\pi _{{\mathbf {x}}}, \nu _{{\mathbf {x}}}$ relate to the functions $\pi _{{\mathbf {y}}}, \nu _{{\mathbf {y}}}$, where ${\mathbf {y}} = {\mathbf {x}}[1:]+[i]$ for some i.

Lemma 3.12

Let ${\mathbf {x}},{\mathbf {y}}\in {\mathcal {A}}^N$ be words such that ${\mathbf {y}}[:N-1] = {\mathbf {x}}[1:]$, and $p\in [2:N-W+1]$. Then $\nu _{{\mathbf {x}}}(p) = \nu _{{\mathbf {y}}}(p-1)$ or ${\mathbf {x}}[L:N]$ is constant and $p = L+1$.

Proof Clearly, ${\mathbf {x}}[p:p+W] = {\mathbf {y}}[p-1:(p-1)+W]$, so

$$\begin{aligned} \nu \bigl ({\mathbf {x}}[p:p+W]\bigr ) = \nu \bigl ({\mathbf {y}}[p-1:(p-1)+W]\bigr ). \end{aligned}$$

To prove the lemma, it remains to discuss the exceptional behavior of $\nu$ that assigns $\alpha _{i,j}$. Fix $i,j\in {\mathcal {A}}$. We claim that with the exception of $p=L+1$ and ${\mathbf {x}}[L:N]$ being constant, the following items are satisfied

• $p\le L$,

• ${\mathbf {x}}[p-1:p-1+W+R]$ is a constant word $[i,\ldots ,i]$,

• ${\mathbf {x}}[p-1+W+R] = j$.

if and only if the following items are satisfied

• $p-1\le L$,

• ${\mathbf {y}}[p-2:p-2+W+R]$ is a constant word $[i,\ldots ,i]$,

• ${\mathbf {y}}[p-2+W+R] = j$.

The forward implication is clear. The only case in which the backward implication could fail is when $p-1 \le L$ but $p\not \le L$, that is $p = L+1$. In that case, since ${\mathbf {y}}[p-2:p-2+W+R]$ is constant, we get that

$$\begin{aligned} {\mathbf {y}}[p-2:p-2+W+R]= & {} {\mathbf {y}}[L-1:L-1+W+R] = {\mathbf {x}}[L:L+W+R] \\= & {} {\mathbf {x}}[L:N] \end{aligned}$$

is constant as well. $\square$

Lemma 3.13

Let ${\mathbf {x}},{\mathbf {y}}\in {\mathcal {A}}^N$ be words such that ${\mathbf {y}}[:N-1] = {\mathbf {x}}[1:]$, and $p\in [1:N-W+1]$. If $p > L+1$ and ${\mathbf {y}}[p-1:N]$ is constant, then $\pi _{{\mathbf {y}}}(p-1) = \pi _{{\mathbf {x}}}(p)+1 \in [:R]$. Otherwise $\pi _{{\mathbf {y}}}(p-1) = \pi _{{\mathbf {x}}}(p)$.

Proof If ${\mathbf {x}}[p:p+W]$ is not constant, then

$$\begin{aligned} \pi _{{\mathbf {x}}}(p) = \pi ({\mathbf {x}}[p:p+W]) = \pi ({\mathbf {y}}[p-1:p-1+W]) = \pi _{{\mathbf {y}}}(p-1). \end{aligned}$$

If ${\mathbf {x}}[p:p+W]$ is constant but ${\mathbf {y}}[p-1:N]$ is not, there is $q\in [p-1+W:N-1]$ such that ${\mathbf {y}}[p-1:q]$ is constant but ${\mathbf {y}}[q+1]\ne {\mathbf {y}}[q]$. Therefore ${\mathbf {x}}[p:q+1]$ is constant and

$$\begin{aligned} \pi _{{\mathbf {x}}}(p)= & {} \min ((q+1)-(p+W), R-1) = \min (q-(p-1+W), R-1) \\= & {} \pi _{{\mathbf {y}}}(p-1). \end{aligned}$$

If ${\mathbf {y}}[p-1:N]$ is constant and $p \le L+1$, then $\pi _{{\mathbf {x}}}(p) = R-1 = \pi _{{\mathbf {y}}}(p-1)$. Finally, if ${\mathbf {y}}[p-1:N]$ is constant and $p > L+1$, then

$$\begin{aligned} \pi _{{\mathbf {y}}}(p-1) = N-(p-1) = (N-p)+1 = \pi _{{\mathbf {x}}}(p)+1\in [:R]. \end{aligned}$$

$\square$

Lemma 3.14

Let ${\mathbf {x}},{\mathbf {y}}\in {\mathcal {A}}^N$ be words such that ${\mathbf {y}}[:N-1] = {\mathbf {x}}[1:]$, and $p\in [K:N-W+1]$. If p is a local maximum in ${\mathbf {x}}$, then $p-1$ is a local maximum in ${\mathbf {y}}$. Conversely, if $p-1$ is a local maximum in ${\mathbf {y}}$ and p is not a local maximum in ${\mathbf {x}}$, then $p \ge L+2$ and there is a local maximum in ${\mathbf {x}}$ in the interval $[L+1:p]$.

Proof By Lemma 3.13, $\pi _{{\mathbf {x}}}(p) = R$ if and only if $\pi _{{\mathbf {y}}}(p-1) = R$, in that case both p and $p-1$ are local maxima. Assume otherwise, that is $\pi _{{\mathbf {x}}}(p) < R$, and $\pi _{{\mathbf {y}}}(p) < R$.

We first prove the forward implication by contradiction. Suppose that p is a local maximum in ${\mathbf {x}}$ but $p-1$ is not a local maximum in ${\mathbf {y}}$. We thus find a position q such that $|p-q|<K$, $\pi _{{\mathbf {x}}}(p)\ge \pi _{{\mathbf {x}}}(q)$ and $\pi _{{\mathbf {y}}}(p-1) \le \pi _{{\mathbf {y}}}(q-1)-1$. From Lemma 3.13, we obtain $\pi _{{\mathbf {x}}}(p-1) \ge \pi _{{\mathbf {x}}}(p)$ and $\pi _{{\mathbf {y}}}(q) \ge \pi _{{\mathbf {y}}}(q-1)-1$. This leads to a cycle in inequalities

$$\begin{aligned} \pi _{{\mathbf {x}}}(p)\ge \pi _{{\mathbf {x}}}(q) \ge \pi _{{\mathbf {y}}}(q-1)-1 \ge \pi _{{\mathbf {y}}}(p-1) \ge \pi _{{\mathbf {x}}}(p), \end{aligned}$$

so all the compared values must be equal.

Since $\pi _{{\mathbf {y}}}(q) \ne \pi _{{\mathbf {y}}}(q-1)$, ${\mathbf {y}}[q-1:N]$ is constant. Since $\pi _{{\mathbf {y}}}(p-1) = \pi _{{\mathbf {x}}}(q)\in [:R]$, also ${\mathbf {y}}[p-1:p-1+W]$ is constant, and consequently, ${\mathbf {y}}[p-1:N]$ is constant. Since $\pi _{{\mathbf {y}}}(q-1) > \pi _{{\mathbf {y}}}(p-1)$, we get $q < p$. On the other hand, since the priority increased at q but not at p, we get $p\le L+1<q$ by Lemma 3.13. Satisfying both is impossible.

Now we prove the second part of the lemma. Let us assume that $p-1$ is a local maximum in ${\mathbf {y}}$ but p is not a local maximum in ${\mathbf {x}}$. There are two possible reasons for p not being a local maximum in ${\mathbf {x}}$. Either $p > N-W-(K-1)$, or there is a position q such that $\nu _{{\mathbf {x}}}(q) > \nu _{{\mathbf {x}}}(p)$ and $|p-q| < K$.

If $p > N-W-(K-1)$, then $p = N-W-(K-1)+1$ and ${\mathbf {y}}[p-2:(p-1)+W]$ is not constant since $p-1$ is a local maximum in ${\mathbf {y}}$. Therefore ${\mathbf {x}}[L+1:p+W]$ is not constant, so there is a local maximum in the interval ${\mathbf {x}}[L+1:p+1]$ by Lemma 3.9 since $p-(L+1) = R-K+1 = M$. However, p is not a local maximum, so the maximum belongs to the interval $[L+1:p]$.

Now suppose that there is q such that $\nu _{{\mathbf {x}}}(q) > \nu _{{\mathbf {x}}}(p)$, and $|p-q| < K$. Since $p-1$ is a local maximum in ${\mathbf {y}}$, $\nu _{{\mathbf {y}}}(q-1) \le \nu _{{\mathbf {y}}}(p-1)$. Similar to the forward implication, we obtain the following identities from Lemma 3.13,

$$\begin{aligned} \nu _{{\mathbf {x}}}(q) = \nu _{{\mathbf {y}}}(q-1) = \nu _{{\mathbf {y}}}(p-1) = \nu _{{\mathbf {x}}}(p)+1. \end{aligned}$$

Moreover $\nu _{{\mathbf {y}}}(p-1)\in [:R]$ and ${\mathbf {y}}[p-1:N]$ is constant since $\nu _{{\mathbf {y}}}(p-1)\ne \nu _{{\mathbf {x}}}(p)$. Since $\nu _{{\mathbf {x}}}(q) = \nu _{{\mathbf {y}}}(q-1) = \nu _{{\mathbf {y}}}(p-1)$, ${\mathbf {x}}[q:q+W]$ is constant and $\nu _{{\mathbf {x}}}(q) = R-1$. We compute

$$\begin{aligned} \nu _{{\mathbf {x}}}(p) = \nu _{{\mathbf {y}}}(p-1)-1 = \nu _{{\mathbf {x}}}(q) - 1 = (R-1)-1 = R-2, \end{aligned}$$

therefore $p = N-(R-2) = L+2$. On the other hand, $q\le L+1$ since $\nu _{{\mathbf {x}}}(q) = \nu _{{\mathbf {y}}}(q-1)$. Therefore ${\mathbf {x}}[L+1:N]$ is constant and $L+1$ is a local maximum in ${\mathbf {x}}$ in the interval $[L+1:p]$. $\square$

Proposition 3.15

The function $f:{\mathcal {A}}^N\rightarrow {\mathbb {G}}$, as constructed in Section 3.1 is such that for any ${\mathbf {x}}\in {\mathcal {A}}^N$, one of the following cases happen:

• (1) there is $i\in {\mathcal {A}}$ such that $f({\mathbf {x}}) = \alpha _{i,i}$ and $f({\mathbf {x}}[1:]+[j]) = \alpha _{i,j}$ for all $j\in {\mathcal {A}}$,

• (2) for every $i\in {\mathcal {A}}$, there is an edge in ${\mathbb {G}}$

  $$\begin{aligned} f({\mathbf {x}}) \rightarrow f({\mathbf {x}}[1:]+[i]). \end{aligned}$$

Proof If ${\mathbf {x}}[L:N]$ is constant, the first case happens. In particular, $i = {\mathbf {x}}[L]$, $\pi _{{\mathbf {x}}}(L) = R-1$, L is a local maximum, and $\nu _{{\mathbf {x}}}(L) = \alpha _{i,i}$, so $f({\mathbf {x}}) = \alpha _{i,i}$. Let ${\mathbf {y}}$ denote ${\mathbf {x}}[1:]+[j]$. Thus $\pi _{{\mathbf {y}}}(L) = R-1$, L is a local maximum in ${\mathbf {y}}$ and we have $\nu _{{\mathbf {x}}}(L) = \alpha _{i,j}$ by the exceptional case for value $\nu _{{\mathbf {y}}}$.

If ${\mathbf {x}}[L:N]$ is not constant, we show that the second case happens. Let ${\mathbf {y}} = {\mathbf {x}}[1:]+[i]$. First, we prove the proposition if both L and $L+1$ are local maxima in ${\mathbf {x}}$. In this case $L-1$ and L are local maxima in ${\mathbf {y}}$ by Lemma 3.14. Also $\nu _{{\mathbf {y}}}(L) = \nu _{{\mathbf {x}}}(L+1)$ by Lemma 3.12. By Lemma 3.4, $\pi _{{\mathbf {x}}}(L) = \pi _{{\mathbf {x}}}(L+1)\ge 0$ and ${\mathbf {x}}[L:L+W+1]$ is periodic with a period smaller than K. We show that ${\mathbf {x}}[L:L+W+1]$ cannot be constant. Assume that the subword is constant to obtain a contradiction, then $\pi _{{\mathbf {x}}}(L) = \min (R-1, \pi _{{\mathbf {x}}}(L+1)+1)$. Since $\pi _{{\mathbf {x}}}(L) = \pi _{{\mathbf {x}}}(L+1)$, we get $\pi _{{\mathbf {x}}}(L+1) = R-1$, so ${\mathbf {x}}[L+1:(L+1)+W+(R-1)]$ is constant. That contradicts the hypothesis that ${\mathbf {x}}[L:N]$ is not constant. Therefore ${\mathbf {x}}[L:L+W+1]$ is periodic with a smallest period k such that $1<k<K$. Thus k is also the smallest period of words ${\mathbf {x}}[L:L+W]$ and ${\mathbf {x}}[L+1:L+1+W]$ by Corollary 2.2. By the definition of $\nu$, the vertices $\nu ({\mathbf {x}}[L:L+W])$ and $\nu ({\mathbf {x}}[L+1:L+W+1])$ are consecutive vertices on a closed walk of length k, so there is an edge

$$\begin{aligned} f({\mathbf {x}}) = \nu ({\mathbf {x}}[L:L+W]) \rightarrow \nu ({\mathbf {x}}[L+1:L+W+1]) = f({\mathbf {y}}). \end{aligned}$$

Now, let us assume that L or $L+1$ is not a local maximum in ${\mathbf {x}}$. Let $p_0$ be the right-most local maximum such that $p_0\le L$, and let $p_1$ be the left-most local maximum such that $p_1 > L$. Both $p_0$ and $p_1$ exist by Corollary 3.10, and $p_1 - p_0 \ge K$ by Corollary 3.5. By the choice of $p_0, p_1$, there is no local maximum strictly between $p_0, p_1$. Therefore by Lemma 3.14$p_0-1, p_0-1$ are local maxima in ${\mathbf {y}}$ and there is no local maximum between them. Since ${\mathbf {x}}[L:N]$ is not constant, $\nu _{{\mathbf {y}}}(p_0-1) = \nu _{{\mathbf {x}}}(p_0){\mathop {=}\limits ^{\mathrm{def}}}u_0$ and $\nu _{{\mathbf {y}}}(p_1-1) = \nu _{{\mathbf {x}}}(p_1){\mathop {=}\limits ^{\mathrm{def}}}u_1$ by Lemma 3.12. Finally, we get the desired edge

$$\begin{aligned} f({\mathbf {x}}) = \nu _{{\mathbf {x}}}(L) ={}&{\text {walk}}(u_0, u_1, p_1-p_0)[L-p_0]\\ \rightarrow {}&{\text {walk}}(u_0, u_1, p_1-p_0)[L-p_0+1] = \nu _{{\mathbf {y}}}(L) = f({\mathbf {y}}). \end{aligned}$$

$\square$

4 Double loop

The core of the paper describing the weakest nontrivial equations [10] is the proof that the existence of a Taylor term implies the existence of a double loop term, that is a term d satisfying the double loop equations:

$$\begin{aligned} d(xx,xxxx,yyyy,yy)&= d(xx,yyyy,xxxx,yy)\\ d(xy,xxyy,xxyy,xy)&= d(yx,xyxy,xyxy,yx) \end{aligned}$$

(the variables are grouped together for better readability). The double loop equations can be obtained as follows. Consider a $4 \times 12$ matrix whose columns are all the quadruples $[a_0,a_1,b_0,b_1] \in \{x,y\}^4$ with $a_0 \ne a_1$ or $b_0 \ne b_1$, and let ${\mathbf {r}}_0,{\mathbf {r}}_1,{\mathbf {r}}_2,{\mathbf {r}}_3$ denote its rows. The double loop equations are then $d({\mathbf {r}}_0) \approx d({\mathbf {r}}_1)$ and $d({\mathbf {r}}_2) \approx d({\mathbf {r}}_3)$. If the columns are organized lexicographically with $x < y$, we get the equations above.

The fact that a Taylor term implies a double loop term is proved in [10] by intermediate steps in the form of the infinite loop lemma (Theorem 4.3 in [10]) followed by the double loop lemma (Theorem 5.2 in [10]). We provide a local version of that procedure by replacing the infinite loop lemma by the local loop lemma. Not only makes this change the proof of the double loop lemma more straightforward but we also prove a stronger, “local” version of the main theorem: If an idempotent algebra satisfies Taylor equations locally on X, it satisfies the double loop equations locally on X. The notion of a locally satisfied equational condition is defined below.

Definition 4.1

Let ${\mathbf {A}}$ be an algebra with a subset $X\subseteq {\mathbf {A}}$. Let ${\mathcal {S}}$ be an equational condition. We say that ${\mathbf {A}}$ satisfies ${\mathcal {S}}$ locally on X if it is possible to assign term operations in ${\mathbf {A}}$ to the term symbols in ${\mathcal {S}}$ so that every equation is satisfied whenever the variables are chosen from the set X.

Note that if X is the universe of ${\mathbf {A}}$, then ${\mathbf {A}}$ satisfying ${\mathcal {S}}$ locally on X just means that ${\mathbf {A}}$ satisfies ${\mathcal {S}}$ as an equational condition.

Theorem 4.2

(Local double loop lemma). Let ${\mathbf {A}} = (A; t^{\mathbf {A}})$ and ${\mathbf {B}} = (B; t^{\mathbf {B}})$ be algebras in the signature consisting of a single n-ary operation symbol t. Assume that ${\mathbf {A}}$ is generated by $\{x^{\mathbf {A}},y^{\mathbf {A}}\}$, $t^{\mathbf {A}}$ is idempotent, ${\mathbf {B}}$ is generated by $\{x^{\mathbf {B}},y^{\mathbf {B}}\}$ and $t^{\mathbf {B}}$ satisfies the quasi Taylor system of equations locally on $\{x^{\mathbf {B}},y^{\mathbf {B}}\}$. Let Q be the subuniverse of ${\mathbf {A}}^2\times {\mathbf {B}}^2$ generated by all the 12 quadruples $[a_0,a_1,b_0,b_1]$ with $a_0,a_1\in \{x^{\mathbf {A}},y^{\mathbf {A}}\},\; b_0,b_1\in \{x^{\mathbf {B}},y^{\mathbf {B}}\}$, such that $a_0\ne a_1$ or $b_0\ne b_1$. Then there is a double loop in Q, that is, a quadruple $[a,a,b,b]\in Q$.

Proof We assume that $x^{\mathbf {A}}\ne y^{\mathbf {A}}$ and $x^{\mathbf {B}}\ne y^{\mathbf {B}}$, otherwise, the theorem is trivial. Let us define a digraph ${\mathbb {G}} = (A,E)$ on A by

$$\begin{aligned} E = \{[a_0,a_1]\in A^2 \mid \exists b\in B:[a_0,a_1,b,b]\in Q\}. \end{aligned}$$

Observe that since the generators of Q are symmetric in the first two coordinates, so is the Q itself, and consequently ${\mathbb {G}} = (A,E)$ is an undirected graph. Clearly $[x^{\mathbf {A}},y^{\mathbf {A}}]\in E$. Our goal is to apply Theorem 1.4 to ${\mathbb {G}}$. $\square$

Claim 4.3

Consider elements $a_0,\ldots ,a_{n-1},a'_0,\ldots ,a'_{n-1}\in \{x^{\mathbf {B}}, y^{\mathbf {B}}\}$ such that there is exactly one $i\in [:n]$ such that $a_i = a'_i$. Then there is a ${\mathbb {G}}$-edge

$$\begin{aligned} t^{{\mathbf {A}}}(a_0,\ldots ,a_{n-1})\rightarrow t^{{\mathbf {A}}}(a'_0,\ldots ,a'_{n-1}) \end{aligned}$$

To verify the claim, we use the Taylor equation number i, that is

$$\begin{aligned} t^{{\mathbf {B}}}(b_0, \ldots , b_{n-1}) = t^{{\mathbf {B}}}(b'_0, \ldots , b'_{n-1}) \end{aligned}$$

for some $b_o,\ldots ,b_{n-1},b'_0,\ldots ,b'_{n-1}\in \{x^{{\mathbf {B}}},y^{{\mathbf {B}}}\}$ where $b_i = x^{{\mathbf {B}}}$ and $b'_i = y^{{\mathbf {B}}}$. Since $b_i\ne b'_i$ and $a_j\ne a'_j$ for every $j\ne i$, we have $[a_j,a'_j,b_j,b'_j]\in Q$ for every $j\in [:n]$. Therefore

$$\begin{aligned} \bigl [ t(a_0,\ldots ,a_{n-1}), t(a'_0,\ldots ,a'_{n-1}), t(b_0,\ldots ,b_{n-1}), t(b'_0,\ldots ,b'_{n-1}) \bigr ]\in Q, \end{aligned}$$

which satisfies the claim.

Due to Claim 4.3, there is a closed walk of length $2n-1$ in ${\mathbb {G}}$ containing $x^{{\mathbf {A}}}$:

By Corollary 2.6, the component of ${\mathbb {G}}$ containing $x^{{\mathbb {A}}}$ is closed under $t^{\mathbf {A}}$. However, since this component contains also $y^{{\mathbb {A}}}$ and $\{x^{{\mathbb {A}}},y^{{\mathbb {A}}}\}$ generates ${\mathbf {A}}$, the component covers all of ${\mathbb {G}}$, hence ${\mathbb {G}}$ is connected. Finally, we set $\alpha _{i,i} = x^{{\mathbf {A}}}$ and $\alpha _{i,j} = y^{{\mathbf {A}}}$ if $i\ne j$. The edges

$$\begin{aligned} x^{{\mathbf {A}}} \rightarrow t(y^{{\mathbf {A}}},\ldots ,y^{{\mathbf {A}}}, x^{{\mathbf {A}}},y^{{\mathbf {A}}},\ldots ,y^{{\mathbf {A}}}) \end{aligned}$$

are direct consequences of Claim 4.3 and the idempotency of t. All the assumptions of Theorem 1.4 are verified, so there is a loop $[a,a]\in E$. By the definition of E, there is a double loop $[a,a,b,b]\in Q$. $\square$

Theorem 4.4

Let ${\mathbf {A}}$ be an idempotent algebra that satisfies Taylor equations locally on X. Then ${\mathbf {A}}$ satisfies double loop equations locally on X.

Proof We construct a “local free algebra” ${\mathbf {F}}$ with the signature of ${\mathbf {A}}$ generated by two generators. The universe F of ${\mathbf {F}}$ consists of all the binary operations $X^2\rightarrow {\mathbf {A}}$ that can be expressed by a term in ${\mathbf {A}}$. The operations on ${\mathbf {F}}$ are naturally inherited from the basic operations on ${\mathbf {A}}$ by the left composition. Thus ${\mathbf {F}}$ is an idempotent algebra generated by the binary projections. Let us denote the binary projections x, y respectively. Since ${\mathbf {A}}$ satisfies some Taylor equations locally on X and the images of the functions x, y equals to X, ${\mathbf {F}}$ satisfies the same Taylor equations locally on $\{x, y\}$.

Let $Q\subseteq F^4$ be a 4-ary relation on F generated by all the quadruples $[a_0,a_1,b_0,b_1]$, where $a_0,a_1,b_0,b_1\in \{x, y\}$ and $a_0\ne a_1$ or $b_0\ne b_1$. By Theorem 4.2, there is a double loop $[a,a,b,b]\in Q$. Therefore, there is a term d in the signature of ${\mathbf {A}}$ that takes the generators of Q and returns [a, a, b, b]. In particular

$$\begin{aligned} d(xx,xxxx,yyyy,yy)&= a,\\ d(xx,yyyy,xxxx,yy)&= a,\\ d(xy,xxyy,xxyy,xy)&= b,\\ d(yx,xyxy,xyxy,yx)&= b. \end{aligned}$$

Thus d satisfies the double loop equations if we plug in x, y in the order above. However, whenever we choose a pair $[z_0,z_1]\in X^2$, then $[x(z_0,z_1), y(z_0,z_1)] = [z_0, z_1]$, hence d satisfies the double loop equations on ${\mathbf {A}}$ if we plug in $z_0, z_1$ in that order. Since $z_0, z_1$ can be any pair of elements of X, ${\mathbf {A}}$ satisfies the double loop equations locally on X. $\square$

5 Strong local loop lemma

In this section, we obtain a strengthening of the local loop lemma by replacing (4) in Theorem 1.4 with a weaker condition. We then use the strengthened version to reprove a finite loop lemma for strongly connected digraphs, in particular, Theorem 7.2 in [2]

For a given n-ary term $t:A^n\rightarrow A$ and a coordinate $i\in [:n]$, we define a digraph ${\mathbb {P}}(t,i)$ on A by $x_i\rightarrow t(x_0,x_1,\ldots ,x_{n-1})$ for all possible values $x_0,\ldots ,x_{n-1}\in A$. Using the digraphs ${\mathbb {P}}(t,i)$, assumption (4) in Theorem 1.4 can be expressed as: “For every $i\in [:n]$, the digraph ${\mathbb {P}}(t,i)$ has a common edge with ${\mathbb {G}}$.”

Let $\overline{{\mathbb {P}}(t,i)}$ denote the transitive closure of ${\mathbb {P}}(t,i)$, that is, an edge $u\rightarrow v$ in $\overline{{\mathbb {P}}(t,i)}$ indicates a walk from u to v in ${\mathbb {P}}(t,i)$. Using this notation, Theorem 1.4 has the following generalization.

Theorem 5.1

Consider a set A, operation $t:A^n\rightarrow A$, a digraph ${\mathbb {G}}$ on A, and elements $a_i,b_i\in {\mathbb {G}}$ for $i\in [:n]$ such that

• (1) t is idempotent,

• (2) ${\mathbb {G}}$ is compatible with t,

• (3) ${\mathbb {G}}$ is either a strongly connected digraph containing closed walks of all lengths greater than one, or ${\mathbb {G}}$ is an undirected connected non-bipartite graph,

• (4) for every $i \in [:n]$, there is a common edge $a_i\rightarrow b_i$ in ${\mathbb {G}}$ and $\overline{{\mathbb {P}}(t,i)}$.

Then ${\mathbb {G}}$ contains a loop.

Proof As in Proposition 3.2, we denote [ : n] by ${\mathcal {A}}$. By the idempotency of t, the edges of ${\mathbb {P}}(t,i)$ form a reflexive relation. Therefore, there is a fixed k such that there is a ${\mathbb {P}}(t,i)$-walk of length k from $a_i$ to $b_i$ for every $i\in {\mathcal {A}}$. For every $i\in {\mathcal {A}}$, fix a substitution $f_i:{\mathcal {A}}^k\rightarrow {\mathbb {G}}$ such that $f_i([i,i,\ldots ,i]) = a_i$ and $t^{*k}(f_i) = b_i$.

We verify the assumptions of Theorem 1.4 considering the operation $t^{*(k-1)n+1}$. The operation $t^{*(k-1)n+1}$ is idempotent, compatible with ${\mathbb {G}}$, and ${\mathbb {G}}$ already satisfies the relational requirements. It remains to find the values $\alpha _{{\mathbf {x}}, {\mathbf {y}}}$, for ${\mathbf {x}},{\mathbf {y}} \in {\mathcal {A}}^{(k-1)n+1}$ to make the condition (4) satisfied. We interpret the matrix $\alpha$ as a sequence of functions in the second variable, that is $\alpha _{{\mathbf {x}}, {\mathbf {y}}} = \alpha _{\mathbf {x}}({\mathbf {y}})$. We need to find functions $\alpha _{{\mathbf {x}}}$ such that there are a ${\mathbb {G}}$-edges

$$\begin{aligned} \alpha _{{\mathbf {x}}}({\mathbf {x}}) \rightarrow t^{*(k-1)n+1}(\alpha _{{\mathbf {x}}}). \end{aligned}$$

Take ${\mathbf {x}}\in {\mathcal {A}}^{(k-1)n+1}$. By the pigeonhole principle, there is $i\in {\mathcal {A}}$ occuring at least k-times in ${\mathbf {x}}$. Let $p_0,\ldots ,p_{k-1}\in [:(k-1)n+1]$ be an increasing sequence of positions in ${\mathbf {x}}$ such that ${\mathbf {x}}[p_j] = i$ for every $j\in [:k]$. We define $\alpha _{{\mathbf {x}}}$ by

$$\begin{aligned} \alpha _{{\mathbf {x}}}({\mathbf {y}}) = f_i([{\mathbf {y}}[p_0], {\mathbf {y}}[p_1], \ldots , {\mathbf {y}}[p_{k-1}]]). \end{aligned}$$

Thus

$$\begin{aligned} \alpha _{{\mathbf {x}}}({\mathbf {x}}) = f_i([i,i,\ldots ,i])&= a_i,\\ t^{*(k-1)n+1}(\alpha _{\mathbf {x}}) = t^{*k}(f_i)&= b_i, \end{aligned}$$

Therefore the assumption (4) of Theorem 1.4 is satisfied by $a_i\rightarrow b_i$, and ${\mathbb {G}}$ has a loop. $\square$

From Theorem 5.1 we obtain the following finite version.

Theorem 5.2

Let A be a finite set and $t:A^n\rightarrow A$ be an idempotent operation. Assume that for every $i\in [:n]$ and every pair $u,v\in A$, there is $w\in A$ such that there are edges $u\rightarrow w$ and $v\rightarrow w$ in $\overline{{\mathbb {P}}(t,i)}$. Then every digraph ${\mathbb {G}}$ that is strongly connected, compatible with t and has algebraic length 1, has a loop.

Proof Fix $i\in [:n]$. We start by proving the following claim by induction on |X|. $\square$

Claim 5.3

For every $X\subseteq A$, there is an element b such that for every $x\in X$, there is an edge $x\rightarrow b$ in $\overline{{\mathbb {P}}(t,i)}$.

If X is empty, it suffices to take any $b\in A$. Otherwise let $X = X'\cup \{x\}$, where the claim is already proven for $X'$, so there is $b'$ such that there is an edge $x'\rightarrow b'$ for every $x'\in X'$. Using the assumption of the theorem and putting $u=b'$, $v=x$, we get a vertex $w = b$ such that there are edges $b'\rightarrow b$, $x\rightarrow b$. By transitivity of $\overline{{\mathbb {P}}(t,i)}$, there are edges $x\rightarrow b$ for every $x\in X$. This finishes the proof of the claim.

For every $i\in [:n]$, we fix $b_i\in A$ such that there is an edge $x\rightarrow b_i$ in $\overline{{\mathbb {P}}(t,i)}$ for every $x\in A$. Consider a strongly connected digraph ${\mathbb {G}}$ with algebraic length 1 that is compatible with t. To obtain a contradiction, suppose that there is no closed walk of length 1 (a loop) in ${\mathbb {G}}$. Since ${\mathbb {G}}$ is a strongly connected digraph with algebraic length 1, it contains closed walks of all sufficiently large lengths. Let k denote the largest length such that there is no closed walk of length k in ${\mathbb {G}}$. The relational power ${\mathbb {G}}^{^{\circ k}}$ is compatible with t, strongly connected, and by the choice of k, ${\mathbb {G}}^{^{\circ k}}$ contains closed walks of all lengths greater than 1 but no loop.

Since ${\mathbb {G}}^{^{\circ k}}$ is strongly connected, we can find nodes $a_i$ such that there are edges $a_i\rightarrow b_i$ in ${\mathbb {G}}^{^{\circ k}}$. Any such edge is also an edge in $\overline{{\mathbb {P}}(t,i)}$ by the choice of $b_i$. Therefore, the assumptions of Theorem 5.1 are satisfied, and we get a contradiction with the hypothesis that ${\mathbb {G}}^{^{\circ k}}$ has no loop. $\square$

The standard finite loop lemma for strongly connected digraphs, originally proved in [2], is a direct consequence.

Corollary 5.4

Let ${\mathbb {G}}$ be a strongly connected digraph with algebraic length 1 compatible with a Taylor operation. Then ${\mathbb {G}}$ has a loop.

Proof Let us denote the Taylor operation as t, and the vertex set of ${\mathbb {G}}$ as A. Since the digraph ${\mathbb {G}}$ is strongly connected and has algebraic length 1, it remains to verify the assumptions of Theorem 5.2. We take $i\in [:n]$ and $u,v\in A$, and find w such that $u\rightarrow w$ and $v\rightarrow w$ in ${\mathbb {P}}(t,i)$. This is straightforward, it suffices to set

$$\begin{aligned} w = t(x_0,\ldots ,x_i=u,\ldots ,x_{n-1}) = t(y_0,\ldots ,y_i=v,\ldots ,y_{n-1}), \end{aligned}$$

where $x_j,y_j$ are set to u or v according to the Taylor equation number i. $\square$

6 Conclusion

Since considering positions of variables in a star power as words and applying simple word combinatorics on them gives surprisingly strong results, this line of argument call for further exploration. In particular, we would like to see a proof that is able to separate the technical effort from the overall powerful machinery. This could lead not only to a nicer proof of the local loop lemma in this article but also pave a way to various interesting generalizations.

A modest generalization would be replacing item (3) in Theorem 1.4 with the hypothesis that ${\mathbb {G}}$ is a strongly connected digraph with algebraic length 1. The fact that we were able to obtain cycles of all lengths whenever we needed suggests that it is rather a technical issue in the proof rather than a real obstacle.

Likely a harder task would be to replace the assumption of a strongly connected digraph by something weaker. While the finite loop lemma, Theorem 1.1, suggests that the assumption of a strongly connected digraph is not entirely necessary, the strong connectedness forms a solid barrier for loop conditions, see Section 6 in [11] for counterexamples.

However, to get a widely applicable and powerful tool, it is necessary to go beyond a single digraph. What are the necessary assumptions to obtain a loop shared by two digraphs? What about loops in hypergraphs (see [7])? A natural question comes from Section 4. While it is possible to prove that a local Taylor term implies local double-loop term, there is a much simpler form of the (global) weakest non-trivial idempotent equational condition:

Question 6.1

Let ${\mathbf {A}}$ be an idempotent algebra that satisfies Taylor identities locally on a set X. Does it necessarily have a term that satisfies

$$\begin{aligned} t(x,y,y,y,x,x) = t(y,x,y,x,y,x) = t(y,y,x,x,x,y) \end{aligned}$$

locally on X?

Lastly, is it possible to apply the ideas in this article to oligomorphic structures, and consequently, infinite constraint satisfaction problem (see [4, 7])? Oligomorphic algebras are, in a sense, the opposite of idempotent algebras—idempotent algebras have only the trivial unary term operation while oligomorphic algebras have a large group of them. On the other hand, notice that the proof of Theorem 1.4 uses the idempotency at just two places, and in a predictable manner. This suggests that there might be a way of using a variant of the local loop lemma in algebras that are not idempotent.