Quartics and Quadratics

I've been playing with polynomials a bit recently, and so I expect this post will be the first of several, explaining my explorations. The question I'd like to look at today is: When is a quartic (degree 4) polynomial the composite of two quadratics (degree 2)? Can every quartic be written as such a composite? Uniquely?

I wouldn't be surprised to find somebody has written this up before. In fact, they've probably dealt with more general questions, in an easier manner. All the same, this is how I spent my day, so I thought I'd share.

You might notice that 4 is the smallest degree polynomial that can be written as a composite of lower degree polynomials. If $p_i$ is a polynomial of degree $d_i$ (for $i=1,2$), then $p_1\circ p_2$ has degree $d_1\cdot d_2$. So if we wanted a cubic as a composite of lower degree polynomials, we'd have trouble doing it, and similarly for quadratics. However, these same considerations help us out a little bit. Suppose $f$ is a quartic that can be written as the composite $p_1\circ p_2$ of quadratics, and that T is a (non-constant) linear function. Then $T\circ f=T\circ p_1\circ p_2=(T\circ p_1)\circ p_2$, showing that $T\circ f$ is still the composite of two quadratics. The same argument works in reverse: if $T\circ f=p_1\circ p_2$, then $f=T^{-1}\circ p_1\circ p_2$ (and $T^{-1}$ exists, since $T$ was assumed linear), which is still the composite of quadratics.

What's the point of this linear function $T$? Well, suppose

$f=ax^4+bx^3+cx^2+dx+e.$

Let $T=\frac{1}{a}(x-e)$, and then notice that $T\circ f$ is monic (leading coefficient 1) and has 0 constant term. If the polynomial $T\circ f$ can be written as a composition of quadratics, then by the previous paragraph, $f$ can be written similarly. So, we can make our lives easier, and assume that $a=1$ and $e=0$.

Let $p_1=a_1x^2+b_1x+c_1$ and $p_2=a_2x^2+b_2x+c_2$. We'd like to know if we can write our $f$ above as $p_1\circ p_2$. If you're following along at home, I'll wait while you write out the composite $p_1\circ p_2$. To check your work (and mine), when you want $f=p_1\circ p_2$, you set the corresponding coefficients equal, and obtain the following system of equations:

$a=a_1a_2^2$
$b=2a_1a_2b_2$
$c=2a_1a_2c_2+a_1b_2^2+a_2b_1$
$d=2a_1b_2c_2+b_1b_2$
$e=a_1c_2^2+b_1c_2+c_1$

Our simplifications let us write $a=1$ and $e=0$. Let's also go ahead and assume $a_1=a_2=1$ (that is, our quadratics are monic), to make our calculations easier. It's also believable (I hope) that we haven't lost anything with this assumption, but perhaps I should think about this some more. I had convinced myself of it in the office this afternoon. Anyway, this makes our equations

$b=2b_2$
$c=2c_2+b_2^2+b_1$
$d=2b_2c_2+b_1b_2$
$0=c_2^2+b_1c_2+c_1$

Remember that we're assuming $b$, $c$, and $d$ were fixed, and are hoping to find $b_1,b_2,c_1$, and $c_2$. The first line clearly makes it easy to find $b_2=b/2$, and we can substitute that in the remaining lines:

$c=2c_2+b_1+(b^2/4)$, or $c-b^2/4=2c_2+b_1$
$d=(b/2)(2c_2+b_1)$, or $2d/b=2c_2+b_1$
$0=c_2^2+b_1c_2+c_1$

Now we're making progress. But first, we've made an assumption in the line $2d/b=2c_2+b_1$. What is it? Well, to divide by $b$, we assume $b\neq 0$. If, alternatively, $b=0$, then also $d=0$ (since $d$ is a multiple of $b$) and $b_2=0$. With all of these values being 0, the above system has 2 equations (the first and third) and 3 unknowns ($b_1$, $c_1$, and $c_2$). We can solve for $b_1$ and then $c_1$ in terms of a free variable $c_2$. Thus we obtain

