Monday, February 19, 2018

angels’ staircases

Here’s a pair of facts I hadn’t much considered before the last time I taught real analysis:

The only kind of discontinuity a monotone function can have are jump discontinuities.
A monotone function can have at most countably many discontinuities.

One thinks immediately of the floor function \(f(x) = \lfloor x \rfloor\), which has a jump of size 1 at every integer. It is possible to have infinitely many jumps within a finite interval; for instance, \(\frac{1}{\lfloor1/x\rfloor}\) has a jump at every unit fraction \(1/n\). But can a monotone function have a dense set of discontinuities, say, the set of rationals? Sure, here’s one:

That’s the graph of \[f(x) = \sum_{n=1}^\infty \frac{\lfloor nx\rfloor}{2^n}.\] It has a jump of size \(1/(2^q-1)\) at each fraction of the form \(p/q\) (when \(p/q\) is in reduced form, of course). Exercise. Why are these the sizes of the jumps? Keep in mind where the discontinuities of \(\lfloor nx \rfloor\) appear.

Here’s a general way to construct a monotone function \(f : \mathbb{R}\to\mathbb{R}\) whose set of discontinuities is your favorite countable set \(C\). Let \(c_1\), \(c_2\), \(c_3\), \(\dots\) be an enumeration of \(C\), and for each \(x\in\mathbb{R}\), set \[N(x) = \{ n\in\mathbb{N} : c_n \le x \} \] Let \(a_1\), \(a_2\), \(a_3\), \(\dots\) be a sequence of strictly positive numbers such that \(\sum a_n \lt \infty\). Then define \[ f(x) = \sum_{n\in N(x)} a_n. \] This function is discontinuous at each point in \(C\) and continuous at each point that is not in \(C\). (Exercise. Why? Keep in mind that the tail of a convergent series can be made arbitrarily small.) Essentially, we have created a distribution by placing a “delta mass” of weight \(a_n\) at the point \(c_n\), and \(f\) is the integral of this distribution from \(-\infty\) to \(x\).

When \(C\) is dense, the construction above produces a strictly increasing function \(f\), and moreover the image of \(f\) is nowhere dense. I call the graph of such a function an “angels’ staircase”, because \(f\) is a one-sided inverse of a “devil’s staircase” function \(g\)—that is, \(g\) is a monotone increasing function that is constant except on a set of measure zero. (MathWorld, on the other hand, uses “devil’s staircase” to refer to both kinds of functions.)

Saturday, August 05, 2017

boxes and fractions

Last week at MathFest, Dusa McDuff gave an excellent series of lectures on symplectic geometry. I enjoyed the second one the most, because in it she described the solution to a concrete problem that had a beautiful and expected answer, and used several tools of varying levels of difficulty. The result was published in the Annals of Mathematics in 2012; you can get the paper here. I won’t be referring to it for the rest of the post, however. Instead I want to highlight one elementary construction she described during this lecture.

About halfway through the talk, McDuff made a comment along the lines of, “Here’s something I must have learned in elementary school, but I’ve been surprised by how many mathematicians don’t know it.” I certainly don’t recall having seen it, at least not in the generality she described, and I do think people of all ages and mathematical abilities could enjoy playing with it.

Start with any fraction—say, \(30/13\)—and make a rectangle whose side lengths are the numerator and the denominator of the fraction.

Now start marking off squares, as large as possible, inside the rectangle. In this example, we can cut off two \(13 \times 13\) squares at first.
When no more large squares fit, start marking off squares from the remaining rectangle along the side.
Continue until you run out of space. In this example, only one more step in the process is needed.
When you’re finished, you will have filled the rectangle with squares of various sizes.
Count how many squares you have of each size and put those numbers in sequence. In this example, we have two large squares, three medium squares, and four small squares, so the sequence is 2, 3, 4. (Yes, I chose the fraction \(30/13\) to get this sequence.) Now write these numbers into a continued fraction, as follows: \[ 2 + \cfrac{1}{3 + \cfrac{1}{4}}. \] To evaluate a continued fraction, we start at the bottom and work through the nested operations: \[ 2 + \cfrac{1}{3 + \cfrac{1}{4}} = 2 + \cfrac{1}{\cfrac{13}{4}} = 2 + \frac{4}{13} = \frac{30}{13}. \] The result is the fraction we started with!

Here’s another example. If we start with the fraction \(25/7\) and follow the same process, we get this picture.

This time there are four different sizes of boxes. Counting the number of boxes of each size gives the sequence 3, 1, 1, 3, and we can check that \[ 3 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{3}}} = 3 + \cfrac{1}{1 + \cfrac{3}{4}} = 3 + \frac{4}{7} = \frac{25}{7}. \]

I had fun figuring out why this works, so in the interest of keeping this post short, I’ll leave that as an exercise for the reader. A hint: the process of cutting off squares is essentially Euclidean division.

Although we started with rectangles whose side lengths are integers, there’s no reason to restrict the above process to that case. In fact, if this process seems familiar, you may have seen it before in the special case of a golden rectangle, in which only one square of each size can be included:

This is related to the fact that the (infinite) continued fraction of the golden ratio has all \(1\)s: \[ \frac{1 + \sqrt{5}}{2} = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}} \] which I explained in another way in my last post.

One more example worth considering. Here is the start of the process when the side lengths of the rectangle are \(\pi\) and \(1\):

