A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the Paley graph, call it $P(p)$, of order p as follows. This graph has vertex set {0, 1, 2, …., p-1} with two vertices i and j joined by an edge if and only if i – j is a quadratic residue modulo p. If p=1 mod 4 then -1 is a quadratic residue modulo p so this is a bona fide undirected graph. Say $c(p)$ is the clique number, or size of the largest complete subgraph of $P(p)$.
We can ignore graphs, etc. and just phrase it in terms of finding a maximum set, A, of quadratic residues modulo p (p still is 1 modulo 4) such that the difference of any two distinct elements of A is still a quadratic residue.
I'll make several comments here at this point:
-
There are the "standard bounds" which are of the form $c(p) > (1/2-o(1)) lg(p)$ and
$c(p) < sqrt(p)$ where $lg(p)$ is the base 2 logarithm.
-
One or both of these bounds have been rediscovered every 5-10 years or so, going all the way back to Erdos and Newman(?) back in the 1950's. Sometime soon, I'll collect a comprehensive list and make it available online. :::::grin:::::: Another interesting observation is that both bounds can be proved either using combinatorial tools (Ramsey's theorem, Lovasz's theta function, SDP and vertex transitive graphs, etc.) OR using number theoretic tools (Gaussian sums, Weil's theorem, etc.)
-
We can look at generalizations involving quadratic nonresidues, nonprime finite fields/rings, etc. which I won't get into, though I can at least refer to Ernie Croot's problem list in arithmetic combinatorics and work of Gasarch and Ruzsa. I'm not interested ( in this post at least:::grin::::) in this.
Finally my question:
Has anyone been able to materially improve either of these bounds?
What I do know about related work is:
-
Maistrelli and Penman give a discussion of these bounds along with some computational work, in Discrete Mathematics in 2006.
-
Fan Chung, Friedlander, Iwaniec and others have studied related problems in character sums and applications in combinatorics but haven't seemed to show (yet?) any improvement in the bounds for $c(p)$. Or, have I missed something obvious here?
-
Andrew Thomason, Chung-Graham-Wilson, etc. have related work on "pseudo-random graphs"
which I will assume is known, or at least accessible to all the readers here. Thomason, in one article, makes some interesting assertions which are plausible but which I need to check. -
There's the work of a number of people from Alon to Wigderson, exploring related questions and their applications to problems in theoretical computer science.
-
Finally, we have estimates for $n(p)$, the least quadratic nonresidue modulo p, following Chowla, Salie, Graham-Ringrose and others. The connection with $c(p)$ is obvious.
What else, of a substantial nature, is there?
I think, in particular, that using work of Granville and Soundarajan, the 1/2 in the first bound can be improved and using a combination of number theoretic methods (Burgess, etc.) and combinatorial methods (Ruzsa, Chang, Green, etc.) the second (square root) bound can be improved. I'm going to stop here and not go into any more specifics, either attempts, propositions, conjectures or computational evidence.
Best Answer
I'm certain that no "material" improvement to the upper bound has been obtained, and this seems to be a very hard open question. Some time ago Tom Sanders showed me an argument which improves the bound in the case $p = n^2 +1$ to $n - 1$. So far as I can tell he hasn't published this. Even if you regard the $-1$ as a "material improvement", it's a matter for conjecture whether his theorem even applies for infinitely many primes $p$.
The Graham-Ringrose estimates, which you mention, show that one cannot hope for $c(p) = O(\log p)$ for all $p$.