2
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Boris Bukh Jun 10 '13 at 21:13
  • $\begingroup$ 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" $\endgroup$ – Joël Jun 11 '13 at 0:32
  • 1
    $\begingroup$ 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 $\endgroup$ – Boris Bukh Jun 11 '13 at 1:54
  • $\begingroup$ 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. $\endgroup$ – Boris Bukh Jun 11 '13 at 1:55
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Jun 12 '13 at 21:27
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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|$. $\endgroup$ – Greg Martin Jun 17 '13 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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