Words Maps and Spectra of Random Graph Lifts

Abstract

We study here the spectra of random lifts of graphs. Let $G$ be a finite connected graph, and let the infinite tree $T$ be its universal cover space. If $\lambda_{1}$ and $\rho$ are the spectral radii of $G$ and $T$ respectively, then, as shown by Friedman [Fri03], in almost every $n$-lift $H$ of $G$, all “new” eigenvalues of $H$ are $\leq O\left(\lambda_{1}^{\;1/2}\rho^{1/2}\right)$. Here we improve this bound to $O\left(\lambda_{1}^{\;1/3}\rho^{2/3}\right)$. It is conjectured in [Fri03] that the statement holds with the bound $\rho+o(1)$ which, if true, is tight by [Gre95]. For $G$ a bouquet with $d/2$ loops, our arguments yield a simple proof that almost every $d$-regular graph has second eigenvalue $O(d^{2/3})$. For the bouquet, Friedman [Fri] has famously proved the (nearly?) optimal bound of $2\sqrt{d-1}+o(1)$.

As an aside, we obtain a new conceptual and relatively simple proof of a theorem of A. Nica [Nica94], which determines, for every fixed $w$, the limit distribution (as $n\to\infty$) of $X_{w}^{(n)}$. A surprising aspect of this theorem is that the answer depends only on the largest integer $d$ so that $w=u^{d}$ for some word $u$.

Introduction

Let $G=(V,E)$ be some fixed finite connected graph with $E=\{g_{1},\ldots,g_{k}\}$, and let $\lambda_{1}\geq\lambda_{2}\ldots\geq\lambda_{|V|}$ be the eigenvalues of its adjacency matrix. We think of the edges as being oriented, though the results do not depend on the orientation chosen. We recall that $L_{n}(G)$ denotes the probability space of $n$-lifts of $G$ (i.e., graphs that have an $n$-fold cover map onto $G$). A graph $H\in L_{n}(G)$, has vertex set $V\times\{1,\ldots,n\}$. For every (oriented) edge $g_{i}=(u,v)$, we choose independently and uniformly a random permutation, $\sigma_{i}\in S_{n}$, and introduce an edge between $(u,j)$ to $(v,\sigma_{i}(j))$ for all $j$. For background on lifts and random lifts, see [LR05, AL06, ALM02, HLW06]. In particular [BL06] shows how to construct regular graph lifts with a nearly optimal spectral gap.

Let $\mu_{max}:=max\{|\mu|~{}:~{}\mu\textrm{~{}is a new eigenvalue of~{}}H\}$. In [Fri03], Friedman showed that $\mu_{max}\leq\lambda_{1}^{\;1/2}\rho^{1/2}+o_{n}(1)$ for almost every $H$. We improve this bound as follows:

Almost every random $n$-lift $H$ of $G$ satisfies:

Let $\Gamma$ be a (not necessarily finite) connected graph, and let $v$ be a vertex in $\Gamma$. We denote by $t_{s}(v)$ the number of closed paths of length $s$ that start and end at $v$. It is well known that the spectral radius of $\Gamma$ equals $\limsup_{s\to\infty}t_{s}(v)^{1/s}$. In particular, this value is independent of the choice of $v$. (These facts may be proven by an easy variation on the proof of Proposition 3.1 in [Buc86].) Returning to our notation, observe that a path that starts and ends at a vertex $v\in V(T)$ is projected to a path of the same length that starts and ends at the corresponding vertex of $G$. Consequently, $\rho\leq\lambda_{1}$ always holds.

Our proof of Theorem 1 suggests an approach that may lead to an even better (nearly optimal) bound $\mu_{max}\leq O\left(\rho\right)$. This plan depends on an unresolved conjecture that we present shortly. It follows from Lubotzky and Greenberg [Gre95] that this statement cannot hold with any bound smaller than $\rho-o(1)$. It is shown in [Gre95] that for every infinite tree $T$ and for every $\epsilon>0$, there exists a constant $c=c(\epsilon,T)>0$, such that if $T$ is the universal covering space of a finite graph $\Gamma$, then at least $c|V(\Gamma)|$ of $\Gamma$’s eigenvalues exceed $\rho(T)-\epsilon$. Thus for $G$ fixed, and for $\epsilon>0$ there exists an $n_{\epsilon}$ such that $\mu_{max}(H)>\rho(G)-\epsilon$ for every $n\geq n_{\epsilon}$ and every $H\in L_{n}(G)$. (Since the infinite $d$-regular tree $T_{d}$ has spectral radius $\rho(T_{d})=2\sqrt{d-1}$ ([Car72]), this extends the Alon-Boppana bound [Nil91] that $\lambda_{2}\geq 2\sqrt{d-1}-o_{n}(1)$ for every $n$-vertex $d$-regular graph).

The “permutation model” of random $d$-regular graphs (for $d$ even) is a special case of random lifts of graphs. In the permutation model, $n$-vertex $d$-regular graphs are generated through a random $n$-lift of a bouquet of $d/2$ loops. Thus, our result, as well as Friedman’s, extend earlier work on random $d$-regular graphs. Namely, Friedman’s result states that $\lambda(G)\leq\sqrt{2d\sqrt{d-1}}+o(1)$ for almost every $d$-regular graph, which is a slight improvement of an old result of Broder and Shamir [BS87]. In this special case, Theorem 1 states that $\lambda(G)=O(d^{2/3})$ holds almost surely, and the tentative proof strategy mentioned above would yield $\lambda(G)=O(d^{1/2})$ almost surely. In particular, we obtain the following corollary (which is, of course, substantially weaker than the one proven in [Fri]):

