15c. Circulant graphs

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

Changing topics, but still obsessed by Fourier analysis, let us discuss now, following , some sharp results in the circulant graph case. Let us start with:

Definition

Associated to any circulant graph [math]X[/math] having [math]N[/math] vertices are:

• The set [math]S\subset\mathbb Z_N[/math] given by [math]i-_Xj\iff j-i\in S[/math].
• The group [math]E\subset\mathbb Z_N^*[/math] consisting of elements [math]g[/math] such that [math]gS=S[/math].
• The number [math]k=|E|[/math], called type of [math]X[/math].

The interest in the type [math]k[/math] is that this is the good parameter measuring the complexity of the spectral theory of [math]X[/math], as we will soon see. To start with, here are a few basic examples, and properties of the type, with [math]\varphi[/math] being the Euler function:

(1) The type can be [math]2,4,6,8,\ldots[/math] This is because [math]\{\pm 1\}\subset E[/math].

(2) [math]C_N[/math] is of type [math]2[/math]. Indeed, we have [math]S=\{\pm 1\}[/math], [math]E=\{\pm 1\}[/math].

(3) [math]K_N[/math] is of type [math]\varphi(N)[/math]. Indeed, here [math]S=\emptyset[/math], [math]E=\mathbb Z_N^*[/math].

Let us first discuss the spectral theory of the circulant graphs. In what follows [math]X[/math] will be a circulant graph having [math]p[/math] vertices, with [math]p[/math] prime. We denote by [math]\xi[/math] the column vector [math](1,w,w^2,\ldots ,w^{p-1})[/math], where [math]w=e^{2\pi i/p}[/math]. With this convention, we have:

Theorem

The eigenspaces of [math]d[/math] are given by [math]V_0={\mathbb C}1[/math] and

[[math]] V_x=\bigoplus_{a\in E}{\mathbb C}\,\xi^{xa} [[/math]]

with [math]x\in \mathbb Z_p^*[/math]. Moreover, we have [math]V_x=V_y[/math] if and only if [math]xE=yE[/math].

Show Proof

Since [math]d[/math] is circulant, we have [math]d(\xi^x)=f(x)\xi^x[/math], with [math]f:{\mathbb Z}_p\to{\mathbb C}[/math] being:

[[math]] f(x)=\sum_{t\in S}w^{xt} [[/math]]

Let [math]K={\mathbb Q}(w)[/math] and let [math]H[/math] be the Galois group of the Galois extension [math]\mathbb Q \subset K[/math]. We have then a well-known group isomorphism, as follows:

[[math]] \mathbb Z_p^*\simeq H\quad,\quad x\to s_x=[w\to w^x] [[/math]]

Also, we know from a standard theorem of Dedekind that the family [math]\{s_x\mid x\in{\mathbb Z}_p^*\}[/math] is free in [math]{\rm End}_{\mathbb Q}(K)[/math]. Now for [math]x,y\in \mathbb Z_p^*[/math] consider the following operator:

[[math]] L = \sum_{t \in S} s_{xt} - \sum_{t \in S} s_{yt} \in End_{\mathbb Q}(K) [[/math]]

We have [math]L({w}) = f(x)-f(y)[/math], and since [math]L[/math] commutes with the action of [math]H[/math], we have:

[[math]] L=0 \iff L({w}) =0 \iff f(x)=f(y) [[/math]]

By linear independence of the family [math]\{s_x\mid x\in \mathbb Z_p^*\}[/math] we get:

[[math]] f(x) = f(y) \iff xS=yS \iff xE=yE [[/math]]

It follows that [math]d[/math] has precisely [math]1+(p-1)/k[/math] distinct eigenvalues, the corresponding eigenspaces being those in the statement.

■

Consider now a commutative ring [math](R,+,\cdot)[/math]. We denote by [math]R^*[/math] the group of invertibles, and we assume [math]2\in R^*[/math]. A subgroup [math]G\subset R^*[/math] is called even if [math]-1\in G[/math]. We have:

Definition

An even subgroup [math]G\subset R^*[/math] is called [math]2[/math]-maximal if, inside [math]G[/math]:

[[math]] a-b=2(c-d)\implies a=\pm b [[/math]]

We call [math]a=b,c=d[/math] trivial solutions, and [math]a=-b=c-d[/math] hexagonal solutions.

To be more precise, in what regards our terminology, consider the group [math]G\subset{\mathbb C}[/math] formed by [math]k[/math]-th roots of unity, with [math]k[/math] even. An equation of the form [math]a-b=2(c-d)[/math] with [math]a,b,c,d\in G[/math] says that the diagonals [math]a-b[/math] and [math]c-d[/math] must be parallel, and that the first one is twice as much as the second one. But this can happen only when [math]a,c,d,b[/math] are consecutive vertices of a regular hexagon, and here we have [math]a+b=0[/math].

