# Canonization of a random circulant graph by counting walks

Oleg Verbitsky Institut für Informatik, Humboldt-Universität zu Berlin,
Germany. Supported by DFG grant KO 1053/8–2. On leave from the IAPMM, Lviv,
Ukraine. Maksim Zhukovskii Department of Computer Science, University of
Sheffield, UK.

###### Abstract

It is well known that almost all graphs are canonizable by a simple
combinatorial routine known as color refinement. With high probability, this
method assigns a unique label to each vertex of a random input graph and,
hence, it is applicable only to asymmetric graphs. The strength of
combinatorial refinement techniques becomes a subtle issue if the input graphs
are highly symmetric. We prove that the combination of color refinement with
vertex individualization produces a canonical labeling for almost all
circulant digraphs (Cayley digraphs of a cyclic group). To our best knowledge,
this is the first application of combinatorial refinement in the realm of
vertex-transitive graphs. Remarkably, we do not even need the full power of
the color refinement algorithm. We show that the canonical label of a vertex
$v$ can be obtained just by counting walks of each length from $v$ to an
individualized vertex.

##  1 Introduction

As it is well known, the graph isomorphism problem is very efficiently
solvable in the average case by a simple combinatorial method known as _color
refinement_ (also _degree refinement_ or _naive vertex classification_). When
a random graph $\mathbf{G}_{n}$ on $n$ vertices is taken as an input, this
algorithm produces a canonical labeling of all vertices in $\mathbf{G}_{n}$ by
coloring them initially by their degrees and then by refining the color
classes as follows: Two equally colored vertices $u$ and $v$ get new distinct
colors if one of the initial colors occurs in the neighborhoods of $u$ and $v$
with different multiplicity. In this way, every vertex gets a unique color
with probability $1-O(n^{-1/7})$ (Babai, Erdős, and Selkow [4]). Thus, the
method produces a canonical labeling for almost all graphs on a fixed set of
$n$ vertices.

This approach is not applicable to regular graphs, even with many refinement
rounds, because if all vertices have the same degree, then the refinement step
makes obviously no further vertex separation. Weisfeiler and Leman [31] came
up with a more powerful refinement algorithm which colors pairs of vertices
instead of single vertices. The idea can be lifted to $k$-tuples of vertices,
for each integer parameter $k$, and the general approach is referred to as the
$k$-dimensional Weisfeiler-Leman algorithm, abbreviated as
$k\text{-}\mathrm{WL}$. Thus, $2\text{-}\mathrm{WL}$ is the original algorithm
in [31], and $1\text{-}\mathrm{WL}$ corresponds to color refinement.
Remarkably, $2\text{-}\mathrm{WL}$ is powerful enough to produce a canonical
labeling for almost all regular graphs of a given vertex degree (Bollobás [8];
see also [22]).

Further restriction of regular input graphs to vertex-transitive graphs is
challenging for combinatorial refinement because no vertex classification is
at all possible in this case. Indeed, $2\text{-}\mathrm{WL}$ assigns the same
color to any two vertices $u$ and $v$ because $u$ is mapped to $v$ by an
automorphism of the graph. The same holds for any dimension $k$. In fact, the
Cai-Fürer-Immerman construction [10] of non-isomorphic graphs $X_{k}$ and
$Y_{k}$ indistinguishable by $k\text{-}\mathrm{WL}$ can be modified so that
these graphs become vertex-transitive [17]. A natural way to enhance this
algorithmic approach is to combine it with vertex individualization [24],
which proves to be advantageous in many contexts; see, e.g., [3]. Note that
$(k+k^{\prime})\text{-}\mathrm{WL}$ supersedes any combination of
$k\text{-}\mathrm{WL}$ with prior individualization of $k^{\prime}$ vertices.
As a consequence, isomorphism of vertex-transitive graphs cannot be solved by
a constant-dimensional WL algorithm even under individualization of any
constant number of vertices.

Motivated by the question of whether or not these basic obstacles persist in
the average case setting, we focus in this paper on Cayley graphs and, more
specifically, on circulant graphs, that is, Cayley graphs of a cyclic group.
While the canonization problem for this class of graphs is known to be
solvable in polynomial time [16] by advanced algebraic methods, it is an open
question whether this can done by using $k\text{-}\mathrm{WL}$ for some
dimension $k$; see [29]. This poses an ongoing challenge for the combinatorial
refinement method, especially because the research on isomorphism of circulant
graphs has a long history with many deep results (see [2, 16, 27, 26] and the
references therein) and because $k\text{-}\mathrm{WL}$ with small dimension
$k$ is known to be applicable to many other natural graphs classes (like,
e.g., planar graphs [21]). Circulant graphs are also interesting on its own
right as they naturally appear and are intensively investigated in many other
theoretical and applied areas; see, e.g., the books [9, 12, 14]. After all,
our primary motivation for the study of circulant graphs is that this is the
most natural first choice of a graph class for benchmarking of combinatorial
refinement in the realm of vertex-transitive graphs.

Our goal is to show that the individualization-refinement approach can be used
to canonize almost all circulants at minimal computational costs. Our
treatment covers also circulant directed graphs, which is advantageous for
expository purposes as the case of digraphs is technically somewhat simpler.
We show that the individualization of a single vertex suffices for random
circulant digraphs, and that two individualized vertices are enough in the
undirected case (in fact, we just perform color refinement twice, each time
with a single individualized vertex). In both the directed and the undirected
cases we keep the overall running time within $O(n^{2}\log n)$, which is the
standard running time of color refinement [11]. This is possible due to the
fact that our input graphs are vertex-transitive and, hence, it does not
actually matter which one of the vertices is individualized. Here, $n$ denotes
the number of vertices, that is, our time bound is actually linearithmic in
the input length if the input (di)graph is presented by the adjacency matrix
and the cyclic structure is not explicitly given (see below the discussion of
different representation concepts). Note also that, as one can expect, our
average-case bound $O(n^{2}\log n)$ is substantially better than the worst-
case bound resulting from [16]. We summarize our main result in a somewhat
condensed form as follows.

######  Theorem 1.1.

A uniformly distributed random circulant (di)graph is with probability at
least $1-n^{-1/2+o(1)}$ canonizable by color refinement combined with vertex
individualization in running time $O(n^{2}\log n)$.

Theorem 1.1 includes two statements, one for undirected graphs (where all
undirected circulant graphs are equiprobable) and the similar statement for
directed graphs. Note that the concept of a uniform distribution of $n$-vertex
circulants is somewhat ambiguous as the notion of an _$n$ -vertex circulant_
alone can be defined in three different natural ways:

  * •

as a Cayley (di)graph of the cyclic group $\mathbb{Z}_{n}$,

  * •

as an isomorphism class of Cayley (di)graphs of $\mathbb{Z}_{n}$ (which we
call an _unlabeled circulant_),

  * •

as a (di)graph on the vertex set $\\{0,1,\ldots,n-1\\}$ isomorphic to a Cayley
(di)graph of $\mathbb{Z}_{n}$ (which we call a _labeled circulant_).

We prove Theorem 1.1 first for random Cayley (di)graphs and then extend it to
the other two concepts. The transition from one distribution to another is
quite general and is based on known results in algebraic graph theory [7, 13,
26].

Remarkably, we show that canonization of a random circulant does not even need
the full power of color refinement and can actually be accomplished by a
weaker algorithmic tool. Let $G$ be an arbitrary (di)graph on the vertex set
$V=\\{0,1,\ldots,n-1\\}$, and let $T\subseteq V$. The _walk matrix_
$W_{T}=(w_{ij})_{i,j\in V}$ is defined by setting $w_{ij}$ to be the number of
walks of length $j$ from the vertex $i$ to a vertex in $T$. If $A$ is the
adjacency matrix of $G$ and $\chi_{T}$ denotes the characteristic vector of
the subset $T$, then $W_{T}$ is formed by the columns
$\chi_{T},A\chi_{T},A^{2}\chi_{T},\ldots,A^{n-1}\chi_{T}$. The theory of walk
matrices, including their applicability to isomorphism testing, has been
developed by Godsil [18] and by Liu and Siemons [23]. Let $G_{T}$ be obtained
from $G$ by coloring all vertices in $T$ by the same color. We call $G_{T}$
_walk-discrete_ if the rows of $W_{T}$ are pairwise different. For any walk-
discrete $G_{T}$, the walk matrix $W_{T}$ yields a canonical labeling of the
vertices of $G_{T}$. This purely algebraic canonization method can be
superseded by the purely combinatorial method of color refinement because if
$w_{uj}\neq w_{vj}$ for some $j$, then color refinement assigns distinct
colors to the vertices $u$ and $v$ in $G_{T}$ (see Section 2.1 for details).

Let $W=W_{V}$ be the _standard_ walk matrix of $G=G_{V}$. Obviously, $G$ is
walk-discrete whenever $W$ is non-singular. Noteworthy, the rank of $W$ for an
undirected graph $G$ is equal to the number of different _main_ eigenvalues of
the adjacency matrix $A$; see [19]. As shown by O’Rourke and Touri [28], a
random undirected graph $\mathbf{G}_{n}$ has non-singular walk matrix with
high probability. As a consequence, $\mathbf{G}_{n}$ is with high probability
canonizable by computing its standard walk matrix.

The above theory essentially exploits the fact that the adjacency matrices of
undirected graphs are symmetric and, by this reason, does not apply to
directed graphs. Nevertheless, we obtain the following spectral criterion for
circulant digraphs.

######  Lemma 1.2.

Let $X$ be a Cayley digraph of a cyclic group and $X_{0}=X_{\\{0\\}}$ be its
version with one individualized vertex. Let $W_{0}$ be the walk matrix of
$X_{0}$. Then $W_{0}$ is non-singular (implying that $X_{0}$ is walk-discrete)
if and only if $X$ has simple spectrum, that is, all eigenvalues of $X$ are
pairwise distinct.

