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

### 2 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. https://arxiv.org/abs/1305.0577 (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!