The relation with our quantum symmetry considerations will come from:

Proposition

Assume that [math]R[/math] has the property [math]3\neq 0[/math], and consider a [math]2[/math]-maximal subgroup [math]G\subset R^*[/math]. Then, the following happen:

• [math]2,3\not\in G[/math].
• [math]a+b=2c[/math] with [math]a,b,c\in G[/math] implies [math]a=b=c[/math].
• [math]a+2b=3c[/math] with [math]a,b,c\in G[/math] implies [math]a=b=c[/math].

Show Proof

All these assertions are elementary, as follows:

(1) This follows from the following formulae, which cannot hold in [math]G[/math]:

[[math]] 4-2=2(2-1)\quad,\quad 3-(-1)=2(3-1) [[/math]]

Indeed, the first one would imply [math]4=\pm 2[/math], and the second one would imply [math]3=\pm 1[/math]. But from [math]2\in R^*[/math] and [math]3\neq 0[/math] we get [math]2,4,6\neq 0[/math], contradiction.

(2) We have [math]a-b=2(c-b)[/math]. For a trivial solution we have [math]a=b=c[/math], and for a hexagonal solution we have [math]a+b=0[/math], hence [math]c=0[/math], hence [math]0\in{G}[/math], contradiction.

(3) We have [math]a-c=2(c-b)[/math]. For a trivial solution we have [math]a=b=c[/math], and for a hexagonal solution we have [math]a+c=0[/math], hence [math]b=-2a[/math], hence [math]2\in{G}[/math], contradiction.

■

As a first result now, coming from this study, we have:

Theorem

A circulant graph [math]X[/math], on [math]p\geq 5[/math] prime vertices, such that

[[math]] E\subset {\mathbb Z}_p [[/math]]

is [math]2[/math]-maximal, has no quantum symmetry, [math]G^+(X)=G(X)[/math].

Show Proof

This comes from the above results, via a long algebraic study, as follows:

(1) We use Proposition 15.24, which ensures that [math]V_1,V_2,V_3[/math] are eigenspaces of [math]d[/math]. By [math]2[/math]-maximality of [math]E[/math], these eigenspaces are different. From the eigenspace preservation in Theorem 15.22 we get formulae of the following type, with [math]r_a,r_a',r_a''\in{\mathcal A}[/math]:

[[math]] \alpha (\xi)=\sum_{a\in E}\xi^a\otimes r_a\quad,\quad \alpha (\xi^2)=\sum_{a\in E}\xi^{2a}\otimes r_a'\quad,\quad \alpha (\xi^3)=\sum_{a\in E}\xi^{3a}\otimes r_a'' [[/math]]

(2) We take the square of the first relation, we compare with the formula of [math]\alpha(\xi^2)[/math], and we use [math]2[/math]-maximality. We obtain in this way the following formula:

[[math]] \alpha(\xi^2)=\sum_{c\in E}\xi^{2c}\otimes r_c^2 [[/math]]

(3) We multiply now this relation by the formula of [math]\alpha(\xi)[/math], we compare with the formula of [math]\alpha(\xi^3)[/math], and we use [math]2[/math]-maximality. We obtain the following formula:

[[math]] \alpha(\xi^3)=\sum_{b\in E}\xi^{3b}\otimes r_b^3 [[/math]]

(4) As a conclusion, the three formulae in the beginning are in fact as follows:

[[math]] \alpha (\xi)=\sum_{a\in E}\xi^a\otimes r_a\quad,\quad \alpha(\xi^2)=\sum_{a\in E}\xi^{2a}\otimes r_a^2\quad,\quad \alpha(\xi^3)=\sum_{a\in E}\xi^{3a}\otimes r_a^3 [[/math]]

(5) Our claim now is that for [math]a\neq b[/math], we have the following “key formula”:

[[math]] r_ar_b^3=0 [[/math]]

Indeed, in order to prove this claim, consider the following equality:

[[math]] \left(\sum_{a\in E}\xi^a\otimes r_a\right) \left(\sum_{b\in E}\xi^{2b}\otimes r_b^2\right)=\sum_{c\in E}\xi^{3c}\otimes r_c^3 [[/math]]

By eliminating all [math]a=b[/math] terms, which produce the sum on the right, we get:

[[math]] \sum\left\{r_ar_b^2\Big| a,b\in E,\,a\neq b,\,a+2b=x\right\}=0 [[/math]]

