It is known that the number of directions formed by a Cartesian product $A \times B \subset AG(2,p)$ is at least $|A||B| - \min\{ |A|,|B|\} + 2$, provided $p$ is prime and $|A||B|<p$. This implies the best known upper bound on the clique number of the Paley graph over $\mathbb{ F}_p$. In this paper, we extend this result to $AG(2,q)$, where $q$ is a prime power. We also give improved upper bounds on the clique number of generalized Paley graphs over $\mathbb{ F}_q$. In particular, for a cubic Paley graph, we improve the trivial upper bound $\sqrt{ q}$ to $0.769\sqrt{ q}+1$. In general, as an application of our key result on the number of directions, for any positive function $h$ such that $h(x)=o(x)$ as $x \to \infty$, we improve the trivial upper bound $\sqrt{ q}$ to $\sqrt{ q}-h(p)$ for almost all non-squares $q$.
Categories: math.CO math.NT