So there are three of the largest boxes, seven of the next largest, then fifteen of the next size (although the resolution of this image doesn’t let you see that). The fact that the first two steps nearly fill the entire rectangle is why \(3 + 1/7 = 22/7\) is such a good approximation for \(\pi\).

P.S. Dusa McDuff is also married to John Milnor, who gave the Hedrick Lectures in 1965. What other husband-and-wife pairs (or other pairs of family members) have both given the same high-profile math lecture series?

Sunday, June 25, 2017

addition of fractions is bilinear

The prototypical example of a bilinear operation is multiplication, \(b(x,y)=xy\). For a function of two variables, bilinear means “linear in each variable.” That means multiplication has the following properties: \[ b(x_1+x_2,y) = b(x_1,y) + b(x_2,y) \] \[ b(x,y_1+y_2) = b(x,y_1) + b(x,y_2) \] \[ b(cx,y) = b(x,cy) = cb(x,y) \] Most operations that are called some kind of “product” (e.g., inner product, cross product, wedge product) get this name, at least in part, because they have the above properties.

Addition is also a function of two variables, but it is not linear in either variable; all of the above axioms fail. So how could it be bilinear? Read on!

Fractions are curious things, because they are pairs of things: a fraction has a numerator (which numerates, meaning it counts some number of things) and a denominator (which denominates, meaning it names the type of thing being counted). And we assume that the numerator and denominator are themselves the same type of thing (whether integers, polynomials, or what have you), so that we can make sense of the equality of fractions: we say \(p/q\) and \(r/s\) are equal if \(qr = ps\).

(I have heard that my grandfather-in-law, who was also a college math professor, claimed it was self-evident that college students should be confused by fractions, in rebuttal to those who would say that fractions are trivial once one has reached the level of college mathematics; \(2/4\) and \(1/2\) are either not clearly the same, or clearly not the same.)

Leaving aside the equality of fractions for a moment, addition of fractions is also a curious thing. The most obvious operation is to add the numerators and denominators separately. This is sometimes called Farey addition, which is a rich topic that truly deserves its own treatment. Let’s use \(\oplus\) to write this kind of addition: \[ \frac{p}{q} \oplus \frac{r}{s} = \frac{p + r}{q + s}. \] That’s not how addition of fractions is usually defined, however. Instead, we produce a new denominator which is a product of the old denominators, and a new numerator which takes into account both the old numerators and the old denominators in a product-y sort of way: \[ \frac{p}{q} + \frac{r}{s} = \frac{ps + qr}{qs} \] (Indeed, you might recognize the numerator as the inner product of \((p,q)\) and \((s,r)\), or of \((q,p)\) and \((r,s)\). In either case, one of the pairs has its numerator and denominator switched.) Perhaps now you see where the title of the post comes from: addition of fractions is bilinear when we treat the fractions as pairs (Farey addition is, after all, essentially vector addition): \[ \left(\frac{p_1}{q_1}\oplus\frac{p_2}{q_2}\right) + \frac{r}{s} = \left(\frac{p_1}{q_1} + \frac{r}{s}\right) \oplus \left(\frac{p_2}{q_2} + \frac{r}{s}\right) \] \[ \frac{p}{q} + \left(\frac{r_1}{s_1}\oplus\frac{r_2}{s_2}\right) = \left(\frac{p}{q} + \frac{r_1}{s_1}\right) \oplus \left(\frac{p}{q} + \frac{r_2}{s_2}\right) \] \[ \frac{cp}{cq} + \frac{r}{s} = \frac{p}{q} + \frac{cr}{cs} = \frac{c(ps + qr)}{c(qs)} \] The last property above is what makes addition of fractions well-defined, meaning that if we replace one fraction in the sum with an equivalent fraction, then the resulting sum is equivalent to the original sum.

This is all very cute and would simply be a curiosity, but I’m writing about it because this property of bilinearity recently helped me understand something about continued fractions.

A finite continued fraction is an expression of the form \[ a_0 + \cfrac{b_1}{a_1 + \cfrac{b_2}{a_2 + \cfrac{b_3}{\ddots + \cfrac{b_{n-1}}{a_{n-1} + \cfrac{b_n}{a_n}}}}} \] (In a simple continued fraction we assume that all of the \(b_i\) equal \(1\), but for my purposes here there’s no reason to make that assumption.) The operations are nested, so to find the value of this expression, we start from the bottom. For example, \[ 1 + \cfrac{2}{3 + \cfrac{4}{5 + \cfrac{6}{7}}} = 1 + \cfrac{2}{3 + \cfrac{4}{\cfrac{41}{7}}} = 1 + \cfrac{2}{3 + \cfrac{28}{41}} = 1 + \cfrac{2}{\cfrac{151}{41}} = 1 + \dfrac{82}{151} = \dfrac{233}{151} \] An infinite continued fraction has the same form as a finite continued fraction, except that the nesting doesn’t stop: \[ a_0 + \cfrac{b_1}{a_1 + \cfrac{b_2}{a_2 + \cfrac{b_3}{a_3 + \ddots}}} \] To make sense of this expression, we need—as is typical in such cases—to consider a sequence of finite continued fractions that should “approximate” this infinite continued fraction. If we truncate the infinite continued fraction after \(a_n\), then we get its \(n\)th convergent, which we write as \(p_n/q_n\). If the sequence of convergents converges, well, then, its limit is the value of the infinite continued fraction. (The Mathologer has an excellent video on infinite continued fractions, which includes an example of an apparent paradox that can arise from an infinite continued fraction that doesn’t converge.)

