The Fast Fourier Transform (FFT) Series

Chapter 1: What is the Square Root of Negative Nine?

The Fast Fourier Transform is a very complex (no pun intended) algorithm that is built upon many of the most fascinating ideas in mathematics — and it has an even more interesting history. It also has practical applications, but, let's be honest... who gives a hoot about those.

Here on this page, the math jester will present a casual, step-by-step explanation of the Fast Fourier Transform, in a quasi-Socratic format.

As the math jester loves to say: mathematics is best done in a slow, deliberative, step-by-step manner, without the constant pressure of competition or the ticking of a timer.

Those who can already define imaginary numbers should skip to the Table at the bottom of this chapter (and then, when they're ready, proceed to Chapter 2).


Pick any natural number. Concentrate on it.

I am going to channel the magic of math to guess your number.

...

Just kidding.

But I can show you some cool facts about your number.

Let n be your number. Consider two intermediate values: P, defined as n+1, and Q, defined as n-1.

Compute P*Q and compare it to n2. Which is larger?

Before we continue, notice that this problem corresponds to a geometric problem: which has more area, a square of side length n, or a rectangle of dimensions (n+1) by (n-1)?


As many of you already know, the square has greater area.

I have deliberately chosen these basic problems, because the next lessons will build on them. Also, it doesn't hurt to hang a question mark on a known truth from time to time, or however that quote went.

Speaking of square roots and simple problems, let's go into even simpler territory and ask, what is a square root?


The right generalization can make a problem easier to solve.
— John D. Cook

Let us start at the beginning.

Suppose I asked you to compute the square root of nine.

You would say three, right?

You would be absolutely correct.

But what would you say if I asked you to compute the square root of negative nine?

Often times, in order to find a answer to a more general question in mathematics, one needs to review what they already know and introduce other constructs and notation. If we were to generalize the factorial function, for example, we would need to find deep properties that the factorial obeys and apply them to non-integer parameters. But that's a story for another day.

When you're asking for a "square root," you're really asking, what number satisfies a*a = 9?

a = 3 satisfies the equation.

Aha, but there is a catch!

There is another number that also satisfies the same equation.

That number, as you well know, is a=(-3).

The most mathematically literate among you may say, "but the square root demands a principal root!" And you'd be right -- but let us ignore that for a moment. This is an example where there are benefits of looking at the bigger picture -- and focusing on principal roots actually hinders our ability to generalize.

The takeaway is that a2 = 9 has two solutions and not just one.


This question corresponds to the polynomial x2 - 9.

We also learn that this can be factored into (x - 3)(x + 3).

This also has a graphical representation as a parabola that is centered at the origin and has two x-intercepts: one at x=-3 and one at x=+3. These connections between algebra and geometry are often mind-blowing — but again, that is a story for another day.

The point is, the general question "what is the square root of c?" can be rephrased as "what are the solutions to x2 - c?"

From this perspective, if we were to demand an answer to the question, "what is the square root of negative nine?", we would therefore need to make sense not just of "sqrt(-9)," but also of the corresponding polynomial, x2 + 9.

As you can see, the general question "what is the square root of c?" can be rephrased as "what are the solutions to x2 - c?" Remember this, it will prove important.

Take a minute and brainstorm some ways in which we can modify this formula. What are some choices and constraints you can make for the variable c? How else could you try to generalize it? This is a small taste for the questions we will be exploring in chapter 2.

Already Know This?


Sometimes it is the people no one can imagine anything of who do the things no one can imagine.
— Alan Turing
Corollary: Sometimes the simplest-looking polynomials have the deepest stories behind them.
— The Math Jester

I provide a table here as a cryptic and, dare I say, sacred, message from the future. What patterns do you notice in it?

In Chapter 2, all will be revealed.


Index Mystery Polynomial
1 t-1
2 t+1
3 t2+t+1
4 t2+1
5 t4+t3+t2+t+1
6 t2-t+1