# Uniformly at Random

## Allies and enemies

Champlain’s new settlement was founded in the summer of 1608 at “Kebec” or the “narrows” of the St. Lawrence.  (Thus making this the year of its 400th anniversary.)  The same year he was invited by a Montagnais-Algonquin-Huron coalition to join forces with them in an raid on their old enemies, the Iroquois.  The attack was to take place the next year.  Champlain agreed to join the coalition, expecting that a sufficiently impressive demonstration of force against the Iroquois would deter them from future attacks against his Indian allies.  Establishing such a peace would in turn be congenial to the development of the fur trade.

In 1609 Champlain set out with his Indian allies and began his journey to the Iroquois country.  They traveled up the St. Lawrence, then, just below Montreal, took the Richelieu River southward into Lake Champlain.  They encountered a Mohawk war party at the southern end of the lake.  Only two other Frenchmen had made it this far with Champlain.  The allies engaged the Mohawks on shore.  The battle began with Champlain discharging his arquebus to devastating effect: a single shot took out three Mohawk warriors.  When the other Frenchmen fired their weapons with similar effects, the Mohawks turned and fled.  The allies pursued, winning a remarkable victory and capturing several prisoners.  The victory was followed by the standard (among the particular nations involved) torture and cannibalism of (some of) the captives.

After his return from Mohawk country to Quebec, Champlain left the colony in the hands of subordinates and returned to France.  He returned the following year, 1610, to Quebec, and again, when his Indian allies requested his aid, fought another battle against the Mohawks.  The allies were again victorious.  After suffering two severe defeats, the Mohawks avoided further conflict with the French for many years.

Written by uncudh

November 29, 2008 at 3:16 am

## The singing contest

In the 1830’s and 1840’s the Finnish physician and scholar Elias Lönnrot traveled throughout  the Finnish district of Karelia, collecting and recording various traditional folk songs.  He arranged and edited this source material to create the Kalevala, the great national epic of Finland.  The influence of the Kalevala on the writings of Tolkien is well-known.  (One can find several essays on the subject in the collection Tolkien and the Invention of Myth.)  The most notable example of such influence can perhaps be seen in Tolkien’s tale of Turin, which contains several themes and plot elements that are strikingly similar to those of the tale of Kullervo from the Kalevala.  This too is a subject that has been much studied.

In Tolkien’s world, as in the Kalevala, much of the “magic” is accomplished through song: Luthien enchants Morgoth through song; the magic of Tom Bombadil seems strongly connected to his singing; the world itself is created through the “Song of the Ainur”.  The following passage from the Kalevala (Magoun’s translation) describes a singing duel between the “wizards” Väinämöinen and Joukahainen:

He sang the cap off the man’s head    into the peak of a cloudbank,
he sang the mittens off his hands    into pond lilies,
then his blue broadcloth coat    to the heavens as a cloud patch,
the soft woolen belt from his waist    into stars throughout the heavens.
He bewitched Joukahainen himself,    sang him into a fen up to the loins,
into a grassy meadow up to the groin,    into a heath up to the armpits.

Written by uncudh

November 28, 2008 at 8:23 pm

Posted in literature

Tagged with , ,

## The Ile-Ste-Croix settlement

The French made several attempts throughout the 1500’s to establish colonies in North America.  Without exception they all failed.  Champlain’s exploratory expedition of 1603 was followed in 1604 by a new French project to establish a colony in the Americas.  This expedition was led by Pierre Dugua, sieur de Mons.  He established in 1604 a settlement on the tiny island of Ile-Ste-Croix, just off the American coast at approximately the Maine-New Brunswick border.  The location was poorly chosen.  After a terrible winter, the settlement was relocated across the Bay of Fundy to Port-Royal, in what is now Nova Scotia.  In each of the years 1604, 1605, and 1606, the French sent out ships to explore the New Brunswick and New England coasts.  The expeditions were led by Champain, de Mons, and Poutrincourt respectively.  Only Champlain’s was reasonably successful; the latter two were spoiled by certain . . . unpleasantness with the Indians that the French met during the expeditions.

Unfortunately for the settlement at Port-Royal, the fashion of hats changed in Paris.  Beaver pelt hats were now wildly popular.  Increased demand for beaver furs allowed certain business interests to pressure King Henri IV to revoke de Mons’s monopoly of the fur trade, which had allowed him to provide financial backing for the settlement project.  With the loss of the monopoly, de Mons’s company failed.  The settlers were recalled to France and the settlement abandoned in 1607.

in 1608 de Mons convinced the king to give him another chance.  The king complied, granting him a 1 year monopoly.  De Mons put together a new expedition, this time led by Champlain, who planned his new settlement in the St. Lawrence valley rather than the coast of Acadia.

