Uniformly at Random

Archive for March 2009

Hadamard’s gap theorem

leave a comment »

We mentioned briefly at the end of this post that Carlson proved that a function whose power series expansion has integer coefficients and radius of convergence 1 is either rational or has a natural boundary.  A function has a natural boundary if every point on its circle of convergence is a singularity.  In particular, it cannot be analytically continued beyond its disc of convergence.

An example of a function with natural boundary is f(z) = \sum_{n=0}^\infty z^{2^n}.  It is enough to show that the singularities of f are dense on the unit circle.  Let k,N be positive integers and let z = re^{2\pi ik/2^N} for some r<1.  Then

f(z) = \sum_{n=0}^\infty z^{2^n} = \sum_{n=0}^\infty (re^{2\pi ik/2^N})^{2^n}

= \sum_{n=0}^{N-1} (re^{2\pi ik/2^N})^{2^n} + \sum_{n=N}^\infty (re^{2\pi ik/2^N})^{2^n}

= \sum_{n=0}^{N-1} (re^{2\pi ik/2^N})^{2^n} + \sum_{n=N}^\infty r^{2^n}.

However, \sum_{n=N}^\infty r^{2^n} is unbounded as r tends to 1.  Thus, z = e^{2\pi ik/2^N} is a singularity of f for every positive k,N.  This gives a dense set of singular points on the unit circle, completing the proof of the claim.

This phenomemon is captured by a general theorem of Hadamard, which states that if \lambda >1 is a real number and \{b_n\} is a sequence of positive integers such that for all n, b_{n+1} > \lambda b_n, then f(z) = \sum_{n=0}^\infty a_n z^{b_n} has a natural boundary.

A much more powerful “gap theorem” due to Fabry, replaces the condition b_{n+1} > \lambda b_n with \lim_{n\to\infty} n/b_n = 0.  This result is capable, for instance, of establishing that f(z) = \sum_{n=0}^\infty z^{n^2} has a natural boundary.

Written by uncudh

March 28, 2009 at 9:42 pm

Posted in math

Tagged with , ,

The decline of Iroquois influence

leave a comment »

We have seen previously that the initial phase of the Iroquois Wars (1640’s to 60’s) was marked by the stunning miltary sucesses of the Iroquois against their enemies—e.g., Huron, Tobacco, Neutrals— north of the Great Lakes.  They were also successful in actions taken against various nations of the Ohio valley.  By the 1660’s however, this continuous warfare began to take its toll on the Iroquois confederacy.  The mid-1660’s was also marked by the English conquest of the Dutch colony of New Netherland, which had been the principal supplier of arms and ammunition to the Iroquois.  Under these circumstances, the Five Nations made peace with the French and ceased hostilities for a time.

During the subsequent period of peace, the Iroquois began to form connections with the English, which eventually led to the creation of the so-called Covenant Chain between the Iroquois confederacy and the English colonies.  In the meanwhile, the French were no less assiduous in seeking out alliances.  In particular, the French formed strong connections with the Algonquian peoples of the upper Great Lakes.

The renewal of the conflict in the 1680’s and 90’s was following by devastating reversals of fortune for the Iroquois.  We have briefly noted earlier that the strong French alliances and increased military presence of the French in the Canadas combined to inflict serious losses on the Iroquois.  The Iroquois made peace once more with the French in 1701—the so-called Great Peace of Montreal—which committed them to neutrality in any future conflicts between the English and French.

There was now a tenuous balance of power in the region, with the Iroquois Confederacy acting as a buffer between the two empires.  Developments in the Ohio valley, however, threatened to destabilize this balance of power.  The Ohio valley was important to each of the three major players for different reasons.  The French wanted control of the Ohio country because they needed the Ohio waterways to connect their forts and settlements in the Canadas to those along the upper Mississippi valley in the so-called Illinois country.  The English wanted that land for future expansion and settlement; futhermore, they could not allow the French to occupy the Ohio valley, as that would seal the English off from the interior of the continent and restrict them to the land east of the Appalachians.  The Iroquois, for their part, claimed authority over the various nations—such as Shawnee, Mingo, and Delaware—that had moved into the Ohio country in response to the pressure of European expansion in the east.

By the 1750’s, the French had begun to establish a significant presence in the Ohio valley, building several large forts at strategic locations along the waterways.  Moreover, the nations of the valley, supposed to be Iroquois dependents, were increasingly coming under French influence.  The Iroquois, dismayed at the decline of their influence among these nations, were inevitably being driven closer and closer to a position which would require them to abandon their neutrality and take action against the French.  The English also could not possibly tolerate such French incursions.  This powderkeg in the Ohio valley would eventually set off the last and most significant of the French and Indian Wars, which would last from 1754 to 1763 and would end with the decisive defeat of the French and the complete and irretrievable loss of their Canadian possessions to the English.

Written by uncudh

March 28, 2009 at 8:53 pm

Posted in history

Tagged with , ,

Power series with integer coefficients

leave a comment »

