Generalization with purpose

Modern number theory begins with the integers, all those whole numbers, positive, negative, and zero. A few times, when teaching number theory, I began simultaneously with the integers, the Gaussian integers, and the Eisenstein integers. One pedagogical reason is this: if you spend the first few weeks of number theory class proving things that students “learned” by fifth grade, then students will not likely be excited. The Euclidean algorithm can excite students, but proving the existence and uniqueness of prime decomposition is — from the students’ perspective — proving something they already (think they) know. Number theory teachers can get flustered by this. “No!” they say, “You only think you know this! It needs to be proven. It’s really not trivial! Really! Pay attention!”

I think there are two important roles for the instructor at this stage. One is to guide the student to wiser ignorance, as in Plato’s Meno, where Socrates says “Is he not better off in knowing his ignorance?”.  To this end, the instructor gives counterexamples, where irreducible elements p (those that cannot be factored further) are not prime (do not satisfy the implication p \vert ab \Rightarrow p \vert a or p \vert b). The first counterexample that I learned was in the ring Z[\sqrt{-5}] in which (1 + \sqrt{-5}) \cdot (1 - \sqrt{-5}) = 2 \cdot 3. The element 2 is irreducible but not prime. I think this counterexample is natural to the number theorist and instructor — having a prior background in quadratic rings — but most unusual to the elementary number theory student.  It also leaves the instructor having to convince the student that 1 \pm \sqrt{-5} and 2 and 3 are irreducible.  That is probably too difficult for the beginning student.  A more elementary example occurs in Hilbert’s monoid \{ 1,5,9,13,17,\ldots \} of natural numbers congruent to one modulo 4. In this monoid (under multiplication), 9 is irreducible. On the other hand, 9 \vert 21 \cdot 21 but 9 does not divide 21. Another way to say this is that 441 factors into irreducible in two ways:  9 \cdot 49 and 21 \cdot 21.  So this Hilbert monoid might break the student’s false intuition that irreducible elements are prime, and that factorization must be unique.

Besides leading the student to wiser ignorance, the instructor should motivate the proof of existence and uniqueness of prime decomposition by demonstrating its application to number systems beyond the integers.  To this end, one strategy is to simultaneously teach students the basic arithmetic of integers, Gaussian integers, and Eisenstein integers. I think students appreciate the details of proofs when they are proving something they don’t already “know”. Only those already devoted to pure mathematics will appreciate a proof of prior “knowledge”.

I have devoted Chapter 5 to a study of Gaussian and Eisenstein integers. I hope that some instructors will follow this chapter as they go through Chapters 2 and 3 to pique the interest of students. It is not technically necessary for what comes later, but Gaussian and Eisenstein integers are beautiful and important in their own right. I have always liked their kaleidoscopic symmetry, so I devoted an entire two-page spread to visualizations of Gaussian and Eisenstein primes.

A two-page spread from Chapter 5
Click to enlarge a two-page spread from Chapter 5

The pictures display the ramified, inert, and split primes in different colors, and the inert primes are displayed below on a number line to provide a scale. A fundamental domain is highlighted to exhibit the kaleidoscopic symmetry. Symmetry will reappear in the study of orthogonal groups of binary quadratic forms later, so it is good to see a few examples here.  Hecke proved equidistribution of prime angles in the Gaussian context (and much more), in efforts to prove the infinitude of primes of the form x^2 + 1. Thus I have drawn attention to the prime angles (with tick marks on the circumference) and the primes of the form x^2 + 1 (with parallel horizontal lines across the Gaussian plane).  Analogously, I have drawn attention to the primes of the form x^2 - x + 1 in the diagram of Eisenstein integers.

Why else study Gaussian and Eisenstein integers?  Some students think that generalization is a worthy goal for its own sake, but I prefer generalization with purpose.  In Chapter 5, we use properties of Gaussian and Eisenstein primes to study properties of ordinary primes (infinitude of primes congruent to one modulo three and modulo four, and relations to primes of the form x^2 + 1).  One “big picture” lesson of this book is that the study of larger and stranger number systems sheds light on the natural numbers.  Exhibit G:  The Gaussian Integers.  Exhibit E:  The Eisenstein Integers.  Later on, quadratic rings, and the rings of modular arithmetic.