Proposition: A quartic $x^4+cx^2+dx$ with $d\neq 0$ can not be written as the composition of two quadratics. The quartic $x^4+cx^2$ can be written as the composite $p_1\circ p_2$ where

$p_1=x^2+(c-2c_2)x+(c_2^2-cc_2)$
$p_2=x^2+c_2$

and $c_2$ can be any value.

Ok, so, assuming $b\neq 0$, what happens? The equations

$c-b^2/4=2c_2+b_1$
$2d/b=2c_2+b_1$

mean that $c-b^2/4=2d/b$, which we chose to re-write as $8d=4bc-b^3$. This is a requirement on the coefficients of the original quartic. However, if this is satisfied, then we can pick

$b_1=2d/b-2c_2$
$c_1=c_2^2-2dc_2/b$

in terms of a free variable $c_2$. We conclude by stating the final proposition, which can be checked by brute force (like everything else above):
Proposition: If $b\neq 0$ in the quartic $f=x^4+bx^3+cx^2+dx$, then $f$ can be written as the composite of quadratics only if $8d=4bc-b^3$ - in which case $f=p_1\circ p_2$ for

$p_1=x^2+(2d/b-2c_2)x+(c_2^2-2dc_2/b)$
$p_2=x^2+b/2 x+c_2$

where $c_2$ can be any value.

So there you have it. Not all quartics can be written as composites of quadratics. For those that can, there are a 1-parameter family of choices for monic quadratic factorizations.

Update 20081115: I've been thinking about my reduction that made the quadratics monic. I've been trying to decide if it was necessary. Playing around with the equations some more, it's not too hard to tell that you can't get rid of the relation $8d=4bc-b^3$ on the coefficients of the quartic, even if you don't assume your quadratics are monic. If you allow non-monic quadratics (but still want the composition to be monic), you have a free choice of value for $a_1$ (as long as it's positive) and for $c_2$ still, and the other coefficients can be solved for in terms of these two values (and the coefficients for the quartic).

Also, the two propositions could be combined. The relation $8d=4bc-b^3$ is present in both propositions, and there's no reason to assume $b\neq 0$ in that relation. Of course, we do end up dividing by $b$ to solve for coefficients in $p_1$ and $p_2$, so it's something to keep in mind.

Ok, I better go do some real work. I've still got other polynomial questions to look at, but they'll have to wait.

A Fun Category

During my time in grad school, I have often wondered what I would talk about if I were invited to give a talk to an undergraduate audience. Like the math club here, or where I went for undergrad. I've generally had a good time with categories, and am pretty convinced something like the following would work as a fun talk. Perhaps my definition of fun needs some work.

For starters, let's just think about sets for a while - and I'll have finite sets in mind, but mostly that shouldn't matter. If $S$ and $T$ are sets, the Cartesian product is the set $S\times T=\{(s,t)|s\in S,t\in T\}$. What makes this new set useful? Why should we care about it? I suppose it depends on who you ask, but since I've got categories in mind, I want to think about functions (=maps) between sets. The product comes with 2 maps, I'll call them $\pi_S$ and $\pi_T$. The map $\pi_S:S\times T\to S$ is defined by $(s,t)\mapsto s$, and the map $\pi_T$ is similar. Now, if I have a set $A$, and a map $f:A\to S\times T$, then I can compose $f$ with either $\pi_S$ or $\pi_T$ and obtain maps $\pi_S\circ f:A\to S$ and $\pi_T\circ f:A\to T$. That is, I can tease out the component pieces of the map $f$. On the other hand, if I started with a set $B$, and maps $g:B\to S$ and $h:B\to T$, I can define a map $(g,h):B\to S\times T$ via $b\mapsto (g(b),h(b))$.

