# Number of cliques of Paley-type graphs
over finite commutative local rings

Andrea L. Gallo, Denis E. Videla  Andrea L. Gallo, FaMAF – CIEM (CONICET),
Universidad Nacional de Córdoba,
Av. Medina Allende 2144, Ciudad Universitaria, (5000) Córdoba, Argentina.
E-mail<EMAIL_ADDRESS>Denis E. Videla, FaMAF – CIEM (CONICET),
Universidad Nacional de Córdoba,
Av. Medina Allende 2144, Ciudad Universitaria, (5000) Córdoba, Argentina.
E-mail<EMAIL_ADDRESS>
###### Abstract.

In this work, given $(R,\mathfrak{m})$ a finite commutative local ring with
identity and $k\in\mathbb{N}$ with $(k,|R|)=1$, we study the number of cliques
of any size in the Cayley graph $G_{R}(k)=Cay(R,U_{R}(k))$ with
$U_{R}(k)=\\{x^{k}:x\in R^{*}\\}$. Using the known fact that the graph
$G_{R}(k)$ can be obtained by blowing-up the vertices of
$G_{\mathbb{F}_{q}}(k)$ a number $|\mathfrak{m}|$ of times, with independence
sets the cosets of $\mathfrak{m}$, where $q$ is the size of the residue field
$R/\mathfrak{m}$ (see [20]). Then, by using the above blowing-up, we reduce
the study of the number of cliques in $G_{R}(k)$ over the local ring $R$ to
the computation of the number of cliques of $G_{R/\mathfrak{m}}(k)$ over the
finite residue field $R/\mathfrak{m}\simeq\mathbb{F}_{q}$. In this way, using
known numbers of cliques of generalized Paley graphs ($k=2,3,4$ and
$\ell=3,4$), we obtain several explicit results for the number of cliques over
finite commutative local rings with identity.

###### Key words and phrases:

Local rings, generalized Paley graphs, cliques

2020 Mathematics Subject Classification. Primary 05C25, 05C30; Secondary
11T30.

Partially supported by CONICET, FONCyT and SECyT-UNC

##  1\. Introduction

In this work we study the number of cliques of $G_{R}(k)$ over finite
commutative local rings with identity $R$, where $(k,|R|)=1$, through the
decomposition of $G_{R}(k)$ in terms of certain graph operation called blow-
up. The case when $k$ and $|R|$ are not coprime remains open. We will reduce
the computation of the number of $\ell$-cliques $\mathcal{K}_{\ell}(G_{R}(k))$
over finite commutative local rings $(R,\mathfrak{m})$ to the problem of
computing $\mathcal{K}_{\ell}(\Gamma(k,q))$ where $\Gamma(k,q)$ is the
generalized Paley graph. More precisely, we will show that
$\mathcal{K}_{\ell}(G_{R}(k))$ can be put in terms of
$\mathcal{K}_{\ell}(\Gamma(k,q))$, where the residue field $R/\mathfrak{m}$ is
isomorphic to $\mathbb{F}_{q}$.

### Preliminaries

Let $G$ be a finite abelian group and $S$ a subset of $G$ with $0\notin S$.
The Cayley graph  $\Gamma=Cay(G,S)$ is the directed graph whose vertex set is
$G$ and $v,w\in G$ form a directed edge (or arc) $\overrightarrow{vw}$ of
$\Gamma$ from $v$ to $w$ if $w-v\in S$. Since $0\notin S$ then $\Gamma$ has no
loops. Notice that if $S$ is symmetric, that is $-S=S$, then we can consider
$Cay(G,S)$ as undirected (and conversely), and hence $Cay(G,S)$ is
$|S|$-regular. In this work, we always consider $S$ symmetric.

We are interested in the unitary Cayley graph of $k$-th powers or $k$-unitary
Cayley graph defined by

(1.1) $G_{R}(k)=Cay(R,U_{R}(k))\qquad\text{where}\qquad U_{R}(k)=\\{x^{k}:x\in
R^{*}\\}.$

The case $G_{R}(1)$ are the called unitary Cayley graphs, they were
extensively studied (see [1], [10], [11], [13] and [17]). Recently, Liu and
Zhou [14] defined and studied the quadratic unitary Cayley graphs
$\mathcal{G}_{R}=Cay(R,T_{R})$, where $T_{R}=Q_{R}\cup(-Q_{R})$ and
$Q_{R}=\\{x^{2}:x\in R^{*}\\}$ with $R$ a finite commutative ring with
identity, when $Q_{R}$ is symmetric then $\mathcal{G}_{R}=G_{R}(2)$. Some
structure properties of $G_{R}(k)$, in the case $R$ local was strudied in [20]
(see also [4] for $R=\mathbb{Z}_{p^{\alpha}}$). In general, notice that
$G_{R}(k)$ is directed, moreover $U_{R}(k)$ is a symmetric set if and only if
$-1\in U_{R}(k)$.

One other interesting instance of these graphs is when $R=\mathbb{F}_{q}$ is a
finite field of cardinality $q=p^{r}$ with $p$ prime, where $k$ a non-negative
integer (with $k\mid q-1$), this graph is called generalized Paley graph (GP-
graph for short) and is denoted by $\Gamma(k,q)$, more precisely

(1.2) $\Gamma(k,q)=Cay(\mathbb{F}_{q},U_{k})\qquad\text{with}\qquad
U_{k}=\\{x^{k}:x\in\mathbb{F}_{q}^{*}\\}.$

Notice that $\Gamma(k,q)$ is an $n$-regular graph with $n=\tfrac{q-1}{k}$. The
graph $\Gamma(k,q)$ is undirected either if $q$ is even or if $k$ divides
$\tfrac{q-1}{2}$ when $p$ is odd (equivalently if $n$ is even when $p$ is odd)
and it is connected if $n$ is a primitive divisor of $q-1$ (see (2.3)). When
$k=1$ we get the complete graph $\Gamma(1,q)=K_{q}$ and when $k=2$ we get the
classic Paley graph $\Gamma(2,q)=P(q)$. The graphs $\Gamma(3,q)$ and
$\Gamma(4,q)$ are also of interest (see [19]). The GP-graphs have been
extensively studied in the few past years (see for instance [12], [15], [16],
[18], [21]. [22], [23], [24].)

#### Number of cliques in generalized Paley graphs

Recall that a complete graph of $n$ vertices is an undirected graph such that
all of its vertices are neighbours, it is denoted by $K_{n}$.

Given $G$ be a graph, a clique in $G$ is a complete subgraph of $G$. The
clique number of $G$ is the size of its maximum clique in $G$ and is usually
denoted by $\omega(G)$. The number of cliques of size $\ell$ in $G$ is denoted
by $\mathcal{K}_{\ell}(G)$, notice that

(1.3) $\omega(G)=\max\\{\ell\in\mathbb{N}:\mathcal{K}_{\ell}(G)\neq 0\\}.$

The clique number of $\Gamma(k,q)$ was studied in [23], [24]. In [9], the
authors found a closed formula for $\mathcal{K}_{\ell}(\Gamma(2,q))$ for
$\ell=3,4$ and $q=p$ prime, in terms of certain binary quadratic forms, see
also [2] for an extension to $q$ a prime power. In [8], the authors found a
general formula for $\mathcal{K}_{\ell}(\Gamma(k,q))$ for $\ell=3,4$ in terms
of hypergeometric sums, they also gave more explicit formulas for $k=2,3,4$.