If $G$ is $d$-regular and $d\geq 107$, then

A major tool in this area is the Trace Method which goes back to Wigner [Wig55]. It is based on a natural connection between graph spectra and word-maps. This approach underlies the work of Broder-Shamir [BS87] and of Friedman [Fri03].

Let $w$ be a (not necessarily reduced) formal word in the letters $g_{1}^{\pm 1},\ldots,g_{k}^{\pm 1}$. For every $k$-tuple $(\sigma_{1},\ldots,\sigma_{k})$ of permutations in $S_{n}$, we form the permutation $w(\sigma_{1},\ldots,\sigma_{k})\in S_{n}$, by replacing $g_{1},\ldots,g_{k}$ with $\sigma_{1},\ldots,\sigma_{k}$ in the expression of $w$. For instance, if $w=g_{2}g_{1}^{\;2}g_{2}^{\;-1}g_{3}$, then $w(\sigma_{1},\sigma_{2},\sigma_{3})=\sigma_{2}\sigma_{1}^{\;2}\sigma_{2}^{\;-1}\sigma_{3}$. The correspondence between $w$ and the permutation $w(\sigma_{1},\ldots,\sigma_{k})\in S_{n}$ is called a word map. Such maps can be evaluated in groups other than $S_{n}$ as well (we refer to this briefly in Section 2). The study of word maps has a long history in group theory (see [LSh07] and the references therein). Our perspective is mostly combinatorial and probabilistic.

For fixed formal word $w$ we denote by $X_{w}^{(n)}$ a random variable on $S_{n}^{\;k}$ which is defined by:

Now let $H$ be an $n$-lift of $G$ and let $A_{G},A_{H}$ be the adjacency matrices of $G,H$ resp. We denote by $\mu$ a running index for the “new” eigenvalues of $H$. For every $t\geq 1$, the trace of $A_{H}^{\;~{}t}$ equals the number of closed paths of length $t$ in $H$. This number can also be expressed as $\left(\sum_{\mu}\mu^{t}\right)+\left(\sum_{i=1}^{|V(G)|}\lambda_{i}^{\;t}\right)$. Therefore, for $t$ even we obtain:

Every closed path in $H$ is a lift of a closed path in $G$. Since the edges of $G$ are labeled $g_{1},\ldots,g_{k}$, every (closed) path in $G$ corresponds to some formal word $w$ in $g_{1}^{\pm 1},\ldots,g_{k}^{\pm 1}$. The closed lifts of this path are in $1:1$ correspondence with the fixed points of $w(\sigma_{1},\ldots,\sigma_{k})$, so that their number is $X_{w}^{(n)}(\sigma_{1},\ldots,\sigma_{k})$. Let ${\cal CP}_{t}(G)$ denote the set of all closed paths of length $t$ in $G$ (i.e., $|{\cal CP}_{t}(G)|=tr(A_{G}^{\;t})$). The above inequality now becomes:

We consider next (Section 2.2) another categorization of the words in $\mathbf{F}_{k}$, which does not depend on a word-map to specific groups such as $S_{n}$. To every $w\in\mathbf{F}_{k}$ we associate $\beta(w)$ which is a non-negative integer or $\infty$. The categorizations induced by both $\phi(w)$ and $\beta(w)$ extend the dichotomy between primitive and imprimitive words (Recall that $w$ is called imprimitive if $w=u^{d}$ for some $u\in\mathbf{F}_{k}$ and $d\geq 2$). Without going into the (somewhat lengthy) definition, let us say that the main step in both [BS87] and [Fri03] can be viewed as the observation that for $i=0,1$, $\phi(w)=i$ iff $\beta(w)=i$. Our aforementioned conjecture states in this language that $\phi(w)=\beta(w)$ for every word $w$ (Conjecture 15). These relations between $\phi$ and $\beta$ allow us to bound the sum in the r.h.s of (3): We can bound the contribution of $w$ to this sum in terms of $\phi(w)$. This is complemented by bounding the number of words $w\in{\cal CP}_{t}(G)$ with a given value of $\beta(w)$ which bound is stated in terms of $\rho$. Indeed, a key step in the present paper (Lemma 20) can be interpreted as a partial proof of the claim that $\beta(w)=2$ iff $\phi(w)=2$.

As an aside to our work we obtain a new conceptual and relatively simple proof of a theorem of A. Nica [Nica94], which determines for every fixed $w$ the limit distribution of $X_{w}^{(n)}$ as $n\to\infty$ (see Theorem 25). We carry out a similar analysis for all higher moments of $X_{w}^{(n)}$, and use the method of moments to derive Nica’s result. A surprising aspect of this theorem is that the limit distribution depends only on the largest integer $d$ such that $w=u^{d}$ for some $u\in\mathbf{F}_{k}$. Nica’s full result (which we derive by the same argument) concerns not only fixed points but applies just as well to the number of $L$-cycles for any fixed $L\geq 1$.

The paper is arranged as follows. We begin (Section 2) with our analysis of word maps and introduce the two new categorizations of formal words. Based on this analysis, we prove Theorem 1 in Section 3. In Section 4 we deal with the distribution of the number of $L$-cycles in $w(\sigma_{1},\ldots,\sigma_{k})$ and present our new proof for Nica’s Theorem. For the reader interested only in this new proof, this section is mostly self-contained with only occasional references to earlier parts of the paper. There are numerous open problems and conjectures raised in this paper, some of which we collect in Section 5.