(6) We fix now elements [math]a,b\in E[/math] satisfying [math]a\neq b[/math]. We know from [math]2[/math]-maximality that the equation [math]a+2b=a'+2b'[/math] with [math]a',b'\in E[/math] has at most one non-trivial solution, namely the hexagonal one, given by [math]a'=-a[/math] and [math]b'=a+b[/math]. Now with [math]x=a+2b[/math], we get that the above equality is in fact one of the following two equalities:

[[math]] r_ar_b^2=0\quad,\quad r_ar_b^2+r_{-a}r_{a+b}^2=0 [[/math]]

(7) In the first case, we are done. In the second case, we know that [math]a_1=b[/math] and [math]b_1=a+b[/math] are distinct elements of [math]E[/math]. So, consider the following equation, over [math]E[/math]:

[[math]] a_1+2b_1=a_1'+2b_1' [[/math]]

The hexagonal solution of this equation, given by [math]a_1'=-a_1[/math] and [math]b_1'=a_1+b_1[/math], cannot appear, because [math]b_1'=a_1+b_1[/math] can be written as [math]b_1'=a+2b[/math], and by [math]2[/math]-maximality we get [math]b_1'=-a=b[/math], which contradicts [math]a+b\in E[/math]. Thus the equation [math]a_1+2b_1=a_1'+2b_1'[/math] with [math]a_1',b_1'\in E[/math] has only trivial solutions, and with [math]x=a_1+2b_1[/math] in the above, we get:

[[math]] r_{a_1}r_{b_1}^2=0 [[/math]]

Now remember that this follows by identifying coefficients in [math]\alpha(\xi)\alpha(\xi^2)=\alpha(\xi^3)[/math]. The same method applies to the formula [math]\alpha(\xi^2)\alpha(\xi)=\alpha(\xi^3)[/math], and we get as well:

[[math]] r_{b_1}^2r_{a_1}=0 [[/math]]

We have now all ingredients for finishing the proof of the key formula, as follows:

[[math]] r_ar_b^3 =r_ar_b^2r_b =-r_{-a}r_{a+b}^2r_b =-r_{-a}r_{b_1}^2r_{a_1} =0 [[/math]]

(8) We come back now to the following formula, proved for [math]s=1,2,3[/math]:

[[math]] \alpha(\xi^s)=\sum_{a\in E}\xi^{sa}\otimes r_a^s [[/math]]

By using the key formula, we get by recurrence on [math]s[/math] that this holds in general.

(9) In particular with [math]s=p-1[/math] we get the following formula:

[[math]] \alpha(\xi^{-1})=\sum_{a\in E}\xi^{-a}\otimes r_a^{p-1} [[/math]]

On the other hand, from [math]\xi^*=\xi^{-1}[/math] we get the following formula:

[[math]] \alpha(\xi^{-1})=\sum_{a\in E}\xi^{-a}\otimes r_a^* [[/math]]

But this gives [math]r_a^* = r_a^{p-1}[/math] for any [math]a[/math]. Now by using the key formula we get:

[[math]] (r_ar_b)(r_ar_b)^* =r_ar_br_b^*r_a^* =r_ar_b^pr_a^* =(r_ar_b^3)(r_b^{p-3}r_a^*) =0 [[/math]]

(10) But this gives [math]r_ar_b=0[/math]. Thus, we have the following equalities:

[[math]] r_ar_b=r_br_a=0 [[/math]]

On the other hand, [math]{\mathcal A}[/math] is generated by coefficients of [math]\alpha[/math], which are in turn powers of elements [math]r_a[/math]. It follows that [math]{\mathcal A}[/math] is commutative, and we are done.

■

Still following , we can now formulate a main result, as follows:

Theorem

A type [math]k[/math] circulant graph having [math]p \gt \gt k[/math] vertices, with [math]p[/math] prime, has no quantum symmetry.

Show Proof

This follows from Theorem 15.25 and some arithmetics, as follows:

(1) Let [math]k[/math] be an even number, and consider the group of [math]k[/math]-th roots of unity [math]G=\{1,w,\ldots,w^{k-1}\}[/math], where [math]w=e^{2\pi i/k}[/math]. By standard arithmetics, [math]G[/math] is [math]2[/math]-maximal in [math]{\mathbb C}[/math].

(2) As a continuation of this, again by some standard arithmetics, for [math]p \gt 6^{\varphi(k)}[/math], with [math]\varphi[/math] being the Euler function, any subgroup [math]E\subset{\mathbb Z}_p^*[/math] of order [math]k[/math] is [math]2[/math]-maximal.

(3) But this proves our result. Indeed, by using (2), we can apply Theorem 15.25 provided that we have [math]p \gt 6^{{\varphi(k)}}[/math], and our graph has no quantum symmetry, as desired.

■

We should mention that the above result, from , is quite old. The challenge is to go beyond this, with results for the graphs having an abelian group action, [math]A\curvearrowright X[/math].

General references

Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].