Suppose now that $X$ is an undirected Cayley graph of $\mathbb{Z}_{n}$. In
this case, the map $x\mapsto(-x)\bmod n$ is an automorphism of $X_{0}$, which
implies that the walk matrix of $X_{0}$ has at most $\lceil(n+1)/2\rceil$
different rows. If this bound is achieved, we call $X_{0}$ _walk-saturated_.
As we will show, this property is sufficient for efficient canonization of
$X$. On the other hand, the spectrum of $X$ has at most $\lceil(n+1)/2\rceil$
different eigenvalues. If there are exactly so many eigenvalues, we say that
$X$ has _saturated spectrum_. We have the following analog of Lemma 1.2 for
the undirected case.

######  Lemma 1.3.

Let $X$ be a Cayley graph of the cyclic group $\mathbb{Z}_{n}$. Then $W_{0}$
has the maximum possible rank $\lceil(n+1)/2\rceil$ (implying that $X_{0}$ is
walk-saturated) if and only if $X$ has saturated spectrum.

Lemmas 1.2 and 1.3 imply that the walk matrix can be used for canonization of
a circulant whenever it has simple (for digraphs) or saturated (for graphs)
spectrum. The following theorem, therefore, estimates the probability that
this canonization method is successful on a random circulant.

######  Theorem 1.4.

  1. 1.

A uniformly distributed random Cayley digraph of $\mathbb{Z}_{n}$ has simple
spectrum with probability at least $1-n^{-1/2+o(1)}$.

  2. 2.

A uniformly distributed random Cayley graph of $\mathbb{Z}_{n}$ has saturated
spectrum with probability at least $1-n^{-1/2+o(1)}$.

Theorem 1.1 follows from Theorem 1.4 on the account of Lemmas 1.2 and 1.3.
Theorem 1.4 is our main technical contribution, which can be of independent
interest in the context of the research on random circulant matrices [9, 25].

The paper is organized as follows. A detailed description of our canonical
labeling algorithm is given in Section 2. Lemmas 1.2 and 1.3 are proved in
Section 3, where they are restated as Lemma 3.1. Theorem 1.4 is proved in
Section 4. The proof of Theorem 1.1 is completed in Section 5.

##  2 The walk matrix and color refinement

###  2.1 Definitions and a relationship

Speaking of a directed graph or, for short, _digraph_ $G=(V,E)$, we always
assume that $G$ is loopless, that is, the adjacency relation $E\subset V^{2}$
is irreflexive. Without loss of generality we suppose that $G$ is defined on
the vertex set $V=\\{0,1,\ldots,n-1\\}$. If $E$ is symmetric, $G$ is referred
to as an (undirected) _graph_. The definitions given below for digraphs apply,
as a special case, also to graphs.

For $t\in V$, we write $G_{t}$ to denote the digraph $G$ with distinguished
vertex $t$. The vertex $t$ is called _terminal_ or _individualized_. We
consider $G_{t}$ to be a vertex-colored digraph where all vertices are equally
colored with the exception of $t$ which has a special color. An isomorphism
from $G_{t}$ to another vertex-individualized digraph $H_{u}$ is defined as a
digraph isomorphism from $G$ to $H$ taking $t$ to $u$.

A _walk_ in $G$ is a sequence of vertices $x_{0}x_{1}\ldots x_{k}$ such that
$(x_{i},x_{i+1})\in E$ for every $0\leq i<k$. We say that $x_{0}x_{1}\ldots
x_{k}$ is a walk of length $k$ from $x_{0}$ to $x_{k}$. Note that a one-
element sequence $x_{0}$ is a walk of length $0$. Given a digraph $G_{t}$ with
terminal vertex $t$, we define its _walk matrix_ $W_{t}=(w_{x,k})_{0\leq
x,k<n}$ by setting $w_{x,k}$ to be the number of walks of length $k$ from $x$
to $t$. Let

$W_{t}(x)=(w_{x,0},w_{x,1},\ldots w_{x,n-1})$

be the row of $W_{t}$ corresponding to the vertex $x$. If $\phi$ is an
isomorphism from $G_{t}$ to $H_{u}$, then clearly $W_{u}(\phi(x))=W_{t}(x)$.
This means that $W_{t}(x)$ can be used as a canonical label for a vertex $x$
in $G_{t}$. We call $G_{t}$ _walk-discrete_ if $W_{t}(x)\neq
W_{t}(x^{\prime})$ for all $x\neq x^{\prime}$. Thus, the walk matrix yields a
canonical labeling for the class of walk-discrete digraphs with an
individualized vertex.

As it was mentioned in Section 1, the walk matrix is efficiently computable by
linear algebraic operations. For walk-discrete digraphs, the corresponding
canonical labeling can also be obtained combinatorially by the _color
refinement_ algorithm (CR). Let $C_{0}$ be the initial coloring of $G_{t}$,
that is, $C_{0}(x)=C_{0}(x^{\prime})$ and $C_{0}(x)\neq C_{0}(t)$ for all
$x\neq t$ and $x^{\prime}\neq t$. CR iteratively computes new colorings

$C_{i+1}(x)=\left(C_{i}(x),\left\\{\\!\\!\left\\{C_{i}(y)\right\\}\\!\\!\right\\}_{y\in
N(x)}\right),$

where $\left\\{\\!\\!\left\\{\right\\}\\!\\!\right\\}$ denotes a multiset and
$N(x)=\\{y\,:\,\begin{array}[]{@{}l@{}}(x,y)\in E\end{array}\\}$ is the out-
neighborhood of $x$. The color classes of $C_{i+1}$ refine the color classes
of $C_{i}$. As soon as the color partition stabilizes, CR terminates and
outputs the current coloring at that point. To prevent the exponential
increase of the color encoding, the colors are renamed after each refinement
step (we never need more than $n$ color names). A relationship between CR and
the walk counts was observed in [30]. We use the following adaptation of this
result for our purposes.

######  Lemma 2.1.

If $w_{x,k}\neq w_{x^{\prime},k}$, then $C_{k}(x)\neq C_{k}(x^{\prime})$.

###### Proof.

Using the induction on $k$, we prove that $w_{x,k}=w_{x^{\prime},k}$ whenever
$C_{k}(x)=C_{k}(x^{\prime})$. In the base case of $k=0$, the equalities
$w_{x,0}=w_{x^{\prime},0}$ and $C_{0}(x)=C_{0}(x^{\prime})$ are equivalent by
definition. Assume that $C_{k}(y)=C_{k}(y^{\prime})$ implies
$w_{y,k}=w_{y^{\prime},k}$ for all $y$ and $y^{\prime}$. Let
$C_{k+1}(x)=C_{k+1}(x^{\prime})$. By the definition of the refinement step, we
have $\left\\{\\!\\!\left\\{C_{k}(y)\right\\}\\!\\!\right\\}_{y\in
N(x)}=\left\\{\\!\\!\left\\{C_{k}(y)\right\\}\\!\\!\right\\}_{y\in
N(x^{\prime})}$. Using the induction assumption, from here we derive the
equality $\left\\{\\!\\!\left\\{w_{y,k}\right\\}\\!\\!\right\\}_{y\in
N(x)}\allowbreak=\left\\{\\!\\!\left\\{w_{y,k}\right\\}\\!\\!\right\\}_{y\in
N(x^{\prime})}$. The equality $w_{x,k+1}=w_{x^{\prime},k+1}$ now follows by
noting that $w_{x,k+1}=\sum_{y\in N(x)}w_{y,k}$. ∎

Lemma 2.1 shows that a canonical labeling of a walk-discrete digraph $G_{t}$
can be obtained by running CR on $G_{t}$ rather than by directly computing the
walk matrix. Recall that CR can be implemented in time $O(n^{2}\log n)$ [6,
11, 20].

###  2.2 Cayley graphs of a cyclic group

Let $\mathbb{Z}_{n}$ denote a cyclic group of order $n$. More specifically, we
let $\mathbb{Z}_{n}=\left\\{0,1,\ldots,n-1\right\\}$ and consider the addition
modulo $n$ on this set. The _Cayley digraph_
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$ is defined by a _connection set_
$S\subseteq\mathbb{Z}_{n}\setminus\\{0\\}$ as follows: $V(X)=\mathbb{Z}_{n}$
and $(x,y)\in E(X)$ if and only if $y-x\in S$. Note that $S=N(0)$, the out-
neighborhood of $0$. If $S$ is _inverse-closed_ , i.e., $S=-S$, then $E(X)$ is
symmetric and we speak of a _Cayley graph_. Cayley (di)graphs of
$\mathbb{Z}_{n}$ are also called _circulant (di)graphs_ or _circulants_.

For $u\in\mathbb{Z}_{n}$, let $X_{u}$ be the vertex-individualized version of
$X$. Since $X$ is vertex-transitive, all $X_{u}$ are isomorphic to each other,
and we can speak about $X_{0}$ without loss of generality. Clearly, in order
to canonize $X$, it is sufficient to canonize $X_{0}$. Therefore, the
canonization method in the preceding subsection applies to any Cayley digraph
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$ provided that $X_{0}$ is walk-
discrete. We just have to individualize an arbitrary vertex of $X$ and then
run CR.

This method does not work for circulant _graphs_. Indeed, define
$\rho:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ by $\rho(x)=-x$. If $S=-S$,
then $\rho$ is an automorphism of $X=\operatorname{Cay}(\mathbb{Z}_{n},S)$
and, hence, $W_{0}(\rho(x))=W_{0}(x)$. This implies that the walk matrix
$W_{0}$ has at most $\lceil(n+1)/2\rceil$ different rows, and $X_{0}$ cannot
be walk-discrete. If this maximum is attained, we call $X_{0}$ _walk-
saturated_.

######  Lemma 2.2.

Let $X=\operatorname{Cay}(\mathbb{Z}_{n},S)$, where $S=-S$, and suppose that
$X_{0}$ is walk-saturated. Fix $u\neq 0$ such that $u\neq n/2$ if $n$ is even.
Then

$(W_{0}(x),W_{u}(x))\neq(W_{0}(y),W_{u}(y))$

for any two different vertices $x$ and $y$ of $X$.

###### Proof.

Since $X_{0}$ is walk-saturated, the equality $W_{0}(x)=W_{0}(y)$ for $x\neq
y$ is possible only if $y=\rho(x)$, i.e., $y=-x$ in $\mathbb{Z}_{n}$. Note
that $W_{u}(x)=W_{0}(x-u)$. Therefore, the equality $W_{u}(x)=W_{u}(y)$
implies that $y=2u-x$. The equalities $y=-x$ and $y=2u-x$ can be fulfilled
simultaneously only if $2u=0$, which is excluded. ∎

