Proof.

\begin{align*} a^{l}(ba)^{s}b^{l}\cdot[a^{l-2}b^{l-1},b^{2-l}a^{1-l}]& = a^{l}(ba)^{s}b^{l}\cdot b^{1-l}a^{2-l}a^{l-1}b^{l-2}a^{l-2}b^{l-1}b^{2-l}a^{1-l}\\ & = a^{l}(ba)^{s}bab^{l-2}a^{l-2}ba^{1-l} \sim a^{l-2}ba(ba)^{s}bab^{l-2}\\ & =a^{l-2}(ba)^{s+2}b^{l-2}. \end{align*}

An obvious induction shows that, for some commutators $c_i$, the element $a^{m}b^{m}c_1c_2\ldots c_{[\frac {m}{2}]}$ is conjugate to $(ba)^{m}$ if $m$ is even, or to $a(ba)^{m-1}b$ if $m$ is odd. This completes the proof (because $a(ba)^{m-1}b=(ab)^{m}\sim (ba)^{m}$, where $\sim$ means conjugation).

Proof. Note that, for any non-identity element $g$ of the commutator subgroup of any group and for any $s\in {{\mathbb {N}}}\cup {\{0\}}$,

\[ {\textrm{cl}}(g^{s})\le s({\textrm{cl}}(g)-1)+\left[\frac{s}{2}\right]_c+1. \]

Indeed, representing $g$ as $g=ch$, where $c$ is a commutator, and ${\textrm {cl}}(h)={\textrm {cl}}(g)-1$, we obtain

\begin{align*} {\textrm{cl}}(g^{s})& ={\textrm{cl}}((ch)^{s})={\textrm{cl}}(c^{s}h^{c^{s-1}}h^{c^{s-2}}\ldots h^{c}h)\le {\textrm{cl}}(c^{s})+s\cdot{\textrm{cl}}(h)\\ & \le \left[\frac{s}{2}\right]_c+1+s({\textrm{cl}}(g)-1) \text{ (by Culler's inequality)}. \end{align*}

This completes the proof because ${\textrm {cl}}((ab)^{m})\le [m/2]$ by Lemma 1.

Proof. Surely, $N(G)$ is either prime or infinite. For $N(G)=2$, the assertion holds, because the group $G$ in this case contains an infinite dihedral subgroup, whose commutator subgroup coincides with the set of commutators (and trivially intersects conjugates of free factors). For $N(G)=\infty$, the argument below is essentially valid, but we leave it to readers, because the assertion of the theorem in this case follows immediately from the results of [Reference Chen2, Reference Ivanov and Klyachko19] mentioned in the introduction. Thus, we assume that $N(G)$ is odd.

If $z^{m}=1$, then we have two bounds:

(***)\begin{align*} {\textrm{cl}}([x,y]^{m}) \le \left[\frac{m}{2}\right]_c+1 \text{ and } {\textrm{cl}}([z,u]^{ms}) \le s\left(\left[\frac{m}{2}\right]-1\right)+\left[\frac{s}{2}\right]_c+1, \end{align*}

The first one is Culler's inequality, and the second one is Lemma 2.

Consider in $G$ a commutator $[z,\,u]$, where $z^{N(G)}=1$ and $u$ does not lie in the same free factors as $z$. Let us divide $n$ by $N=N(G)$ with remainder: $n=rN+t$, where $0\le t< N$ (and $r=[\frac {n}{ N}]$). Let the symbols $\Delta _0(a,\,b,\,\ldots )$ and $\Delta _{odd}(a,\,b,\,\ldots )$ denote the number of zeros and the number of odd numbers in the tuple $(a,\,b,\,\ldots )$. Then for odd $N$, we obtain

\begin{align*} k(G,n)& \le{\textrm{cl}}([z,u]^{n})= {\textrm{cl}}([z,u]^{rN+t}) \le {\textrm{cl}}([z,u]^{rN})+{\textrm{cl}}([z,u]^{t}) \\ & {\mathrel{\mathop{\le}\limits^{\scriptscriptstyle({{**}*})}}} \left(r\left(\left[\frac{N}{2}\right]-1\right)+\left[\frac{r}{2}\right]_c+1\right)+\left(\left[\frac{t}{2}\right]_c+1\right)\\ & =\left(r\bigg(\frac{N-1}{2}-1\bigg)+\left[\frac{r}{2}\right]_c+1\right)+\left(\left[\frac{n-rN}{2}\right]_c+1\right)\\ & =r\bigg(\frac{N-1}{2}-1\bigg)+\frac{r}{2}+1+\frac{n-rN}{2}+1 -\Delta_0(r,n-rN)-\frac{1}{2}\Delta_{odd}(r,n-rN)\\ & =\frac{n}{2}-r+2-\Delta_0(r,n-rN)-\frac{1}{2}\Delta_{odd}(r,n-rN)\\ & =\left[\frac{n}{2}\right]-r+2-\Delta_0(r,n-rN)-\frac{1}{2}(\Delta_{odd}(r,n-rN) -\Delta_{odd}(n)) \\ & =\left[\frac{n}{2}\right]-r+2-\Delta_0(r,n-rN)- \Delta_{odd}(r)(1-\Delta_{odd}(n))\\ & = \begin{cases} \left[\frac{n}{2}\right]-r+1 & \text{if a), b), or c) holds};\\ \left[\frac{n}{2}\right]-r+2 & \text{otherwise}. \end{cases} \end{align*}

