2.1 Proof overview of the main theorem: the power of walk counts

Remarkably, we show that canonization of a random circulant does not even need the full power of colour 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_{ik})_{i,k\in V}$ is defined by setting $w_{ik}$ to be the number of walks of length $k$ from the vertex $i$ to a vertex in $T$ . That is, $w_{ik}$ is the number of vertex sequences $x_0,x_1,\ldots ,x_k$ in $G$ such that $x_0=i$ , $x_k\in T$ , and the pair $(x_j,x_{j+1})$ is an edge of $G$ for every $j\lt k$ . 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 [Reference Godsil24] and by Liu and Siemons [Reference Liu and Siemons32]. Let $G_T$ be obtained from $G$ by colouring all vertices in $T$ by the same colour. 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 labelling of the vertices of $G_T$ . This purely algebraic canonization method can be superseded by the purely combinatorial method of colour refinement because if $w_{uk}\ne w_{vk}$ for some $k$ , then colour refinement assigns distinct colours to the vertices $u$ and $v$ in $G_T$ (see Section 3.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 [Reference Hagos25]. As shown by O’Rourke and Touri [Reference O’Rourke and Touri37], 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.Footnote ²

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.

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. 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 analogue of Lemma 2.1 for the undirected case.

As an immediate consequence of Lemma 2.1, the rows of the walk matrix yield a canonical labelling of a circulant digraph whenever it has a simple spectrum. With only a small amount of additional technical effort (see Lemma 3.2 in the next section), Lemma 2.2 implies that the walk matrix can also be used to canonize a circulant graph whenever it has a saturated spectrum. The following theorem therefore estimates the success probability of these canonization methods on random circulants.

Thus, Theorem1.1 for Cayley (di)graphs follows from Theorem2.3 in view of Lemma 2.1 and 2.2. Theorem2.3 $-$ and hence, as already noted, also Theorem1.1 $-$ extends to the other two models of a random circulant discussed in Section 1, namely, the random labelled and unlabelled circulants.

Theorem2.3 is our main technical contribution and may be of independent interest in the context of research on random circulant matrices [Reference Bose and Saha10, Reference Meckes34]. Moreover, this result has further noteworthy consequences for properties of random circulant graphs, which we discuss in the next subsection.

2.2 Compactness and naïve canonization

Note that two $n$ -vertex graphs $G$ and $H$ with adjacency matrices $A$ and $B$ , respectively, are isomorphic if and only if there is an $n\times n$ permutation matrix $P$ such that $AP=PB$ . This observation leads to a natural linear programming relaxation for the graph isomorphism problem. Recall that an $n\times n$ real matrix $S$ is doubly stochastic if its elements are nonnegative and all its rows and columns sum up to $1$ . A doubly stochastic matrix $S$ satisfying the equation $AS=SB$ is called a fractional isomorphism from $G$ to $H$ . In particular, if $AS=SA$ , then $S$ is a fractional automorphism of $G$ .

Tinhofer [Reference Tinhofer42] calls a graph $G$ compact if the polytope formed in $\mathbb{R}^{n^2}$ by the fractional automorphisms of $G$ is integral, that is, the extreme points of this polytope have integer coordinates. If a compact graph $G$ is isomorphic to another graph $H$ , then the polytope of fractional isomorphisms from $G$ to $H$ is also integral. On the other hand, this polytope contains no integral point at all if $G$ and $H$ are non-isomorphic. This has an algorithmic consequence. If we know that a graph $G$ is compact, then we can decide whether or not $G$ is isomorphic to any other given graph $H$ in polynomial time by using linear programming. It suffices to compute an extreme point of the polytope of fractional isomorphisms from $G$ to $H$ and check if it has integer coordinates.

While no efficient method is known in general for determining whether a graph $G$ is compact, Schreck and Tinhofer [Reference Schreck and Tinhofer41] established a sufficient condition for the compactness of circulant graphs. In our terminology, they showed that circulant graphs with saturated spectrum are compact. Consequently, Part 2 of our Theorem2.3 immediately implies the following result.

In [Reference Tinhofer43], Tinhofer presented another, fairly surprising combinatorial approach to testing whether two graphs are isomorphic provided one of them is compact. The approach can be recast as a canonization algorithm and was considered as such also by Immerman and Lander [Reference Immerman and Lander26]. Specifically, they consider the following algorithmic procedure.

NAïVE CANONIZATION

INPUT: a graph $X$ .

1. 1. Set $\widetilde X=X$ .

2. 2. Run colour refinement on $\widetilde X$ and denote the resulting coloured graph by $\widehat X$ .

3. 3. If the vertex colours in $\widehat X$ are pairwise distinct, then output this colouring as a canonical labelling of $X$ .

4. 4. Otherwise

   1. (a) choose an arbitrary vertex $v$ in the non-singleton colour class of $\widehat X$ with leastFootnote ³ colour;

   2. (b) reset $\widetilde X$ to be $\widehat X$ with the vertex $v$ individualized;

   3. (c) repeat Step 2 again.

We say that the above procedure works correctly on input $X$ if it produces a canonical labelling of $X$ irrespectively of which vertex $v$ is chosen in any execution of Step 4(a). Note that naïve canonization works correctly whenever it terminates after the first execution of Step 3, which occurs for almost all graphs $X$ by [Reference Babai, Erdős and Selkow5]. In the general case, when Step 4 is executed at least once, it is clear that a non-backtracking refinement-individualization procedure like this cannot be expected to be correct. Indeed, naïve canonization obviously fails on any regular but non-vertex-transitive graph $X$ . All the more surprising, then, is the result established in [Reference Tinhofer43] that the approach still works correctly on such a broad and naturally defined class of graphs as the class of compact graphs.

Combining this fact with Corollary 2.4, we obtain the following result.

Note that the class of graphs on which naïve canonization succeeds is strictly larger than the class of compact graphs; see [Reference Arvind, Köbler, Rattan and Verbitsky2]. This remains true also when we focus on circulant graphs. Indeed, Schreck and Tinhofer [Reference Schreck and Tinhofer41] proved that a non-empty and non-complete circulant graph with a prime number of vertices is compact if and only if it has saturated spectrum. Remarkably, Kluge [Reference Kluge29] showed that naïve canonization works correctly on every circulant graph with a prime number of vertices.

Finally, we remark that naïve canonization makes sense only if we are a priori confident in its correctness. Corollary 2.5 is quite constructive in this regard, as the sufficient condition of Schreck and Tinhofer [Reference Schreck and Tinhofer41] – having a saturated spectrum – is verifiable in polynomial time. Moreover, it can be shown by a direct argument that naïve canonization works correctly on every walk-saturated circulant graph.

2.3 Organization of the rest of the paper

The proof of our Main Theorem (Theorem1.1) spans Sections 3–6. Section 3 begins with preliminaries and then provides a detailed description of our canonical labelling algorithm for circulant graphs with saturated spectrum. Lemma 2.1 and 2.2 are proved in Section 4, as special cases of a more general result stated there as Lemma 4.1. Theorem2.3 is proved in Section 5. This establishes Theorem1.1 for Cayley (di)graphs over $\mathbb{Z}_n$ .

The proof of Theorem1.1 is completed in Section 6, which is devoted to the other two models of a random circulant. In this section, we establish two “transition” lemmas. Specifically, Lemma 6.4 allows us to extend the probability bound of Theorem2.3 from random Cayley (di)graphs to random unlabelled circulants, while Lemma 6.6 further extends this bound to random labelled circulants.

Finally, Theorem1.2 is proved in Section 7.

3.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-coloured digraph where all vertices are equally coloured with the exception of $t$ which has a special colour. 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_0x_1\ldots x_k$ such that $(x_i,x_{i+1})\in E$ for every $0\le i\lt k$ . We say that $x_0x_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\le x,k\lt n}$ by setting $w_{x,k}$ to be the number of walks of length $k$ from $x$ to $t$ . Let