Lemma 2.2 justifies the correctness of the following algorithm for the class
of walk-saturated circulant graphs.

Canonical labeling algorithm

Input: a circulant graph $X$.

  1. 1.

Individualize an arbitrary vertex of $X$. By vertex-transitivity, we can
without loss of generality assume that the individualized vertex is $0$.

  2. 2.

Run CR on $X_{0}$. Let $C$ be the obtained coloring of the vertex set.

  3. 3.

Let $c$ be the lexicographically least color such that there are exactly two
vertices $u_{1}$ and $u_{2}$ with $C(u_{1})=C(u_{2})=c$. If such $c$ does not
exist, then give up. Let $u$ be any of $u_{1}$ and $u_{2}$. Individualize $u$
in $X$.

  4. 4.

Run CR on $X_{u}$. Let $C^{\prime}$ be the obtained coloring.

  5. 5.

To each vertex $x$, assign the label $L(x)=(C(x),C^{\prime}(x))$.

  6. 6.

Check that all labels $L(x)$ are pairwise distinct. If not, then give up.

For each circulant input graph, our canonization algorithm either produces a
vertex labeling $L$ or explicitly gives up (doing always the same for
isomorphic inputs). The labeling $L$ is canonical because it does not depend
on which vertex is individualized in Step 1 (by vertex-transitivity) nor in
Step 3 (because $u_{1}$ and $u_{2}$ are interchangeable by an automorphism of
$X_{0}$). Lemma 2.2 ensures that the algorithm succeeds whenever $X_{0}$ is
walk-saturated, and this will allow us to estimate the success probability
based on Lemma 1.3 (cf. Lemma 3.1) and Theorem 1.4.

Finally, we remark that if the algorithm is run on a non-circulant input graph
and outputs a vertex labeling, then this labeling does not need to be
canonical. To make it canonical in all cases, Steps 1 and 3 have to be
performed for all possible individualized vertices, which can yield $2n$
different labelings $L_{1},\ldots,L_{2n}$. Of all these candidate labelings,
the algorithm chooses that which yields the isomorphic copy of $X$ with
lexicographically least adjacency matrix. The running time of this algorithm
variant is $O(n^{3}\log n)$. The similar modification is as well possible in
the case of digraphs.

##  3 The walk matrix and the spectrum of circulants

###  3.1 The spectrum of a circulant

Let $A=(a_{ij})$ be the adjacency matrix of a circulant digraph $X$, that is,
$A$ is the 0–1 matrix whose rows and columns are indexed by the elements
$0,1,\ldots,n-1$ of $\mathbb{Z}_{n}$ such that $a_{ij}=1$ exactly when
$(i,j)\in E(X)$, that is, $j-i\in S$. Note that $A$ is a _circulant matrix_ ,
which means that the $(i+1)$-th row of $A$ is obtained from its $i$-th row by
the cyclic shift in one element to the right.

Let $\omega$ be an $n$-th root of unity, i.e., $\omega\in\mathbb{C}$ and
$\omega^{n}=1$. For the vector
$V_{\omega}=(1,\omega,\omega^{2},\ldots,\omega^{n-1})^{\top}$, the definition
of a circulant matrix easily implies the equality

$A\,V_{\omega}=\left(a_{0}+a_{1}\omega+a_{2}\omega^{2}+\cdots+a_{n-1}\omega^{n-1}\right)\,V_{\omega}=\left(\sum_{j\in
S}\omega^{j}\right)V_{\omega},$

where $(a_{0},a_{1},a_{2},\ldots,a_{n-1})$ is the first row of $A$, that is,
the characteristic vector of $S\subset\mathbb{Z}_{n}$. We conclude that
$V_{\omega}$ is an eigenvector of $A$ corresponding to the eigenvalue
$\lambda_{\omega,S}=\sum_{j\in S}\omega^{j}$.

Let $\zeta_{n}$ be a primitive $n$-th root of unity. To be specific, we fix
$\zeta_{n}=e^{-2\pi\mathrm{i}/n}$. The $n$ vector-columns $V_{\omega}$ for
$\omega=\zeta_{n}^{0},\zeta_{n}^{1},\zeta_{n}^{2},\ldots,\zeta_{n}^{n-1}$ form
a Vandermonde matrix with non-zero determinant. It follows that these $n$
vectors are linearly independent and, therefore,
$\lambda_{\zeta_{n}^{0},S},\lambda_{\zeta_{n}^{1},S},\ldots,\lambda_{\zeta_{n}^{n-1},S}$
is the full spectrum of $A$. The $i$-th eigenvalue in this sequence will be
denoted by

$\lambda_{i,S}=\sum_{j\in S}\zeta_{n}^{ij}.$ (1)

###  3.2 Discrete Fourier transform

Let $\mathbb{C}^{\mathbb{Z}_{n}}$ denote the vector space of all functions
from ${\mathbb{Z}_{n}}$ to the field of complex numbers $\mathbb{C}$ with
pointwise addition and pointwise scalar multiplication. The pointwise
multiplication on $\mathbb{C}^{\mathbb{Z}_{n}}$ will be denoted by $\circ$.
Another way to introduce a product on $\mathbb{C}^{\mathbb{Z}_{n}}$ is to
consider the convolution $\alpha*\beta$ of two functions
$\alpha,\beta:\mathbb{Z}_{n}\rightarrow\mathbb{C}$, which is defined by
$(\alpha*\beta)(x)=\sum_{y\in{\mathbb{Z}_{n}}}\alpha(x-y)\beta(y)$ for each
$x\in{\mathbb{Z}_{n}}$. Both $\circ$ and $*$ are bilinear and, therefore, both
$(\mathbb{C}^{\mathbb{Z}_{n}},\circ)$ and $(\mathbb{C}^{\mathbb{Z}_{n}},*)$
are $n$-dimensional algebras over $\mathbb{C}$. The algebra
$(\mathbb{C}^{\mathbb{Z}_{n}},*)$ can alternatively be seen as the _group
algebra_ of $\mathbb{Z}_{n}$ over $\mathbb{C}$ and, as such, it is semisimple
by Maschke’s theorem; see, e.g., [15, Section 7.1]. Like any two
$n$-dimensional commutative semisimple $\mathbb{C}$-algebras, the algebras
$(\mathbb{C}^{\mathbb{Z}_{n}},*)$ and $(\mathbb{C}^{\mathbb{Z}_{n}},\circ)$
are isomorphic (see [15, Corollary 2.4.2]). We now describe an explicit
algebra isomorphism from $(\mathbb{C}^{\mathbb{Z}_{n}},*)$ to
$(\mathbb{C}^{\mathbb{Z}_{n}},\circ)$.

For $T\subseteq{\mathbb{Z}_{n}}$, let $\chi_{T}\in\mathbb{C}^{\mathbb{Z}_{n}}$
be the characteristic function of $T$. In particular, $\chi_{\mathbb{Z}_{n}}$
is the identically one function. For $x\in{\mathbb{Z}_{n}}$, we set
$\delta_{x}=\chi_{\\{x\\}}$.

For $\alpha:\mathbb{Z}_{n}\rightarrow\mathbb{C}$, define
$\widehat{\alpha}:\mathbb{Z}_{n}\rightarrow\mathbb{C}$ by

$\widehat{\alpha}(i)=\sum_{j=0}^{n-1}\zeta_{n}^{ij}\alpha(j).$ (2)

The _discrete Fourier transform (DFT)_ is the linear operator
$\mathcal{F}:\mathbb{C}^{\mathbb{Z}_{n}}\rightarrow\mathbb{C}^{\mathbb{Z}_{n}}$
defined by $\mathcal{F}(\alpha)=\widehat{\alpha}$. In the standard basis
$\delta_{0},\delta_{1},\ldots,\delta_{n-1}$, the DFT is represented by the
matrix $F=(\zeta_{n}^{ij})_{i,j\in\mathbb{Z}_{n}}$. Since $F$ is the familiar
Vandermonde matrix with non-zero determinant, the map $F$ is a linear
isomorphism from $\mathbb{C}^{\mathbb{Z}_{n}}$ onto itself. It is well known
and easy to derive from the definitions that

$\mathcal{F}(\alpha*\beta)=\mathcal{F}(\alpha)\circ\mathcal{F}(\beta).$ (3)

###  3.3 The rank of the walk matrix

An obvious sufficient condition for a digraph $X_{0}$ to be walk-discrete is
the non-singularity of its walk matrix $W_{0}$. In the case of Cayley graphs
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$, this observation has the following
analog: The vertex-individualized graph $X_{0}$ is walk-saturated whenever its
walk matrix $W_{0}$ has maximum possible rank $\lceil(n+1)/2\rceil$. In both
cases, the condition that $W_{0}$ has maximum possible rank admits a spectral
criterion.

Recall that an $n\times n$ matrix has _simple spectrum_ if all $n$ of its
eigenvalues are pairwise distinct. In the case of an undirected graph
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$, where $S=-S$, Equality (1) implies
that $\lambda_{a,S}=\lambda_{b,S}$ for $a\neq b$ whenever $a+b=n$. If the
eigenvalues of $A$ are unequal otherwise, that is, $A$ has
$\lceil(n+1)/2\rceil$ distinct eigenvalues, then we say that $X$ has
_saturated spectrum_ (i.e., $\lambda_{i}$ has multiplicity 1 if $i=0$ or if
$n$ is even and $i=n/2$, and multiplicity 2 otherwise).

######  Lemma 3.1.

Let $X=\operatorname{Cay}(\mathbb{Z}_{n},S)$ and $W_{0}$ be the walk matrix of
$X_{0}$.

  1. 1.

$\operatorname{rk}W_{0}=n$ if and only if $X$ has simple spectrum.

  2. 2.

Let $S=-S$. Then $\operatorname{rk}W_{0}=\lceil(n+1)/2\rceil$ if and only if
$X$ has saturated spectrum.

###### Proof.