Written by uncudh

November 28, 2008 at 6:11 pm

Posted in history

Tagged with , ,

## Some more curious continued fractions

We have previously observed that $e$ has the remarkably regular continued fraction expansion $e = [2; 1, 2, 1, 1, 4, 1, 1, 6,\ldots]$.

Another curious continued fraction is the following:

$\sum_{n \geq 1} 2^{-\lfloor 2n/(\sqrt{5}-1) \rfloor} = [0; 2^0, 2^1, 2^1, 2^2, 2^3, 2^5, 2^8, 2^{13}, \ldots]$,

where the exponents of the 2’s in the continued fraction are the Fibonacci numbers. This unusual continued fraction has been independently rediscovered by several authors. See, for example, Anderson, Brown, and Shiue, Proc. Amer. Math. Soc. 123 (1995), 2005-2009.

Among the most famous continued fractions are the Rogers-Ramanujan continued fractions:

$\cfrac{1}{1+\cfrac{e^{-2\pi}}{1+\cfrac{e^{-4\pi}}{1+\cfrac{e^{-6\pi}}{\vdots}}}} = \left( \sqrt{\frac{5+\sqrt{5}}{2}} - \frac{\sqrt{5}+1}{2} \right)e^{2\pi/5}$

$1-\cfrac{e^{-\pi}}{1+\cfrac{e^{-2\pi}}{1-\cfrac{e^{-3\pi}}{\vdots}}} = \left( \sqrt{\frac{5-\sqrt{5}}{2}} - \frac{\sqrt{5}-1}{2} \right)e^{\pi/5}$.

Ramanujan included these formulas in his famous 1913 letter to Hardy. Later, Hardy wrote, “[These formulas] defeated me completely. I had never seen anything in the least like them before. A single look at them is enough to show that they could only be written down by a mathematician of the highest class. They must be true because, if they were not true, no one would have had the imagination to invent them.”

Written by uncudh

November 27, 2008 at 1:50 am

Posted in math

Tagged with ,

## On the number of 1’s in the binary expansions of multiples of 3

Consider the sequence of multiples of 3: i.e., 3, 6, 9, 12, 15, 18, 21, 24 etc.  Now write these numbers in base 2 to obtain the sequence 11, 110, 1001, 1100, 1111, 10010, 10101, 11000, etc.  Look at these binary expansions and note which ones have an even number of 1’s and which ones have an odd number of 1’s.  For instance, construct the sequence whose n-th term is 0 if there is an even number of 1’s in the binary expansion of 3n and is 1 if there is an odd number of 1’s in the binary expansion of 3n.  This sequence begins 0, 0, 0, 0, 0, 0, 1, 0, etc.  If one generates (by computer) a long initial segment of this sequence, one may note that there seems to be a clear preponderance of 0’s in any initial segment of this sequence.  In fact, there appears to always be more 0’s than 1’s in any initial segment of the sequence.

Intuitively, this looks to be utterly bizarre.  One would expect the parity of 1’s in the binary expansions of 3n to be more or less random.  That is, there should sometimes be a slight preponderance of those with even parity and sometimes a slight deficit of those with even parity.  Nevertheless, one can prove definitively that in any intial segment of the sequence 0, 0, 0, 0, 0, 0, 1, 0, . . . , whose n-th term counts the parity of 1’s in the binary expansion of 3n, there are always more 0’s than 1’s.  Furthermore, the excess of 0’s over 1’s in any initial segment of length n can be bounded from below and above by $1/20 n^{\log 3 / \log 4}$ and $5n^{\log 3 / \log 4}$ respectively.

This curious result was obtained by Donald J. Newman in 1969 and appears in Proc. Amer. Math. Soc..

Written by uncudh

November 26, 2008 at 7:29 pm

Posted in math

Tagged with

Samuel de Champlain made his first voyage to Canada in 1603 as part of an expedition led by Pont-Gravé.  The expedition sailed up the St. Lawrence, stopping at the harbour of Tadoussac, at the junction of the Saguenay River and the St. Lawrence.  By a curious coincidence, at the same time a large number of Montaignais, Etchemins and Algonquins had gathered nearby to celebrate a great victory over their enemies, the Iroquois.  They were celebrating with a great tobacco-feast, or tabagie.  The French were invited to participate: they smoked tobacco with the leaders, joined in the feasting, and watched the celebratory dances.  Of this chance meeting between the French and the Indians, David Hackett Fischer writes in Champlain’s Dream:

