# Farey Dissection

Standard

The Farey sequence $\mathcal{F}_n$ of order $n$ is the ascending sequence of irreducible fractions between 0 and 1, whose denominators do not exceed $n$. This sequence was discovered by Charles Haros in 1806, but Augustin-Louis Cauchy named it after geologist John Farey.

Thus $\frac{h}{k}$ belongs to $\mathcal{F}_n$ if $0\leq h\leq k\leq n$ and $\text{gcd}(h,k)=1$, the numbers 0 and 1 are included in the forms $\frac{0}{1}$ and $\frac{1}{1}$. For example,
$\displaystyle{\mathcal{F}_5 = \frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}}$

Following are the  characteristic properties of Farey sequence (for proofs refer §3.3, §3.4 and §3.7 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers):

1. If $\displaystyle{\frac{h}{k}}$ and $\displaystyle{\frac{h'}{k'}}$ are two successive terms of $\mathcal{F}_n$, then $kh'-hk'=1$.
2. If $\displaystyle{\frac{h}{k}}$$\displaystyle{\frac{h''}{k''}}$ and $\displaystyle{\frac{h'}{k'}}$ are three successive terms of $\mathcal{F}_n$, then $\displaystyle{\frac{h''}{k''}=\frac{h+h'}{k+k'}}$.
3. If $\displaystyle{\frac{h}{k}}$ and $\displaystyle{\frac{h'}{k'}}$ are two successive terms of $\mathcal{F}_n$, then the mediant $\displaystyle{\frac{h+h'}{k+k'}}$ of $\displaystyle{\frac{h}{k}}$ and $\displaystyle{\frac{h'}{k'}}$ falls in the interval $\displaystyle{\left(\frac{h}{k},\frac{h'}{k'}\right)}$.
4. If $n>1$, then no two successive terms of $\mathcal{F}_n$ have the same denominator.

The Stern-Brocot tree, which we saw earlier while understanding the working of clocks, is a data structure showing how the sequence is built up from 0 (=0/1) and 1 (=1/1) by taking successive mediants.

Now, consider a circle $\mathcal{C}$ of unit circumference, and an arbitrary point $O$ of the circumference as the representative of 0 (zero), and represent a real number $x$ by the point $P_x$ whose distance from $O$, measured round the circumference in the anti-clockwise direction, is $x$.

Plainly all integers are represented by the same point $O$, and numbers which differ by an integer have the same representative point.

Now we will divide the circumference of the circle $\mathcal{C}$ in the following manner:

1. We take the Farey sequence $\mathcal{F}_n$, and form all the mediants $\displaystyle{\theta = \frac{h+h'}{k+k'}}$ of the successive pairs $\displaystyle{\frac{h}{k}}$$\displaystyle{\frac{h'}{k'}}$. The first and last mediants are $\displaystyle{\frac{1}{n+1}}$ and $\displaystyle{\frac{n}{n+1}}$. The mediants naturally do not belong themselves to $\mathcal{F}_n$.
2. We now represent each mediant $\theta$ by the point $P_\theta$. The circle is thus divided up into arcs which we call Farey arcs, each bounded by two points $P_\theta$ and containing  one Farey point, the representative of a term of $\mathcal{F}_n$. Thus $\displaystyle{\left(\frac{n}{n+1},\frac{1}{n+1}\right)}$ is a Farey arc containing the one Farey point $O$.

The aggregate of Farey arcs is called Farey dissection of the circle. For example, the sequence of mediants for $n=5$, say $\mathcal{M}_5$ is
$\displaystyle{\mathcal{M}_5 = \frac{1}{6},\frac{2}{9},\frac{2}{7},\frac{3}{8},\frac{3}{7},\frac{4}{7},\frac{5}{8},\frac{5}{7},\frac{7}{9},\frac{5}{6}}$

And hence the Farey disscetion looks like:

Let $n>1$. If $P_{h/k}$ is a Farey point, and$\frac{h_1}{k_1}$, $\frac{h_2}{k_2}$ are the terms of $\mathcal{F}_n$ which precede and follow $\frac{h}{k}$, then the Farey arc around $P_{h/k}$ is composed of two parts, whose lengths are
$\displaystyle{\frac{h}{k}-\frac{h+h_1}{k+k_1}=\frac{1}{k+k_1}, \qquad \frac{h+h_2}{k+k_2}-\frac{h}{k}=\frac{1}{k(k+k_2)}}$
respectively. Now $k+k_1<2n$, since $k_1$ and $k_2$ are unequal (using the point (4.) stated above)and neither exceeds $n$; and $k+k_1>n$ (using the point (3.) stated above). We thus obtain:

Theorem: In the Farey dissection of order $n$, there $n>1$, each part of the arc which contains the representative $\displaystyle{\frac{h}{k}}$ has a length between $\displaystyle{\frac{1}{k(2n-1)}}$ and $\displaystyle{\frac{1}{k(n+1)}}$.

For example, for $\mathcal{F}_5$ we have:

Using the above result, one can prove the following result about rational approximations (for more discussion, see §6.2 of  Niven-Zuckerman-Montgomery’s An Introduction to the Theory of Numbers):

Theorem: If $x$ is a real number, and $n$ a positive integer, then there is an irriducible fraction $\displaystyle{\frac{h}{k}}$ such that $0 and $\displaystyle{\left| x-\frac{h}{k}\right| \leq \frac{1}{k(n+1)}}$

One can construct a geometric proof of Kronceker’s theorem in one dimension using this concept of Farey dissection. See §23.2 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers  for details.

