Euler on research

September 20, 2013

Found a great quote while reading through Lagarias’s recent paper on Euler’s constant,

Jeffrey C. Lagarias. Euler’s constant: Euler’s work and modern developments, Bull. Amer. Math. Soc. (N.S.), 50 (4), (2013), 527–628. MR3090422.

Lagarias quotes Truesdell,

Clifford Ambrose Truesdell, III. An idiot’s fugitive essays on science, Methods, criticism, training, circumstances. Springer-Verlag, New York, 1984. MR769106 (86g:01060); and Great scientists of old as heretics in “the scientific method”. University Press of Virginia, Charlottesville, VA, 1987. MR915762 (88m:01038).

Lagarias:

C. Truesdell [303, Essay 10], [304, pp. 91–92], makes the following observations about the methods used by Euler, his teacher Johann Bernoulli, and Johann’s teacher and brother Jacob Bernoulli:

1. Always attack a special problem. If possible solve the special problem in a way that leads to a general method.

2. Read and digest every earlier attempt at a theory of the phenomenon in question.

3. Let a key problem solved be a father to a key problem posed. The new problem finds its place on the structure provided by the solution of the old; its solution in turn will provide further structure.

4. If two special problems solved seem cognate, try to unite them in a general scheme. To do so, set aside the differences, and try to build a structure on the common features.

5. Never rest content with an imperfect or incomplete argument. If you cannot complete and perfect it yourself, lay bare its flaws for others to see.

6. Never abandon a problem you have solved. There are always better ways. Keep searching for them, for they lead to a fuller understanding. While broadening, deepen and simplify.

170 – Extra credit

September 20, 2013

Choose a mathematician whose work is somehow related to calculus. The connection may be loose (of course, Newton or Leibniz qualify, but so does John Nash). To avoid repetitions, email me your choice, and I’ll let you know whether your choice has not yet been claimed.

Write (well, type) an essay on their life and mathematical work. It may be short. Make sure to follow reasonable standards of style when citing references, etc. Due December 2 (after Thanksgiving break).

Analysis – Counting the rationals

September 18, 2013

It is easy to see that to show that $\mathbb Q$ is countable, it suffices to show the countability of $\mathbb Q^+$, or even of $\mathbb Q\cap(0,1]$.

I.

There is a straightforward way of enumerating the latter: First list the fractions with denominator $1$, then those with denominator $2$ (skipping those already listed), then those with denominator $3$ (again, skipping repetitions), etc. This list begins

$\displaystyle \frac11;\frac12;\frac13,\frac23;\frac14,\frac34;\frac15,\frac25,\frac35,\frac45;\dots$

Cantor’s  first proof of the uncountability of the reals (the nested intervals argument) from 1874 proceeds as follows:

Given any (injective) sequence $a_1,a_2,\dots$ of reals, we want to exhibit a real that was not listed. There are two cases: Either there are $i\ne j$ with $a_i, and such that there is no $k$ with $a_k\in(a_i,a_j)$, in which case we are obviously done, or (more interestingly), whenever $a_i, we can find an $a_k$ strictly in between (the range of the sequence is dense in itself). Assume we are in this situation.

Define two sequences $b_1,b_2,\dots$ and $c_1,c_2,\dots$ as follows:

• First, $b_1=a_1$ and $c_1=a_2$.
• For definiteness, suppose that $a_1>a_2$. The other case is treated similarly. Let $b_2$ be $a_i$, where $i$ is least such that $a_i\in(c_1,b_1)$. Then define $c_2$ as $a_j$, where $j$ is least such that $a_j\in(c_1,b_2)$.
• In general, given $c_n, we define $b_{n+1}$ as $a_k$, where $k$ is least such that $a_k\in(c_n,b_n)$, and then define $c_{n+1}$ as $a_m$, where $m$ is least such that $a_m\in(c_n,b_{n+1})$. Note that these sequences are well defined, because of our density assumption.

The construction just described ensures that if $I_n=[c_n,b_n]$, then:

1. For any $n$, we have that $a_n\notin I_{n+1}$, and
2. The intervals are nested and decreasing: $I_1\supsetneq I_2\supsetneq I_3\dots$

It follows (from the completeness of the reals) that $\bigcap_n I_n\ne\emptyset$, and (from 1.) that any real in this intersection is not in the range of the sequence $a_1,a_2,\dots$

