Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?$$

share|cite|improve this question
It's confusing to use lower-case letters to denote sets; usually sets are denoted by upper-case letters. – Qiaochu Yuan Nov 1 '12 at 6:19
Thank you, Qiaochu Yuan. – fmkatz Nov 1 '12 at 6:22
The rationals with odd denominator in reduced form? – ronno Nov 1 '12 at 6:38
@ronno, do you mean odd numerator? That would've been my guess. – Christopher A. Wong Nov 1 '12 at 6:53
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. – Esteban Crespi Nov 1 '12 at 10:21
up vote 1 down vote accepted

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.

share|cite|improve this answer
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.) – 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.

share|cite|improve this answer
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$. – Esteban Crespi Nov 1 '12 at 10:34
@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$. – 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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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