Why is the treatment of Gaussian and Eisenstein integers delayed until Chapter 5, instead of following my pedagogical advice to include them in the teaching of prime decomposition?  There are two reasons.  First, for shorter courses, I can imagine an instructor skipping Chapter 5.  Second, Gaussian and Eisenstein integers connect the first part of the book (foundational properties of integers and rational numbers) to the second part of the book (on binary quadratic forms).  By Chapter 7, we will study definite binary quadratic forms, and the Gaussian and Eisenstein integers will reappear in relation to the unique forms of discriminants -3 and -4, respectively.

Fractions and semiotics.

Fractions haunt elementary school teachers and occupy a disproportionate (1/2? 2/3? 15/17?) amount of time in math teacher professional development. Many college students arrive with a distaste for fractions; they are generally much happier talking about 3.4 rather than 17/5. There are a few likely reasons: it is much easier to work with decimals on a handheld calculator, and numbers are easier to compare as decimals rather than fractions.

But I like fractions, especially comparing them, and teaching fractions raises some important issues at the heart of mathematics. My two favorite fraction topics are the mediant fraction and kissing fractions. Both topics can be found in L. R. Ford’s article “Fractions” from the American Mathematical Monthly, vol. 45, no. 9 (Nov. 1938), pp. 586–601.

The mediant fraction is what happens every day when a child adds fractions the wrong way. The mediant of 1/3 and 1/2 is 2/5. Add the numerator, add the denominator — it’s a natural thing to try, but it doesn’t give you the sum. It gives you the mediant.

I wish more teachers would tell these children something like “What you’ve done isn’t adding the fractions, it’s something much more interesting. You’ve made the mediant fraction!”

What does this operation do? If you start with fractions with positive denominator, the output fraction is between the fractions you start with. But strangely, to a novice, the operation is really an operation on fractions, not on rational numbers. For example, the mediant of 2/6 and 1/2 is 3/8. But hang on a second — the mediant of 1/3 and 1/2 is 2/5, and 1/3 = 2/6, so how can this be?

This is one sign that the mediant isn’t an operation on rational numbers. It makes sense for fractions, but it depends on how the fraction is written. Further explanation is in the two-page spread below.

Screenshot from Chapter 4 of the Illustrated Theory of Numbers
Click to enlarge a two-page spread from Chapter 4

I think teachers and students have trouble with this, and the obstruction is a poor understanding of semiotics. In other words, teachers and students do not adequately distinguish between numbers and how numbers are written. I made a common decision to use the word “fraction” to mean a written expression like “a/b”, and “rational number” to mean a number which can be described by a fraction. So “1/3” and “2/6” are different fractions, which mean the same rational number.

Why is this so important (besides the fact that the mediant is an operation on fractions)? I think this issue arises again and again. Eventually, I would guess most students think that numbers are decimal expansions. The number \pi is the decimal expansion 3.14... for most students. But this too is incorrect, leading to confusion when students or teachers hear that 0.999\ldots equals 1 for the first time. Real numbers are not decimal expansions, nor are rational numbers fractions.

What about kissing fractions? Given integers a, b, c, d, I say that a/b kisses c/d if ad - bc = 1 or ad - bc = -1. I call this kissing, because two fractions kiss when their Ford circles kiss; kissing circles have been around for a long time, sometimes called tangent (touching) circles or osculating circles. Kissing fractions are the algebraic counterpart of kissing circles. Kissing fractions leads to more kissing, love triangles, and more. You’ll have to read Chapter 4 to find out. In case you think it is all a love-fest, Chapter 4 also contains material on the construction of the 17-gon and Dirichlet’s approximation theorem.

The mediant fraction and kissing fractions forced me to make a few notational decisions. Since the mediant fraction is not the sum, nor even really related to the sum, how should one write it? I use the “vee” symbol, as in

