NITEP 141

KEK-TH-2436

Gauge Coupling Unification
in simplified Grand Gauge-Higgs Unification

Nobuhito Maru,${}^{a,\,b}$ Haruki Takahashi${}^{\,c,\,d}$ and Yoshiki
Yatagai${}^{\,a}$

a Department of Physics, Osaka Metropolitan University,
Osaka 558-8585, Japan

b Nambu Yoichiro Institute of Theoretical and Experimental Physics (NITEP),
Osaka Metropolitan University, Osaka 558-8585, Japan

c KEK Theory Center, High Energy Accelerator Research Organization (KEK),
Oho 1-1, Tsukuba, Ibaraki 305-0801, Japan

d The Graduate University for Advance Studies (SOKENDAI),
Oho 1-1, Tsukuba, Ibaraki 305-0801, Japan

Grand gauge-Higgs unification of five dimensional SU(6) gauge theory on an
orbifold $S^{1}/Z_{2}$ with localized gauge kinetic terms is discussed. The
Standard model (SM) fermions on the boundaries and some massive bulk fermions
coupling to the SM fermions on the boundary are introduced. Taking the power-
law running contributions from the bulk fields into account, perturbative
gauge coupling unification is shown to be realized at around $10^{14}$ GeV,
which is a few order smaller than the unification scale of four dimensional
grand unified theories.

##  1 Introduction

Gauge-Higgs unification (GHU) [1] is one of the physics beyond the Standard
Model (SM), which solves the hierarchy problem by identifying the SM Higgs
field with one of the extra spatial component of the higher dimensional gauge
field. In this scenario, the physical observables in Higgs sector are
calculable and predictable regardless of its non-renormalizability. For
instance, the quantum corrections to Higgs mass and Higgs potential are known
to be finite at one-loop [2] and two-loop [3] thanks to the higher dimensional
gauge symmetry.

The hierarchy problem originally exists in grand unified theory (GUT) whether
the discrepancy between the GUT scale and the weak scale are kept and stable
under quantum corrections. Therefore, the extension of GHU to grand
unification is a natural direction to explore. One of the authors discussed a
grand gauge-Higgs unification (GGHU) [4], 111For earlier attempts and related
recent works, see [5] where the five dimensional $SU(6)$ GGHU was considered
and the SM fermions were embedded into zero modes of $SU(6)$ multiplets in the
bulk. This setup was very attractive because of the minimal matter content
without massless exotic fermions absent in SM, namely an anomaly-free matter
content. However, the down-type Yukawa couplings and the charged lepton Yukawa
couplings in GHU originated from the gauge interaction cannot be allowed since
the left-handed $SU(2)_{L}$ doublets and the right-handed $SU(2)_{L}$ singlets
are embedded into different $SU(6)$ multiplets. This fact seems to be generic
in any GHU models as long as the SM fermions are embedded into the bulk
fermions. Fortunately, alternative approach to generate Yukawa coupling in a
context of GHU has been known [6, 7], in which the SM fermions are introduced
on the boundaries (i.e. fixed point in an orbifold compactification). We also
introduce massive bulk fermions, which couple to the SM fermions through the
mass terms on the boundary. Integrating out these massive bulk fermions leads
to non-local SM fermion masses, which are proportional to the bulk to boundary
couplings and exponentially sensitive to their bulk masses. Then, the SM
fermion mass hierarchy can be obtained by very mild tuning of bulk masses.

Along this line, we have improved an $SU(6)$ grand GHU model of [4] in [8],
where the SM fermion mass hierarchy except for top quark mass was obtained by
introducing them on the boundary as $SU(5)$ multiplets, the four types of
massive bulk fermions in $SU(6)$ multiplets coupling to the SM fermions.
Furthermore, we have shown that the electroweak symmetry breaking and an
observed Higgs mass can be realized by introducing additional bulk fermions
with large dimensional representation. In GHU, generation of top quark mass is
nontrivial since Yukawa coupling is originally gauge coupling and fermion mass
is at most an order of W boson mass as it stands. As another known approach
[6], introducing the localized gauge kinetic terms on the boundary is known to
have enhancement effects on fermion masses. In a paper [10], we followed this
approach in order to realize the SM fermion mass hierarchy including top
quark. Then, we have shown that the fermion mass hierarchy including top quark
mass was indeed realized by appropriately choosing the bulk mass parameters
and the size of the localized gauge kinetic terms. The correct pattern of
electroweak symmetry breaking was obtained by introducing extra bulk fermions
as in our paper [10], but their representations have become greatly
simplified.

Next central issue is the gauge coupling unification, which should be explored
in a context of GUT scenario. It is well known that the gauge coupling running
in (flat) large extra dimensions follows the power dependence on energy scale
not logarithmic one [11]. Therefore, the GUT scale is likely to be very small
comparing to the conventional 4D GUT. It is therefore very nontrivial whether
the unified $SU(6)$ gauge coupling at the GUT scale is perturbative since many
bulk fields were introduced in our models [8, 10], which might lead to Landau
pole below the GUT scale. In fact, we saw that the perturbative gauge coupling
unification cannot be realized because the number of the bulk fermions is too
much in the previous setup [10]. Therefore, we had to reduce the number of the
bulk fermions to avoid such a problem in our model discussed in our paper
[15]. It was shown that this reduction will lead to additional generation
mixings in the bulk. Moreover, since we have changed now the bulk fermions
couple to the SM fermions on the boundaries in our paper [15], reproducing the
SM fermion masses and generation mixings is nontrivial and their study should
be reanalyzed. We have shown that the SM fermion masses and mixing can be
almost reproduced by mild tuning of bulk masses and the parameters of the
localized gauge kinetic terms. Our model [15] was expected to overcome this
issue. In fact, we will see in this paper that the perturbative gauge coupling
unification can be realized in our setup [15]. The unification scale will be
found to be around $10^{14}$ GeV, which is a few order smaller than that of
four dimensional grand unified theories. Therefore, our model will be a good
starting point for constructing a realistic model of GGHU.

This paper is organized as follows. In the next section, we briefly review the
gauge, Higgs and fermion sectors of our model. In section 3, it is shown that
the perturbative gauge coupling unification can be realized in our model.
Final section is devoted to our conclusions.

##  2 Review of our model

###  2.1 Gauge and Higgs sector

In this subsection, we briefly explain gauge and Higgs sectors of $SU(6)$ GHU
model [15]. We consider a five dimensional (5D) $SU(6)$ gauge theory with an
extra space compactified on an orbifold $S^{1}/Z_{2}$ with the radius $R$. The
orbifold has two fixed points at $y=0,\pi R$ where $y$ denotes the fifth
coordinate and their $Z_{2}$ parities are given as follows.

$\displaystyle P$ $\displaystyle=$
$\displaystyle\mbox{diag}(+,+,+,+,+,-)\,\,\mbox{at}~{}y=0,$ $\displaystyle
P^{\prime}$ $\displaystyle=$
$\displaystyle\mbox{diag}(+,+,-,-,-,-)\,\,\mbox{at}~{}y=\pi R.$ (1)

The $Z_{2}$ parity for the gauge field and the scalar field originated from an
extra component of five dimensional gauge field are assigned as
$A_{\mu}(-y)=PA_{\mu}(y)P^{{\dagger}}$, $A_{y}(-y)=-PA_{y}(y)P^{{\dagger}}$,
which implies that $SU(6)$ gauge symmetry is broken to $SU(3)_{C}\times
SU(2)_{L}\times U(1)_{Y}\times U(1)_{X}$ by the combination of the symmetry
breaking pattern at each boundary,

$\displaystyle SU(6)\rightarrow SU(5)\times U(1)_{X}\hskip
45.52458pt\mbox{at}~{}y=0,$ (2) $\displaystyle SU(6)\rightarrow SU(2)\times
SU(4)\times U(1)^{\prime}~{}\mbox{at}~{}y=\pi R.$ (3)

The decomposition of the gauge field into the SM gauge group and their $\beta$
function are shown in Table 1 which we will use for an analysis of the gauge
coupling running in section 2. The hypercharge $U(1)_{Y}$ is embedded in
Georgi-Glashow $SU(5)$ GUT, where the weak mixing angle is
$\sin^{2}{\theta_{W}}=3/8$ ($\theta_{W}$ : weak mixing angle) at the
unification scale.

gauge field $SU(6)\rightarrow SU(3)_{C}\times SU(2)_{L}\times U(1)_{Y}$
---
$35^{(+,+)}=(8,1)_{0}^{(+,+)}\oplus(1,3)_{0}^{(+,+)}\oplus(1,1)_{0}^{(+,+)}\oplus(1,1)_{0}^{(+,+)}$
$\oplus(3,2)_{5/6}^{(+,-)}\oplus(3^{*},2)_{-5/6}^{(+,-)}\oplus(3,1)_{-1/3}^{(-,+)}\oplus(3^{*},1)_{1/3}^{(-,+)}\oplus(1,2)_{-1/2}^{(-,-)}\oplus(1,2)_{-1/2}^{(-,-)}$
$\beta$ function ($b_{3}$, $b_{2}$, $b_{1}$)
$(3,0,0)+(0,2,0)+(0,0,0)+(0,0,0)$
$+(1,\frac{3}{2},\frac{5}{2})+(1,\frac{3}{2},\frac{5}{2})+(\frac{1}{2},\frac{3}{2},\frac{1}{5})+(\frac{1}{2},\frac{3}{2},\frac{1}{5})+(0,\frac{1}{2},\frac{3}{10})+(0,\frac{1}{2},\frac{3}{10})$
Table 1: Gauge field and its $\beta$ function. $r_{1,2}$ in
$(r_{1},~{}r_{2})_{a}$ are $SU(3),~{}SU(2)$ representations in the SM,
respectively. $a$ is $U(1)_{Y}$ charges.

The SM $SU(2)_{L}$ Higgs doublet field is identified with a part of an extra
component of gauge field $A_{y}$ in a following,

$A_{y}=\frac{1}{\sqrt{2}}\left(\begin{array}[]{c|c|c}&&H\\\ \hline\cr&&\\\
&&\\\ \hline\cr H^{{\dagger}}&&\\\ \end{array}\right).$ (4)

We suppose that a vacuum expectation value (VEV) of the Higgs field is taken
to be in the 28-th generator of $SU(6)$, $\langle
A_{y}^{a}\rangle=\frac{2\alpha}{Rg}\delta^{a\,28}$, where $g$ is a 5D $SU(6)$
gauge coupling constant and $\alpha$ is a dimensionless constant. The VEV of
the Higgs field is given by $\langle H\rangle=\frac{\sqrt{2}\alpha}{Rg}$. In
this setup, the doublet-triplet splitting problem is solved by the orbifolding
since the $Z_{2}$ parity of the colored Higgs is $(+,-)$ and it becomes
massive [12].

After the Higgs field has the VEV, the mass eigenvalues of the 5D bulk fields
are given by $m_{n}(q\alpha)=\frac{n+\nu+q\alpha}{R}$, where $n$ is KK mode,
$\nu=0\,(1/2)$ is for a periodic (anti-periodic) boundary condition. $q$ is an
integer charge determined by the $SU(2)$ representation to which the field
coupling to Higgs field belongs. If the field with coupling to Higgs field
belongs to N+1 representation of $SU(2)_{L}$, the integer charge $q$ is equal
to $N$.