In the case of $G_{R}(k)$ when $R$ is not a finite field, recently Bhowmik and
Barman studied the number of cliques for the local ring
$R=\mathbb{Z}_{p^{\alpha}}$ with $k=2$ (see [4]). For $R$ non-local, Das
studied the number of cliques for $R=\mathbb{Z}_{pq}$ with $k=2$ and $p,q$
primes, this formula was recently generalized for $R=\mathbb{Z}_{n}$ for $n$
odd in [5].

### Outline and main results

In what follows let $R$ be a finite commutative ring with identity and let
$k\in\mathbb{N}$ be coprime with $|R|$. We now give a brief account of the
main results in the paper.

In Section 2, we recall some facts about $t$-balanced blow-up operations and
show a general reduction formula for $\mathcal{K}_{\ell}(G^{(m)})$ in terms of
$\mathcal{K}_{\ell}(G)$. Thus, we recall the structure of the graph $G_{R}(k)$
for $R$ a local ring with unique maximal ideal $\mathfrak{m}$. In this case,
we have that $G_{R}(k)=G_{R/\mathfrak{m}}(k)^{(m)}$ where $m=|\mathfrak{m}|$
and so, by using the formula obtained previously, we show that we can compute
$\mathcal{K}_{\ell}(G_{R}(k))$ in terms of
$\mathcal{K}_{\ell}(G_{R/\mathfrak{m}}(k))$ and $m$.

In Section 3, we study the number of complete subgraphs of size $3$
(triangles) of $G_{R}(k)$ for $k=2,3,4$. We also show that in the case $R$ a
finite field, we obtain a derived property in field extensions for the number
of cliques, more precisely for $k=3$ and $4$ we show that we can derive the
values of $\mathcal{K}_{3}(\Gamma(k,q^{\ell}))$ from the value of
$\mathcal{K}_{3}(\Gamma(k,q))$, under some hypothesis.

Finally, in section 4 we find a close formula for the number of clique of size
$4$ for $G_{R}(2)$. In the same way as in $3$-cliques, we obtain a derived
property in field extensions for the number of $4$-cliques.

##  2\. Balanced blow-ups and cliques in $G_{R}(k)$

#### Balanced blow-ups and cliques

For any graph $G$ and $m\in\mathbb{N}$, the (balanced) blow-up of order $m$ of
$G$, denoted $G^{(m)}$, is the graph obtained by replacing each vertex $x$ of
$G$ by a set $V_{x}$ of $m$ independent vertices and every edge $\\{x,y\\}$ of
$G$ by a complete bipartite graph $K_{m,m}$ with parts $V_{x}$ and $V_{y}$ (of
course $G^{(1)}=G$). Notice that we have the natural isomorphism

(2.1) $G\otimes\mathring{K}_{m}\simeq G^{(m)},$

where $\mathring{\Gamma}$ denotes a graph $\Gamma$ with a loop added at each
vertex.

######  Proposition 2.1.

Let $G$ be a simple undirected graph and let $m,\ell\in\mathbb{N}$. Then,

$\mathcal{K}_{\ell}(G^{(m)})=\mathcal{K}_{\ell}(G)\cdot m^{\ell}.$

###### Proof.

Notice that any clique of size $\ell$ of $G^{(m)}$ induces a clique of the
same size in $G$. Indeed the vertices of this clique in $G^{(m)}$ must belong
to different independent sets of the blow-up, since if two of them belong to
the same independent set, so they are not neighbors. Conversely, given a
clique $K_{\ell}$ in $G$, by blowing up of its vertices we can obtain
$|m|^{\ell}$ distinct cliques in $G^{(m)}$. The above argument shows that all
of the cliques in $G^{(m)}$ can be obtained in this way. Hence, by the so
called multiplication principle of combinatorics we have that

$\mathcal{K}_{\ell}(G^{(m)})=\mathcal{K}_{\ell}(G)\cdot m^{\ell},$

as asserted. ∎

######  Example 2.2.

For $\ell,m,n\in\mathbb{N}$ we have that

$\mathcal{K}_{\ell}(K_{n}^{(m)})=\tbinom{n}{\ell}m^{\ell}.$

Indeed, by taking into account that any choice of $\ell$ vertices in $K_{n}$
determines a clique in $K_{n}$ and all of the cliques in $K_{n}$ are
determined uniquely in this way, we have that
$\mathcal{K}_{\ell}(K_{n})=\binom{n}{\ell}$. The assertion follows immediately
from the above proposition.

As a consequence of the previous proposition we obtain the following.

######  Corollary 2.3.

Let $G$ be a simple undirected graph. Then, $\omega(G^{(m)})=\omega(G)$ for
any $m\in\mathbb{N}$.

###### Proof.

By Proposition 2.1 we have that $\mathcal{K}_{\ell}(G^{(m)})=0$ if and only if
$\mathcal{K}_{\ell}(G)=0$. The corollary follows directly from (1.3). ∎

#### The structure of $G_{R}(k)$ and the number $\mathcal{K}_{\ell}(G_{R}(k))$
for $R$ local

We recall some structural properties of the graphs $G_{R}(k)$ defined in (1.1)
for $R$ a finite commutative local ring $(R,\mathfrak{m})$ with identity,
where $k$ is coprime with $|R|$.

######  Theorem 2.4 ([20]).

Let $(R,\mathfrak{m})$ be a finite commutative local ring with
$m=|\mathfrak{m}|$ and residue field $R/\mathfrak{m}\simeq\mathbb{F}_{q}$. If
$k\in\mathbb{N}$ satisfies $(k,|R|)=1$, then

(2.2) $G_{R}(k)\simeq{\Gamma(k,q)}^{(m)}\simeq
G_{\mathbb{F}_{q}}(k)\otimes\mathring{K}_{m},$

where ${\Gamma(k,q)}^{(m)}$ denotes the balanced blow-up of order $m$ of
$\Gamma(k,q)$, whose independent sets are all the cosets of $\mathfrak{m}$ in
$R$, and $\mathring{K}_{m}$ is the complete graph of $m$ vertices with a loop
added at every vertex. In particular, $G_{R}(k)$ is
$\frac{m(q-1)}{k}$-regular.

######  Remark 2.5.

Recently, Liu and Zhou [14] defined and studied the quadratic unitary Cayley
graphs $\mathcal{G}_{R}=Cay(R,T_{R})$, where $T_{R}=Q_{R}\cup(-Q_{R})$ and
$Q_{R}=\\{x^{2}:x\in R^{*}\\}$ with $R$ a finite commutative ring with
identity. Under the same conditions of the above theorem, they obtained the
same decomposition, with a different technique, by using group theory. In its
case they do not show that the independent sets of the blow-up are all the
cosets of $\mathfrak{m}$ in $R$ (see Theorems 2.3 and 2.5 in [14]). The same
decomposition was shown by de Beaudrap [3] in the case $R=\mathbb{Z}_{n}$ and
$k=2$.

Recall that an integer $n$ is a primitive divisor of $p^{r}-1$ if $n\mid
p^{r}-1$ and $n\nmid p^{a}-1$ for all $1\leq a<r$. For simplicity, as in our
previous works [18] we denote this fact by

(2.3) $n\dagger p^{r}-1.$

Also, it is well-known that

