Cliques, Paley graphs and quadratic residues

Question

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:

1. 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.

2. 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.)

3. 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:

1. Maistrelli and Penman give a discussion of these bounds along with some computational work, in Discrete Mathematics in 2006.

2. 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?

3. 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.

4. 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.

5. 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.

Answer 1

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$.

Answer 2

Seva suggested to add a plot in David Wood's answer. Since I cannot edit his answer, I put it in my `answer' which of course isn't an answer to the original question. The horizontal axis is for the primes $p<10000$. The red graph is the clique number $c(p)$ (with consecutive points connected). The green graph is $\log(p)/\log(2)+3/2$, the expected size of $c(p)$ according to a heuristic by Stephen Cohen. But that cannot be the right size by Graham-Ringrose, see Ben Green's answer. The blue line is $\alpha\log^2(p)$, where $\alpha=0.2382\ldots$ was chosen as to minimize $\sum(c(p)-\alpha\log^2(p))^2$ in this range.

(The values $c(p)$ were computed with Sage up to $p<5000$, and the remaining ones were taken from here and here.)

^(source)

Answer 3

This is a little late, but since this is the first thing that pops up with a google search of cliques in Paley graphs, I will mention the following: here is a result that improves the bound of $\sqrt{p}$ to $\sqrt{p} - 1$ for infinitely many primes.

Answer 4

I don't know if this is of any use to those interested in this question, but here goes anyway ... a long time ago I wrote code that computes maximum cliques in graphs. By exploiting the symmetry in the graph, the algorithm reduces the search space considerably. For each prime $p \equiv 1 \pmod 4$ here is a maximum clique in the corresponding Paley graph. For what it is worth, the cliques stay fairly small. I would guess this is polylogarithmic growth.

p=5 c=[ 4, 0 ]

p=13 c=[ 9, 10, 6 ]

p=17 c=[ 11, 10, 12 ]

p=29 c=[ 27, 28, 23, 22 ]

p=37 c=[ 21, 33, 32, 22 ]

p=41 c=[ 33, 38, 34, 29, 13 ]

p=53 c=[ 46, 47, 40, 36, 30 ]

p=61 c=[ 54, 58, 53, 39, 38 ]

p=73 c=[ 54, 66, 62, 70, 16 ]

p=89 c=[ 86, 87, 77, 8, 6 ]

p=97 c=[ 79, 81, 73, 57, 48, 46 ]

p=101 c=[ 97, 98, 84, 75, 61 ]

p=109 c=[ 103, 102, 77, 74, 39, 14 ]

p=113 c=[ 112, 104, 108, 21, 17, 13, 6 ]

p=137 c=[ 134, 136, 135, 15, 14, 13, 6 ]

p=149 c=[ 147, 141, 142, 23, 22, 29, 28 ]

p=157 c=[ 156, 145, 39, 144, 36, 35, 0 ]

p=173 c=[ 170, 164, 139, 135, 51, 26, 22, 13 ]

p=181 c=[ 176, 180, 44, 24, 33, 28, 8 ]

p=193 c=[ 179, 178, 187, 115, 48, 40, 17 ]

p=197 c=[ 192, 193, 96, 132, 36, 35, 20, 11 ]

p=229 c=[ 216, 220, 201, 125, 158, 116, 67, 55, 40 ]

p=233 c=[ 228, 229, 124, 173, 11, 4, 3 ]

p=241 c=[ 202, 226, 67, 120, 43, 38, 14 ]

p=257 c=[ 248, 246, 124, 25, 4, 2, 0 ]

p=269 c=[ 267, 268, 119, 118, 95, 65, 52, 22 ]

p=277 c=[ 275, 262, 223, 106, 115, 87, 32, 25 ]

p=281 c=[ 277, 257, 187, 62, 76, 66, 4 ]

p=293 c=[ 272, 286, 199, 215, 146, 62, 46, 3 ]

p=313 c=[ 300, 311, 292, 179, 94, 62, 36, 37 ]

p=317 c=[ 310, 301, 285, 257, 294, 89, 231, 50, 35 ]

p=337 c=[ 315, 322, 88, 81, 60, 34, 33, 32, 6 ]

p=349 c=[ 346, 334, 120, 53, 89, 33, 16, 11, 2 ]

p=353 c=[ 349, 351, 330, 319, 164, 153, 142, 42, 7 ]

