## 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 , 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 be a prime power such that . This choice implies that in the difference of two numbers, , is a square iff 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 and two are adjacent iff their difference is a square.

When the field is , where 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 . 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 . This upper bound is sharp for the field (This is a very nice construction of Aart Blokhuis.)

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

Hanson and Petridis thus improved the upper bound significantly! They gave the upper bound 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 , where is prime, is at least . Here and are subsets of each with at least two elements and . 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 where the difference between any two elements is a square then in all directions, , 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 .

I forgot to mention an earlier 2006 improvement by E. Maistrelli and D. B. Penman that proved for primes of the form . 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 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).

And here is the reason for the old 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, , then there is an n-vertex empty subset, (all differences are quadratic nonresidues). For any two distinct elements (vertices) of , the sets and are disjoint, because if there would be then is a quadratic non-residue, contradiction. Considering , we have disjoint n-element sets in . Sababa!

Another proof of the old bound:

Suppose S is a clique of size more than . Consider the function where we choose to be a non residue. By the pigeon hole principle, there exists some so that but then which is a square. Contradiction!