So when I think about the product of two sets, I notice that maps to the product are essentially the same as individual maps to the sets I started with. This is how I want to think about the product in other contexts. If I start with two things (objects in some category) $x$ and $y$, I want their product $x\times y$ to be another thing (object) with the property that whenever I have component maps (a map to $x$ and a map to $y$), then I get a map to the product. Additionally, my product will come with two maps, $\pi_x$ and $\pi_y$, which I think of as the projections, following the example above.

What I'd like to do now is pick a fun context (category) and figure out what the product is in that category. In a category I'm supposed to have some collection of objects, and some collection of arrows between objects (satisfying various properties). So the category of finite sets, that I used above, just had finite sets as objects and functions as arrows. My new category will have as objects the positive integers. There will be a single arrow from $n$ to $m$ precisely when $n$ divides $m$.

So what is the product of $n$ and $m$ in this category? For now, let me call it $p$. Remember that $p$ comes with maps to $n$ and $m$ - which is to say, $p$ divides $n$ and $m$. There's a word for that - $p$ is a common divisor of $n$ and $m$. Which common divisor? Well, suppose $a$ is some other divisor. That means $a$ divides $n$ and $m$, or, in arrow notation, $a\to n$ and $a\to m$. But part of being the product was that whenever I have maps to $n$ and $m$, I get a map to the product, $p$. So $a\to p$, or, in other words, $a$ divides $p$. So, we've found that if $a$ is any other divisor of $n$ and $m$, then since $p$ is the product, $a$ must divide $p$. That makes $p$ the greatest common divisor.

Wasn't that fun?

These things can be 'dualized', and what you get is supposed to be called the sum. 'Dualizing' means flipping all the arrows around. Let's go back to finite sets for a minute. The product $S\times T$ came with maps $S\times T\to S$ and $S\times T\to T$. The dual of this idea (call it the coproduct, or sum), is an object, which I'll denote $S\coprod T$ and it has arrows $S\to S\coprod T$ and $T\to S\coprod T$. Notice how the arrows are going the 'other way' than they did for the product? For the product we mapped from the product to the components, whereas for the sum we map from the components to the sum. The sum also has the property that if $S\to A$ and $T\to A$, then $S\coprod T\to A$ (again, notice how this is flipped from the product case, where $A\to S$ and $A\to T$ gave $A\to S\times T$). The object, in sets, that is the coproduct is more commonly known as the disjoint union.

Exercise for the reader: what is the coproduct in the other category above, the 'divides' category?

You might ask why I decided that what was important, back in the beginning, was functions (maps). It's a good question. I've read somewhere (though I forget where) that thinking about objects by themselves is ok, but thinking about how they related to other objects (via maps) is even better. For a while I wasn't really sure why this should be, but I'm starting to put it together. If you go back and think about set cardinalities, you'll quickly notice that you are really asking about maps between sets, as a way to compare their sizes. If there is an injective or surjective map, you know one of the objects is at least as big as the other. If you've got a bijection, the two sets are the same size. It's hard to think about the size of a set, once you get past finite sets (but even there, really), without comparing it to other sets. And the way you compare sets is via maps between them. For an somewhat more advanced example, algebraic topology is wholly dedicated to maps between spaces. If you've got some space $X$, you decide that you'd really like to know about maps from various dimensional spheres into your space $X$. But perhaps that's a subject for another day.

Fun with Series

The 'Sequences and Series' chapter of Calc 2 is the one I have been looking forward to the most, because there are some many awesome external diversions one can bring in to the class. I've already talked here about the first batch of fun things I mentioned in class, and thought I might update on some more things I've said, and plan on saying.

Now that we've talked about geometric series, it's possible to compute the area of the Koch snowflake, whose length we already computed in class when we talked about sequences. Our text (Stewart) has an exercise about the Cantor set, and the Sierpinski Carpet. The students are asked to compute the total length removed from [0,1] in order to make the Cantor set, and similarly the area removed to make Sierpinski's Carpet. I hope they found it surprising that the bits removed had the same length as the interval, and area as the square, even though there are still (clearly) infinitely many points remaining. While I was at it, I mentioned the Menger Sponge origami projects (and looking them up again convinced me that I should probably do one someday).

