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?



Integer subset that only occupies (p-1)/2 equivalence classes mod p?
See section 4.3 of Helfgott and Venkatesh, ["How small must ill-distributed sets be?"](http://math.stanford.edu/~akshay/research/hs.pdf) 


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