It turns out that if we carry out Cantor’s construction when the sequence of $a_i$ is the enumeration of the rationals in $(0,1]$ we began with, then $\bigcap_n I_n=\{1/\phi\}$, where $\phi$ is the golden ratio.

This is proved in the nice note

Mike Krebs, and Thomas Wright. On Cantor’s first uncountability proof, Pick’s theorem, and the irrationality of the golden ratio, Amer. Math. Monthly, 117 (7),  (2010), 633–637. MR2681523 (2011e:11127).

II.

There is a very nice enumeration of $\mathbb Q^+$ with combinatorial significance.

The rationals are used to label the nodes of the infinite complete binary tree, and the resulting enumeration simply follows the nodes of the tree, lexicographically.

We begin by putting $1/1$ at the root of the tree. Once a node has been labelled $m/n$, its left successor is labelled $m/(m+n)$, and its right successor is latex $(m+n)/n$.

And that’s all! The list so produced begins

$\displaystyle \frac11;\frac12,\frac21;\frac13,\frac32,\frac23,\frac31;\dots$

The proof that this is indeed a bijective listing of $\mathbb Q^+$ is remarkably simple; one verifies in order the following claims:

1. The numerator and denominator of any of the assigned fractions are relative prime.
2. Every positive rational is assigned to some node.
3. Every positive rational is assigned to some node.

For this, one proceeds by induction. For example, if there is a fraction $m/n$ not in reduced form, and used as a label, pick such a fraction appearing in as small a level as  possible, and note that the fraction cannot be $1/1$. A contradiction is now attained by noting that $\mathrm{gcd}(m,n)=\mathrm{gcd}(m-n,n)=\mathrm{gcd}(m,n-m)$.

Similarly, if $m/n$ appears in more than one node, then $m\ne n$, and its immediate predecessor (either $(m-n)/n$ or $m/(n-m)$, depending on whether $m>n$ or $m) must also appear more than once.

Finally, if some fraction is not listed, we can choose its denominator $n$ least among the denominators of all skipped fractions, and then choose its numerator $m$ least among the numerators of all skipped fractions with denominator $n$. A contradiction follows because $m\ne n$, and if $m>n$, then $(m-n)/n$ must also have been skipped, but $m-n, while if $m, then $m/(n-m)$ must have been skipped, but $n-m.

This enumeration is due to Neil Calkin and Herbert Wilf, who also showed that it has the following nice combinatorial properties:

1. There is a sequence $b(0),b(1),b(2),\dots$ of positive integers such that the $n$-th fraction in the enumeration is just $\displaystyle \frac{b(n)}{b(n+1)}$ (in reduced form). In particular, the denominator of a fraction is the numerator of its successor in the enumeration. So $b(0)=1$, $b(1)=1$, $b(2)=2$, $b(3)=1$, $b(4)=3$, $b(5)=2$, $b(6)=3$, etc.
2. In fact, $b(n)$ is precisely the number of ways of writing $n$ as a sum of powers of $2$, where each power can be used at most twice. For example, $b(6)=3$, because we can write $6$ as $2^2+2^1$, as $2^2+2^0+2^0$, or as $2^1+2^1+2^0+2^0$.

This is proved in the nice note

Neil J. Calkin, and Herbert S. Wilf. Recounting the rationals, Amer. Math. Monthly, 107 (4), (2000), 360–363. MR1763062 (2001d:11024).

Some natural questions:

1. What can we say about the real(s) that comes out when the procedure from Cantor’s proof from section I is applied to this enumeration?
2. Any infinite path through the binary tree defines a sequence of rationals. What reals appear as limit points of these sequences?

Analysis – Some remarks on continued fractions

September 18, 2013

Most introductory books on number theory have at least one section on the theory of continued fractions. I suggest

William Stein. Elementary number theory: primes, congruences, and secrets. A computational approach.  Undergraduate Texts in Mathematics, Springer, New York, 2009. MR2464052 (2009i:11002).

downloadable from his webpage. Chapter 5 is on continued fractions. Of interest to us is the proof that for any integer $a_0$ and any infinite sequence of positive integers $a_1,a_2,\dots$ the corresponding continued fraction $\displaystyle {}[a_0;a_1,a_2,\dots]=a_0+\frac1{a_1+\frac1{a_2+\dots}}$ converges to an irrational number. This gives us an explicit bijection between the space of irrationals $\mathbb R\setminus\mathbb Q$ and Baire space, $\mathbb N^{\mathbb N}$. The bijection is actually a homeomorphism, so the two spaces are equal, as topological spaces. This was first noted by Baire, in

