A NOTE ON GRAPHS WITH A PRESCRIBED ADJACENCY PROPERTY

NEW

Problem: Reconstructed conjecture (Remark 2): Let $q\equiv1\pmod4$ be a prime power, $k\ge1$, and let $G_q$ be the Paley graph on $\mathbb F_q$. If

$$q<\bigl(1+2\sqrt{2k}\bigr)^2,$$

then $G_q\notin \mathcal G(1,2,k)$; i.e. there exist distinct vertices $a,b,c$ such that fewer than $k$ vertices are adjacent to $a$ and nonadjacent to both $b,c$.

This is exactly the statement following the authors’ computer verification for $q\le1009$.

Result: The conjecture is false. Take

$$q=5^5=3125,\qquad k=377.$$

Then

$$3125< (1+2\sqrt{754})^2=3017+4\sqrt{754},$$

since $27^2<754$. But $G_{3125}\in\mathcal G(1,2,377)$.

Proof. Let $F=\mathbb F_{3125}$ and let $\eta$ be its quadratic character. Since $q\equiv1\pmod4$, $\eta(-1)=1$. By translation, it suffices to count, for distinct $0,b,c$,

$$N(b,c)=|\{x\notin\{0,b,c\}:\eta(x)=1,\ \eta(x-b)=\eta(x-c)=-1\}|.$$

Put

$$S=\sum_{x\in F}\eta(x(x-b)(x-c)).$$

For the nonsingular elliptic curve

$$E_{b,c}: y^2=x(x-b)(x-c),$$

we have $\#E_{b,c}(F)=q+1+S$. Hasse gives

$$|S|\le 2\sqrt q=50\sqrt5<112,$$

so $S\ge -111$.

Expanding the indicator product gives

$$8N(b,c)=q+1+S-R,$$

where

$$R=(1-\eta(b))(1-\eta(c))+(1+\eta(b))(1-\eta(b-c))+(1+\eta(c))(1-\eta(b-c)).$$

A direct check with signs $\pm1$ gives $R\in\{0,4,8\}$. Hence

$$8N(b,c)\ge3126-111-8=3007,$$

so $N(b,c)\ge376$.

If $N(b,c)=376$, then

$$3008=3126+S-R,$$

so $S=R-118$. Since $S\ge-111$ and $R\in\{0,4,8\}$, necessarily $R=8$ and $S=-110$. Then $E_{b,c}$ would have trace

$$t=q+1-\#E_{b,c}(F)=-S=110.$$

But Waterhouse’s classification of elliptic-curve traces says that over $\mathbb F_{p^r}$, with $p>3$ and $r$ odd, the only trace divisible by $p$ that can occur for a supersingular elliptic curve is $0$; ordinary traces are not divisible by $p$. Here $p=5$, $r=5$, and $110\ne0$ is divisible by $5$, impossible.

Thus $N(b,c)\ne376$, so $N(b,c)\ge377$ for all distinct $b,c$. Therefore $G_{3125}\in\mathcal G(1,2,377)$, contradicting the conjecture.

Citation: Uses the conjecture from Ananchuen–Caccetta, “A note on graphs with a prescribed adjacency property,” Bull. Austral. Math. Soc. 50 (1994), Remark 2. The trace obstruction uses W. C. Waterhouse, “Abelian varieties over finite fields,” Ann. Sci. École Norm. Sup. 2 (1969), 521–560.