1\. A vector-column $(a_{0},a_{1},\ldots,a_{n-1})^{\top}$ will be identified
in a natural way with the function $\alpha\in\mathbb{C}^{\mathbb{Z}_{n}}$ such
that $\alpha(x)=a_{x}$ for $x\in\mathbb{Z}_{n}$. In this way, the columns of
the walk matrix $W_{0}$ correspond to the functions
$\eta_{0},\eta_{1},\ldots,\eta_{n-1}$ where $\eta_{k}(x)=w_{x,k}$. Thus, the
rank of $W_{0}$ is equal to the dimension of the linear subspace $U$ of
$\mathbb{C}^{\mathbb{Z}_{n}}$ spanned by these functions.

Note that

$\eta_{k+1}(x)=\sum_{y\in
N(x)}\eta_{k}(y)=\sum_{y\in\mathbb{Z}_{n}}\chi_{S}(y-x)\eta_{k}(y)\\\
=\sum_{y\in\mathbb{Z}_{n}}\chi_{-S}(x-y)\eta_{k}(y)=(\chi_{-S}*\eta_{k})(x).$

It follows that $\eta_{0}=\delta_{0}$, $\eta_{1}=\chi_{-S}$,
$\eta_{2}=\chi_{-S}*\chi_{-S}$ and, generally, $\eta_{k}=\chi_{-S}^{*(k)}$ is
the $(k-1)$-fold convolution of $k$ copies of the characteristic function
$\chi_{-S}$ of the set $-S$.

Let us apply the discrete Fourier transform $\mathcal{F}$. Note that
$\mathcal{F}(\delta_{0})$ is the all-ones vector. As easily seen from (1) and
(2), $\mathcal{F}(\chi_{-S})$ is the vector whose entries are the eigenvalues
$\lambda_{0,-S},\lambda_{1,-S},\ldots,\lambda_{n-1,-S}$ of
$X^{\prime}=\operatorname{Cay}(\mathbb{Z}_{n},-S)$, the transpose of the
digraph $X$ where all arcs are reversed. If $X^{\prime}$ has at least two
equal eigenvalues, then Equality (3) readily implies that, seen as vectors,
$\mathcal{F}(\eta_{0}),\mathcal{F}(\eta_{1}),\ldots,\mathcal{F}(\eta_{n-1})$
have a common pair of equal coordinates. Therefore, $\dim
U=\dim\mathcal{F}(U)\leq n-1$.

Conversely, suppose that all eigenvalues of $X^{\prime}$ are pairwise
distinct. Recall that $\mathcal{F}(U)$ contains the vectors
$\mathcal{F}(\delta_{0})=(1,1,\ldots,1)^{\top}$ and
$\mathcal{F}(\chi_{S})=(\lambda_{0,-S},\lambda_{1,-S},\ldots,\lambda_{n-1,-S})^{\top}$.
By (3), $\mathcal{F}(U)$ contains also the vectors
$\mathcal{F}(\chi_{S}^{*(k)})\allowbreak=\left((\lambda_{0,-S})^{k},(\lambda_{1,-S})^{k},\ldots,(\lambda_{n-1,-S})^{k}\right)^{\top}$
for all $k<n$. These $n$ vectors form a Vandermonde matrix, which is non-
degenerate because all $\lambda_{i,-S}$ are pairwise distinct. It follows that
$\dim U=\dim\mathcal{F}(U)=n$.

We have shown that $\operatorname{rk}W_{0}=n$ exactly when the transpose
digraph $X^{\prime}$ has simple spectrum. It remains to note that the spectra
of $X$ and $X^{\prime}$ are simultaneously simple or not. This follows from
(1) by applying the automorphism of the cyclotomic field
$\mathbb{Q}(\zeta_{n})$ from the Galois group
$\operatorname{Aut}(\mathbb{Q}(\zeta_{n})/\mathbb{Q})$ mapping $\zeta_{n}$ to
$\zeta_{n}^{-1}$ (and fixing $\mathbb{Q}$).111Recall that
$\mathbb{Q}(\zeta_{n})$ is obtained by adjoining $\zeta_{n}$ to the field of
rationals $\mathbb{Q}$. In other words, this is the smallest subfield of
$\mathbb{C}$ containing $\mathbb{Q}$ and $\zeta_{n}$.

2\. This part is proved by virtually the same argument (which is even somewhat
simpler because we do not need to consider the transpose of $X$). ∎

##  4 Proof of Theorem 1.4

We set $\zeta_{n}=e^{-2\pi\mathrm{i}/n}$. As discussed in Subsection 3.1, a
circulant $X=\operatorname{Cay}(\mathbb{Z}_{n},S)$ has eigenvalues
$\lambda_{0},\lambda_{1},\ldots,\lambda_{n-1}$ where

$\lambda_{a}=\sum_{j\in
S}\zeta_{n}^{aj}=\sum_{j=0}^{n-1}\chi_{S}(j)\zeta_{n}^{aj}.$

Let $\sigma_{j}=\chi_{S}(j)$. If $X$ is a random digraph, i.e., the connection
set $S$ is chosen uniformly at random among all subsets of
$\mathbb{Z}_{n}\setminus\\{0\\}$, then
$\sigma_{1},\sigma_{2},\ldots,\sigma_{n-1}$ is a Bernoulli process, that is,
these $n-1$ random variables are independent and identically distributed with
$\sigma_{j}$ taking each of the values 0 and 1 with probability $1/2$. If $X$
is a random graph, i.e., the connection set $S=-S$ is chosen randomly among
all inverse-closed subsets, the values
$\sigma_{1},\sigma_{2},\ldots,\sigma_{\lfloor n/2\rfloor}$ form a Bernoulli
process, and the remaining values are determined by the equality
$\sigma_{j}=\sigma_{n-j}$. For each $a=0,1,\ldots,n-1$, the eigenvalue

$\lambda_{a}=\sum_{j=1}^{n-1}\sigma_{j}\zeta_{n}^{aj}$ (4)

becomes a random variable taking its values in the cyclotomic field
$\mathbb{Q}(\zeta_{n})$.

We will use the following observation. As usually, $\phi(n)$ stands for
Euler’s totient function.

######  Lemma 4.1.

No two different subsets of
$\\{\zeta_{n}^{j}\,:\,\begin{array}[]{@{}l@{}}1\leq j\leq n/\ln
n\end{array}\\}$ have equal sums of their elements.

###### Proof.

The known lower bounds for $\phi(n)$ (see, e.g., [5]) imply that
$\phi(n)>n/\ln n$ for $n\geq 3$. The existence of such subsets would therefore
yield a non-trivial linear combinations with rational coefficient of
$1,\zeta_{n},\zeta_{n}^{2},\ldots,\zeta_{n}^{\phi(n)-1}$, contradicting the
fact that these numbers form a basis of $\mathbb{Q}(\zeta_{n})$ considered as
a vector space over $\mathbb{Q}$. ∎

Our overall strategy for proving Theorem 1.4 will be to use the union bound

$\mathsf{P}[\lambda_{a}=\lambda_{b}\text{ for some }0\leq a,b\leq
n-1]\leq\sum_{0\leq a,b\leq n-1}\mathsf{P}[\lambda_{a}=\lambda_{b}]$

and to show that the right hand side is bounded by $n^{-1/2+o(1)}$. The
summation goes through the pairs of unequal $a$ and $b$, which in the
undirected case also have to satisfy the condition $a+b\neq n$. We split the
set of all such pairs $a,b$ in three classes $P_{1},P_{2},P_{3}$ and prove
that $\sum_{(a,b)\in P_{\ell}}\mathsf{P}[\lambda_{a}-\lambda_{b}=0]$ is
sufficiently small for each $\ell=1,2,3$. To define the sets
$P_{1},P_{2},P_{3}$, let us introduce some notation.

Given an integer $a$, let

$g(a)=n/\gcd{(a,n)}\text{ and }a^{\prime}=a/\gcd{(a,n)}.$

Note that

$\zeta_{n}^{aj}=\zeta_{g(a)}^{a^{\prime}j}.$ (5)

The integers $a^{\prime}$ and $g(a)$ are coprime, and we set
$r=(a^{\prime})^{-1}\bmod{g(a)}$.

Furthermore, let $g=g(a)$ and $\xi=\zeta_{g}$. Since $\xi$ is a $g$-th
primitive root of unity, the $g-1$ numbers

$\xi=\zeta_{n}^{ar},\ \xi^{2}=\zeta_{n}^{2ar},\ \ldots\
,\xi^{g-1}=\zeta_{n}^{(g-1)ar}$ (6)

(where the equalities are due to (5)) are pairwise distinct. It is useful to
note that they appear in the right hand side of (4) for the $g-1$ indices
$j=r,2r,\ldots,(g-1)r$, which are understood modulo $n$.

Given another integer $b$, set $\eta=\zeta_{n}^{br}$ and note that the $g-1$
numbers (where $g=g(a)$ as defined above)

$\eta=\zeta_{n}^{br},\ \eta^{2}=\zeta_{n}^{2br},\ \ldots\
,\eta^{g-1}=\zeta_{n}^{(g-1)br}$ (7)

appear in the same places in the corresponding expression for $\lambda_{b}$.
Let $h=g(b)$.

Considering a pair of different $a$ and $b$, we will always assume without
loss of generality that $g\geq h$. Let $g^{\prime}=g^{\prime}(a,b)$ be the
minimum positive integer such that $\eta^{g^{\prime}}=1$. Note that
$g^{\prime}\leq h\leq g$. Thus, the number of different numbers in the
sequence (7) is equal to $g^{\prime}$ if $g^{\prime}<g$ and to $g^{\prime}-1$
if $g^{\prime}=g$.

Note that $\eta\neq\xi$. Otherwise we would have
$\zeta_{n}^{ar}=\zeta_{n}^{br}$ and $h=g$. By (5), this would imply
$\zeta_{g}^{a^{\prime}r}=\zeta_{g}^{b^{\prime}r}$ and, as a consequence,
$a^{\prime}=b^{\prime}$ and $a=b$.

Let $\varepsilon>0$ be an arbitrarily small constant. Once this parameter is
fixed, $n$ will be supposed to be sufficiently large. We divide the set of all
pairs $a,b$ into three parts $P_{1},P_{2},P_{3}$ and, correspondingly, split
our analysis into three cases. We give a detailed argument for digraphs (Part
1 of the theorem), which with minor changes works also for graphs (Part 2). We
comment on these changes in the end of the proof.