Word Maps and the Level of Primitivity of a Word

We begin with some notation. We denote by $\Sigma_{k}$ the set of all finite words in letters $g_{1}^{\pm 1},\ldots,g_{k}^{\pm 1}$ (though we occasionally use the letters $a,b,c,\ldots$ instead). The quotient of $\Sigma_{k}$ modulo reduction of words is $\mathbf{F}_{k}$, the set of elements of the free group on $k$ generators. For instance, the set ${\cal CP}_{t}(G)$ introduced before Equation (3) is a subset of $\Sigma_{k}$, so it may contain different words which are equivalent as members of $\mathbf{F}_{k}$.

For every group $P$ and every word $w\in\Sigma_{k}$, the word map $w:P^{k}\rightarrow P$ is defined by substitutions and composition. For $p_{1},\ldots,p_{k}\in P$, the element $w(p_{1},\ldots,p_{k})$ is obtained by substituting $p_{i}$ for each occurrence of $g_{i}$ in $w$ and this for every $1\leq i\leq k$. Clearly, the word map of $w$ is invariant under reductions, so we can regard $w$ as an element in $\mathbf{F}_{k}$.

Most research on word maps concerns the range of certain fixed words $w$ in a group $P$. More specifically, for $P$ finite, it is of interest to understand the distribution induced on $P$ by the word map $w:P^{k}\rightarrow P$ and the uniform distribution on $P^{k}$. This perspective makes it natural to consider an equivalence relation on words (beyond that of reduction).

In order to introduce this equivalence relation, we now recall some simple terminology from combinatorial group theory. There are three elementary Nielsen transformations defined on the free group $\mathbf{F}_{k}$: (i) Exchanging any two generators $g_{i}$ and $g_{j}$ for some $i\neq j$, (ii) Replacing some $g_{i}$ with $g_{i}^{-1}$, (iii) Replacing any $g_{i}$ by $g_{i}g_{j}$, for some $i\neq j$. We recall (e.g. [MKS66], Theorem 3.2) that these transformations generate the automorphism group $\mathbf{A}_{k}$ of $\mathbf{F}_{k}$. We say that two words $w_{1},w_{2}\in\mathbf{F}_{k}$ are equivalent, and denote $w_{1}\sim w_{2}$, if they belong to the same orbit of $\mathbf{A}_{k}$. Obviously, $``\sim"$ is an equivalence relation. It is quite clear that for every finite group $P$, every two equivalent words $w_{1},w_{2}\in\mathbf{F}_{k}$ induce the same distribution on $P$. We do not know whether the converse is true as well, and we state a specific problem (Conjecture 17) in this vein.

Given a word $w$ and the distribution it induces on a group $P$, it is of interest to consider how far this distribution is from the uniform distribution. The two gradings of words $\phi(\cdot)$ and $\beta(\cdot)$ can be viewed as our attempts to capture this intuition. Both parameters associate a non-negative integer or $\infty$ with every $w\in\mathbf{F}_{k}$, and they tend to grow as the above-mentioned distance decreases. Of course, the distribution furthest away from the uniform distribution corresponds to the word $w=1$. Indeed, $\beta(w)=0$ iff $\phi(w)=0$ iff $w=1$ (Lemma 12). Also, $\beta(w)=1$ iff $\phi(w)=1$ iff $w$ is imprimitive (Lemma 13). In this case the range of $w$ contains only powers of certain exponent. (Recall that $w\in\mathbf{F}_{k}$ is called imprimitive if $w=u^{d}$ for some word $u$ and $d\geq 2$.) At the other end of the scale, both $\beta(w)$ and $\phi(w)$ equal $\infty$ for words that are $\sim$-equivalent to a single-letter word. Clearly, such words always induce the uniform distribution on $P$. Another important property is that both $\beta$ and $\phi$ are invariant under $``\sim"$.

The definition of $\phi(w)$ depends on the word map for the symmetric group $S_{n}$ (see Section 2.1). The definition of $\beta(w)$ is more involved and is based on a certain analysis of $w$ as a formal word without reference to groups (see Section 2.2). In fact, we have arrived at our definition of $\beta(w)$ through our study of $\phi(w)$. Some proven results and extensive numerical simulations suggest that $\phi(w)=\beta(w)$ for every $w$ (Section 2.3). One advantage of the parameter $\beta$ over $\phi$ is that we can bound the number of words with fixed value of $\beta$ - see Section 3.1.

Since both $\phi(w)$ and $\beta(w)$ offer an extension of the primitive-imprimitive dichotomy for words, we tend to think of them as quantifying “the level of primitivity” of a word (this level is 0 if $w=1$, it is 1 if $w$ is imprimitive, and $\geq 2$ for primitive words - see Section 2.3).

In this section we present a method to calculate the expectation of $X_{w}^{(n)}$, the number of fixed points in $w(\sigma_{1},\ldots,\sigma_{k})$ (defined in (6)). We count the fixed points in $w(\sigma_{1},\ldots,\sigma_{k})$ for all $k$-tuples $(\sigma_{1},\ldots,\sigma_{k})\in S_{n}^{\;k}$ and divide by $(n!)^{k}$. This calculation is carried out through a certain categorization of all fixed points. We note that similar considerations appear in [Nica94] and in [Fri91].

