Havens' Haven
Subtitle: Chakravala in a Taxicab
I have never done anything “useful”. No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world.
— G. H. Hardy
# Christopher Havens
If you were facing a 25 year stretch for murder and had landed in solitary for a while, you might think to yourself, “Maybe this would be a good time to catch up on some number theory”. Something like this occurred to Christopher Havens when he was convicted of murdering Randen Robinson and sent to the Washington State Monroe Correctional Complex northeast of Seattle. He had dropped out of high school, began using drugs, and killed Robinson during a drug-related dispute. After his conviction, bad behavior sent him to solitary confinement for a year.
While in solitary, Havens started working puzzles and then realized that the guards were handing out math problems to other prisoners. He did as much math as they could provide, quickly learning calculus and number theory, but eventually exceeded the guards’ ability to keep up with his level.
That’s when he sent this letter that eventually arrived on the desk of Matthew Cargo, editor for Mathematical Sciences Publishers, whose partner Marta Cerruti is Associate Professor of Materials Engineering at McGill University.
Her parents are mathematicians and her father, Umberto Cerruti, is a number theorist at the University of Torino in Italy. Umberto Cerruti sent Havens a problem to work on, and Christopher wrote back with a long, complicated solution that turned out to be correct.
Christopher has since published a paper jointly with Cerruti and two other mathematicians, in the journal Research in Number Theory, “Linear fractional transformations and nonlinear leaping convergents of some continued fractions”. He hopes to inspire other prisoners through mathematics and has started the Prison Mathematics Project (PMP) to connect inmates with mathematicians. They hold bi-weekly meetings to discuss math problems and work on larger projects. Beginning in 2016 the PMP has been holding Pi Day celebrations.
“You should never set aside your dreams and goals and dismiss them as impossible just because you are institutionally challenged,” Havens said. “Today is not just a day to celebrate pi, but mathematics as a whole and celebrate an opportunity we have to move our lives in a positive direction.”
Besides having a research paper published, Chris also submitted a problem to Math Horizons, a magazine published by the Mathematical Association of America (MAA) meant to be accessible to undergraduate mathematics majors. The problem is this, What is the smallest positive integer such that is a perfect square? This is a form of Pell’s Equation, and there’s a connection to the mathematicians Srinivasa Ramanujan and G. H. Hardy.
Ramanujan was a self-taught mathematician from India who produced thousands of new ideas in number theory. In early January 1913, he sent a letter with some of his results to Hardy who was at Cambridge at the time. Later, Hardy said that the letters were “certainly the most remarkable I have received” and that Ramanujan was “a mathematician of the highest quality, a man of altogether exceptional originality and power”. He invited Ramanujan to visit him in England, and Ramanujan arrived in April 1914.
Ramanujan (22 December 1887 – 26 April 1920) was ill most of his short life and Hardy visited him while he was in the hospital.
I remember once going to see him when he was ill at Putney. I had ridden in taxi cab number 1729 and remarked that the number seemed to me rather a dull one, and that I hoped it was not an unfavourable omen. “No,” he replied, “it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways.”
The number is now known as a taxicab number or the Ramanujan-Hardy number and is the number Havens chose for the problem. The drawing at the top of Hardy and Ramanujan was done by Chris Havens.
# Pell’s Equations
Pell’s equations are in the form
for integers , and . The problem that Chris Havens proposed is to find and such that , which can be rearranged into a Pell equation,
In the 7th century, Indian mathematician and astronomer Brahmagupta first studied equations in this form (he called it the Varga-Prakriti equation), and Pell had nothing to do with them. This is an example of Stigler’s Law of Eponymy, named for University of Chicago statistics professor Stephen Stigler, which says that no scientific discovery is named after its original discoverer. Stigler’s Law is itself an example, having been earlier described by sociologist Robert K. Merton. Leonard Euler misattributed the equations to Pell rather than to the several earlier mathematicians who worked on similar equations including Diophantus, Bhāskara II, Narayaṇa Paṇḍita, William Brouncker, and Pierre de Fermat.
The equations are hyperbolic functions and have solutions at points where both and are integers. This is an example of the equation plotted in Desmos. Use x^2-2y^2=1
to plot the function, and plot solutions in the form as shown on the second line.
In the 12th century, Bhāskara II (1114–1185) continued the work of Brahmagupta (598–670) and developed an algorithm for finding solutions that he called the Chakravala Method.
# The Chakravala
Bhāskara named his method Chakra (meaning “wheel”) because of its iterative nature. Shailesh Shirali is a mathematician at the Sahyadri School in India who wrote “The Chakravala Method - Zeroing in on a Solution” in the mathematics journal At Right Angles. This description of the Chakravala is from his paper.
The first step to understanding the Chakravala comes from the Diophantus-Brahmagupta-Fibonacci identity,
Brahmagupta extended this to
It’s not clear how these identities were discovered, but they are easy to verify by expanding and collecting terms. You can start to see how the Chakravala works for finding integer solutions to the equation if we already have two solutions,
then
To complete the method, we need Bhāskarā’s lemma which says that if , then
which can be easily verified with expansion and collection of terms.
Given a non-square positive integer , we’re looking for a solution to . If we have two solutions and a third solution can be generated from the Brahmagupta identity using
Suppose and we have two solutions and meaning that
Using the equations for and ,
gives a new solution ,
If we already have one triple that works, a second one can be derived by using giving the triple and calculating a new and ,
so
The trick to finding a solution for is to start with an “almost” solution and iterate using the Chakravala until . Finding is done by letting and then setting to the nearest integer greater than so that gives the smallest positive integer . From Bhāskarā’s, lemma we need to be evenly divisible by and to be as close to as possible. The steps in the algorithm are,
- Find an initial nearby solution to where and have no common divisors
- Look for divisible by and then select the that minimizes
- Get new values and from
Repeat the second and third steps until .
Does the Chakravala ever end, or does the wheel keep on turning? Fortunately, the algorithm converges, that is, it eventually gets to . The proof is given by A. Bauval in “An elementary proof of the halting property for the Chakravala Algorithm”.
But to make the Chakravala work requires understanding modular arithmetic.
# Modular Arithmetic
In number theory it’s often useful to describe a number by its remainder when divided by another number, so if
then goes into times with a remainder of . An example is the angle when going around a circle:
If the circle has a radius of , then the angle ranges from to , but once it gets back to the -axis the remainder resets to . That is, you can’t tell from looking at where the pointer is whether it’s gone around zero times, once, twice, or more. The sloped lines in this plot represent the remainder of the angle after dividing by . Usually, the numbers , and are integers and the equation is often written as
meaning that the remainder when is divided by is , or “ equals modulo ”. The is missing in the equation because it’s the integer number of times that divides , and we’re only interested in the remainder .
If and then , since
For example, and so . Of course, adding so you have to apply the modulus again to get . Subtraction works the same way with .
You can multiply numbers modulo . Using the same notation from above,
So, and .
The only arithmetic operation left is division. Since it would be convenient if we could divide both sides by to get , but clearly, that’s wrong, . The division operation that we’re used to means that if
then
If the solution to dividing by is , then multiplication reverses this, so times must equal . We need an equivalent for modulo division. Suppose there are two numbers and such that multiplication by gives the same answer modulo ,
This means that and for some and . Since then , so
for some integer . We can find a solution to the division problem using the greatest common divisor of and .
The greatest common divisor (gcd) of two integers is the largest integer that divides both of them. To find the gcd, find the prime factors of each, and then take the product of all the common factors,
Suppose the and that . The second condition means that does not divide evenly into . Divide by to get some integer . Now is also a divisor of since , but can’t be a divisor of because if it were, then both and would be divisors of , as would the product meaning that wasn’t really the greatest common divisor. So, if doesn’t go evenly into , then it must divide , since
This means that
only when
So, a unique solution exists only when the . In this case, and are said to be relatively prime or coprime. Let’s go back to the original problem of finding such that . One way to find would be to check every element of the set until we find a solution. But there’s a faster way using the greatest common divisor method discovered by Euclid.
# The Euclidian Algorithm
Euclid’s algorithm is a more practical method for finding the greatest common divisor of two numbers than listing their prime factors and then calculating the product of their common factors. Suppose you want to find where . Now, , and for some . Write in terms of : . Maybe you find that , meaning that is a divisor of . Then,
and
This means that divides both and and if we let then and , so is the largest divisor of both and .
Using the example from above, we’ll find the using the Euclidean Algorithm:
We get the answer in just two steps, and no factorization is needed. If isn’t zero, continue the process until some .
The Euclidean Algorithm can be extended to solve problems such as
As an example, let’s start by finding the greatest common divisor of and ,
Now, suppose we want to solve
From the gcd calculation above,
Replace the in the second equation with the one from the first to get
so and .
# Modular Division
Going back to the division equation above,
In other words, if the solution to dividing by is , then in modular arithmetic terms (modulo ), is times plus some constant multiple of . This is exactly the extended Euclidean algorithm for the gcd that we just did. If and are coprime, meaning , then from the extended Euclidean algorithm there are integers and such that
and
for every integer . Here’s the trick - when you calculate the term with is zero because is a divisor. So what’s left is
which means that
so is the inverse of .
If and is an integer multiple of , then
but there won’t be a unique solution modulo (but there will be modulo ).
We now have methods for calculating addition, subtraction, multiplication, and under special conditions, division modulo , and with the Chakravala algorithm we can find the solution to any Pell’s equation.
# The Algorithm
To solve the equation
for a given positive integer , start with values for and . An easy choice for is since setting to the next larger integer to makes small.
- Find values of such that divides , and select the that minimizes .
- Recompute
If we have a solution, otherwise find a new satisfying the constraint and iterate until .
Finding such that divides means that there is some such that
or
Using the extended Euclidean algorithm, we can find and an integer such that
The that satisfies and minimizes will have a remainder of when divided by , so it’s just a matter of finding the multiple ,
Let and start with , so . Then we want . This is equivalent to
When the problem is trivial because has to be in the set . For , is minimized when . Update and ,
Calculating a new value for , we need to be divisible by , and so any value of will do, and the value that minimizes is . Updating the values for , and give , and , so the algorithm stops with
Using the PARI/GP language, the code chakravala.gp finds the smallest values of and for a given . This is a screenshot of the solution to Chris Havens’ problem with the Ramanujan-Hardy Taxicab number 1729:
# The Prison Mathematics Project
The Prison Mathematics Projects likes to hear from people willing to volunteer time to help inmates improve their math skills. From the website,
In early 2012, a prisoner by the name Christopher Havens began studying mathematics for the very first time within the prison inside of prison. Christopher was in a form of isolation that we call solitary confinement… prisoners know it as “the hole”. Having no other form of stimulation, mathematics occupied every hour of Christopher’s days, lasting the better part of a year until he was released back into the general population. In so many cases, the negative effects of prolonged isolation manifests itself through the behaviors in both the short and the long term. However, this case is one where a mix of isolation and the transformative powers of mathematics caused Christopher to undergo a steady chain of personal growth while igniting within him a passion for mathematics.
If you have some ability in mathematics and would like to volunteer, you can submit your name and email address, and the PMP will connect you with an inmate to become their “pen pal”. Donations are also greatly appreciated.
# Reach out!
If you have any questions or comments regarding this article you can visit this thread on GitHub discussions or email us directly