# Independence of an interval and a product set in $\mathbb Z/L\mathbb Z$.

I have $k$ distinct prime numbers $\ell_1 < \dots <\ell_k$, and for each $i=1,\dots,k$, a subset $A_i$ of $\mathbb Z / \ell_i \mathbb Z$. Let $L=\ell_1 \dots \ell_k$. Now using the chinese reminder theorem, $\mathbb Z/ L \mathbb Z = \prod_{i=1}^k \mathbb Z /\ell_i \mathbb Z$, hence the subset $\prod_{i=1}^k {A_i}$ of the RHS is identified to a subset $A$ of $\mathbb Z/L \mathbb Z$ (that what I call a "product set").

Now consider an interval $I$ of $\mathbb Z / \ell \mathbb Z$. I would say (that's acknowledgedly a vague definition) that $I$ and $A$ are "approximately independent" of $\frac{|A \cap I|}{|I|}$ is close to $\frac{|A|}{L}$. For exemple, when $I = \mathbb Z/L\mathbb Z$, then these two fractions are trivially equal.

Now it seems natural to believe that when $|I|$ is large with respect to the $\ell_i$, even if it is small with respect to $L=\prod_i \ell_i$, then $A$ is approximately independent to $I$.

Is this intuition true in some sense?

I apologize for this vague question: I think it makes sense as it is and it seems that any of my attempt to make it more precise will result in something false or trivial. I also have the frustrating impression that I have already seen this problem, or something very close to it (that is concerning the "independence" of product sets in $\mathbb Z / L \mathbb Z$ with other natural subsets of $\mathbb Z / L \mathbb Z$) discussed somewhere, perhaps even on MO. But I am not able to recall where, and missing even a name or keywords for this problem, I don't know where to look for. So any reference or names for this question is welcome. (PS: I don't even know how to tag this question. Please feel free to change tags)

• Adding $1$ to an element of $\mathbb{Z}/L\mathbb{Z}$, add $1$ to its remainder mod $\ell_i$ for each $i$. So, an interval is just a line with slope $(1,1,\dotsc,1)$ in the appropriately shaped torus. You assert a property of the segments of this line that is stronger than equidistribution in the torus (which would correspond to the case when all $A_i$'s are intervals themselves). A reasonable approach would be to use Cauchy--Schwarz inequality to complete the variables. – Boris Bukh Jun 10 '13 at 21:13
• Interesting. So my question would be a dynamical system question, kind of... But I don't understand what you mean by: "use Cauchy-Schwarz inequality to complete the variable" – Joël Jun 11 '13 at 0:32
• Let $\chi$ be the characteristic function of the line segment. Then subtract its mean, which is to say consider $\chi'=\chi-\mathbb{E}\chi$. Then goal is then to prove that the sum of $\chi'$ over a box $A_1\times\dots\times A_k$ is small. Pick one of $k$ variables (or more generally some small set of variables), and Cauchy-Schwarz sum in that variable. You will get a sum $\sum_{x_1\in A} (\dotsc)^2$. This sum is smaller than the corresponding sum where range of $x_1$ is not restricted. This is called "completing" a sum. As a self-promotion, look at section 6 of arxiv.org/abs/1002.2554 – Boris Bukh Jun 11 '13 at 1:54
• Of course, the first task would be work out the simpler problem where $A_1,\dotsc,A_k$ are intervals (i.e. the equidistribution problem). A possible issue is that some primes might be close to multiples of other primes, and so the rate of equidistribution might be very poor. – Boris Bukh Jun 11 '13 at 1:55
• There was a more numerical version of this question on MathOverflow a few months back. Hopefully someone will provide a link. A specialization of this is bounding Jacobsthal's function. My personal odyssey starts with the Westzynthius question 37679, and continues with several linked and related MathOverflow questions. Gerhard "Smartphone Copy-Paste Not So Good" Paseman, 2013.06.12 – Gerhard Paseman Jun 12 '13 at 21:27

I don't like to answer my own question, but I don't like to have one of my question still open when it should not be anymore. So actually, thanks to Boris Bukh's comments, which put in my mind the word "equidistribution", I eventually remembered where I saw a setting that looked a lot like my question: it is the setting of the large sieve, that I had seen before without really understanding what it was for. But if one looks for instance to Kowalski's beautiful book "The large sieve and its applications", chapter II, one sees a setting in which my question fits naturally. Using it it is an exercise to get upper bound on $\frac{|A \cap I|}{|I|}$ which are conforms to my intuition that this should be close to $\frac{|A|}{|L|}$. For lower bound I don't know, but it was actually upper bound I was interested in. Unfortunately, the upper bound I get are not quote as good as I would need, but that's my problem.
• Just wanted to point out that if you let $J$ be the complement of $I$ in $\mathbb Z/L\mathbb Z$, then an upper bound on $|A\cap J|/|J|$ can be connected to a lower bound on $|A\cap I|/|I|$. – Greg Martin Jun 17 '13 at 19:21