# Understanding Geometry – 2

Standard

If you want to brush up your high school geometry knowledge, then KhanAcademy is a good place to start. For example, I learned a new proof of Pythagoras Theorem (there are 4 different proofs on KhanAcademy) which uses scissors-congruence:

In this post, I will share with you few theorems from L. I. Golovina and I. M. Yaglom’s “Induction in Geometry ”  which I learned while trying to prove Midpoint-Polygon Conjecture.

Theorem 1: The sum of interior angles of an n-gon is $2\pi (n-2)$.

Theorem 2: The number of ways in which a convex n-gon can be divided into triangles by non-intersecting diagonals is given by

$\displaystyle{\frac{2(2n-5)!}{(n-1)!(n-3)!}}$

Theorem 3: Given a $\triangle ABC$, with $n-1$ straight lines $CM_1, CM_2, \ldots CM_{n-1}$ drawn through its vertex $C$, cutting the triangle into $n$ smaller triangles $\triangle ACM_1, \triangle M_1CM_2, \ldots, \triangle M_{n-1}CB$. Denote by $r_1, r_2, \ldots r_n$ and $\rho_1, \rho_2, \ldots, \rho_n$ respectively the radii of the inscribed and circumscribed circles of these triangles (all the circumscribed circles are inscribed within the angle $C$ of the triangle) and let $r$ and $\rho$ be the radii of the inscribed and circumscribed circles (respectively) of the $\triangle ABC$ itself. Then

$\displaystyle{\frac{r_1}{\rho_1} \cdot\frac{r_2}{\rho_2} \cdots\frac{r_n}{\rho_n} =\frac{r}{\rho} }$

Theorem 4: Any convex n-gon which is not a parallelogram can be enclosed by a triangle whose sides lie along three sides of the given n-gon.

Theorem 5 (Levi’s Theorem): Any convex polygon which is not a parallelogram can be covered with three homothetic polygons smaller than the given one.

The above theorem gives a good idea of what “combinatorial geometry” is all about. In this subject, the method of mathematical induction is widely used for proving various theorems. Combinatorial geometry deals with problems, connected with finite configurations of points or figures. In these problems, values are estimated connected with configurations of figures (or points) which are optimal in some sense.

Theorem 6 (Newton’s Theorem): The midpoints of the diagonals of a quadrilateral circumscribed about a circle lie on one straight line passing through the centre of the circle.

Theorem 7 (Simson’s Theorem): Given a $\triangle ABC$ inscribed in the circle $S$ with an arbitrary point $P$ on this circle. Then then feet of the perpendiculars dropped from the point $P$ to the sides of the $\triangle ABC$ are collinear.

We can extend the above idea of Simson’s line to any n-gon inscribed in a circle.

Theorem 8: A 3-dimensional space is divided into $\frac{(n+1)(n^2-n+6)}{6}$ parts by $n$ planes, each three of which intersect and no four of which have a common point.

Theorem 9: Given $n$ spheres in 3-dimesnional space, each four of which intersect. Then all these spheres intersect, i. e. there exists a point belonging to all the spheres.

Theorem 10 (Young’s Theorem): Given $n$ points in the plane such that each pair of them are at a distance of at most 1 from each other. Then all these points can be enclosed in a circle of radius $1/\sqrt{3}$.

I won’t be discussing their proofs since the booklet containing the proofs and the detailed discussion is freely available at Mir Books.

Also, I would like to make a passing remark about the existence of a different kind of geometry system, called “finite geometry“. A finite geometry is any geometric system that has only a finite number of points. The familiar Euclidean geometry is not finite because a Euclidean line contains infinitely many points. A geometry based on the graphics displayed on a computer screen, where the pixels are considered to be the points, would be a finite geometry. While there are many systems that could be called finite geometries, attention is mostly paid to the finite projective and affine spaces because of their regularity and simplicity. You can learn more about it here: http://www.ams.org/samplings/feature-column/fcarc-finitegeometries

# Kissing Circles

Standard

In mathematics there are number of named theorems, consider following:

Kissing Circle Theorem: If four circles are tangent to each other at six distinct points, and the circles have curvatures ki (for i = 1, …, 4) then:
$(k_1+ k_2 +k_3 + k_4)^2 = 2(k_1^2 + k_2^2 + k_3^2 + k_4^2)$.
By solving this equation, one can construct a fourth circle tangent to three given, mutually tangent circles

The curvature (or bend) of a circle is defined as k = ±1/r, where r is its radius. The larger a circle, the smaller is the magnitude of its curvature, and vice versa.

This Theorem is more commonly known as : Descartes Theorem.

Author: Jiuguang Wang (http://bit.ly/1PZbRae)

For proof of this Theorem, refer: http://euler.genepeer.com/from-herons-formula-to-descartes-circle-theorem/

I want to share the poem explaining above Theorem: (published in Nature, June 1936)

The Kiss Precise

For pairs of lips to kiss maybe
Involves no trigonometry.
‘Tis not so when four circles kiss
Each one the other three.
To bring this off the four must be
As three in one or one in three.
If one in three, beyond a doubt
Each gets three kisses from without.
If three in one, then is that one
Thrice kissed internally.

Four circles to the kissing come.
The smaller are the benter.
The bend is just the inverse of
The distance from the center.
Though their intrigue left Euclid dumb
There’s now no need for rule of thumb.
Since zero bend’s a dead straight line
And concave bends have minus sign,
The sum of the squares of all four bends
Is half the square of their sum.

To spy out spherical affairs
An oscular surveyor