In combinatorial enumeration one often works with generating functions.  The coefficients of the power series expansion of such a generating function are therefore integers, since they are meant to count objects of a certain size.  A curious old result of Fatou states that a function whose power series expansion has integer coefficients and radius of convergence 1 is either rational or transcendental.  This result also appears as Problem VIII.167 of Polya and Szego’s famous Aufgaben book.  We shall attempt to prove this result below.

We begin with the following particular case of Parseval’s identity.  Let f(z) = \sum_{n=0}^\infty a_n z^n be a function with radius of convergence R.  Then for r < R we have

\sum_n |a_n|^2 r^{2n} = \frac{1}{2\pi} \int_0^{2\pi} |f(re^{i\theta})|^2 d\theta.

To see this, first let \overline{z} denote the complex conjugate of z.  Then we have

|f(z)|^2 = f(z)\overline{f(z)} = \sum_n a_nz^n \cdot \sum_m \overline{a_m}\overline{z}^m.

Since these series converge absolutely, we may multiply them to obtain

|f(z)|^2 = \sum_{n,m} a_n \overline{a_m} z^n \overline{z}^m.

Writing z = re^{i\theta}, we have

|f(re^{i\theta})|^2 = \sum_{n,m} a_n \overline{a_m} r^{n+m} e^{i\theta(n-m)}.

We now integrate term by term to obtain

\int_0^{2\pi} |f(re^{i\theta})|^2 d\theta = \sum_{n,m}\int_0^{2\pi} a_n \overline{a_m} r^{n+m} e^{i\theta(n-m)} d\theta.

Observe that

\int_0^{2\pi} a_n \overline{a_m }r^{n+m} e^{i\theta(n-m)} d\theta

equals 2\pi |a_n|^2 r^{2n} when n=m and 0 otherwise.  Thus,

\int_0^{2\pi} |f(re^{i\theta})|^2 d\theta = \sum_n 2\pi |a_n|^2 r^{2n},

which is the claimed identity.

Next, let f(z) = \sum_{n=0}^\infty a_n z^n be a power series with integer coefficients such that infinitely many a_i are non-zero.  We claim that if f(z) is convergent in the interior of the unit disc, then it is unbounded there.

Suppose to the contrary that f(z) is bounded in the interior of the unit disc.  In particular, for r<1, f(z) is bounded on the circle of radius r.  Thus, the integral \frac{1}{2\pi} \int_0^{2\pi} |f(re^{i\theta})|^2 d\theta is also bounded.  However, we have seen that

\frac{1}{2\pi} \int_0^{2\pi} |f(re^{i\theta})|^2 d\theta = \sum_n |a_n|^2 r^{2n},

and, since the a_i are integers, the series on the right hand side tends to infinity as r tends to 1.  This contradiction proves the claim.

Now, let us suppose that f(z) = \sum_{n=0}^\infty a_n z^n is a power series with integer coefficients and radius of convergence 1.  Suppose contrary to our desired conclusion that f(z) is algebraic but not rational.  Then f(z) satisfies an equation of the form

p_d(z) [f(z)]^d + p_{d-1}(z) [f(z)]^{d-1} + \cdots + p_1(z)f(z) + p_0(z) = 0,

where d > 1 and the p_i are polynomials with integer coefficients.  Since d>1, we can multiply through by [p_d(z)]^{d-1} to obtain

[p_d(z)]^d [f(z)]^d + p_{d-1}(z) [p_d(z)]^{d-1} [f(z)]^{d-1} + \cdots + p_1(z) [p_d(z)]^{d-1} f(z) + p_0(z) [p_d(z)]^{d-1} = 0.

Setting y = p_d(z)f(z), we can rewrite this as

y^d + p_{d-1}(z) y^{d-1} + \cdots + p_1(z) [p_d(z)]^{d-2} y + p_0(z) [p_d(z)]^{d-1} = 0.

Note that y^d cannot be unbounded in the interior of the unit disc, since this term dominates the other terms of lower order in the left hand side, and if y^d were to be unbounded, then the above equation could not hold.  It follows then that y^d is bounded, and hence y = p_d(z)f(z) is bounded.  However, y = p_d(z)f(z) is a function whose power series has integer coefficients and radius of convergence 1.  We have previously seen that such a function cannot be bounded in the interior of the unit disc.  This contradiction establishes the desired result: i.e., a function whose power series expansion has integer coefficients and radius of convergence 1 is either rational or transcendental.

Polya conjectured a stronger result, namely that either the function is rational or admits the unit circle as a natural boundary (i.e., has no analytic continuation beyond the unit disc).  This was eventually proved by Carlson.

Written by uncudh

March 24, 2009 at 7:58 pm

Posted in math

Tagged with ,

Tea drinking habits of New Englanders in the 1770’s

leave a comment »

John Adams added the following postscript to a letter written to his wife Abigail on 6 July 1774.

I believe I forgot to tell you one Anecdote:  When I first came to this House it was late in the Afternoon, and I had ridden 35 miles at least.  “Madam” said I to Mrs. Huston, “is it lawfull for a weary Traveller to refresh himself with a Dish of Tea provided it has been honestly smuggled, or paid no Duties?”