Comparing this with Corollary 1, we conclude that Theorem 1 is proven (modulo the main theorem).

Proof. We assume that all collisions occur at vertices. This can be achieved by the subdivision of each edge of the initial map into two equal parts by new vertices of degree two (and slowing down all cars).

Let us prove the first assertion. For each cluster $K=K_i$ centred at $v=v_i$, consider a minimal set of connecting paths $\pi _j=\pi _{i\,j}$ such that these paths contain all points of $K$. Due to minimality, for each connecting car, we have at most one corresponding connecting path $\pi _j$ lying in the boundary of a cell $D_j=D_{i\,j}$, which is moved around by this car. By the definition of cluster, the length $\tau _j$ of the path $\pi _j$ is less than $T/2$.

Let us connect the starting and the ending points of the path $\pi _j$ by a new path $\pi _j'$ of the same length lying inside the cell $D_j$ (so, we duplicate the path $\pi _j$). (Note that these duplications for all clusters under consideration may produce several chords inside a cell, but these chords never intersect, because the clusters are independent.)

The cell $D_j$ turns into two cells (see Figure 4, on the left): the large cell $D_j'$ of the same perimeter as the initial cell $D_j$ and the small cell $\Gamma _j$ of perimeter $2\tau _j$.

Figure 4.

Cells in the modified map.

We want to define car motion on this modified map. Cars moving around the large cells imitate the cars moving around the initial cells $D_j$, except that they use the new road $\pi _j'$ instead of $\pi _j$.

To define a car moving around the small cell, let us consider the motion of already defined cars on the boundary of a small cell. The boundary of each small cell $\Gamma =\Gamma _j$ has length $2\tau _j$ and consists of three segments (listed counterclockwise, see Figure 4, on the right):

• – part $\textbf {a}=\pi _j'$ of length $\tau =\tau _j$; in this segment, the connecting car is moving during time interval $0\le t\le \tau$ (to simplify notation, we assume that the complete collision at $v_i$ occurs at zero moment, other cases can, of course, be considered similarly); part ${\bf a}$ ends at the corner $c$ at the centre $v_i$ of the cluster $K_i$;

• – part ${\bf b}$ of length one (this is the first edge of the path $\pi _j$), starting at the corner $c$; in this segment, another connecting car of the cluster $K_i$ is moving during time $-1\le t\le 0$;