###  2.2 Localized gauge kinetic term

As mentioned in the introduction, we introduce additional localized gauge
kinetic terms at $y=0$ and $y=\pi R$ to reproduce a top quark mass. Lagrangian
for $SU(6)$ gauge field is

$\mathcal{L}_{g}=-\frac{1}{4}\mathcal{F}^{a\,MN}\mathcal{F}^{a}_{MN}-2\pi
Rc_{1}\delta(y)\frac{1}{4}\mathcal{F}^{b\,\mu\nu}\mathcal{F}^{b}_{\mu\nu}-2\pi
Rc_{2}\delta(y-\pi
R)\frac{1}{4}\mathcal{F}^{c\,\mu\nu}\mathcal{F}^{c}_{\mu\nu},$ (5)

where the first term is the bulk gauge kinetic term with 5D space-time indices
$M,N=0,1,2,3,5$. The second and the third terms are gauge kinetic terms with
4D space-time indices $\mu,\nu=0,1,2,3$ localized at fixed point. $c_{1,2}$
are dimensionless free parameters. The superscript $a,b,c$ denote the gauge
indices for $SU(6)$, $SU(5)\times U(1)$, $SU(2)\times SU(4)\times
U(1)^{\prime}$. Note that the localized gauge kinetic terms have only to be
invariant under unbroken symmetries on each fixed point.

Because of the presence of localized gauge kinetic terms, the mass spectrum of
the SM gauge field becomes very complicated. In particular, their effects for
a periodic sector and an anti-periodic sector are different, where the
(anti-)periodic sector means the fields satisfying a condition $A(y+\pi
R)=(-)A(y)$ or the fields with parity
$(P,P^{{}^{\prime}})=(+,+),(-,-)((+,-),(-,+))$. This difference originates
from the boundary conditions for wave functions with a definite charge $q$,
$f_{n}(y;q\alpha)$. In a basis where 4D gauge kinetic terms are diagonal, we
found them to be $f_{n}(y+\pi R;q\alpha)=e^{2i\pi q\alpha}f_{n}(y;q\alpha)$ in
periodic sector and $f_{n}(y+\pi
R;q\alpha)=e^{2i\pi(q\alpha+1/2)}f_{n}(y;q\alpha)$ in anti-periodic sector.
The KK mass spectrum of the SM gauge fields are obtained from the equation

$2(1-c_{1}c_{2}(\pi Rm_{n})^{2})\sin^{2}(\pi Rm_{n})+(c_{1}+c_{2})\pi
Rm_{n}\sin(2\pi Rm_{n})-2\sin^{2}(\pi(q\alpha+\nu))=0$ (6)

where $m_{n}$ is the KK mass. The mass spectrum of the gauge field are
deformed when $c=c_{1}+c_{2}\gg 1$. In the case of introducing only one
localized term $r\equiv c_{1}/(c_{1}+c_{2})=0$ or $1$, the mass spectrum tends
to be shifted as follows.

$\displaystyle\frac{n+\nu+\alpha}{R}$
$\displaystyle\rightarrow\frac{n+\nu}{R},$ (7)
$\displaystyle\frac{n+\nu}{R},\frac{n+\nu-\alpha}{R}$
$\displaystyle\rightarrow\frac{n+\nu-1/2}{R},$

where $\nu=0$ or $1/2$. Similarly, in the case of $r=c_{1}/(c_{1}+c_{2})=1/2$,
the mass spectrum tends to be shifted,

$\displaystyle\frac{n+\nu+\alpha}{R}$ $\displaystyle\rightarrow\frac{n}{R},$
(8) $\displaystyle\frac{n+\nu}{R},\frac{n+\nu-\alpha}{R}$
$\displaystyle\rightarrow\frac{n-1}{R}.$

###  2.3 Fermion sector

In the paper [10], the SM fermions were embedded into $SU(5)$ multiplets
localized at $y=0$ boundary, where three sets of decouplet, anti-quintet and
singlet $\chi_{10},\chi_{5^{*}},\chi_{1}$ were introduced. We also introduced
three types of bulk fermions $\Psi$ and $\tilde{\Psi}$ (referred as ”mirror
fermions”) with opposite $Z_{2}$ parities each other per a generation and
constant mass term such as $M\bar{\Psi}\tilde{\Psi}$ in the bulk to avoid
exotic 4D massless fermions. Without these mirror fermions and mass terms, we
necessarily have extra exotic 4D massless fermions with the SM charges after
an orbifold compactification. In this setup, we have no massless chiral
fermions the bulk and its mirror fermions. The massless fermions are only the
SM fermions and the gauge anomalies for the SM gauge groups are trivially
canceled.

Figure 1: The SM gauge coupling running in our previous model [10]. The
horizontal axis is an energy scale in GeV, and the verical axis is an inverse
of the fine structure constant of the gauge coupling. The red dashed, blue
dashed, and orange lines denote the running of $SU(3)_{C}$, $SU(2)_{L}$, and
$U(1)_{Y}$ gauge coupling constants, respectively. The compactification scale
is taken to be 10 TeV.

However, we could not obtain perturbative gauge coupling unification as shown
in Fig. 1 because the number of the bulk fermions was too much in the previous
setup as mentioned in the introduction. As can be seen from Fig. 1, all of the
gauge couplings were not only unified, but also blown up around $10^{5\sim 6}$
GeV, where the compactification scale is taken to be 10 TeV being a typical
scale to realize 125 GeV Higgs mass in GHU scenario. In order to avoid such a
problem, we have succeeded in reducing the number of the bulk fermions in this
model [15], which also reproduces the fermion masses, mixing angles and a CP
phase. From now on, fermion sector of our model will be shown briefly. 222In
[15], we have shown the mechanism generating the SM masses and the generation
mixings based on this setup.

In the setup of our model, we introduced five of bulk fermions
$\Psi_{20},\Psi_{15},\Psi_{15^{\prime}},\Psi_{6},\Psi_{6^{\prime}}$ and the
corresponding mirror fermions shown in Table 2.

bulk fermion $SU(6)\rightarrow SU(5)$ | mirror fermion
---|---
$20^{(+,+)}=10\oplus 10^{*}$ | $20^{(-,-)}$
$15^{(+,+)}=10\oplus 5$ | $15^{(-,-)}$
$15^{\prime(+,-)}=10^{\prime}\oplus 5^{\prime}$ | $15^{\prime(-,+)}$
$6^{(-,-)}=5\oplus 1$ | $6^{(+,+)}$
$6^{\prime(+,+)}=5^{\prime}\oplus 1^{\prime}$ | $6^{\prime(-,-)}$
Table 2: Representation of bulk fermions and the corresponding mirror
fermions. $R$ in $R^{(+,+)}$ means an $SU(6)$ representation of the bulk
fermion. $r_{i}$ in $r_{1}\oplus r_{2}$ are $SU(5)$ representations.

The SM quarks and leptons for the first and the second generation were
embedded into $SU(5)$ multiplets localized at $y=0$ boundary, which were two
sets of decouplet, anti-quintet and singlet
$\chi_{10},\,\chi_{5^{*}},\,\chi_{1}$. On the other hand, those for the third
generation were embedded into $SU(3)_{C}\times SU(2)_{L}\times U(1)_{Y}$
multiplets localized at $y=\pi R$ boundary.

bulk fermion $SU(5)\rightarrow SU(3)_{C}\times SU(2)_{L}\times U(1)_{Y}$ |  $\beta$ function ($\tilde{b}_{3}$, $\tilde{b}_{2}$, $\tilde{b}_{1}$)
---|---
$10=Q_{20}(3,2)_{1/6}^{(+,+)}\oplus U^{*}_{20}(3^{*},1)_{-2/3}^{(+,-)}\oplus E^{*}_{20}(1,1)_{1}^{(+,-)}$ | (1, $\frac{3}{2}$, $\frac{1}{10}$), ($\frac{1}{2}$, 0, $\frac{4}{5}$), (0, 0, $\frac{3}{5}$)
$10^{*}=Q^{*}_{20}(3^{*},2)_{-1/6}^{(-,-)}\oplus U_{20}(3,1)_{2/3}^{(-,+)}\oplus E_{20}(1,1)_{-1}^{(-,+)}$ | (1, $\frac{3}{2}$, $\frac{1}{10}$), ($\frac{1}{2}$, 0, $\frac{4}{5}$), (0, 0, $\frac{3}{5}$)

Table 3: 20 bulk fermion and their $\beta$ function. $r_{1,2}$ in
$(r_{1},~{}r_{2})_{a}$ are $SU(3),~{}SU(2)$ representations in the SM,
respectively. $a$ is $U(1)_{Y}$ charges.

bulk fermion $SU(5)\rightarrow SU(3)_{C}\times SU(2)_{L}\times U(1)_{Y}$ |  $\beta$ function ($\tilde{b}_{3}$, $\tilde{b}_{2}$, $\tilde{b}_{1}$)
---|---
$10=Q_{15}(3,2)_{1/6}^{(+,-)}\oplus U^{*}_{15}(3^{*},1)_{-2/3}^{(+,+)}\oplus E^{*}_{15}(1,1)_{1}^{(+,+)}$ | (1, $\frac{3}{2}$, $\frac{1}{10}$), ($\frac{1}{2}$, 0, $\frac{4}{5}$), (0, 0, $\frac{3}{5}$)
$5=D_{15}(3,1)_{-1/3}^{(-,+)}\oplus L^{*}_{15}(1,2)_{1/2}^{(-,-)}$ | ($\frac{1}{2}$, 0, $\frac{1}{5}$), (0, $\frac{1}{2}$, $\frac{3}{10}$)
bulk fermion $SU(5)\rightarrow SU(3)_{C}\times SU(2)_{L}\times U(1)_{Y}$ |  $\beta$ function ($\tilde{b}_{3}$, $\tilde{b}_{2}$, $\tilde{b}_{1}$)
$10^{\prime}=Q_{15^{\prime}}(3,2)_{1/6}^{(+,+)}\oplus U^{*}_{15^{\prime}}(3^{*},1)_{-2/3}^{(+,-)}\oplus E^{*}_{15^{\prime}}(1,1)_{1}^{(+,-)}$ | (1, $\frac{3}{2}$, $\frac{1}{10}$), ($\frac{1}{2}$, 0, $\frac{4}{5}$), (0, 0, $\frac{3}{5}$)
$5^{\prime}=D_{15^{\prime}}(3,1)_{-1/3}^{(-,-)}\oplus L^{*}_{15^{\prime}}(1,2)_{1/2}^{(-,+)}$ | ($\frac{1}{2}$, 0, $\frac{1}{5}$), (0, $\frac{1}{2}$, $\frac{3}{10}$)

Table 4: Upper (Lower) table shows 15 ($\textbf{15}^{\prime}$) bulk fermion
and their $\beta$ function. $r_{1,2}$ in $(r_{1},~{}r_{2})_{a}$ are
$SU(3),~{}SU(2)$ representations in the SM, respectively. $a$ is $U(1)_{Y}$
charges.

