On the Clique Number of Paley Graphs of Prime Power Order

Chi Hoi Yip

Published 2020-04-02Version 1

Finding a reasonably good upper bound for the clique number of Paley graph is an old and open problem in additive combinatorics. A recent breakthrough by Hanson and Petridis using Stepanov's method gives an improved upper bound on $\mathbb{F}_p$, where $p \equiv 1 \pmod 4$. We extend their idea to the finite field $\mathbb{F}_q$, where $q=p^{2s+1}$ for a prime $p\equiv 1 \pmod 4$ and a non-negative integer $s$. We show the clique number of the Paley graph over $\mathbb{F}_{p^{2s+1}}$ is at most $\min \bigg(p^s \bigg\lceil \sqrt{\frac{p}{2}} \bigg\rceil, \sqrt{\frac{q}{2}} + \frac{p^s+1}{4} + \frac{\sqrt{2p}}{32} p^{s-1}\bigg)$.