5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ CRT ? $\endgroup$ Jan 20, 2010 at 2:05
  • 2
    $\begingroup$ Chinese Remainder Theorem. $\endgroup$ Jan 20, 2010 at 2:10
  • $\begingroup$ 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. $\endgroup$
    – Aeryk
    Jan 20, 2010 at 2:43
  • $\begingroup$ I believe the large sieve should show that such a set has at most on order of sqrt(N) elements in [1..N]. $\endgroup$
    – JSE
    Jan 20, 2010 at 2:44

3 Answers 3

6
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jan 20, 2010 at 7:53
  • $\begingroup$ 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. $\endgroup$ Jan 20, 2010 at 8:12
  • $\begingroup$ Oops. Maybe I should leave off the 1. $\endgroup$ Jan 20, 2010 at 8:14
  • $\begingroup$ 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. $\endgroup$ Jan 20, 2010 at 8:25
1
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ "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. $\endgroup$ Jan 20, 2010 at 12:45
  • $\begingroup$ 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. $\endgroup$ Jan 20, 2010 at 12:47
  • $\begingroup$ 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? $\endgroup$ Jan 20, 2010 at 15:13
  • $\begingroup$ Wow, thanks for pointing out all those mistakes (and explaining how to create such a set). $\endgroup$ Jan 20, 2010 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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