Case 1: $P_{1}=\\{(a,b)\,:\,\begin{array}[]{@{}l@{}}g\geq
n^{10\varepsilon}\text{ and }g^{\prime}\geq n^{\varepsilon}\end{array}\\}$.

Note that $\eta\neq 1$ for else $g^{\prime}=1$. For the argument $\arg(z)$ of
a complex number $z$, we suppose that $\arg(z)\in[0,2\pi)$. Note that
$\arg(\eta)>\arg(\xi)$ because $\eta\neq\xi$ and $g(b)\leq g$. We claim that
there exists $s$ such that $1\leq s\leq\ln^{10}n$ and

$\text{either }\arg(\eta^{s})<2\pi/\ln^{10}n\text{ or
}\arg(\eta^{-s})<2\pi/\ln^{10}n.$

Indeed, there exist $s_{1}$ and $s_{2}$ such that $1\leq
s_{1}<s_{2}\leq\ln^{10}n\leq g^{\prime}$ and the distance between
$\eta^{s_{2}}$ and $\eta^{s_{1}}$ in the circle
$\\{z\in\mathbb{C}\,:\,\begin{array}[]{@{}l@{}}|z|=1\end{array}\\}$ is at most
$2\pi/\ln^{10}n$ and non-zero. We can take $s=s_{2}-s_{1}$.

We now consider three subcases. If $\arg(\eta^{-s})<2\pi/\ln^{10}n$, then we
set $K=\left\\{s,2s,\ldots,\lfloor\ln^{2}n\rfloor s\right\\}$. Note that

$\left\\{\arg(\xi^{k})\right\\}_{k\in K}\subset(0,2\pi/\ln^{8}n)\text{ and
}\left\\{\arg(\eta^{k})\right\\}_{k\in K}\subset(2\pi-2\pi/\ln^{8}n,2\pi),$
(8)

which also implies

$\left\\{\xi^{k}\right\\}_{k\in K}\cap\left\\{\eta^{k}\right\\}_{k\in
K}=\emptyset.$ (9)

The second case we consider is that $\arg(\eta^{s})<2\pi/\ln^{10}n$ and
$\eta^{s}\neq\xi^{s}$. As easily seen, there exists a subset
$K\subset\\{s,2s,\ldots,\lfloor\ln^{2}n\rfloor s\\}$ of size at least
$\lfloor\ln^{2}n\rfloor/2$ such that, while

$\left\\{\arg(\xi^{k})\right\\}_{k\in K}\subset(0,2\pi/\ln^{8}n)\text{ and
}\left\\{\arg(\eta^{k})\right\\}_{k\in K}\subset(0,2\pi/\ln^{8}n),$ (10)

Equality (9) holds anyway.

We now show that in the above two cases the equality
$\lambda_{a}=\lambda_{b}$, i.e.,

$\sum_{j=1}^{n-1}\sigma_{j}\zeta_{n}^{aj}=\sum_{j=1}^{n-1}\sigma_{j}\zeta_{n}^{bj}$
(11)

has small probability. Let us expose the values of all random variables
$\sigma_{j}$ excepting $\sigma_{kr}$ with $k\in K$ (recall that the indices
are considered modulo $n$). Equality (11) can now be written as

$c_{1}+\sum_{k\in K}\sigma_{kr}\xi^{k}=c_{2}+\sum_{k\in K}\sigma_{kr}\eta^{k}$

for some constants $c_{1}$ and $c_{2}$. In other words, we estimate the
probability of the event that for a random subset $K^{\prime}\subseteq K$ the
random variable $\sum_{k\in K^{\prime}}(\xi^{k}-\eta^{k})$ is equal to a fixed
number. Consider two different subsets $K_{1},K_{2}\subseteq K$. The equality

$\sum_{k\in K_{1}}(\xi^{k}-\eta^{k})=\sum_{k\in K_{2}}(\xi^{k}-\eta^{k})$

is equivalent to

$\sum_{k\in K_{1}}\xi^{k}+\sum_{k\in K_{2}}\eta^{k}=\sum_{k\in
K_{2}}\xi^{k}+\sum_{k\in K_{1}}\eta^{k},$ (12)

which is impossible due to (9) and Lemma 4.1. Lemma 4.1 is applicable due to
(8) and (10) (in the former case, both sides of (12) have to be multiplied by
$\zeta_{n}^{t}$ for a small $t$). We conclude that $\lambda_{a}=\lambda_{b}$
with probability at most $2^{-|K|}=n^{-\Theta(\ln n)}$.

There remains the case that $\arg(\eta^{s})<2\pi/\ln^{10}n$ and
$\eta^{s}=\xi^{s}$. Consider the complex numbers $\eta^{ks+1}-\xi^{ks+1}$ for
$0\leq k\leq\ln^{2}n$. Their absolute values are equal as
$|\eta^{ks+1}-\xi^{ks+1}|=|\xi^{ks}(\eta-\xi)|=|\eta-\xi|$. Moreover, these
numbers are pairwise different and close to each other in the circle
$\\{z\in\mathbb{C}\,:\,\begin{array}[]{@{}l@{}}|z|=|\eta-\xi|\end{array}\\}$
because

$\bigl{|}\arg(\eta^{ks+1}-\xi^{ks+1})-\arg(\eta^{(k-1)s+1}-\xi^{(k-1)s+1})\bigr{|}\\\
=\bigl{|}\arg(\xi^{ks}(\eta-\xi))-\arg(\xi^{(k-1)s}(\eta-\xi))\bigr{|}=s\arg(\xi)\leq\frac{2\pi}{\ln^{10}n}.$

In order to estimate the probability of (11), let us expose all random
variables $\sigma_{j}$ excepting $\sigma_{(ks+1)r}$ with $0\leq
k\leq\ln^{2}n$. Lemma 4.1 implies that there is at most one assignment of the
unexposed variables satisfying (11). This yields the probability bound
$n^{-\Theta(\ln n)}$. We conclude that

$\sum_{(a,b)\in
P_{1}}\mathsf{P}[\lambda_{a}=\lambda_{b}]=|P_{1}|n^{-\Theta(\ln
n)}=n^{-\Theta(\ln n)}.$

Case 2:
$P_{2}=\\{(a,b)\,:\,\begin{array}[]{@{}l@{}}g<n^{10\varepsilon}\end{array}\\}$.
Let $J=\\{j<n\,:\,\begin{array}[]{@{}l@{}}\zeta_{n}^{aj}=\xi\end{array}\\}$.
Note that $|J|=\frac{n}{g}>n^{1-10\varepsilon}$. Moreover, $J$ contains a
subset $J^{\prime}\subseteq J$ of size
$|J^{\prime}|\geq|J|/h>n^{1-20\varepsilon}$ such that the numbers
$\zeta_{n}^{bj}$ for all $j\in J^{\prime}$ are equal to the same $h$-th root
of unity $\eta^{\prime}$. If $h<g$, then clearly $\xi\neq\eta^{\prime}$. If
$h=g$, then we have $\eta^{\prime}=\eta$ and, hence, $\xi\neq\eta^{\prime}$ as
well.

Let us expose all random variables $\sigma_{j}$ except those for $j\in
J^{\prime}$. Equality (11) then implies that $\sum_{j\in
J^{\prime}}\sigma_{j}=c$ for a constant $c$. The probability of the last event
is bounded by
${|J^{\prime}|\choose\lfloor|J^{\prime}|/2\rfloor}2^{-|J^{\prime}|}=O(|J^{\prime}|^{-1/2})=O(n^{-1/2+10\varepsilon})$.

We now estimate the number of pairs $(a,b)$ in $P_{2}$. Recall that
$a=\gcd{(a,n)}a^{\prime}$, where $a^{\prime}\leq
n/\gcd{(a,n)}=g<n^{10\varepsilon}$. The factor $\gcd{(a,n)}$ of $a$ can be
chosen in at most $d(n)$ ways, where $d(n)$ denotes the total number of
divisors of $n$. It is known [1, Theorem 13.12] that $d(n)=n^{O(1/\ln\ln n)}$.
Since there are less than $n^{10\varepsilon}$ possibilities to choose the
factor $a^{\prime}$, the element $a$ can be chosen in at most
$n^{11\varepsilon}$ ways, and the same holds true as well for $b$. It follows
that $|P_{2}|\leq n^{22\varepsilon}$, and we conclude that

$\sum_{(a,b)\in
P_{2}}\mathsf{P}[\lambda_{a}=\lambda_{b}]=O(|P_{2}|n^{-1/2+10\varepsilon})=O(n^{-1/2+32\varepsilon}).$

Case 3: $P_{3}=\\{(a,b)\,:\,\begin{array}[]{@{}l@{}}g\geq
n^{10\varepsilon}\text{ while }g^{\prime}<n^{\varepsilon}\end{array}\\}$. Set
$m$ to be the largest integer such for the corresponding element of the
sequence (6) we have $\arg(\xi^{m})<2\pi/\ln^{2}n$. Let
$J=\\{r,2r,\ldots,mr\\}$. Note that $|J|=m\geq n^{8\varepsilon}$. Moreover,
$J$ contains a subset $J^{\prime}\subseteq J$ of size
$|J^{\prime}|\geq|J|/g^{\prime}>n^{7\varepsilon}$ such that the numbers
$\zeta_{n}^{bj}$ for all $j\in J^{\prime}$ are equal to the same $h$-th root
of unity $\eta^{\prime}$.

Let us expose all $\sigma_{j}$ except for $j\in J^{\prime}$. By Chernoff’s
bound, we have $\frac{1}{2}|J^{\prime}|-|J^{\prime}|^{2/3}<\sum_{j\in
J^{\prime}}\sigma_{j}<\frac{1}{2}|J^{\prime}|+|J^{\prime}|^{2/3}$ with
probability no less than
$1-2\exp(-|J^{\prime}|^{1/3})>1-\exp(-n^{\varepsilon})$. Consider the event
(11) conditioned on $\sum_{j\in J^{\prime}}\sigma_{j}=m$ for a fixed integer
$m$ such that
$\frac{1}{2}|J^{\prime}|-|J^{\prime}|^{2/3}<m<\frac{1}{2}|J^{\prime}|+|J^{\prime}|^{2/3}$.
Lemma 4.1 implies that Equality (11) can be satisfied by at most one
assignment to the variables $\sigma_{j}$ for $j\in J^{\prime}$. Therefore,
(11) is fulfilled with probability at most $1/{|J^{\prime}|\choose m}$, which
does not exceed $2^{-n^{6\varepsilon}}$. This readily implies that
$\sum_{(a,b)\in
P_{3}}\mathsf{P}[\lambda_{a}=\lambda_{b}]\leq\exp(-(1+o(1))n^{\varepsilon})$.