(2.4) $\Gamma(k,q)\text{ is connected}\quad\Leftrightarrow\quad n\dagger q-1,$

where $n$ is the regularity degree of $\Gamma(k,q)$, that is

$n=\tfrac{q-1}{k^{\prime}}\quad\text{ where }\quad k^{\prime}=(k,q-1).$

######  Corollary 2.6 ([20]).

Let $(R,\mathfrak{m})$ be a finite commutative local ring with
$m=|\mathfrak{m}|$ and residue field $R/\mathfrak{m}\simeq\mathbb{F}_{q}$. Let
$k\in\mathbb{N}$ such that $(k,|R|)=1$. Then,

  1. $(a)$

$-1\in U_{R}(k)$ if and only if $-1\in U_{R/\mathfrak{m},k}$. In particular,
$-1\in U_{R}(k)$ if and only if $q$ is even or else if $q$ odd and
$(k,q-1)\mid\frac{q-1}{2}$.

  2. $(b)$

$G_{R}(k)$ is undirected if and only if $G_{R/\mathfrak{m}}(k)$ is undirected.

  3. $(c)$

$G_{R}(k)$ is connected if and only if $\frac{q-1}{(k,q-1)}\dagger q-1$.

######  Remark 2.7.

Items ($a$) and ($b$) of the above corollary, imply that if $(R,\mathfrak{m})$
is a finite local ring with $|R/\mathfrak{m}|=q$, then

$G_{R}(k)\text{ is undirected}\quad\Leftrightarrow\quad\text{ $q$ even or else
$(k,q-1)\mid\tfrac{q-1}{2}$ with $q$ odd}.$

Hence, this arythmetic condition will appear many times in the rest of the
work.

As a direct consequence of Proposition 2.1 and Theorem 2.4 we obtain the
following result.

######  Theorem 2.8.

Let $(R,\mathfrak{m})$ be a finite commutative local ring with
$m=|\mathfrak{m}|$ and residue field $R/\mathfrak{m}\simeq\mathbb{F}_{q}$. Let
$k\in\mathbb{N}$ such that $(k,q-1)\mid\frac{q-1}{2}$. If $(k,q)=1$, then

(2.5) $\mathcal{K}_{\ell}(G_{R}(k))=\mathcal{K}_{\ell}(\Gamma(k,q))\cdot
m^{\ell}\quad\text{for all $\ell\in\mathbb{N}$}.$

###### Proof.

The hypothesis assure that $G_{\mathbb{F}_{q}}(k)$ is an undirected graph, and
by the above corollary $G_{R}(k)$ is undirected, as well. On the other hand,
since $(k,q)=1$ then by Theorem 2.4 we have that

$G_{R}(k)=\Gamma(k,q)^{(m)}$

where $m$ is the size of $\mathfrak{m}$. Hence, the assertion it follows
directly from Proposition 2.1. ∎

By taking into account the corollary 2.3, Theorem 2.4 implies the following
consequence.

######  Proposition 2.9.

Let $(R,\mathfrak{m})$ be a finite commutative local ring with
$m=|\mathfrak{m}|$ and residue field $R/\mathfrak{m}\simeq\mathbb{F}_{q}$. Let
$k\in\mathbb{N}$ such that $(k,q-1)\mid\frac{q-1}{2}$. If $(k,q)=1$, then

$\omega(G_{R}(k))=\omega(\Gamma(k,q)).$

##  3\.  The number $\mathcal{K}_{3}(G_{R}(k))$ for $k$ small.

In this section, we exploit some known values of
$\mathcal{K}_{\ell}(\Gamma(k,q))$ in order to obtain formulas for $R$ general
local rings. In [8], as we mentioned in the preliminaries the authors obtained
a general formula for $\mathcal{K}_{\ell}(\Gamma(k,q))$ which is complicated
to deal with, but for some cases ($k$ and $\ell$ small) these formulas become
more tractable.

We begin with the cases $\ell=3$ and $k=2,3,4$.

######  Theorem 3.1.

Let $(R,\mathfrak{m})$ be a finite commutative local ring with
$m=|\mathfrak{m}|=q^{\beta}$ and residue field
$R/\mathfrak{m}\simeq\mathbb{F}_{q}$. Let $k\in\mathbb{N}$ such that
$k\mid\frac{q-1}{2}$ if $q$ is odd or else $k\mid q-1$ for $q$ even. Then, we
have the following cases:

  1. ($a$)

($k=2$)If $q\equiv 1\pmod{4}$ then

$\mathcal{K}_{3}(G_{R}(2))=\frac{q^{3\beta+1}(q-1)(q-5)}{48}$

  2. ($b$)

($k=3$) If $q=p^{r}$ for a prime $p$, such that $3\mid q-1$ if $q$ is even, or
else $6\mid q-1$ if $q$ is odd. When $p\equiv 1\pmod{3}$, write
$4q=c^{2}+27d^{2}$ for $c,d\in\mathbb{Z}$ such that $c\equiv 1\pmod{3}$ and
$p\nmid c$. When $p\equiv 2\pmod{3}$, let $c=-2(-p)^{\frac{r}{2}}$. Then

$\mathcal{K}_{3}(G_{R}(3))=\frac{q^{3\beta+1}(q-1)(q+c-8)}{162}.$

  3. ($c$)

($k=4$) Let $q=p^{r}\equiv 1\pmod{8}$ for a prime $p$. Write $q=e^{2}+4f^{2}$
for $e,f\in\mathbb{Z}$, such that $e\equiv 1\pmod{4}$, and $p\nmid e$ when
$p\equiv 1\pmod{4}$. Then

$\mathcal{K}_{3}(G_{R}(4))=\frac{q^{3\beta+1}(q-1)(q-6e-11)}{2^{7}\cdot 3}.$

###### Proof.

All of the assertion follows directly from Theorem 2.8 and Corollaries 2.10,
2.11 and 2.12 from [8]. ∎

######  Remark 3.2.

  1. ($a$)

In [4], the authors found the same value in the item $(a)$, only when
$R=\mathbb{Z}_{p^{\alpha}}$, by using some calculations in terms of Jacobi
sums and Dirichlet characters. Notice that in this case its maximal ideal has
size $p^{\alpha-1}$ and the residue field is $\mathbb{F}_{p}$, so $q=p$ and
$\beta=\alpha-1$, in terms of the notation of the above proposition. Hence,
for $p\equiv 1\pmod{4}$ we have that

$\mathcal{K}_{3}(G_{\mathbb{Z}_{p^{\alpha}}}(2))=\frac{p^{3\alpha-2}(p-1)(p-5)}{48}.$

  2. ($b$)

Notice that the hypothesis that the author assume in Corollary 2.12 of [8] was
$q=e^{2}+f^{2}$ instead of $q=e^{2}+4f^{2}$, both hypothesis are the same,
since if we assume that $q=e^{2}+f^{2}$ with $q\equiv 1\pmod{8}$ and $e\equiv
1\pmod{4}$, then necessarily $f\equiv 0\pmod{4}$, that is $f=2f^{\prime}$ and
so $q=e^{2}+4f^{\prime 2}$.

#### Derived values of $\mathcal{K}_{3}(\Gamma(k,q))$ in field extensions for
$k=3,4$.