\frac{1}{2} \vee \frac{2}{3} = \frac{3}{5}.

I think the “vee” symbol is good since it is symmetric (like the mediant operation) and it points to where the mediant ends up: right between the fractions you start with (if the denominator is positive).

For kissing, I couldn’t resist using the heart symbol, as in

\frac{1}{2} \heartsuit \frac{2}{3}. since (1)(3) - (2)(2) = -1

Again the heart symbol is symmetric, and kissing is a symmetric relation. I hope I’m not getting carried away.

Now here is an activity for teachers who have made it all the way to the bottom of this blog post; an audience of 20-50 students is ideal. Write fractions on index cards; include all the reduced fractions between 0/1 and 1/1, with denominators up to 7 or 8 or 9. Your cards should include fractions like 2/5 and 3/7 and 1/4 and the like, one fraction per card.

Begin the activity by passing out the cards, and asking everyone with a card to stand up and line up in order of their (now personal) fractions. Quickly 0/1 and 1/1 will stand at opposite sides of the room. The activity usually takes a bit of time, as 2/5 and 3/7 have difficulty sizing each other up.

Next is a good opportunity to share how students compare fractions (common denominators, some weird butterfly technique, etc.).

Finally, have the students sit down, except for 0/1 and 1/1, who should stand at the corners of the front of the room. Ask them to add themselves, the wrong way (yielding 1/2), and ask 1/2 to stand between them. Then ask 0/1 and 1/2 to add themselves the wrong way, and ask the result (1/3) to stand between them. The students can take it from there… and they will remember the mediant fraction.

May the readers always understand signs, what they signify, and the difference between the two

Colorful programming

A few months ago, I signed up for CS 101 at  This provided a wonderful introduction to the Python programming language.  I was a pretty good Turbo Pascal programmer in high-school (early 1990s), but my programming since then had only involved short snippets in R (for statistics), SAGE (for research mathematics), and a bit of experimentation in javascript.  With Python, I finally feel like I can playfully program again.   I don’t have to worry about declaring various classes and main() things to control window objects.  Programming is fun and simple again, even if I’m only using basic functional programming constructs.

Beyond the fun, Python is useful to me in two ways. First, SAGE is wisely built upon Python, so by learning Python I can do much more in SAGE. Second, by using a Python script to output TikZ code (nothing fancy – just some string manipulations), I can create data-dense PDF graphics with mathematical precision and quality typography and color.  In other words, I have control over the graphics in my book.  Any ugliness or error is my own. An example of a graphic created with a Python script, TikZ, and LaTex, is the opening graphic for Chapter 3 found below. The Sieve of Eratosthenese is visualized by different color-filters for each prime; multiples of 2 (starting with 4) are sieved with a red line, multiples of 3 with a blue line, etc.. The white-space remaining is prime. But to see the resulting primes at the end, I switch to black-and-white, and reverse the white-space of the primes to thin black lines for the primes. This allows the reader to see the distribution of primes between 2 and 577, irregular jumps and all. To label the vertical axis, I have minimized ink by placing labels only at primes; there is no use labeling 100, 200, 300, or placing additional tick marks, when the primes themselves can be used for the same purpose.  Some fine-tuning might still be in order.

2-page spread, opening of Chapter 3
Click to enlarge the opening of Chapter 3

Now that I’ve become a Python advocate, I decided to go one step further and give Python code snippets throughout the Illustrated Theory of Numbers. You can see one in the margin on the right page. Inserting these snippets of code raises a lot of natural questions.

Why insert Python code instead of some universal pseudo-code? I am actively advocating Python, since I think the reader can benefit from learning Python, especially for future work in SAGE. Python is freely available and cross-platform. A C++ or Java programmer should be able to read Python code and translate easily enough into his or her native language.  Also, Python is surprisingly fast for an interpreted language!

