Parity and Partition of the Rational Numbers. Part II: Density of the Three Parity Classes

In last week’s post, we defined an extension of parity from the integers to the rational numbers. Three parity classes were found — even, odd and none. This week, we show that, with an appropriate ordering or enumeration of the rationals, the three classes are not only equinumerate (having the same cardinality) but of equal density in ${\mathbb{Q}}$ . This article is a condensation of part of a paper [Lynch & Mackey, 2022] recently posted on arXiv.

A simple way of separating the rational numbers — ratios of whole numbers — into three subsets is given in schematic form:

$\displaystyle \mbox{Odd} = \frac{odd}{odd} \qquad \qquad \mbox{Even} = \frac{even}{odd} \qquad \qquad \mbox{None} = \frac{odd}{even}$

The term none is an initialism for neither odd nor even. Corresponding to this three-way partition, we defined three subsets of the rationals:

$\displaystyle \begin{array}{rcl} \mbox{Even:\ \ } \mathbb{Q}_E &=& \{ q\in\mathbb{Q} : q = \textstyle{\frac{2m}{2n+1}\ \mbox{for some}\ m,n\in\mathbb{Z}} \} \\ \mbox{Odd:\ \ } \mathbb{Q}_O &=& \{ q\in\mathbb{Q} : q = \textstyle{\frac{2m+1}{2n+1}\ \mbox{for some}\ m,n\in\mathbb{Z}} \} \\ \mbox{None:\ \ } \mathbb{Q}_N &=& \{ q\in\mathbb{Q} : q = \textstyle{\frac{2m+1}{2n}\ \mbox{for some}\ m,n\in\mathbb{Z}} \} \,. \end{array}$

The rational numbers are countable: they can be put into one-to-one correspondence with the natural numbers. This is also true for the sets ${\mathbb{Q}_E}$ , ${\mathbb{Q}_O}$ and ${\mathbb{Q}_N}$ . Numerical evidence indicates that, for a large cutoff of the denominator size, all three classes have about the same number of elements. We will show rigourously, using set density, that this is true.

The Density of subsets of ${\mathbb{N}}$ .

In pure set-theoretic terms, the set of even positive numbers is “the same size” as the set of all natural numbers; both are infinite countable sets. However, cardinality is a blunt instrument: with the usual ordering, every second natural number is even and, intuitively, we feel that there are half as many even numbers as natural numbers. The concept of density provides a means of expressing the relative sizes of sets that is more discriminating than cardinality.

Density — also called natural or asymptotic density — is defined for many interesting subsets of ${\mathbb{N}}$ , although not for all subsets. Assume a subset ${A}$ of ${\mathbb{N}}$ is enumerated as ${\{a_1, a_2, \dots \}}$ . We define the density of ${A}$ in ${\mathbb{N}}$ as the limit, if it exists,

$\displaystyle \rho_\mathbb{N}(A) = \lim_{n\rightarrow\infty}\ \frac{|\{a_k : a_k\le n\}|} {n} \,. \nonumber \ \ \ \ \ (1)$

Thus, if the fraction of elements of ${A}$ among the first ${n}$ natural numbers converges to a limit ${\rho_\mathbb{N}(A)}$ as ${n}$ tends to infinity, then ${A}$ has density ${\rho_\mathbb{N}(A)}$ . More generally, if ${A = \{a_1, a_2, a_3, \dots \}}$ is a subset of a countable set ${X}$ enumerated as ${\{x_1,x_2,x_3, \dots \}}$ , we define the density of ${A}$ in ${X}$ — if it exists — as

$\displaystyle \rho_{X}(A) = \lim_{n\rightarrow\infty}\ \frac{|A\cap \{x_1, x_2, \dots , x_n\}|}{n} \,. \nonumber \ \ \ \ \ (2)$

For ${X = \mathbb{N}}$ , we usually write ${\rho_\mathbb{N}(A)}$ as ${\rho(A)}$ . For ${A = \mathbb{N}_E}$ or ${A = \mathbb{N}_O}$ , we have ${\rho(A) = \textstyle{\frac{1}{2}}}$ , as might be expected. This is consistent with our intuitive notion that ${50\%}$ of the natural numbers are even and ${50\%}$ are odd.

Let us now rearrange the natural numbers into a set ${F}$ such that there are twice as many even as odd numbers in ${F}$ . We reorder ${\mathbb{N}}$ so that each odd number is followed by two even ones:

$\displaystyle F = \{ 1, 2, 4, 3, 6, 8, 5, 10, 12,\ \dots\ , 2n-1, 4n-2, 4n, \dots \} \,.$

It is easy to see that ${\rho_F(\mathbb{N}_E) = \frac{2}{3}}$ and ${\rho_F(\mathbb{N}_O) = \frac{1}{3}}$ .

Proceeding further, we can construct a set ${H}$ in which the ${n}$ -th odd number is followed by ${n}$ even numbers. We find that ${\rho_H(\mathbb{N}_E)=1}$ , so that “almost all the elements of ${H}$ are even”. These examples make it clear that density depends strongly on the ordering of the set. We will show that, for the rational numbers with the Calkin-Wilf and Stern-Brocot orderings defined below,