We can say more things about the cases $k=3,4$ when $R=\mathbb{F}_{q}$ is a
finite field. In [19] Podestá and Videla studied the energy and spectra of
$\Gamma(3,q)$ and $\Gamma(4,q)$, in this case somo constants appear, very
similar to the costants $c$ and $e$ present in the formulas for
$\mathcal{K}_{3}(G_{\mathbb{F}_{q}}(4))$. By using complex numbers, they
proved that the costants can be obtained recursively when $q$ grows (in some
particular way). This allow them to proved that the spectrum can be obtained
recursively. In this case, we can do the same for the number of cliques, as
the following results assert.

######  Theorem 3.3.

Let $p$ be a prime with $p\equiv 1\pmod{3}$. If there is a minimal
$t\in\mathbb{N}$ such that

(3.1) $p^{t}=X^{2}+27Y^{2}$

has integral solutions $x,y\in\mathbb{Z}$ with $(x,p)=1$, then
$\mathcal{K}_{3}(\Gamma(3,p^{t\ell+s}))$, with $\ell\geq 1$ and $0\leq s<t$,
is determined by the numbers $\mathcal{K}_{3}(\Gamma(3,p^{t}))$ and
$\mathcal{K}_{3}(\Gamma(3,p^{s}))$.

###### Proof.

Let $t$ be minimal in $\mathbb{N}$ such that (3.1) has an integral solution
$x,y$ with $(x,p)=1$. Notice that if $(x,y)$ is a solution of (3.1) then
$(x,-y)$ and $(-x,\pm y)$ are also solutions. Also, from (3.1) we have that
$x^{2}\equiv 1\pmod{3}$ since $p\equiv 1\pmod{3}$ and hence $x\equiv\pm
1\pmod{3}$. Thus, we will choose one solution $(x_{0},y_{0})$, with
$x_{0}\in\\{\pm x\\}$ and $y_{0}\in\\{\pm y\\}$, such that $x_{0}\equiv
1\pmod{3}$.

Considering the complex number

(3.2) $z_{x,y}:=x+3\sqrt{3}iy,$

we have that $\|z_{x,y}\|^{2}=x^{2}+27y^{2}=p^{t}$ and hence

(3.3) $p^{t\ell}=\|z_{x,y}\|^{2\ell}=\|z_{x,y}^{\ell}\|^{2}$

for any $\ell\in\mathbb{N}$. Now, we will express $z_{x,y}^{\ell}$ in the form
given in (3.2). For any $\ell\in\mathbb{N}$ put

$z_{x,y}^{\ell}:=z_{x_{\ell-1},y_{\ell-1}}=x_{\ell-1}+3\sqrt{3}iy_{\ell-1}$

where $z_{x,y}^{1}=z_{x,y}$ and $x_{0}=x$, $y_{0}=y$. For instance,
$x_{1}+3\sqrt{3}iy_{1}=z_{x,y}^{2}=(x^{2}-27y^{2})+3\sqrt{3}i(2xy)$ so
$x_{1}=x^{2}-27y^{2}$ and $y_{1}=2xy$. By the relation
$z_{x,y}^{\ell+1}=z_{x,y}z_{x,y}^{\ell}$, one sees that the sequence
$\\{(x_{\ell},y_{\ell})\\}_{\ell\in\mathbb{N}_{0}}$ is thus recursively
defined as follows: let $x_{0}=x$, $y_{0}=y$ and for any $\ell>0$ take

(3.4) $x_{\ell}=x_{0}x_{\ell-1}-27y_{0}y_{\ell-1}\qquad\text{and}\qquad
y_{\ell}=x_{0}y_{\ell-1}+x_{\ell-1}y_{0}.$

Now, in the proof of Theorem 3.1 of [19] the authors showed the following
claim:

Claim 1: $x_{\ell}\equiv 1\pmod{3}$ and $(x_{\ell},p)=1$ for all
$\ell\in\mathbb{N}_{0}$.

Now assume that $s\in\\{1,\ldots,t-1\\}$ (the case $s=0$ was treated before),
and let $c_{0,s},d_{0,s}\in\mathbb{Z}$ with $c_{0,s}\equiv 1\pmod{3}$ and
$(c_{0,s},p)=1$ such that

$4p^{s}=c_{0,s}^{2}+27d_{0,s}^{2}=\|z_{c_{0,s},d_{0,s}}\|^{2}$

with $z_{c_{0,s},d_{0,s}}=c_{0,s}+3\sqrt{3}id_{0,s}$. Hence, we have that

$4p^{t\ell+s}=\|z_{c_{0,s},d_{0,s}}\|^{2}\|z_{x_{\ell-1},y_{\ell-1}}\|^{2}=\|z_{c_{0,s},d_{0,s}}z_{x_{\ell-1},y_{\ell-1}}\|^{2}=\|z_{c_{\ell,s},d_{\ell,s}}\|^{2}$

where $\\{(c_{\ell,s},d_{\ell,s})\\}_{\ell\in\mathbb{N}_{0}}$ also satisfies
the recursions

(3.5) $c_{\ell,s}=c_{0,s}x_{\ell-1}-27d_{0,s}y_{\ell-1}\qquad\text{and}\qquad
d_{\ell,s}=c_{0,s}y_{\ell-1}+d_{0,s}x_{\ell-1},$

with $x_{\ell},y_{\ell}$ recursively defined as in (3.4). The following claim
is also proved in Theorem 3.1 of [19]

Claim 2: $c_{\ell,s}\equiv 1\pmod{3}$ and $(c_{\ell,s},p)=1$ for all
$\ell\in\mathbb{N}_{0}$.

In order to prove that the $\mathcal{K}_{3}(\Gamma(3,p^{t\ell+s}))$ is
determined by $\mathcal{K}_{3}(\Gamma(3,p^{s}))$ and
$\mathcal{K}_{3}(\Gamma(3,p^{t}))$, it is enough to put $c_{\ell,s}$ in terms
of $c_{0,s}$ and $x_{0}$. In [19] it is shown that $c_{\ell,s}$’s satisfy the
following recursion

(3.6) $c_{\ell+1,s}=2x_{0}c_{\ell,s}-p^{t}c_{\ell-1,s}.$

By solving this two terms linear recurrence, we obtain that

(3.7)
$c_{\ell,s}=\tfrac{1}{2}(c_{0,s}+3\sqrt{3}d_{0,s}i)(x_{0}+3\sqrt{3}y_{0}i)^{\ell}+\tfrac{1}{2}(c_{0,s}-3\sqrt{3}d_{0,s}i)(x_{0}-3\sqrt{3}y_{0}i)^{\ell},$

In this way, for every $\ell\in\mathbb{N}$, $c_{\ell,s}$ can be put in terms
of $c_{0,s},d_{0,s}$ and $x_{0},y_{0}$ only, to finish the proof notice that
$d_{0,s}$ can be put in terms of $c_{0,s}$ and $y_{0}$ can be put in terms of
$x_{0}$, as we wanted to show. ∎

Recall that an integer $a$ is a cubic residue modulo a prime $p$ if $a\equiv
x^{3}\pmod{p}$ for some integer $x$. By Euler’s criterion, $a$ is a cubic
residue mod $p$, with $(a,p)=1$, if and only if

(3.8) $a^{\frac{p-1}{d}}\equiv 1\pmod{p}$

where $d=(3,p-1)$. We have the following direct consequence of Theorem 3.3.

######  Theorem 3.4.