Why insert code at all? Why not just make a download freely available? I plan to eventually post all code in the book, fully commented and a bit expanded (for exception-handling). This way, readers will be able to download the python script, import it, and compute to their heart’s content. But personally, I find something satisfying about personally typing short snippets of code and then clicking RUN. Maybe it reminds me of programming 20 years ago. It might be an issue of pacing. I like writing on the chalkboard as I lecture, because it sets a deliberate thoughtful pace. When I type in a code snippet myself, I think about each line and why it works. I hope readers can enjoy typing and modifying the short (5-15 lines) code snippets on their own.

Don’t existing software packages work better? The answer is certainly yes. I have not given code snippets which are perfectly optimized. I have aimed for a balance between readability and speed. Hopefully a reader can learn Python by experimenting with these snippets, and a reader with programming background can understand exactly how the snippets work. Optimizing code requires a sacrifice in clarity, or much more space for explanation. On the other hand, I have tried to give code that works well in practice, for a student of number theory. You’re not going to factor 50-digit numbers with the included code, but 10-digit numbers should factor very quickly. The included sieve code makes a list of prime numbers up to 1 million in 0.07 seconds on my MacBook Pro. This should be a good start for students, and if they want more power they can use PARI and SAGE, or maybe NZMath if they want pure Python.

A final word about the code-snippets: I still have not figured out how to properly attribute them. The Sieve of Eratosthenes snippet on the 2-page spread above is based on code posted by Robert William Hanks to StackOverflow on July 27, 2010. I will be asking the publisher for suggestions on how to make code citations in a wildly open-source world, and I appreciate any suggestions along the way.

With respect to history

Last winter, I had the privelege of teaching our History of Mathematics (Math 181) course at UC Santa Cruz. As I had lobbied previously for the course to satisfy the campuswide “textual analysis” requirement, I had to focus on primary sources in the class. Fortunately, I had plenty of fair warning and spent a few months reading and pretending to be a historian before the first day of class.

My goal in teaching was to have every student engage directly with at least two primary mathematical sources, in translation of course. The first resource was the textbook I chose: The Mathematics of Egypt, Mesopotamia, China, India, and Islam: a Sourcebook, edited by Victor Katz. This book is a goldmine, if you understand what it is. It is not a history of math textbook; rather, it presents a huge number of primary sources, some in short excerpts and some in extended passages, with background and guidance from five experts. This covered everything I wanted, except for Greek mathematics, for which primary and secondary source material is plentiful and free online. I enjoyed teaching from the Sourcebook and I have referred to it often, for enjoyment, and also in teacher education projects.

After reading the Sourcebook and other modern scholarship in the history of mathematics, I found the typical treatment of history in math textbooks inadequate (and often just plain false). Certainly some great mathematicians have ventured into a study of history; Dickson and Weil and van der Waarden are three prime examples. But I find their treatments most useful as annotated bibliographies. More appealing to me are treatments by David Fowler of Greek Mathematics; after reading Fowler I am convinced that “translating” Euclid into modern algebraic notation is historically destructive. On the other hand, I don’t have the time to bury myself in Chapter X of the Elements, trying to understand the whole text as Euclid’s contemporaries might have understood it.

Historical Notes, from Chapter 2
Click to enlarge the historical notes from Chapter 2.

In writing the Illustrated Theory of Numbers, I am trying to give respect to history.  Even if I devote less space to history than to mathematics, I hope I give them the same scholarly respect.  To that end, I have avoided spreading legends (like Gauss adding the numbers from 1 to 100) and I have avoided relying on secondary accounts as much as possible. I sometimes “translate” older sources into modern notation, but I try to raise a caution flag when this might be misleading. I incorporate historical information from China and India and elsewhere, to avoid Western bias as much as possible (given the history of scholarship and my Western-only language skills). At the end of each chapter, I am including some historical notes. These contain historical highlights and bits of primary source material and historical scholarship. In the style of Tufte, I have provided annotated citations in the margins.

Tools of the trade

Most authors of math texts do not design their books with two-page spreads in mind. Typically, an author types in LaTex, and trusts LaTex to handle all the formatting, page layout, etc.. But for an illustrated book, I care about page layout. I want the reader to open the book to any page, and find the content on the left complementary to the content on the right.

