Ford circles are named after
Ford, Sr. (1886-1967)
who introduced the concept in 1938
(American Mathematical Monthly, volume 45, 9, pp. 586-601).
The famous Ford-Fulkerson optimisation algorithm (1956) is named after his son,
Lester Randolph Ford, Jr. (who was born in 1927).
The Ford circle of the rational number p/q (expressed in lowest terms)
is the circle of diameter 1/q2 tangent
from above to the x-axis at point p/q.
Ford circles of irrational numbers are of radius 0 and reduce to a single point.
The line y = 1 is sometimes considered to be a degenerate Ford circle
of infinite radius associated with
¥ (unsigned infinity).
Remarkably, two Ford circles never overlap.
The Ford circles associated with two irreducible fractions
a/b and c/d are
tangent to each other if, and only if,
ad and bc are consecutive integers.
The largest Ford circle between such tangent Ford circles is associated
with the mediant fraction
(a+c) / (b+d).
The nth Farey series is the increasing sequence of all
the rational numbers (irreducible fractions) between 0 and 1
whose denominators are n or less.
For example, the sixth Farey series is:
0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1
Each term of a Farey series is the mediant of the two terms that
(the three corresponding Ford circles are thus pairwise tangent).
In 1816, the geologist
Sen. (1766-1826) published this remark in a
short letter to
the Philosophical Magazine, entitled
"On a curious Property of vulgar Fractions".
This attracted the attention of Augustin Cauchy, who supplied a proof in
Exercises de mathématiques (1816).
Cauchy is responsible for the enduring attribution of these finite sequences to Farey.
In 1802 (14 years before Farey and Cauchy)
one C. Haros had studied the 99th Farey series,
in a paper about the approximation of decimal fractions by common fractions.
Some Farey series appear in the Stern-Brocot tree,
A binary tree containing a single occurrence of every positive rational.
Let's label each node of a binary tree with a triplet of integers so that
the left and right offsprings of a node labeled (x,y,z) are respectively labeled
(x,x+y,y) and (y,y+z,z).
The label of the root determines the labels assigned to all the nodes.
Let's call numerator tree the tree so labeled whose root bears the label
Call denominator tree the one whose root is labeled (1,1,0).
We use a graphical representation, where each offspring is assigned a box
half the size of its parent's.
In each box, only the middle integer of the "label" is shown.
The other two values are simply found at the top of each bounding vertical line.
(In the middle of an ascendant's box, except for a leftmost or rightmost node.)
The Stern-Brocot tree is the binary tree whose nodes are
labeled with the rational number p/q,
where p (resp. q) is the middle integer in the label of the corresponding node
of the above numerator tree (resp. denominator tree).
Remarkably, all rational numbers are thus obtained
in irreducible form.
The rational numbers which appear in the left half of the tree are between 0 and 1.
A Farey series is obtained when the
numbers in the first half of a line are interspersed with the numbers sitting
at the top of the box boundaries.
For example, the fourth Farey series is obtained from the last line shown above:
0, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1
Any positive rational appears
once and only once in the Stern-Brocot tree, at a location determined by its
continued fraction expansion (CFE)...
To reach the positive rational whose CFE is
go q0 steps right, q1 steps left, q2 steps right, and
so forth alternately... then
go back one step (either that,
or perform only qn-1 steps in the last stage).
The Stern-Brocot tree was discovered (at least) twice:
- In 1858 by Moritz Stern
(Über eine zahlentheoretische Funktion. Crelle's Journal 55:193-220).
Moritz Abraham Stern (1807-1894)
is credited with noticing the genius of his student
Riemann (1826-1866) early on at Göttingen.
Stern was also one of the main teachers of
Dedekind (1831-1916) who was Gauss's last student
(receiving his doctorate in 1852).
In 1858, Stern was appointed to succeed
Gauss (1777-1855) as professor
ordinarius of mathematics at Göttingen University.
He was the first jewish Ordinarius
in a German university.
- In 1861, by Achille Brocot
(Calcul des rouages par approximation, nouvelle méthode.
Revue Chronométrique 3:186-194).
Achille Brocot (1817-1878)
was a famous innovative clockmaker,
who stumbled upon the Stern-Brocot tree while computing optimal gear ratios.
de Stern-Brocot" by Jean-Paul Davalan
Eisenstein-Stern Diatomic Sequence
Also known as Dijkstra's "fusc" function, the sequence of the so-called
"Stern numbers" forms a
recursively defined integer sequence :
b(0) = 0 , b(1) = 1 ,
b(2n) = b(n), b(2n+1) = b(n) + b(n+1)
In 1982, Edsger Wybe Dijkstra
called the sequence of Stern numbers "fusc" because it possesses
a curious obfuscated property:
If the sum of two indices, n and m, is
a power of 2, then b(n) and b(m) are coprime.
The number of ways to express n as a sum of powers of 2
without using more than two equal terms turns out to be b (n+1).
(This provides an obscure alternate way to define Stern numbers.)
The sequence of the ratios of two consecutive Stern numbers
un = b(n) / b(n+1) runs through all nonnegative
rational numbers (in reduced form) just once!
0, 1,1/2, 2, 1/3, 3/2, 2/3, 3,1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, ...
Moshe Newman is credited
with the discovery of a very nice alternate definition of this rational sequence,
uo = 0 and
un+1 = f (un )
f (x) = 1 / (1 + 2 ë x û - x )
When this sequence is displayed as
a binary tree, each level features
the same fractions as in the Stern-Brocot tree, but
at different locations:
The respective positions [0 = leftmost] of a given fraction
are mirror images in binary numeration.
In this tree, the left child of a / b
is a / (a+b) ,
the right child is (a+b) / b.
Thus, if the parent fraction is in lowest terms, so are both offsprings...
References and History :
M. Eisenstein (1823-1852)
"Eine neue Gattung zahlentheoretischer Funktionen [...]" (1850)
Verhandlungen der Königlich Preussischen Akademie
der Wissenschaften zu Berlin
Moritz A. Stern (1807-1894)
"Über eine zahlentheoretische Funktion" (1858)
Journal für die reine und angewandte Mathematik,
C. Giuli and R. Giuli
"A primer on Stern's Diatomic Sequence" (1979; some errors)
17:2 (1979) 103-108, 246-248, 318-320.
Neil J. Calkin
and Herbert S. Wilf
"Recounting the Rationals"
July 6, 1999 ]
The American Mathematical Monthly, 107
(April 2000) 360-363.
"Tree of fractions and Dijkstra's fusc function"
(March 27, 2002)
Seminar on Number Theory and Algebra, University of Zagreb.
Jeremy Gibbons, David Lester and Richard Bird
"Enumerating the Rationals"
[ pdf ]
Pick's Formula (or Pick's Theorem)
The surface area of a planar lattice polygon is I + ½ B
- 1, where:
- I is the number of lattice points in the polygon's interior.
- B is the number of lattice points on the polygon's boundary
(i.e., at the vertices or on the edges).
This result is due to
(1852-1949) who published it in 1899 ("Geometrisches zur Zahlenlehre"
Sitzungber. Lotos, Naturwissen Zeitschrift Prague,
19, pp. 311-319).
Pick was instrumental in the appointment of Albert Einstein to the German University of Prague
and became a close friend of Einstein's during his stay in Prague (1911-1913).
Pick's theorem became famous in 1969, when it appeared in the
third edition of the popular book Mathematical Snapshots which
Steinhaus (1887-1972) had first published in 1938...
Lattice points (which Pick called reticular points)
are points whose coordinates are integers. A lattice polygon is
a polygon whose vertices are lattice points.
In the plane, a lattice polygon may be dissected into lattice triangles which
have no lattice points (besides their vertices) inside of them or on their borders.
Therefore, Pick's formula for the area of a lattice polygon is a consequence of the
following (surprising) special case:
A lattice triangle which has no lattice points besides its vertices
(i.e., inside of it,
or on its edges) has a surface area of ½