We begin with some technicalities. Let $w=g_{i_{1}}^{\;\alpha_{1}}g_{i_{2}}^{\;\alpha_{2}}\ldots g_{i_{m}}^{\;\alpha_{m}}\in\Sigma_{k}$, where $i_{1},\ldots,i_{m}\in\{1,\ldots,k\}$ and $\alpha_{1},\ldots,\alpha_{m}\in\{-1,1\}$, and let $\sigma_{1},\ldots,\sigma_{k}\in S_{n}$. Assume that $s_{0}\in\{1,\ldots,n\}$ is a fixed point of $w(\sigma_{1},\ldots,\sigma_{k})$. Associated with $s_{0}$ is the following closed trail:

with $s_{1},\ldots,s_{m-1}\in\{1,\ldots,n\}$, and $s_{b~{}\textrm{mod}~{}m}=\sigma_{i_{b}}^{\;\alpha_{b}}(s_{b-1})$ ($b=1,\ldots,m$).

Note that for the sake of convenience, we compose permutations from left to right. This is inconsequential for the analysis of the variables $X_{w}^{(n)}$ since $w(\sigma_{1},\ldots,\sigma_{k})$ with left-to-right composition is the inverse of $w(\sigma_{1}^{\;-1},\ldots,\sigma_{k}^{\;-1})$ with right-to-left composition, and thus both have the same cycle structure.

We categorize fixed points according to their associated trails. Let $s_{0}\to\ldots\to s_{m-1}\to s_{0}$ and $s^{\prime}_{0}\to\ldots\to s^{\prime}_{m-1}\to s^{\prime}_{0}$ be the trails of the fixed points $s_{0}$ and $s^{\prime}_{0}$ in $w(\sigma_{1},\ldots\sigma_{k})$ and $w(\sigma^{\prime}_{1},\ldots,\sigma^{\prime}_{k})$ respectively. These two trails are placed in the same category, if they have the same coincidence pattern, that is, if for every $i,j\in\{0,\ldots,m-1\}$, $s_{i}=s_{j}\Leftrightarrow s^{\prime}_{i}=s^{\prime}_{j}$.

Each closed trail consists of $m$ integers, or points, possibly with repetitions, and each category of trails uniquely corresponds to some partition of these $m$ points. Consequently, there are at most $B(m)$ categories, where the $m$-th Bell Number, $B(m)$, is the number of partitions of an $m$ element set. This bound is, however, not tight. For instance, if $s_{a+1}=\sigma_{j}(s_{a})$ and $s_{b+1}=\sigma_{j}^{\;-1}(s_{b})$, then $s_{a}=s_{b+1}\Leftrightarrow s_{a+1}=s_{b}$. Therefore, not every partition corresponds to a realizable category of trails.

It is convenient to associate a directed edge-colored graph $\Gamma$ with each category. Vertices in $\Gamma$ correspond to blocks in the partition that defines $\Gamma$’s category. In other words, $\Gamma$ has as many vertices as the number of distinct integers among the $s_{b}$’s. There is a directed edge labeled $j$ from one vertex (=block) to another, whenever the trails include an arrow labeled $\sigma_{j}$ (resp. $\sigma_{j}^{\;-1}$) from a point in the first (second) block to a point in the second (first) one.

Of special importance is the graph associated with the finest possible partition which we call the universal graph. Two points in the trail are merged in this partition if and only if they are merged in every realizable partition. If $w$ is cyclically reduced (i.e., no two consecutive letters are inverses, nor are the first and last letter), this is the partition where all $m$ points in the trail are distinct. To illustrate, we draw in Figure 1 the universal graph of three different words.

All other graphs are now easily derived as quotients of the universal graph, or partitions of its vertices. A quotient graph has one vertex per each block in the partition. It has a $j$-labeled directed edge ($j$-edge for short) from block $v_{1}$ to block $v_{2}$, if the universal graph contains a $j$-edge from a vertex in $v_{1}$ to a vertex in $v_{2}$. A quotient is not realizable if it contains two distinct $j$-edges with common head and different tails or vice-versa. We denote by ${\cal Q}_{w}$ the set of all realizable quotients .

To illustrate, we draw (Figure 2) all the realizable quotient graphs of the universal graph of the commutator word (one of the graphs in Figure 1). Note that a four element set has 15 partitions (the fourth Bell number, $B(4)=15$), of which only 7 are realizable in this case.

These graphs suggest a simple formula for the number of fixed points in each category. Let $v_{\Gamma}$, ($e_{\Gamma}$) be the number of vertices (edges) in the graph $\Gamma$, and $e_{\Gamma}^{j}$ be the number of $j$-edges (and so $e_{\Gamma}=\sum_{j=1}^{k}e_{\Gamma}^{j}$). To count the number of fixed points in $\Gamma$’s category, or the number of realizations of $\Gamma$, we first label $\Gamma$’s vertices by distinct numbers from $\{1,\ldots,n\}$ (i.e., specify the values of $s_{0},\ldots,s_{m-1}$) . This can be done in $n(n-1)\ldots(n-v_{\Gamma}+1)$ ways. For each $j=1,\ldots,k$ there are \big{(}n-e_{\Gamma}^{j}\big{)}! permutations that are consistent with the $e_{\Gamma}^{j}$ values in the permutation $\sigma_{j}$ that are already determined. Thus, the number of realizations of $\Gamma$ is:

A formula for the expectation of $X_{w}^{(n)}$ is now at hand:

(The third equality holds only for $n$ that is $\geq e_{\Gamma}^{j}$ for all $j$ and $\Gamma$.)

We illustrate these calculations for $w$ the commutator word $g_{1}g_{2}g_{1}^{\;-1}g_{2}^{\;-1}$. If we go over the graphs in Figure 2 in clockwise order starting at the upper-left graph, (6) becomes:

