Cliques in the Paley graph and a problem of Sarkozy - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T09:37:43Z http://mathoverflow.net/feeds/question/107545 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107545/cliques-in-the-paley-graph-and-a-problem-of-sarkozy Cliques in the Paley graph and a problem of Sarkozy Seva 2012-09-19T09:44:41Z 2012-09-21T05:42:00Z <p>The following question is motivated by pure curiosity; it is not a part of any research project and I do not have any applications. The question comes as an interpolation between two notoriously difficult open problems.</p> <p>The first problem is to show that if $p\equiv 1\pmod 4$ is prime, and a set $A\subset{\mathbb F}_p$ has the property that the difference of any two elements of $A$ is a square, then $A$ is "small". (Basic details can be found <a href="http://mathoverflow.net/questions/48591/cliques-paley-graphs-and-quadratic-residues" rel="nofollow">here</a>). Notice that, letting <code>${\mathcal Q}:=\{x^2\colon x\in{\mathbb F}_p\}$</code>, one can write the assumption as $A-A\subset{\mathcal Q}$.</p> <p>The second problem, to my knowledge first posed by Andras Sarkozy several years ago, is to determine whether the set of all squares is as a sumset; that is, whether ${\mathcal Q}=A+B$ with <code>$A,B\subset{\mathbb F}_p$</code> and <code>$\min\{|A|,|B|\}\ge 2$</code>. The conjectural answer is, of course, negative, provided that $p$ is sufficiently large.</p> <p>Both problems just mentioned seem to be quite tough; but, maybe, the following combination of the two is more tractable:</p> <blockquote> <p>For a prime $p\equiv 1\pmod 4$, writing ${\mathcal Q}$ for the set of all squares in ${\mathbb F}_p$, does there exist a set $A\subset{\mathbb F}_p$ such that $A-A={\mathcal Q}$?</p> </blockquote> <p>Compared to the first of the two aforementioned problems, we now assume that <em>every quadratic residue</em> is representable as a difference of two elements of $A$; compared to the second problem we assume that $B=-A$. Is there a way to utilize these extra assumptions?</p> <p>A funny observation is that sets $A$ with the property in question do exist for $p=5$ and also for $p=13$; however, it would be very plausible to conjecture that these values of $p$ are exceptional. (In this direction, <a href="http://mathoverflow.net/users/18739/peter-mueller" rel="nofollow">Peter Mueller</a> has verified computationally that no other exceptions of this sort occur for $p&lt;1000$.) </p>