The definition is nice as far as it goes, but wouldn’t it be even nicer to know how successive convergents are related? That is, how can we get \(p_{n+1}/q_{n+1}\) from earlier convergents? Fortunately, there are simple recurrence relations due to Euler and Wallis: \[ p_{n+1} = a_{n+1} p_n + b_{n+1} p_{n-1}, \qquad q_{n+1} = a_{n+1} q_n + b_{n+1} q_{n-1}. \] It was in trying to understand these formulas that I got stuck. Finite continued fractions, as explained above, are computed from the bottom up. But when we move from the \(n\)th convergent to the \((n+1)\)st convergent of an infinite continued fraction, we add a new term to the bottom. That is, we change the start of the computation, not the end of it. That throws off my instincts for how recurrence should work.

It’s easy to find proofs of the Euler–Wallis recurrence relations. Most of them use induction, which is fine. But many also implicitly use the fact that continued fractions “can be” defined with real numbers for \(a_i\) and \(b_i\), not just integers. I never specified integers in the definitions above, either, but in many cases one wants to make that restriction, including the purpose for which I’ve been studying continued fractions. I felt it should be possible to prove such a fundamental relationship without leaving the natural “context” of whatever type of numbers was allowed to begin with.

Here is where the bilinearity of fraction addition came to my aid. One of the nice things about bilinear operations is that, if you fix one input, the result is just an ordinary linear function with respect to the other input, which can represented by a matrix. If we fix \(p/q\), say, and add to it a variable fraction \(x/y\), and represent the fractions as vectors (since we’re thinking of them as pairs anyway), then the calculation of the sum \(p/q+x/y\) becomes \[ \begin{pmatrix} py + qx \\ qy \end{pmatrix} = \begin{pmatrix} q & p \\ 0 & q \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}. \] When computing continued fractions, we repeatedly start with a fraction, invert it, multiply the (new) numerator by some quantity, and add another value. All of these have representations as linear transformations: the reciprocal of \(x/y\) is given by \[ \begin{pmatrix} y \\ x \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}. \] Multiplying the numerator of a fraction \(x/y\), say by a constant \(c\), is given by \[ \begin{pmatrix} cx \\ y \end{pmatrix} = \begin{pmatrix} c & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \] Putting together the above linear transformations, we find that if \(a\) and \(b\) are fixed, then the matrix form of the transformation that sends \(x/y\) to \(a+b/(x/y)\) is \[ \begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix} \begin{pmatrix} b & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} a & b \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \] We can find \(p_n/q_n\), then, by starting with \(a_n = a_n/1\) and applying the above procedure repeatedly: \[ \begin{pmatrix} p_n \\ q_n \end{pmatrix} = \begin{pmatrix} a_0 & b_1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_1 & b_2 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_{n-1} & b_n \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_n \\ 1 \end{pmatrix} \] However, something is aesthetically “off” with this formula: the \(a\) term and the \(b\) term in each matrix on the right have different indices.

Let's try rearranging our steps so that like indices get grouped together: first invert the fraction, then add \(a\), then multiply the denominator of the result by \(b\) (which works out correctly, because in the next round the first thing we’ll do is invert again). This sequence of steps produces the formula \[ \begin{pmatrix} 1 & 0 \\ 0 & b \end{pmatrix} \begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} a & 1 \\ b & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \] To make this work in computing the \(n\)th convergent of a continued fraction, we need to start with \(a_n/b_n\) (already promising), and we need to set \(b_0 = 1\) so that when we divide by it, we don’t change the final value (we were missing a \(b_0\) anyway, which was also somewhat unsatisfying). Therefore, to find \(p_n/q_n\) by repeated linear transformations, we have \[ \begin{pmatrix} p_n \\ q_n \end{pmatrix} = \begin{pmatrix} a_0 & 1 \\ b_0 & 0 \end{pmatrix} \begin{pmatrix} a_1 & 1 \\ b_1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_{n-1} & 1 \\ b_{n-1} & 0 \end{pmatrix} \begin{pmatrix} a_n \\ b_n \end{pmatrix} \] We can improve this formula a bit more by thinking about where \(a_n/b_n\) came from. If we followed the same steps as before, then we must have inverted something, added it to \(a_n\), and multiplied the denominator of the result by \(b_n\). The thing we must have added to \(a_n\) is \(0 = 0/1\), which came from “inverting” \(1/0\). Thus, if we set \(p_{-1} = 1\) and \(q_{-1} = 0\), then the following equation holds for all \(n \ge 0\): \[ \begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix} = \begin{pmatrix} a_0 & 1 \\ b_0 & 0 \end{pmatrix} \begin{pmatrix} a_1 & 1 \\ b_1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_{n-1} & 1 \\ b_{n-1} & 0 \end{pmatrix} \begin{pmatrix} a_n & 1 \\ b_n & 0 \end{pmatrix} \] Whenever you end up with a formula this beautiful, you know you must have done something right.

It was an encounter with this matrix representation in a set of number theory notes that sparked the thoughts that led to this post. That set of notes did not contain a proof of the matrix formula, however. A few other sources that I have since found do use this formulation and prove it, such as this set of notes, which also includes a similar discussion to mine.

