On eigenfunctions and maximal cliques of generalised Paley graphs of square order

NEW

Problem: Let $q=p^r$ be odd, let $m\mid(q+1)$, $2\le m\le (q+1)/3$, and let $\mathrm{GP}(q^2,m)$ be the Cayley graph on $\mathbb F_{q^2}$ whose connection set is the set of nonzero $m$-th powers. Choose $\alpha\in\mathbb F_{q^2}\setminus\mathbb F_q$ with $\alpha^q=-\alpha$. Conjecture 4.9 asserts: if $p\nmid(m-1)$, then the cliques constructed in Proposition 4.6, namely

$$N(\alpha)\cup\{\alpha\}\quad\text{or}\quad N(\alpha)\cup\{\alpha,-\alpha\},$$

according as $m\nmid (q+1)/2$ or $m\mid (q+1)/2$, and the corresponding Proposition 4.7 cliques on $\alpha\mathbb F_q$, are maximal. Here

$$N(u)=\{x\in\mathbb F_q: u-x \text{ is an }m\text{-th power in }\mathbb F_{q^2}\}.$$

Result: The conjecture is true.

Let $w=(q+1)/m$. Since $p\nmid(q+1)$, $p\nmid w$, and since $p\nmid(m-1)$,

$$w\not\equiv 1\pmod p,$$

so $\binom w2\ne0$ in $\mathbb F_{q^2}$.

Let

$$Q=\{z\in\mathbb F_{q^2}^*:z^{q+1}=1\},\qquad Q_0=\{z\in Q:z^w=1\}.$$

The map

$$\theta(z)=\alpha\frac{z+1}{z-1}$$

bijectionally sends $Q\setminus\{1\}$ to $\mathbb F_q$, and

$$N(\alpha)=\theta(Q_0\setminus\{1\}).$$

Key lemma. If an affine map $x\mapsto tx+(1-t)a$, with $t\in\mathbb F_q^*$, $a\in\mathbb F_q$, stabilizes $N(\alpha)$, then either it is the identity, or it is $x\mapsto -x$.

Indeed, the induced Möbius map on $Q_0$ is

$$z\mapsto \frac{Az+B}{Cz+D},$$

where, with $s=(1-t)a/\alpha$,

$$A=t+s+1,\quad B=t-s-1,\quad C=t+s-1,\quad D=t-s+1.$$

Since it stabilizes $Q_0$, the polynomial

$$(Az+B)^w-(Cz+D)^w$$

vanishes on all $w$-th roots of unity, hence is a multiple of $z^w-1$. Therefore the coefficients of $z$ and $z^2$ vanish:

$$AB^{w-1}=CD^{w-1},\qquad A^2B^{w-2}=C^2D^{w-2}.$$

If none of $A,B,C,D$ is zero, division gives $A/B=C/D$, hence $AD=BC$, but directly

$$AD-BC=4t\ne0,$$

a contradiction. The zero cases force either $t=1$, giving the identity, or $t=-1$ and $a=0$, giving $x\mapsto -x$.

Now suppose the Proposition 4.6 clique $C$ is not maximal. Any extra vertex $v\notin C$ adjacent to all of $C$ must lie outside $\mathbb F_q$, and since $|N(v)|=|N(\alpha)|$, one has $N(v)=N(\alpha)$. By Proposition 5.1 of Goryainov–Shalaginov–Yip, under the present hypotheses this implies that for some $a\in\mathbb F_q$ and $t\in\mathbb F_q^*$,

$$\alpha-a=t(v-a),$$

and the affine map $x\mapsto tx+(1-t)a$ stabilizes $N(\alpha)$. By the lemma, the only nontrivial possibility is $t=-1,a=0$, hence $v=-\alpha$.

If $m\nmid(q+1)/2$, then $\alpha$ is not an $m$-th power, so $2\alpha$ is not an $m$-th power, and $\alpha$ is not adjacent to $-\alpha$. Thus no such $v$ exists.

If $m\mid(q+1)/2$, then $-\alpha$ is already included in the Proposition 4.6 clique, so again no new vertex can be added. Hence the Proposition 4.6 clique is maximal.

Finally, when $m\mid(q+1)/2$, $\alpha$ itself is an $m$-th power, so multiplication by $\alpha^{-1}$ is an automorphism of $\mathrm{GP}(q^2,m)$. It sends the Proposition 4.6 clique $N(\alpha)\cup\{\alpha,-\alpha\}$ to the Proposition 4.7 clique $\alpha\mathbb F_q$-construction with vertices $\{\pm1\}\cup(\alpha\mathbb F_q\cap N(1))$. Therefore the Proposition 4.7 clique is maximal as well.

Citation: Uses the definitions and Proposition 5.1 from Goryainov, Shalaginov, and Yip, “On eigenfunctions and maximal cliques of generalised Paley graphs of square order,” Finite Fields Appl. 87 (2023), Paper No. 102150. The maximality argument above resolves Conjecture 4.9.