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 .