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

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$,

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

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$,

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

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

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

Thus

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

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.