bulk fermion $SU(5)\rightarrow SU(3)_{C}\times SU(2)_{L}\times U(1)_{Y}$ |  $\beta$ function ($\tilde{b}_{3}$, $\tilde{b}_{2}$, $\tilde{b}_{1}$)
---|---
$5=D_{6}(3,1)_{-1/3}^{(-,+)}\oplus L^{*}_{6}(1,2)_{1/2}^{(-,-)}$ | ($\frac{1}{2}$, 0, $\frac{1}{5}$), (0, $\frac{1}{2}$, $\frac{3}{10}$)
$1=N^{*}_{6}(1,1)_{0}^{(+,+)}$ | (0, 0, 0)
bulk fermion $SU(5)\rightarrow SU(3)_{C}\times SU(2)_{L}\times U(1)_{Y}$ |  $\beta$ function ($\tilde{b}_{3}$, $\tilde{b}_{2}$, $\tilde{b}_{1}$)
$5^{\prime}=D_{6^{\prime}}(3,1)_{-1/3}^{(-,-)}\oplus L^{*}_{6^{\prime}}(1,2)_{1/2}^{(-,+)}$ | ($\frac{1}{2}$, 0, $\frac{1}{5}$), (0, $\frac{1}{2}$, $\frac{3}{10}$)
$1^{\prime}=N^{*}_{6^{\prime}}(1,1)_{0}^{(+,-)}$ | (0, 0, 0)

Table 5: Upper (Lower) table shows 6 ($\textbf{6}^{\prime}$) bulk fermion and
their $\beta$ function. $r_{1,2}$ in $(r_{1},~{}r_{2})_{a}$ are
$SU(3),~{}SU(2)$ representations in the SM, respectively. $a$ is $U(1)_{Y}$
charges.

The decomposition of the introduced bulk fermions in the 20,
$\textbf{15}~{}(\textbf{15}^{\prime})$, $\textbf{6}~{}(\textbf{6}^{\prime})$
representations into the SM gauge group and their $\beta$ function are
summarized in Tables 5, 5, 5, respectively.

Solving the exact KK spectrum of the bulk fermions from this Lagrangian is a
very hard task because of the complicated bulk and boundary system. We assume
in this paper that the physical mass induced for the boundary fields is much
smaller than the masses of the bulk fields [6]. This is reasonable since the
compactfication scale and the bulk mass mainly determining the KK mass
spectrum of the bulk fields is larger than the mass for the boundary fields
whose typical scale is given by the Higgs VEV. In this case, the effects of
the mixing on the spectrum for the bulk fields can be negligible and the
spectrum $m_{n}^{2}=(\frac{\lambda}{\pi R})^{2}+m_{n}(q\alpha)^{2}$ is a good
approximation [6].

##  3 Gauge coupling unification

In ordinary 4D field theories, the gauge couplings $g_{i}~{}(i=1,2,3)$ of the
Standard Model are dimensionless. They evolve as the following one-loop
renormalization group equation (RGE)

$\frac{d}{d\ln{\mu}}\alpha_{i}^{-1}(\mu)=-\frac{b_{i}}{2\pi},$ (9)

whose solution is given by

$\alpha_{i}^{-1}(\mu)=\alpha_{i}^{-1}(M_{Z})-\frac{b_{i}}{2\pi}\ln{\frac{\mu}{M_{Z}}}.$
(10)

This is the usual logarithmic running of the gauge couplings. Here
$\alpha_{i}\equiv g_{i}^{2}/4\pi$, the $b_{i}$ are the one-loop beta-function
coefficients for the Standard Model gauge group

$(b_{1},b_{2},b_{3})=(41/10,-19/6,-7)$ (11)

and we have taken the Z-mass $M_{Z}\equiv$ 91.17 GeV as an arbitrary low-
energy reference scale.

These gauge couplings also receive corrections in extra dimensions, and we can
calculate such corrections in the usual way by evaluating the same one-loop
diagrams (particularly the vacuum polarization diagram) as shown in [11]. The
full one-loop corrected gauge coupling is given as

$\alpha_{i}^{-1}(\Lambda)=\alpha_{i}^{-1}(\mu)-\frac{\tilde{b}_{i}}{4\pi}\int^{\frac{\pi}{4}\mu^{-2}}_{\frac{\pi}{4}\Lambda^{-2}}\frac{dt}{t}\mathcal{P}(t)$
(12)

where $\tilde{b}_{i}$ are new beta-function coefficients by bulk fermion
contributions. $\mu$ is a renormalization scale and $\Lambda$ is the cutoff
scale of 5D theory. $\mathcal{P}(t)$ denotes the contribution from the bulk
fields with KK mass spectrum $m_{n}$,

$\mathcal{P}(t)\equiv\sum^{\infty}_{n=-\infty}\exp{\left\\{-tm_{n}^{2}\right\\}}.$
(13)

KK mass $m_{n}^{2}$ | $\mathcal{P}(t)$
---|---
$r_{0}^{2}\delta_{n,0}/R^{2}$ | $\exp[-r_{0}^{2}t/R^{2}]$
$\\{(n+\alpha)^{2}+\lambda^{2}\\}/R^{2}$ | $\theta_{3}(i\alpha t/R^{2},\exp[-t/R^{2}])\exp[-t(\alpha^{2}+\lambda^{2})/R^{2}]$
$\\{(n+1/2+\alpha)^{2}+\lambda^{2}\\}/R^{2}$ | $\theta_{2}(i\alpha t/R^{2},\exp[-t/R^{2}])\exp[-t(\alpha^{2}+\lambda^{2})/R^{2}]$
Table 6: The results of evaluation of $\mathcal{P}(t)$ depending on the KK mass. |
---|---
|
Figure 2: The perturbative gauge coupling unification in the case of $c=80$,
$r=0$ and $R^{-1}=10$ TeV. The upper figures show the energy dependence of
gauge coupling $\alpha^{-1}$ (left) and $g$ (right). The lower figures show
the energy dependence of differences between each pair of the gauge couplings
$\alpha_{i}^{-1}-\alpha_{j}^{-1}$ (left) and $g_{i}-g_{j}$ (right).

The results are expressed by the elliptic theta functions
$\theta_{i}~{}(i=2,3)$

$\displaystyle\theta_{2}(v,q)$ $\displaystyle=$ $\displaystyle
2q^{1/4}\sum^{\infty}_{n=0}q^{n(n+1)}\cos[(2n+1)v],$ (14)
$\displaystyle\theta_{3}(v,q)$ $\displaystyle=$ $\displaystyle
1+2\sum^{\infty}_{n=0}q^{n^{2}}\cos[2nv].$ (15)

Note that the results are different depending on whether the fields are
periodic or anti-periodic as can be seen from Table 6. This means that we
should be careful for the periodicity of the fields listed in Table 1, 5, 5,
5, 6 in our analysis. The elliptic theta functions $\theta_{i}~{}(i=2,3)$ can
be approximated to

$\theta_{i}(0,\exp[-t/R^{2}])\sim R\sqrt{\frac{\pi}{t}}$ (16)

in the case of $t/R^{2}\ll 1$ which corresponds to the assumption that both
$\mu$ and $\Lambda$ are much larger than $R^{-1}$. After substituting this
approximation (16) into (12) and evaluating the integral over $t$, RGE (12)
becomes the following expression

$\alpha_{i}^{-1}(\Lambda)=\alpha_{i}^{-1}(\mu)-\frac{b_{i}-\tilde{b}_{i}^{(+)}}{4\pi}\ln\frac{\Lambda}{\mu}-\frac{\tilde{b}_{i}^{(+)}+\tilde{b}_{i}^{(-)}}{\pi}R(\Lambda-\mu).$
(17)

The third term on the right-hand side shows the power-law dependence of the
gauge coupling on the energy scale. Here $+\,(-)$ in $\tilde{b}_{i}^{(+(-))}$
shows that its contribution comes from the (anti-)periodic fields. Note that
the bulk fermion and the corresponding mirror fermion have the same $\beta$
function because they have the same periodicity. Asymptotic freedom of gauge
couplings can be confirmed by the fact that the beta function for KK mode
$\tilde{b}^{(+)}+\tilde{b}^{(-)}$ is negative. It can be calculated by using
informations in Table 1, 5, 5, 5,

$\tilde{b}_{i}^{(+)}+\tilde{b}_{i}^{(-)}=-\frac{2}{3}<0.$ (18)

Therefore, the perturbative gauge coupling unification is expected in this
model, which cannot be realized in the previous model [10] due to the large
number of the introduced bulk fermions. Fig. 2 shows energy dependences of the
gauge couplings and differences between each pair of gauge couplings at
$c=80$, $r=0$ and $R^{-1}=10$ TeV. In this case, the unification scale $M_{G}$
and unification coupling $\alpha_{G}^{-1}(g_{G})$ are identified with the
scale where $U(1)$ and $SU(2)_{L}$ couplings are unified and we obtain
$M_{G}\sim 2.1\times 10^{14}$ GeV and $\alpha_{G}^{-1}\sim 4.4\times 10^{9}$,
($g_{G}\sim 5.3\times 10^{-5}$). The difference between the unification
coupling and $SU(3)_{C}$ coupling at $M_{G}$ is
$\left|(\alpha_{G}^{-1}-\alpha_{3}^{-1})/\alpha_{G}^{-1}\right|\sim 5\times
10^{-10}$ ($\left|(g_{G}-g_{3})/g_{G}\right|\sim 2.6\times 10^{-10}$),
therefore three gauge couplings unify with an accuracy of $10^{-10}$.
Alternatively, assuming the unification of three couplings $\alpha_{G}$ at
$M_{G}$, and evolving $SU(3)$ coupling down to the weak scale by RGE,
$\alpha_{3}^{-1}(M_{z})\sim 10.7$ ($g_{3}\sim 1.08$) is found, which is larger
(smaller) than the experimental value $\alpha_{3}\sim 8.4$ ($g_{3}\sim 1.2$).
We also analyze $r=1/2$ and $r=1$ cases. In the former case, almost the same
result as $r=0$ case is obtained. In the latter case, the differences are
smaller ($\sim 10^{-11}$), unification scale is larger ($M_{G}\sim 4.1\times
10^{15}$) and $SU(3)$ coupling at the weak scale is larger ($\alpha_{3}\sim
13.2$). We analyze the coupling unification in other parameter cases,
$(c,r,R^{-1})$ = $(80,0,15\mbox{ TeV})$, $(90,0,10\mbox{ TeV})$,
$(90,0,15\mbox{ TeV})$ shown in previous paper [15] and the results are shown
in Table 7. The unification scale in our model is comparable to that of four-
dimensional GUT, since the running of coupling constant in $t/R^{2}\gg 1$
region is dominated by the contributions linearly dependent on the energy
scale as in Eq. (17) and their beta functions (Eq. 18) are common, then the
differences between each pair of the gauge couplings are dominated by the
logarithmic terms. In each case shown in Table 7, the theoretical value for
$SU(3)$ coupling with one-loop corrections at the weak scale are slightly
deviated from the experimental value. However, it is possible that we could
analyze two-loop corrections to obtain more accurate unification since the
difference between the each pair of the couplings at $M_{G}$ is extremely
small.

