jsEval "curl_module('../haskell/GenFun.ob')"
Getting the third degree
I first met Dr. David Paget in December 1993, at a two-week mathematics olympiad training camp in Melbourne. Up until then, it was the longest I’d been away from home on my own, even accounting for Mum’s brief visit about halfway through.
Dr. Paget was in charge, not only of our education, but also played the role of a boarding school headmaster: enforcing curfews; making sure we went to bed on time; lecturing us on how he had no tolerance for swearing. As I write this, I realize he was only a little older than I am now, yet I can’t imagine myself herding teenagers with the same natural authority.
Two years and three camps later, he informed me that I was not to be one of the six students representing Australia at the International Mathematics Olympiad later that year. I did receive a consolation prize: I was the reserve, which meant I got the team blazer and tie (which I treasure to this day), but it also meant I had to do the same work as the team, only I didn’t actually get to compete. I couldn’t help hoping that a team member would have to withdraw so I could take their place.
That was my worst memory involving Dr. Paget, though obviously it wasn’t because of him: I was simply gutted to miss out. I’m glad he was the one that broke the news to me, as he had a lot of experience with difficult conversations of that nature.
Fortunately, my other memories of him are pleasant ones. I remember him standing in the kitchenette of the common room, sipping from a mug in one hand while us students were struggling over a cryptic crossword puzzle. One of us read one of the clues to him. He looked at the ceiling for a moment, then announced the answer, and jokingly asked if we were looking at the section for children!
But my main motivation for this page is memory that is, fittingly, mathematical in nature. Dr. Paget taught us how to solve cubic equations. I was captivated, for I had heard such a feat was possible, but our schools never taught beyond the quadratic, and my own research was stymied by the limited selections of my local public libraries.
I took notes at the time, but now, decades later, I still don’t need to refer to them. The memory stuck because I was so keen to learn such rare and rarefied wisdom.
How to solve cubics
We start with a monic cubic:
\[ x^3 + a x^2 + b x + c = 0 \]
Introduce another variable:
\[ x = y - \frac{a}{3} \]
This eliminates the \(x^2\) term, hence for some \(r, s:\)
\[ y^3 = r y + s \]
I only learned recently that this is known as a depressed cubic.
Introduce two more variables: \(y = u + v.\) Then:
\[ y^3 = (u + v)^3 = u^3 + 3uv (u + v) + v^3 = 3 uvy + (u^3 + v^3) \]
Equating coefficients yields:
\[ r = 3uv , s = u^3 + v^3 \]
Thus we can compute the sum of \(u^3\) and \(v^3\) along with their product, allowing us to find them by solving a quadratic equation:
\[ u^3 = \frac{s + \sqrt{s^2 - 4r^3 / 27}}{2} \]
We take cube roots to find \(u\), then compute \(v = r/(3u) \), and finally \( x = u + v + a/3. \) The three cube roots of \(u\) lead to the three solutions of the original cubic.
We run into division by zero when \(u = 0\), but this special case is easy, for it implies \(r = 0\), thus \(y\) can be any cube root of \(s.\)
Alternatively, define:
\[ \begin{align} a &= \frac{s}{2} \\ b &= a^2 - \left( \frac{r}{3} \right)^3 \end{align} \]
whence:
\[ y = \sqrt[3]{a + \sqrt{b}} + \sqrt[3]{a - \sqrt{b}} \]
but care must be taken to choose matching cube roots.
How to solve quartics
A few years later at university, I gained access to more rarefied mathematics texts. I soon found Harold M. Edwards, Galois theory, which walks through solutions of several kinds of equations with radicals, including a method for solving general quartic equations.
Start with a depressed quartic:
\[ x^4 = -p x^2 - qx - r \]
Introduce a variable \(a\) and we have:
\[ (x^2 + a)^2 = x^4 + 2 a x^2 + a^2 = (2a - p)x^2 - q x + a^2 - r \]
We want the right-hand polynomial to be a perfect square, thus we want its discriminant to be zero:
\[ q^2 - 4(2a - p)(a^2 - r) = 0 \]
This is a cubic equation for \(a\), which we duly solve, and since we know the right-hand side is a perfect square, we have:
\[ (x^2 + a)^2 = (2a - p)\left(x - \frac{q}{2(2a - p)}\right)^2 \]
Taking either square root leads to a quadratic we can solve for \(x\).
Duel-Purpose Technology
Today, descriptions of the above algorithms are one click away. Better still, unlike textbooks focused on mathematics, we can just as easily learn their history, which turns out to be a gripping tale involving fierce rivalries, betrayals of secrets, and a Ferrari.
We leave others to reveal who murdered whom. Instead we explore the details that only a programmer would care about: famous early test cases. See Martin A. Nordgaard, Sidelights on the Cardan-Tartaglia Controversy.
Scipione del Ferro first solved the depressed cubic, at a time when mathematicians publicly challenged each other to battles of wits, posing problems they hoped would stump their rivals. At stake was honour, money, and employment, so they jealously guarded their secret techniques, in contrast to their modern counterparts who are under pressure to publish first.
So when I think I had it bad, I remind myself it was once far tougher to learn to solve the cubic. Indeed, we only know of del Ferro’s work thanks to the lucky few he confided in, which included his student Antonio Maria Fior (sometimes Fiore).
Fior "flitted about from place to place, causing battle and disturbance". Thanks to his bragging, Nicolo Tartaglia soon discovered how to solve a cubic, as knowing that someone else has already solved it can give you confidence. Especially a character like Fior; perhaps Tartaglia thought that if a guy like Fior knows how to do it, it can’t be that difficult!
Fior learned of Tartaglia’s work, and challenged him to a duel. They exchanged 30 problems with each other.
Positive Thinking
All of Fior’s problems took the form \(x^3 + px = q\) for positive rationals \(p, q.\) In those days, there was a widespread prejudice against negative numbers. (Though this phobia was not global, for example, the ancient Chinese were fine with negative numbers.) Hence mathematicians distinguished between equations of the form:
\[ x^3 + px = q \]
and:
\[ x^3 = px + q \]
where \(p, q\) are non-negative, as fine and upstanding numbers are supposed to be.
Evidently, Fior was only comfortable with the first form. Furthermore, all but a handful of his problems set \(p = 1\). Thus we can dispatch his problems with a few lines of code:
import GenFun
texRat (p :% q)
| q == 1 = show p
| otherwise = concat ["\\frac{", show p, "}{", show q, "}"]
-- Solve x^3 + px = q
delFerroTex p q = concat ["\\sqrt[3]{", texRat a, "+", sqrtB, "}"
, "+", "\\sqrt[3]{", texRat a, "-", sqrtB, "}"]
where
a = q/2
b = a^2 + p^3/27
sqrtB = concat["\\sqrt{", texRat b, "}"]
outTex s = jsEval_ $ [r|
const e = document.createElement("div"); e.style["font-size"]="85%";
e.textContent = String.raw`|] ++ "\\[" ++ s ++ "\\]" ++ [r|`;
runme_out.appendChild(e); MathJax.typeset([e]);
|]
delFerro p q = outTex $ delFerroTex p q
fior = delFerro 1
The problems were given in prose, for example:
-
"Find the number which added to its cube root gives 6."
-
"Divide thirteen into two parts such that the product of these parts shall equal the square of the smallest part multiplied by the same."
We translate them to equations; see Nordgaard for the English version.
-- 1. x^3 + x = 6 fior 6 -- 2. 4x^3 + 3x = 40 delFerro (3/4) 10 -- 3. x^3 + x = 5 fior 5 -- 4. 9x^3 + 13x/3 = 7 delFerro (13/3/9) (7/9) -- 5. x^3 + x = 900 fior 900 -- 6. x^3 + x = 100 fior 100 -- 7. x^3 + 2x = 13 delFerro 2 13 -- 8. x^3 + 3x = 15 delFerro 3 15 -- 9. x^3 + 4x = 17 delFerro 4 17 -- 10 to 13: mapM_ fior [14,20,2000,800] -- 14. x(13-x) = x^4, x is positive fior 13 -- 15. x^3 + x = 500 fior 500 -- 16 to 30: mapM_ fior [7,12,9,25,26,28,27,29,34,12,100,140,300,810,700]
Fior’s test cases are intriguing. Why did he repeat some of them? Was he hoping to fool Tartaglia with the wordy window dressing cloaking the equations? And why did he choose \(p = 1\) and natural \(q\) so often? Was he bad at calculation, so picked simpler numbers for safety? Or maybe there’s a different explanation: to avoid easy solutions via factoring, Fior had to choose cubics with no rational roots. Perhaps he felt unsure about this task for \(p \ne 1.\)
His problems are so monotonous that even a layman would guess that if you can solve one, then you can solve them all, as Tartaglia wound up doing in a few hours. They strongly suggest Fior could only answer one kind of question.
Fior’s problems also contain a danger: from the solutions alone, a clever mathematician can spot patterns and deduce the method. Indeed, after the winning the contest, Tartaglia guarded his answers as closely as his algorithm. I wonder how the judging worked. Did they show solutions only to each other? Or was there a third party who was sworn to secrecy?
Return fire
Nordgaard states "we have record of only the first four" of Tartaglia’s challenge questions, which alone show far greater range than Fior’s:
-
\( x^2 (x + 4) = r \)
-
\( x^2 (x - 30) = r \)
-
\( x^3 + 4x = 13 \)
-
\( x^3 - x = 10 \)
The latter two are depressed so we can solve them right away:
delFerro 4 13 delFerro -1 10
Some sources say Fior scored zero on Tartaglia’s problems, but he should have been able to solve the third problem. Perhaps he panicked on seeing the full problem set, and on realizing the strength of his opponent.
The first two problems involve "a given rational number" \(r\), which reinforce my suspicion that contestant’s solutions are kept private; the answer is a formula involving \(r\) which might give the game away.
To solve them, we need to depress cubics:
depress p = case reverse $ toList p of
a:b:rest -> (c, ((recip a :+: Pz) * p) # fromList [-c, 1])
where c = b/(3*a)
_ -> (0, p)
tartaglia p = outTex $ delFerroTex m -minusn ++ subTex where
(subme, minusn :+: m :+: _) = depress p
subTex
| subme < 0 = "+" ++ texRat -subme
| otherwise = "-" ++ texRat subme
We test our code on the first two problems with some sample values:
tartaglia $ fromList [-89, 0, 4, 1] tartaglia $ fromList [-64, 0, -30, 1]
Easy cases are hard
In theory, the formula works on any cubic. But what happens when we try it on easy problems, like \( x^3 = 1 ?\)
delFerro 0 1
This is correct, because depending on the choice of cube root, this evaluates to simply \(1, \omega,\) or \(\omega^2\), where
\[ \omega = \frac{-1 + \sqrt{3}}{2} \]
is a primitive cube root of unity.
It’d be nice if our code could do this for us, which we can do with a routine to detect perfect squares or cubes of rationals. But then it gets trickier. Take \( x^3 - 15x - 4 = 0, \) where \(x = 4\) is clearly a root:
delFerro -15 4
This is:
\[ \sqrt[3]{2 + 11i} + \sqrt[3]{2 - 11i} \]
We can simplify further because \( (2 + i)^3 = 8 + 12 i - 6 - i = 2 + 11i, \) leading to the three solutions:
\[ \begin{align} (2 + i) + (2 - i) &= 4 \\ \omega(2 + i) + \omega^2(2 - i) &= -2 - \sqrt{3} \\ \omega^2(2 + i) + \omega(2 - i) &= -2 + \sqrt{3} \end{align} \]
all of which are real.
Automating this is at least as difficult as detecting perfect cubes over the complex numbers, which is more work than I wanted to do.
It was worse for the first researchers to solve the cubic. Recall they felt negative numbers were nonsensical; taking a square root of such a number is several bridges too far. The challenge questions seem to have been chosen to avoid this embarrassment.
And yet, mathematicians were eventually forced to accept the "mental torture", as Cardano described it. Complex numbers were tolerated on a temporary basis, as they were necessary in intermediate calculations to find real solutions. It took a few centuries before mathematicians felt that negative numbers and imaginary numbers had the same standing as positive numbers.
Two Variables
It might be said that for me, cubic equations became more than an interesting curiosity. Towards the end of my undergraduate studies, I took a course that studied solutions of cubics, except with two variables. This means the combined degree of each term is at most three, so in general, such equations have the form:
\[ a_0 + a_1 x + a_2 y + a_3 x^2 + a_4 xy + a_5 y^2 + a_6 x^3 + a_7 x^2 y + a_8 xy^2 + a_9 y^3 = 0 \]
These are known as elliptic curves, due to a historical accident; they only have an indirect tenous connection to ellipses. My graduate degree focused on certain kinds of elliptic curves over finite fields, which turn out to be useful in cryptography.