Summing up, we see that $\sum_{0\leq a,b\leq
n-1}\mathsf{P}[\lambda_{a}=\lambda_{b}]=O(n^{-1/2+\varepsilon})$ for each
$\varepsilon>0$ and sufficiently large $n$. This proves Part 1 of Theorem 1.4.
The proof of Part 2 is virtually the same. It should only be noted that for an
unexposed random variable $\sigma_{j}$, in place of the term
$\sigma_{j}\zeta_{n}^{aj}$ we now have to deal with
$\sigma_{j}\zeta_{n}^{aj}+\sigma_{n-j}\zeta_{n}^{a(n-j)}=\sigma_{j}(\zeta_{n}^{aj}+\zeta_{n}^{-aj})$.
Lemma 4.1 is still applicable after multiplication of the whole sum by
$\zeta_{n}^{t}$ for a small $t$. In the first subcase of Case 1, there is a
possibility that $\eta^{-s}=\xi^{s}$, which is treated similarly to the third
subcase of Case 1.

######  Remark 4.2.

The probability bound in Theorem 1.4 is nearly optimal. As can be shown, a
random digraph $\operatorname{Cay}(\mathbb{Z}_{n},S)$ for $n=3p$ with $p$
prime has repeated eigenvalues with probability $\Omega(n^{-1/2})$. Also, the
spectrum of a random graph $\operatorname{Cay}(\mathbb{Z}_{n},S)$ for $n=5p$
is not saturated with the same probability bound.

##  5 Proof of Theorem 1.1

We are now prepared to prove our main result. Specifically, we prove Theorem
1.1 for each of the three concepts of a circulant:

  * •

A Cayley (di)graph $X=\operatorname{Cay}(\mathbb{Z}_{n},S)$. The uniform
probability distribution of $X$ means that the connection set $S$ is
equiprobably chosen among all subsets of $\mathbb{Z}_{n}\setminus\\{0\\}$ in
the case of digraphs and among all inverse-closed subsets in the case of
graphs.

  * •

An unlabeled circulant, i.e., an isomorphism class of Cayley (di)graphs
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$. The uniform distribution means that
each isomorphism class on $\mathbb{Z}_{n}$ is chosen equiprobably. In the
algorithmic setting, an isomorphism class is presented by its representative
(a (di)graph from the class). Alternatively, we can think of the probability
distribution on all Cayley (di)graphs $X=\operatorname{Cay}(\mathbb{Z}_{n},S)$
in which each $X$ appears with probability $1/(\ell_{n}\,s(X))$, where
$\ell_{n}$ is the total number of $n$-vertex unlabeled circulants and $s(X)$
is the number of connection sets $S$ such that
$\operatorname{Cay}(\mathbb{Z}_{n},S)\cong X$.

  * •

A labeled circulant, i.e., a (di)graph on the vertex set
$\\{0,1,\ldots,n-1\\}$ isomorphic to some
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$. The uniform distribution is
considered on all $n$-vertex (di)graphs in this class.

In each of the three cases, we use the same canonization algorithm presented
in Subsection 2.2. For digraphs, the algorithm is extremely simple: We just
individualize one vertex in an input digraph $X$ and run CR on the obtained
vertex-colored graph $X_{0}$. In this way we either get an individual label
for each vertex of $X$ or the algorithm gives up. The labeling is canonical
for all circulants $X$, and it is successfully produced whenever $X_{0}$ is
walk-discrete. For graphs, the algorithm is a little bit more complicated and
is discussed in detail in Subsection 2.2. It succeeds whenever $X_{0}$ is
walk-saturated.

In Subsection 3.3 we noted two sufficient spectral conditions: $X_{0}$ is
walk-discrete whenever $X$ has simple spectrum, and $X_{0}$ is walk-saturated
whenever $X$ has saturated spectrum. This reduces our task to estimating the
probability that the random digraph $X$ has simple spectrum and, respectively,
that the random graph $X$ has saturated spectrum. In the case of Cayley
(di)graphs, the proof is completed by applying Theorem 1.4.

It remains to show that the estimate of Theorem 1.4 stays as well true for the
uniformly distributed labeled and unlabeled circulants. To this end, we
present a general way to convert an estimate for one distribution into an
estimate for another distribution with a small overhead cost.

###  5.1 Formal framework

We introduce the following notation simultaneously for graphs and digraphs.
Let $\mathcal{C}$ be the set of all Cayley (di)graphs $X$ of cyclic groups,
that is, all $X=\operatorname{Cay}(\mathbb{Z}_{n},S)$ for any $n$ and $S$. We
say that a set $\mathcal{Q}\subseteq\mathcal{C}$ is _isomorphism-invariant
within $\mathcal{C}$_ if for every $X\in\mathcal{Q}$ and $Y\in\mathcal{C}$, we
have $Y\in\mathcal{Q}$ whenever $X\cong Y$. Considering a set
$\mathcal{Q}\subseteq\mathcal{C}$, we will always tacitly assume that
$\mathcal{Q}$ is isomorphism-invariant within $\mathcal{C}$.

In general, speaking of a (di)graph $X$, we always suppose that the vertex set
of $X$ is $\\{0,1,\ldots,n-1\\}$, where $n$ is the order of $X$. For a set of
(di)graphs $\mathcal{Q}$, by $\mathcal{Q}_{n}$ we denote the set of the
(di)graphs in $\mathcal{Q}$ that have order $n$. By
${\mathcal{Q}}^{\mathfrak{u}}$ we denote the unlabeled version of
$\mathcal{Q}$ where isomorphic graphs are not distinguished. Formally,
${\mathcal{Q}}^{\mathfrak{u}}$ is the quotient set of $\mathcal{Q}$ by the
isomorphism relation. In other words, ${\mathcal{Q}}^{\mathfrak{u}}$ consists
of all unlabeled graphs whose representatives appear in $\mathcal{Q}$.
Furthermore, ${\mathcal{Q}}^{\mathfrak{l}}$ is the closure of $\mathcal{Q}$
under isomorphism, that is, if $\mathcal{Q}$ contains a (di)graph $X$ of order
$n$, then ${\mathcal{Q}}^{\mathfrak{l}}$ contains all graphs on the vertex set
$\\{0,1,\ldots,n-1\\}$ isomorphic to $X$. We write
${\mathcal{Q}}^{\mathfrak{u}}_{n}$ and ${\mathcal{Q}}^{\mathfrak{l}}_{n}$ to
denote the restrictions of ${\mathcal{Q}}^{\mathfrak{u}}$ and
${\mathcal{Q}}^{\mathfrak{l}}$ to the (di)graphs of order $n$.

Let $a(\mathcal{Q}_{n})$ denote the minimum number of automorphisms of a
(di)graph in $\mathcal{Q}_{n}$. Note that

$|{\mathcal{Q}}^{\mathfrak{l}}_{n}|\leq|{\mathcal{Q}}^{\mathfrak{u}}_{n}|\,n!/a(\mathcal{Q}_{n}).$
(13)

The following important fact is a consequence of the main result in [26]; see
[26, Theorem 1.1] and the discussion right after its statement.

######  Proposition 5.1 (Muzychuk [26]).

For every $S\subseteq\mathbb{Z}_{n}\setminus\\{0\\}$ there are at most
$\phi(n)$ sets $S^{\prime}\subseteq\mathbb{Z}_{n}\setminus\\{0\\}$ such that
$\operatorname{Cay}(\mathbb{Z}_{n},S^{\prime})\cong\operatorname{Cay}(\mathbb{Z}_{n},S)$.

Proposition 5.1 readily implies that if $\mathcal{Q}\subseteq\mathcal{C}$,
then

$|{\mathcal{Q}}^{\mathfrak{u}}_{n}|\leq|\mathcal{Q}_{n}|\leq\phi(n)|{\mathcal{Q}}^{\mathfrak{u}}_{n}|.$
(14)

Seeing $\mathbb{Z}_{n}$ as a ring with addition and multiplication modulo $n$,
we write $\mathbb{Z}_{n}^{\times}$ to denote the multiplicative group of order
$\phi(n)$ consisting of the invertible elements of $\mathbb{Z}_{n}$. For a set
$S\subseteq\mathbb{Z}_{n}\setminus\\{0\\}$, we define the subgroup
$K(S)\leq\mathbb{Z}_{n}^{\times}$ by
$K(S)=\\{k\in\mathbb{Z}_{n}^{\times}\,:\,\begin{array}[]{@{}l@{}}kS=S\end{array}\\}$.
In the case of digraphs, we call a connection set $S$ _multiplier-free_ if
$K(S)=\\{1\\}$. In the case of graphs, an inverse-closed connection set $S=-S$
is called _multiplier-free_ if $K(S)=\\{1,-1\\}$. The set of Cayley (di)graphs
with multiplier-free connection sets is denoted by $\mathcal{A}$.

In addition to (14), Proposition 5.1 implies that if
$\mathcal{Q}\subseteq\mathcal{A}$, then

$\displaystyle|\mathcal{Q}_{n}|$ $\displaystyle=\
\phi(n)|{\mathcal{Q}}^{\mathfrak{u}}_{n}|\quad\text{for digraphs,}$ (15)
$\displaystyle\frac{\phi(n)}{2}\,|{\mathcal{Q}}^{\mathfrak{u}}_{n}|\ \leq$
$\displaystyle|\mathcal{Q}_{n}|$ $\displaystyle\leq\
\phi(n)|{\mathcal{Q}}^{\mathfrak{u}}_{n}|\quad\text{for graphs.}$ (16)

######  Lemma 5.2.

  1. 1

A random connection set $S\subseteq\mathbb{Z}_{n}\setminus\\{0\\}$ is not
multiplier-free with probability less than $n\,2^{-n/4}$.

  2. 2

