Programming

Booklet of Maupassant's
Pierre and Jean (91 pp.)

Sometimes it's nice to have a printed booklet of a web page or pdf file — half letter-size (5½ x 8½), about the size of many printed books. There will be a limit on the number of pages short of book-binding (!). The image here shows Maupassant's Pierre and Jean at 91 pages, that's about the upper limit. This story takes 23 sheets, considering that four pages are printed on each sheet; folding and stapling more sheets than that becomes difficult. I'll walk through the steps from web page to booklet. The requirements to do this are as follows:

Gerbert's abacus with representative numbers

Gerbert of Aurillac was a Benedictine monk from this small village in south-central France who was born about 950 AD and died in 1003. He was a great teacher and scholar, politician and church leader. He became Pope Sylvester II in 999 and served in that role till his death. He was the first French pope and the only mathematician to become pope. And mathematician he was, sent as a young man by his abbot to study in Christian Spain, bordering Al-Andalus, then a shining light of Islamic civilization. The first documented appearance of the Hindu-Arabic numerals in Christian Europe was in 976 in a manuscript by Vigila, a monk in the vicinity of Barcelona, then a Christian outpost in northern Spain near where Gerbert resided from 967 to 970. Gerbert brought the Hindu-Arabic numerals he encountered in Spain back to Christian Europe for an abacus / counting board he invented which was subsequently named after him.

How CORDIC trig works, courtesy of Wikipedia.

CORDIC is is a complex of fast algorithms to calculate transcendental functions using only table lookup, addition and bit shifting. Here I take up Volder's original scheme from 1959 to calculate sines and cosines quickly (CORDIC stands for COordinate Rotation DIgital Computer). My original article from 1992 holds up reasonably well, The CORDIC Method for Faster sin and cos Calculations, except for the Borland graphics — nice pre-Windows, but long-gone. Converting to Visual C requires only one change to the core routines related to moving from 16-bit to 32-bit integers (see comment in code). I've bundled up the source files for anyone who wants to take them into a Visual C Win 32 application, and here is a minimal C implementation. Wikipedia has a first-class article on this subject with lucid explanations and many pertinent references. Volder himself published an illuminating retrospective in 2000, explaining that the initial motivation was digitizing the navigation system of Convair's B-58 jet bomber (Volder worked for Convair).

A system of three congruences is shown on the right, but start with the simpler system:
\[ \begin{align*}
x &\equiv 1 \hspace{-.6em} {\pmod{2}}\\
x &\equiv 2 \hspace{-.6em} {\pmod{3}}.
\end{align*} \]
Values congruent \( \text{mod} \; 6 \) are certainly congruent \( \text{mod} \; 2 \) and \( \text{mod} \; 3, \) so in looking for an \( x \) solving both congruences simultaneously, it suffices to consider congruence classes \( \text{mod} \; 6 \) and in particular their smallest positive residues, namely \( 0, 1, 2, 3, 4, 5. \) We're seeking an odd number among those \( 6 \) since \( x \equiv 1{\pmod{2}}, \) one that is also congruent to \( 2 \; \text{mod} \; 3. \) \( x = 1 \) won't do, since \( 1 \equiv 1{\pmod{3}} \) neither will \( x = 3, \) since \( 3 \equiv 0{\pmod{3}}. \) \( x = 5 \) is the solution, since it satisfies both congruences, and it is the only solution \( \text{mod} \; 6. \)

Integers under \( 40 \) that are the sum of two squares. \( \color{red}{25} \) is the first that is the sum of two squares in two ways.

\( 5 = 1^2 + 2^2 \) is the sum of two squares, \( 3 \) is not. Dealing with whole numbers only, including \( 0, \) it's a bit of a riddle coming up with the criterion distinguishing the two situations. Based on empirical investigations, mathematicians in the \( 17^\text{th} \) century found the key. According to Leonard Dickson^[1]:

A. Girard (Dec 9, 1632) had already made a determination of the numbers expressible as a sum of two integral squares: every square, every prime \( 4n + 1, \) a product formed of such numbers, and the double of one of the foregoing.