Though I've not yet figured out how, exactly, to bring it up in class, I think we're going to have a day and talk about cardinalities a little. I should at least show them that there is more than one infinity. Clearly it ties in to the examples from the previous paragraph, but it's also just good for their general education. Plus it's hugely fascinating. And they've spent all this time thinking about functions on the real line, they might as well know a little more about the line itself.

Even though I don't know a whole lot about it, since we were talking about p-series the other day I figured I should mention Riemann's ζ function, the associated Hypothesis, and the million dollar reward for a proof. They seemed to enjoy that there was a financial incentive, but at least one commented that there were surely easier ways to make a million dollars. I also showed how the divergence of the harmonic series implies that there are infinitely many primes, by considering the expression

$\sum_{n=1}^{\infty}\frac{1}{n}=\prod_{p}\frac{1}{1-p^{-1}}=\prod_{p}\left(\sum_{k=0}^{\infty} 1/p^k\right)$

These products are taken over all primes.

We also talked about the integral test in class, so I couldn't help bringing up the Euler-Mascheroni constant γ. I didn't say horribly much about it in class, but did mention how it can be used to approximate the number of terms in the harmonic series you would have to add up in order to get a chosen value. I worked through determining that it requires more than 12000 terms to just add up to 100.

The next thing I plan on talking about in class is sometimes referred to as the Kempner Series, and is obtained from the harmonic series by removing those terms whose denominators have some chosen digit. For example, remove all the terms that have a 0 as a digit in the denominator. What is initially surprising about this series is that it converges, though after some more thought you realize you've thrown out rather a lot of the series. Anyway, to show the Kempner series converges, you compare against a geometric series - all things we're talking about in my class.

Perhaps some of the most fun (besides, perhaps, the multiple infinities) will be once we get to Taylor series. I plan on presenting one of Euler's proofs that $\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}$, by thinking about the Taylor series for $\sin(x)/x$. The way this works is to realize that $\sin(x)/x$ is zero at the non-zero integer multiples of $\pi$, so you think of the infinite polynomial that is the Taylor series as also being the product $\prod_{0\neq n}(1-x/(n\pi))$. After expanding this infinite product, you compare the coefficient of $x^2$ to the corresponding coefficient from the Taylor series, and Robert's your father's brother.

Another fun example I plan on doing (at least to some extent) is showing that

$\int_0^1 \frac{1}{x^x}dx=\sum_{n=1}^{\infty}\frac{1}{x^x}.$

This requires a bit of messing about, but it's so pretty that it's got to be worth it, right?

The final fun thing about Taylor series is it gives a nice segway into my research. Of course, I won't get too involved with telling them about my research, exactly. But I will mention that it's a direct analogy to Taylor series. And it'll give me a chance to talk about topology, which is always good.

Update 20081103: I realized I should include some text references here, sorry about that. The two books I had in mind were:

1. Gamma, by Julian Havil
2. Euler: The Master of Us All, by William Dunham
   

Fun with Sequences

We started the chapter on Sequences and Series in my calc II class last week. This is the chapter I have been looking forward to the most, even though, of course, all of the chapters are interesting. I decided to use one class period mostly talking about things that didn't matter for the class at all, because they are irresistibly fun.

I started with some limits of recursive sequences, which actually are (a small) part of the class. Things like

$\sqrt{2}$, $\sqrt{2\sqrt{2}}$, $\sqrt{2\sqrt{2\sqrt{2}}}$, $\ldots\rightarrow 2$

and

$a_1=1, a_{n+1}=1+1/a_n$

which converges to the golden ratio. I resisted talking too much about the golden ratio and the Fibonacci sequence, because I figured many students had probably already seen it, or could easily learn about it online (which I suggested they do). Of course, at that point, you might as well write out, without any simplifying, the first couple of terms in that sequence and start talking about continued fractions, which I did.

