Let $\mathbb{Q}[n]$ be the set of rational numbers with denominator $\le n$ and for any $X\subseteq \mathbb{Q}$, let $X[n]=X\cap \mathbb{Q}[n]$.

Is there a set of rational numbers, X, such that for any interval Y of rationals: $$\underset{n\to \infty }{\mathop{\lim }}\,\frac{card(X[n]\cap Y)}{card(\mathbb{Q}[n]\cap Y)} = 1/2 ?$$

  • $\begingroup$ It's confusing to use lower-case letters to denote sets; usually sets are denoted by upper-case letters. $\endgroup$ – Qiaochu Yuan Nov 1 '12 at 6:19
  • $\begingroup$ The rationals with odd denominator in reduced form? $\endgroup$ – ronno Nov 1 '12 at 6:38
  • $\begingroup$ @ronno, do you mean odd numerator? That would've been my guess. $\endgroup$ – Christopher A. Wong Nov 1 '12 at 6:53
  • $\begingroup$ I think that the proportion of fractions with even numerator and denominator bounded by $N$ is aproximately one third, and the same for even denominator. $\endgroup$ – Esteban Crespi Nov 1 '12 at 10:21
  • $\begingroup$ A good candidate for your set $X$ with a very simple description is the set of reduced fractions $a/b$ with $$ a\cdot b \equiv 0 \pmod{3} $$ $\endgroup$ – Esteban Crespi Nov 1 '12 at 11:22

As I mentioned in a comment above there is a nice set $X$ containing half the rationals with a very simple description: the set of reduced fractions $a/b$ with $\operatorname{gcd}(ab,3)=1$.

To see it, we can map each reduced fraction $a/b$ to the pair $(x,y) \equiv (a,b) \pmod{3}$. There are 8 possible pairs $(x,y)$: $$ (0,1),(0,2),(1,0),(2,0),(1,1),(1,2),(2,1),(2,2) $$ if we can prove that reduced fractions in an interval $Y$ are uniformly distributed between these 8 pairs then we have the result.

It is clearly enough to prove this for an interval $Y = [0,\lambda)$ for some real $\lambda > 0$. Lets fix a pair $(x,y)$ and call $A_{(x,y)}(n)$ the number of fractions $a/b$ with $b\le n$, $\operatorname{gcd}(a,b)=1$, $a < \lambda b$, and $(a,b)\equiv(x,y\pmod{3}$ ie the horrid sum;

$$ A_{(x,y)}(n) = \sum_{b\le n}\sum_{\begin{matrix}\operatorname{gcd}(a,b)=1\\(a,b)\equiv (x,y) \pmod{3}\\a \le \lambda b\end{matrix}} 1 $$

Now we use the Möbius identity: $$ \sum_{d \vert \operatorname{gcd}(a,b)}\mu(d) = \begin{cases}1 \quad&\text{if }\operatorname{gcd}(a,b)=1\\0&\text{otherwise}\end{cases} $$ to get

$$ A_{(x,y)}(n) = \sum_{b\le n}\sum_{\begin{matrix}(a,b)\equiv (x,y) \pmod{3}\\a \le \lambda b\end{matrix}} \sum_{d\vert \operatorname{gcd}(a,b)} \mu(d) $$

We can invert this sums puting $b = kd, a = td$ and then $t < \lambda k$ so we have

$$ A_{(x,y)}(n) = \sum_{d\le n} \mu(d) \sum_{\begin{matrix}kd\le n\\kd\equiv y\pmod{3}\end{matrix}}\sum_{\begin{matrix}t<\lambda k \\td\equiv x\pmod{3}\end{matrix}} 1 $$

In the outer sum we can limit ouselves to integers $d$ coprime with 3, (if $3 \vert d$ as $(x,y)\not\equiv (0,0)\pmod{3}$ there is nothing to sum) so we have:

$$ \begin{align} A_{(x,y)}(n) &= \sum_{\begin{matrix}d\le n\\d\not\equiv 0\pmod{3}\end{matrix}} \mu(d) \sum_{\begin{matrix}kd\le n\\kd\equiv y\pmod{3}\end{matrix}}\sum_{\begin{matrix}t<\lambda k \\td\equiv x\pmod{3}\end{matrix}} 1\\ &=\sum_{\begin{matrix}d\le n\\d\not\equiv 0\pmod{3}\end{matrix}} \mu(d) \sum_{\begin{matrix}kd\le n\\kd\equiv y\pmod{3}\end{matrix}} \left(\frac{\lambda k}3 + O(1)\right) \\ &=\sum_{\begin{matrix}d\le n\\d\not\equiv 0\pmod{3}\end{matrix}} \mu(d) \left( \frac{ \lambda n^2}{18d^2} + O(n/d) \right)\\ &=\frac{\lambda n^2}{18}\sum_{\begin{matrix}d=1\\d\not\equiv 0\pmod{3}\end{matrix}}^\infty \frac{\mu(d)}{d^2} + O(n) + O(n\log n) \end{align} $$

We can evaluate the constant in the last equation, call $$ B = \sum_{\begin{matrix}d=1\\d\not\equiv 0\pmod{3}\end{matrix}}^\infty \frac{\mu(d)}{d^2} $$ then $$ B - \frac{B}{9} = \sum_{\begin{matrix}d=1\\d\not\equiv 0\pmod{3}\end{matrix}}^\infty \frac{\mu(d)}{d^2} +\sum_{\begin{matrix}d=1\\d\not\equiv 0\pmod{3}\end{matrix}}^\infty \frac{\mu(3d)}{(3d)^2} = \sum_{d=1}^\infty \frac{\mu(d)}{d^2} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}$$ and so: $$ B = \frac{27}{4\pi^2} $$ and finally $$ A_{(x,y)}(n) = \frac{3\lambda }{8\pi^2} n^2 + O(n\log n) $$ so each pair $(x,y)$ have ultimately the same proportion $1/8$ of all reduced fraction in the interval, as was to be shown.

