The largest clique in the Paley Graph: unexpected significant progress and surprising connections.

The result on Paley Graphs by Hanson and Petridis

On May 2019, Brandon Hanson and Giorgis Petridis posed a paper on the arXive: Refined Estimates Concerning Sumsets Contained in the Roots of Unity. The abstract was almost as short as the title (the paper is short as well!):

We prove that the clique number of the Paley graph is at most \sqrt {p/2}+1, and that any supposed additive decompositions of the set of quadratic residues can only come from co-Sidon sets.

Let me elaborate on the first half of the abstract.

Let q be a prime power such that q=1 (\mod 4). This choice implies that in F_q the difference of two numbers, a-b, is a square iff -(a-b) is a square, so the Paley graph we are going to define is a simple graph.

In the Payley graph the vertices are the elements of F_q and two are adjacent iff their difference is a square.

When the field is F_p, where p is prime, then the Paley graph is conjectured to be an excellent construction for a Ramsey graphs, the largest complete subgraph (which has the same size as its largest empty subgraph since it is self-complementary) is conjectured to be \log(p)\log \log (p). This is actually a lower bound for infinitely many primes, proved by Montgomery under the assumption that the generalized Riemann hypothesis holds.

The upper bound (which is easy to prove) is \sqrt p. This upper bound is sharp for the field F_{p^2}. (This is a very nice construction of Aart Blokhuis.)

There was practically no improvement on the \sqrt p upper bound until 2013, when Bachoc, Ruzsa and Matolcsi, proved that the \sqrt p-1 bound holds for infinitely many primes.

Hanson and Petridis thus improved the upper bound significantly! They gave the upper bound \sqrt{p/2}+1 on the clique size of the Paley graph. Their  proof uses Stepanov’s method.

The result of Di Benedetto, Solymosi, and White on directions in Cartesian products

A couple weeks ago, Daniel Di Benedetto, József Solymosi, and Ethan White posted a paper on the arxive: On the directions determined by a Cartesian product in an affine Galois plane. Also here the abstract is also quite short (and so is the entire paper!).

We prove that the number of directions contained in a set of the form A \times B \subset AG(2,p), where p is prime, is at least |A||B| -\min\{|A|,|B|\}+2. Here A and B are subsets of GF(p) each with at least two elements and |A||B|<p. This bound is tight for an infinite class of examples. Our main tool is the use of the Rédei polynomial with Szőnyi’s extension.

A surprising connection

Now, if you have a set A where the difference between any two elements is a square then in A \times A all directions, (a-b)/(c-d), are also squares. To Daniel, József, and Ethan’s  great surprise applying their bound on the clique number of the Paley graph gave the very same bound as Hanson and Petridis!

I am thankful to Józsi Solymosi for very helpful clarifications.

Payley graph with 13 vertices (source: wikipedea)

A quick Sum-Product update, and associations.

Now that I mention Józsi’s work let me also use this opportunity to give a quick update about Erdős-Szemeredi’s sum product conjecture. In an old post from 2009, I presented Elekes’ pioneering geometric proof for his sum-product world record and gave a link to a paper and a blog post written by Izabella Laba about József Solymosi’s new (then) world record. I just saw an article by Kevin Hartnett about the problem in Quanta Magazine describing several subsequent records. The current world record is in a 2019 paper by George Shakan.   (Sergei Konyagin and Ilya Shkredov broke József’s record in 2015, and the new record improved a 2016 world record by Misha Rudnev, Ilya Shkredov and Sophie Stevens; I also updated my related MO answer.) Of course, the sum-product phenomena is a huge area with amazing applications (See, here, here, here, and here; I recall that Jean Bourgain referred to it as a gold mine or something like that). Now, talking about sum-product theorems, and about Bourgain, and about Quanta Magazine, I should mention a lovely Quanta podcast featuring Alex Kontorovich interviewed by Steven Strogatz  .

This entry was posted in Combinatorics, Number theory and tagged , , , , , . Bookmark the permalink.

3 Responses to The largest clique in the Paley Graph: unexpected significant progress and surprising connections.

  1. Gil Kalai says:

    I forgot to mention an earlier 2006 improvement by E. Maistrelli and D. B. Penman that proved \sqrt{p} - 1 for primes of the form n^2+1. It is conjectured but not known if there are infinitely many such primes. (This is a famous conjecture on its own).

    Christine Bachoc, Imre Z. Ruzsa, and Mate Matolcsi, proved \sqrt{p} - 1 for about three quarter of primes. (C. Bachoc, M. Matolcsi, I. Z. Ruzsa: Squares and difference sets in finite fields, Integers, Vol. 13, Article A77).

  2. Gil Kalai says:

    And here is the reason for the old \sqrt p bound: The Paley graph is self complementary (multiplying with a quadratic non-residue every elements of the field, quadratic residues become quadratic non-residues and non-residues to residues). So, if n is the size of the largest clique, K_n, then there is an n-vertex empty subset, E_n (all differences are quadratic nonresidues). For any two distinct elements (vertices) e_1,e_2 of E_n, the sets K_n+e_1 and K_n+e_2 are disjoint, because if there would be k_1+e_1=k_2+e_2 then k_1-k_2 is a quadratic non-residue, contradiction. Considering K_n+E_n, we have n^2 disjoint n-element sets in F_p. Sababa!

  3. Asvin G. says:

    Another proof of the old \sqrt(p) bound:

    Suppose S is a clique of size more than \sqrt(p). Consider the function f(x,y) = ax+by where we choose a/b to be a non residue. By the pigeon hole principle, there exists some x,y,u,v \in S so that ax+by = au+bv but then a/b = (v-u)/(x-y) which is a square. Contradiction!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s