\begin{equation*} W_t(x)=(w_{x,0},w_{x,1},\ldots w_{x,n-1}) \end{equation*}

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)\ne W_t(x')$ for all $x\ne x'$ . Thus, the walk matrix yields a canonical labelling for the class of walk-discrete digraphs with an individualized vertex.

As it was mentioned in Section 2, the walk matrix is efficiently computable by linear algebraic operations. For walk-discrete digraphs, the corresponding canonical labelling can also be obtained combinatorially via the colour refinement algorithm (CR), which we now describe formally.

Given a vertex-coloured digraph $G$ with initial colouring $C_0$ , CR iteratively computes new colourings

(1) \begin{equation} C_{i+1}(x)={\left ( C_i(x),\{\!\{C_i(y)\}\!\}_{y\in N(x)} \right )}, \end{equation}

where $\{\!\{\ \}\!\}$ denotes a multiset and $N(x)=\{y\; :\; (x,y)\in E\}$ is the out-neighbourhood of $x$ . For each $i$ , the colouring $C_i$ is canonical, i.e., isomorphism-invariant. Indeed, an easy induction on $i$ shows that if $\phi$ is a (colour-preserving) isomorphism from $G$ to a vertex-coloured graph $H$ , then

(2) \begin{equation} C_i(\phi (x))=C_i(x). \end{equation}

The colour classes of $C_{i+1}$ refine the colour classes of $C_i$ : if $C_i(x)\ne C_i(x')$ , then $C_{i+1}(x)\ne C_{i+1}(x')$ . The algorithm terminates after performing $n$ refinement rounds, where $n$ is the number of vertices in $G$ , and outputs the colouring $C_n$ . Note that the colour partition becomes stable by this point.

A relationship between CR and the walk counts was observed in [Reference Powers and Sulaiman39]. We use the following adaptation of this result for our purposes.

Lemma 3.1 shows that a canonical labelling of a walk-discrete digraph $G_t$ can be obtained by running CR on $G_t$ rather than by directly computing the walk matrix, and we conclude this subsection by commenting on the efficiency of CR.

The inductive definition (1) leads to an exponential increase in the size of the colour encoding. To prevent this, colours are renamed after each refinement step. In this way, we never need more than $n$ distinct colour names. To encode the colours after each refinement round, we can use, for example, the first $n$ non-negative integers in binary. This allows us, in the next subsection, to refer to the least colour having a certain property. Note that, once the renaming rule is fixed, the modified colouring remains canonical in the sense of Equality (2).

Finally, recall that CR can be implemented in time $O(n^2\log n)$ [Reference Berkholz, Bonsma and Grohe7, Reference Cardon and Crochemore12, Reference Immerman and Lander26], while preserving the canonicity of the final colouring with respect to graph isomorphism; see [Reference Berkholz, Bonsma and Grohe7].

3.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=\{0,1,\ldots ,n-1\}$ and consider the addition modulo $n$ on this set. The Cayley digraph $X=\textrm {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-neighbourhood 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=\textrm {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=\textrm {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 3.2. Let $X = {\textrm{Cay}}(\mathbb{Z}_n,S)$ , where $S=-S$ , and suppose that $X_0$ is walk-saturated. Fix $u\ne 0$ such that $u\ne n/2$ if $n$ is even. Then

\begin{equation*} (W_0(x),W_u(x))\ne (W_0(y),W_u(y)) \end{equation*}

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

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

CANONICAL LABELLING 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 colouring of the vertex set.

3. 3. Let $c$ be the least colour 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'$ be the obtained colouring.

5. 5. To each vertex $x$ , assign the label $L(x)=(C(x),C'(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 labelling $L$ or explicitly gives up (doing always the same for isomorphic inputs). The labelling $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 3.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 2.2 and Theorem2.3.

Finally, we remark that if the algorithm is run on a non-circulant input graph and outputs a vertex labelling, then this labelling 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 labellings $L_1,\ldots ,L_{2n}$ . Of all these candidate labellings, 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.

4.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

\begin{equation*} {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 , \end{equation*}

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$ .

Now, let $\omega =\zeta _n$ be a primitive $n$ -th root of unity. To be specific, we fix $\zeta _n=e^{-2\pi \textrm{i}/n}$ . The $n$ column vectors $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 below denoted by

(3) \begin{equation} \lambda _{i,S}=\sum _{j\in S}\zeta _n^{ij}. \end{equation}

4.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., [Reference Drozd and Kirichenko17, 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 [Reference Drozd and Kirichenko17, 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\}}$ .

The discrete Fourier transform (DFT) is the linear operator $\mathcal{F} \, : \, \mathbb{C}^{\mathbb{Z}_n} \rightarrow \mathbb{C}^{\mathbb{Z}_n}$ mapping a function $\alpha :\mathbb{Z}_n \rightarrow \mathbb{C}$ into the function $\mathcal{F}(\alpha ):\mathbb{Z}_n \rightarrow \mathbb{C}$ defined by

(4) \begin{equation} \mathcal{F}(\alpha )(i)=\sum _{j=0}^{n-1}\zeta _n^{ij}\alpha (j). \end{equation}

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

(5) \begin{equation} \mathcal{F}(\alpha *\beta )=\mathcal{F}(\alpha )\circ \mathcal{F}(\beta ). \end{equation}

4.3 The rank of the walk matrix

We are now prepared to derive Lemma 2.1 and 2.2 from the following more general fact.

Proof. Let $X'=\textrm {Cay}(\mathbb{Z}_n,-S)$ be the transpose of the digraph $X$ , i.e., the digraph obtained from $X$ by reversing all arcs. Note that the adjacency matrices of $X$ and $X'$ are transposes of each other and therefore have the same spectrum. Denote the number of distinct eigenvalues of $X'$ , and hence also of $X$ , by $R$ .

A column vector $(a_0,a_1,\ldots ,a_{n-1})^\top$ will be naturally identified with the function $\alpha \in \mathbb{C}^{\mathbb{Z}_n}$ defined by $\alpha (x)=a_x$ for all $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. We, therefore, have to prove that $\dim U=R$ .

Note that

\begin{align*} \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). \end{align*}

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 DFT $\mathcal{F}$ . Note that $\mathcal{F}(\delta _0)$ is the all-ones vector. As easily seen from (3) and (4), $\mathcal{F}(\chi _{-S})$ is the vector whose entries are the eigenvalues $\lambda _{0,-S},\lambda _{1,-S},\ldots ,\lambda _{n-1,-S}$ of the transpose $X'=\textrm {Cay}(\mathbb{Z}_n,-S)$ . Equality (5) readily implies that the matrix formed by the column vectors $\mathcal{F}(\eta _0),\mathcal{F}(\eta _1),\ldots ,\mathcal{F}(\eta _{n-1})$ has exactly $R$ distinct rows. Consequently, $\dim U=\dim \mathcal{F}(U)\le R$ . In fact, equality holds because the aforementioned matrix contains a non-degenerate Vandermonde matrix of size $R\times R$ as a submatrix.

Lemma 2.1 and 2.2 correspond, respectively, to the special cases $\textrm {rk} W_0=n$ and $\textrm {rk} W_0=\lceil (n+1)/2\rceil$ of Lemma 4.1. If $S=-S$ , then $\textrm {rk} W_0\le \lceil (n+1)/2\rceil$ due to the symmetry of the undirected graph $X=\textrm {Cay}(\mathbb{Z}_n,S)$ . Lemma 4.1 shows that $X$ can have at most $\lceil (n+1)/2\rceil$ distinct eigenvales,Footnote ⁴ and that this maximum is attained exactly when $\textrm {rk} W_0$ attains the same maximum value $\lceil (n+1)/2\rceil$ .

6.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 (di)graphs $X=\textrm {Cay}(\mathbb{Z}_n,S)$ for any $n$ and $S$ . Recall that the notion of a Cayley (di)graph was formally defined in Section 3.2. According to this definition, two graphs $X=\textrm {Cay}(\mathbb{Z}_n,S)$ and $Y=\textrm {Cay}(\mathbb{Z}_n,T)$ in $\mathcal{C}$ are different exactly when $S\ne T$ .

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 unlabelled 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 unlabelled graphs whose representatives appear in $\mathcal{Q}$ . Furthermore, ${\mathcal{Q}}^{\mathfrak{l}}$ is defined to be 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$ .

Note that ${{\mathcal{C}}}^{\mathfrak{u}}$ is precisely the set of unlabelled circulants, and ${{\mathcal{C}}}^{\mathfrak{l}}$ is the set of labelled circulants.

For an arbitrary set of (di)graphs $\mathcal{Q}$ , let $a(\mathcal{Q}_n)$ denote the minimum number of automorphisms of a (di)graph in $\mathcal{Q}_n$ . Note that

(26) \begin{equation} |{\mathcal{Q}}^{\mathfrak{l}}_n|\le |{\mathcal{Q}}^{\mathfrak{u}}_n|\,n!/a(\mathcal{Q}_n). \end{equation}

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

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

(27) \begin{equation} |{\mathcal{Q}}^{\mathfrak{u}}_n|\le |\mathcal{Q}_n|\le \phi (n)|{\mathcal{Q}}^{\mathfrak{u}}_n|. \end{equation}

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)\le \mathbb{Z}_n^\times$ by $K(S)=\{k\in \mathbb{Z}_n^\times\; :\; {kS=S}\}$ . 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}$ .

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$ .

Proof. Assume that

(28) \begin{equation} \textrm {Cay}(\mathbb{Z}_n,S)\cong \textrm {Cay}(\mathbb{Z}_n,T). \end{equation}

Let $kS=S$ for $k\in \mathbb{Z}_n^\times$ . To obtain the lemma, it is enough to prove that $kT=T$ as well.

We use the following fact, which was conjectured by Zibin and proved by Muzychuk, Klin, and Pöschel [Reference Muzychuk, Klin and Pöschel36]. Let $d\mid n$ , i.e., $d$ is a divisor of $n$ . For $S\subseteq \mathbb{Z}_n$ , define $(S)_d=\{s\in S\; :\; {\gcd (s,n)=d}\}$ . Then, according to [Reference Muzychuk, Klin and Pöschel36, Theorem 5.1], the isomorphism (28) implies that for every $d\mid n$ there exists $m_d\in \mathbb{Z}_n^\times$ such that $(T)_d=m_d(S)_d$ .

For $k\in \mathbb{Z}_n^\times$ , let $\mu _k$ be the permutation of $\mathbb{Z}_n$ defined by $\mu _k(x)=kx$ . The equality $kS=S$ means that $S$ is a union of orbits of $\mu _k$ , that is, there is a set $H\subset \mathbb{Z}_n$ such that

\begin{equation*} S=\bigcup _{h\in H}\langle k\rangle h=\bigcup _{d\mid n}\bigcup _{h\in (H)_d}\langle k\rangle h, \end{equation*}

where $\langle k\rangle$ denotes the subgroup of $\mathbb{Z}_n^\times$ generated by $k$ . Note that $(S)_d=\bigcup _{h\in (H)_d}\langle k\rangle h$ . It follows that

\begin{equation*} T=\bigcup _{d\mid n}(T)_d=\bigcup _{d\mid n}m_d(S)_d=\bigcup _{d\mid n}\bigcup _{h\in (H)_d}\langle k\rangle (hm_d). \end{equation*}

This shows that $T$ is also a union of orbits of $\mu _k$ and, as required, $kT=T$ .

If $\mathcal{Q}\subseteq {\mathcal{A}}$ is isomorphism-invariant within $\mathcal{C}$ , then the lower bound in (27) can be improved as follows:

(29) \begin{align} |\mathcal{Q}_n|&= \phi (n)|{\mathcal{Q}}^{\mathfrak{u}}_n|\quad\ \text{for digraphs,} \end{align}

(30) \begin{align} \frac {\phi (n)}2\,|{\mathcal{Q}}^{\mathfrak{u}}_n|\ \le |\mathcal{Q}_n|&\le \ \phi (n)|{\mathcal{Q}}^{\mathfrak{u}}_n|\quad \text{for graphs.} \end{align}

Indeed, if $\textrm {Cay}(\mathbb{Z}_n,S)\in {\mathcal{A}}$ and $k,k'\in \mathbb{Z}_n^\times$ , then the isomorphic copies $\textrm {Cay}(\mathbb{Z}_n,kS)$ and $\textrm {Cay}(\mathbb{Z}_n,k'S)$ of this graph are distinct (i.e., $kS\ne k'S$ ) whenever $k'\ne k$ in the case of digraphs and $k'\ne \pm k$ in the case of graphs.

Proof. Define the annihilator of $a\in \mathbb{Z}_n$ by $\textrm {Ann}(a)=\{x\in \mathbb{Z}_n\; :\; {xa=0}\}$ . Since $\textrm {Ann}(a)$ is a subgroup of $\mathbb{Z}_n$ , we have $|\textrm {Ann}(a)|\le n/2$ for every $a\ne 0$ .

1. 1. It suffices to prove that, for each $a\ne 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 \textrm {Ann}(a-1)$ . Thus, $\mu _a$ is the identity on $\textrm {Ann}(a-1)$ and a fixed-point-free permutation of the set $\mathbb{Z}_n \! \setminus \! \textrm {Ann}(a-1)$ . Denote the restriction of $\mu _a$ to the latter set by $\mu '_a$ . Let $c_1,\ldots ,c_t$ be the cycle type of $\mu '_a$ . Note that $\sum _{i=1}^tc_i=n-|\textrm {Ann}(a-1)|\ge n/2$ . Note also that $t\le (\sum _{i=1}^tc_i)/2$ because $c_i\ge 2$ for all $i$ . The equality $aS=S$ is true if and only if every cycle of $\mu '_a$ either is entirely in $S$ or is disjoint from $S$ . This happens with probability

   \begin{equation*} \prod _{i=1}^t 2^{-c_i+1}=2^{-(\sum _{i=1}^tc_i)+t}\le 2^{-(\sum _{i=1}^tc_i)/2}\le 2^{-n/4}. \end{equation*}

2. 2. Again, it is enough to prove that, for each $a\ne \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\ne -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 under this action. We have $\mu _a(\{x,-x\})=\{x,-x\}$ if and only if $ax=x$ or $ax=-x$ , which happens exactly when $x\in \textrm {Ann}(a-1)\cup \textrm {Ann}(a+1)$ . Note that

   (31) \begin{equation} |\textrm {Ann}(a-1)\cup \textrm {Ann}(a+1)|\le \frac n2+1. \end{equation}

Indeed, let $b=\gcd (a-1,n)$ and $c=\gcd (a+1,n)$ , and note that $|\textrm {Ann}(a-1)|=b$ and $|\textrm {Ann}(a+1)|=c$ . Since the sets $\textrm {Ann}(a-1)$ and $\textrm {Ann}(a+1)$ share at least one element, namely $0$ , it is enough to prove that $b+c\le n/2+2$ . Since neither $a-1=0$ nor $a+1=0$ , neither $b$ nor $c$ exceeds $n/2$ . Hence, we are immediately done if $b\le 2$ or $c\le 2$ . Suppose, therefore, that both $b\ge 3$ and $c\ge 3$ .

Let $d=\gcd (b,c)$ . Since $d$ divides both $a-1$ and $a+1$ , we have $d\le 2$ . If $d=1$ , then $b$ and $c$ are coprime divisors of $n$ and, therefore, $b+c\le b+n/b$ . Note that $3\le b\le n/c\le n/3$ . In particular, $n\ge 9$ in this case. It follows that $b+c\le n/3+3\lt n/2+2$ .

If $d=2$ , then $b/2$ and $c/2$ are coprime divisors of $n/2$ . The similar argument yields

\begin{equation*} \frac b2 + \frac c2 \le \frac b2 + \frac {n/2}{b/2} \le \frac n3 + \frac 32 \lt \frac n2+2, \end{equation*}

completing the proof of Bound (31).

Since $x$ belongs to $\textrm {Ann}(a-1)\cup \textrm {Ann}(a+1)$ simultaneously with $-x$ , the number of fixed points under the action of $\mu _a$ on $Z$ is at most $n/4$ . It follows that at least $n/4-1$ pairs in $Z$ are non-fixed. Similarly to Part 1, we conclude that $aS=S$ with probability at most $2^{-n/8+1}$ .

To conclude the notational stuff, let $\mathcal{Q}\subseteq {\mathcal{C}}$ . Then $\mathbb{P}[ \mathcal{Q}_n ]=|\mathcal{Q}_n|/|{\mathcal{C}}_n|$ is the probability that a random Cayley (di)graph $\textrm {Cay}(\mathbb{Z}_n,S)$ , where $S$ is chosen equiprobably among all possible connection sets $S\subseteq \mathbb{Z}_n \! \setminus \! \{0\}$ , belongs to $\mathcal{Q}$ . Exactly this random Cayley (di)graph model is considered in Theorem2.3 and studied in Section 5. In what follows, we also write $\mathbb{P}_{\mathfrak{l}}[ {\mathcal{Q}}^{\mathfrak{l}}_n ]$ to denote the probability that a random labelled circulant of order $n$ , that is, a (di)graph chosen randomly and uniformly in ${{\mathcal{C}}}^{\mathfrak{l}}_n$ , belongs to ${\mathcal{Q}}^{\mathfrak{l}}_n$ . Thus, $\mathbb{P}_{\mathfrak{l}}[ {\mathcal{Q}}^{\mathfrak{l}}_n ]=|{\mathcal{Q}}^{\mathfrak{l}}_n|/|{{\mathcal{C}}}^{\mathfrak{l}}_n|$ . Similarly, $\mathbb{P}_{\mathfrak{u}}[ {\mathcal{Q}}^{\mathfrak{u}}_n ]=|{\mathcal{Q}}^{\mathfrak{u}}_n|/|{{\mathcal{C}}}^{\mathfrak{u}}_n|$ is the probability that a random unlabelled circulant of order $n$ belongs to ${\mathcal{Q}}^{\mathfrak{u}}_n$ .

6.2 From cayley (di)graphs to unlabelled circulants

Lemma 6.4. Let $\mathcal{R}\subseteq {\mathcal{C}}$ . If $\mathcal{R}$ is isomorphism-invariant within $\mathcal{C}$ , then

\begin{eqnarray*} \mathbb{P}_{\mathfrak{u}}[ {\mathcal{R}}^{\mathfrak{u}}_n ]&\le &(1+o(1))\,\mathbb{P}[ {\mathcal{R}}_n ]+n^2\,2^{-n/4}\quad \text{for digraphs,}\\[5pt] \mathbb{P}_{\mathfrak{u}}[ {\mathcal{R}}^{\mathfrak{u}}_n ]&\le &(2+o(1))\,\mathbb{P}[ {\mathcal{R}}_n ]+2n^2\,2^{-n/8}\quad \text{for graphs.} \end{eqnarray*}

Proof. We prove the inequality for graphs; the case of digraphs is similar. Note that ${{\mathcal{C}}}^{\mathfrak{u}}_n\setminus {{\mathcal{A}}}^{\mathfrak{u}}_n={({\mathcal{C}}_n \! \setminus \! {\mathcal{A}}_n)}^{\mathfrak{u}}$ due to Lemma 6.2. Applying the inequalities (27) to $\mathcal{Q}={\mathcal{C}}\setminus {\mathcal{A}}$ and to $\mathcal{Q}={\mathcal{C}}$ , we derive from Lemma 6.3

(32) \begin{equation} \mathbb{P}_{\mathfrak{u}}[ {{\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|} =\frac {|{({\mathcal{C}}_n \! \setminus \! {\mathcal{A}}_n)}^{\mathfrak{u}}|}{|{{\mathcal{C}}}^{\mathfrak{u}}_n|}\le \frac {|{\mathcal{C}}_n\setminus {\mathcal{A}}_n|}{|{\mathcal{C}}_n|/\phi (n)}=\phi (n)\,\mathbb{P}[ {\mathcal{C}}_n\setminus {\mathcal{A}}_n ]\le 2n^2\,2^{-n/8}. \end{equation}

Note that ${\mathcal{R}}^{\mathfrak{u}}_n\cap {{\mathcal{A}}}^{\mathfrak{u}}_n={(\mathcal{R}_n\cap {\mathcal{A}}_n)}^{\mathfrak{u}}$ because $\mathcal{A}$ is isomorphism-invariant within $\mathcal{C}$ by Lemma 6.2 and $\mathcal{R}$ is isomorphism-invariant within $\mathcal{C}$ by assumption. Using Bound (32) and applying the inequalities (30) to $\mathcal{Q}=\mathcal{R}\cap {\mathcal{A}}$ and to $\mathcal{Q}={\mathcal{A}}$ , we obtain

\begin{align*} \mathbb{P}_{\mathfrak{u}}[ {\mathcal{R}}^{\mathfrak{u}}_n ]\le \mathbb{P}_{\mathfrak{u}}[ {\mathcal{R}}^{\mathfrak{u}}_n\cap {{\mathcal{A}}}^{\mathfrak{u}}_n ]+\mathbb{P}_{\mathfrak{u}}[ {{\mathcal{C}}}^{\mathfrak{u}}_n\setminus {{\mathcal{A}}}^{\mathfrak{u}}_n ]\le \frac {\mathbb{P}_{\mathfrak{u}}[ {\mathcal{R}}^{\mathfrak{u}}_n\cap {{\mathcal{A}}}^{\mathfrak{u}}_n ]}{\mathbb{P}_{\mathfrak{u}}[ {{\mathcal{A}}}^{\mathfrak{u}}_n ]}+2n^2\,2^{-n/8} =\frac {|{\mathcal{R}}^{\mathfrak{u}}_n\cap {{\mathcal{A}}}^{\mathfrak{u}}_n|}{|{{\mathcal{A}}}^{\mathfrak{u}}_n|}+2n^2\,2^{-n/8}\\[5pt] =\frac {|{(\mathcal{R}_n\cap {\mathcal{A}}_n)}^{\mathfrak{u}}|}{|{{\mathcal{A}}}^{\mathfrak{u}}_n|}+2n^2\,2^{-n/8} \le \frac {2\,|\mathcal{R}_n\cap {\mathcal{A}}_n|/\phi (n)}{|{\mathcal{A}}_n|/\phi (n)}+2n^2\,2^{-n/8}\le \frac {2\,|\mathcal{R}_n|}{|{\mathcal{A}}_n|}+2n^2\,2^{-n/8}\\[5pt] =\frac {2\,\mathbb{P}[ \mathcal{R}_n ]}{\mathbb{P}[ {\mathcal{A}}_n ]}+2n^2\,2^{-n/8} =(2+o(1))\,\mathbb{P}[ \mathcal{R}_n ]+2n^2\,2^{-n/8}. \end{align*}

For the last equality we used Lemma 6.3 once again.

Let $\mathcal{R}$ be the set of all Cayley digraphs $X=\textrm {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=\textrm {Cay}(\mathbb{Z}_n,S)$ whose spectrum is not saturated. Lemma 6.4 implies that the bound of Theorem2.3 holds true also for unlabelled circulants. This completes the proof of Theorem1.1 in the unlabelled case.

6.3 From unlabelled to labelled 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=\textrm {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, $\textrm {Aut}(X)$ is as small as possible (see [Reference Dobson, Malnič and Marušič16, Section 8.1]), then we call $X$ firm. In other words, $X$ is firm exactly when $\textrm {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 $\textrm {Aut}(X)$ isomorphic to the dihedral group $D_{2n}$ . If $X$ has no other automorphisms, i.e., $\textrm {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

(33) \begin{eqnarray} |{\mathcal{Q}}^{\mathfrak{l}}_n|&=&(n-1)!\,|{\mathcal{Q}}^{\mathfrak{u}}_n|\quad \text{for digraphs,} \end{eqnarray}

(34) \begin{eqnarray} |{\mathcal{Q}}^{\mathfrak{l}}_n|&=&\frac {(n-1)!}2\,|{\mathcal{Q}}^{\mathfrak{u}}_n|\quad \text{for graphs.} \end{eqnarray}

We will need the following estimates obtained in [Reference Bhoumik, Dobson and Morris8, Reference Dobson, Spiga and Verret15].Footnote ⁵

Note that ${{\mathcal{C}}}^{\mathfrak{u}}_n\setminus {{\mathcal{F}}}^{\mathfrak{u}}_n={({\mathcal{C}}_n \! \setminus \! {\mathcal{F}}_n)}^{\mathfrak{u}}$ because $\mathcal{F}$ is obviously isomorphism-invariant within $\mathcal{C}$ . Applying the inequalities (27) to $\mathcal{Q}={\mathcal{C}}\setminus {\mathcal{F}}$ and to $\mathcal{Q}={\mathcal{C}}$ , similarly to (32) we get the relation

\begin{equation*} \mathbb{P}_{\mathfrak{u}}[ {{\mathcal{C}}}^{\mathfrak{u}}_n \! \setminus \! {{\mathcal{F}}}^{\mathfrak{u}}_n ]\le \phi (n)\,\mathbb{P}[ {\mathcal{C}}_n \! \setminus \! {\mathcal{F}}_n ]. \end{equation*}

By Proposition 6.5, this implies that

(35) \begin{eqnarray} \mathbb{P}_{\mathfrak{u}}[ {{\mathcal{C}}}^{\mathfrak{u}}_n\setminus {{\mathcal{F}}}^{\mathfrak{u}}_n ]&=&2^{-n/4+o(n)}\quad \text{for digraphs,} \end{eqnarray}

(36) \begin{eqnarray} \mathbb{P}_{\mathfrak{u}}[ {{\mathcal{C}}}^{\mathfrak{u}}_n\setminus {{\mathcal{F}}}^{\mathfrak{u}}_n ]&=&O(n^2\,2^{-n/8})\quad \text{for graphs.} \end{eqnarray}

Lemma 6.6. Let $\mathcal{S}\subseteq {\mathcal{C}}$ . If $\mathcal{S}$ is isomorphism-invariant within $\mathcal{C}$ , then

\begin{eqnarray*} \mathbb{P}_{\mathfrak{l}}[ {\mathcal{S}}^{\mathfrak{l}}_n ]&\ge &\mathbb{P}_{\mathfrak{u}}[ {\mathcal{S}}^{\mathfrak{u}}_n ]-2^{-n/4+o(n)}\quad \text{for digraphs,}\\[5pt] \mathbb{P}_{\mathfrak{l}}[ {\mathcal{S}}^{\mathfrak{l}}_n ]&\ge &\mathbb{P}_{\mathfrak{u}}[ {\mathcal{S}}^{\mathfrak{u}}_n ]-O(n^2\,2^{-n/8})\quad \text{for graphs.} \end{eqnarray*}

Proof. We prove the inequality for graphs; the case of digraphs is similar. Note that ${\mathcal{S}}^{\mathfrak{u}}_n\cap {{\mathcal{F}}}^{\mathfrak{u}}_n={(\mathcal{S}_n\cap {\mathcal{F}}_n)}^{\mathfrak{u}}$ and ${\mathcal{S}}^{\mathfrak{l}}_n\cap {{\mathcal{F}}}^{\mathfrak{l}}_n={(\mathcal{S}_n\cap {\mathcal{F}}_n)}^{\mathfrak{l}}$ because both $\mathcal{S}$ and $\mathcal{F}$ are isomorphism-invariant within $\mathcal{C}$ . Applying the inequality (26) to $Q={\mathcal{C}}$ and the equality (34) to $\mathcal{Q}=\mathcal{S}\cap {\mathcal{F}}$ , we derive

(37) \begin{align} \mathbb{P}_{\mathfrak{l}}[ {\mathcal{S}}^{\mathfrak{l}}_n ]\ge \mathbb{P}_{\mathfrak{l}}[ {\mathcal{S}}^{\mathfrak{l}}_n\cap {{\mathcal{F}}}^{\mathfrak{l}}_n ] & = \frac {|{\mathcal{S}}^{\mathfrak{l}}_n\cap {{\mathcal{F}}}^{\mathfrak{l}}_n|}{|{{\mathcal{C}}}^{\mathfrak{l}}_n|}=\frac {|{(\mathcal{S}_n\cap {\mathcal{F}}_n)}^{\mathfrak{l}}|}{|{{\mathcal{C}}}^{\mathfrak{l}}_n|} \nonumber\\& \ge \frac {(n-1)!\,|{(\mathcal{S}_n\cap {\mathcal{F}}_n)}^{\mathfrak{u}}|/2}{(n-1)!\,|{{\mathcal{C}}}^{\mathfrak{u}}_n|/2} =\frac {|{\mathcal{S}}^{\mathfrak{u}}_n\cap {{\mathcal{F}}}^{\mathfrak{u}}_n|}{|{{\mathcal{C}}}^{\mathfrak{u}}_n|}= \mathbb{P}_{\mathfrak{u}}[ {\mathcal{S}}^{\mathfrak{u}}_n\cap {{\mathcal{F}}}^{\mathfrak{u}}_n ]. \end{align}

This implies that

\begin{equation*} \mathbb{P}_{\mathfrak{l}}[ {\mathcal{S}}^{\mathfrak{l}}_n ]\ge \mathbb{P}_{\mathfrak{u}}[ {\mathcal{S}}^{\mathfrak{u}}_n ]-\mathbb{P}_{\mathfrak{u}}[ {{\mathcal{C}}}^{\mathfrak{u}}_n\setminus {{\mathcal{F}}}^{\mathfrak{u}}_n ]\ge \mathbb{P}_{\mathfrak{u}}[ {\mathcal{S}}^{\mathfrak{u}}_n ]-O(n^2\,2^{-n/8}). \end{equation*}

The last inequality follows from the bound (36).

Now, let $\mathcal{S}$ be the set of all Cayley digraphs $X=\textrm {Cay}(\mathbb{Z}_n,S)$ with simple spectrum. In the case of graphs, we set $\mathcal{S}$ to be the set of all $X=\textrm {Cay}(\mathbb{Z}_n,S)$ with saturated spectrum. We already know that the bound of Theorem2.3 holds true for unlabelled circulants. Lemma 6.6 implies that it is as well true for labelled circulants.

Lemma 6.6 provides a rather general way of showing that if a property holds for almost all unlabelled circulants, then it also holds for almost all labelled circulants. We remark that that for the property $\mathcal{S}$ that a circulant digraph has simple spectrum (or that a circulant graph has saturated spectrum) this can be alternatively derived from Lemma 2.1, 2.2, and 3.2. Indeed, these lemmas imply that $\mathcal{S}\subseteq {\mathcal{F}}$ , which allows us to obtain the inequality $\mathbb{P}_{\mathfrak{l}}[ {\mathcal{S}}^{\mathfrak{l}}_n ]\ge \mathbb{P}_{\mathfrak{u}}[ {\mathcal{S}}^{\mathfrak{u}}_n ]$ directly from (38).

The proof of Theorem1.1 is complete.

7.1 Description of 2-WL

For notational simplicity, an ordered pair $(a,b)$ will be denoted by $ab$ . Given a loopless digraph $X=(V,E)$ as an input, $2\text{-}\textrm{WL}$ iteratively computes a sequence of colourings $c^i_X$ of the Cartesian square $V\times V$ . The initial colouring is defined by $c^0_X(uv)=(\textit{type}(uv),\textit{type}(vu))$ where $\textit{type}(uv)$ takes on one of three values according to the type of an ordered vertex pair $uv$ , namely arc if $uv\in E$ , nonarc if $uv\notin E$ and $u\ne v$ , and loop if $u=v$ . The colouring is modified iteratively as follows:

\begin{equation*} c^{i+1}_X(uv)=\{\!\{{\left ( c^{i}_X(uw), c^{i}_X(wv) \right )}\}\!\}_{w\in V}. \end{equation*}

In words, the new colour of a pair $uv$ is a “superposition” of all old colour pairs observable along the extensions of $uv$ to a triple $uwv$ . Denote the partition of $V\times V$ into the colour classes of $c^i_X$ by $\mathcal{C}^i_X$ . A simple inductive argument shows that

\begin{equation*} c^{i+1}_X(uv)\ne c^{i+1}_X(u'v')\text{ whenever }c^{i}_X(uv)\ne c^{i}_X(u'v') \end{equation*}

which means that $\mathcal{C}^{i+1}_X$ is finer than or equal to $\mathcal{C}^i_X$ . It follows that the partition stabilizes starting from some step $t=t(X)$ , that is, $\mathcal{C}^{t}_X=\mathcal{C}^{t-1}_X$ , which implies that $\mathcal{C}^i_X=\mathcal{C}^{t-1}_X$ for all $i\ge t$ . Note that $t\le |V|^2$ . As soon as the stabilization is reached, the algorithm terminates and outputs the colouring $c^t_X$ .

An easy induction on $i$ shows that, if $\phi$ is an isomorphism from $X$ to $Y$ , then

(38) \begin{equation} c^i_X(uv)=c^i_Y(\phi (u)\phi (v)). \end{equation}

Note that the length of $c^i_X$ -colours (in any natural encoding) grows exponentially with $i$ increasing. Similarly to CR, the exponential blow-up is remedied by renaming the colours after each step. Finally, note that $2\text{-}\textrm{WL}$ can be implemented in time $O(n^3\log n)$ ; see [Reference Immerman and Lander26, Reference Immerman and Sengupta27].

Let $\textrm {WL}_2(X)=\mathcal{C}^{t}_X$ denote the stabilized partition of $V^2$ . It can be noticed that $\textrm {WL}_2(X)$ forms a coherent configuration [Reference Chen and Ponomarenko13], but we will not use this fact directly. However, we will need another source of coherent configurations, which we introduce in the next subsection.

7.2 Orbitals of a permutation group

Let $G\le \textrm {Sym}(V)$ be a group of permutations of a set $V$ . A natural action of $G$ on $V^2$ is defined by $\alpha (x,y)=(\alpha (x),\alpha (y))$ for $x,y\in V$ and $\alpha \in G$ . An orbit of this action is called orbital. We denote the partition of $V^2$ into the orbitals of $G$ by $\textrm {Orb}_2(G)$ .

Equality (39) readily implies that the partition $\textrm {WL}_2(X)$ is refined by the partition $\textrm {Orb}_2(\textrm {Aut}(X))$ . Similarly to the concept of a Schurian coherent configuration [Reference Chen and Ponomarenko13], we call a digraph $X$ Schurian if $\textrm {WL}_2(X)=\textrm {Orb}_2(\textrm {Aut}(X))$ .

For each $a\in \mathbb{Z}_n$ , a digraph $X=\textrm {Cay}(\mathbb{Z}_n,S)$ has an automorphism $\sigma _a$ defined by $\sigma _a(x)=x+a$ . These automorphisms form a subgroup of $\textrm {Aut}(X)$ . If this subgroup is normal, the circulant $X$ is called normal (see [Reference Dobson, Malnič and Marušič16, Chapter 8.1], where this concept is discussed in the more general setting of Cayley graphs for any groups). Note that if $X$ is firm – according to the definition given in Section 6.3, then $X$ is normal. This is true both for digraphs and graphs (in the case of graphs, recall that every subgroup of index 2 is normal).

Extending the definition of a firm Cayley (di)graph in Section 6.3, we also call an arbitrary labelled circulant (di)graph firm if it is isomorphic to a firm Cayley (di)graph $\textrm {Cay}(\mathbb{Z}_n,S)$ or, equivalently, if $\textrm {Aut}(X)$ is as small as possible, i.e., $\textrm {Aut}(X)$ isomorphic to the cyclic group in the directed case and to the dihedral group in the undirected case.

The Schurity property of a digraph $X$ is beneficial because it enables an efficient computation of the partition $\textrm {Orb}_2(\textrm {Aut}(X))$ just by running $2\text{-}\textrm{WL}$ on $X$ . Moreover, if $X$ is a firm circulant (di)graph, then the knowledge of $\textrm {Orb}_2(\textrm {Aut}(X))$ allows us to determine the automorphism group $\textrm {Aut}(X)$ as a permutation group. We now state this fact formally in the form that will be useful in the next subsection.

Let $C_n$ denote a cyclic permutation group on the $n$ -element set $V$ that acts on $V$ transitively or, equivalently, contains a cycle of length $n$ . Assume that $n\ge 3$ and note that $C_n$ has a unique extention to a dihedral group (of permutations of $V$ ). We denote this dihedral permutation group by $D_{2n}$ . Note that all $\phi (n)$ elements of order $n$ in $C_n$ are cycles of length $n$ . The same holds true for $D_{2n}$ . Indeed, every element in $D_{2n} \! \setminus \! C_n$ has degree 2. We now observe that, given the partitions $\textrm {Orb}_2(C_n)$ and $\textrm {Orb}_2(D_{2n})$ , the elements of order $n$ in $C_n$ and $D_{2n}$ can be explicitly constructed as permutations of the set $V$ .