Note: I suppose that with some additional work it can be proven that for a given modulus $m$ the reduced fractions $a/b$ are uniformly distributed when reducing mod $m$ between the pairs $(x,y)$ such that $\operatorname{gcd}(x,y,m)=1$. And then we could find sets containing any given proportion of the rationals with the same procedure.

  • $\begingroup$ Wow. Thank you. That's the kind of explicit solution I was hoping for - though, I must admit, it will take me a while to work through and understand the proof. (The proof certainly has enough detail; I'm just weak on the number theory.) $\endgroup$ – fmkatz Nov 3 '12 at 22:27

Yes. Let $\phi(n)$ be the number of rationals in $[0,1)$ with denominator (when in reduced form) exactly equal to $n$. This is the Euler totient function (OEIS:A000010), and while it jumps around, on average it grows linearly, such that $\sum_{k=1}^{n}\phi(k)\sim 3n^2/\pi^2$, and clearly $\phi(n) \le n$. Define the indicator variable $a_n$ recursively: $a_1=1$, and $a_n=1$ for $n>1$ if $\sum_{k=1}^{n-1}a_{k}\phi(k) < \frac{1}{2} \sum_{k=1}^{n-1}\phi(k);$ otherwise $a_n=0$. Then the set consisting of all rational numbers with denominator $n$ such that $a_n=1$ satisfies the given condition. For each new denominator $n$, we are including rationals with that denominator if the density so far is less than $1/2$. Because the contribution to the density from rationals with denominator $n$ decreases to zero (as $1/n$), the density converges to $1/2$ as $n\rightarrow\infty$. The generalization to fractions other than $1/2$ is obvious.

  • $\begingroup$ I think there something missing in the right hand side of the inequality $\sum_{k=1}^{n-1} a_k\phi(k) < 1/2$, I suppose you mean $<\frac{1}{2}\sum_{k=1}^{n-1} \phi(k)$? On the other hand, even if it is probably true, I can't see how to prove that this construction works for all the intervals $Y$. $\endgroup$ – Esteban Crespi Nov 1 '12 at 10:34
  • $\begingroup$ @EstebanCrespi: You're right about the missing term, thanks. It works for any interval because the number of rationals with denominator $n$ in an interval of length $\lambda$ is $\lambda \phi(n) + o(n)$ as $n \rightarrow \infty$... that is, the corrections grow much more slowly than $n$. $\endgroup$ – mjqxxxx Nov 1 '12 at 12:20

The probabilistic method is well suited to such settings...

Order the positive rationals as $\{q_n\mid n\geqslant1\}$ in any way you prefer (for example, ordering the reduced fractions $p/q$ first along the increasing values of $p+q$ and then along the increasing values of $p$ in case of equal $p+q$).

Let $(\xi_n)_{n\geqslant1}$ denote an i.i.d. sequence of Bernoulli random variables such that, for every $n$, $\mathbb P(\xi_n=1)=\mathbb P(\xi_n=0)=\frac12$. Let $X\subseteq\mathbb Q_+$ denote the random set $X=\{q_n\mid n\in N\}$ where $N=\{n\geqslant1\mid\xi_n=1\}$.

Then the law of large numbers asserts that $X$ is almost surely a solution, for every fixed interval $Y=(a,b)$ with $0\leqslant a\lt b$ rationals. There are countably many such intervals $Y$ hence $X$ is almost surely a solution, simultaneously for all of them.

To get a suitable random subset of $\mathbb Q$, do the same thing, independently, with $\{-q_n\mid n\geqslant1\}$ (or start from any ordering of $\mathbb Q$).

To realize any density $\alpha$ in $(0,1)$ instead of $\frac12$, use an i.i.d. sequence $(\xi^\alpha_n)_{n\geqslant1}$ of Bernoulli random variables such that, for every $n$, $\mathbb P(\xi^\alpha_n=1)=\alpha$ and $\mathbb P(\xi^\alpha_n=0)=1-\alpha$. This has the additional advantage to show that one can realize each set $X_\alpha$ with density $\alpha$ in a way such that $X_\alpha\subseteq X_\beta$ (and $X_\alpha\subset X_\beta$ almost surely) for every $\alpha\lt\beta$.


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.