Here was a moment of high importance in the history of North America.  Nobody had planned these events, but both French and Indian leaders were quick to see an opportunity.  The Great Tabagie marked the beginning of an alliance between the founders of New France and three Indian nations.  Each entered willingly into the relationship and gained something of value in return.  The Indians acquired a potential ally against their mortal enemies, the Iroquois.  The French won support for settlement, exploration, and trade.  The alliance that formed here would remain strong for many years because it rested on a mutuality of material interest.

Written by uncudh

November 24, 2008 at 10:23 pm

## Ramanujan’s partition congruences

Ramanujan proved several remarkable divisibility properties of the number $p(n)$ (recall that these denote the number of partitions of a positive integer $n$). One such property is that $p(5n+4)$ is always a multiple of 5. The simplest proofs of this result of which I am aware make use of the following identity of Jacobi:

$\sum_{n=-\infty}^\infty (-1)^n (2n+1) q^{n(n+1)/2} = \prod_{k \geq 1}(1-q^k)^3$.

I do not feel sufficiently ambitious to derive Jacobi’s identity here, so we shall assume it without proof and proceed accordingly, this time following Berndt, Number Theory in the Spirit of Ramanujan. Let us begin with the identity

$\sum_{n \geq 0} p(n) q^n = \prod_{k \geq 1}(1-q^k)^{-1}$.

Multiplying both sides by $q\prod_{k \geq 1}(1-q^{5k})$ gives

$\prod_{k \geq 1}(1-q^{5k})\sum_{n \geq 0} p(n) q^{n+1} = q\prod_{k \geq 1}(1-q^{5k})\prod_{k \geq 1}(1-q^k)^{-1}$,

which we may rewrite as

$\prod_{k \geq 1}(1-q^{5k})\sum_{n \geq 0} p(n) q^{n+1} = q\prod_{k \geq 1}(1-q^{5k})\prod_{k \geq 1}(1-q^k)^{-5}\prod_{k \geq 1}(1-q^k)^4$.

However, by the binomial theorem we have

$\prod_{k \geq 1}(1-q^{5k}) \equiv \prod_{k \geq 1}(1-q^k)^5 \pmod 5$,

where the mod 5 notation means the coefficients of $q^i$ on each side of the equivalence are congruent modulo 5. We therefore conclude that

$\prod_{k \geq 1}(1-q^{5k})\prod_{k \geq 1}(1-q^k)^{-5} \equiv 1 \pmod 5$,

which in turn implies that

$\prod_{k \geq 1}(1-q^{5k})\sum_{n \geq 0} p(n) q^{n+1} \equiv q\prod_{k \geq 1}(1-q^k)^4 \pmod 5$.

To show that $p(5n+4)$ is a multiple of 5 it therefore suffices to show that the coefficients of $q^{5n+5}$ in the above expression are multiples of 5. Consider then the righthand side of the equivalence. We have

$q\prod_{k \geq 1}(1-q^k)^4$

$= q\prod_{k \geq 1}(1-q^k)\prod_{k \geq 1}(1-q^k)^3$

$= q\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}\sum_{k=-\infty}^\infty (-1)^k (2k+1) q^{k(k+1)/2}$,

where we have used Euler’s Pentagonal Number Theorem to obtain the first sum and Jacobi’s Identity to obtain the second sum. Continuing, we have

$q\prod_{k \geq 1}(1-q^k)^4$

$= \sum_{j=-\infty}^\infty\sum_{k=-\infty}^\infty(-1)^{j+k}(2k+1)q^{1+(3j^2+j)/2+k(k+1)/2}$.

The exponents of $q$ in the above sum are therefore multiples of 5 when $1+(3j^2+j)/2+k(k+1)/2$ is a multiple of 5. Observe that

$2(j+1)^2 + (2k+1)^2 = 8(1+(3j^2+j)/2+k(k+1)/2) - 10j^2 - 5$,

so that $1+(3j^2+j)/2+k(k+1)/2$ is a multiple of 5 exactly when $2(j+1)^2 + (2k+1)^2$ is a multiple of 5. However, $2(j+1)^2$ can only be 0, 2, or 3 mod 5, and $(2k+1)^2$ can only be 0, 1, or 4 mod 5. Thus, $2(j+1)^2 + (2k+1)^2$ is a multiple of 5 exactly when both $2(j+1)^2$ and $(2k+1)^2$ are multiples of 5. However, if $(2k+1)^2$ is a multiple of 5, then so must $2k+1$ be. We therefore conclude that the coefficient of $q^{5n+5}$ in $q\prod_{k \geq 1}(1-q^k)^4$—and hence in $\prod_{k \geq 1}(1-q^{5k})\sum_{n \geq 0} p(n) q^{n+1}$—is a multiple of 5. This implies that $p(5n+4)$ is a multiple of 5, as claimed.

Written by uncudh

November 24, 2008 at 4:50 pm

Posted in math

Tagged with ,