Back to the question of proving the Euler–Wallis recurrence relations. Suppose we have computed the \(n\)th convergent of a continued fraction, and we wish to proceed to the \((n+1)\)st convergent. In our new formulation, that just means appending another matrix to the product: \[ \begin{pmatrix} p_{n+1} & p_n \\ q_{n+1} & q_n \end{pmatrix} = \begin{pmatrix} a_0 & 1 \\ b_0 & 0 \end{pmatrix} \begin{pmatrix} a_1 & 1 \\ b_1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_n & 1 \\ b_n & 0 \end{pmatrix} \begin{pmatrix} a_{n+1} & 1 \\ b_{n+1} & 0 \end{pmatrix} \]

If we group all but the last matrix on the right together, use the previous equation, and then carry out the final multiplication, we get: \[ \begin{pmatrix} p_{n+1} & p_n \\ q_{n+1} & q_n \end{pmatrix} = \begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix} \begin{pmatrix} a_{n+1} & 1 \\ b_{n+1} & 0 \end{pmatrix} = \begin{pmatrix} a_{n+1} p_n + b_{n+1} p_{n-1} & p_n \\ a_{n+1} q_n + b_{n+1} q_{n-1} & q_n \end{pmatrix} \] Thus, the Euler–Wallis recurrence relations are a consequence of the fact that matrix multiplication is associative (and also the fact that addition of fractions is bilinear!).

As a bonus, the difference between successive convergents is now seen to be a consequence of the fact that the determinant is multiplicative: \[ \begin{vmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{vmatrix} = \left\vert \begin{pmatrix} a_0 & 1 \\ b_0 & 0 \end{pmatrix} \begin{pmatrix} a_1 & 1 \\ b_1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_{n-1} & 1 \\ b_{n-1} & 0 \end{pmatrix} \begin{pmatrix} a_n & 1 \\ b_n & 0 \end{pmatrix} \right\vert \] \[ p_n q_{n-1} - p_{n-1} q_n = (-1)^{n+1} b_1 b_2 \cdots b_n \] \[ \frac{p_n}{q_n} - \frac{p_{n-1}}{q_{n-1}} = (-1)^{n+1} \frac{b_1 b_2 \cdots b_n}{q_n q_{n-1}} \] An infinite continued fraction can therefore be written as an alternating series: \[ a_0 + \cfrac{b_1}{a_1 + \cfrac{b_2}{a_2 + \cfrac{b_3}{a_3 + \ddots}}} = a_0 + \sum_{n=1}^\infty (-1)^{n+1} \frac{b_1 \cdots b_n}{q_n q_{n-1}}. \] When all of the \(a_i\)s and \(b_i\)s are positive, the condition for this series to converge is essentially that the \(b_i\)s don’t grow too quickly with respect to the denominators \(q_n\). In particular, if \(b_i = 1\) for all \(i\) (as in the case of a simple fraction) and \(a_i \ge 1\) for all \(i\), then the \(q_n\)s grow exponentially fast, and so the series (and hence the infinite continued fraction) is guaranteed to converge!

No introductory piece on continued fractions is complete without mentioning Fibonacci numbers and the golden ratio. Let \(\phi\) be the number defined by the infinite continued fraction \[ \phi = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}} \] that is, \(a_i = b_i = 1\) for all \(i\). Then we have \[ p_{-1} = 1, \qquad q_{-1} = 0, \qquad p_0 = 1, \qquad q_0 = 1 \] \[ p_{n+1} = p_n + p_{n-1}, \qquad q_{n+1} = q_n + q_{n-1} \qquad \forall\ n. \] Then, with the convention that the Fibonacci numbers \(F_n\) are defined by \[ F_0 = 0, \qquad F_1 = 1, \qquad F_{n+1} = F_n + F_{n-1} \] we have \(p_n = F_{n+2}\) and \(q_n = F_{n+1}\) for all \(n \ge -1\). Using the matrix formulation for computing convergents of \(\phi\), this means \[ \begin{pmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{pmatrix} = \begin{pmatrix} p_n & p_{n-1} \\ q_n & q_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n+1} \] (Try it!) On the other hand, the continued fraction equation for \(\phi\) implies that \[ \phi = 1 + \dfrac{1}{\phi}, \] which is the defining equation for the golden ratio, and has the solution \(\phi = \dfrac{1 + \sqrt{5}}{2}\). (We reject the negative solution because the value of the continued fraction is positive.) So it follows immediately that \[ \lim_{n\to\infty} \frac{F_{n+1}}{F_n} = \frac{1 + \sqrt{5}}{2} = 1 + \sum_{n=1}^\infty \frac{(-1)^n}{F_n F_{n+1}}. \]

If I have time, another day I’ll explain what all of this has to do with hyperbolic geometry, the Farey–Ford tessellation, and the dynamics of circle rotations.

Wednesday, March 15, 2017

existence and uniqueness for some simple ODEs

Last week in my analysis class we discussed ordinary differential equations (ODEs) and their solutions. The proof of the existence and uniqueness of solutions to ODEs is one of my favorite examples of an extremely abstract theorem (in this case, the contraction mapping principle) being used to solve a concrete problem (how do we know if an ODE has a solution, and if so, whether it’s uniquely specified by its initial conditions?). This post is just to give some simple examples that unearth the concerns one might have.