$c$ | $r$ | $R^{-1}$ | $M_{G}$ | $\alpha_{G}^{-1}$ | $\left|(\alpha_{G}^{-1}-\alpha_{3}^{-1})/\alpha_{G}^{-1}\right|$ | $\alpha^{-1}_{3}(M_{Z})$
---|---|---|---|---|---|---
$80$ | 0 |  $10$ TeV |  $2.1\times 10^{14}$ GeV | $4.4\times 10^{9}$ | $5.26\times 10^{-10}$ | $10.7$
$80$ | 0 |  $15$ TeV |  $2.2\times 10^{14}$ GeV | $3.2\times 10^{10}$ | $6.12\times 10^{-10}$ | $10.4$
$90$ | 0 |  $10$ TeV |  $2.1\times 10^{14}$ GeV | $4.3\times 10^{9}$ | $5.25\times 10^{-10}$ | $10.7$
$90$ | 0 |  $15$ TeV |  $2.3\times 10^{14}$ GeV | $3.2\times 10^{9}$ | $6.1\times 10^{-10}$ | $10.4$
Table 7: The results of gauge coupling unification analysis at $r=0$. The
unification scale $M_{G}$ and the unification coupling $\alpha_{G}^{-1}$ are
identified with the scale where $U(1)$ and $SU(2)_{L}$ couplings are unified.
$\left|(\alpha_{G}^{-1}-\alpha_{3}^{-1})/\alpha_{G}^{-1}\right|$ is the
difference between $\alpha_{G}^{-1}$ and $SU(3)_{C}$ coupling at $M_{G}$.
$\alpha_{3}^{-1}(M_{Z})$ is the $SU(3)$ coupling at weak scale, assuming that
three gauge couplings are unified to $\alpha_{G}^{-1}$ at $M_{G}$.

We further analyze the coupling unification in the case of larger
compactification scale, which was not analyzed in the previous paper [15].
Although this case is not realistic since the Higgs mass is likely to be
enhanced, the SM fermion masses and mixings can be reproduced in larger
compactification scale. The results are shown in Table 8. In the range of
$R^{-1}=200$ TeV $-$ $220$ TeV, $SU(3)$ coupling at the weak scale can be
within the error range of experimental value.

$c$ | $r$ | $R^{-1}$ | $M_{G}$ | $\alpha_{G}^{-1}$ | $\alpha_{3}^{-1}(M_{Z})$
---|---|---|---|---|---
$80$ | 0 |  $200$ TeV |  $3.8\times 10^{14}$ GeV | $4.1\times 10^{8}$ | $8.55$
$80$ | 0 |  $220$ TeV |  $4.0\times 10^{14}$ GeV | $3.8\times 10^{8}$ | $8.49$
Table 8: The results of gauge coupling unification analysis in the case of
large compactified scale at $r=0$. The unification scale $M_{G}$ and the
unification coupling $\alpha_{G}^{-1}$ are identified with the scale where
$U(1)$ and $SU(2)_{L}$ couplings are unified. $\alpha_{3}^{-1}(M_{Z})$ is the
$SU(3)$ coupling at the weak scale, assuming that three gauge couplings are
unified to $\alpha_{G}^{-1}$ at $M_{G}$.

##  4 Conclusions

In this paper, we have discussed $SU(6)$ GGHU with localized gauge kinetic
terms. The SM fermions are introduced on the boundaries. We also introduced
massive bulk fermions in three types of $SU(6)$ representations coupling to
the SM fermions on the boundaries. The number of them has been reduced in
order to achieve perturbative gauge coupling unification which could not be
realized in [8, 10]. It was shown in this paper that the perturbative gauge
coupling unification can be indeed realized in our model [15]. Remarkably, the
unification scale in our model was found to be $10^{14}$ GeV, which is a few
order smaller than the 4D GUT scale $10^{15-16}$ GeV. This is because the beta
functions for introduced bulk fermions are common to each gauge coupling
running and the differences between each pair of gauge couplings are dominated
by the logarithmic contributions in RGE. Our model turned out to be indeed a
good starting point for constructing a realistic model of GGHU.

There is an issue to be explored in a context of GUT scenario, namely, a
proton decay. In large extra dimension models such as GHU discussed in this
paper, $X,Y$ gauge boson masses are likely to be light comparing to the
conventional GUT scale due to the power law running of the gauge coupling.
Therefore, proton decays very rapidly and our model is immediately excluded by
the experimental constraints from the Super Kamiokande data as it stands.
Possible dangerous baryon number violating operators must be forbidden, for
instance, by some symmetry (see [14] for UED case) for the proton stability.
If $U(1)_{X}$ in our model is broken to some discrete symmetry which plays its
role, it would be very interesting. It would be also interesting to
investigate the main decay mode of the proton decay in our model and give
predictions for Hyper Kamiokande experiments.

### Acknowledgments

This work was supported by JST SPRING, Grant Number JPMJSP2139 (YY).

## References

  * [1] N.S. Manton, Nucl. Phys. B 158, 141 (1979); D.B. Fairlie, Phys. Lett. B 82, 97 (1979), J. Phys. G 5, L55 (1979); Y. Hosotani, Phys. Lett. B 126, 309 (1983), Phys. Lett. B 129, 193 (1983), Annals Phys. 190, 233 (1989).
  * [2] H. Hatanaka, T. Inami and C.S. Lim, Mod. Phys. Lett. A 13, 2601 (1998); I. Antoniadis, K. Benakli and M. Quiros, New J. Phys. 3, 20 (2001); G. von Gersdorff, N. Irges and M. Quiros, Nucl. Phys. B 635, 127 (2002); R. Contino, Y. Nomura and A. Pomarol, Nucl. Phys. B 671, 148 (2003); C.S. Lim, N. Maru and K. Hasegawa, J. Phys. Soc. Jap. 77, 074101 (2008).
  * [3] N. Maru and T. Yamashita, Nucl. Phys. B 754, 127 (2006); Y. Hosotani, N. Maru, K. Takenaga and T. Yamashita, Prog. Thoer. Phys. 118, 1053 (2007).
  * [4] C.S. Lim and N. Maru, Phys. Lett. B 653, 320 (2007).
  * [5] G. Burdman and Y. Nomura, Nucl. Phys. B 656, 3 (2003); N. Haba, Y. Hosotani, Y. Kawamura and T. Yamashita, Phys. Rev. D 70, 015010 (2004); K. Kojima, K. Takenaga and T. Yamashita, Phys. Rev. D 84, 051701 (2011); Phys. Rev. D 95, no. 1, 015021 (2017); JHEP 1706, 018 (2017); Y. Hosotani and N. Yamatsu, PTEP 2015, 111B01 (2015); A. Furui, Y. Hosotani and N. Yamatsu, PTEP 2016, no. 9, 093B01 (2016); Y. Hosotani and N. Yamatsu, PTEP 2017, no. 9, 091B01 (2017); PTEP 2018, no. 2, 023B05 (2018); S. Funatsu, H. Hatanaka, Y. Hosotani, Y. Orikawa and N. Yamatsu, Phys. Rev. D 99, no. 9, 095010 (2019), Phys. Rev. D 102, no.1, 015005 (2020); A. Angelescu, A. Bally, S. Blasi and F. Goertz, Phys. Rev. D 105, no.3, 035026 (2022).
  * [6] C.A. Scrucca, M. Serone and L. Silvestrini, Nucl. Phys. B 669, 128 (2003).
  * [7] C. Csaki, C. Grojean and H. Murayama, Phys. Rev. D 67, 085012 (2003).
  * [8] N. Maru and Y. Yatagai, PTEP 2019, no. 8, 083B03 (2019); arXiv:1903.08359 [hep-ph].
  * [9] M. Carena, T.M.P. Tait and C.E.M. Wagner, Acta Phys. Polon. B 33, 2355 (2002).
  * [10] N. Maru and Y. Yatagai, Eur. Phys. J. C, 80(10):933 (2020); arXiv:1911.03465 [hep-ph].
  * [11] K.R. Dienes, E. Dudas and T. Gherghetta, Phys. Lett. B 436, 55 (1998); Nucl. Phys. B 537, 47 (1999).
  * [12] Y. Kawamura, Prog. Theor. Phys. 105, 999 (2001).
  * [13] P.A. Zyla et al. (Particle Data Group), Prog. Theor. Exp. Phys. 2020, 083C01 (2020).
  * [14] T. Appelquist, B.A. Dobrescu, E. Ponton and H.U. Yee, Phys. Rev. Lett. 87, 181802 (2001).
  * [15] N. Maru, H. Takahashi and Y. Yatagai, arXiv:2205.05824 [hep-ph].


# Descriptive Complexity of the
Generalized Spectra of Graphs

Aida Abiad<EMAIL_ADDRESS>Department of Mathematics and Computer
Science, Eindhoven University of Technology, The NetherlandsDepartment of
Mathematics: Analysis, Logic and Discrete Mathematics, Ghent University,
Belgium Department of Mathematics and Data Science, Vrije Universiteit
Brussel, Belgium Anuj Dawar<EMAIL_ADDRESS>Department of Computer
Science and Technology, University of Cambridge, UK Octavio Zapata
<EMAIL_ADDRESS>Departamento de Matemáticas, Facultad de Ciencias,
Universidad Nacional Autónoma de México, México

###### Abstract

Two graphs are cospectral if their respective adjacency matrices have the same
multiset of eigenvalues, and generalized cospectral if they are cospectral and
so are their complements. We study generalized cospectrality in relation to
logical definability. We show that any pair of graphs that are elementary
equivalent with respect to the three-variable counting first-order logic
$C^{3}$ are generalized cospectral, and this is not the case with $C^{2}$, nor
with any number of variables if we exclude counting quantifiers. Using this
result we provide a new characterization of the well-known class of distance-
regular graphs using the logic $C^{3}$. We also show that, for controllable
graphs (it is known that almost all graphs are controllable), the elementary
equivalence in $C^{2}$ coincides with isomorphism.

##  1 Introduction

Let $\Gamma$ be a graph on $n$ vertices with adjacency matrix $A$. The
characteristic polynomial $\varPhi(\Gamma,x)$ of $\Gamma$ is the
characteristic polynomial of $A$:

$\varPhi(\Gamma,x):=\det(xI-A).$

Two graphs are cospectral if they have the same characteristic polynomial.
Since the adjacency matrices of isomorphic graphs are permutation similar, we
see that isomorphic graphs are cospectral. For any real number $y$ the
generalized characteristic polynomial $\varPhi_{y}(\Gamma,x)$ of the adjacency
matrix $A$ is defined by

$\varPhi_{y}(\Gamma,x):=\det(xI-yJ-A),$

where $J$ and $I$ denote the all-one matrix and the identity matrix,
respectively. Two graphs are generalized cospectral (sometimes also called
$\mathbb{R}$-cospectral) if they have the same polynomial $\varPhi_{y}$ for
all values of $y$, that is, if the have the same generalized spectrum. Since
$\varPhi_{y}(\Gamma,x)$ is the characteristic polynomial of $(A+yJ)$, it
follows that isomorphic graphs are generalized cospectral. Since

$\varPhi(\Gamma,x)=\varPhi_{0}(\Gamma,x)$

we see that generalized cospectral graphs are cospectral. If ${\mkern
2.0mu\overline{\mkern-2.0mu\Gamma}}$ denotes the complement of $\Gamma$, then

$\varPhi({\mkern 2.0mu\overline{\mkern-2.0mu\Gamma}},x)=(-1)^{n}\
\varPhi_{-1}(\Gamma,-x-1)$

and hence generalized cospectral graphs have cospectral complements. Johnson
and Newman [13] showed that cospectral graphs with cospectral complements are
generalized cospectral.