Associated with every $w\in\mathbf{F}_{k}$ is a power series $\sum_{i=0}^{\infty}a_{i}(w)x^{i}$ that has a positive radius of convergence where the coefficients $a_{i}(w)$ are integers. In particular, for every $w$ and for every sufficiently large $n$, there holds $\Phi_{w}(n)=\sum_{i=0}^{\infty}a_{i}(w)\frac{1}{n^{i}}$.

As we saw in (6), for large enough $n$ (e.g., $n\geq|w|$ suffices),

Since every $\Gamma$ is a connected graph, we have $e_{\Gamma}-v_{\Gamma}+1\geq 0$. The lemma follows when we individually consider the expression corresponding to each $\Gamma$. (See the proof of Lemma 19 for a thorough analysis of these expressions). ∎

By Lemma 4, the contribution of every $w\in{\cal CP}_{t}(G)$ in (3), is $\frac{a_{i}(w)+o(1)}{n^{i-1}}$ for some nonnegative integer $i$. This induces the following useful grading of words:

Recall that although the construction of $\Phi_{w}$ depends on the actual representation of $w$ (a reduction of $w$ usually changes ${\cal Q}_{w}$), this function captures some features of the distribution of the image of $w$ on $S_{n}$. Thus $\Phi_{w}$, as well as $\phi(w)$, are invariant not only under reduction, but also under $``\sim"$.

With this new terminology we can reinterpret both [BS87] and [Fri03] as follows: Both papers rely on the fact that $\phi(w)=0$ iff $w$ reduces to the empty word, and that $\phi(w)=1$ iff $w$ is imprimitive (see Lemmas 12 and 13). To study the new spectrum of random lifts, one proceeds as follows: The number of words of these two kinds can be bounded in terms of $\rho$ (the spectral radius of the universal cover) alone (and does not depend on $\lambda_{1}$, the spectral radius of the base graph). Finally, the rest of the words (which are, in fact, the vast majority) contribute to the summation in (3) only $O\left(\frac{1}{n}\right)$ each.

Here we extend these ideas and seek (with partial success) a similar characterization for all words with $\phi(w)=i$ for fixed $i$. Our analysis of the new spectrum extends these arguments and refines them. We further split the above-mentioned third set and attain an improved bound on the contributions of these subsets to the sum in Equation (3).

2 More on the Level of Primitivity: β​(⋅)𝛽⋅\beta(\cdot)

We now start our second attempt at capturing the “level of primitivity” of $w$ by means of the parameter $\beta(w)$. We begin with some definitions.

Recall the notion of a trail from Section 2.1. Consider then the following trail through $w=g_{i_{1}}^{\;\alpha_{1}}g_{i_{2}}^{\;\alpha_{2}}\ldots g_{i_{|w|}}^{\;\alpha_{|w|}}$ (this time, the $s_{i}$’s should not be thought of as numbers but rather as abstract symbols, and the trail deliberately ends with $s_{|w|}$ and not with $s_{0}$):

As in our former definition of a realizable category of trails, we say that a partition of $\{s_{0},\ldots,s_{|w|}\}$ is realizable if the following conditions hold: Whenever $i_{h}=i_{l}$ and $\alpha_{h}=\alpha_{l}$, $s_{h-1}$ is in the same block with $s_{l-1}$ (we denote $s_{h-1}\equiv s_{l-1}$) iff $s_{h}\equiv s_{l}$. Likewise, whenever $i_{h}=i_{l}$ and $\alpha_{h}=-\alpha_{l}$, $s_{h-1}\equiv s_{l}\Leftrightarrow s_{h}\equiv s_{l-1}$. (In other words, a partition is realizable whenever it traces a trail of some point, fixed or not, through $w(\sigma_{1},\ldots,\sigma_{k})$ for some $\sigma_{1},\ldots,\sigma_{k}\in S_{n}$ and some $n$.)

As before, to each realizable partition of $\{s_{0},\ldots,s_{|w|}\}$ corresponds a directed edge-colored graph $\Gamma$, which is a quotient of the graph of the trail. According to our former notation, $\Gamma\in{\cal Q}_{w}$ whenever $s_{0}\equiv s_{|w|}$. We now concentrate on the number of pairs of $s_{i}$’s that should be merged in order to yield a specific $\Gamma$.

Let $\Gamma$ be the quotient graph corresponding to some realizable partition of $\{s_{0},\ldots,s_{|w|}\}$. We say that set of pairs $\left\{\{s_{j_{1}},s_{k_{1}}\},\ldots,\{s_{j_{r}},s_{k_{r}}\}\right\}$ generates $\Gamma$, if $\Gamma$ corresponds to the finest realizable partition in which $s_{j_{i}}\equiv s_{k_{i}}~{}\forall i=1,\ldots,r$.

Let us return to the commutator word $w=g_{1}g_{2}g_{1}^{\;-1}g_{2}^{\;-1}$. The trail here is

In Figure 3 we revisit the seven quotient graphs from Figure 2 (the seven graphs in ${\cal Q}_{w}$), and specify a smallest generating set for each of them.

We denote by $\chi(\Gamma)=e_{\Gamma}-v_{\Gamma}+1$ the Euler characteristic of $\Gamma$. It turns out that there is a tight connection between $\chi(\Gamma)$ and the smallest size of a generating set of $\Gamma$:

Let $\Gamma$ be the quotient graph corresponding to some realizable partition of $\{s_{0},\ldots,s_{|w|}\}$. The smallest cardinality of a generating set for $\Gamma$ is $\chi(\Gamma)$.

