The Oldest Computer Program

I’m preparing for my classes next semester, and one of the courses I’ll be teaching is cryptography (a majors-level course).  Perhaps the most remarkable feature about cryptography, and a telling feature about mathematics in general, is the following:

Computer security relies on mathematical algorithms that are at least 250 years old.

Put another way:  250 years ago, there was no practical use for a very broad area of mathematics.  Today, that area of mathematics is the basis of civilization in the 21st century.  Any time you visit a website with an  https designation, you are using a method of encryption that could have been invented by Thomas Jefferson.

A crucial component of modern cryptographic implementations is the fast powering algorithm.  The first recorded appearance of this algorithm was in the work of Pingala, an Indian mathematician who lived in the 3rd century BC.  Pingala not only wrote down the algorithm, but (in modern terms) wrote down a computer program to implement it.  Incidentally, the treatise of Pingala was the first to use the zero symbol (though in Pingala’s manuscript, it’s just a symbol that has no specific meaning).

Here’s a video I’ve prepared on the subject:


Obesity, Poverty, and National Security

According to the internet, if you ate only ramen, you’d save thousands of dollars each year in food.

That sounds great, except there’s a problem: ramen lacks a wide range of essential nutrients and vitamins. You’d lose your teeth to scurvy, a lack of vitamin D would cause your bones to become brittle and easily broken, you’d suffer nightblindness from a lack of vitamin A, and you’d be tired all the time from a lack of iron and the B vitamins. In short, all the money you saved on food, and much, much, more, would be spent on increased medical care.

The problem is that eating healthy is costly. And this leads to a national security crisis.

If you want the short version, I’ve summarized the key points in a ten-minute video:

A little more mathematics:

Food buyers face what mathematicians call a constrained optimization problem: they have to meet certain caloric and nutritional goals (the constraints), which defines a feasible region. Generally speaking, any point in the feasible region defines a solution to the problem; what you want to do is to find the optimal solution.

The optimal solution is generally determined by the objective function. For example, if you lived off x packages of ramen and y eggs, the important objective function might be the total cost of your meals. At 15 cents a pack of ramen and 20 cents an egg, the objective function has the form L = 0.15x + 0.20y, and we might want to minimize the value of the objective function.

In the following, I’ll assume you want to minimize the value of the objective function; the arguments are similar if you’re trying to maximize the value (for example, if you’re designing a set of roads, you might want to maximize the traffic flow through a town center).

There’s a theorem in mathematics that says the optimal solution will be found on the boundary of the feasible region. The intuition behind this theorem is the following: Imagine any point inside the feasible region. If you change any one of the coordinates while leaving the others the same, the value of the objective function will generally change. The general idea is to move in the direction that decreases the objective function, and continue moving in that direction until you hit the boundary of the feasible region.

At this point, you can’t move any further in that direction. But you can try one of the other directions. Repeating this process allows us to find the optimal solution.

We can go further. Suppose our objective function is linear (like the cost function). Then the same analysis tells us the optimal solution will be found at a vertex of the feasible region. This suggests an elegant way to solve linear optimization problems:

  • Graph the feasible region and locate all the vertices. Generally speaking, the constraints are themselves linear functions, so (in our ramen and egg example) the feasible region will be a polygon.
  • Evaluate the objective function at each vertex,
  • Choose the vertex that minimizes the value of the objective function.

Easy, huh? Except…

  • If you have n commodities, you have to work in \mathbb{R}^{n}.
  • This means the feasible region will be some sort of higher solid.
  • This also means that finding the vertices of the feasible region will require solving systems of n equations in n unknowns.

In 1945 ,George Stigler did such an analysis to find a minimal cost diet that met caloric and nutritional requirements. To make the problem tractable, he focused on a diet consisting of just seven food items: wheat flour; evaporated milk; cabbage; spinach; dried navy beans; pancake flour; and pork liver.

“Thereafter the procedure is experimental because there does not appear to be any direct method of finding the minimum of a linear function subject to linear conditions.” The problem is that with seven items, you’re working with hyperplanes in \mathbb{R}^{7}, and the constraints will give you hundreds of vertices to check.

Note the date: 1945. What Stigler didn’t know is that there was a method for finding the minimum value easily. But that’s a story for another post…

Why Study Higher Mathematics?

