# Picking out an odd subset

I want to know whether the following property holds:

There exists a constant C such that for any big positive integer N and any nonempty subset M of {1,...,N} there exists a positive integer p(M)$\lt$ logN such that some residue class modulo p(M) contains odd number of elements from M.

A weaker form of the same property is also useful:

There exists a constant C such that for any big positive integer N and any disjoint (but not simultaneously empty!) subsets M, M' of {1,...,N} there exists a positive integer p(M)$\lt$C logN such that some residue class modulo p(M) contains different numbers of elements from M and M'.

-
Presumably the first "$p(M) < \log N\phantom.$" should be "$p(M) < C \log N\phantom.$" also? –  Noam D. Elkies Dec 16 '11 at 6:09
It is not clear why the second property is weaker than the first. The first looks false. Indeed, fix $x$ small compared with $N$, and for each $p \leq x$ impose the condition that every congruence class mod $p$ arise an even number of times in $M$. if $M\phantom.$ is regarded in the usual way as a vector in $({\bf Z}/2{\bf Z})^N$, each of our conditions mod $p$ is a homogeneous linear constraint, and there are about $x^2/2$ such constraints, so as long as $x^2/2 < N\phantom.$ they can be satisfied simultaneously by a nonzero vector, i.e. a nonempty $M$. So $C \log N$ is much too small. –  Noam D. Elkies Dec 16 '11 at 6:15
is the obvious $C\sqrt{N}$ conjecture true? Seems like the constraints look independent except for the fact that they all mandate that the total number of elements in $M$ is even. –  Will Sawin Dec 16 '11 at 8:54
Perhaps ideas connected with large sieve will help here. If $M(p,h)$ denotes the number of elts of $M$ congruent to $h$ mod $p$ then the assumption that $M(p,h)$ is always even should force the square mean $\sum_h |M(p,h) - |M|/p|^2$ to be, say, twice the size that one might expect for a positive fraction of $p$s. I'm not claiming to have an actual argument, though! –  Ben Green Dec 16 '11 at 10:32
The second question is hardly any better than the first. Consider all subsets. For each of them consider the cardinalities of its intersections with $C\log^2 N$ residue classes involved. We have $2^N$ subsets and just $N^\{Clog^2N}=e^{O(\log^3 N)}$ options. So two different sets have the same vector of cardinalities. If the corresponding sets intersect, just remove the common part. $P(M)<C\sqrt N$ is plausible but I'd like to know if it will be of any use for the OP before giving it any thought. –  fedja Dec 16 '11 at 14:13