A random inverse-closed connection set $S=-S$ is not multiplier-free with
probability less than $4n\,2^{-n/8}$.

###### Proof.

Define the _annihilator_ of $a\in\mathbb{Z}_{n}$ by
$\operatorname{Ann}(a)=\\{x\in\mathbb{Z}_{n}\,:\,\begin{array}[]{@{}l@{}}xa=0\end{array}\\}$.
Since $\operatorname{Ann}(a)$ is a subgroup of $\mathbb{Z}_{n}$, we have
$|\operatorname{Ann}(a)|\leq n/2$ for every $a\neq 0$.

1\. It suffices to prove that, for each $a\neq 1$ in
$\mathbb{Z}_{n}^{\times}$, the equality $aS=S$ is fulfilled with probability
at most $2^{-n/4}$. Let $\mu_{a}$ be the permutation of $\mathbb{Z}_{n}$
defined by $\mu_{a}(x)=ax$. We have $\mu_{a}(x)=x$ exactly when
$x\in\operatorname{Ann}(a-1)$. Thus, $\mu_{a}$ is the identity on
$\operatorname{Ann}(a-1)$ and a fixed-point-free permutation of the set
$\mathbb{Z}_{n}\setminus\operatorname{Ann}(a-1)$. Denote the restriction of
$\mu_{a}$ to this set by $\mu^{\prime}_{a}$. Let $c_{1},\ldots,c_{t}$ be the
cycle type of $\mu^{\prime}_{a}$. Note that
$\sum_{i=1}^{t}c_{i}=n-|\operatorname{Ann}(a-1)|\geq n/2$. Note also that
$t\leq(\sum_{i=1}^{t}c_{i})/2$ because $c_{i}\geq 2$ for all $i$. The equality
$aS=S$ is true if and only if every cycle of $\mu^{\prime}_{a}$ either is
entirely in $S$ or is disjoint from $S$. This happens with probability

$\prod_{i=1}^{t}2^{-c_{i}+1}=2^{-(\sum_{i=1}^{t}c_{i})+t}\leq
2^{-(\sum_{i=1}^{t}c_{i})/2}\leq 2^{-n/4}.$

2\. Again, it is enough to prove that, for each $a\neq\pm 1$ in
$\mathbb{Z}_{n}^{\times}$, the equality $aS=S$ is fulfilled with probability
at most $2^{-n/8+2}$. Let $Z$ be the set of all pairs $\\{x,-x\\}$ for
$x\in\mathbb{Z}_{n}$ such that $x\neq-x$. Note that
$|Z|=\lfloor(n-1)/2\rfloor$. The permutation $\mu_{a}$ naturally acts on $Z$
by $\mu_{a}(\\{x,-x\\})=\\{ax,-ax\\}$. Let us estimate the number of fixed
points. We have $\mu_{a}(\\{x,-x\\})=\\{x,-x\\}$ if and only if $ax=x$ or
$ax=-x$, which happens exactly when
$x\in\operatorname{Ann}(a-1)\cup\operatorname{Ann}(a+1)$. It is easy to show
that $|\operatorname{Ann}(a-1)\cup\operatorname{Ann}(a+1)|\leq n/2+4$. Since
$x$ belongs to $\operatorname{Ann}(a-1)\cup\operatorname{Ann}(a+1)$
simultaneously with $-x$, the number of fixed points is bounded by $n/4+2$. It
follows that at least $n/4-3$ pairs in $Z$ are non-fixed. Similarly to Part 1,
we conclude that $aS=S$ with probability at most $2^{-n/8+2}$. ∎

To conclude the notational stuff, let $\mathcal{Q}\subseteq\mathcal{C}$. We
write $\mathsf{P}[{\mathcal{Q}}^{\mathfrak{l}}_{n}]$ to denote the probability
that a random labeled circulant of order $n$, i.e., a (di)graph chosen
randomly and uniformly in ${\mathcal{C}}^{\mathfrak{l}}_{n}$, belongs to
${\mathcal{Q}}^{\mathfrak{l}}_{n}$. Thus,
$\mathsf{P}[{\mathcal{Q}}^{\mathfrak{l}}_{n}]=|{\mathcal{Q}}^{\mathfrak{l}}_{n}|/|{\mathcal{C}}^{\mathfrak{l}}_{n}|$.
Similarly,
$\mathsf{P}[{\mathcal{Q}}^{\mathfrak{u}}_{n}]=|{\mathcal{Q}}^{\mathfrak{u}}_{n}|/|{\mathcal{C}}^{\mathfrak{u}}_{n}|$
is the probability that a random unlabeled circulant of order $n$ belongs to
${\mathcal{Q}}^{\mathfrak{u}}_{n}$.

###  5.2 From Cayley (di)graphs to unlabeled circulants

######  Lemma 5.3.

If $\mathcal{R}\subseteq\mathcal{C}$, then

$\displaystyle\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}]$
$\displaystyle\leq$
$\displaystyle(1+o(1))\,\mathsf{P}[\mathcal{R}_{n}]+n^{2}\,2^{-n/4}\quad\text{for
digraphs,}$ $\displaystyle\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}]$
$\displaystyle\leq$
$\displaystyle(2+o(1))\,\mathsf{P}[\mathcal{R}_{n}]+4n^{2}\,2^{-n/8}\quad\text{for
graphs.}$

###### Proof.

We prove the inequality for graphs; the case of digraphs is similar. Applying
the inequalities (14) to $\mathcal{Q}=\mathcal{C}\setminus\mathcal{A}$ and to
$\mathcal{Q}=\mathcal{C}$, we derive from Lemma 5.2

$\mathsf{P}[{\mathcal{C}}^{\mathfrak{u}}_{n}\setminus{\mathcal{A}}^{\mathfrak{u}}_{n}]=\frac{|{\mathcal{C}}^{\mathfrak{u}}_{n}\setminus{\mathcal{A}}^{\mathfrak{u}}_{n}|}{|{\mathcal{C}}^{\mathfrak{u}}_{n}|}\leq\frac{|\mathcal{C}_{n}\setminus\mathcal{A}_{n}|}{|\mathcal{C}_{n}|/\phi(n)}=\phi(n)\,\mathsf{P}[\mathcal{C}_{n}\setminus\mathcal{A}_{n}]\leq
4n^{2}\,2^{-n/8}.$ (17)

Using this bound and applying the inequalities (16) to
$\mathcal{Q}=\mathcal{R}\cap\mathcal{A}$ and to $\mathcal{Q}=\mathcal{A}$, we
obtain

$\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}]\leq\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}\cap{\mathcal{A}}^{\mathfrak{u}}_{n}]+\mathsf{P}[{\mathcal{C}}^{\mathfrak{u}}_{n}\setminus{\mathcal{A}}^{\mathfrak{u}}_{n}]\leq\frac{\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}\cap{\mathcal{A}}^{\mathfrak{u}}_{n}]}{\mathsf{P}[{\mathcal{A}}^{\mathfrak{u}}_{n}]}+4n^{2}\,2^{-n/8}\\\
=\frac{|{\mathcal{R}}^{\mathfrak{u}}_{n}\cap{\mathcal{A}}^{\mathfrak{u}}_{n}|}{|{\mathcal{A}}^{\mathfrak{u}}_{n}|}+4n^{2}\,2^{-n/8}\leq\frac{2\,|\mathcal{R}_{n}\cap\mathcal{A}_{n}|/\phi(n)}{|\mathcal{A}_{n}|/\phi(n)}+4n^{2}\,2^{-n/8}\leq\frac{2\,|\mathcal{R}_{n}|}{|\mathcal{A}_{n}|}+4n^{2}\,2^{-n/8}\\\
=\frac{2\,\mathsf{P}[\mathcal{R}_{n}]}{\mathsf{P}[\mathcal{A}_{n}]}+4n^{2}\,2^{-n/8}=(2+o(1))\,\mathsf{P}[\mathcal{R}_{n}]+4n^{2}\,2^{-n/8}.$

For the last equality we used Lemma 5.2 once again. ∎

Let $\mathcal{R}$ be the set of all Cayley digraphs
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$ whose spectrum is _not_ simple. In
the case of graphs, we set $\mathcal{R}$ to be the set of all
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$ whose spectrum is _not_ saturated.
Lemma 5.3 implies that the bound of Theorem 1.4 holds true also for unlabeled
circulants. This completes the proof of Theorem 1.1 in the unlabeled case.

###  5.3 From unlabeled to labeled circulants

For $a\in\mathbb{Z}_{n}$, define a bijection
$\sigma_{a}:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ by $\sigma_{a}(x)=x+a$.
For every Cayley digraph $X=\operatorname{Cay}(\mathbb{Z}_{n},S)$, the map
$\sigma_{a}$ is an automorphism of $X$ for all $a$. If $X$ has no other
automorphism, that is, $\operatorname{Aut}(X)$ is as small as possible (see
[14, Section 8.1]), then we call $X$ _firm_. In other words, $X$ is firm
exactly when $\operatorname{Aut}(X)\cong\mathbb{Z}_{n}$.

Now, let $X$ be a Cayley graph. In this case there is also another
automorphism $\rho$ defined by $\rho(x)=-x$. The automorphisms $\sigma_{1}$
and $\rho$ generate a subgroup of $\operatorname{Aut}(X)$ isomorphic to the
dihedral group $D_{2n}$. If $X$ has no other automorphisms, i.e.,
$\operatorname{Aut}(X)\cong D_{2n}$, then we say that $X$ is a _firm Cayley
graph_ of $\mathbb{Z}_{n}$. Note that a firm graph is not firm as a digraph;
this should not make any confusion because we treat random graphs and random
digraphs separately (even when in parallel).

The set of firm (di)graphs is denoted by $\mathcal{F}$. The following
equalities easily follow from the definitions: If
$\mathcal{Q}\subseteq\mathcal{F}$, then

$\displaystyle|{\mathcal{Q}}^{\mathfrak{l}}_{n}|$ $\displaystyle=$
$\displaystyle(n-1)!\,|{\mathcal{Q}}^{\mathfrak{u}}_{n}|\quad\text{for
digraphs,}$ (18) $\displaystyle|{\mathcal{Q}}^{\mathfrak{l}}_{n}|$
$\displaystyle=$
$\displaystyle\frac{(n-1)!}{2}\,|{\mathcal{Q}}^{\mathfrak{u}}_{n}|\quad\text{for
graphs.}$ (19)