It is still an open question whether almost all graphs are characterized by
their generalized characteristic polynomial. More precisely, a graph $\Gamma$
is determined by its generalized spectrum if every graph which is generalized
cospectral with $\Gamma$ is isomorphic to $\Gamma$. It has been conjectured
that the proportion of graphs on $n$ vertices which are determined by their
generalized spectra goes to 1 as $n$ tends to infinity. Wang et al. [18, 21,
14, 19] have a number of results supporting this conjecture. They gave
sufficient conditions for a graph to be determined by its generalized
spectrum, and the majority of their results are proven for a wide class of
graphs, the so-called controllable graphs. In fact, it is known that almost
all graphs are controllable [15].

In this paper we study these concepts from the perspective of logical
definability. We prove that generalized cospectrality is implied by elementary
equivalence with respect to the three-variable counting first-order logic
$C^{3}$. We also show that this is not the case with $C^{2}$, nor with any
number of variables if we exclude counting quantifiers. Using this result we
prove that generalized cospectrality coincides with $C^{3}$-equivalence for a
relevant class of regular graphs (including all distance-regular graphs).
Finally we show that, for controllable graphs, $C^{2}$-equivalence coincides
with isomorphism. The latter yields a new proof of the classical result of
Immerman and Lander [12] that almost all graphs are definable (up to
isomorphism) in the logic $C^{2}$. Our work implies some of the results in the
work of Dawar, Severini and Zapata [6] and presents them in a more general
setup.

##  2 Generalized Cospectrality

If $u$ and $v$ are vertices from a graph $\Gamma$ with adjacency matrix $A$,
the number of walks in $\Gamma$ from $u$ to $v$ with length $\ell$ is equal to
$(A^{\ell})_{u,v}$. Thus the number of closed walks of length $\ell$ in
$\Gamma$ is $\operatorname{tr}(A^{\ell})$, and so

$\sum_{\ell\geq 0}\operatorname{tr}(A^{\ell})x^{\ell}$

is the generating function for closed walks in $\Gamma$ counted by length. If
$\varPhi^{\ \\!\\!\prime}(\Gamma,x)$ denotes the derivative of
$\varPhi(\Gamma,x)$ with respect to $x$, we find that

$\sum_{\ell\geq 0}\operatorname{tr}(A^{\ell})x^{\ell}=\frac{x^{-1}\ \varPhi^{\
\\!\\!\prime}(\Gamma,x^{-1})}{\ \varPhi(\Gamma,x^{-1})}.$

Therefore, two graphs are cospectral if and only if they have the same number
of closed walks of each length.

If $\Gamma$ and $\Gamma^{\prime}$ are non-cospectral graphs, there exists some
$\ell\geq 1$ such that the number of closed walks of length $\ell$ in $\Gamma$
and $\Gamma^{\prime}$ is not the same. This fact can be expressed in the
language of first-order logic using counting quantifiers and not more than 3
variables. The language $L^{k}$ consists of the fragment of first-order logic
in which only $k\geq 1$ distinct variables can be used. We use $C^{k}$ to
denote extension of $L^{k}$ with counting quantifiers: for each non-negative
integer $r$, we have a quantifier $\exists^{\geq r}$ whose semantics is
defined so that $\exists^{\geq r}\phi(x)$ is true in a graph if there are at
least $r$ distinct vertices which can be substituted for $x$ to make $\phi$
true. We use the abbreviation $\exists^{=r}\phi$ for the formula
$\exists^{\geq r}\phi\land\lnot\exists^{\geq r+1}\phi$ that asserts the
existence of exactly $r$ vertices satisfying $\phi$.

Two graphs $\Gamma$ and $\Gamma^{\prime}$ are elementary equivalent with
respect to a first-order language $L$ (or $L$-equivalent), just in case
$\Gamma\models\phi$ if and only if $\Gamma^{\prime}\models\phi$ for any
$L$-sentence $\phi$. In other words, $L$-equivalent graphs are precisely those
graphs that cannot be distinguished by any property defined by a sentence in
the language $L$. We write $\Gamma\equiv_{L}\Gamma^{\prime}$ to denote that
$\Gamma$ and $\Gamma^{\prime}$ are elementary equivalent with respect to $L$.

The next result shows that $C^{3}$-equivalence implies generalized
cospectrality.

######  Theorem 2.1.

$C^{3}$-equivalent graphs are generalized cospectral.

###### Proof.

For every non-negative integer $r$, we use counting quantifiers and not more
than three variables to write a formula $\psi_{\ell}^{r}(x,y)$ that asserts
the existence of exactly $r$ distinct walks of length $\ell\geq 1$ between $x$
and $y$. We define $\psi_{\ell}^{r}(x,y)$ by induction on $\ell$. For
$\ell=1$, let

$\psi_{1}^{0}(x,y):=\lnot
E(x,y),\quad\psi_{1}^{1}(x,y):=E(x,y)\quad\textnormal{and}\quad\psi_{1}^{r}(x,y):=\bot\
\textnormal{ if }\ r>1.$

Assuming that we have defined $\psi_{\ell}^{r}(x,y)$ for every $r$, we proceed
with the definitions for $\ell+1$:

$\psi_{\ell+1}^{0}(x,y):=\forall z(E(x,z)\to\psi_{\ell}^{0}(z,y)).$

An integer partition of $r>1$ is a sequence
$(r_{1}^{a_{1}},r_{2}^{a_{2}},\dots,r_{d}^{a_{d}})$ of $d\leq r$ pairwise
distinct positive integers (called the parts of $r$), such that for any $i$
($1\leq i\leq d$) the part $r_{i}\geq 0$ is repeated $a_{i}\geq 1$ times and
$r=\sum_{i=1}^{d}a_{i}r_{i}$. Let $\Pi_{r}$ denote the set of all integer
partitions of $r$ and note that this is a finite set. Then

$\psi_{\ell+1}^{r}(x,y):=\bigvee_{(r_{1}^{a_{1}},\ldots,r_{d}^{a_{d}})\in\Pi_{r}}[\bigwedge_{i=1}^{d}(\exists^{=a_{i}}x\
\psi_{\ell}^{r_{i}}(z,y))\land\exists^{\geq a}z\ E(x,z)]$

where $a=\sum_{i=1}^{d}a_{i}$. Here $a_{i}$ denotes the number of neighbors of
$x$ for which there are exactly $r_{i}$ walks of length $\ell$ from each of
them to $y$.

All of these definitions make use of at most three variables, and therefore
each $\psi_{\ell}^{r}$ is a formula of the language $C^{3}$. Thus we can write
a $C^{3}$-sentence $\phi_{\ell}^{r}$ which is true in a graph when the total
number of closed walks of length $\ell$ is exactly $r$:

$\phi_{\ell}^{r}:=\bigvee_{(r_{1}^{a_{1}},\dots,r_{d}^{a_{d}})\in\Pi_{r}}\bigwedge_{i=1}^{d}\exists^{=a_{i}}x\exists
y\ (\psi_{\ell}^{r_{i}}(x,y)\land x=y).$

If $\Gamma$ and $\Gamma^{\prime}$ are not generalized cospectral graphs, then
either $\Gamma$ and $\Gamma^{\prime}$ are non-cospectral or ${\mkern
2.0mu\overline{\mkern-2.0mu\Gamma}}$ and ${\mkern
2.0mu\overline{\mkern-2.0mu\Gamma^{\prime}}}$ are non-cospectral. Without loss
of generality we assume that $\Gamma$ and $\Gamma^{\prime}$ do not have the
same number of closed walks of length $\ell$ for some $\ell\geq 1$. Let $r$ be
the number of closed walks of length $\ell$ in $\Gamma$. Then
$\Gamma\models\phi_{\ell}^{r}$ and $\Gamma^{\prime}\not\models\phi_{\ell}^{r}$
and therefore $\Gamma\not\equiv_{C^{3}}\Gamma^{\prime}$. ∎

Theorem 2.1 is optimal in the sense that $C^{2}$-equivalence is not sufficient
for generalized cospectrality. To see this, let $\Gamma$ be the disjoint union
of two triangles and let $\Gamma^{\prime}$ be a cycle of length 6. A simple
pebble game argument shows that $\Gamma\equiv_{C^{2}}\Gamma^{\prime}$ (see
e.g. [12, Proposition 4.7.4]). However, $\Gamma$ and $\Gamma^{\prime}$ are not
generalized cospectral because they have a different number of triangles and
the spectrum determines the number of triangles.

The converse of Theorem 2.1 does not hold in general. Suppose, for instance,
that $\Gamma$ and $\Gamma^{\prime}$ are the left and right graphs from Figure
1, respectively. This is the smallest pair of nonisomorphic generalized
cospectral graphs. Since $\Gamma$ has one isolated vertex and
$\Gamma^{\prime}$ is connected, then $\Gamma\models\exists x\forall y\lnot
E(x,y)$ and $\Gamma\not\models\exists x\forall y\lnot E(x,y)$. Hence
$\Gamma\not\equiv_{C^{2}}\Gamma^{\prime}$, and therefore
$\Gamma\not\equiv_{C^{k}}\Gamma^{\prime}$ for $k\geq 2$.

Figure 1: Smallest pair of generalized cospectral graphs with respect to the
adjacency matrix.

The use of counting is essential for the distinguishability of the generalized
spectra in finite-variable logics.

######  Theorem 2.2.

There is a pair of nonisomorphic $L^{k}$-equivalent graphs which are not
generalized cospectral for each positive integer $k$.

###### Proof.

For $k\geq 1$, let $n_{k}$ be the smallest integer greater than
$2(k\log(4)+\log(k))/\log(13)$ and let $q_{k}=13^{n_{k}}$. Then
$q_{k}>k^{2}2^{4k}$. We write ${\mathbb{F}}_{q_{k}}$ to denote the finite
field of order $q_{k}$.

Let $\Gamma_{k}$ and $\Gamma^{\prime}_{k}$ be a pair of graphs with vertex set
${\mathbb{F}}_{q_{k}}$ defined as follows. Two vertices $i$ and $j$ are
adjacent in $\Gamma_{k}$ if there exists a positive integer $x$ such that
$x^{2}\equiv(i-j)\ \mathopen{(}\textnormal{mod}\ q_{k}\mathclose{)}$. The
vertices $i$ and $j$ are adjacent in $\Gamma^{\prime}_{k}$ if there exists a
positive integer $x$ such that $x^{3}\equiv(i-j)\
\mathopen{(}\textnormal{mod}\ q_{k}\mathclose{)}$. Hence, $\Gamma_{k}$ is a
Paley graph and $\Gamma^{\prime}_{k}$ is a cubic Paley graph.

It can be shown that with our choice of parameters
$\Gamma_{k}\equiv_{L^{k}}\Gamma^{\prime}_{k}$ (see [2] and also [1]). Since
Paley graphs and cubic Paley graphs are strongly regular, the parameters
(which include the degree) of these classes of graphs determine their
characteristic polynomials. Thus $\Gamma_{k}$ and $\Gamma^{\prime}_{k}$ are
cospectral if and only if they have the same parameters. However, $\Gamma_{k}$
is regular of degree $(q_{k}-1)/2$ and $\Gamma^{\prime}_{k}$ is regular of
degree $(q_{k}-1)/3$. Therefore $\Gamma_{k}$ and $\Gamma^{\prime}_{k}$ are not
isomorphic and not generalized cospectral. ∎

