THE SUBSPACE STRUCTURE OF MAXIMUM CLIQUES IN PSEUDO-PALEY GRAPHS FROM UNIONS OF CYCLOTOMIC CLASSES

NEW

Problem: For an odd prime $p$, fix a primitive element $g\in \mathbb F_{p^{4}}^\*$. Let

$$C_j=g^j\langle g^{p+1}\rangle,\qquad j\in \mathbb Z/(p+1)\mathbb Z$$

be the $(p+1)$-st cyclotomic classes of $\mathbb F_{p^4}$. For $I\subset\{0,\dots,p\}$ with $|I|=(p+1)/2$, $PP(p^4,p+1,I)$ is the Cayley graph on $\mathbb F_{p^4}^+$ with connection set $\bigcup_{j\in I}C_j$.

Reconstructed Conjecture 5.9: if $V\le \mathbb F_{p^4}$ is a 2-dimensional $\mathbb F_p$-subspace with $1\in V$, then $V$ is a clique in $PP(p^4,p+1,I)$ for some such $I$ iff

$$V=\mathbb F_p\oplus a\mathbb F_p$$

with $a=g^{(p+1)k}$ for an odd integer $k$.

Result: The conjecture is true.

Let $F=\mathbb F_{p^4}$, $K=\mathbb F_{p^2}$, and $N=N_{F/K}$. The key observation is

$$x/y\in C_0\iff N(x)/N(y)\in \mathbb F_p^\*.$$

Indeed, if $x/y=g^m$, then $x/y\in C_0$ iff $p+1\mid m$, while $N(g^m)=(g^{p^2+1})^m$, and $\mathbb F_p^\*=\langle (g^{p^2+1})^{p+1}\rangle$.

Suppose first that $V$ is a clique for some $I$. Since $0,1\in V$, necessarily $0\in I$. By Asgarli–Yip’s equal-contribution theorem for maximum cliques in semi-primitive pseudo-Paley graphs, applied with $q=p^4$, $2d=p+1$, $r=2$, $t=1$, we have

$$|V\cap C_0|=\frac{p^2-1}{(p+1)/2}=2(p-1).$$

But $\mathbb F_p^\*\subset C_0$, so $V\cap C_0$ contains exactly one further $\mathbb F_p^\*$-line. Choose $a$ on that line. Then

$$V=\mathbb F_p\oplus a\mathbb F_p,\qquad a\in C_0.$$

Write $a=g^{(p+1)k}$. Put

$$c=N(a)=a^{p^2+1}\in \mathbb F_p^\*.$$

Then

$$c=g^{(p+1)k(p^2+1)}=\eta^k,$$

where $\eta=g^{(p+1)(p^2+1)}$ is primitive in $\mathbb F_p^\*$. Hence $c$ is a nonsquare in $\mathbb F_p^\*$ iff $k$ is odd.

It remains to show $c$ cannot be square. Let $s=a+a^{p^2}$. Since $a\notin\mathbb F_p$, one has $s\notin\mathbb F_p$. The projective $\mathbb F_p$-lines in $V$ are represented by $1$ and by $a+t$, $t\in\mathbb F_p$. For $t,u\in\mathbb F_p$,

$$N(a+t)=t^2+st+c.$$

Using $s\notin\mathbb F_p$, two finite lines $a+t$ and $a+u$ lie in the same cyclotomic class iff

$$t=u\quad\text{or}\quad tu=c.$$

Also the line $1$ is in the same class as $a+t$ iff $t=0$. Thus the cyclotomic-class fibers are precisely the orbits of the involution

$$t\mapsto c/t,\qquad 0\leftrightarrow \infty.$$

If $c$ were square, this involution would have two fixed points, so the $p+1$ lines of $V$ would occupy $(p+3)/2$ cyclotomic classes, more than $(p+1)/2$, impossible for a clique in a graph built from only $(p+1)/2$ classes. Hence $c$ is nonsquare, so $k$ is odd.

Conversely, suppose

$$V=\mathbb F_p\oplus a\mathbb F_p,\qquad a=g^{(p+1)k},\quad k\text{ odd}.$$

Then $a\in C_0$, and $c=N(a)\in\mathbb F_p^\*$ is nonsquare. The same involution $t\mapsto c/t$, $0\leftrightarrow\infty$, has no fixed points on $\mathbb P^1(\mathbb F_p)$. Therefore the $p+1$ projective lines of $V$ occupy exactly $(p+1)/2$ cyclotomic classes. Let $I$ be that set of class indices. Then

$$V\setminus\{0\}\subset \bigcup_{j\in I}C_j,$$

so every nonzero difference of two elements of $V$ lies in the connection set. Hence $V$ is a clique in $PP(p^4,p+1,I)$.

This proves both directions.

Citation: Uses Theorem 1.6 of Asgarli–Yip, “The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes,” Finite Fields Appl. 99 (2024), Paper No. 102492. The final classification argument above is elementary and supplies the claimed resolution of Conjecture 5.9.