Let $p$ be a prime with $p\equiv 1\pmod{3}$. If $2$ is a cubic residue modulo
$p$, then the number $\mathcal{K}_{3}(\Gamma(3,p))$ determines the numbers
$\mathcal{K}_{3}(\Gamma(3,p^{\ell}))$ for every $\ell\in\mathbb{N}$. In this
case, $\mathcal{K}_{3}(\Gamma(3,p^{\ell}))$ is given by

(3.9)
$\mathcal{K}_{3}(\Gamma(3,p^{\ell}))=\frac{p^{\ell}(p^{\ell}-1)(p^{\ell}+c_{\ell}-8)}{162}.$

where $c_{\ell}$ are defined by

$c_{\ell}=-(x_{0}+3\sqrt{3}y_{0}i)^{\ell}-(x_{0}-3\sqrt{3}y_{0}i)^{\ell},$

where $x_{0}$ and $y_{0}$ are the solutions of $p=X^{2}+27Y^{2}$ with
$(x_{0},p)=1$ and $x_{0}\equiv 1\pmod{3}$.

###### Proof.

A classic result in number theory, conjectured by Euler and first proved by
Gauss using cubic reciprocity, asserts that (see for instance [6])

(3.10) $p=x^{2}+27y^{2}\quad\text{for some
$x,y\in\mathbb{Z}$}\qquad\Leftrightarrow\qquad\begin{cases}p\equiv
1\pmod{3}\quad\text{ and,}\\\ 2\text{ is a cubic residue modulo
$p$}.\end{cases}$

By hypothesis we have that $p\equiv 1\pmod{3}$ and $2$ is a cubic residue
modulo $p$, so there exist $x,y\in\mathbb{Z}$ such that $p=x^{2}+27y^{2}$.
Moreover, since either $x$ or $-x$ is congruent to $1$ mod $p$, we choose the
solution $(z,y)$, where $z\in\\{\pm x\\}$ with $z\equiv 1\pmod{3}$. Thus, the
assertion follows directly from Theorem 3.3 with $t=1$ and $s=0$. ∎

######  Example 3.5.

Let $p=31$. We know that $2$ is a cubic residue modulo $31$ and in this case
we have $31=2^{2}+27\cdot 1^{2}$. We take the solutions $x_{0}=-2$ and
$y_{0}=1$ of $31=X^{2}+37Y^{2}$. By Theorem 3.4, we have that
$\mathcal{K}_{3}(\Gamma(3,31))$ determines
$\mathcal{K}_{3}(\Gamma(3,31^{\ell}))$ for every $\ell$ and

$\mathcal{K}_{3}(\Gamma(3,p^{\ell}))=\frac{p^{\ell}(p^{\ell}-1)(p^{\ell}+c_{\ell}-8)}{162}.$

where $c_{\ell}$ satisfies

$c_{\ell}=-(-2+3\sqrt{3}i)^{\ell}-(-2-3\sqrt{3}i)^{\ell},$

In Table 1 we give the values of $\Gamma(3,31^{\ell})$ for the first five
values of $\ell$.

Table 1. First values of $c_{\ell}$ and $\mathcal{K}_{3}(\Gamma(3,31^{\ell}))$ $\ell$ | $c_{\ell}$ | Values of $\mathcal{K}_{3}(\Gamma(3,31^{\ell}))$
---|---|---
1 | $4$ | $155$
2 | $46$ | $5689120$
3 | $-308$ | $161470943875$
4 | $-194$ | $4861047204287040$
5 | $10324$ | $144899484304503423275$

$\lozenge$

######  Theorem 3.6.

If $p$ is a prime with $q=p^{r}\equiv 1\pmod{8}$ and $p\equiv 1\pmod{4}$, then
the number of cliques $\mathcal{K}_{3}(\Gamma(4,q^{\ell}))$ is determined by
$\mathcal{K}_{3}(\Gamma(4,q))$ for every $\ell\in\mathbb{N}$. Moreover,
$\mathcal{K}_{3}(\Gamma(4,q^{\ell}))$ is given by

$\mathcal{K}_{3}(\Gamma(4,q^{\ell}))=\frac{q^{\ell}(q^{\ell}-1)(q^{\ell}-6e_{\ell}-11)}{2^{7}\cdot
3}.$

where the number $e_{\ell}$ is given by

(3.11)
$e_{\ell}=\tfrac{1}{2}(e_{1}+2f_{1}i)^{\ell}+\tfrac{1}{2}(e_{1}-2f_{1}i)^{\ell}=\mathit{Re}(e_{1}+2f_{1}i)^{\ell},$

where $e_{1}$ and $f_{1}$ are integral solutions of $q=X^{2}+4Y^{2}$ with
$e_{1}\equiv 1\pmod{4}$ and $(e_{1},p)=1$.

###### Proof.

It is well known that the equation $q=X^{2}+4Y^{2}$ with $p\equiv 1\pmod{4}$
always has a solution $(x,y)$ satisfying $(x,p)=1$. In particular, since
$q\equiv 1\pmod{8}$ then $q\equiv 1\pmod{4}$ as well. Let $e_{1},f_{1}$ be the
solution of the above equation with $e_{1}\equiv 1\pmod{4}$ and $(e_{1},p)=1$.
Notice that if we take $z_{x,y}=x+iy$, then $p=\|z_{e_{1},f_{1}}\|^{2}$, so we
have that

$q^{\ell}=\|z_{e_{1},f_{1}}^{\ell}\|^{2}.$

As in the proof of Theorem 3.3, we can put
$z_{e_{1},f_{1}}^{\ell}=:z_{e_{\ell},f_{\ell}}$, where $e_{\ell},f_{\ell}$ are
defined recursively as follows

(3.12) $e_{\ell+1}=e_{1}e_{\ell}-4f_{1}f_{\ell}\qquad\text{and}\qquad
f_{\ell+1}=e_{1}f_{\ell}+f_{1}e_{\ell}.$

Both sequences $\\{e_{\ell}\\}_{\ell\in\mathbb{N}_{0}}$ and
$\\{f_{\ell}\\}_{\ell\in\mathbb{N}_{0}}$ also satisfy the recursion

(3.13) $r_{\ell+1}=2e_{1}r_{\ell}-q\cdot r_{\ell-1}.$

It can be shown that

$f_{\ell+1}=f_{1}\Big{(}\sum_{i=1}^{\ell}e_{i}e_{1}^{\ell-i}+e_{1}^{\ell}\Big{)}\quad\text{and}\quad
e_{\ell}=\tfrac{1}{f_{1}}(f_{\ell+1}-e_{1}f_{\ell})=\sum_{i=1}^{\ell}e_{i}e_{1}^{\ell-i}-e_{1}\sum_{i=1}^{\ell-1}e_{i}e_{1}^{\ell-1-i}$

so we have that

(3.14)
$e_{\ell+1}=e_{1}\sum_{i=1}^{\ell}e_{i}e_{1}^{\ell-i}-q\sum_{i=1}^{\ell-1}e_{i}e_{1}^{\ell-1-i}-4f_{1}^{2}e_{1}^{\ell-1}.$

As in proof of Theorem 3.1 of [19], we can show that $(e_{\ell},p)=1$ and
$e_{\ell}\equiv 1\pmod{4}$. Indeed, notice that (3.12) implies that
$e_{\ell+1}\equiv e_{\ell}\pmod{4}$ and by hypothesis $e_{1}\equiv 1\pmod{4}$
and so $e_{\ell}\equiv 1\pmod{4}$ for all $\ell\geq 1$.

