%~Mouliné par MaN_auto v.0.25.0 2021-11-05 09:42:38
\documentclass[AHL,Unicode,longabstracts,published]{cedram}
\newcommand{\noopsort}[1]{}
\DeclareMathOperator{\cayl}{Cay}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\sq}{sq}
\DeclareMathOperator{\triangles}{N}
\DeclareMathOperator{\DRR}{DRR}
\DeclareMathOperator{\GRR}{GRR}
\DeclareMathOperator{\ORR}{ORR}
\newcommand*{\Z}{\mathbf{Z}}
\newcommand*{\N}{\mathbf{N}}
\newcommand{\bfun}{\mathbf{1}}
\newcommand{\bfP}{\mathbf{P}}
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\newcommand*{\orCayley}[2]{\overrightarrow\cayl(#1,#2)}
\newcommand*{\presentation}[2]{\left\langle#1\middle|#2\right\rangle}
\newcommand*{\setst}[2]{\{#1 \mid #2\}}
\newcommand*{\Triangles}[2]{\triangles_3(#1,#2)}
\newcommand*{\unCayley}[2]{\cayl(#1,#2)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\graphicspath{{./figures/}}
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
\let\oldtilde\tilde
\renewcommand*{\tilde}[1]{\mathchoice{\widetilde{#1}}{\widetilde{#1}}{\oldtilde{#1}}{\oldtilde{#1}}}
\let\oldexists\exists
\renewcommand*{\exists}{\mathrel{\oldexists}}
\let\oldforall\forall
\renewcommand*{\forall}{\mathrel{\oldforall}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title[Cayley graphs with few automorphisms]{Cayley graphs with few automorphisms: the case of infinite groups}
\alttitle{Groupes de Cayley avec peu d'automorphismes~: le cas des groupes infinis}
\subjclass{53C28, 53C26, 32Q45}
\keywords{GRR, DRR, ORR, Cayley graph, automorphisms of graphs, generalized dihedral group, generalized dicyclic group, regular automorphism group}
\author[\initial{P.-H.} \lastname{Leemann}]{\firstname{Paul-Henry} \lastname{Leemann}}
\address{Universit\'e de Neuch\^atel,\\
Institut de math\'ematiques,\\
11 Rue Emile-Argand\\
2000 Neuch\^atel (Suisse)}
\email{paul-henry.leemann@unine.ch}
\thanks{The first author was supported by Swiss
National Fund for Scientific Research Grant No. $200021\_188578$. The second author's research was supported by the ANR projects AGIRA (ANR-16-CE40-0022) and ANCG (ANR-19-CE40-0002-01). Part of this work was performed within the framework of the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program ``Investissements d'Avenir'' (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).}
\author[\initial{M.} \lastname{de la Salle}]{\firstname{Mikael} \lastname{de la Salle}}
\address{CNRS, Université de Lyon,\\
Univ Claude Bernard Lyon 1\\
Institut Camille Jordan\\
43 blvd. du 11 novembre 1918\\
69622 Villeurbanne (France)}
\email{delasalle@math.univ-lyon1.fr}
\begin{abstract}
We characterize the finitely generated groups that admit a Cayley graph whose only automorphisms are the translations, confirming a conjecture by Watkins from 1976. The proof relies on random walk techniques. As a consequence, every finitely generated group admits a Cayley graph with countable automorphism group. We also treat the case of directed graphs.
\end{abstract}
\begin{altabstract}
Nous caractérisons les groupes de type fini qui admettent un graphe de Cayley dont les seuls automorphismes sont les translations. Cela confirme une conjecture de Watkins formulée en 1976. Les preuves reposent sur des méthodes de marches aléatoires. Une conséquence des résultats est que tout groupe de type fini admet un graphe de Cayley dont le groupe d'automorphismes est dénombrable. Nous obtenons des résultats similaires pour les graphes dirigés.
\end{altabstract}
\datereceived{2020-10-26}
\dateaccepted{2021-06-01}
\editor{I. Benjamini}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\dateposted{2022-02-23}
\begin{document}
\maketitle
\section{Introduction}
Given a group $G$ and a symmetric generating set $S \subseteq G\setminus\{1\}$, the Cayley graph $\unCayley{G}{S}$ is the simple unoriented graph with vertex set $G$ and an edge between $g$ and $h$ precisely when $g^{-1}h \in S$. By construction, the action by left-multiplication of $G$ on itself induces an action of the group on its Cayley graph, which is free and vertex-transitive.
We are here interested in the question to decide when $S$ can be chosen so that these are all the automorphisms of $\unCayley{G}{S}$, or equivalently the automorphism group of the graph acts freely and transitively on the vertex set. The main result of this paper is
\begin{theo}\label{thm:main}
Every finitely generated group $G$ that is not virtually abelian admits a finite degree Cayley graph whose automorphism group is not larger than $G$ acting by left-translation.
\end{theo}
A Cayley graph of $G$ whose automorphism group acts freely on its vertex set is called a \emph{graphical regular representation}, or $\GRR$.
The main result in~\cite{LdlS2020} is similar to Theorem~\ref{thm:main}, but with the assumption of not being virtually abelian replaced by having an element of infinite (or sufficiently large) order and being non-abelian and non-generalized dicyclic (see Section~\ref{sec:reminders} for definitions). Combining both results, we obtain that the infinite finitely generated groups that do not admit a $\GRR$ are precisely the abelian and the generalized dicyclic groups.
Together with the results from~\cite{MR0295919,MR642043,HetzelThese,MR0255446,MR0392660,MR0457275,MR0319804,MR0280416,MR0363998,MR0344157} that treated the case of finite groups\footnote{We refer to the introduction of~\cite{LdlS2020} and the references therein for a more detailed exposition of the work on finite groups.}, we obtain the following result. The equivalence between~\eqref{item:GRR} and~\eqref{item:Gnonexceptionnal} confirms Watkin's conjecture~\cite{MR0422076}.
\begin{coro}\label{cor:main}
For a finitely generated group $G$, the following are equivalent:
\begin{enumerate}
\item\label{item:GRR}
$G$ admits a $\GRR$,
\item\label{item:locFiniteGRR}
$G$ admits a finite degree $\GRR$,
\item\label{item:Gnonexceptionnal}
$G$ does not belong to the following list:
\begin{itemize}
\item the non-trivial abelian groups different from $\Z/2\Z$ and $(\Z/2\Z)^n$ for $n \geq 5$,
\item the generalized dicyclic groups,
\item the following $10$ finite groups of cardinality at most $32$\footnote{with GAP IDs respectively $[6,1], [8,3], [10,1], [12,3],[24,11], [32,26], [16,13], [16,6], [18,4], [27,3]$. The first digit in the GAP ID is the order of the group, and the second is the label of the group in GAP's numbering of groups of that order. For example, the last group in the list is of order 27, and is the third in GAP's list of groups of order 27. It is also isomorphic to the free Burnside group $B(2,3)$.}: the dihedral groups of order $6, 8, 10$, the alternating group $A_4$, the products $Q_8\times \Z/3\Z$ and $Q_8\times \Z/4\Z$ (for $Q_8$ the quaternion group) and the four groups given by the presentations
\begin{align*}
&\presentation{a,b,c}{a^2=b^2=c^2=1, abc=bca = cab},
\\
&\presentation{a,b}{a^8=b^2=1, b^{-1} a b =a^5},
\\
&\presentation{a,b,c}{a^3=b^3=c^2=(ac)^2=(bc)^2=1, ab=ba},
\\
&\presentation{a,b,c}{a^3=b^3=c^3=1, ac=ca, bc=cb,b^{-1} a b = ac}.
\end{align*}
\end{itemize}
\end{enumerate}
\end{coro}
\subsection{Consequences}
Another consequence of our result is the following fact, which was a motivation of the second-named author for~\cite{LdlS2020} and the present work, see~\cite{delaSalleTessera}. This solves a conjecture raised in~\cite{delaSalleTessera}.
\begin{coro}\label{cor:discrete_automorphism_group}
Every finitely generated group admits a finite degree Cayley graph whose automorphism group is countable.
\end{coro}
Recall the classical fact that the topology of pointwise convergence on vertices turns the automorphism group of a finite degree graph into a locally compact metrizable group: a sequence $(\phi_n)_n$ of automorphisms converges to $\phi$ if and only if for every $x$, $\phi_n(x) = \phi(x)$ for all but finitely many $n$. For this topology the stabilizer of a vertex is a compact subgroup, and therefore either finite or uncountable. Therefore Corollary~\ref{cor:discrete_automorphism_group} can be equivalently phrased as \emph{Every finitely generated group admits a finite degree Cayley graph whose automorphism group is discrete} (equivalently \emph{has finite stabilizers}).
Corollary~\ref{cor:discrete_automorphism_group} has interesting graph-theoretical consequences, that we now explain. Following~\cite{MR3156647,MR3658820,delaSalleTessera}, given two graphs $X$ and $Y$ and a positive integer~$R$, we say that $Y$ is \emph{$R$-locally $X$} if every ball of radius $R$ in $Y$ appears as a ball of radius $R$ in $X$. A graph $X$ is \emph{local to global rigid} (LG-rigid) if there is $R>0$ such that any graph that is $R$-locally $X$ is covered by $X$.
\begin{coro}\label{cor:LGrigid}
Every finitely presented group admits a finite degree Cayley graph that is $LG$-rigid.
\end{coro}
The existence of a $LG$-rigid finite degree Cayley graph is actually equivalent to finite presentability, as a non finitely presented group cannot admit LG-rigid Cayley graphs, see~\cite{delaSalleTessera}.
\subsection{About the proof}
Theorem~\ref{thm:main} is only new for groups with bounded exponents: the case of groups with elements of infinite (or arbitrarily large) order was covered in~\cite{LdlS2020}. We have therefore concentrated our efforts for finitely generated torsion groups, but the proof that we finally managed to obtain turned out to apply without much more efforts in the generality of Theorem~\ref{thm:main}.
The proof relies partly on the results from~\cite{LdlS2020}, and partly on new ideas involving random walks on groups. In particular we use some recent results by Tointon~\cite{tointon} on the probability that two independent realizations of the random walk commute. Necessary background of group theory is presented in Section~\ref{sec:reminders}. We discuss the needed contributions from~\cite{LdlS2020} in Section~\ref{sec:few_automorphisms:past}. The new aspects, including random walk reminders are presented in Section~\ref{sec:random_walks}. In the small Section~\ref{sec:conclusion}, we deduce the main theorem and its corollaries, and then in Section~\ref{sec:conjecture} we discuss a conjecture that would significantly simplify our proofs. Finally, in Section~\ref{sec:directed} we briefly discuss some directed variants of the GRR problem.
\subsection*{Acknowledgements}
Both authors thank the anonymous referees for their useful comments and suggestions.
\section{Group theory background}\label{sec:reminders}
This short section sets the group theoretical notation and terminology and contains some standard group theory results that will be used later. It can be safely skipped by most readers.
We start with a definition used in the introduction.
\begin{defi}\label{def:gen_dicyclic}
A \emph{generalized dicyclic group} is a non-abelian group with an abelian subgroup $A$ of index $2$ and an element $x$ not in $A$ such that $x^4=1$ and $xax^{-1} = a^{-1}$ for all $a \in A$.
\end{defi}
A group is said to be of \emph{exponent $n$} if every element satisfies $g^n=1$, and of \emph{bounded exponent} if it is of exponent $n$ for some integer $n$. It is known that finitely generated groups of exponent $n$ are finite if $n \in \{1,2,3,4,6\}$, but can be infinite for large $n$, see~\cite[14.2]{MR1357169}.
We shall denote the index of a subgroup $H$ of $G$ by $|G:H|$.
If $A$ is a subset of a group $G$, the \emph{centralizer} of $A$ in $G$ is the subgroup denoted $C_G(A)$ of elements of $G$ commuting with every element of $A$. The centralizer of $G$ in $G$ is the \emph{center} $Z(G)$ of $G$. If $g \in G$, we write $C_G(s)$ for $C_G(\{s\})$.
In the following, by \emph{group property} we mean of property $P$ that a group $G$ can have (``$G$ is $P$'') or not (``$G$ is not $P$'').
\begin{defi}
If $P$ and $Q$ are two group properties, we say that a group $G$ is:
\begin{itemize}
\item $P$-by-$Q$ if it admits a normal subgroup $N$ that is $P$ such that the quotient group $G/N$ is $Q$,
\item locally $P$ if every finitely generated subgroup of $G$ is $P$,
\item virtually $P$ if $G$ admits a finite index subgroup $H$ that is $P$.
\end{itemize}
\end{defi}
\goodbreak
Observe that a locally finite group $G$ is finitely generated if and only if it is finite.
A group $G$ is \emph{$2$-nilpotent} (or nilpotent of class $\leq 2$) if it is an extension $1\to N \to G \to K \to 1$ of abelian groups $N,K$ with $N \leq Z(G)$.
We will use later the following elementary fact:
\begin{lemm}\label{lemma:almost_central_extension_of_almost_abelian}
If $1\to N \to G \to K \to 1$ is an extension with $K$ virtually abelian and $|G:C_G(N)|<\infty$, then $G$ is virtually $2$-nilpotent.
\end{lemm}
\begin{proof}
If $K_1 \frac{\sqrt{5}-1}{2}$, then $G$ is virtually abelian.
\end{lemm}
\begin{proof}
Denote $c_n \coloneqq \bfP(g_n^2 = 1)$. Observe that
\begin{align*}
\bfP\left(g_n^2 = {g'_n}^2=\left(g_ng'_n\right)^2=1\right) &= \bfP\left(g_n^2 = {g'_n}^2=1\right) - \bfP\left(g_n^2 = {g'_n}^2=1 \neq\left(g_ng'_n\right)^2\right)\\
&\geq \bfP\left(g_n^2 = {g'_n}^2=1\right) - \bfP\left(\left(g_ng'_n\right)^2\neq 1\right)\\
& = c_n^2 -\left(1- c_{2n}\right).
\end{align*}
In the last line, we used that $g_ng'_n$ is distributed as $g_{2n}$.
So, if $c=\liminf_n c_n$, we obtain
\[
\liminf_n \bfP\left(g_n^2 = {g'_n}^2=\left(g_ng'_n\right)^2=1\right) \geq c^2 +c-1,
\]
which is positive if and only if $c>\tfrac{\sqrt{5}-1}{2}$. To conclude using~\eqref{eq:proba_of_commuting}, it remains to observe that $g_n^2 = {g'_n}^2=(g_ng'_n)^2=1$ implies that $g_n$ and ${g'_n}$ commute.
\end{proof}
We now proceed to prove Lemma~\ref{lemma:Mikael2}.
\begin{proof}[Proof of Lemma~\ref{lemma:Mikael2}$\MK$\eqref{item:s2_finite_conjugacy_class}]
Let $G,s,m,H_i,a_i$ satisfying~\eqref{eq:main_equation}.
Assume that $\alpha < \tfrac{3-\sqrt{5}}{4}$.
By~\eqref{eq:main_equation}, for every $g \in G$ such that $g^2 \neq 1$, we have
\begin{align*}
(sg)^2 &= 1\quad \text{or}\quad sg \in a_1 H_1\cup\,\dots\,\cup a_m H_m
\\
\intertext{and}
\left(s^{-1} g\right)^2 &= 1 \quad \text{or}\quad g \in a_1 H_1\cup\,\dots\,\cup a_m H_m.
\end{align*}
In particular, if $g^2 \neq 1$ and $g \notin \{1,s^{-1}\} (a_1 H_1\cup\,\dots\,\cup a_m H_m)$, we have $(sg)^2=(s^{-1} g)^2 = 1$, which implies
\[
g^{-1}s^2g=\left(g^{-1}s\right)(sg) = \left(s^{-1}g\right)\left(g^{-1}s^{-1}\right) = s^{-2}.
\]
Therefore we obtain
\[
\bfP\left(g_n^{-1} s^2 g_n=s^{-2}\right) \geq \bfP\left(g_n^2 \neq 1\text{ and }g_n \notin \left\{1,s^{-1}\right\} \left(a_1 H_1\cup\,\dots\,\cup a_m H_m\right)\right).
\]
If $c:=\liminf_n \bfP(g_n^2 = 1) > \tfrac{\sqrt{5}-1}{2}$, we know by Lemma~\ref{lemma:prob_of_involution} that $G$ is virtually abelian. So we can as well assume that $c \leq \tfrac{\sqrt{5}-1}{2}$. By~\eqref{eq:proba_of_coset} we can bound
\[
\limsup_n \bfP\left(g_n^{-1} s^2 g_n=s^{-2}\right) \geq 1 - c - 2 \sum_{i=1}^m \frac{1}{|G:H_i|} \geq \frac{3-\sqrt{5}-4\alpha}{2}.
\]
Observe that $\tfrac{3-\sqrt{5}-4\alpha}{2}>0$ by our assumption on $\alpha$. Now, if $g_n^{-1} s^2 g_n=s^{-2}$ and ${g'_n}^{-1} s^2 {g'_n}=s^{-2}$, then $g_n{g'_n}$ and $s^2$ commute, or equivalently $g_n{g'_n} \in C_G(s^2)$. Therefore, since $g_n{g'_n}$ is distributed as $g_{2n}$, we obtain
\[
\limsup_n \bfP\left(g_{2n}\in C_G\left(s^2\right)\right) \geq \left(\frac{3-\sqrt{5}-4\alpha}{2}\right)^2.
\]
By~\eqref{eq:proba_of_coset}, the left-hand side is equal to $\tfrac{1}{|G:C_G(s^2)|}$ and the claim is proven.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{lemma:Mikael2}$\MK$\eqref{item:involution_implies_virt_ab}] Let $G,s,m,H_i,a_i$ satisfying~\eqref{eq:main_equation}, with $s^2=1$ and $\alpha<\tfrac{(1-\alpha)^3}{24}$.
Our main goal will be to prove that two randomly chosen elements of $G$ (for well-chosen probability measures on $G$ that are not exactly random walks but mixtures of random walks) commute with non-vanishing probability. By~\cite{tointon}, we will deduce that $G$ is \emph{virtually abelian}. We proceed by contradiction, and assume that $G$ is not virtually abelian.
The element $s$ having order $2$, we can as well assume that the probability measure $\mu$ is $s$-left-invariant, that is it satisfies $\mu(sg) = \mu(g)$ for every $g \in G$. By~\eqref{eq:main_equation} and~\eqref{eq:proba_of_coset}, we know that
\[
\liminf_n \bfP\left(g_n \in \sq^{-1}(1) \cup s\sq^{-1}(1)\right)\geq 1-\alpha.
\]
By the $s$-invariance of $\mu$, $\bfP(g_n \in \sq^{-1}(1)) = \bfP(g_n \in s\sq^{-1}(1))$,so $\liminf_n \bfP(g_n^2=1)\linebreak \geq \frac{1-\alpha}{2}$.
As before, since $g^2=h^2 = (gh)^2$ implies that $g$ and $h$ commute, \eqref{eq:proba_of_commuting} implies that
\[
\lim_n \bfP\left(g_n^2 = {g'_n}^2 = \left(g_n g'_n\right)^2 = 1\right) = 0.
\]
On the other hand, $g_ng'_n$ being distributed as $g_{2n}$, we have
\[
\liminf_n \bfP\left(\left(g_ng'_n\right)^2=1 \text{ or } \left(sg_ng'_n\right)^2=1\right)\geq 1-\alpha.
\]
Let now $g_n^{(1)}, g_n^{(2)}$ and $g_n^{(3)}$ be three independent copies of the random walk on $G$ given by $\mu$. Let $A_n$ be the event
\[
A_n = \left\{ \forall 1 \leq i\neq j \leq 3, \left(g_n^{(i)}\right)^2= 1 \quad\text{and}\quad \left(sg_n^{(i)}g_n^{(j)}\right)^2=1\right\}.
\]
It follows from the preceding discussion that the difference of $\{ \forall 1 \leq i \leq 3, (g_n^{(i)})^2\linebreak= 1\}$ and $A_n$ has probability $\leq 3\alpha +o(1)$, so
\[
\liminf_n \bfP(A_n) \geq \liminf_n \bfP\left(\forall 1 \leq i \leq 3, \left(g_n^{(i)}\right)^2= 1\right)-3\alpha \geq \frac{(1-\alpha)^3}{8} - 3\alpha.
\]
This is strictly positive by assumption.
But on $A_n$, for every $1 \leq i,j \leq 3$, we have
\[
s g_n^{(i)} g_n^{(j)} s^{-1} = \left(g_n^{(i)}g_n^{(j)}\right)^{-1} = g_n^{(j)} g_n^{(i)}
\]
and therefore
\[
\left(sg_n^{(1)}\right) g_n^{(2)} g_n^{(3)} \left(sg_n^{(1)}\right)^{-1} = s g_n^{(1)} g_n^{(2)} s^{-1} s g_n^{(3)} g_n^{(1)} s^{-1} = g_n^{(2)} g_n^{(1)} g_n^{(1)} g_n^{(3)} = g_n^{(2)} g_n^{(3)}.
\]
To say it differently, $s g_n^{(1)}$ commutes with $g_n^{(2)} g_n^{(3)}$. We deduce
\[
\bfP\left(\left[s g_n^{(1)},g_n^{(2)}g_n^{(3)}\right]=1\right)\geq \bfP(A_n).
\]
Using that $\mu$ is $s$-invariant, $sg_n^{(1)}$ is distributed as $g_n^{(1)}$ and
\[
\bfP\left(\left[g_n^{(1)},g_n^{(2)}g_n^{(3)}\right]=1\right) = \bfP\left(\left[sg_n^{(1)},g_n^{(2)}g_n^{(3)}\right]=1\right).
\]
We can rewrite this as
\[
\liminf_n \mu^{\ast n} \otimes \mu^{\ast 2n}\left(\left\{(g,h) \in G \times G \,\middle|\, [g,h]=1\right\}\right) >0.
\]
Denote by $\nu_n$ the probability $\frac{1}{2}(\mu^{\ast n} + \mu^{\ast 2n})$. We clearly have $\nu_n \otimes \nu_n \geq \frac 1 4 (\mu^{\ast n} \otimes \mu^{\ast 2n})$, so
\[
\liminf_n \nu_n\otimes \nu_n \big(\left\{(g,h) \in G \middle| [g,h] = 1\right\}\big) >0.
\]
On the other hand, it follows from~\cite[Theorem~1.11]{tointon} that the sequences of measures $\mu^{\ast n}$ and $\mu^{\ast 2 n}$ (and therefore also $\nu_n$) measure index uniformly, hence the preceding is a contradiction with~\cite[Theorem~1.9]{tointon}. So our starting assumption that $G$ is not virtually abelian is absurd. This concludes the proof of the Lemma~\ref{lemma:Mikael2}.
\end{proof}
\subsection{Counting triangles}
We now state and prove a lemma on the augmentation of the number of triangles (in Cayley graphs of $G$) containing some $s_0\in G$. It complements results of~\cite[Lemma~9.2]{delaSalleTessera} and~\cite[Lemma~31]{LdlS2020} which where valid for groups with elements of infinite (respectively very large) order. The conclusion of Lemma~\ref{Lemma:9.2} is also cleaner than in~\cite{LdlS2020,delaSalleTessera}.
\begin{lemm}\label{Lemma:9.2}
Let $G$ be a finitely generated group that is not virtually abelian, and let $S\subset G\setminus \{1\}$ be a finite symmetric generating set.
Then for each $s_0$ in $S$, there exists $S\subset S'\subset G$ a finite symmetric generating set such that
\begin{enumerate}
%\renewcommand{\theenumi}{\alph{enumi}}
\item $\Delta\coloneqq S'\setminus S$ has at most $4$ elements;\label{ConditionA}
\item $\Delta$ does not contain elements of order at most $2$;\label{ConditionAA}
\item $\Delta\cap\setst{s^2}{s\in S}=\emptyset$;\label{ConditionB}
\item $\Triangles{s}{S'}\leq 6$ for all $s\in\Delta$;\label{ConditionC}
\item $\Triangles{s}{S'}=\Triangles{s}{S}$ for all $s\in S\setminus\{s_0,s_0^{-1}\}$;\label{ConditionD}
\item\label{item:cases_Lemma92}
the value of $\Triangles{s_0}{S'}-\Triangles{s_0}{S}$ is equal to
\[
\begin{cases}
1 & \text{if }s_0^2\neq 1\text{ and }C_G(s_0)\text{ is locally finite},\\
2 & \text{if }s_0^2=1\text{ and }C_G(s_0)\text{ is locally finite},\\
2 & \text{if }s_0^2\neq 1\text{ and }C_G(s_0)\text{ is not locally finite},\\
4 & \text{if }s_0^2=1\text{ and }C_G(s_0)\text{ is not locally finite}.
\end{cases}
\]
\end{enumerate}
\end{lemm}
\begin{proof}
Let $g$ be an element of $G$ and $\Delta_g\coloneqq\{g,g^{-1},s_0^{-1}g,g^{-1}s_0\}$. We will show that there exists some $g$ in $G$ such that $S'=S'_g\coloneqq S\cup\Delta_g$ works. Observe that for all $g$, the set $S'_g$ satisfies Condition~\ref{ConditionA} of the lemma, and that it satisfies~\ref{ConditionAA} if and only if $g^2 \neq 1$ and $(s_0^{-1}g)^2 \neq 1$, or equivalently $g \notin \sq^{-1}(1) \cup s_0 \sq^{-1}(1)$.
We first restrict our attention to elements $g$ such that the following two conditions hold
\begin{align}
\abs{g}_S &\geq 3\label{Condition1}
\\
\left|s_0^{-1}g\right|_S &\geq 3\label{Condition2}
\end{align}
where $\abs g_S$ is the word length of $g$ relative to the generating set $S$.
Since $S$ is finite, the number of $g\in G$ such that one of the conditions~\eqref{Condition1}-\eqref{Condition2} do not hold is finite. Also, for a $g$ satisfying Conditions~\eqref{Condition1} and~\eqref{Condition2} the intersection $\Delta_g\cap S$ is empty and Condition~\eqref{ConditionB} is automatically satisfied. Moreover, in the Cayley graph of $G$ relative to $S'_g$, a triangle with a side labelled by $s\in\Delta_g$ has at least another side labelled by an element of $\Delta_g$, otherwise $s$ would have $S$-length at most~$2$. This implies that any edge labelled by $s\in\Delta_g$ belongs to at most $6$ triangles in $\unCayley{G}{S'}$, which is Condition~\eqref{ConditionC}. Indeed, if one edge $e$ is labelled by $s\in\Delta_g$, there are at most three possibilities to put an edge labelled by $t\in \Delta_g\setminus\{s^{-1}\}$ at each extremity of $e$, thus giving a maximum number of $2\cdot 3=6$ triangles containing~$e$. This also shows that for any $s\in S$ we have
\[
\triangles_3\left(s,S'_g\right)-\triangles_3(s, S)=\left|\left\{t\in\Delta_g\,\middle|\,s^{-1}t \in \Delta_g\right\}\right|=\left|\Delta_g\cap s\Delta_g\right|\,.
\]
We now turn our attention on the set $\Delta_g\cap s\Delta_g$. Its cardinality is equal to the number of pairs $(u,v) \in \Delta_g$ such that $u=sv$. By replacing $u$ and $v$ by the words $g,g^{-1},s_0^{-1}g$ and $g^{-1}s_0$, this gives us $16$ equations in the group. Among these $16$ equations, $4$ imply that $s=1$. The $12$ remaining equations for elements of $\Delta_g\cap s\Delta_g$ are shown in Table~\ref{TableDeltag}.
\begin{table}
\caption{Possible elements of $\Delta_g\cap s\Delta_g$, where $\sq(g)= g^2$.}\label{TableDeltag}
\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|l||l|}
\hline
\text{Possible elements of }$\Delta_g\cap s\Delta_g$ & \text{Occurs if}\\
\hline\hline $g=ss_0^{-1}g$ & $s=s_0$\\
\hline $s_0^{-1}g=sg$ & $s=s_0^{-1}$\\
\hline $g^{-1}s_0=sg^{-1}$ & $s=g^{-1}s_0g$\\
\hline $g^{-1}=sg^{-1}s_0$ & $s=g^{-1}s_0^{-1}g$ \\
\hline $g=sg^{-1}$ &$\sq(g)=s$\\
\hline $g^{-1}=sg$ & $\sq(g)=s^{-1}$\\
\hline $s_0^{-1}g=sg^{-1}$ & $\sq(g)=s_0s$\\
\hline $g^{-1}=ss_0^{-1}g$ & $\sq(g)=s_0s^{-1}$\\
\hline $g=sg^{-1}s_0$ & $\sq\left(s_0^{-1}g\right)=s_0^{-1}s$\\
\hline $g^{-1}s_0=sg$ & $\sq\left(s_0^{-1}g\right)=s_0^{-1}s^{-1}$\\
\hline $s_0^{-1}g=sg^{-1}s_0$ & $\sq\left(s_0^{-1}g\right)=s$\\
\hline $g^{-1}s_0=ss_0^{-1}g$ & $\sq\left(s_0^{-1}g\right)=s^{-1}$\\
\hline
\end{tabular}
\end{center}
\end{table}
%\[
%\arraycolsep=1.6pt
%%\newcommand*\arraystretch{1.4}
%\begin{array}{|l||l|}
%\hline
%\text{Possible elements of }\Delta_g\cap s\Delta_g & \text{Occurs if}\\
%\hline\hline g=ss_0^{-1}g & s=s_0\\
%\hline s_0^{-1}g=sg & s=s_0^{-1}\\
%\hline g^{-1}s_0=sg^{-1} & s=g^{-1}s_0g\\
%\hline g^{-1}=sg^{-1}s_0 & s=g^{-1}s_0^{-1}g \\
%\hline g=sg^{-1} &\sq(g)=s\\
%\hline g^{-1}=sg &\sq(g)=s^{-1}\\
%\hline s_0^{-1}g=sg^{-1} &\sq(g)=s_0s\\
%\hline g^{-1}=ss_0^{-1}g &\sq(g)=s_0s^{-1}\\
%\hline g=sg^{-1}s_0 &\sq(s_0^{-1}g)=s_0^{-1}s\\
%\hline g^{-1}s_0=sg &\sq(s_0^{-1}g)=s_0^{-1}s^{-1}\\
%\hline s_0^{-1}g=sg^{-1}s_0 &\sq(s_0^{-1}g)=s\\
%\hline g^{-1}s_0=ss_0^{-1}g &\sq(s_0^{-1}g)=s^{-1}\\
%\hline
%\end{array}
%\]
In particular, if $g$ is as in the conclusion of Proposition~\ref{Prop:ultimate} for $F = S \cup s_0 S \cup s_0^{-1} S$ and $s=s_0$, we see that only the first two lines in this Table occur if $C_G(s_0)$ is locally finite, and only the first four occur otherwise. This implies Condition~\eqref{ConditionD}. Also, Condition~\ref{ConditionAA} holds in this case since $1$ belongs to $s_0^{-1}S\subseteq F$, and Condition~\eqref{item:cases_Lemma92} is automatically satisfied. The fact that there are infinitely many $g$ in the conclusion of Proposition~\ref{Prop:ultimate} imply that we can find such $g$ satisfying also conditions\linebreak\eqref{Condition1}-\eqref{Condition2}.
\end{proof}
We are now ready to prove Proposition~\ref{Prop:9.3}.
\begin{proof}[Proof of Proposition~\ref{Prop:9.3}]
The proof will be by successive applications of Lemma~\ref{Lemma:9.2}. To prove the proposition, it is enough that all elements of $S$ belong to at least $7$ $\tilde S$-triangles (to distinguish them from the newly added elements which will belong to at most $6$ $\tilde S$-triangles) and that the numbers $\Triangles{s^{\pm1}}{\tilde S}$ for $s$ in $S$ are all distinct.
Let $S_0 = S \cup S^{-1}$, so that $|S_0|\leq 2|S|$. Let $s_1,\,\dots,\,s_n$ be any enumeration of the elements of $S$. Apply successively Lemma~\ref{Lemma:9.2} at most $7$ times with $s_1$, to get a set $S_1$ containing $S$ and such that $\Triangles{s_1}{S_1}$ is larger than $7$. Then, applying Lemma~\ref{Lemma:9.2} for $s_2$ at most $8$ times, we can bring $\Triangles{s_2}{S_2}$ to another value $\geq 7$. Doing the same for each element of $S$, we finally obtain a set $\tilde S$ as in the lemma, after a total number of $\leq 7+8+ \dots + (\abs S+6)=\abs S(\abs S+13)/2$ successive applications of Lemma~\ref{Lemma:9.2}. At the end, we have
\[
\left|\tilde S\right| \leq |S_0|+4 \frac{\abs S(\abs S+13)}{2} \leq 2\abs S(\abs S+14).\qedhere
\]
%\let\qed\relax
\end{proof}
\section{Proofs of the main results}\label{sec:conclusion}
We collect here for completeness the straightforward proofs of the results from the introduction.
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Let $G$ be as in Theorem~\ref{thm:main}, and $S_0$ be a finite generating set. Let $S_1 = (S_0 \cup S_0^2 \cup S_0^3)\setminus\{1\}$, and $S_2$ be the generating set $\tilde S$ given by Proposition~\ref{Prop:9.3} for $S=S_1$. By Proposition~\ref{Prop:9.3} and the discussion preceding it, every automorphism of $\unCayley{G}{S_2}$ preserves the $S_1$-colours: $\phi(gs) \in \{\phi(g) s,\phi(g) s^{-1}\}$ for every $g \in G$ and $s \in S_1$. By Theorem~\ref{orientation-rigid}, $\phi$ is a left-translation by an element of~$G$.
\end{proof}
\begin{proof}[Proof of Corollary~\ref{cor:main}]
If $G$ is finite, the equivalence is the content of~\cite{MR642043}. We can assume that $G$ is infinite and finitely generated. The implication~\eqref{item:locFiniteGRR}$\implies$\eqref{item:GRR} is obvious, and the implication~\eqref{item:GRR}$\implies$\eqref{item:Gnonexceptionnal} is known and very easy, see~\cite{MR0280416}. For the reader's convenience, we recall the argument. If an infinite finitely generated group $G$ is either abelian or generalized dicyclic then there is a nontrivial permutation $\phi$ of $G$ satisfying $\phi(gh) \in \{\phi(g)h,\phi(g)h^{-1}\}$ for every $g,h \in G$: take for $\phi$ the inverse map if $G$ is abelian, and the map that is the identity on $A$ and the inverse on $G \setminus A$ if $G$ is generalized dicyclic and $x,A$ are as in Definition~\ref{def:gen_dicyclic}. In particular, $\phi$ induces an automorphism of every Cayley graph of $G$, different from a translation. Observe that this argument even rules out the existence of a non-locally finite $\GRR$.
We have to justify~\eqref{item:Gnonexceptionnal}$\implies$\eqref{item:locFiniteGRR}. If $G$ is not virtually abelian, then~\eqref{item:locFiniteGRR} is the conclusion of Theorem~\ref{thm:main}. Otherwise, $G$ admits an element of infinite order (a torsion abelian finitely generated group is finite), and~\cite[Theorem~2]{LdlS2020} applies and proves~\eqref{item:locFiniteGRR}.
\end{proof}
\begin{proof}[Proof of Corollary~\ref{cor:discrete_automorphism_group}]
If $G$ is not virtually abelian, this is a particular case of Theorem~\ref{thm:main}. Otherwise, as explained in the proof of Corollary~\ref{cor:main}, $G$ has an element of infinite order and~\cite[Theorem J]{delaSalleTessera} applies.
\end{proof}
\begin{proof}[Proof of Corollary~\ref{cor:LGrigid}]
Combine Corollary~\ref{cor:discrete_automorphism_group} with~\cite[Theorem~E]{delaSalleTessera}.
\end{proof}
\section{A conjecture on the squares of a random walk}\label{sec:conjecture}
We mentionned before Lemma~\ref{lemma:prob_of_involution} that we expect that the following conjecture holds.
\begin{conj}\label{conj:proba_of_sq}
Let $G$ be a finitely generated group that is not virtually abelian, $\mu$ be a symmetric probability measure on $G$ with finite and generating support containing the identity, and $(g_n)$ a realization of the random walk on $G$ given by $\mu$. Then
\begin{equation}\label{eq:proba_of_square}
\forall a \in G, \lim_n \bfP\left(g_n^2=a\right) = 0.
\end{equation}
\end{conj}
Better, there should be a function $f:(0,1] \to \N$ such that, in a group $G$, if
\[
\exists a \in G, \limsup_n \bfP\left(g_n^2=a\right) \geq \varepsilon,
\]
then $G$ admits an abelian subgroup of index $\leq f(\varepsilon)$. This is known to be true for finite groups~\cite{MR3899225,MR1242094}.
The main case of the conjecture is when $a=1$: indeed with similar methods as the reduction to $F=\{1\}$ in the proof of Proposition~\ref{Prop:ultimate}, one can show that the case $a=1$ in Conjecture~\ref{conj:proba_of_sq} implies the full conjecture for $G$ not virtually $2$-nilpotent.
Let us mention here that this conjecture would allow to greatly simplify our proofs, as it would imply immediately the following variant of Proposition~\ref{Prop:ultimate}, which also implies the main Theorem~\ref{thm:main} by the same argument.
\begin{lemm}
If Conjecture~\ref{conj:proba_of_sq} holds for $G$, then for every $s \in G$ and $F \subset G$ finite there are infinitely many $g \in G \setminus (\sq^{-1}(F) \cup s \sq^{-1}(F))$ such that
\[
\begin{cases}
g^{-1} s g \notin F&\text{if }C_G(s)\text{ has infinite index in}\,G\\
g^{-1} s g = s&\text{otherwise}.
\end{cases}
\]
\end{lemm}
\begin{proof}
We prove the stronger fact that the probability that $g=g_n$ satisfies the conclusion of the lemma is $1-o(1)$ when $|G:C_G(s)|=\infty$, and $\frac{1}{|G:C_G(s)|} - o(1)$ otherwise.
It follows from~\eqref{eq:proba_of_square} that
\begin{align}
\lim_n \bfP\left(g_n \in \sq^{-1}(F)\right) &= 0.\nonumber
\\
\intertext{It also implies that}
\lim_n \bfP\left(g_n \in s \sq^{-1}(F)\right) &= 0.\label{eq:proba_of_square3}
\end{align}
To justify this, we need to introduce an independant copy $(g'_n)_{n\,\geq\,0}$ of the random walk $(g_n)$. Since the support of $\mu$ is symmetric and generates $G$, there is a $k$ such that $\bfP(g'_k=s^{-1})>0$. So using that $g_{n+k}$ is distributed as $g'_k g_n$, we obtain
\begin{align*}
\bfP\left(g_{n+k} \in \sq^{-1}(F)\right) &\geq \bfP\left(s^{-1}g_n \in \sq^{-1}(F)\quad\text{and}\quad g'_k = s^{-1}\right) \\
& = \bfP\left(g_n \in s \sq^{-1}(F)\right) \bfP\left(g'_k = s^{-1}\right).
\end{align*}
This proves~\eqref{eq:proba_of_square3}. Moreover, it follows from~\eqref{eq:proba_of_coset} that
\[
\begin{cases}
\lim_n\bfP\left(g_n^{-1} s g_n \notin F\right) = 1 &\text{if }\left|G:C_G(s)\right|=\infty\\
\lim_n\bfP\left(g_n^{-1} s g_n =s\right) = \frac{1}{\left|G:C_G(s)\right|}&\text{otherwise}.
\end{cases}
\]
The conclusion follows.
\end{proof}
\section{Directed and oriented graphs}\label{sec:directed}
A natural variation of Cayley graphs is the concept of \emph{Cayley digraph} (directed graph). Given a group $G$ and a (not necessarily symmetric) generating set $S\subseteq G\setminus\{1\}$, the Cayley digraph $\orCayley{G}{S}$ is the digraph with vertex set $G$ and with an arc (directed edge) from $g$ to $h$ if and only if $g^{-1}h\in S$.
A Cayley digraph $\orCayley{G}{S}$ of $G$ whose automorphism group acts freely on its vertex set is called a \emph{digraphical regular representation}, or $\DRR$. If moreover $\orCayley{G}{S}$ has no bigons (that is if $S\cap S^{-1}=\emptyset$) then we speak of an \emph{oriented graphical regular representation}, or $\ORR$.
We have the directed equivalent of Corollary~\ref{cor:main}:
\begin{prop}\label{prop:DRR}
For a finitely generated group $G$, the following are equivalent:
\begin{enumerate}
\item\label{item:DRR}
$G$ admits a $\DRR$,
\item\label{item:locFiniteDRR}
$G$ admits a finite degree $\DRR$,
\item\label{item:GnonDexceptionnal}
$G$ is neither the quaternion group $Q_8$, nor any of $(\Z/2\Z)^2$, $(\Z/2\Z)^3$, $(\Z/2\Z)^4$, $(\Z/3\Z)^2$.
\end{enumerate}
\end{prop}
\begin{proof}
If $G$ is finite, the equivalence is the content of~\cite{MR603394}. We can assume that $G$ is infinite and finitely generated. The implication~\eqref{item:locFiniteDRR} $\implies$\eqref{item:DRR} is obvious, and the implication~\eqref{item:DRR}$\implies$\eqref{item:GnonDexceptionnal} is empty for infinite groups. We have to justify~\eqref{item:GnonDexceptionnal}$\implies$\eqref{item:locFiniteDRR}.
Let $S$ be a finite generating set of $G$. Using Proposition~\ref{Prop:9.3} and~\cite[Lemma~32]{LdlS2020} we obtain a finite generating set $S\subseteq \tilde S\subset G$ such that for all $s\in S$ and $t\in\tilde S$, if $\Triangles{s}{\tilde S}=\Triangles{t}{\tilde S}$ then $t=s$ or $t=s^{-1}$. By~\cite[Lemma~5]{LdlS2020} and~\cite[Proposition~6]{LdlS2020} there exists a generating set $T\subseteq\tilde S$ such that $\orCayley{G}{T}$ is a $\DRR$. Moreover, $T\cap T^{-1}$ consist only of elements of order $2$.
\end{proof}
Observe that the equivalence of~\eqref{item:DRR} and~\eqref{item:GnonDexceptionnal} was the content of~\cite{MR0498225,MR603394}.
We will conclude with the oriented equivalent of Corollary~\ref{cor:main} and thus answer~\cite[Problem 2.7]{MR603394}. Recall that a generalized dihedral group $G$ is the semi-direct product $A\rtimes \Z/2\Z$ where $A$ is an abelian group and $\Z/2\Z$ acts on $A$ by inversion.
\begin{prop}
For a finitely generated group $G$, the following are equivalent:
\begin{enumerate}
\item\label{item:ORR}
$G$ admits an $\ORR$,
\item\label{item:locFiniteORR}
$G$ admits a finite degree $\ORR$,
\item\label{item:GnonOexceptionnal}
$G$ does not belong to the following list:
\begin{itemize}
\item the non-trivial generalized dihedral groups,
\item the following $11$ finite groups of cardinality at most $64$: $Q_8$, $\Z/4\Z\times\Z/2\Z$, $\Z/4\Z\times(\Z/2\Z)^2$, $\Z/4\Z\times(\Z/2\Z)^3$, $\Z/4\Z\times(\Z/2\Z)^4$, $(\Z/3\Z)^2$, $\Z/3\Z\times(\Z/2\Z)^3$, $D_4 \circ D_4$ (the central product of two dihedral groups of order $8$, which has order $32$) and the three groups (of respective orders $16$, $16$ and $32$) given by the presentations
\begin{align*}
&\left\langle a,b\,\middle|\, a^4 = b^4=(ab)^2=\left(ab^{-1}\right)^2=1\right\rangle,
\\
&\left\langle a,b,c \,\middle|\, a^4 = b^4=c^4=(ba)^2=\left(ba^{-1}\right)^2=(bc)^2=\left(bc^{-1}\right)^2=1\right.\\
&\mkern242mu\left. a^2c^{-2}=a^2b^{-2}=cac^{-1}a^{-1}=1\right\rangle,
\\
&\left\langle a,b,c\,\middle|\, a^4 = b^4=c^4=(ab)^2=\left(ab^{-1}\right)^2=(ac)^2=\left(ac^{-1}\right)^2=1\right.\\
&\mkern256mu\left.(bc)^2=\left(bc^{-1}\right)^2=a^2b^2c^2=1\right\rangle.
\end{align*}
\end{itemize}
\end{enumerate}
\end{prop}
\begin{proof}
If $G$ is finite, the equivalence is the content of~\cite{MR3873496}, while every generating set of a generalized dihedral group contains an element of order $2$ (namely any element not in $A$). Once again, we have to justify~\eqref{item:GnonOexceptionnal}$\implies$\eqref{item:locFiniteORR} for $G$ infinite.
Let $G$ be a finitely generated group which is not generalized dihedral. Then by~\cite[Proposition~5.2]{MR0498225} there exists a finite generating set $S$ of $G$ without elements of order~$2$. Then the generating set $\tilde S$ given by Proposition~\ref{Prop:9.3} and~\cite[Lemma~32]{LdlS2020} has also no elements of order $2$. This implies that for $T$ given by~\cite[Lemma~5]{LdlS2020} and~\cite[Proposition~6]{LdlS2020} the $\DRR$ $\orCayley{G}{T}$ is actually an $\ORR$.
\end{proof}
%\providecommand{\noopsort}[1]{}
%\newcommand*\cprime{$'$}
\bibliography{leemann}
\end{document}