It is quite easy to construct a set $\widehat{S}$ of $\chi(\Gamma)$ pairs that generates $\Gamma$. To this end, we adopt the original terminology of [BS87]. As we follow the path of $w$ through $\Gamma$, each move has one of three types. In a free step we traverse a new edge and reach a new vertex, and so one vertex and one edge are added to the partial graph. In a coincidence a new edge leads us to an “old” vertex, so we gain one new edge and no new vertices. In a forced step we traverse an old edge (necessarily to an old vertex), so the numbers of vertices and edges remain unchanged. Consequently, $\chi(\Gamma)$ equals the number of coincidences in this walk. We introduce into $\widehat{S}$ one pair for each coincidence. If the $j$-th step is a coincidence in which we reach a vertex in $\Gamma$ representing the block $s_{i_{1}},\ldots,s_{i_{r}}~{}(i_{1}\leq\ldots\leq i_{r}<j)$, we add $\{s_{j},s_{i_{1}}\}$ to $\widehat{S}$. Clearly, the cardinality of $\widehat{S}$ is $\chi(\Gamma)$ and it generates $\Gamma$.

To see that $\Gamma$ has no generating set smaller than $\widehat{S}$, consider ${\cal S}$, the collection of all generating sets of $\Gamma$ of the smallest possible cardinality. We claim that $\widehat{S}$ is the lexicographically first member of ${\cal S}$. Concretely, write each pair under consideration as $\{s_{i},s_{j}\}$ with $i>j$. Now sort the pairs in each $S\in{\cal S}$ in increasing lexicographic order and let $T\in{\cal S}$ be the lexicographically first member of ${\cal S}$. Our claim is that $T=\widehat{S}$. Observe that if $\{s_{i},s_{j}\}\in T$ then there is no index $h<i$ with $h\neq j$ with $\{s_{i},s_{h}\}\in T$. Otherwise we could replace the pair $\{s_{i},s_{j}\}$ with the pair $\{s_{h},s_{j}\}$ and generate the same quotient as does $T$ with a lexicographically smaller set of pairs.

It is helpful to consider for each $1\leq i\leq|w|$ the graph $\Gamma_{i}$ that is the quotient of $s_{0}\to\ldots\to s_{i}$ generated by the initial segments of $T$ that includes only those pairs in $T$ where both indices are $\leq i$. We claim that $\Gamma_{i-1}$ is a subgraph of $\Gamma_{i}$ for all $i$. If there is no pair in $T$ where $s_{i}$ is the larger member, this is clear. If $\{s_{i},s_{j}\}$ is in $T$ then the index $j$ is uniquely defined by the above remark. In this case we need to show that the identification of $s_{i}$ with $s_{j}$ does not entail any additional identification (which would violate the inclusion $\Gamma_{i-1}\subseteq\Gamma_{i}$). How can such an identification occur? Only if the label of the edge $(s_{i-1},s_{i})$ agrees with that of an edge $e$ incident with the block that contains $s_{j}$ (and has the correct orientation). Let $s_{\nu}$ be a member of the block at the other end of $e$. Clearly $\nu<i$. But now again we can generate the quotient generated by $T$ by a lexicographically smaller set, i.e., replace the pair $\{s_{i},s_{j}\}$ by $\{s_{i-1},s_{\nu}\}$.

We can again recognize the three types of steps by observing how the graphs $\Gamma_{i}$ grow at each step. If $\Gamma_{i}$ stays unchanged, this is a forced move. If only an edge is added, this is a coincidence and in a free step one vertex and one edge are added. It is exactly at each coincidence step that vertices at $T$ get merged. But this is precisely what we did in constructing $\widehat{S}$, so that $\widehat{S}=T$, as claimed.

The following categorization of the quotient graphs in ${\cal Q}_{w}$ turns out to be very useful:

Let $w$ be a word in $\Sigma_{k}$. We say that a quotient graph $\Gamma\in{\cal Q}_{w}$ has type A, if one of the smallest generating sets for $\Gamma$ contains the pair $\{s_{0},s_{|w|}\}$. Otherwise, we say $\Gamma$ has type B.

Given a word $w$, we classify the graphs in ${\cal Q}_{w}$ according to their characteristics and type. Note that $\chi(\Gamma)\leq|w|$, since every $\Gamma$ has at most $|w|$ edges. We illustrate this again with the seven graphs of the commutator word: The figure-eight graph with one vertex and two edges has type B. The other six graphs have type A (their generating sets specified in Figure 3 purposely include $\{s_{0},s_{4}\}$). Table 1 shows the whole census.

We are now ready for the second definition for a word’s “level of primitivity”. Let $w$ be a word in $\Sigma_{k}$. We define $\beta(w)$ to be the smallest characteristic of a type-B graph in ${\cal Q}_{w}$. Namely,

In the next few lemmas we establish several properties of $\beta(\cdot)$ which are clearly desirable. Among others, $\beta(\cdot)$ is proved to be invariant under reductions, and hence well defined as a function on $\mathbf{F}_{k}$.

$\beta(\cdot)$ is invariant under cyclic shifts.