On the other hand, we have that $(e_{1},p)=1$ by hypothesis. Notice that
$e_{2}=e_{1}^{2}-4f_{1}^{2}$ and $f_{2}=2e_{1}f_{1}$. By taking into account
that $q=e_{1}^{2}+4f_{1}^{2}$, we obtain that $e_{2}=2e_{1}^{2}-q\equiv
2e_{1}^{2}\pmod{p}$. Since $p>4$ is prime and $(e_{1},p)=1$, we obtain that
$e_{2}\not\equiv 0\pmod{p}$ and thus $(e_{2},p)=1$. We now prove that
$(e_{\ell},p)=1$ for any $\ell\geq 3$ by contradiction.

Suppose that the second statement of the claim is false, so there exists a
minimum $L>2$ such that $p\mid e_{L}$, that is $e_{L}\equiv 0\pmod{p}$. By
(3.14), we obtain that

$e_{1}\sum_{i=1}^{L-1}e_{i}e_{1}^{L-1-i}-4f_{1}^{2}e_{1}^{L-2}\equiv
e_{L}\equiv 0\pmod{p},$

and using that $4f_{1}^{2}=q-e_{1}^{2}$ we get

$e_{1}\sum_{i=1}^{L-1}e_{i}e_{1}^{L-1-i}+e_{1}^{L}=e_{1}\big{(}e_{1}^{L-1}+\sum_{i=1}^{L-1}e_{i}e_{1}^{L-1-i}\big{)}\equiv
0\pmod{p}.$

Since $(e_{1},p)=1$, we have that

(3.15) $e_{1}^{L-1}+\sum_{i=1}^{L-1}e_{i}e_{1}^{L-1-i}\equiv 0\pmod{p}.$

Notice that

$\sum_{i=1}^{L-1}e_{i}e_{1}^{L-1-i}=e_{L-1}+\sum_{i=1}^{L-2}e_{i}e_{1}^{L-1-i}.$

By applying (3.14) with $\ell=L-1$ we arrive at

$e_{L-1}\equiv
e_{1}\sum_{i=1}^{L-2}e_{i}e_{1}^{L-2-i}-4f_{1}^{2}e_{1}^{L-3}\equiv\sum_{i=1}^{L-2}e_{i}e_{1}^{L-1-i}+e_{1}^{L-1}\pmod{p}$

where we again used that $4f_{1}^{2}=q-e_{1}^{2}$. Thus, we have that

$2e_{L-1}\equiv e_{L-1}+\sum_{i=1}^{L-2}e_{i}e_{1}^{L-1-i}+e_{1}^{L-1}\equiv
e_{1}^{L-1}+\sum_{i=1}^{L-1}e_{i}e_{1}^{L-1-i}\equiv 0\pmod{p},$

by (3.15). Hence $e_{L-1}\equiv 0\pmod{p}$ since $(2,p)=1$, which contradicts
the minimality of $L$. Therefore $(e_{\ell},p)=1$ for all $\ell\in\mathbb{N}$.
This proves the claim.

In order to prove that $\mathcal{K}_{3}(\Gamma(4,q^{\ell}))$ is determined by
$\mathcal{K}_{3}(\Gamma(4,q))$, notice that if $q\equiv 1\pmod{8}$ then
$q^{\ell}\equiv 1\pmod{8}$ as well, so by item ($c$) of Proposition 3.1, it is
enough to put every $e_{\ell}$ in terms of $e_{1}$ and $f_{1}$ only, since the
value. By solving the linear recurrence (3.13) and by recalling that
$e_{2}=e_{1}^{2}-4f_{1}^{2}$ and $f_{2}=2e_{1}f_{1}$, we obtain that
$e_{\ell}$ are as given in (3.11). Therefore, the value of
$\mathcal{K}_{3}(\Gamma(4,q^{\ell}))$ is determined by
$\mathcal{K}_{3}(\Gamma(4,q))$, as desired. ∎

######  Example 3.7.

Let $p=17$. Since $17=1^{2}+4\cdot 2^{2}$, we take $e_{1}=1$ and $f_{1}=2$.
The number of cliques $\mathcal{K}_{3}(\Gamma(4,5^{\ell}))$ is given for any
$\ell\in\mathbb{N}$ by

$\mathcal{K}_{3}(\Gamma(4,17^{\ell}))=\frac{17^{\ell}(17^{\ell}-1)(17^{\ell}-6e_{\ell}-11)}{2^{7}\cdot
3}$

with

$e_{\ell}=\tfrac{1}{2}(1+4i)^{\ell}+\tfrac{1}{2}(1-4i)^{\ell}=\mathit{Re}(1+4i)^{\ell}$

In Table 2 we give the values of $\mathcal{K}_{3}(\Gamma(4,5^{4\ell}))$ for
the first five values of $\ell$

Table 2. Values of $\mathcal{K}_{3}(\Gamma(4,17^{\ell}))$ $\ell$ | $e_{\ell}$ | Values of $\mathcal{K}_{3}(\Gamma(4,17^{\ell}))$
---|---|---
1 | $1$ | $0$
2 | $-15$ | $79764$
3 | $-47$ | $325790856$
4 | $161$ | $1499479239720$
5 | $761$ | $7430192286281890$

$\lozenge$

##  4\.  The number $\mathcal{K}_{4}(G_{R}(k))$ for $k=2,3,4$

In this section we study the number $\mathcal{K}_{4}(G_{R}(k))$, for
$(R,\mathfrak{m})$ a local ring for $k=2,3,4$, by showing that we can always
obtain this value in terms of $\mathcal{K}_{4}(G_{R/\mathfrak{m}}(k))$ for
$k=2,3,4$. In the case that $R=\mathbb{F}_{p^{\ell}}$, we show that we can
alwas obtain the value of $\mathcal{K}_{4}(\Gamma(2,p^{\ell}))$ recursively
from $\mathcal{K}_{4}(\Gamma(2,p))$ when $p\equiv 1\pmod{4}$.

Given $\chi,\psi$ multiplicative characters of $\mathbb{F}_{q}$ with extension
$\chi(0)=\psi(0)=0$, the usual Jacobi sums is defined by
$J(\chi,\psi)=\sum_{a\in\mathbb{F}_{q}}\chi(a)\psi(1-a)$, we have also the
symbol $\binom{\psi}{\chi}=\frac{\psi(-1)}{q}J(\chi,\overline{\psi})$. For a
multiplicative character $\chi_{k}$ of $\mathbb{F}_{q}$ of order $k$ with
$q\equiv 1\pmod{k}$ and given $\vec{t}=(t_{1},t_{2},t_{3},t_{4}.t_{5})$, the
hypergeometric functions

${}_{3}F_{2}\left(\vec{t};1\right)_{q,k}={}_{3}F_{2}\left(\begin{matrix}\chi_{k}^{t_{1}},&&\chi_{k}^{t_{2}},&&\chi_{k}^{t_{3}}\\\\[3.00003pt]
&&\chi_{k}^{t_{4}},&&\chi_{k}^{t_{5}}&\end{matrix};1\right)_{q}=\frac{q}{q-1}\sum_{\chi}\tbinom{\chi_{k}^{t_{1}}\chi}{\chi}\tbinom{\chi_{k}^{t_{2}}\chi}{\chi_{k}^{t_{4}}\chi}\tbinom{\chi_{k}^{t_{3}}\chi}{\chi_{k}^{t_{5}}\chi}\chi(1),$