• – part ${\bf c}$ of length $|\textbf {c}|=\tau -1$; not much is known about cars moving here; however, we know that $\tau < T/2$, therefore, $|\textbf {c}|=\tau -1< T-\tau -1$; this means that

  there are no cars in ${\bf c}$ (including its ends) at some moment of time $\tau < t< T-1$ and even during some subinterval $\Delta _\Gamma$ (of positive duration) of the time interval $\tau < t< T-1$

  (because the time interval $\tau < t< T-1$ has duration $T-1-\tau >|\textbf {c}|$, and all cars move with the unit speed). Note also that we can choose time intervals $\Delta _\Gamma$ disjoint for different small cells $\Gamma$:
  \[ \Delta_\Gamma\cap \Delta_{\Gamma'}=\emptyset\ \text{for }\Gamma\ne\Gamma'. \]

Now, let us define a new car $\alpha _\Gamma$ moving around the small cell $\Gamma =\Gamma _j$:

• – at moment zero, $\alpha _\Gamma$ is at the corner $c$ (and participates in the complete collision at $v_i$);

• – then $\alpha _\Gamma$ moves (slowly) along the segment ${\bf b}$ without any collisions, because the (connecting) car moving in the opposite direction has left segment ${\bf b}$ having met our car $\alpha _\Gamma$ at $v_i$; so segment ${\bf b}$ is safe until the moment $T-1$;

• – during the time interval $\Delta _\Gamma$ (which starts earlier than $T-1$ by definition of $\Delta _\Gamma$), our new car $\alpha _\Gamma$ (rapidly) moves through the segment ${\bf c}$; no collisions occur, because ${\bf c}$ is safe during the time interval $\Delta _\Gamma$ by definition of $\Delta _\Gamma$ (and because $\Delta _\Gamma \cap \Delta _{\Gamma '}=\emptyset$ for $\Gamma \ne \Gamma '$);

• – thus, our car $\alpha _\Gamma$ arrives to segment ${\bf a}$ later than moment $\tau$ (again, by definition of $\Delta _\Gamma$); this means that the connecting car already left ${\bf a}$, and our car $\alpha _\Gamma$ safely without any collisions arrives to corner $c$ at the end of the period.

We obtain a periodic motion on a map on surface $S$, the number of complete collisions is precisely $\varkappa$, and the sum $\sum \nolimits \limits _D(d_D-1)$ over all faces remains the same as for the initial map (because each small face $\Gamma _j$ is moved around by one car, i.e. $d_{\Gamma _j}=1$). Thus, applying the car-crash lemma to this motion, we obtain assertion a).

To prove assertion b), we divide the period of time $I=\{t\;|\;0\le t< T\}$ into two half-periods: $I=I_1\sqcup I_2$, where $I_1=\{t\;|\;0\le t< T/2\}$ and $I_2=\{t\;|\;T/2\le t< T\}$.

The periodicity of the motion implies that, at each point, not more than one complete collision occurs during period $I$. Therefore, the set of points of complete collision $\Pi =\{p_1,\,\ldots,\,p_n\}$ is partitioned into two subsets: $\Pi =\Pi _1\sqcup \Pi _2$, and the multiset ${{\mathcal {N}}}=(N_1,\,\ldots,\,N_n)$ of the degrees of these points is partitioned into two submultisets:

\[ {{\mathcal{N}}}={{\mathcal{N}}}_1\sqcup{{\mathcal{N}}}_2, \text{ where } {{\mathcal{N}}}_i=(\text{degrees of points of complete collision occurring during }I_i). \]

Suppose that $\Pi _i$ can be partitioned into $\varkappa _i$ independent clusters and cannot be partitioned into a fewer number of independent clusters. Then $\varkappa _1+\varkappa _2\ge \varkappa$ (because $\Pi$ can be partitioned into $\varkappa _1+\varkappa _2$ independent clusters, which is impossible if $\varkappa _1+\varkappa _2<\varkappa$).

We say that a set of points of complete collision is independent if the sets of colliding cars at these points during the period $I$ are disjoint.

Let us concentrate on $\Pi _1$ now. Suppose that

• – $v_1\in \Pi _1$ is a point at which the first (timewise) collision occurs (if such $v_1$ exists);

• – $v_2\in \Pi _1$ is a point at which the first (timewise) collision occurs such that the set $\{v_1,\, v_2\}$ is independent (if such $v_2$ exists);

• – $v_3\in \Pi _1$ is a point at which the first (timewise) collision occurs such that the set $\{v_1,\, v_2,\, v_3\}$ is independent (if such $v_3$ exists);