A few software innovations have made the illustration and layout of this book possible and free. One is the Tufte-LaTex package, which imitates the layout of Tufte’s books, especially the spacious margins for sidenotes. Another is the combination of PGF and TikZ for illustrations within LaTex. This package outputs to beautiful PDF, with color control in the CMYK colorspace. Moreover, using basic programming constructs within PGF/TikZ (and sometimes using personal Python scripts to output TikZ code), one can precisely place dots and weighted lines as necessary for mathematical figures, and integrate these figures seamlessly with text.

Below is a two-page spread (click to enlarge!) from the first chapter of the book, in which I count pairs in the set \{1,2,3,4,5,6,7,8,9,10\}.

A 2-page spread from Chapter 1
Click to enlarge a 2-page spread from Chapter 1.

The figure on the right-page exhibits what Tufte calls “small multiples”. There are 45 possible 2-element subsets of \{1,2,3,4,5,6,7,8,9,10\}. To illustrate the connection between 2-element subsets and points in a triangular arrangement, I produced a picture of all 45 subsets! Each small illustration (small triangle) fits into a large triangle, and the location of a small triangle in the large triangle also matches the location of a blue dot within the small triangle. The reader is meant to connect Figure 1.4 on the left page to the large figure on the right page, as the blue dots, red dots, and blue lines correspond (after a bit of rotation and folding).

Better late than never!

I have decided to chronicle my efforts to write and publish a book, the Illustrated Theory of Numbers. These efforts really began about seven or eight years ago, the first time I taught an introductory number theory class (Math 115 at UC Berkeley). Around the same time, I had started working with K-12 teachers, and I was inspired to take a visual and dynamic approach. Some unusual aspects of my class were: I introduced Gaussian integers and Eisenstein integers from the beginning, I used Conway’s topograph to study binary quadratic forms, and I followed Zolotarev’s proof of quadratic reciprocity.

Since then, I have taught similar material at UC Santa Cruz, and at the MMSS summer program at the University of Michigan. Each time I teach number theory, I find a few new approaches. Making number theory elementary might not be a virtuous goal in itself, but illustrating number theory is most rewarding.

When I first learned about number theory, I didn’t like it. I was given (or maybe I bought) a copy of Hardy and Wright’s classic text (An Introduction to the Theory of Numbers). From what I hear, this book has inspired generations of number theorists. But to me, early in my undergraduate career, it seemed like a large collection of unmotivated algebraic and analytic tricks. I didn’t get it. Instead, I enjoyed topology and complex analysis.

Later as an undergraduate, I had the great benefit of taking many (five, I think) courses with Goro Shimura. The first, I think, was a course on Riemann surfaces, meant as a second course in complex analysis. The second was a course in number theory. Incredibly, to me at the time, Shimura introduced aspects of number theory in parallel to what he had taught about Riemann surfaces — primes were analogous to points on a Riemann surface, and I was hooked. Around the same time, I took a “junior seminar” with John Conway, who taught us his beautiful approach to quadratic forms via the “topograph”. Since then, I have always taken a geometric approach to teaching number theory.

A few things have convinced me to write a number theory text — to enter a somewhat saturated market. First is that I cannot find any number theory texts which I find visually beautiful and suitable as an introductory text. This is the gap I hope to fill. A one-day course with Edward Tufte opened my eyes to the possibilities and importance of visual design. As Tufte explored visual design related to statistics in his first book (Visual Display of Quantitative Information), I hope to explore visual design related to introductory number theory in my first book. Hopefully I will not resort to taking out a second mortgage to self-publish!

Last year after teaching Math 110 at UCSC for the second time, I found myself with about 12 unpolished chapters of an illustrated number theory text. Now (with the security of tenure), I have begun polishing these chapters, adding more content and illustrations, with the goal of submitting parts of the book to a publisher by the end of the summer.

I have polished the first three chapters now, so this blog does not begin at the beginning. But with the next few posts I’ll try to catch up and share my experiences.