Just about everyone will tell you that mathematics is important and should be taught in school.  All the arguments are over the type of mathematics that should be taught.  Algebra?  Statistics?  Probability?  Real world problems (“John has 137 erasers to distribute among 17 students…”)?  Math world problems (“How many ways can Ellen arrange six different books on a shelf…”)?

The problem is that you can’t answer the question of “What should we teach in school?” until we answer the question of “Why should we have an educated population?”  There are three reasons for getting an education:

  1. To help yourself.
  2. To help your community.
  3. To help your government.

These goals aren’t mutually exclusive:  If you help yourself, for example by getting a better job, then you help the government, because you pay more in taxes (and, because you have a better job, you are more likely to want to keep things the way they are…so you support the government).  Likewise, if you help your community, you’re helping yourself, because you’re making your own living environment better.  At the same time, helping the community might not be helping the government, and vice versa.

This is where things get interesting.  If school mathematics focuses on “real world problems” and “useful mathematics,” then it’s set up to help individuals and the government.  However, there’s no guarantee that this will help the community:  wealthy persons exist, even (and perhaps especially) under repressive regimes.

Here’s why higher mathematics is important.  First, a quick definition (my own):  Higher mathematics is any mathematics that focuses on proofs.  Every branch of mathematics can be taught and learned at a higher level:  3 + 2 = 5 is arithmetic and very basic; higher mathematics occurs when you ask (and answer) why 3 + 2 is 5.

I’ve talked elsewhere about why mathematicians do proofs. Despite my silver-tongued eloquence, not everyone is convinced:  students continue to ask “Why should we have to prove things that everyone knows?”  But consider this:  Throughout history…

  • Everyone knew that men were smarter than women.
  • Everyone knew the sun went around the Earth.
  • Everyone knew that slavery was acceptable.

Progress occurred when people began asking “Well sure, everyone knows these things…but are they really true?”

And this is one of the things that higher mathematics trains you to do:  Proof causes you to ask questions about what “everybody knows.”  Take that “3 + 2 = 5”.  What do we really mean by that?  There’s a few different answers, but one of them is “3 + 2 is the second number after 3.”  (You can go in a few different directions after this point, but that’s another story)

We can go further:  proof requires us to construct a logical argument, with each step based on the step before it.  We can’t make bold leaps, like “Since this happened one time, it must happen all the time.”  Instead, we have to establish a chain of causality, with each step carefully constructed.

We can go further still:  proof forces you to constantly question your own beliefs.  Many people accept 5 \times 3 = 3 \times 5 without question.  But if you’ve been taught to do proofs, there’s a little voice inside your head saying “Why do you believe that?”  If the answer is “Because someone told me it was true”, then you’re uncomfortable…and try to find evidence.

Now for the punchline:  You can slant history to make sure your country is always right, and other countries are always wrong.  Philosophy can be wrangled to serve the state:  China did this for two thousand years.  Even science can be forced into doctrinal correctness:  physics and chemistry did very well under the Soviets.  The arts can be browbeat into submission; literature can be stifled; engineering can be co-opted.

But questioning belief and demanding evidence is an integral part of higher mathematics.  You cannot remove these components from higher mathematics without destroying higher mathematics.

And if the state chooses not to teach higher mathematics?  Then the mathematics needed to solve new problems will not be developed.  Individuals and society will suffer…and the government will be replaced.    Thus I claim:

The development and continued existence of a free society depends on the teaching of higher mathematics.

Two Is the Oddest Number

One of the biggest problems facing anyone in a creative field is:  How do I create something new?  For obvious reasons, you can’t be taught how to be original.  But there are some ways you can make it easier for your creativity to emerge.  Here’s one strategy:  Two is the oddest number.

What does that mean?  One of my thesis advisors (and the original source of the saying) explained it like this.  To a mathematician, there are only three numbers:  zero, one, or infinity.  Either something doesn’t exist at all (zero); it’s unique (one); or it happens infinitely often (infinity).

For example, suppose you have a line and a point.  In Euclidean geometry, there is a unique straight line through the point that is parallel to the given line.  In spherical geometry, there are zero straight lines through the point that are parallel.  In hyperbolic geometry, there are an infinite number of straight lines through the point that are parallel.  Thus zero, one, or infinity.

Or consider primes.  There is a unique even prime:  2.  All other primes are odd.