We will need the following estimates obtained in [7, 13].222Note that, since
$\mathcal{F}\subseteq\mathcal{A}$, in Subsection 5.2 we could use Proposition
5.4 instead of Lemma 5.2 (which, however, has an advantage of being proved by
an elementary method).

######  Proposition 5.4.

  1. 1.

$\mathsf{P}[\mathcal{C}_{n}\setminus\mathcal{F}_{n}]=O(n^{2}2^{-n/4})$ for
digraphs (Dobson, Spiga, and Verret [13, Theorem 1.6]).

  2. 2.

$\mathsf{P}[\mathcal{C}_{n}\setminus\mathcal{F}_{n}]=O(n2^{-n/8})$ for graphs
(Bhoumik, Dobson, and Morris [7, Theorem 3.2]).

Applying the inequalities (14) to
$\mathcal{Q}=\mathcal{C}\setminus\mathcal{F}$ and to
$\mathcal{Q}=\mathcal{C}$, similarly to (17) we get the relation

$\mathsf{P}[{\mathcal{C}}^{\mathfrak{u}}_{n}\setminus{\mathcal{F}}^{\mathfrak{u}}_{n}]\leq\phi(n)\,\mathsf{P}[\mathcal{C}_{n}\setminus\mathcal{F}_{n}].$

By Proposition 5.4, this implies that

$\displaystyle\mathsf{P}[{\mathcal{C}}^{\mathfrak{u}}_{n}\setminus{\mathcal{F}}^{\mathfrak{u}}_{n}]$
$\displaystyle=$ $\displaystyle O(n^{3}\,2^{-n/4})\quad\text{for digraphs,}$
(20)
$\displaystyle\mathsf{P}[{\mathcal{C}}^{\mathfrak{u}}_{n}\setminus{\mathcal{F}}^{\mathfrak{u}}_{n}]$
$\displaystyle=$ $\displaystyle O(n^{2}\,2^{-n/8})\quad\text{for graphs.}$
(21)

######  Lemma 5.5.

If $\mathcal{R}\subseteq\mathcal{C}$, then

$\displaystyle\mathsf{P}[{\mathcal{R}}^{\mathfrak{l}}_{n}]$
$\displaystyle\geq$
$\displaystyle\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}]-O(n^{3}\,2^{-n/4})\quad\text{for
digraphs,}$ $\displaystyle\mathsf{P}[{\mathcal{R}}^{\mathfrak{l}}_{n}]$
$\displaystyle\geq$
$\displaystyle\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}]-O(n^{2}\,2^{-n/8})\quad\text{for
graphs.}$

###### Proof.

We prove the inequality for graphs; the case of digraphs is similar. Applying
the inequality (13) to $Q=\mathcal{C}$ and the equality (19) to
$\mathcal{Q}=\mathcal{R}\cap\mathcal{F}$, we derive

$\mathsf{P}[{\mathcal{R}}^{\mathfrak{l}}_{n}]\geq\mathsf{P}[{\mathcal{R}}^{\mathfrak{l}}_{n}\cap{\mathcal{F}}^{\mathfrak{l}}_{n}]=\frac{|{\mathcal{R}}^{\mathfrak{l}}_{n}\cap{\mathcal{F}}^{\mathfrak{l}}_{n}|}{|{\mathcal{C}}^{\mathfrak{l}}_{n}|}\geq\frac{(n-1)!\,|{\mathcal{R}}^{\mathfrak{u}}_{n}\cap{\mathcal{F}}^{\mathfrak{u}}_{n}|/2}{(n-1)!\,|{\mathcal{C}}^{\mathfrak{u}}_{n}|/2}=\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}\cap{\mathcal{F}}^{\mathfrak{u}}_{n}].$

This implies that

$\mathsf{P}[{\mathcal{R}}^{\mathfrak{l}}_{n}]\geq\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}]-\mathsf{P}[{\mathcal{C}}^{\mathfrak{u}}_{n}\setminus{\mathcal{F}}^{\mathfrak{u}}_{n}]\geq\mathsf{P}[{\mathcal{R}}^{\mathfrak{u}}_{n}]-O(n^{2}\,2^{-n/8}).$

The last inequality follows from the bound (21). ∎

Now, let $\mathcal{R}$ be the set of all Cayley digraphs
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$ with simple spectrum. In the case of
graphs, we set $\mathcal{R}$ to be the set of all
$X=\operatorname{Cay}(\mathbb{Z}_{n},S)$ with saturated spectrum. We already
know that the bound of Theorem 1.4 holds true for unlabeled circulants. Lemma
5.5 implies that it is as well true for labeled circulants. The proof of
Theorem 1.1 is complete.

## References

  * [1] T. M. Apostol.  Introduction to analytic number theory.  New York, NY: Springer, 1998.
  * [2] L. Babai.  Isomorphism problem for a class of point-symmetric structures.  Acta Math. Acad. Sci. Hungar., 29(3-4):329–336, 1977.
  * [3] L. Babai, X. Chen, X. Sun, S. Teng, and J. Wilmes.  Faster canonical forms for strongly regular graphs.  In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS’13), pages 157–166. IEEE Computer Society, 2013.
  * [4] L. Babai, P. Erdős, and S. M. Selkow.  Random graph isomorphism.  SIAM Journal on Computing, 9(3):628–635, 1980.
  * [5] E. Bach and J. Shallit.  Algorithmic number theory, Vol. 1: Efficient algorithms.  Cambridge, MA: The MIT Press, 1996.
  * [6] C. Berkholz, P. S. Bonsma, and M. Grohe.  Tight lower and upper bounds for the complexity of canonical colour refinement.  Theory Comput. Syst., 60(4):581–614, 2017.
  * [7] S. Bhoumik, T. Dobson, and J. Morris.  On the automorphism groups of almost all circulant graphs and digraphs.  Ars Math. Contemp., 7(2):499–518, 2014.
  * [8] B. Bollobás.  Distinguishing vertices of random graphs.  Annals of Discrete Mathematics, 13:33–49, 1982.
  * [9] A. Bose and K. Saha.  Random circulant matrices.  Boca Raton, FL: CRC Press, 2019.
  * [10] J. Cai, M. Fürer, and N. Immerman.  An optimal lower bound on the number of variables for graph identifications.  Combinatorica, 12(4):389–410, 1992.
  * [11] A. Cardon and M. Crochemore.  Partitioning a graph in $O(|A|\log_{2}|V|)$.  Theor. Comput. Sci., 19:85–98, 1982.
  * [12] P. J. Davis.  Circulant matrices. New York, NY: AMS Chelsea Publishing, 2nd ed. edition, 1994.
  * [13] E. Dobson, P. Spiga, and G. Verret.  Cayley graphs on abelian groups.  Combinatorica, 36(4):371–393, 2016.
  * [14] T. Dobson, A. Malnič, and D. Marušič.  Symmetry in graphs, volume 198 of Camb. Stud. Adv. Math. Cambridge: Cambridge University Press, 2022.
  * [15] Y. A. Drozd and V. V. Kirichenko.  Finite dimensional algebras.  Springer-Verlag, Berlin, 1994.
  * [16] S. Evdokimov and I. Ponomarenko.  Circulant graphs: recognizing and isomorphism testing in polynomial time.  St. Petersbg. Math. J., 15(6):813–835, 2004.
  * [17] F. Fuhlbrück, J. Köbler, I. Ponomarenko, and O. Verbitsky.  The Weisfeiler-Leman algorithm and recognition of graph properties.  Theor. Comput. Sci., 895:96–114, 2021.
  * [18] C. Godsil.  Controllable subsets in graphs.  Ann. Comb., 16(4):733–744, 2012.
  * [19] E. M. Hagos.  Some results on graph spectra.  Linear Algebra Appl., 356(1-3):103–111, 2002.
  * [20] N. Immerman and E. Lander.  Describing graphs: A first-order approach to graph canonization.  In Complexity Theory Retrospective, pages 59–81. Springer, 1990\.
  * [21] S. Kiefer, I. Ponomarenko, and P. Schweitzer.  The Weisfeiler-Leman dimension of planar graphs is at most 3.  J. ACM, 66(6):44:1–44:31, 2019.
  * [22] L. Kucera.  Canonical labeling of regular graphs in linear average time.  In 28th Annual Symposium on Foundations of Computer Science (FOCS’87), pages 271–279, 1987.
  * [23] F. Liu and J. Siemons.  Unlocking the walk matrix of a graph.  J. Algebr. Comb., 55(3):663–690, 2022.
  * [24] B. D. McKay and A. Piperno.  Practical graph isomorphism, ii.  Journal of Symbolic Computation, 60:94–112, 2014.
  * [25] M. W. Meckes.  Some results on random circulant matrices.  In High dimensional probability. V: The Luminy volume., pages 213–223. Beachwood, OH: IMS, Institute of Mathematical Statistics, 2009.
  * [26] M. Muzychuk.  A solution of the isomorphism problem for circulant graphs.  Proc. Lond. Math. Soc. (3), 88(1):1–41, 2004.
  * [27] M. E. Muzychuk, M. H. Klin, and R. Pöschel.  The isomorphism problem for circulant graphs via Schur ring theory.  In Codes and Association Schemes, volume 56 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 241–264. DIMACS/AMS, 1999.
  * [28] S. O’Rourke and B. Touri.  On a conjecture of Godsil concerning controllable random graphs.  SIAM J. Control. Optim., 54(6):3347–3378, 2016.
  * [29] I. Ponomarenko.  On the WL-dimension of circulant graphs of prime power order.  E-print, http://arxiv.org/abs/2206.15028, 2022.
  * [30] D. L. Powers and M. M. Sulaiman.  The walk partition and colorations of a graph.  Linear Algebra Appl., 48:145–159, 1982.
  * [31] B. Weisfeiler and A. Leman.  The reduction of a graph to canonical form and the algebra which appears therein.  NTI, Ser. 2, 9:12–16, 1968.  English translation is available at https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.