Let $w\in\Sigma_{k}$, and let $w^{\prime}$ be some cyclic shift of $w$. There is an obvious bijection between ${\cal Q}_{w}$ and ${\cal Q}_{w^{\prime}}$, obtained by applying the appropriate cyclic shift on the indices of the $s_{i}$’s in the blocks’ names. (E.g, if $w^{\prime}$ is attained from $w$ by a right cyclic shift of two positions, replace each label $s_{i}$ in $w$ by $s^{\prime}_{j}$ in $w^{\prime}$ where $j\equiv i+2\mod|w|$.) We claim that in addition, each $\Gamma\in{\cal Q}_{w}$ has the same type in ${\cal Q}_{w}$ as its matching quotient $\Gamma^{\prime}$ in ${\cal Q}_{w^{\prime}}$. It suffices to show that if $\Gamma$ has type A in ${\cal Q}_{w}$, then $\Gamma^{\prime}$ have type A in ${\cal Q}_{w^{\prime}}$ (It then follows by symmetry that $\Gamma$ has type A in ${\cal Q}_{w}$ iff $\Gamma^{\prime}$ has type A in ${\cal Q}_{w^{\prime}}$).

Let $S$ be a smallest generating set of $\Gamma$ with $\{s_{0},s_{|w|}\}\in S$. Given $S$, we can generate $\Gamma$ gradually, through a series of quotients. To proceed from the quotient $\Gamma_{i}$ to the next quotient, we add a pair $\{s_{j},s_{r}\}\in S$. To determine $\Gamma_{i+1}$ we carry out all necessary identifications and only them. Formally, $\Gamma_{i+1}$ is the finest realizable quotient of $\Gamma_{i}$ in which the pair $\{s_{j},s_{r}\}$ is merged. It is easily verified that the final quotient is $\Gamma$ regardless of the order at which the pairs in $S$ are introduced. But merging $\{s_{0},s_{|w|}\}$ in $w$, and merging $\{s^{\prime}_{0},s^{\prime}_{|w|}\}$ in $w^{\prime}$, yield equivalent quotient graphs (these are the universal graphs of $w$ and of $w^{\prime}$, as defined in Section 2.1 around Figure 1). We can now proceed by applying the same series of quotients as described above on both universal graphs, to conclude that $\Gamma^{\prime}$ is of type A with respect to $w^{\prime}$ as well. ∎

Let $w\in\Sigma_{k}$, and let $w^{\prime}$ be its reduced form. Then $\beta(w)=\beta(w^{\prime})$.

We need to show that $\beta$ does not change when a letter and its inverse are inserted consecutively into a word. But Lemma 8 says that $\beta$ is invariant under cyclic shifts, so it suffices to show that $\beta(w)=\beta(w^{\prime})$ for $w=g_{i_{1}}^{\;\alpha_{1}}g_{i_{2}}^{\;\alpha_{2}}\ldots g_{i_{m}}^{\;\alpha_{m}}$ and $w^{\prime}=g_{i_{1}}^{\;\alpha_{1}}g_{i_{2}}^{\;\alpha_{2}}\ldots g_{i_{m}}^{\;\alpha_{m}}g_{j}g_{j}^{\;-1}$. To see this, we define below for every quotient $\Gamma\in{\cal Q}_{w}$ the subset $\epsilon(\Gamma)\subseteq{\cal Q}_{w^{\prime}}$ of all consistent extensions of $\Gamma$. The set $\epsilon(\Gamma)$ contains a certain member $\delta(\Gamma)$ which plays a special role. The relevant properties of $\epsilon$ and $\delta$ are:

The union of the images of $\epsilon$ is all of ${\cal Q}_{w^{\prime}}$.

If $\Gamma_{1}\neq\Gamma_{2}\in{\cal Q}_{w}$, then $\epsilon(\Gamma_{1})$ and $\epsilon(\Gamma_{2})$ are disjoint.

If $\Gamma\in{\cal Q}_{w}$ has type A, then all members in $\epsilon(\Gamma)$ have type A.

For every $\Gamma\in{\cal Q}_{w}$, one graph $\delta(\Gamma)\in\epsilon(\Gamma)$ has the same Euler characteristic and the same type as $\Gamma$. All other members in $\epsilon(\Gamma)$ have Euler characteristic $\chi(\Gamma)+1$.

It should be clear that these properties prove the lemma.

If $v\in V(\Gamma)$ is the vertex corresponding to $s_{m}$, then $\epsilon(\Gamma)$ is the set of all extensions of $\Gamma\in{\cal Q}_{w}$ where there is a $j$-edge (an edge labeled $j$) starting at $v$. If $\Gamma$ already has such an edge, then we can attain a graph $\Gamma^{\prime}\in{\cal Q}_{w^{\prime}}$ by adding $s_{m+2}$ to the block containing $s_{m}$, and adding $s_{m+1}$ to the block at the end of this $j$-edge. We then define $\epsilon(\Gamma)=\{\delta(\Gamma)\}=\{\Gamma^{\prime}\}\approx\{\Gamma\}$ (We use “$\approx$” to denote equality as vertex-unlabeled-graphs.)

Otherwise, $\epsilon(\Gamma)$ includes all the $(v_{\Gamma}-e_{\Gamma}^{j}+1)$ different possible extensions of $\Gamma$ with such an edge. We only need to specify the other vertex of this new edge, that corresponds to $s_{m+1}$. In the graph $\delta(\Gamma)$ the vertex $s_{m+1}$ is new and so is the $j$-edge $(s_{m},s_{m+1})$. Clearly, $\chi(\delta(\Gamma))=\chi(\Gamma)$, as claimed. Otherwise this additional edge can go from $s_{m}$ to any of the $v_{\Gamma}-e_{\Gamma}^{j}$ vertices in $\Gamma$ which are not tails of a $j$-edge. Such graphs clearly have characteristics $\chi(\Gamma)+1$.