• – $\ldots$

The number of points $v_i$ is at least $\varkappa _1$, because otherwise $\Pi _1$ would admit a partition on a less than $\varkappa _1$ number of independent clusters (e.g. if $v_1$ and $v_2$ do exist, and $v_3$ does not, then each point from $\Pi _1$ is either in a cluster centred at $v_1$ or in a cluster centred at $v_2$).

Thus, $\Pi _1$ contains independent points $v_1,\,\ldots,\,v_{\varkappa _1}$, and $\Pi _2$ contains independent points $w_1,\,\ldots,\,w_{\varkappa _2}$ (by similar reasons). Therefore, the number of all existing cars is at least

\begin{align*} \max\bigg(\sum\deg v_i,\sum\deg w_i\bigg) & \ge {\textbf{fp}}(\deg v_1,\ldots,\deg v_{\varkappa_1}, \deg w_1,\ldots,\deg w_{\varkappa_2})\\ & \ge {\textbf{fp}}(N_1,\ldots,N_\varkappa) \end{align*}

(where the last estimate follows immediately from the inequalities $\varkappa _1+\varkappa _2\ge \varkappa$ and $N_1\le \ldots \le N_n$).

This completes the proof of assertion b), because the bound $\sum \nolimits \limits _D d_D\ge N_n$ is obvious (if, at some point, $N_n$ cars collide, then $N_n$ cars do exist).

Proof. To prove (2), it suffices to substitute bound a) of the cluster lemma to bound b) of the same lemma (as the fair partition function ${\textbf {fp}}(N_1,\,\ldots,\,N_\varkappa )$ is surely non-decreasing as a function of $\varkappa$).

Let us prove (3). Using the monotonicity of the function ${\textbf {fp}}$ with respect to each argument and formulae (2) and (1), for $\varkappa =\chi (S)+\sum \nolimits \limits _D(d_D-1)$, we obtain

\begin{align*} \sum\limits_D d_D & {\mathrel{\mathop{\ge}\limits^{\scriptscriptstyle(2)}}} \max\bigl( {\textbf{fp}}(N_1,\ldots,N_\varkappa),N_n\bigr) \ge {\textbf{fp}}(\overbrace{\underbrace{1,1,1,1,1\ldots,1}_ {\min(l,\varkappa)\text{ ones}}, N_{l+1},N_{l+1},\ldots,N_{l+1}}^{\varkappa\text{ numbers}}) {\mathrel{\mathop=\limits^{\scriptscriptstyle(1)}}}\\ & {\mathrel{\mathop=\limits^{\scriptscriptstyle(1)}}} \begin{cases} \left[\dfrac{\varkappa+1}{2}\right] & \text{if }\varkappa\le l;\\ \left[\dfrac{l+1}{2}\right]+N_{l+1}\cdot\frac{\varkappa-l}{2} & \text{if }\varkappa>l \text{ and }\varkappa-l\in 2{{\mathbb{Z}}};\\ \left[\dfrac{l+1-\min(l,N_{l+1})}{2}\right]+N_{l+1}\cdot\frac{\varkappa-l+1}{2} & \text{if }\varkappa>l \text{ and }\varkappa-l\notin 2{{\mathbb{Z}}}.\\ \end{cases} \end{align*}

Case 0: $\varkappa \le l$.

• – If $\varkappa -l$ is even, then $[(\varkappa +1)/2]\ge [(l+1)/2]+N_{l+1}\cdot (\varkappa -l)/2$ (since $N_{l+1}\ge 1$).

