MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
CRT ? – Tom Leinster Jan 20 '10 at 2:05
Chinese Remainder Theorem. – darij grinberg Jan 20 '10 at 2:10
The set of squares was given as an example of a subset that satisfies the desired property for (p+1)/2 equivalence classes. The question is if there is a similarly ``nice'' set that does so for (p-1)/2 equivalence classes. – Aeryk Jan 20 '10 at 2:43
I believe the large sieve should show that such a set has at most on order of sqrt(N) elements in [1..N]. – JSE Jan 20 '10 at 2:44
up vote 6 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
Before I am told that this has too few residue classes, one may be able to change the offset recursively to give the desired result, not just arbitrarily. – Gerhard Paseman Jan 20 '10 at 7:53
And if you don't like that one, how about 1, 3, 15, 105, 945, 10395, 135135, etc. I think that can fit the bill even better than the original. – Gerhard Paseman Jan 20 '10 at 8:12
Oops. Maybe I should leave off the 1. – Gerhard Paseman Jan 20 '10 at 8:14
Darn. Doesn't work for 17. While it can be fixed, it looks more arbitrary after fixing (instead of multiplying by the next odd number, multiply by some small multiple of the next odd number). Time for bed. – Gerhard Paseman Jan 20 '10 at 8:25

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

share|cite|improve this answer
"I don't think the result is actually true"---you mean you don't think such a set exists? I think one can easily construct one using CRT. You build it recursively. The point is that if it has size n, and has size at most (p-1)/2 mod p for all primes p, then you ignore all the primes bigger than 2n+3 because if you throw in another element it will still be too small to fill up (p-1)/2 classes, and for all primes <= 2n+3 you make sure that the new element is in a new congruence class mod p if we're still too small mod p, and is in an old congruence class mod p if we've got to the (p-1)/2 limit. – Kevin Buzzard Jan 20 '10 at 12:45
One can even make this uniform, because, the moment one has hit (p-1)/2 classes mod p one can ensure that all the rest of the numbers hit each cong class mod p equally, by making the new numbers "take it in turns" with the classes. – Kevin Buzzard Jan 20 '10 at 12:47
I don't understand your comment that since A is infinite, the set of odd primes dividing some a in A must be infinite. Perhaps it is true, but it takes an argument. Something like that there is some p=4k+1 so that the primes are all simultaneously 4th powers mod p. Are the primes where q is a 4th power determined by residues mod cq for some c? – Douglas Zare Jan 20 '10 at 15:13
Wow, thanks for pointing out all those mistakes (and explaining how to create such a set). – Zev Chonoles Jan 20 '10 at 15:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.