Then I jumped to the (unsolved) 3n+1 problem: Consider the piecewise rule that defines $a_{n+1}$ to be $a_n/2$ if $a_n$ is even, and $3a_n+1$ if $a_n$ is odd. Now given any starting number $a_1$, the question is: does the sequence starting at $a_1$ and following the piecewise rule always eventually end up at the cycle 1, 4, 2, 1, 4, 2, 1...? I really love stating these simple problems (simple to state, that is) for my class, and pointing out that they are unsolved. I've also already mentioned the problem of finding odd perfect numbers.

From there, it's probably time to draw some pictures. The Koch snowflake is a fun example to do. I only talked about how it has an infinite perimeter, and will return later to finding the area, once we've done a little more with series.

Once you're on fractals, it's hard to resist the Mandelbrot set. This one's a little harder to talk about in a calc II class, because it involves complex numbers. But you can still talk about taking a function $f$ and a starting value $a_1$, and considering the sequence $a_1, f(a_1), f(f(a_1)), f(f(f(a_1))),\ldots $. This sequence is what you consider to determine if a point is in the Mandelbrot set, using the function $f(z)=z^2+a_1$ (a different function for each point you consider). So I showed a couple printed out pictures of the set, and encouraged my students to go online and look for more pictures.

I regret, just a little, missing the Cantor set in my discussion. Perhaps another day.

That's all I got to in class. Of course, there's still several weeks left in the semester, and lots of fun things that can be said with sequences and series. When we get to Taylor series, I'll probably tell them a little about my research, which is analogous to the series they'll be looking at. Since I'll be talking about my research, I'll also talk a bit about topology.

While I was wandering around wikipedia, looking for more fun things to talk about, I ran across the page on the ? function. I'd not heard of it before, but it looks pretty interesting. I should probably look at it some more sometime.

A Common Tangent

For what value of $a$ ($a>1$) does $a^x$ have a common tangent with its inverse, $\log_a x$?

Let $c$ be the $x$-coordinate of the point of tangency, so that the $y$-coordinate is $a^c$ and $\log_a c$. Setting these $y$-coordinates equal doesn't seem to get us anywhere.

So let's move to the tangent line. The derivative of $a^x$ is $a^x\cdot \ln a$, while the derivative of $\log_a x$ is $1/(x\cdot \ln a)$. Plugging in our common point, $x=c$, and setting the two slopes equal, we get $a^c\cdot \ln a=1/(c\cdot \ln a)$. Again, not obviously useful.

What gets me through this problem is thinking about it graphically. Since $a^x$ and $\log_a x$ are inverse functions, each is the mirror image of the other across the line $y=x$. This means that their common tangent line will, in fact, be that same line, $y=x$.

Therefore, the slope of the common tangent line will be 1. Our two ways to represent the slope are $a^c\cdot \ln a$ and $1/(c\cdot \ln a)$. Setting the second equal to 1 and solving for $c$, we get $c=1/(\ln a)$, which we could also write as $(\ln e)/(\ln a)=\log_a e$. The first way we represented the point of tangency was $(c,a^c)$, but since it is on the line $y=x$, this is also $(c,c)$, so $c=a^c$.

We're almost there. In $c=a^c$, replace the left-hand side with $1/(\ln a)$, from our slope calculations. On the right-hand side, replace $c$ with $\log_a e$. Then we get $1/(\ln a)=a^{\log_a e}=e$, so $1/e=\ln a$, and we see that $a=e^{(1/e)}$.

I'm not sure why I first asked this question. I was teaching calc 1 at the time, and probably looking for interesting homework problems. I seem to recall chickening out in assigning this as a problem. Perhaps some other semester. Either way, I thought it was cute.

Update 20081229: Apparently (according to the penguin dictionary of curious and interesting numbers) this value, $e^{(1/e)}$ is also the value of $x$ for which $x^{(1/x)}$ is a maximum. This isn't entirely correct, as the maximum occurs at $x=e$, and therefore $e^{(1/e)}$ is the maximum value. Wikipedia has a page.

Origami Numbers