where the sum is taken over all of the multiplicative characters $\chi$ of
$\mathbb{F}_{q}$

######  Proposition 4.1.

Let $(R,\mathfrak{m})$ be a finite commutative local ring with
$m=|\mathfrak{m}|=q^{\beta}$ and residue field
$R/\mathfrak{m}\simeq\mathbb{F}_{q}$. Let $k\in\mathbb{N}$ such that
$k\mid\frac{q-1}{2}$ if $q$ is odd or else $k\mid q-1$ for $q$ even. Then, we
have the following cases:

  1. ($a$)

$(k=2)$ Let $q=p^{r}\equiv 1\pmod{4}$ for a prime $p$. Write $q=x^{2}+4y^{2}$
for integers $x$ and $y$, such that $p\nmid x$ when $p\equiv 1\pmod{4}$. Then

$\mathcal{K}_{4}(G_{R}(2))=\frac{q^{4\beta+1}(q-1)((q-9)^{2}-16y^{2})}{2^{9}\cdot
3}.$

  2. ($b$)

($k=3$) If $q=p^{r}$ for a prime $p$, such that $3\mid q-1$ if $q$ is even, or
else $6\mid q-1$ if $q$ is odd. When $p\equiv 1\pmod{3}$, write
$4q=c^{2}+27d^{2}$ for $c,d\in\mathbb{Z}$ such that $c\equiv 1\pmod{3}$ and
$p\nmid c$. When $p\equiv 2\pmod{3}$, let $c=-2(-p)^{\frac{r}{2}}$. If
$\chi_{3}$ is a multiplicative character of $\mathbb{F}_{q}$ of order $3$ and
$\varepsilon$ is the trivial multiplicative character, then

$\mathcal{K}_{4}(G_{R}(3))=\tfrac{q^{4\beta+1}(q-1)}{2^{3}3^{7}}\big{[}q^{2}+5q(c-11)+10c^{2}-85c+316+12q^{2}{}_{3}F_{2}\left(\begin{matrix}\chi_{3},&&\chi_{3},&&\overline{\chi}_{3}\\\
&&\varepsilon,&&\varepsilon&\end{matrix};1\right)_{q}\big{]}.$

  3. ($c$)

($k=4$) Let $q=p^{r}\equiv 1\pmod{8}$ for a prime $p$. Write $q=e^{2}+4f^{2}$
for $e,f\in\mathbb{Z}$, such that $e\equiv 1\pmod{4}$, and $p\nmid e$ when
$p\equiv 1\pmod{4}$. Write $q=u^{2}+2v^{2}$ for integers $u$ and $v$, such
that $u\equiv 3\pmod{4}$, and $p\nmid u$ when $p\equiv 1,3\pmod{8}$. If
$\varphi$ and $\chi_{4}$ are multiplicative characters of $\mathbb{F}_{q}$ of
order $2$ and $4$, respectively and $\varepsilon$ is the trivial
multiplicative character, then

$\displaystyle\mathcal{K}_{4}(G_{R}(4))$
$\displaystyle=\frac{q^{4\beta+1}(q-1)}{2^{15}\cdot 3}$
$\displaystyle\cdot\Big{[}q^{2}-2q(15x+101)+304x^{2}+(930-40u)x+801+120u^{2}$
$\displaystyle+12q^{2}{}_{3}F_{2}\left(\begin{matrix}\chi_{4},&&\chi_{4},&&\overline{\chi_{4}}\\\
&&\varepsilon,&&\varepsilon&\end{matrix};1\right)_{q}+30q^{2}{}_{3}F_{2}\left(\begin{matrix}\chi_{4},&&\varphi,&&\varphi\\\
&&\varepsilon,&&\varepsilon&\end{matrix};1\right)_{q}\Big{]}$

###### Proof.

All of the assertions follows directly from Theorem 2.8 and Corollaries 2.3,
2.5 and 2.7 from [8]. ∎

######  Remark 4.2.

By taking $R=\mathbb{Z}_{p^{\alpha}}$ in item ($a$) of Proposition 4.1, we
have that $\beta=\alpha-1$ and $q=p$ prime, in this case we have that

(4.1)
$\mathcal{K}_{4}(G_{\mathbb{Z}_{p^{\alpha}}}(2))=\frac{p^{4\alpha-3}(p-1)((p-9)^{2}-16y^{2})}{2^{9}\cdot
3}.$

where $y$ is as in the hypothesis. On the other hand, in [4] the authors
showed that

$\mathcal{K}_{4}(G_{\mathbb{Z}_{p^{\alpha}}}(2))=\frac{p^{2\alpha-1}(p-1)\Big{(}p^{2\alpha-2}\big{(}(p-9)^{2}-2p\big{)}+J(\psi,\varphi)^{2}+\overline{J(\psi,\varphi)}^{2}\Big{)}}{2^{9}\cdot
3},$

where $J(\psi,\varphi)=\sum_{a\in\mathbb{Z}_{p^{\alpha}}}\psi(a)\varphi(1-a)$
is the Jacobi sum of $\psi$ and $\varphi$, with $\psi$ and $\varphi$ Dirichlet
characters modulo $p^{\alpha}$ of order $4$ and $2$ respectively. Thus, by the
above equalitties we can obtain that

$J(\psi,\varphi)^{2}+\overline{J(\psi,\varphi)}^{2}=2p^{2\alpha-2}(p-8y^{2}),$

This formula was found very recently in [5] from other identity.

As in theorems 3.3 and 3.6, we obtain the following

######  Theorem 4.3.

If $p$ is a prime with $p\equiv 1\pmod{4}$ then the number of cliques
$\mathcal{K}_{4}(\Gamma(2,p^{\ell}))$ is determined by
$\mathcal{K}_{4}(\Gamma(2,p))$ for every $\ell\in\mathbb{N}$. Moreover,
$\mathcal{K}_{4}(\Gamma(2,p^{\ell}))$ is given by

$\mathcal{K}_{4}(\Gamma(2,p^{\ell}))=\frac{p^{\ell}(p^{\ell}-1)((p^{\ell}-9)^{2}-16f_{\ell}^{2})}{2^{9}\cdot
3}.$

where the number $f_{\ell}$ is given by

(4.2)
$f_{\ell}=-\tfrac{i}{4}(e_{1}+2f_{1}i)^{\ell}+\tfrac{i}{4}(e_{1}-2f_{1}i)^{\ell}=\mathit{Im}\,(e_{1}+2f_{1}i)^{\ell},$

where $e_{1}$ and $f_{1}$ are integral solutions of $p=X^{2}+4Y^{2}$ with
$e_{1}\equiv 1\pmod{4}$ and $(e_{1},p)=1$.

###### Proof.

It is well known that the equation $p^{2}=X^{2}+4Y^{2}$ with $p\equiv
1\pmod{4}$ always has a solution $(x,y)$ satisfying $(x,p)=1$. Let
$e_{1},f_{1}$ be the solution of the above equation with $e_{1}\equiv
1\pmod{4}$ and $(e_{1},p)=1$. Notice that if we take $z_{x,y}=x+2iy$, then
$p=\|z_{e_{1},f_{1}}\|^{2}$, so we have that

