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

NEW

Problem: Reconstructed statement: Let $q=p^r$ be odd, $m\mid(q+1)$, $2\le m\le (q+1)/3$, and $p\nmid(m-1)$. Let

$$\mathrm{GP}(q^2,m)=\operatorname{Cay}(\mathbb F_{q^2}^+,(\mathbb F_{q^2}^*)^m).$$

Put $w=(q+1)/m$, let $Q=\{x\in\mathbb F_{q^2}^*:x^{q+1}=1\}$, and let $Q_0\le Q$ be its subgroup of order $w$. Choose $\alpha\in\mathbb F_{q^2}\setminus\mathbb F_q$ with $\alpha^q=-\alpha$. Then the conjecture asserts maximality of the Proposition 4.10 and 4.13 cliques:

• if $w$ is even, $\{0\}\cup Q_0$ is maximal;
• if $w$ is odd, $\alpha Q_0$ is maximal;
• if $w$ is even, $\{0\}\cup \alpha Q_0$ is maximal.

This matches Conjecture 4.14 because Proposition 4.10 is the $Q_0$-construction and Proposition 4.13 is the $\alpha Q_0$-construction.

Result: The conjecture is true.

Let $S=(\mathbb F_{q^2}^*)^m$. For $x\ne0$,

$$x\in S\iff x^{q-1}\in Q_0\iff (x^{q-1})^w=1.$$

Indeed, if $x=\beta^a$ for a primitive $\beta$, then $x\in S\iff m\mid a$, while $x^{q-1}=(\beta^{q-1})^a\in Q_0\iff m\mid a$.

Since $q+1=mw$, modulo $p$ we have $mw\equiv1$. Thus $p\nmid w$, and

$$w-1\equiv m^{-1}(1-m)\not\equiv0\pmod p$$

because $p\nmid(m-1)$. Hence $\binom w1,\binom w2\ne0$ in $\mathbb F_{q^2}$. Also $w\ge3$.

First suppose $z\notin Q_0$ and $z-t\in S$ for all $t\in Q_0$. Then for all $t\in Q_0$,

$$\left(\frac{z^q-t^{-1}}{z-t}\right)^w=1.$$

Since $Q_0$ is the set of roots of $T^w-1$, the polynomial

$$(z^q-T^{w-1})^w-(z-T)^w$$

is $0$ modulo $T^w-1$. The coefficients of $T$ and $T^2$ give

$$z^q=(-1)^wz^{w-1},\qquad (z^q)^2=(-1)^w z^{w-2}.$$

If $z\ne0$, these imply $z^w=(-1)^w$ and $z^q=z^{-1}$. Thus $z\in Q$. If $w$ is even, then $z^w=1$, so $z\in Q_0$, contradiction. Therefore, for even $w$, the only possible such $z\notin Q_0$ is $z=0$.

Now suppose $z\notin Q_0$ and $\alpha(z-t)\in S$ for all $t\in Q_0$. Since $\alpha^{q-1}=-1$, we get

$$\left(\frac{z^q-t^{-1}}{z-t}\right)^w=(-1)^w.$$

Thus

$$(z^q-T^{w-1})^w-(-1)^w(z-T)^w\equiv0\pmod{T^w-1}.$$

Again using the $T$ and $T^2$ coefficients,

$$z^q=z^{w-1},\qquad (z^q)^2=z^{w-2}.$$

If $z\ne0$, then $z^w=1$ and $z^q=z^{-1}$, hence $z\in Q_0$, contradiction. Therefore $z=0$. But $z=0$ is possible only when $\alpha\in S$, equivalently $(\alpha^{q-1})^w=(-1)^w=1$, i.e. only when $w$ is even.

Now maximality follows immediately.

1. If $w$ is even and a vertex $y\notin\{0\}\cup Q_0$ were adjacent to every vertex of $Q_0$, then the first calculation forces $y=0$, contradiction. Hence $\{0\}\cup Q_0$ is maximal.

2. If $w$ is odd and a vertex $y\notin\alpha Q_0$ were adjacent to every vertex of $\alpha Q_0$, write $y=\alpha z$. Then $z\notin Q_0$ and $\alpha(z-t)\in S$ for all $t\in Q_0$, impossible by the second calculation. Hence $\alpha Q_0$ is maximal.

3. If $w$ is even and $y\notin\{0\}\cup\alpha Q_0$ were adjacent to every vertex of $\alpha Q_0$, write $y=\alpha z$. Then $z\notin Q_0$ and the second calculation forces $z=0$, so $y=0$, contradiction. Hence $\{0\}\cup\alpha Q_0$ is maximal.

Thus all cliques from Propositions 4.10 and 4.13 are maximal under the conjectured hypotheses.

Citation: The conjecture and constructions are 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; arXiv:2203.16081. The proof above is a direct resolution of Conjecture 4.14.