##  3 Coherent Algebras

A matrix algebra is a real or complex vector space of matrices closed under
matrix multiplication. The Schur product of two $n\times n$ matrices $A$ and
$B$ is the $n\times n$ matrix $A\circ B$ given by

$(A\circ B)_{i,j}=(A)_{i,j}(B)_{i,j}.$

This is a commutative and associative operation with the identity $J$. A
coherent algebra is a matrix algebra closed under conjugate-transpose and
Schur multiplication which contains $I$ and $J$.

If $A$ is the adjacency matrix of a graph $\Gamma$, the adjacency algebra of
$\Gamma$ is the matrix algebra ${\mathbb{C}}[A]$ of polynomials in $A$ with
complex coefficients. It is the unique minimal matrix algebra that contains
$A$. The coherent closure of $\Gamma$ is the intersection of all matrix
algebras that contain ${\mathbb{C}}[A]$ which are closed under Schur product
and conjugate-transpose. It is the unique minimal coherent algebra that
contains ${\mathbb{C}}[A]$.

A homomorphism of algebras is a ring homomorphism that commutes with scalar
multiplication. An algebra homomorphism between two coherent algebras need not
preserve the Schur product. A coherent homomorphism is an algebra homomorphism
that commutes with Schur multiplication.

Any vector space of matrices which is closed under Schur product has a unique
basis of matrices with entries 0 and 1, see for instance [3, Theorem
2.6.1(i)]. An algebra homomorphism between two coherent algebras commutes with
Schur product if and only if it maps the 01-basis of one algebra to the
01-basis of the other (see e.g. [5, Proposition 2.3.17]).

Weisfeiler and Leman [22] provided an algorithm that computes in polynomial
time the 01-basis of the coherent closure of any graph. Two graphs are called
WL-equivalent if there is an invertible coherent homomorphism between their
coherent closures. The adjacency matrix of a graph does not necessarily belong
to the 01-basis of its coherent closure. However, we have the following result
which implies that WL-equivalent graphs are generalized cospectral. It follows
from [4, Theorem 5.2].

######  Lemma 3.1.

Two graphs are WL-equivalent if and only if they are $C^{3}$-equivalent.

##  4 Distance-Regular Graphs

Let $\Gamma$ be a graph on $n$ vertices with diameter $d$. We say that
$\Gamma$ is distance-regular with intersection array
$\\{b_{0},b_{1},\dots,b_{d-1};c_{1},c_{2},\dots,c_{d}\\}$ if $\Gamma$ is
regular of degree $k=b_{0}$, and if for any two vertices $u$ and $v$ at
distance $i$, there are precisely $c_{i}$ neighbors of $v$ at distance $i-1$
from $u$, and $b_{i}$ neighbors of $v$ at distance $i+1$ from $u$. It is well
known that two distance-regular graphs are cospectral if and only if they have
the same intersection array (see e.g. [3]). Since the only vertex at distance
0 from a given vertex is itself, we have that $c_{1}=1$. The five Platonic
solids are simple examples: the tetrahedron has intersection array
$\\{3;1\\}$, the octahedron $\\{4,1;1,4\\}$, the cube $\\{3,2,1;1,2,3\\}$, the
icosahedron $\\{5,2,1;1,2,5\\}$ and the dodecahedron
$\\{3,2,1,1,1;1,1,1,2,3\\}$. Every strongly regular graph with parameters
$\\{n,k;a,c\\}$ is a distance-regular graph with diameter at most 2 and
intersection array $\\{k,k-a-1;1,c\\}$.

The $i$-th distance matrix of $\Gamma$ is the $n\times n$ 01-matrix $A_{i}$
with $uv$-entry equal to 1 if and only if the distance between vertex $u$ and
vertex $v$ in $\Gamma$ is $i$. By convention, we set $A_{0}=I$ and $A_{i}=0$
if $i$ is greater than $d$. Then $\sum_{i=0}^{d}A_{i}=J$ and so
${\mathcal{D}}=\\{A_{0},A_{1},\dots,A_{d}\\}$ is a linearly independent set of
symmetric 01-matrices. It follows that $\mathop{\mathrm{span}}({\mathcal{D}})$
is a Schur-closed vector space of symmetric matrices which contains $I$ and
$J$.

Since $A_{1}$ is the adjacency matrix of $\Gamma$, if we set
$a_{i}=k-b_{i}-c_{i}$ for $i=0,\dots,d$ where $b_{-1}=b_{d}=c_{0}=c_{d+1}=0$,
then we have

$A_{1}A_{i}=b_{i-1}A_{i-1}+a_{i}A_{i}+c_{i+1}A_{i+1}.$

If $i$ is less than $d$ then $c_{i+1}$ is non-zero, and thus $A_{i+1}$ is a
linear combination of $A_{i-1},A_{i}$ and $A_{1}A_{i}$. We see by induction
that $A_{i}$ is a polynomial of degree $i$ in $A_{1}$ for $i=1,\dots,d$. Again
by induction, we find that
$A_{i}A_{j}\in\mathop{\mathrm{span}}({\mathcal{D}})$ for all $i$ and $j$ (see
[10, Lemma 4.2.2]). Thus $\mathop{\mathrm{span}}({\mathcal{D}})$ is closed
under matrix multiplication and so it is a coherent algebra.

Consider two graphs $\Gamma$ and $\Gamma^{\prime}$ with adjacency matrices $A$
and $A^{\prime}$, respectively. Since $A$ and $A^{\prime}$ are real symmetric
matrices, they are diagonalizable. This implies that if $A$ and $A^{\prime}$
have the same characteristic polynomial, then
$Q^{{}^{\\!\top\\!\\!}}AQ=A^{\prime}$ for some orthogonal matrix $Q$. It
follows that cospectral graphs have similar adjacency matrices. In particular,
if $\Gamma$ and $\Gamma^{\prime}$ are cospectral distance-regular graphs, then
all their distance matrices are simultaneously similar. This is because the
$i$-th distance matrix of $\Gamma$ is a polynomial of degree $i$ in the
adjacency matrix of $\Gamma$, and the same is true for $\Gamma^{\prime}$. So
if $A_{i}$ and $A_{i}^{\prime}$ are respectively the $i$-th distance matrices
of $\Gamma$ and $\Gamma^{\prime}$, then there is a polynomial $p_{i}$ of
degree $i$ such that

$A^{\prime}_{i}=p_{i}(A_{1}^{\prime})=p_{i}(Q^{{}^{\\!\top\\!\\!}}A_{1}Q)=Q^{{}^{\\!\top\\!\\!}}p_{i}(A_{1})Q=Q^{{}^{\\!\top\\!\\!}}A_{i}Q$

for all $i$.

Suppose $\Gamma$ and $\Gamma^{\prime}$ are distance-regular graphs. Friedland
[9] proved that if $\varPsi$ is an invertible coherent homomorphism between
two coherent algebras, then there exists a unitary matrix $U$ such that
$\varPsi(M)=UMU^{\ast}$ for all $M$. The converse is also true. In particular,
there is an invertible coherent homomorphism $\varPsi$ between the coherent
algebras generated by the distance matrices of $\Gamma$ and $\Gamma^{\prime}$
provided $\Gamma$ and $\Gamma^{\prime}$ are generalized cospectral. By taking
the restriction of $\varPsi$ to the coherent closures of $\Gamma$ and
$\Gamma^{\prime}$, we obtain that $\Gamma$ and $\Gamma^{\prime}$ are WL-
equivalent. Thus we obtain the following consequence of Lemma 3.1. A proof of
a stronger result will be given in Section 5.

######  Theorem 4.1.

For distance-regular graphs, generalized cospectrality implies
$C^{3}$-equivalence.

Now assume $\Gamma$ is a regular graph of degree $k$. Then we have that

$\varPhi({\mkern 2.0mu\overline{\mkern-2.0mu\Gamma}},x)=(-1)^{n}\
\frac{x-n+k+1}{x+k+1}\ \varPhi(\Gamma,-x-1).$

Therefore, two regular graphs are cospectral if and only if they are
generalized cospectral. The unique distance-regular graph with intersection
array $\\{5,4,1,1;1,1,4,5\\}$ is called the Wells graph, see for instance [3,
Theorem 9.2.9]. Van Dam and Haemers [16] showed that there is a regular graph
cospectral with the Wells graph which is not distance-regular. We have the
following result which implies that the Wells graph and its cospectral mate
are not $C^{3}$-equivalent.

######  Theorem 4.2.

For each intersection array ${\mathcal{I}}$ there is a $C^{3}$-sentence
$\phi_{\mathcal{I}}$ such that a graph $\Gamma$ satisfies $\phi_{\mathcal{I}}$
if and only if $\Gamma$ is distance-regular with intersection array
${\mathcal{I}}$.

###### Proof.

Let ${\mathcal{I}}=\\{b_{0},b_{1},\dots,b_{d-1};c_{1},c_{2},\dots,c_{d}\\}$.
We write a $C^{3}$-sentence which is true in a graph $\Gamma$ if and only if
$\Gamma$ is distance-regular with intersection array ${\mathcal{I}}$. We can
express the existence of a path from $x$ to $y$ of length $i\geq 0$ in the
three-variable counting logic $C^{3}$ as follows:

$\phi_{0}(x,y):=(x=y),\quad\quad\phi_{1}(x,y):=E(x,y)$

and

$\phi_{i+1}(x,y):=\exists z[E(x,z)\land\exists x(z=x\land\phi_{i}(x,y))].$

Let $\delta_{i}(x,y)$ be the $C^{3}$-formula defined by

$\delta_{i}(x,y):=\phi_{i}(x,y)\land\bigwedge_{j=0}^{i-1}\lnot\phi_{j}(x,y).$

Hence $\Gamma\models\delta_{i}(x,y)$ precisely when $x$ and $y$ are vertices
at distance $i$ in $\Gamma$. If $r$ is a positive integer, we define the
$C^{3}$-sentences

$\gamma^{r}_{i}:=\forall x\forall
y[\delta_{i}(x,y)\to\exists^{=r}z(E(y,z)\land\delta_{i-1}(x,z))]\ \textnormal{
for }\ i\geq 1.$

and

$\beta^{r}_{i}:=\forall x\forall
y[\delta_{i}(x,y)\to\exists^{=r}z(E(y,z)\land\delta_{i+1}(x,z))]\ \textnormal{
for }\ i\geq 0.$

Then $\Gamma\models\gamma^{c_{i}}_{i}\land\beta^{b_{i}}_{i}$ if and only if
for any two vertices $x$ and $y$ at distance $i$ in $\Gamma$, there are
exactly $c_{i}$ vertices adjacent to $y$ at distance $i-1$ from $x$, and
$b_{i}$ vertices adjacent to $y$ at distance $i+1$ from $x$. Therefore

$\Gamma\models\bigwedge_{i=1}^{d}(\beta^{b_{i}}_{i-1}\land\gamma^{c_{i}}_{i})$

whenever $\Gamma$ is distance-regular with intersection array ${\mathcal{I}}$.
∎

One consequence of the previous result is that all graphs which are
$C^{3}$-equivalent to the Wells graph are isomorphic to it. Indeed