Here are the three examples I’d like to consider: \[ y' = y, \hspace{0.5in} y' = y^2, \hspace{0.5in} (y')^2 = y. \] The first equation is familiar as characteristic of exponential functions. With the initial condition \(y(t_0) = C\), we obtain the solution \(y(t) = Ce^{t-t_0}\). Thus every initial condition results in a globally-defined solution. With this solution in hand, we can even show that it is unique, by a bit of trickery. Suppose \(f(t)\) is any solution to the initial value problem \(y'=y\), \(y(t_0)=C\), and consider the function \(g(t)=\frac{Ce^{t-t_0}}{f(t)}\). Then \[ g'(t) = \frac{f(t) Ce^{t-t_0} - f'(t) Ce^{t-t_0}}{(f(t))^2} = \frac{Ce^{t-t_0}}{(f(t))^2}(f(t) - f'(t)). \] But by assumption \(f'(t) = f(t)\), so \(g'(t) = 0\). Thus \(g(t)\) is constant, and because \(g(t_0) = 1\), we must have \(g(t)=1\) for all \(t\). Therefore \(f(t) = Ce^{t-t_0}\). (How does the case where \(f(t) = 0\) for some \(t\) need to be handled?)

The form of the second equation suggests that its solutions, once they get above \(y = 1\), should grow faster than exponential functions, because the growth rate depends quadratically on \(y\) rather than linearly. A bit of thought suggests the solution \(y(t) = -\frac{1}{t}\); by translating in the \(t\)-direction, we can satisfy any initial condition with a solution of the form \(y(t) = -\frac{1}{t-a}\). Again, the solution is uniquely specified by its initial condition. But these solutions are no longer globally defined; each one “blows up” at some finite time, either before or after the point at which we specify the initial condition. This shows that in general we cannot expect global solutions to ODEs; the usual existence theorem only guarantees local existence of solutions (although global existence can be guaranteed by stronger hypotheses, which are rarely satisfied).

The third equation looks similar to the second, but squaring the \(y'\) term rather than \(y\) has some major consequences. First, the equation implies that solutions must be non-negative. This is not serious, however; changing the equation slightly to \((y')^2 = |y|\) allows solutions to be negative. More serious is the fact that both of the following functions are solutions that satisfy the initial condition \(y(t_0) = 0\): \[ y(t) = 0 \hspace{1in} y(t) = \frac14(t - t_0)^2. \] Indeed, by piecing together these two types of solutions, we can obtain solutions that remain 0 for any length of time, then “take off” unexpectedly. In short, we have existence, but we definitely do not have uniqueness, because as soon as a solution reaches zero, it can remain zero for an indeterminate amount of time. (We do have local uniqueness for solutions that have a non-zero initial condition, however.) The issue is that the equation allows the derivatives of its solutions to grow and shrink too quickly when they are near zero; more precisely, the function \(\sqrt{|y|}\) is not Lipschitz in any interval containing 0.

As I said, my purpose here is not to expound the statement or proof of any theorem on existence and uniqueness, just to provide some simple examples that illustrate what considerations must be made in formulating such a theorem.

Friday, August 19, 2016

specifications in analysis

Earlier this week, I wrote about expectations for my analysis class this fall (which also apply broadly to upper-level math classes) and some things I learned about specs grading this summer. In this post, I’ll share the specifications I have created for analysis. (I have taught real analysis before, and last time I tried a standards-based approach. Frankly, that basically turned into a point system, albeit a simplified one, which is why I’m trying something completely different this time.)

The rest of the post is taken verbatim from (the current draft of) my syllabus.

Effective learning requires effective methods of assessment. The assessments should relate as directly as possible to the expectations of the class, and they should provide both feedback on how to improve and opportunities to demonstrate improvement as the semester progresses. In my experience, “traditional” grading schemes based on assigning points or percentages to individual tasks do not serve these functions well. Therefore, this course adopts specifications grading*, in which grades are tied to specific outcomes. This is likely to be different from grading policies in other classes you have taken, so feel free to ask me questions or let me know if you have concerns. I hope that this system will make clear the connections between the expectations stated in the previous section and the ways you will be assessed.

Overall grading. At the end of the semester, I am required to submit to the university a letter grade reflecting your achievement in this class. That grade will be determined on the basis of a set of specifications in four areas: (1) class participation, (2) written proofs, (3) exams, and (4) synthesizing activities. Each of these areas will receive a simple grade of A, B, C, D, or F. The following sections describe how these grades will be determined. Your final grade will depend on your performance in all four areas, according to the following table.

Final grade based on individual grades of
A all As, or 3 As and 1 B
A– two As and two Bs
B+ one A and three Bs
B all Bs, or 3 Bs and 1 C
B– two Bs and two Cs
C+ one B and three Cs
C all Cs, or 3 Cs and 1 D
D– two Cs and two Ds
I will use my discretion to assign a final letter grade to other combinations of individual letter grades.

Class participation. Attendance at every class meeting is required. Most weeks, we will alternate days between discussing reading assignments and presenting solutions to exercises. The end of this syllabus has a schedule of what we will be doing in class each day (with allowance for adjustments, as needed).

Reading. In order to participate effectively on discussion days, you will need to read the textbook before coming to class. Each reading assignment is about 10 pages. The textbook attempts to be very accessible, but that does not mean it is easy. We will be working with ideas that stretch reason and imagination. You should be prepared to spend at least 1–2 hours on each reading assignment; rereading pages, paragraphs, or sentences; working out examples; and writing questions or comments in the margins or on separate paper. You should be especially mindful of definitions. These are not always set apart from the text, so pay attention when new vocabulary is introduced. Start working on a list of definitions and theorems from the start of the semester. The chapter summaries can be an aid in this process.

Collaborating. On days with a reading assignment, you will work in small groups to discuss the material. I will assign these groups at the start of each week. You should bring your own questions and thoughts to these discussions. If there is extra time, you can also discuss the current set of exercises.

Presenting. On the remaining days, you will take turns presenting solutions to exercises distributed previously. The solution you present does not necessarily need to be entirely correct, but it should show evidence of a serious effort. You should also be prepared to answer questions from me or other students. To maintain balance, no one will be allowed to present more than once every two weeks, unless every student in the class has already presented during that time period. In exceptional cases, some of these verbal presentations may be made to me outside of class (no more than one per student).

To earn a you must do the following
D attend at least 75% of class meetings
present at least one proof in class
C attend at least 85% of class meetings and contribute to discussions
present at least three proofs in class
B attend at least 90% of class meetings and contribute to discussions
present at least four proofs in class
A attend all class meetings (2 unexcused absences allowed) and contribute to discussions
present at least five proofs in class

Written proofs. Over the semester, you will develop a portfolio of work that you have submitted for formal assessment. Most of your contributions will be proofs. Each week I will indicate one or more exercises whose solutions could be submitted to your portfolio. You may discuss your work with other students in the class, to have them check whether it meets the standards of the class and give you feedback. A proof for the portfolio is due the Monday after it is assigned. These proofs must be typed using LaTeX, Google docs, Microsoft Word, or another system.

When you submit a written proof for your portfolio, I will judge whether it is Successful, Quasi-successful, or Unsuccessful (see the earlier section on “Proofs” under “Expectations” for details about these ratings), and mark it correspondingly with one of S/Q/U. Proofs marked Q or U will not be counted towards your grade. However, proofs can be resubmitted at the cost of one or two of your allotted tokens; see section on “Tokens” below.

To earn a your portfolio must contain
D at least four successful proofs
C at least six successful proofs
B at least eight successful proofs
A at least ten successful proofs

Exams. There will be two midterm exams and a final exam. Each one will have a take-home portion and an in-class portion. [Dates and times, listed in syllabus, omitted here.]

The take-home portions will consist of two or three proofs that you are to complete on your own, without consulting other students. (You may discuss your work with me before turning in the exam, although I might not answer questions directly.) These will be judged as successful, partially successful, or unsuccessful, like the proofs in your portfolio. They cannot be resubmitted after grading, however.

The in-class portions will test your mastery of definitions and the statements of theorems. You will need to be able to state both definitions and theorems properly. You will also be asked to recognize and provide examples of situations or objects where a definition or theorem does or does not apply.

To earn a you must do the following
D correctly answer 60% of in-class test questions
write at least two successful proofs on take-home exams
C correctly answer 75% of in-class test questions
write at least three successful proofs and one quasi-successful proof on take-home exams
B correctly answer 85% of in-class test questions
write at least four successful proofs and two quasi-successful proofs on take-home exams
A correctly answer 95% of in-class test questions, write six successful proofs on take-home exams

Synthesis. To master the ideas of the class, you must spend time synthesizing the material for yourself. The items in this graded section will be added to your portfolio, to complement the proofs. All materials in this section must be typed using LaTeX, Google docs, Microsoft Word, or another system.

List of definitions and theorems. It should be clear at this point that being able to produce accurate statements of definitions and theorems is essential to success in this class. To encourage you to practice these, I am requiring you to create a list of these statements for the entire course. Your list should be organized in some way that makes sense to you—e.g., alphabetically or chronologically.

The textbook can be used as a reference, as can the internet, but how do you quickly recall what definitions we’ve used and how they're related? How do you find the phrasing of a theorem that’s become most familiar? This list should help you in these situations. More importantly, creating it will help you review and organize the material in your own mind.

I will verify your progress on these lists at each in-class exam.

Papers. Twice during the semester, once in the first half and once in the second half, I will provide a list of topics that we have been discussing, from which you can choose to base a paper on. These will be due approximately two weeks after the midterm exams.

There is a third paper that can be completed at any point in the semester on a topic of your choosing, but you must get the topic approved by me before Thanksgiving.

These papers will for the most part be expository, meaning they will present previously known mathematical results (not original research). Here are the requirements for a paper to be acceptable:

  • It should have 1500–4500 words.
  • It should use correct grammar, spelling, notation, and vocabulary.
  • It should be organized into paragraphs and, if you wish, sections.
  • It should cover the topic clearly and reasonably thoroughly, with an intended audience of other math students (who may be assumed to have studied as much analysis as you).
  • It should contain a proof of at least one major result.
  • The writing should be original to you. Of course, small pieces like definitions may be taken directly from another source, but apart from these the paper should be your own work.
  • Citations are generally not necessary in expository mathematical writing, except for the following: a statement of theorem that you are not proving, a peculiar formulation of a concept/definition, or a creative idea (e.g., an uncommon metaphor or illustration) from another source.
  • You may choose to follow the style of our textbook, or a more formally structured math textbook, or something more journalistic or creative, as long as the previous criteria are met.
Papers that do not meet these criteria will be considered unsatisfactory and will not count towards your grade. An unsatisfactory paper can be revised and resubmitted at the cost of three tokens.

To earn a you must do the following
D create a list of definitions and theorems to include in your portfolio
C create a list of definitions and theorems to include in your portfolio
write a paper on one of the topics provided
B create a list of definitions and theorems to include in your portfolio
write two papers on the topics provided, one during each half of the semester
A create a list of definitions and theorems to include in your portfolio
write two papers on the topics provided, one during each half of the semester
write a third paper on a topic of your own choosing related to the class

Tokens. You start out the semester with seven (7) virtual “tokens,” which can be used in various ways:

  • One token allows you to resubmit a written proof initially judged to be quasi-successful (must be used within one week of initial grading).
  • Two tokens allow you to resubmit a written proof initially judged to be unsuccessful (must be used within one week of initial grading).
  • Three tokens allow you to resubmit an unsatisfactory paper (must be used within one week of receiving paper back).
  • One token gives you a 48 hour extension past the due date for a paper.
Unused tokens may be exchanged for a prize at the end of the semester. [maybe?!?]

*Based on Linda Nilson’s book Specifications Grading: Restoring Rigor, Motivating Students, and Saving Faculty Time.

Thursday, August 18, 2016

taking specs seriously

I’ve been an advocate of standards-based grading since I started using it over three years ago. It has addressed many of the concerns I had about the dominant point-based grading system and encouraged students to move forward in their understanding rather than feeling trapped by past performance.

I’m not solely an SBG proponent when it comes to grading, however. For one thing, I find it hard to adapt SBG to upper-level math courses. For another, the time seems ripe for experimentation in grading practices as more of us realize the shortcomings of what we have inherited from decades past. Not that we should constantly reinvent the grading process, but we should be open to various thoughtful ways of providing authentic assessment.

So I was certainly interested a couple of years ago when several fellow instructors began talking about specifications grading, a method espoused by Linda Nilson in her book Specifications Grading: Restoring Rigor, Motivating Students, and Saving Faculty Time. I adopted some of the ideas I heard and appreciated the increased flexibility it offered.

However, it was not until this summer that I read through Nilson’s book. It was useful because it seems Nilson and I think differently in ways I can’t quite put my finger on, and so the book has lots of ideas I would not have intuited on my own. Here are a few of the things I garnered from reading the book that I hadn’t picked up from online discussions (not that these things weren’t said, but this time they stuck):

  • Sometimes it’s OK to use percentages. I’ve been highly points- and percentages-averse since starting SBG. Percentages, my argument went, were essentially meaningless, because they’re constantly being curved (so they don’t really represent a “percentage” of anything) and the difference between 80% and 81% is essentially a coin toss (so they aren’t as linearly ordered as people like to think). But that argument isn’t uniformly true. In a course where precision is important, it is possible to measure, for instance, how many definitions a student can correctly state. For my upcoming analysis class, I expect “A” students to get definitions right 95% of the time, “B” students 85% of the time, “C” students 75% of the time. This really is quantifiable, and a definition is either correct (with respect to the established conventions of the subject) or not, so each one can be graded yes/no. As long as not everything is forced into a percentages model, this can be an effective way to give feedback.
  • Make students work for an A, but give them some choice in how to get there. As instructors, we want an A to represent mastery, an indication that the student can think nimbly and complexly about the subject. Ideally, students who earn an A will be the ones most invested in the subject. To demonstrate all this, students should have ownership of their work. They should make meaningful choices that reflect their interests and their skills as well as the subject at hand.
  • Not everyone has to do everything. This is closely tied to the previous point. Nilson uses the metaphor of “hurdles”: grade levels can be differentiated by having students clear either higher hurdles (more complex, better quality work) or more hurdles (more extensive work), or a mix of the two. I’m not generally a fan of having students earn higher grades by just proving they can do more—that takes more of my time, and more of theirs. But true mastery requires a measure of initiative. Having a small number of optional assignments that give students opportunities to distinguish themselves makes sense as part of a larger grading scheme.
  • There are good reasons to limit reassessments. Of course, one of these reasons is the subtitular “saving faculty time.” In past upper-level classes where I’ve allowed essentially unlimited resubmission, I’ve been swamped/behind at several points in the semester as students frantically tried to get something accepted. But that’s not even the best reason. By limiting reassessments and grading work pass/fail (or pass/progressing/fail or some other variant), students are encouraged to submit their best work each time, and to spend extra time making sure they check its quality before asking me to do so. The onus is on me to establish clear expectations, and on students to meet them. We’re not negotiating what’s acceptable through repeated revision and grading.
I also found the chapter on cognitive models (Chapter 3, “Linking Grades to Outcomes”) helpful in considering what it means to have a higher level of mastery; previously I wasn’t really familiar with anything beyond Bloom’s Taxonomy.

If this post was of interest to you, I hope you’ll consider joining the Google+ Community on “Standards-Based and Specifications Grading” (SBSG), where teachers of diverse disciplines are meeting to discuss how to implement these two particular alternative forms of grading.

Tomorrow I’ll share my full set of specifications for real analysis.

Tuesday, August 16, 2016

expectations in analysis

I’m working on the syllabus for my (junior and senior level) analysis class this fall, and I’d like to share some parts of it, hopefully thereby eliciting feedback. The main thing I’m concerned about is the type of specifications grading I’m adopting for the class—I’ll share that later this week. This post is about establishing the expectations of the course, on which the specifications will be based. None of these are particular to analysis; they establish what I believe any student in an upper-level mathematics course should achieve.

The rest of the post is taken verbatim from (the current draft of) my syllabus.

To learn mathematics, it is essential to engage actively with the material. This is especially true at this stage in your mathematical careers, as the focus of study shifts from developing computational tools to examining underlying concepts and practicing abstract reasoning. This shift may be described as a move from pre-rigorous thinking, which is informal and intuitive, to rigorous thinking, which is formal and precise. (This terminology has been suggested by mathematician Terence Tao; he also includes a post-rigorous stage, in which professional mathematicians work, where one is able to make intuitive arguments that are grounded by formal training.)

The content of this course resides in definitions, theorems, and proofs. You will be expected to state both definitions and theorems accurately and to illustrate them through examples. Mathematics is not merely a collection of disconnected facts, however, and so you will also develop your logical skills by proving mathematical truths, linking definitions to their profound consequences captured by theorems. All of this will happen in the context of a community—two really, our class and the larger mathematical community.

Definitions. In mathematics, as in other sciences, it is necessary to quantify what is being studied and to be able to identify what is of interest at each moment. This is done by carefully establishing and internalizing definitions. This is not to say that definitions do not involve creativity; as a subject develops, often definitions evolve to encompass more or fewer cases, to be more precise, or to reorganize ideas.

By the end of the course, you should be able to:

  • state definitions accurately and explain any notation or previously-defined terms they contain;
  • identify whether or not an object meets the conditions of a given definition;
  • give examples that satisfy a given definition as well as examples that do not satisfy it;
  • test an unfamiliar definition using examples;
  • create new definitions when needed.

Theorems. A theorem has two parts: the antecedent (its assumptions) and the consequent (its conclusions). To take a familiar example, the equation \(a^2 + b^2 = c^2\) by itself is not a theorem; rather, the Pythagorean Theorem states that “If \(c\) is the length of the hypotenuse of a right triangle, and \(a\) and \(b\) are the lengths of its other two sides, then \(a^2 + b^2 = c^2\).” A theorem may not always include the words “if” and “then,” but you should always be able to determine what are the antecedent and the consequent. Sometimes rephrasing the theorem’s statement can help. For example, “Every differentiable function is continuous” can be rephrased as “If a function is differentiable, then it is continuous.” In most cases, the consequent does not imply the antecedent (e.g., not every continuous function is differentiable). A theorem that says one set of conditions holds “if and only if” another set of conditions holds is logically making two statements (the antecedent and consequent can be reversed), and both must be proved.

By the end of the course, you should be able to:

  • state theorems accurately and identify what are their assumptions and their conclusions;
  • determine whether the conditions of a theorem do or do not hold in a given situation, explain why, and determine what the theorem does or does not imply in that situation;
  • recognize logically equivalent forms of a theorem;
  • formulate and test conjectures.

Proofs. Proofs are how we as individuals and as a community determine the truth of mathematical statements, i.e., theorems. Here is one definition of a proof, due to David Henderson: A proof is “a convincing communication that answers -- Why?” The extent to which a proof succeeds, therefore, depends on how well it embodies these three properties: it should be logical (does it convince?), it should be comprehensible (does it communicate?), and it should be intentional (does it answer why?). Evidently, each of these properties depends somewhat on the others. It is thus reasonable to classify proofs into an S/Q/U system:

  • (S) A successful proof makes an argument for the truth of a mathematical statement that is fully convincing to an informed reader or listener. It employs appropriate vocabulary and carefully chosen notation. It avoids sloppy reasoning. It makes clear use of the theorem’s assumptions and, when necessary, previously known results. The best examples provide motivation for the methods chosen. Minor revisions may be advisable, but they do not hinder the overall effectiveness.
  • (Q) A quasi-successful proof contains most of the ideas necessary to make a complete argument. It may have slips in logic or notation, or it may neglect a special case, or it may be hard to read. It contains sufficient evidence, however, that the argument can be “salvaged” by filling in gaps or clarifying language. Serious revision is necessary. [Not in syllabus: thanks to Dan for suggesting “quasi-”.]
  • (U) An unsuccessful proof does not convince an informed person of the truth of the purported theorem, for one or more of the following reasons: – It makes logical leaps or omits key ideas. – It demonstrates incomplete understanding of definitions or notation. – It fails to reference previous results when appropriate. Complete revision is generally necessary.
In other words, a successful proof is of sufficient quality that it could reasonably be accepted as part of a paper in a professional journal. A quasi-successful proof has some merit, but it requires revision, after which it might or might not be acceptable at a professional level. An unsuccessful proof is sufficiently flawed that it would not be acceptable as part of a professional publication.

By the end of the course, you should be able to:

  • evaluate, on the basis of professional standards, whether a given proof is successful or not;
  • write original, successful proofs.

Community. Our class time will be structured primarily around discussion rather than lecture. The idea is to have a space that promotes sharing ideas, making guesses, taking risks, and sharpening our reasoning abilities. I will guide and facilitate these conversations, but everyone is responsible for contributing to discussions, both in small groups and with the entire class. That is, in this course mathematical authority resides not just with me as the instructor, but with every class member. I will give short lectures (20 minutes) when the entire class agrees it would be beneficial, but not more often than once a week.

By the end of the course, you should be able to:

  • engage in discussions about mathematics by sharing questions, proposals, and insights;
  • evaluate others' contributions critically and respond constructively;
  • present your own work in front of an audience and address their comments and questions.