$p^{\ell}=\|z_{e_{1},f_{1}}^{\ell}\|^{2}.$

As in the proof of Theorem 3.6, we can put
$z_{e_{1},f_{1}}^{\ell}=:z_{e_{\ell},f_{\ell}}$, where $e_{\ell},f_{\ell}$ are
defined recursively as follows

(4.3) $e_{\ell+1}=e_{1}e_{\ell}-4f_{1}f_{\ell}\qquad\text{and}\qquad
f_{\ell+1}=e_{1}f_{\ell}+f_{1}e_{\ell}.$

Both sequences $\\{e_{\ell}\\}_{\ell\in\mathbb{N}_{0}}$ and
$\\{f_{\ell}\\}_{\ell\in\mathbb{N}_{0}}$ also satisfy the recursion

(4.4) $r_{\ell+1}=2e_{1}r_{\ell}-p\cdot r_{\ell-1}.$

By the proof of Theorem 3.6, we have that $(e_{\ell},p)=1$ and $e_{\ell}\equiv
1\pmod{4}$.

In order to prove that $\mathcal{K}_{4}(\Gamma(2,p^{\ell}))$ is determined by
$\mathcal{K}_{4}(\Gamma(2,p))$, notice that if $p\equiv 1\pmod{4}$ then
$p^{\ell}\equiv 1\pmod{4}$ as well, so by Proposition 4.1, it is enough to put
every $f_{\ell}$ in terms of $e_{1}$ and $f_{1}$ only. By solving the linear
recurrence (3.13) and by recalling that $e_{2}=e_{1}^{2}-4f_{1}^{2}$ and
$f_{2}=2e_{1}f_{1}$, we obtain that $f_{\ell}$ are as given in (4.2).
Therefore, the value of $\mathcal{K}_{4}(\Gamma(2,p^{\ell}))$ is determined by
$\mathcal{K}_{4}(\Gamma(2,p))$, as asserted. ∎

######  Example 4.4.

Let $p=5$. Since $5=1^{2}+4\cdot 1^{2}$, we take $e_{1}=1$ and $f_{1}=1$. The
value of $\mathcal{K}_{4}(\Gamma(2,5^{\ell}))$ is given by

$\mathcal{K}_{4}(\Gamma(2,5^{\ell}))=\frac{5^{\ell}(5^{\ell}-1)((5^{\ell}-9)^{2}-16f_{\ell}^{2})}{2^{9}\cdot
3}.$

where $f_{\ell}$ is give by (3.11),

$f_{\ell}=-\tfrac{i}{4}(1+2i)^{\ell}+\tfrac{i}{4}(1-2i)^{\ell}=\mathit{Im}\,(1+2i)^{\ell}.$

In Table 3 we give the values of $\mathcal{K}_{4}(\Gamma(2,5^{\ell}))$ for the
first five values of $\ell$.

Table 3. Values of $\mathcal{K}_{4}(\Gamma(2,5^{\ell}))$ $\ell$ | $f_{\ell}$ | Values of $\mathcal{K}_{4}(\Gamma(2,5^{\ell}))$
---|---|---
1 | $1$ | $0$
2 | $2$ | $75$
3 | $1$ | $135625$
4 | $22$ | $283140000$
5 | $-19$ | $61674593750$

## References

  * [1] R. Akhtar, M. Boggess, T. Jackson-Henderson, I. Jiménez, R. Karpman, A. Kinzel, D. Pritikin. On the unitary Cayley graph of a finite ring. Electron. J. Combin. 16:1, (2009), Res. Paper 117, 13 pp.
  * [2] R. Atanasov, M. Budden, J. Lambert, K. Murphy, A. Penland, On certain induced subgraphs of Paley graphs. Acta Univ. Apulensis Math. Inform. 40 (2014), 51–65.
  * [3] N. de Beaudrap. On restricted unitary Cayley graphs and symplectic transformations modulo $n$ Electron. J. Combin. 17, (2010) p. R69.
  * [4] A. Bhowmik, R. Barman On a Paley-Type Graph on $\mathbb{Z}_{n}$ Graphs and Combinatorics 38, 41 (2022).
  * [5] A. Bhowmik, R. Barman Cliques of orders three and four in the Paley-type graphs (2023) arXiv:2301.07021.
  * [6] D.A. Cox. Primes of the form $x^{2}+ny^{2}$. John Wiley & Sons, Inc. 1989.
  * [7] A. Das. Paley-type graphs of order a product of two distinct primes. Algebra and Discrete Mathematics 28 1 (2019).
  * [8] M.L. Dawsey and D. McCarthy, Generalized Paley graphs and their complete subgraphs of orders three and four, Res. Math Sci. 8, (2021) Article number 18.
  * [9] R.J. Evans, J.R. Pulham, J. Sheenan. On the Number of Complete Subgraphs Contained in Certain Graphs. J. Combin. Theory Series B 30, (1981) 364–371.
  * [10] A. Ilić. The energy of unitary Cayley graphs. Linear Algebra Appl. 431, (2009) 1881–1889.
  * [11] D. Kiani, M.M. Haji Aghaei, M. Yotsanan, B. Suntornpoch. Energy of unitary Cayley graphs and gcd-graphs. Linear Algebra Appl. 435:6, (2011) 1336–1343.
  * [12] T.K. Lim, C.E. Praeger. On generalised Paley graphs and their automorphism groups. Michigan Math. J. 58:1, (2009) 294–308.
  * [13] X. Liu, S. Zhou. Spectral properties of unitary Cayley graphs of finite commutative rings. Electron. J. Combin. 19:4, (2012), Paper 13, 19 pp.
  * [14] X. Liu, S. Zhou. Quadratic unitary cayley graphs of finite commutative rings. Linear Algebra and its Appl. 479, (2015) 73–90.
  * [15] G. Pearce, C.E. Praeger. Generalised Paley graphs with a product structure. Annals of Combinatorics 23, (2019) 171–182.
  * [16] R.A. Podestá, D.E. Videla. The Waring’s problem over finite fields through generalized Paley graphs. Discrete Math. 344, (2021) 112324.
  * [17] R.A. Podestá, D.E. Videla. Integral equienergetic non-isospectral unitary Cayley graphs, Linear Algebra Appl. 612, (2021) 42–74.
  * [18] R.A. Podestá, D.E. Videla. A reduction formula for Waring numbers through generalized Paley graphs, Journal of Algebraic Combinatorics, 56:4, (2022), 1255–1285.
  * [19] R.A. Podestá, D.E. Videla. Generalized Paley graphs equienergetic with their complements, Linear and multilinear algebra (2022), in press, http://dx.doi.org/10.1080/03081087.2022.2159918.
  * [20] R.A. Podestá, D.E. Videla. Waring numbers over finite commutative local rings, (2022), Preprint: arXiv:2212.12396.
  * [21] R.A. Podestá, D.E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Adv. Math. Comm. 17:2, (2023) 446–464.
  * [22] D.E. Videla. On diagonal equations over finite fields via walks in NEPS of graphs. Finite Fields App. 75, (2021) 101882.
  * [23] C.H. Yip. On the directions determined by Cartesian products and the clique number of generalized Paley graphs. Integers. 21, (2021) Paper A51 .
  * [24] C.H. Yip. On the clique number of Paley graphs of prime power order. Finite Fields App. 77, (2022) 101930.