• – If $\varkappa -l$ is odd, then $[(\varkappa +1)/2]\ge [l/2]+N_{l+1}\cdot (\varkappa -l+1)/2$ $[\ge [(l+1- \min (l,\,N_{l+1}))/2]+N_{l+1}\cdot (\varkappa -l+1)/2$.

Thus, for all $\varkappa$ and $l$,

\[ \sum\limits_D d_D \ge \begin{cases} \left[\dfrac{l+1}{2}\right]+N_{l+1}\cdot\dfrac{\varkappa-l}{2} & \text{if }\varkappa-l\in 2{{\mathbb{Z}}};\\ \left[\dfrac{l+1-\min(l,N_{l+1})}{2}\right]+N_{l+1}\cdot\dfrac{\varkappa-l+1}{2} & \text{if }\varkappa-l\notin 2{{\mathbb{Z}}}.\end{cases} \]

Case 1: $\varkappa -l$ is even.

\begin{align*} \sum\limits_D d_D & \ge \left[\frac{l+1}{2}\right]+N_{l+1}\cdot\frac{\varkappa-l}{2} \Longrightarrow\ \varkappa-l \le \frac{2}{N_{l+1}}\bigg(\sum\limits_D d_D -\left[\frac{l+1}{2}\right]\bigg) \Longrightarrow\ \\ \varkappa-l & \le 2\left[\frac{1}{N_{l+1}}\bigg(\sum\limits_D d_D -\left[\frac{l+1}{2}\right]\bigg)\right], \end{align*}

where the last implication is valid since $\varkappa -l\in 2{{\mathbb {Z}}}$. The obtained bound coincides with (3), because $\varkappa =\chi (S)+\sum \nolimits \limits _D(d_D-1)$.

Case 2: $\varkappa -l$ is odd.

\begin{align*} \sum\limits_D d_D & \ge \left[\frac{l+1-N_{l+1}}{2}\right]_+ + N_{l+1}\cdot\frac{\varkappa-l+1}{2} \ \Longrightarrow\ \\ \varkappa-l+1 & \le \frac{2}{N_{l+1}}\bigg(\sum\limits_D d_D -\left[\frac{l+1-N_{l+1}}{2}\right]_+\bigg); \end{align*}

$\varkappa -l+1$ is even, hence, $\varkappa -l+1 \le 2\left [\frac {1}{N_{l+1}}\left (\sum \nolimits \limits _D d_D -\left [\frac {l+1-N_{l+1}}{2}\right ]_+\right )\right ],$ as required. This completes the proof.

Proof. Without loss of generality, we can assume that the number $|J|$ of free factors is two. Indeed, suppose that the cyclically irreducible form $u$ of the elements $u_i$ contains a letter $a_j\in A_j\setminus {\{1\}}$ for some $j\in J$. Then $G$ decomposes into the free product $G=A*B$, where $A=A_j$ and $B=\mathop {\,{\Huge\ast}\,}\limits \limits _{j'\in J\setminus \{j\}} A_{j'}$, and the conditions of the theorem remain fulfilled for this decomposition. Thus, we assume that the number of factors is two: $G=A*B$.

Equality (4) allows us to draw a Howie diagram on an oriented closed (possibly non-connected) surface $S$ of genus $k'{\stackrel {\textrm {def}}{=}}\frac {1}{2}(2-\chi (S))$ with $l'$ exterior vertices and $m$ cells, whose labels are $u^{n_1},\,\ldots,\,u^{n_m}$, where

\[ k'\le k\text{ and }2k'+l'\le 2k+l. \]

In detail, this construction was explained in [Reference Ivanov and Klyachko19]. Let us restrict ourselves to just one example. If $k=m=1$ and $l=0$, then, in most cases, we naturally obtain a torus without exterior vertices (with several interior vertices), and with one cell, whose label is $u_1^{n_1}$ (see Figure 1, for instance); but if, e.g. commutator $c_1$ has the form $c_1=[a,\,v]$, where $a\in A\setminus {\{1\}}$ and $v\in (A*B)\setminus A$, then we obtain a sphere with two exterior vertices (whose labels are $a$ and $a^{-1}$) and one cell, whose label is $c_1$. For $m>1$, we can even obtain a non-connected surface (if equality (4) decomposes into a product of two equalities of the same type).

On the obtained diagram, a multiple uniform motion is naturally defined: a cell with label $u^{n_i}$ are moved around by $n_i$ cars with unit speed (one edge per minute); at moment $s\in {{\mathbb {Z}}}$, each car is at the corner whose label is the $s$th letter of the word $u$ (where $s$ is counted modulo the length of $u$).

Thus, collisions outside vertices (i.e. inside edges) cannot occur, because at each moment of time either

• – all cars are at $A$-vertices,

• – or all cars are at $B$-vertices,

• – or each car is moving along an edge from an $A$-vertex to a $B$-vertex,

• – or each car is moving along an edge from a $B$-vertex to an $A$-vertex.

A complete collision at a vertex $v$ means that all corners at this vertex have the same label equal to a letter of the word $u$. If vertex $v$ is interior, then the product of these labels must be 1, i.e. $\deg v\ge N$. Applying the corollary of the cluster lemma to this motion, we obtain the inequality

(5)\begin{align} \Phi(k',l')& {\stackrel{\textrm{def}}{=}}2-2k'-l'+\sum_{i=1}^{m}(n_i-1) \le \Psi(l') {\stackrel{\textrm{def}}{=}} \notag\\ & {\stackrel{\textrm{def}}{=}} \begin{cases} 2\left[\dfrac{1}{N}\bigg(\displaystyle\sum\limits_{i=1}^{m} n_i -\left[\dfrac{l'+1}2\right]\bigg)\right], & \text{if }\displaystyle\sum\limits_{i=1}^{m}(n_i-1)-l'\in 2{{\mathbb{Z}}}\;\\ 2\left[\dfrac{1}{N}\bigg(\displaystyle\sum\limits_{i=1}^{m} n_i -\left[\dfrac{l'+1-N}2\right]_+\bigg)\right]-1, & \text{if }\displaystyle\sum\limits_{i=1}^{m}(n_i-1)-l'\notin 2{{\mathbb{Z}}}. \end{cases} \end{align}