Today I gave a (brief) talk for the Graduate Seminar in the math department here at UVA. This is an informal setting, which is only for grad students (no professors heckling the speaker). They're generally an hour, but I only went slightly over half of that time. All the same, it was a pretty comprehensible talk. At the very least, it was comprehensible material - who knows how the talk went.

The title for my talk was Origami Numbers. I walked through the first 5 of the Huzita-Hatori(-Justin-...) axioms [wikipedia], which are enough to do standard straight edge and compass constructions. The first 4 are pretty straight forward, and it's with the 5th that you start making interesting things - parabolas. Then with the 6th axiom, we are able to obtain cubic roots, showing that origami is more powerful than a straight edge and compass. A great reference, and my starting point, for all of this, is the book Project Origami by Thomas Hull (which has lots of other goodies).

One thing I found while preparing my talk was identified as Lill's method in this paper by Alperin and Lang. It's a graphical method for finding roots of polynomials, and I'd never seen it before. The paper 'Geometric Solutions of Algebraic Equations' by Riaz talks about it, as does this site, which I just found (so I should take another look at). Lill's method draws a piecewise linear path (starting, say, at O, and ending at T), where the lengths of pieces correspond to coefficients of your chosen polynomial. Then you are supposed to draw another path from O that bounces around off the lines you made and ends at T. This line shows you one of the roots for the original polynomial (see the above references for more details). It doesn't seem particularly practical if you want to find roots (I'd go for Newton's method, if all else failed), but it's fun to have a new graphical way to think about things.

Homework Helper

I've been a little bit frustrated with the way the discussion session for my calculus class has been going recently. That time is set aside as a time for students to ask whatever questions they have, without me lecturing on any new content. Of course, generally the questions they have are 'can you do this homework problem?' or 'I got stuck on this problem, can we go through it?'. Generally, those are fine questions that I'm happy to answer. However, I'm getting the impression that many of the students have not yet looked at the assignment yet, and are just waiting for me to do half of it for them. Of course, this'll come back to bite them on the exam, but it's fairly frustrating all around. So I've been trying to decide what to do about it.

It occurred to me today that even just answering those questions asked by the students who have looked at the assignment isn't very efficient. If they've already started, but gotten stuck, it'd be fairly quick for me to sit down with them individually, find their error, and send them on their merry way. Even there, though, that's not what I should be doing. It's easy for me to spot errors, generally. Especially when I've already looked at the problem with several other students. But it would be hugely valuable for students to be able to find their own mistakes. It can be maddening trying to find your own mistakes, of course, but it's an important skill to have.

A good way to practice finding mistakes, even if they get all of their own problems correct, would be to help identify mistakes in other people's work. Of course, this process can be ironed out a little online. I am envisioning a system where students can go and enter the work they have on a problem, up to the point where they got stuck. Then other students could go and try to find errors in people's work. This way people that get stuck can get help whenever it's convenient for them (as opposed to waiting for office hours or something), and students can practice finding errors in work.

It seems there should be some sort of credits system involved. At the beginning of the semester, students have, say... 3 credits, or 5 or something. A credit gives you permission to ask a question. To earn credits, you submit a bug report on another person's question. Perhaps a bug report just identifies what line the error occurs on, without identifying the error. And I guess answers would need to be verified before credit is added to the person who submitted the answer. Perhaps the person asking the question verifies it?

That's about as far as I've taken the idea today. Clearly there'd have to be an easy way to enter work, perhaps with some sort of graphical formula editor. Also probably some anonymity, so you can see questions, but not who submitted them (nor who answered them?). It also seems like what might happen is that the people who have the most questions might have a hard time spotting other people's mistakes in order to earn credits to ask more questions. So perhaps there's a way to account for that. Something like... if you earn lower than an N on the exam, each point less than that gets you a free credit?

Anyway, that's a day's thought on the idea. What do you all think? Do you know of a system that does something like this already? Could something like the above idea be worthwhile and helpful? How could it fail? Where does it need improvement? What additional policies might you use?