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>
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8946030735969543, "perplexity": 602.5779914881626}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2013-20/segments/1368701562534/warc/CC-MAIN-20130516105242-00016-ip-10-60-113-184.ec2.internal.warc.gz"}