$\displaystyle \rho_\mathbb{Q}(\mathbb{Q}_E) = \rho_\mathbb{Q}(\mathbb{Q}_O) = \rho_\mathbb{Q}(\mathbb{Q}_N) = \tfrac{1}{3} \,. \nonumber \ \ \ \ \ (3)$

The Calkin-Wilf Ordering

The initial rows of the Calkin-Wilf tree.

There are many exhaustive sequences of rationals, one attractive option being the Calkin-Wilf tree [Calkin & Wilf, 1999]. The Calkin-Wilf tree is complete: it includes all positive rational numbers and each such number occurs precisely once. The tree starts with the root value ${{1}/{1}}$ , and everything springs from this root (see Figure) Each rational in the tree has two “children”: for the entry ${m/n}$ , the children are ${m/(m+n)}$ and ${(m+n)/n}$ . The “left child” ${m/(m+n)}$ is always smaller that ${1}$ while the “right child” ${(m+n)/n}$ is always greater that ${1}$ (mnemonic: the children are “top over sum” and “sum over bottom”). The pattern of parity from one row of the Calkin-Wilf diagram to the next is simple. Denoting odd parity, even parity and no parity by ${o}$ , ${e}$ and ${n}$ respectively, the parity transfer rules are as follows:We can show that the elements of the Calkin-Wilf tree are remarkably regular, with the pattern ${(o, n, e)}$ repeating interminably (see Figure at head of this post). Thus, the parity of any specific term in the tree can easily be deduced. This implies that, with the ordering of ${\mathbb{Q}}$ corresponding to the Calkin-Wilf tree, the three parity classes all have the same density.

Theorem 1. Let ${\mathbb{Q}^{+}}$ be ordered with the Calkin-Wilf tree. Then ${\mathbb{Q}^{+}}$ may be partitioned into three parity classes, ${\mathbb{Q}_E^{+}}$ , ${\mathbb{Q}_O^{+}}$ and ${\mathbb{Q}_N^{+}}$ , each having asymptotic density ${\frac{1}{3}}$ .

Proof. The proof follows by using the transfer rules and an inductive argument. Full details are in the arXiv preprint (Lynch and Mackey, 2022).

The Calkin-Wilf tree enumerates the positive rationals ${\mathbb{Q}^{+}}$ . This enumeration, which we write ${\{q_n:n\in\mathbb{N}\}}$ , can be extended in a natural way to the full set of rationals: we enumerate ${\mathbb{Q}}$ by ${\{0,q_1,-q_1,q_2,-q_2, \dots \}}$ . With this ordering, the rational numbers split into three parts, each of asymptotic density ${\frac{1}{3}}$ :

$\displaystyle \rho_\mathbb{Q}(\mathbb{Q}_E) = \rho_\mathbb{Q}(\mathbb{Q}_O) = \rho_\mathbb{Q}(\mathbb{Q}_N) = \tfrac{1}{3} \,. \nonumber \ \ \ \ \ (4)$

The Stern-Brocot Ordering

The initial rows of the Stern-Brocot tree.

The Stern-Brocot tree [Graham, Knuth and Patashnik, 1994, pg.116] is another ordering of ${\mathbb{Q}}$ very similar to the Calkin-Wilf tree. The numbers at each level are formed from the mediants of adjacent pairs of numbers above (see Figure) The mediant of two (reduced) rationals, ${m_1/n_1}$ and ${m_2/n_2}$ is defined as ${M(m_1/n_1, m_2/n_2):= (m_1+m_2)/(n_1+n_2)}$ . We note that the parity of the mediants of two numbers of different parity is the third parity:

$\displaystyle M(e,o) = n \,,\qquad M(o, n) = e \,,\qquad M(n,e) = o \,. \nonumber \ \ \ \ \ (5)$

We now show that, with the ordering of the Stern-Brocot tree, the split into three sets of equal density holds true.

Theorem 2. For the order of ${\mathbb{Q}}$ induced by the Stern-Brocot process, the asymptotic density of each parity class, ${\mathbb{Q}_E}$ , ${\mathbb{Q}_O}$ and ${\mathbb{Q}_N}$ , is ${\frac{1}{3}}$ .

Proof. The proof follows by using the transfer rules and an inductive argument. Full details are in the arXiv preprint (Lynch and Mackey, 2022).

Summary.

We have extended parity from the integers to the rational numbers. Three parity classes — even, odd and none — were found. The Calkin-Wilf tree was found to have a remarkably simple parity pattern, with the sequence `odd/none/even’ repeating indefinitely. Using the natural density, which provides a means of distinguishing the sizes of countably infinite sets, the three parity classes are equally dense in the rationals. The same conclusion holds for the Stern-Brocot tree.

Sources

Calkin, Neil and Wilf, Herbert S., 1999: Recounting the rationals. American Mathematical Monthly, 107, (4), 360–363. PDF

Graham, Ronald L., Knuth, Donald E. and Patashnik, Oren, 1994: Concrete Mathematics, Second Edn., Addison-Wesley Publ.~Co., ISBN: 978-0-2015-5802-9.

Lynch, Peter & Michael Mackey, 2022: Parity and Partition of the Rational Numbers. Preprint on arXiv.

Lynch, Peter, 2018: That’s Maths: Listing the Rational Numbers II: The Stern-Brocot Tree. Post.

Lynch, Peter, 2018: That’s Maths: Listing the Rational Numbers III: The Calkin-Wilf Tree. Post.

ThatsMaths