The part about primes \( p \equiv 1 \; (\text{mod} \; 4) \) is central, because a product of two numbers each of which is the sum of two squares is itself the sum of two squares. Since \( 5 = 1^2 + 2^2 \) and \( 13 = 2^2 + 3^2, \) for example, \( 65 = 5 \cdot 13 \) is also the sum of two squares: \( 65 = 4^2 + 7^2. \) In fact there is a second representation: \( 65 = 1^2 + 8^2, \) and the number of representations is of interest too (this exact example is from Diophantus).

All Abelian groups of order 72.

The Fundamental Theorem of Finite Abelian Groups decisively characterizes the Abelian finite groups of a given order. Its remote origins go back to Gauss in the Disquisitiones Arithmeticae in 1801 and it was nailed down by Schering (1869) and by Frobenius and Stickelberger (1879)^[1]:

Fundamental Theorem of Finite Abelian Groups

Let \( G \) be a finite Abelian Group of order \( n. \) Then: \[ \begin{equation}{G \cong \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \cdots \times \mathbb{Z}_{n_s},} \tag{1} \end{equation} \] where \( s \) and the \( n_i \) are the unique integers satisfying \( s \geq 1, n_i \geq 2 \) for all \( i, \) and \( n_{i+1} \; | \; n_i \) for \( 1 \leq i \leq s - 1. \) And also: \[ \begin{equation}{G \cong \mathbb{Z}_{p^{\beta_1}} \times \cdots \times \mathbb{Z}_{p^{\beta_t}} \times \cdots \times \mathbb{Z}_{q^{\gamma_1}} \times \cdots \times \mathbb{Z}_{q^{\gamma_u}},} \tag{2} \end{equation} \] for \( p \) and \( q \) and all the other primes dividing \( n, \) again in a unique way, where \( \sum \beta_i \) is the exponent of the greatest power of \( p \) dividing \( n, \) \( \sum \gamma_i \) is the exponent of the greatest power of \( q \) dividing \( n, \) and so on for all the other primes dividing \( n. \)

Sergei Bernstein.

In 1912 Sergei Bernstein introduced his famous polynomials to prove the Weierstrass Approximation theorem:

If \( F(x) \) is any continuous function in the interval [0,1], it is always possible, regardless how small \( \varepsilon \), to determine a polynomial \( E_n(x) = {a_0 x^n + a_1 x^{n-1} + \cdots + a_n} \) of degree \( n \) high enough such that we have \[ {|F(x) - E_n(x)|} < \varepsilon \] for every point in the interval under consideration.

Weierstrass proved the theorem originally in 1885^[1], the very man who had earlier shown how wild a continuous function can be and in particular, how far from being smooth and subject to a Taylor expansion. Bernstein's proof was simple and based on probability theory. Maven Philip J. Davis says that "while [Bernstein's proof] is not the simplest conceptually, it is easily the most elegant".^[2]

Think of a square in the plane and how it can be rotated around its center to coincide with its original position. There are four rotations altogether — 90°, 180°, 270°, and 360° clockwise, the last bringing the square back to its original configuration. You wouldn't even know the square had been moved unless the corners were somehow distinguished. Starting at the upper left, number the corners 1, 2, 3, 4 in clockwise fashion in order to track the rotations, so that a 90° rotation is identified with the cyclic permutation \( (1 2 3 4) \). In essence, you're rotating around a z axis perpendicular to the plane through the center of the square. You can also rotate around an x, or horizontal, axis through the center of the square. The square comes out of the plane, but is pinned at the middles of the left and right edges as it rotates around that axis through space by 180° — the result is the same whichever way the rotation proceeds, the permutation \( (1 4) (2 3) \). There is a similar vertical rotation, and rotations around each diagonal. These eight rotations form a group, the rigid motions of the square, and the same can be done for any regular polygon. These are the dihedral groups, \( D_4 \) in the case of the square. \( D_n \) has \( 2n \) elements and these groups are nice concrete examples of finite groups.