Integer subset that only occupies (p-1)/2 equivalence classes mod p? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T14:59:34Z http://mathoverflow.net/feeds/question/12364 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12364/integer-subset-that-only-occupies-p-1-2-equivalence-classes-mod-p Integer subset that only occupies (p-1)/2 equivalence classes mod p? Aeryk 2010-01-20T01:46:44Z 2010-01-21T00:41:23Z <p>I'm not quite sure the best way to ask this, so bear with me: Does anyone know of a subset of integers such that, for any odd prime p, the subset only occupies (p-1)/2 equivalence classes mod p (and does so uniformly)?</p> <p>For example, take the subset of squares. Elementary number theory shows that they (as quadratic residues) occupy (p+1)/2 equivalence classes mod p. But the answer to the above is not to take the non-residues since being a non-residue is a local property, not a property of an integer.</p> <p>It is possible to construct such a set of integers one element at a time in an ad hoc manner using some initial members, a whole lot of CRT, and making a somewhat arbitrary choice at each step. But is there a more well-known'' set that has this property?</p> http://mathoverflow.net/questions/12364/integer-subset-that-only-occupies-p-1-2-equivalence-classes-mod-p/12392#12392 Answer by Zev Chonoles for Integer subset that only occupies (p-1)/2 equivalence classes mod p? Zev Chonoles 2010-01-20T07:20:35Z 2010-01-20T15:21:04Z <p>Here is something I noticed - no idea if it helps:</p> <p>Suppose <code>$A\subset\mathbb{Z}$</code> has the property that for each odd prime $p$ and $\phi_p:\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$, we have $|\phi_p(A)|=\frac{p-1}{2}$. Consider the map $f_p:\mathbb{Z}/p\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$ with $f_p(x)=x^2$. Then $|f_p(\phi_p(A))|\leq\frac{p-1}{2}$. Since there are $\frac{p+1}{2}$ quadratic residues mod $p$, we must have that <strong>for each</strong> odd prime $p$, there is an $x_p\in\mathbb{Z}/p\mathbb{Z}$ such that $a^2\not\equiv x_p^2\bmod p$ for all $a\in A$ (which is $\Leftrightarrow$ $a\not\equiv \pm x_p\bmod p$). </p> http://mathoverflow.net/questions/12364/integer-subset-that-only-occupies-p-1-2-equivalence-classes-mod-p/12395#12395 Answer by Gerhard Paseman for Integer subset that only occupies (p-1)/2 equivalence classes mod p? Gerhard Paseman 2010-01-20T07:47:12Z 2010-01-20T07:47:12Z <p>I do not have an answer, but a suggestion: Consider looking at the primorials + 1. If you start late enough, there should be few equivalence classes hit (about 1/log p for large enough p) until you reach the primorial +1 that includes p. Also, one might do well to consider factorials or central binomial coefficients ( (2n!)/(n!)(n!) ) with a constant offset. </p> <p>I do not call it an answer because I do not know how natural a sequence is wanted. But if this is cheesy enough to be downvoted, I would like to know why.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.01.19</p> http://mathoverflow.net/questions/12364/integer-subset-that-only-occupies-p-1-2-equivalence-classes-mod-p/12407#12407 Answer by JSE for Integer subset that only occupies (p-1)/2 equivalence classes mod p? JSE 2010-01-20T12:29:44Z 2010-01-20T12:29:44Z <p>See section 4.3 of Helfgott and Venkatesh, <a href="http://math.stanford.edu/~akshay/research/hs.pdf" rel="nofollow">"How small must ill-distributed sets be?"</a> </p> <p>for an example of a subset of [1..N] of size about log N with small projections onto Z/pZ, and section 4.2 for a "guess" about what such subsets might look like in general. They speculate that such a set might have to be either very small (say, of size N^eps) or highly correlated with a "thin set," say, the values of a polynomial (i.e. x^2, as in the first case you describe.) </p>