“No sir, said she, we have renounced all Tea in this Place.  I cant make Tea, but I’le make you Coffee.”  Accordingly I have drank Coffee every Afternoon since, and have borne it very well.  Tea must be universally renounced.  I must be weaned, and the sooner, the better.

(Note: The Boston Tea Party took place 16 December 1773.)

Written by uncudh

March 23, 2009 at 10:08 pm

Posted in history

Tagged with ,

Forthcoming publications

leave a comment »

There are a couple of books coming out soon whose upcoming release I am awaiting with interest.  The first is Tolkien’s The Legend of Sigurd and Gudrun.  The book consists of Tolkien’s verse renderings of the Norse tales concerning Sigurd the Volsung (the most notable of the Norse sources being the Volsungasaga).  We have previously made reference (here and here) to William Morris’s version of the Sigurd legend.  It will be interesting to compare Tolkien’s version.

The second is Arora and Barak’s Complexity Theory: A Modern Approach.  The standard reference in this area for a long time was Papadimitriou’s book Computational Complexity, but it is now somewhat old and  does not contain the latest research.  Arora and Barak have posted an early draft of their book online, and it looks like it could quite possibly replace Papadimitriou as the standard computational complexity text.

Written by uncudh

March 22, 2009 at 11:10 pm

The Ten Thousand at Nineveh

leave a comment »

After the death of Prince Cyrus during the Battle of Cunaxa (401 BC, near Babylon), the Greek army of the Ten Thousand found themselves trapped on the eastern side of the Euphrates river (i.e., between the Euphrates and the Tigris).  The Persian army was in the vicinity and its presence prevented the Greeks from re-crossing the Euphrates in order to make their way back towards Greece.  The Greeks were therefore compelled to cross over to the eastern side of the Tigris and travel northward, following the Tigris backwards towards its sources in northern Mesopotamia, hoping to eventually pass through Armenia and make their way to the Black Sea.  During the course of this northward travel along the Tigris, the Greeks passed through the ruins of some of the once great cities of the ancient Assyrians.  Xenophon describes passing through the ruins of the Assyrian capital of Nineveh as follows (Anabasis III.4, Loeb Classical Library edition):

From this place they marched one stage, six parasangs, to a great stronghold, deserted and lying beside a city.  The name of this city was Mespila, and it was once inhabited by the Medes.  The foundation of its wall was made of polished stone full of shells, and was fifty feet in breadth and fifty in height.  Upon this foundation was built a wall of brick, fifty feet in breadth and a hundred in height; and the circuit of the wall was six parasangs.  Here, as the story goes, Medea, the king’s wife, took refuge at the time when the Medes were deprived of their empire by the Persians.  To this city also the king of the Persians laid siege, but he was unable to capture it either by length of siege or by storm; Zeus, however, rendered the inhabitants thunderstruck, and thus the city was taken.

In a footnote to this passage in the LCL edition, the translator points out that

[t]he ruins which Xenophon saw here were those of Nineveh, the famous capital of the Assyrian Empire.  It is revealing that he can characterize this great Assyrian city (as well as Kalhu above) with the casual and misleading statement that “it was once inhabited by the Medes.”  In fact, the capture of Nineveh by the Medes (c. 600) was the precise event which closed the important period of its history, and it remained under the control of the Medes only during the succeeding half-century, i.e. until the Median Empire was in its turn overthrown by the Persians (549).

Written by uncudh

March 22, 2009 at 10:55 pm

Spring

leave a comment »

In honour of the beginning of spring, here is a little from Chapter 17 of Thoreau’s Walden, entitled “Spring”:

The change from storm and winter to serene and mild weather, from dark and sluggish hours to bright and elastic ones, is a memorable crisis which all things proclaim. It is seemingly instantaneous at last. Suddenly an influx of light filled my house, though the evening was at hand, and the clouds of winter still overhung it, and the eaves were dripping with sleety rain. I looked out the window, and lo! where yesterday was cold gray ice there lay the transparent pond already calm and full of hope as in a summer evening, reflecting a summer evening sky in its bosom, though none was visible overhead, as if it had intelligence with some remote horizon. I heard a robin in the distance, the first I had heard for many a thousand years, methought, whose note I shall not forget for many a thousand more – the same sweet and powerful song as of yore. O the evening robin, at the end of a New England summer day! If I could ever find the twig he sits upon! I mean he; I mean the twig. This at least is not the Turdus migratorius. The pitch pines and shrub oaks about my house, which had so long drooped, suddenly resumed their several characters, looked brighter, greener, and more erect and alive, as if effectually cleansed and restored by the rain. I knew that it would not rain any more. You may tell by looking at any twig of the forest, ay, at your very wood-pile, whether its winter is past or not. As it grew darker, I was startled by the honking of geese flying low over the woods, like weary travellers getting in late from Southern lakes, and indulging at last in unrestrained complaint and mutual consolation. Standing at my door, I could bear the rush of their wings; when, driving toward my house, they suddenly spied my light, and with hushed clamor wheeled and settled in the pond. So I came in, and shut the door, and passed my first spring night in the woods.

Written by uncudh

March 21, 2009 at 9:16 pm

Posted in literature

Tagged with ,