Note that

(6)\begin{equation} \Psi(l+2)\le\Psi(l) \text{ and } \Psi(l\pm 1)\le\Psi(l)+1 \text{ for all }l. \end{equation}

The first inequality is obvious; to explain the second one, we put $n{\stackrel {\textrm {def}}{=}}\sum \nolimits n_i$. Now, if $\sum \nolimits (n_i-1)-l$ is even, then

\begin{align*} & \Psi(l\pm 1)\le\Psi(l-1)=2\left[\frac{1}{N}\left(n-\left[\frac{l-N}2\right]_+\right)\right]-1 \le 2\left[\frac{1}{N}\left(n-\left[\frac{l-N}2\right]\right)\right]-1 \\ & \quad \le 2\left[\frac{1}{N}\left(n-\left[\frac{l+1-2N}{2}\right]\right)\right]-1 = 2\left[\frac 1N\left(n-\left[\frac{l+1}2\right]+N\right)\right]-1\\ & \quad = 2\left[\frac{1}{N}\left(n-\left[\frac{l+1}2\right]\right)\right]+2-1 = \Psi(l)+1; \end{align*}

if $\sum \nolimits (n_i-1)-l$ is odd, then $\Psi (l\pm 1) \le \Psi (l-1) = \left[\tfrac {1}{N}(n-\left[\tfrac {l}{2}\right]\right] \le 2\left[\tfrac {1}{N}(n-\left[\frac{l+1-N}{2}\right]_+)\right] =\Psi (l)+1.$ This proves (6).

Now, if $l'\ge l$, then $\Phi (k,\,l)\le \Phi (k',\,l')$, because $2k'+l'\le 2k+l$ (as was noted above), and $\Psi (l'){\mathrel {\mathop {\le }\limits ^{\scriptscriptstyle (6)}}}\Psi (l)+1$. Therefore, $\Phi (k,\,l)\le \Phi (k',\,l')\le \Psi (l'){\mathrel {\mathop {\le }\limits ^{\scriptscriptstyle (6)}}}\Psi (l)+1$ and, hence, $\Phi (k,\,l)\le \Psi (l)$, because $\Phi (k,\,l)$ and $\Psi (l)$ have the same parity [see (5)]. This completes the proof in the case where $l'\ge l$.

Now, suppose that $l'< l$. Note that (6) implies that the function $l\mapsto l+\Psi (l)$ is non-decreasing. Thus, the assertion of the theorem follows immediately from (5), because $k'\le k$ (as is noted above).