So how does this help you create something new?  One way is to try and find a second example of something.  Here’s an example, that requires some background in permutation groups.  Here’s the short version, though if you really want to delve into the topic, take a look at my (in progress) videos on abstract algebra.

Suppose I have a set of distinct symbols a, b, c, d, \ldots.  A permutation occurs when I rearrange the symbols.  It’s best to think of the permutation as what happens when you do a “replace all” in a document.  A compact way to represent these permutations is cycle notation, where an expression like (abc) indicates you’re going to replace all as with bs, all bs with cs, and all cs with as.  Because this cycle has three elements, it’s called a 3-cycle.

We can also have 2-cycles:  (ab).  These occur so often that we have a special name for them:  they are transpositions.  

We can juxtapose two cycles (of any length) and form a composition.  For example, (ac)(ad).  For somewhat technical reasons, we read these from right to left.  Thus first we replace all as with $latex $d$s, and all ds with latex $a$s; then we replace all as with cs and cs with as.  The net effect is that all as have been replaced with ds; all ds with cs (because the first cycle replaced them with a a, and the second cycle replaced the a with a c); and all cs with as.  So (ac)(ad) is the same as (adc).

In a similar manner, we can write (ac)(bc) as (acb).

At this point, the mathematician says “Hmmm…two times we’ve managed to replace a composition of two transpositions with a 3-cycle.  But two is an odd number…maybe we can always replace a composition of two transpositions with a 3-cycle?”

So now we try it on (ab)(cd).  And we find…the first component of a rather important theorem in the study of permutations.

Why Do Proofs

Proof is an essential part of mathematics, but it’s sometimes not clear why we prove things in mathematics.  By way of example, let’s consider a simple problem:  Multiplying two even numbers.

If you were a scientist, you would collect data. For example:  4 \times 6 = 242 \times 8 = 1610 \times 10 = 100, and so on.  After a few hundred pieces of evidence, you would form an hypothesis:  The product of two even numbers is even.  You might then perform some more experiments to test the hypothesis:  82 \times 14 = 114814 \times 32 = 44811 \times 4 = 44 (then sheepishly realize that 11 isn’t even, so we’ll ignore that), 24 \times 4 = 95 (better recheck that…yup, it’s supposed to be 96), and so on.

But if you’re a mathematician, you’d next try to prove that the product of two even numbers is an even number.  The first thing to realize is this:  No one ever tries to prove anything they don’t already believe to be true.  If you asked me to prove the product of two even numbers is an odd number, I’d say “But that’s not true…why should I waste time trying to prove it?”  What this means is that we don’t prove things because we doubt their truth:  proof isn’t a way of obtaining truth, because in some sense, we already have it.

So why do we prove things?  Let’s consider what we’d have to do.

  • First, what do we mean by “the product of two even numbers?”  We need to clarify what we mean by an even number:  “I know it when I see it” isn’t good enough.  We come to the conclusion:  An even number is any number that can be written as the product of 2 and some other whole number m.
  • So now we multiply two even numbers:  (2m) \times (2n) = 4mn.
  • But we need to write this as a product of 2 and some other number, so we have 4mn = 2 (2mn).

There’s our proof.

But stop and smell the roses.  Halfway through, we found the product of two even numbers was 4mn.  This means that the product of two even numbers is in fact a multiple of 4.  If we go back to our data, we’ll see that it’s there…but it might not have been obvious at the time.

So what has this effort of proof given us?

  • We had to dig down deep and elaborate on what we man by “even number.”  In general, proof requires us to define our terms in a meaningful and useful way.
  • We had to use a little bit of algebra.  In general, proof requires us to review mathematics we’ve already learned.  (In fact, since most terms in mathematics have a standard definition, the first step also requires a review of the mathematics we’ve learned…or the mathematics we should have learned)
  • We discovered something that we might have missed the first time around.

A Mathematical Litmus Test: The Handshake Problem.

Broadly speaking, mathematics can be separated into two very broad categories:  algebra and analysis.  Mathematicians likewise fall into these categories.

Which type of person are you?  One possible litmus test concerns the handshake problem, which I was introduced to as an undergraduate.  The handshake problem is the following:

Every person in the world has a handshake number, which is the number of times they’ve shaken hands with someone else.  This handshake number is either odd or even.  Is the number of people with an odd handshake number even or odd?

I’ll let you think about the answer for awhile.