We prove the first two properties of $\epsilon$ by recovering, for every $\Gamma^{\prime}\in{\cal Q}_{w^{\prime}}$ the (unique) graph $\Gamma\in{\cal Q}_{w}$ with $\Gamma^{\prime}\in\epsilon(\Gamma)$. We consider the $(m+1)$-st step in the path of $w^{\prime}$ through $\Gamma^{\prime}$ (the step from $s_{m}$ to $s_{m+1}$), and use the notations of Lemma 6. If this step is free, then $\Gamma$ is obtained from $\Gamma^{\prime}$ by deleting the vertex corresponding to $s_{m+1}$ and the edge $(s_{m},s_{m+1})$ (as well as, of course, omitting $s_{m+2}$ from its block). If it is a coincidence, then clearly $\Gamma\approx\Gamma^{\prime}\setminus(s_{m},s_{m+1})$. Otherwise, it is forced and so $\Gamma\approx\Gamma^{\prime}$.

We want to show next that if $\Gamma\in{\cal Q}_{w}$ has type A, then all graphs in $\epsilon(\Gamma)$ have type A as well. By assumption $\Gamma$ is generated by a set $S$ of cardinality $|S|=\chi(\Gamma)$ and $\{s_{0},s_{m}\}\in S$. Note that $s_{m}\equiv s_{m+2}$ in every quotient of $w^{\prime}$. Therefore, when we consider generating sets for graphs in ${\cal Q}_{w^{\prime}}$, the vertices $s_{m}$ and $s_{m+2}$ play the exact same role. We therefore define $S^{\prime}$ to be the set of pairs that is attained by replacing each occurrence of $s_{m}$ in $S$ with $s_{m+2}$. Clearly, $S^{\prime}$ generates the graph $\delta(\Gamma)\in\epsilon(\Gamma)$. For any other graph in $\epsilon(\Gamma)$, we add to $S^{\prime}$ the pair $\{s_{m+1},s_{i}\}$ where $s_{i}~{}(i\leq m)$ corresponds to the vertex which $(s_{m},s_{m+1})$ goes to. In each of these cases we found a smallest generating set $S^{\prime}$ that includes the pair $\{s_{0},s_{m+2}\}$, so all members of $\epsilon(\Gamma)$ have type A.

Finally, we need to show that if $\Gamma\in{\cal Q}_{w}$ has type B, then so does $\delta(\Gamma)$. So suppose $\delta(\Gamma)$ has type A, with a smallest generating set $S^{\prime}$ that contains the pair $\{s_{0},s_{m+2}\}$. Let us construct a set of pairs $S$ by replacing each occurrence of $s_{m+2}$ in $S^{\prime}$ by $s_{m}$. If $S^{\prime}$ contains some pair $\{s_{m+1},s_{i}\}$, then clearly $s_{m+1}$ is not a new vertex in $\delta(\Gamma)$, and we are necessarily in the case where $\Gamma\approx\delta(\Gamma)$ (recall that $\Gamma$ and $\delta(\Gamma)$ have the same characteristic). In this case the edge $(s_{m},s_{m+1})$ is not new, so it is merged with some $(s_{r-1},s_{r})$ (or $(s_{r+1},s_{r})$) for some $r<m$. Thus, we can replace each $s_{m+1}$ in $S^{\prime}$ with $s_{r}$. This is a contradiction since $S$ is a smallest generating set of $\Gamma$ which therefore has type A. ∎

Note that from Lemmas 8 and 9 it follows that $\beta$ is invariant under cyclic reduction as well, or under conjugation. Similar arguments show that it is also invariant under the equivalence relation $``\sim"$, but we do not include the proof. In the following lemma we state an important property of type-B quotient graphs. This property plays a crucial role in the sequel, where we introduce a bound to the number of words with some fixed value of $\beta(\cdot)$.

Let $\Gamma\in{\cal Q}_{w}$ have type B. As we trace the path of $w$ through $\Gamma$, every edge in $\Gamma$ is traversed at least twice.

We show that if some edge $e$ is traversed only once, then $\Gamma$ has type A. Lemma 8 allows us to assume that $e$ is the last step in the path of $w$, i.e. the step from $s_{|w|-1}$ to $s_{|w|}$. In the proof of Lemma 6, we constructed $\widehat{S}$, a generating set of $\Gamma$ of smallest cardinality, with one pair for each coincidence in the path of $w$ through $\Gamma$. Here, the last coincidence corresponds to the pair $\{s_{0},s_{|w|}\}$. Therefore $\Gamma$ has type A. ∎

The converse is not true. There are quotients of type A where every edge is traversed more than once. Consider the word $w=ababa$. One of the quotient graphs in ${\cal Q}_{w}$ is a figure-eight with one vertex and two loops. Each edge in this quotient is traversed twice or thrice, but the quotient has type A. It is generated by the two pairs $\{s_{0},s_{2}\},\{s_{0},s_{5}\}$.

3 Some Connections between ϕ​(w)italic-ϕ𝑤\phi(w) and β​(w)𝛽𝑤\beta(w)

We now turn to examine the relation between $\phi$ and $\beta$. We first observe that $a_{i}(w)$ (the coefficient of $\frac{1}{n^{i}}$ in the power series form of $\Phi_{w}(n)$), is completely determined by quotients in ${\cal Q}_{w}$ with characteristic $\leq i$. This is easily verified by considering the contribution of each $\Gamma\in{\cal Q}_{w}$ in (7). We are now able to use our new perspective and show that (as mentioned above) for $i=0,1$, $\phi(w)=i\Leftrightarrow\beta(w)=i$.