René Baire. Sur la représentation des fonctions discontinues. Deuxième partie, Acta Math. 32 (1), (1909), 97–176. MR1555048.

For a very nice alternative proof of the homeomorphism that does not involve continued fractions, see Chapter 1 of

Arnold W. Miller. Descriptive set theory and forcing. How to prove theorems about Borel sets the hard way. Lecture Notes in Logic, 4. Springer-Verlag, Berlin, 1995.MR1439251 (98g:03119).

Arnie’s homeomorphism also has the nice feature of being an explicit order preserving bijection between $\mathbb Z^{\mathbb N}$, ordered lexicographically, and the set of irrationals.

In William’s book, you may also want to look at section 5.4, where a proof is provided of Euler’s theorem from 1737 that the continued fraction of $e$ is given by

$e=[2;1,2,1,1,4,1,1,6,1,1,8,\dots].$

(No such nice pattern is known for $\pi$.)

A few nice additional results on continued fractions, with references, are given in this blog entry.

A fascinating open problem, due to Zaremba from 1972, is discussed in

Alex Kontorovich. From Apollonius to Zaremba: local-global phenomena in thin orbits. Bull. Amer. Math. Soc. (N.S.), 50 (2), (2013), 187–228. MR3020826.

To state the problem, fix a positive integer $n$, and consider the set

$\displaystyle N_n=\{m\mid \mbox{ there is an }r\mbox{ such that }1\le r\le m,$ $\displaystyle \mathrm{gcd}(m,r)=1,\mbox{ and if }\frac mr=[a_0;a_1,\dots,a_k],$ $\displaystyle \mbox{ then }a_i\le n\mbox{ for all }i\le k\}.$

For example, $N_1$ consists of all numerators appearing in finite continued fractions consisting solely of ones: ${}[1],[1;1],[1;1,1],[1;1,1,1],\dots$, that is, $\displaystyle 1,2,\frac32,\frac53,\frac85,\dots$, so $N_1$ is the set of positive Fibonacci numbers.

Zaremba’s conjecture is that $N_5=\mathbb N^+$. In fact, much more is expected to be true. For example, Hensley conjectured in 1996 that $N_2$ contains all positive integers, with finitely many exceptions. The best result to date is that $N_{50}$ contains almost all positive integers, in the sense that

$\displaystyle \lim_{n\to\infty}\frac{N_{50}\cap[1,n]}n=1.$

For this, see the announcement,

Jean Bourgain, and Alex Kontorovich. On Zaremba’s conjecture, C. R. Math. Acad. Sci. Paris, 349 (9-10), (2011), 493–495. MR2802911 (2012e:11012),

and the preprint

Jean Bourgain, and Alex Kontorovich. On Zaremba’s conjecture. ArXiv:1107.3776.

(Of immediate interest to us is the fact described in Kontorovich’s survey that for $n\ge2$, the set of infinite continued fractions

$[1;a_0,a_1,a_2,\dots]$

where $1\le a_i\le n$ for all $i$ is a Cantor set.)

170 – Hippasus of Metapontum

September 16, 2013

Erroll Morris ran a series of essays on the New York Times a couple of years ago, on the topic of incommesurability. The whole series is highly recommended. You may particularly enjoy reading Part III, on Hippassus of Metapontum, the mythical Pythagorean who proved the irrationality of square root of two, and was killed by the other followers of the cult as a result.

The legend is told in many places; Morris lists a few in his essay. I first found it as an appendix to Carl Sagan‘s book version of Cosmos.

School picture

September 15, 2013

“OK. Smile for the camera.”

“Uh, mmm, OK. Let’s try again. Smile.”

“Hehe. Let’s smile this time.”

“Fine.”

Analysis – HW 1

September 5, 2013

This set is due Monday, September 16, at the beginning of lecture.

Recall that $\mathbb N=\{0,1,2,\dots\}$. Given a sequence $\vec a=a_0,a_1,\dots$ of nonnegative real numbers, for $F$ a finite subset of $\mathbb N$, the expression

$\displaystyle \sum_{F}\vec a=\sum_{n\in F}a_n$