$\Gamma\models\beta^{5}_{0}\land\beta^{4}_{1}\land\beta^{1}_{2}\land\beta^{1}_{3}\land\gamma^{1}_{1}\land\gamma^{1}_{2}\land\gamma^{4}_{3}\land\gamma^{5}_{4}$

if and only if $\Gamma$ is distance-regular with intersection array
$\\{5,4,1,1;1,1,4,5\\}$, and the Wells graph is unique up to isomorphism with
this intersection array.

######  Corollary 4.3.

There is a pair of nonisomorphic generalized cospectral regular graphs which
are not $C^{3}$-equivalent.

###### Proof.

Let $\Gamma$ be the Wells graph and let $\Gamma^{\prime}$ be a nonisomorphic
cospectral mate of $\Gamma$. Then $\Gamma$ is distance-regular and so it is
regular. Also $\Gamma^{\prime}$ is regular. Thus $\Gamma$ and
$\Gamma^{\prime}$ cannot be $C^{3}$-equivalent for then we would have that
$\Gamma^{\prime}$ is distance-regular with the same intersection array as
$\Gamma$, and this would imply that $\Gamma$ and $\Gamma^{\prime}$ are
isomorphic. ∎

##  5 Quotient-Polynomial Graphs

Quotient-polynomial graphs were introduced by Fiol and Penjić [8] as a
generalization of orbit-polynomial and distance-regular graphs.

Let $\Gamma$ be a graph on $n$ vertices with adjacency matrix $A$. For each
eigenvalue $\theta$ of $A$, let $E_{\theta}$ be the matrix representing the
orthogonal projection onto the eigenspace belonging to $\theta$. Then $A$ has
the spectral decomposition

$A=\sum_{\theta}\theta E_{\theta}.$

For any two vertices $u$ and $v$ from $\Gamma$, let $\mathbf{w}_{\ell}(u,v)$
be the number of walks of length $\ell$ between $u$ and $v$ in $\Gamma$. Thus

$\mathbf{w}_{\ell}(u,v)=(A^{\ell})_{u,v}=\sum_{\theta}\theta^{\ell}(E_{\theta})_{u,v}.$

Suppose $A$ has $d+1$ distinct eigenvalues (and hence the diameter of $\Gamma$
is at least $d$). We say that a partition $\pi=(C_{1},\dots,C_{m})$ of
$V(\Gamma)\times V(\Gamma)$ is walk-regular if all the pairs $(u,v)$ in cell
$C_{i}$ have the same vector

$\mathbf{w}(u,v)=(\mathbf{w}_{0}(u,v),\dots,\mathbf{w}_{d}(u,v))^{{}^{\\!\top\\!\\!}}.$

It follows that all pairs of vertices from the same cell are at the same
distance.

Given a walk-regular partition $\pi=(C_{1},\dots,C_{m})$ of $\Gamma$, let
$B_{i}$ be the $n\times n$ 01-matrix with $uv$-entry equal to 1 if and only if
$(u,v)\in C_{i}$. Let $w_{\ell}(i)$ be the the number of walks of length
$\ell$ between any two vertices $u$ and $v$ such that $(u,v)\in C_{i}$. Then,
for all $\ell=0,\dots,d$, we have

$A^{\ell}=\sum_{i=1}^{m}w_{\ell}(i)B_{i}.$

Thus
${\mathbb{C}}[A]=\mathop{\mathrm{span}}\\{A^{0},\dots,A^{d}\\}\subset\mathop{\mathrm{span}}\\{B_{1},\dots,B_{m}\\}$,
and so it is necessary that $m\geq d+1$. We say that $\Gamma$ is quotient-
polynomial if there are polynomials $p_{i}$ with degree at most $d$ such that
$p_{i}(A)=B_{i}$ for all $i$. It follows that $\Gamma$ is quotient-polynomial
if and only if ${\mathbb{C}}[A]=\mathop{\mathrm{span}}\\{B_{1},\dots,B_{m}\\}$
(and hence $m=d+1$). Every distance-regular graph is quotient-polynomial, see
for instance [7, Proposition 5.1].

Fiol and Penjić [8] showed that a graph is quotient-polynomial if and only if
its adjacency algebra is closed under Schur product. Since $\pi$ is a
partition, we have $\sum_{i=1}^{m}B_{i}=J$ and so $J\in{\mathbb{C}}[A]$. It
follows that $\Gamma$ is quotient-polynomial if and only if ${\mathbb{C}}[A]$
is a coherent algebra. Therefore, a graph is quotient-polynomial if and only
if its coherent closure is its adjacency algebra.

######  Theorem 5.1.

Two quotient-polynomial graphs are generalized cospectral if and only if they
are $C^{3}$-equivalent.

###### Proof.

We show that for quotient-polynomial graphs generalized cospectrality implies
$C^{3}$-equivalence. For the converse we already have Theorem 2.1. Let
$\Gamma$ and $\Gamma^{\prime}$ be graphs with adjacency matrices $A$ and
$A^{\prime}$, respectively. If $\Gamma$ and $\Gamma^{\prime}$ are generalized
cospectral, then they are cospectral and so there exists an orthogonal matrix
$Q$ such that $Q^{{}^{\\!\top\\!\\!}}AQ=A^{\prime}$. Let $B_{i}$ and
$B_{i}^{\prime}$ be the matrices associated with the walk-regular partitions
of $\Gamma$ and $\Gamma^{\prime}$, respectively. Suppose $\Gamma$ and
$\Gamma^{\prime}$ are quotient-polynomial. Then there is a polynomial $p_{i}$
of degree at most $d$ such that

$B^{\prime}_{i}=p_{i}(A^{\prime})=p_{i}(Q^{{}^{\\!\top\\!\\!}}AQ)=Q^{{}^{\\!\top\\!\\!}}p_{i}(A)Q=Q^{{}^{\\!\top\\!\\!}}B_{i}Q$

for all $i$. Thus there is an invertible coherent homomorphism
$\varPsi(M)=Q^{{}^{\\!\top\\!\\!}}MQ$ between the coherent closures of
$\Gamma$ and $\Gamma^{\prime}$. Therefore $\Gamma$ and $\Gamma^{\prime}$ are
WL-equivalent, and hence Lemma 3.1 implies that $\Gamma$ and $\Gamma^{\prime}$
are $C^{3}$-equivalent. ∎

Since quotient-polynomial graphs are a generalization of orbit-polynomial and
distance-regular graphs, as a corollary of Theorem 5.1 we obtain Theorem 4.1.

##  6 Controllable Graphs

Let $\Gamma$ be a graph on $n$ vertices with adjacency matrix $A$, and let
${\mathbf{1}}$ denote the all-one vector of length $n$. The number of walks of
length $\ell$ in $\Gamma$ is equal to

$\operatorname{tr}(A^{\ell}J)={\mathbf{1}}^{{}^{\\!\top\\!\\!}}A^{\ell}{\mathbf{1}}.$

Since

$\sum_{\ell\geq 0}A^{\ell}x^{\ell}=(I-xA)^{-1}$

we have that the generating function for all walks in $\Gamma$ is

$\sum_{\ell\geq
0}\operatorname{tr}(A^{\ell}J)x^{\ell}={\mathbf{1}}^{{}^{\\!\top\\!\\!}}(I-xA)^{-1}{\mathbf{1}}.$

We say that two graphs are walk-equivalent if their generating functions for
all walks are equal. Since

$xI-(J-A)=(xI+A)(I-(xI+A)^{-1}J)$

and

$I-(xI+A)^{-1}J=I-((xI+A)^{-1}{\mathbf{1}}){\mathbf{1}}^{{}^{\\!\top\\!\\!}}$

then using the identity
$\det(\mathbf{u}\mathbf{v}^{{}^{\\!\top\\!\\!}})=1-\mathbf{v}^{{}^{\\!\top\\!\\!}}\mathbf{u}$,
we find that

$\frac{\varPhi({\mkern 2.0mu\overline{\mkern-2.0mu\Gamma}},x-1)}{(-1)^{n}\
\varPhi(\Gamma,-x)}=1-{\mathbf{1}}^{{}^{\\!\top\\!\\!}}(xI+A)^{-1}{\mathbf{1}}$

and so

${\mathbf{1}}^{{}^{\\!\top\\!\\!}}(I-xA)^{-1}{\mathbf{1}}=\frac{1}{x}\left(\frac{\varPhi({\mkern
2.0mu\overline{\mkern-2.0mu\Gamma}},-x^{-1}-1)}{(-1)^{n}\
\varPhi(\Gamma,x^{-1})}-1\right).$

Thus, if two graphs are generalized cospectral then they are walk-equivalent.

######  Theorem 6.1.

$C^{2}$-equivalent graphs are walk-equivalent.

###### Proof.

We write a $C^{2}$-formula $\psi^{r}_{\ell}(x)$ such that for any graph
$\Gamma$ and any vertex $u$ from $\Gamma$, we have

$\Gamma\models\psi^{r}_{\ell}(u)$

if and only if there are $r\geq 0$ walks of length $\ell\geq 1$ in $\Gamma$
starting at $u$. We proceed by induction on $\ell$. If $\ell=1$ then we let

$\psi^{0}_{1}(x):=\forall y\lnot
E(x,y)\qquad\textnormal{and}\qquad\psi^{r}_{1}(x):=\exists^{=r}y\
E(x,y)\quad\textnormal{for}\ r>0.$

For $\ell>1$, we define

$\psi^{0}_{\ell+1}(x):=\forall y(E(x,y)\to\psi^{0}_{\ell}(y))$

and if $r>0$ then

$\psi^{r}_{\ell+1}(x):=\bigvee_{(r_{1}^{a_{1}},\dots,r_{d}^{a_{d}})\in\Pi_{r}}[(\bigwedge_{i=1}^{d}\exists^{=a_{i}}y\
\psi_{\ell}^{r_{i}}(y))\land\exists^{\geq a}y\ E(x,y)]$

where $\Pi_{r}$ is the set of integer partitions
$(r_{1}^{a_{1}},\dots,r_{d}^{a_{d}})$ of $r$ (so $r=\sum_{i=1}^{d}a_{i}r_{i}$)
and $a=\sum_{i=1}^{d}a_{i}$. With this notation we define the $C^{2}$-sentence
$\phi_{\ell}^{r}$ as follows:

$\phi_{\ell}^{r}:=\bigvee_{(r_{1}^{a_{1}},\dots,r_{d}^{a_{d}})\in\Pi_{r}}\
\bigwedge_{i=1}^{d}\exists^{=a_{i}}x\ \psi_{\ell}^{r_{i}}(x).$

By definition $\Gamma\models\phi_{\ell}^{r}$ if and only if there are $r$
walks of length $\ell$ in $\Gamma$.

Now suppose that $\Gamma$ and $\Gamma^{\prime}$ are two graphs which are not
walk-equivalent. Then $\Gamma$ and $\Gamma^{\prime}$ have a different number
of walks of length $\ell$ for some $\ell$. Let $r$ be the number of walks of
length $\ell$ in $\Gamma$. We have $\Gamma\models\phi_{\ell}^{r}$ and
$\Gamma^{\prime}\not\models\phi_{\ell}^{r}$. Therefore
$\Gamma\not\equiv_{C^{2}}\Gamma^{\prime}$. ∎

######  Corollary 6.2.

Two regular graphs are walk-equivalent if and only if they are
$C^{2}$-equivalent.