p=373 c=[ 367, 371, 252, 115, 88, 87, 49, 1 ]

p=389 c=[ 385, 379, 177, 115, 268, 226, 201, 48, 20 ]

p=397 c=[ 386, 377, 107, 91, 88, 72, 58, 24, 15 ]

p=401 c=[ 384, 395, 63, 52, 41, 34, 23, 12, 92 ]

p=409 c=[ 398, 402, 232, 382, 235, 143, 126, 23, 5 ]

p=421 c=[ 419, 414, 194, 145, 117, 31, 14, 10, 5 ]

p=433 c=[ 427, 428, 236, 426, 46, 45, 44, 28, 20, 19, 11 ]

p=449 c=[ 448, 438, 346, 244, 133, 117, 77, 66, 7 ]

p=457 c=[ 446, 455, 117, 108, 70, 61, 54, 53, 52, 45, 36 ]

p=461 c=[ 450, 451, 336, 429, 428, 192, 170, 131, 82, 78, 77 ]

p=509 c=[ 498, 489, 176, 85, 80, 165, 74, 69, 60 ]

p=521 c=[ 520, 510, 113, 122, 93, 73, 51, 41, 9 ]

p=541 c=[ 533, 521, 256, 429, 153, 351, 126, 122, 117, 360, 95 ]

p=557 c=[ 555, 548, 451, 188, 455, 166, 72, 53, 17, 13, 7 ]

p=569 c=[ 551, 568, 51, 552, 49, 17, 16, 15, 8 ]

p=577 c=[ 566, 575, 182, 160, 148, 151, 89, 55, 20, 1 ]

p=593 c=[ 590, 592, 396, 421, 451, 305, 323, 255, 239, 181, 139 ]

p=601 c=[ 594, 592, 236, 367, 385, 234, 188, 218, 140, 9, 1 ]

p=613 c=[ 608, 587, 234, 417, 521, 405, 388, 251, 128, 118, 52, 31 ]

p=617 c=[ 612, 614, 216, 610, 337, 512, 78, 71, 64, 62, 60 ]

p=641 c=[ 637, 621, 254, 238, 181, 126, 124, 117, 110, 108, 53 ]

p=653 c=[ 645, 639, 183, 603, 155, 149, 136, 113, 73, 50, 26 ]

p=661 c=[ 651, 654, 554, 528, 516, 490, 128, 166, 31, 19, 2 ]

p=673 c=[ 657, 659, 452, 630, 96, 67, 40, 38, 13, 12, 11 ]

p=677 c=[ 670, 649, 337, 553, 434, 256, 141, 127, 87, 72, 8 ]

p=701 c=[ 700, 699, 213, 323, 212, 182, 118, 94, 93, 29 ]

p=709 c=[ 697, 694, 617, 179, 223, 164, 176, 160, 117, 101 ]

p=733 c=[ 722, 718, 168, 676, 481, 503, 180, 158, 20, 11, 1 ]

p=757 c=[ 740, 731, 554, 230, 168, 305, 93, 86, 77, 74, 47 ]

p=761 c=[ 750, 751, 142, 301, 285, 324, 105, 68, 66, 29, 27 ]

p=769 c=[ 741, 756, 294, 260, 300, 270, 198, 108, 44, 17, 12 ]

p=773 c=[ 766, 765, 401, 578, 170, 169, 153, 132, 88, 74, 30 ]

p=797 c=[ 794, 793, 140, 309, 292, 155, 99, 53, 37 ]

Answer 5

Actually if you use multi-dimensional character sum estimates instead of the single variable Hasse-Weil estimate then you should be able to obtain $c(p)>\log_2(p)$. In fact I have done this assuming a reasonably plausible estimate for the character sums required. (In fact I did this for k-colourings of graphs but the case k=2 is what is needed here). It is a very involved and difficult calculation.

The problem is the required estimates are not obviously derivable from the standard estimates of Deligne, Katz, Sperber for example and although I am reasonably sure they can be derived by someone with knowledge in this area I personally am unable to do this!

Montgomery showed that the least non-residue must sometimes have value $\epsilon \ln(p)\ln\ln(p)$ which shows that definitely $c(p)=O(\ln(p))$ is wrong. However it is possibly true infinitely often and if so this would keep alive the hope that the Paley graphs provide explicit constructions of graph colourings with no monochromatic clique larger than $c\log_2(n)$, where $n$ is the number of vertices, for infinitely many n.