has what is hopefully the obvious meaning: If $n_0 is the increasing enumeration of the elements of $F$, then

$\sum_{F}\vec a=\sum_{i=0}^k a_{n_i}=a_{n_0}+a_{n_1}+\dots+a_{n_k}$,

with the (standard) convention that if $F$ is empty, then $\sum_{F}\vec a=0$.

For $S$ an arbitrary subset of $\mathbb N$ (so $S$ may be finite or infinite), define

$\displaystyle \sum_{S}\vec a=\sup\{\sum_{F}\vec a\mid F\mbox{\ is a finite subset of\ }S\},$

provided that the supremum exists. There is a small ambiguity here, in that if $S$ is finite, we have defined $\sum_{S}\vec a$ in two potentially conflicting ways.

1. Show that both definitions coincide if $S$ is finite.

2. Give an example of a sequence $\vec a$ and a set $S$ such that $\sum_{n\in S}a_n$ is not defined. Show that for any $\vec a$ and any $S$, if $\sum_{n\in S}a_n$ is not defined, then neither is $\sum_{n\in\mathbb N}a_n$.

3. Show that, if $\sum_{\mathbb N}\vec a$ is defined, then

$\sum_{\mathbb N}\vec a=\sup\{\sum_{k=0}^m a_k\mid m\in\mathbb N\}$.

More generally, show that, as long as $\sum_{S}\vec a$ is defined, then

$\sum_{S}\vec a=\sup\{\sum_{S\cap[0,m]} \vec a\mid m\in\mathbb N\}$

and that, if this supremum exists, then so does $\sum_{S}\vec a$, and the displayed equality holds.

4. Fix a positive integer $k\ge 2$. Show that if $\vec a$ is such that, for every $n$, $a_n$ has the form $\displaystyle \frac{b_n}{k^{n+1}}$ where $b_n\in\{0,1,\dots,k-1\}$ then, for any $S$, $\sum_{n\in S}a_n$ is defined, and is a number in the interval $[0,1]$.

5. Show that for every $x\in[0,1]$ and every positive integer $k\ge2$ there is some $\vec a$ as in item 4. such that $\sum_{\mathbb N}\vec a=x.$ Describe as precisely as possible all the quadruples $(k,x,\vec a,\vec a')$ such that $k\ge 2$ is an integer, $x\in[0,1]$, $\vec a\ne \vec a'$ are sequences as in 4., and yet

$\sum_{n\in\mathbb N}a_n=x=\sum_{n\in \mathbb N}a'_n.$

Hopefully it is clear that all we are describing is the base $k$ representation of any number $x\in[0,1]$.

6. Indicate how to extend the above so any real has a base $k$ representation (for any $k\ge2$).

7. Given $k\ge 2$, let $\vec a$ be the sequence with $n$-th term $a_n=1/k^n$ for all $n$. Show that $2$ is the only value of $k$ such that there are $S_1\ne S_2$ with $\sum_{S_1}\vec a=\sum_{S_2}\vec a.$ Describe all such pairs $(S_1,S_2)$. Show that for all $k\ge 2$ there is some $\vec a$ as in 4., with the same “failure of injectivity” property.

The above gives us that $|\mathbb R|\ge|\mathcal P(\mathbb N)|$ in the sense that there is an injection $\psi:\mathcal P(\mathbb N)\to \mathbb R$.

8. Make this explicit, that is, give an example of such an injection $\psi$, hopefully related to these sums we are considering.

One can also show that $|\mathcal P(\mathbb N)|\ge|\mathbb R|$ and in fact there is a bijection between these two sets, though you do not need to do this here.

As indicated in item 7., when $\vec a=1,1/2,1/4,1/8,\dots$ the function $\rho:\mathcal P(\mathbb N)\to\mathbb R$ given by $\rho(S)=\sum_{n\in S}a_n$ is not an injection.

9. For this $\vec a$, show that the collection of sets $S$ such that there is a set $T\ne S$ with $\sum_{S}\vec a=\sum_{T}\vec a$ is countable. Show that if $\mathcal F\subset\mathcal P(\mathbb N)$ is countable, then there is a bijection between $\mathcal P(\mathbb N)$ and $\mathcal P(\mathbb N)\setminus \mathcal F$ so, in particular, even $\rho$ allows us to verify that $|\mathbb R|\ge|\mathcal P(\mathbb N)|$.