Integer subset that only occupies (p-1)/2 equivalence classes mod p? - MathOverflow

Integer subset that only occupies (p-1)/2 equivalence classes mod p?

2010-01-20T01:46:44Z

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)?

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.

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?

Answer by Zev Chonoles for Integer subset that only occupies (p-1)/2 equivalence classes mod p?

2010-01-20T07:20:35Z

Here is something I noticed - no idea if it helps:

Suppose $A\subset\mathbb{Z}$ 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 for each 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$).

Answer by Gerhard Paseman for Integer subset that only occupies (p-1)/2 equivalence classes mod p?

2010-01-20T07:47:12Z

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.

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.

Gerhard "Ask Me About System Design" Paseman, 2010.01.19

Answer by JSE for Integer subset that only occupies (p-1)/2 equivalence classes mod p?

2010-01-20T12:29:44Z

See section 4.3 of Helfgott and Venkatesh, "How small must ill-distributed sets be?"

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.)