###### Proof.

Let $\Gamma$ be a $k$-regular graph on $n$ vertices with adjacency matrix $A$.
If $A$ has spectral decomposition

$A=\sum_{\theta}\theta E_{\theta}$

then $A{\mathbf{1}}=k{\mathbf{1}}$ and
$E_{k}=n^{-1}{\mathbf{1}}{\mathbf{1}}^{{}^{\\!\top\\!\\!}}$. Thus
$E_{\theta}E_{k}=E_{\theta}{\mathbf{1}}{\mathbf{1}}^{{}^{\\!\top\\!\\!}}=0$
and so ${\mathbf{1}}^{{}^{\\!\top\\!\\!}}E_{\theta}{\mathbf{1}}=0$ for all
$\theta\neq k$. Since

$(I-xA)^{-1}=\sum_{\theta}\frac{1}{1-x\theta}E_{\theta}$

we find that the generating function for all walks in $\Gamma$ is

${\mathbf{1}}^{{}^{\\!\top\\!\\!}}(I-xA)^{-1}{\mathbf{1}}=\frac{n}{1-xk}.$

Hence, any two $k$-regular graphs on $n$ vertices are walk-equivalent.
Therefore if $\Gamma$ and $\Gamma^{\prime}$ are two regular graphs such that
$\Gamma\not\equiv_{C^{2}}\Gamma^{\prime}$, then either the number of vertices
in $\Gamma$ is different than the number of vertices in $\Gamma^{\prime}$ or
the degree of $\Gamma$ is different than the degree of $\Gamma^{\prime}$. In
either case, $\Gamma$ and $\Gamma^{\prime}$ are not walk-equivalent. The
converse follows immediately from Theorem 6.1. ∎

The walk matrix of $\Gamma$ is the $n\times n$ matrix

$W_{\Gamma}=\big{(}{\mathbf{1}}\quad A{\mathbf{1}}\quad\cdots\quad
A^{n-1}{\mathbf{1}}\big{)}.$

Our next result combined with Theorem 2.1 and the fact that $C^{3}$-equivalent
graphs are necessarily $C^{2}$-equivalent implies [17, Lemma 3].

######  Lemma 6.3.

Let $\Gamma$ and $\Gamma^{\prime}$ be $C^{2}$-equivalent graphs. Then

$W^{{{}^{\\!\top\\!\\!}}}_{\Gamma}W_{\Gamma}=W^{{{}^{\\!\top\\!\\!}}}_{\Gamma^{\prime}}W_{\Gamma^{\prime}}.$

###### Proof.

We shall use the $C^{2}$-formulas $\psi^{r}_{\ell}(x)$ which are defined in
the proof of Theorem 6.1. Recall that $\psi^{r}_{\ell}(x)$ asserts the
existence of exactly $r$ walks of length $\ell$ starting at $x$. Since
$\Gamma$ and $\Gamma^{\prime}$ are $C^{2}$-equivalent, there is a vertex $v$
from $\Gamma$ such that $\Gamma\models\psi^{r}_{\ell}(v)$ if and only if there
is a vertex $v^{\prime}$ from $\Gamma^{\prime}$ such that
$\Gamma^{\prime}\models\psi^{r}_{\ell}(v^{\prime})$. Hence the mapping
$v\mapsto v^{\prime}$ is a bijection between the sets

$\\{v\in
V(\Gamma):\Gamma\models\psi^{r}_{\ell}(v)\\}\qquad\textnormal{and}\qquad\\{v^{\prime}\in
V(\Gamma^{\prime}):\Gamma^{\prime}\models\psi^{r}_{\ell}(v^{\prime})\\}$

for each $r\geq 0$ and $\ell\geq 1$. Since the rows of the walk matrix of a
graph are indexed by the vertices of the graph, it follows that $W_{\Gamma}$
and $W_{\Gamma^{\prime}}$ are equal up to a permutation of the rows induced by
the above bijection. Thus there is a permutation matrix $P$ such that
$PW_{\Gamma}=W_{\Gamma^{\prime}}$. Then

$W^{{{}^{\\!\top\\!\\!}}}_{\Gamma^{\prime}}W_{\Gamma^{\prime}}=(PW_{\Gamma})^{{{}^{\\!\top\\!\\!}}}(PW_{\Gamma})=W_{\Gamma}^{{{}^{\\!\top\\!\\!}}}P^{{{}^{\\!\top\\!\\!}}}PW_{\Gamma}=W^{{{}^{\\!\top\\!\\!}}}_{\Gamma}W_{\Gamma}.\qed$

We say that a graph $\Gamma$ is controllable if its walk matrix $W_{\Gamma}$
is invertible. The theory of controllable graphs was developed in [11], where
it was conjectured that the proportion of graphs on $n$ vertices which are
controllable goes to 1 as $n\to\infty$. It was later confirmed in [15] that
indeed almost all graphs are controllable. Wang and Xu [20] proved that if
$\Gamma$ and $\Gamma^{\prime}$ are two walk-equivalent controllable graphs
with adjacency matrices $A$ and $A^{\prime}$, respectively, then
$Q=W_{\Gamma}W_{\Gamma^{\prime}}^{-1}$ is an orthogonal matrix such that
$Q^{{{}^{\\!\top\\!\\!}}}AQ=A^{\prime}$ and $Q{\mathbf{1}}={\mathbf{1}}$. Thus
we have the following consequence of Theorem 6.1, Lemma 6.3 and the preceding
remark.

######  Corollary 6.4.

Two controllable graphs are isomorphic if and only if they are
$C^{2}$-equivalent.

###### Proof.

We prove that $C^{2}$-equivalent controllable graphs are isomorphic. Consider
two controllable graphs $\Gamma$ and $\Gamma^{\prime}$ with adjacency matrices
$A$ and $A^{\prime}$, respectively. If $\Gamma$ and $\Gamma^{\prime}$ are
$C^{2}$-equivalent, then by Theorem 6.1 $\Gamma$ and $\Gamma^{\prime}$ are
walk-equivalent. Hence the matrix $Q=W_{\Gamma}W_{\Gamma^{\prime}}^{-1}$
satisfies $Q^{{{}^{\\!\top\\!\\!}}}AQ=A^{\prime}$.

Now, in the proof of Lemma 6.3 we saw that there is a permutation matrix $P$
such that $W_{\Gamma}=P^{{}^{\\!\top\\!\\!}}W_{\Gamma^{\prime}}$. Then we have

$Q=W_{\Gamma}W_{\Gamma^{\prime}}^{-1}=P^{{}^{\\!\top\\!\\!}}W_{\Gamma^{\prime}}W_{\Gamma^{\prime}}^{-1}=P^{{}^{\\!\top\\!\\!}}$

and thus $PAP^{{{}^{\\!\top\\!\\!}}}=A^{\prime}$. Therefore $\Gamma$ and
$\Gamma^{\prime}$ are isomorphic. ∎

######  Remark 6.5.

For any fragment $L$ of the first-order language of graphs, we say that a
graph $\Gamma$ is $L$-definable if there is an $L$-sentence $\phi$ such that
every graph satisfying $\phi$ is isomorphic to $\Gamma$. Since almost all
graphs are controllable [15], Corollary 6.4 implies the classical result of
Immerman and Lander [12] that almost all graphs are $C^{2}$-definable.

### Acknowledgments

Part of this work was done during a Dagstuhl Seminar on Logic and Random
Discrete Structures, Germany, in February 2022. The authors would like to
thank the organizers of the workshop.

The research of A. Abiad is partially supported by the FWO grant number
1285921N. The research of O. Zapata is partially supported by the Sistema
Nacional de Investigadores grant number 620178.

## References

  * [1] Ananchuen, W., and Caccetta, L. Cubic and quadruple Paley graphs with the $n$-e.c. property.  Discrete Mathematics 306, 22 (2006), 2954–2961.
  * [2] Blass, A., Exoo, G., and Harary, F. Paley graphs satisfy all first-order adjacency axioms.  Journal of Graph Theory 5, 4 (1981), 435–439.
  * [3] Brouwer, A. E., Cohen, A. M., and Neumaier, A. Distance-Regular Graphs.  Springer Berlin Heidelberg, 1989.
  * [4] Cai, J.-Y., Fürer, M., and Immerman, N. An optimal lower bound on the number of variables for graph identification.  Combinatorica 12, 4 (1992), 389–410.
  * [5] Chen, G., and Ponomarenko, I. Lectures on coherent configurations.  http://www.pdmi.ras.ru/~inp/ccNOTES.pdf (2019).
  * [6] Dawar, A., Severini, S., and Zapata, O. Descriptive complexity of graph spectra.  Annals of Pure and Applied Logic 170 (2019), 993–1007.
  * [7] Fiol, M. A. Quotient-polynomial graphs.  Linear Algebra and its Applications 488 (2016), 363–376.
  * [8] Fiol, M. A., and Penjić, S. On symmetric association schemes and associated quotient-polynomial graphs.  Algebraic Combinatorics 4, 6 (2021), 947–969.
  * [9] Friedland, S. Coherent algebras and the graph isomorphism problem.  Discrete Applied Mathematics 25, 1-2 (1989), 73–98.
  * [10] Godsil, C. D. Algebraic Combinatorics, vol. 6.  CRC Press, 1993.
  * [11] Godsil, C. D. Controllable subsets in graphs.  Annals of Combinatorics 16, 4 (2012), 733–744.
  * [12] Immerman, N., and Lander, E. Describing graphs: A first-order approach to graph canonization.  In Complexity Theory Retrospective. Springer, 1990, pp. 59–81.
  * [13] Johnson, C. R., and Newman, M. A note on cospectral graphs.  Journal of Combinatorial Theory, Series B 28, 1 (1980), 96–103.
  * [14] Mao, L., Liu, F., and Wang, W. A new method for constructing graphs determined by their generalized spectrum.  Linear Algebra and its Applications 447 (2015), 112–127.
  * [15] O’Rourke, S., and Touri, B. On a conjecture of Godsil concerning controllable random graphs.  SIAM Journal on Control and Optimization 54, 6 (2016), 3347–3378.
  * [16] Van Dam, E. R., and Haemers, W. H. Spectral characterizations of some distance-regular graphs.  Journal of Algebraic Combinatorics 15, 2 (2002), 189–202.
  * [17] Van Dam, E. R., and Haemers, W. H. Developments on spectral characterizations of graphs.  Discrete Mathematics 309, 3 (2009), 576–586.
  * [18] Wang, W. Generalized spectral characterization revisited.  The Electronic Journal of Combinatorics 20 (2013), #P4.
  * [19] Wang, W. A simple arithmetic criterion for graphs being determined by their generalized spectra.  Journal of Combinatorial Theory, Series B 122 (2017), 438–451.
  * [20] Wang, W., and Xu, C.-X. A sufficient condition for a family of graphs being determined by their generalized spectra.  European Journal of Combinatorics 27, 6 (2006), 826–840.
  * [21] Wang, W., and Xu, C.-X. On the asymptotic behavior of graphs determined by their generalized spectra.  Discrete Mathematics 310 (2010), 70–76.
  * [22] Weisfeiler, B., and Leman, A. The reduction of a graph to canonical form and the algebra which appears therein.  Nauchno-Technicheskaya Informatsia, Seriya 2, 9 (1968), 12–16.