Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
Could you give the exact reference to the "Ernie Croot's list"? –  Seva Dec 8 '10 at 12:05
    
Yes, here it is: people.math.gatech.edu/~ecroot/E2S-01-11.pdf especially Sect. 2.8. –  Mike Mar 21 '11 at 0:10
5  
Seems that the list is actually compiled by two people... –  Seva Oct 13 '11 at 7:14
1  
Yes, you're right Seva. My apologies. :) I'll have to write you later, re: followup/questions to 1 or 2 of your papers. Thanks. –  Mike Nov 4 '11 at 20:28

4 Answers 4

up vote 13 down vote accepted

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

share|improve this answer
    
Ben, thanks. I'll email him about this later, after I think about it for a little while. –  Mike Nov 4 '11 at 20:29

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.) alt text

share|improve this answer

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 ]

share|improve this answer
2  
Maybe, you could add several lines of code to your program to plot the results? That is, to plot the largest size of a clique as a function of $p$ (along with the graph of $\log^2p$ or anything you think could serve as a better approximation?) –  Seva Aug 28 '12 at 18:18

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.