mathblag

Musings on mathematics and teaching.

The Pyramids of Mars

The other day, I was having a nice conversation with a young exchange student from Mars. He explained to me that mathematics is very different on his planet, because they use triangles instead of squares.

“What on Earth do you mean?” I replied.

He took out a pad of paper and drew a square array of 25 dots, arranged in 5 rows and 5 columns.

 

test

“Yes, of course,” I said, somewhat impatiently. “Your picture clearly shows that 5 squared is 25. Are you telling me that it’s different on Mars?”

My Martian friend was unperturbed. “Certainly, 5 squared is 25 on Mars, and everywhere else in the universe. But we prefer triangles to squares. Can you guess what “5 triangled” means?

“Well, I think that 5 triangled must be 15, since 1+2+3+4+5 = 15.” I drew a picture like this.

triangle

“That is correct. On my planet, we write 52 = 15. An exponent of 2 means triangled instead of squared.”

I pondered this for a moment. “OK, if the second power is a triangle, what is the third power? Is it a pyramid?”

 

“Pyramid of 35 spheres animation“. Licensed under CC BY-SA 3.0 via Wikimedia Commons.

Pyramid of 35 spheres

“That’s the idea. It’s a tetrahedron, to be precise. In Martian mathematics, a third power is the sum of consecutive triangular numbers. For example, 53 = 1 + 3 + 6 + 10 + 15 = 35.”

This made sense to me, but I still had a nagging doubt. “We can only see objects in three dimensions. Are higher powers possible in Martian mathematics?

“Yes, of course. The pattern continues forever, even if we can’t draw the pictures. A fourth power is a sum of consecutive third powers, a fifth power is a sum of consecutive fourth powers, and so on.”

It was starting to make sense. “Does that mean that 54 = 1 + 4 + 10 + 20 + 35 = 70 in Martin mathematics?”

My friend confessed that he wasn’t sure. Fourth powers had always given him trouble in school. But he pulled out a Martian calculator (shaped like a triangle, of course) and confirmed that my calculation was correct.

Naturally, I had a million other questions about Martian mathematics.  Do they have triangular roots instead of square roots? Does the quadratic formula become a triangle-atic formula? Is there a Martian equivalent of the binomial theorem? But my friend was tired, and he suggested that I should ask his old Martian professor instead. I have arranged a meeting with her, and I will let you know what I learn.

Nit-picking the birthday paradox

The birthday paradox predicts that in a group of 23 people, there is a 51% chance that two or more share the same birthday. This calculation assumes that birthdays are uniformly and independently distributed among the 365 days of the year, ignoring leap years.

It turns out that birthdays are not quite uniform. Some days have more birthdays than others, as shown in this heat map from Facebook’s Andy Kriebel. Oddly enough, September is the most common birth month.

Screen_shot_2014-05-17_at_1.59.19_pm

Does this make any difference in our calculations? Roy Murphy collected data on birthdays from 480,040 insurance policy applications. Assuming that these frequencies represented the actual distribution of birthdays in the entire population, I ran a simulation to estimate the probability that at least two people in a group of 23 share a birthday. After 100 million trials, the number of successes was 50,784,080, which is in agreement with the theoretical probability. (My Python code is available here.)

 

Three piles of coins

A recent post by Jim Wilder reminded me of the following problem which I heard many years ago.

There are three piles of coins. You are allowed to move coins from one pile to another, but only if the number of coins in the destination pile is doubled. For example, if the first pile has 6 coins and the second pile has 4 coins, then you may move 4 coins from the first pile to the second pile — no more or less. Prove that by repeating moves of this sort, it is possible to empty one of the piles.

I will post my solution in a few days, but I would like to know the origin of this problem. Does anyone know?

A Somos Sequence

Somos sequences are sequences that are defined by certain nonlinear recurrence relations. The Somos-k sequence obeys the recurrence relation

a_n a_{n-k} = \sum\limits_{i=1}^{\lfloor k/2 \rfloor} a_{n-i} a_{n-k+1}

with initial values a_n = 1 for 0 \le n \le k-1\ .

The first interesting case is k = 4:

a_n a_{n-4} = a_{n-1} a_{n-3} + (a_{n-2})^2

The first 15 terms of the Somos-4 sequence (A006720) are

1, 1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898.

It is easy to prove by induction that a_n is always a positive rational number. It is not at all obvious that a_n is always an integer, but this is true as well. I will present a proof due to Janice Malouf and George Bergman.

Step 1: Four consecutive terms are coprime.

We first show that any four consecutive terms are pairwise coprime. The proof is by induction. It is obvious that the first four terms are pairwise coprime. Assume that a_{n-4}, a_{n-3}, a_{n-2}, a_{n-1} are pairwise coprime for some n, and let p be a a prime divisor of (the numerator of) a_n. Then p divides a_n a_{n-4}, so p also divides a_{n-1} a_{n-3} + (a_{n-2})^2. From this we conclude that

p\ |\ a_{n-2} \iff (p\ |\ a_{n-1})\ or \ (p\ |\ a_{n-3})\ .

But p cannot divide two of the terms (a_{n-3}, a_{n-2}, a_{n-1}), because we assumed that they are coprime. Therefore, p divides none of them; so (a_{n-3}, a_{n-2}, a_{n-1}, a_n) are coprime. This completes the induction step.

Step 2: Modular madness!

Direct calculation shows that (at least) the first eight terms are integers. Consider nine consecutive terms

a, b, c, d, e, f, g, h, i

and suppose that the first eight terms are integers. We will show that i is also an integer.

The recurrence yields the following equations.

ae = bd + c^2

bf = ce + d^2

cg = df + e^2

dh = eg + f^2

ei = fh + g^2

Reducing the equations modulo e yields the following equations. (The divisions are allowed because b, c, d, and e are coprime.)

bd + c^2 \equiv 0

f \equiv \dfrac{d^2}{b}

g \equiv \dfrac{df}{c} \equiv \dfrac{d^3}{bc}

h \equiv \dfrac{f^2}{d} \equiv \dfrac{d^4}{b^2d} \equiv \dfrac{d^3}{b^2}

ei \equiv \dfrac{d^5}{b^3} + \dfrac{d^6}{b^2c^2}

Step 3: A lucky factorization.

Observe that we can write the final equation as

ei \equiv \dfrac{d^5}{b^3 c^2} (c^2 + bd).

But c^2 + bd \equiv 0, so ei \equiv 0 \pmod{e}.

This implies that i is an integer.

Inscribed polygons and the Fourier transform

Draw a polygon in the plane. We can construct a new polygon by connecting the midpoints of the original polygon. I will call this the midpoint process. What happens if we repeat this process many times?

Inscribed polygons
It is clear that the polygons are shrinking to a point. We can also observe that the polygons appear to be approaching a limiting shape. I will explain why this is the case, and I will show that (except in very special cases) the limiting shape is an affine regular polygon, i.e. a regular polygon to which a linear transformation has been applied. Since linear transformations carry circles to ellipses, it follows that the limiting shape can be inscribed in an ellipse.

Credit: I learned about this problem from Michael Pershan. Please take a few minutes to read his excellent blog post on the topic, and then come back here. Also, Jason Davies has created a mesmerizing Javascript applet for exploring the midpoint process. The ideas in this post are drawn from the book Mathematical Time Exposures by Isaac J. Schoenberg.

Complex numbers

We will use complex numbers to analyze this problem. Every point in the plane is represented by a unique complex number. Similarly, a polygon with n vertices can be represented by a sequence of n complex numbers.

The equation z^n = 1 has n solutions in the complex plane. They are

1, w, w^2, \ldots w^{n-1}

where w = e^{2\pi i/n} = \cos(2\pi/n) + i \sin(2\pi/n).

If we connect these points with line segments then we produce a regular polygon. This picture shows the six complex solutions to z^6 = 1.

complex hexagon

Star polygons

We can form other polygons by connecting the vertices in different ways.

Let n \ge 3 be a fixed integer. For each integer k between 0 and n-1, let P_k be the following polygon.

P_k = (1, w^k, w^{2k}, \ldots, w^{(n-1)k})

P_1 is a regular polygon, and P_{n-1} is the same polygon with the opposite orientation. The other polygons are star polygons, except when k divides n. If k and n are not coprime, then the polygon has repeated vertices. The following picture shows P_1, P_2, P_3, and P_4 when n = 5.

star polygons

The “polygon” P_0 is rather boring. It consists of the same vertex 1, repeated n times. But we will need P_0 as well!

The discrete Fourier transform

A sequence of complex numbers x_0, x_1, \ldots x_{n-1} is transformed into a new sequence X_0, X_1, \ldots X_{n-1} by the formula

X_k = \sum\limits_{j=0}^{n-1} x_j e^{-2\pi ijk/n}.

This transformation is called the discrete Fourier transform (DFT). It is an essential tool in signal processing and image processing, and it has many other important applications. In signal processing, the Fourier coefficients X_k represent amplitudes, and the indices k are frequencies.

The DFT is an invertible transformation, and the inverse is defined by

x_j = \dfrac1n \sum\limits_{k=0}^{n-1} X_k e^{2\pi ijk/n}.

Applying this to the polygon P = (x_0, x_1, \ldots, x_{n-1}), we obtain

P = \dfrac1n \sum\limits_{k=0}^{n-1} X_k P_k.

In other words, every n-gon can be expressed uniquely as a linear combination of the P_k.

Putting it all together

You might well be wondering what this has to do with the original problem. The key idea is that the midpoint process is very easy to understand when it is applied to a regular polygon or a star polygon. Applying the midpoint process to P_k yields a smaller copy of P_k. Of course, P_0 is unchanged by this process and remains a single point. But note that P_1 and P_{n-1} shrink relatively slowly, and the other P_k shrink more rapidly. See the figure below.

inscribed pentagons

After many iterations, the polygon will look like

aP_0 + bP_1 + cP_{n-1}

because the other components will be negligible.

But we recall that P_1 and P_{n-1} are regular n-gons (with opposite orientations), and multiplication by a fixed complex number is a linear transformation. Therefore,

aP_0 + bP_1 + cP_{n-1}

is an affine regular polygon.

The loophole

There is one special case that needs to be noted. If X_1 and X_{n-1} are both zero, then the limiting shape will not be as described above. For example, if we start with a 5-pointed star, then each iteration will yield a smaller 5-pointed star. But this is an unstable equilibrium. If we perturb the star by moving a vertex by an arbitrarily small amount, then X_1 and X_{n-1} will no longer be zero, and the limiting shape will be an affine regular polygon.

Sums of periodic functions

A real function is said to be periodic if there exists a real number P > 0 so that f(x+P) = f(x) for all x. The number P is said to be a period of the function. The most familiar examples of periodic functions are the trigonometric functions sine, cosine, and tangent.

Note that if P is a period of a function, then 2P, 3P, 4P, \ldots are also periods. If a periodic function is continuous and nonconstant, then it has a least period, and all other periods are positive integer multiples of the least period.

There are discontinuous periodic functions that have no least period. The most famous example is the Dirichlet function, defined by D(x) = 1 if x is rational, D(x) = 0 if x is irrational. Every positive rational number is a period of the Dirichlet function, so there is no least period.

Sums of periodic functions are often periodic

The sum of two periodic functions is often periodic, but not always. Suppose that f is periodic with least period P, and g is periodic with least period Q. If P and Q have a common multiple R, then f+g is periodic with period R. However, R is not necessarily the least period of f+g. To give an extreme example, \sin(x) + -\sin(x) has no least period.

Some readers may have heard of biorhythm theory, which was popular in the 1970s. The theory claims that humans are influenced by three fundamental cycles: a physical cycle of 23 days, an emotional cycle of 28 days, and an intellectual cycle of 33 days. These cycles are usually modeled as sine waves that start on one’s day of birth. We might suppose that a person’s happiness on day x is the sum of these three cycles.

h(x) = \sin\frac{2\pi x}{23} + \sin\frac{2\pi x}{28} + \sin\frac{2\pi x}{33}

biorhythm

The figure shows a portion of the graph of this function. It appears to be quite irregular but in fact it repeats every 21,252 days, since 21,252 is the least common multiple of 23, 28, and 33. (View this graph on Desmos.)

Sums of periodic functions are not always periodic

If the periods of two periodic functions do not have a common multiple, then their sum is not periodic. Perhaps the simplest example is \sin(x) + \sin(\pi x), whose terms have least periods 2π and 2 respectively.

Polynomials are finite sums of periodic functions

Sums of periodic functions can be peculiar indeed. In fact, we can prove the following astonishing theorem: If P is a polynomial function of a real variable, and the degree of P is n, then P is the sum of n+1 periodic functions.

It is clear that a non-constant polynomial cannot be expressed as a finite sum of continuous periodic functions, since a continuous periodic function is bounded, and a finite sum of bounded functions is bounded. In fact, it can be shown that an unbounded continuous function cannot be expressed as a finite sum of Lebesgue measurable periodic functions. Consequently, we will need to use the Axiom of Choice.

R as a vector space over Q

The statement that every vector space has a basis is equivalent to the Axiom of Choice. Since \mathbb{R} is a vector space over \mathbb{Q}, there is a subset A of \mathbb{R}, called a Hamel basis, so that every real number can be written uniquely as a finite linear combination of elements of A with rational coefficients.

For each x \in \mathbb{R}, we write x = \sum_{a\in A} (x,a) a where (x,a) is rational and \{a \in A: (x,a) \ne 0\} is finite for every x.

Periodicity of (x,a)

It is readily seen that (x+y,a)=(x,a)+(y,a) for all x,y \in \mathbb{R} and all a \in A.  Moreover (a,b)=0 for distinct a,b \in A. It follows that (x+b,a)=(x,a) for all x \in \mathbb{R} and distinct a,b \in A. In other words, the function x \mapsto (x,a) is periodic with period b for any b \in A\setminus a.

The identity function is the sum of two periodic functions

Choose two distinct elements c,d \in A. Then x = (x,c)c + \sum_{a \in A\setminus c} (x,a) a.

Let f_1(x) = (x,c) c and f_2(x) = \sum_{a \in A\setminus c} (x,a)a.

Then f_1 has period d, f_2 has period c, and f_1 + f_2 is the identity function.

x^2 is the sum of three periodic functions

Note that x^2 = \sum_{a, b \in A} (x,a)(x,b) ab. Choose three distinct elements c,d,e \in A. The term (x,a)(x,b)ab has period c, unless a=c or b=c. Since no term involves all three of c,d,e, it follows that each term has a period of either c, d, or e.

Let C be the sum of all terms which have period c; let D be the sum of all terms which have period d but not c; and let E be the sum of all terms which do not have period c or d. Such terms must have period e.  More specifically,

C = \sum_{a, b \in A\setminus c} (x,a)(x,b)ab

D = (x,c)^2 c^2 + 2\sum_{a \in A\setminus\{c,d\}} (x,a)(x,c)ac

E = 2(x,c) (x,d) cd

Then x^2 = C + D + E is a representation of x^2 as the sum of three periodic functions.

A polynomial of degree n is the sum of n+1 periodic functions

Let P be a polynomial of degree n. Using the identity x = \sum_{a\in A} (x,a)a we can express P(x) as a linear combination of products (x,a)(x,b)(x,c)\ldots with a,b,c,\ldots \in A. Each term involves at most n distinct elements of A.

Let a_0, a_1, \ldots, a_n be n+1 distinct elements of A. No product (x,a)(x,b)(x,c)\cdots in the expansion can involve ALL of a_0, a_1, \ldots, a_n. Therefore, we can group the terms into n+1 sums, P_0, P_1, \ldots, P_n, so that no term in P_i involves a_i.

Thus, we have P(x) = P_0(x) + P_1(x) + \cdots + P_n(x), and each P_i has period a_iQED.

A polynomial of degree n cannot be written as the sum of n periodic functions

Suppose that for some n, there is a polynomial P of degree n which is the sum of n periodic functions. Let p be one of the periods. Then P(x+p) - P(x) is a polynomial of degree n-1, and it is also the sum of n-1 periodic functions, since one of the terms cancels. By repeating this, we eventually obtain a polynomial of degree 1 that is the sum of 1 periodic function. But this is absurd.

e^x is not the sum of periodic functions

Suppose that e^x is the sum of n periodic functions. Let p be one of the periods. Then e^{x+p} - e^x is the sum of n-1 periodic functions, since the term with period p cancels out. But e^{x+p} - e^x is a constant multiple of e^x, so we conclude that e^x is the sum of n-1 periodic functions. By repeating this, we find that e^x is the sum of 1 periodic function. But this is absurd.

Reference

Stefano Mortola and Roberto Peirone, The Sum of Periodic Functions, Topology Atlas Document # vaaa-21

Ice cream quiz

This problem was posted in an ice cream shop in Oxford, England. I found it surprisingly difficult.

ice cream quiz

Here is my solution. Suppose that x + 3 = a^3 and x^2 + 3 = b^3. After substituting,

a^6 > (a^3 - 3)^2 + 3 = b^3

which implies that a^2 - 1 \ge b. Therefore

(a^3 - 3)^2 + 3 \le (a^2 - 1)^3

a^6 - 6a^3 + 12 \le a^6 - 3a^4 + 3a^2 - 1

3a^4 - 6a^3 - 3a^2 \le -13

3a^2 (a^2 - 2a - 1) \le -13

But the left side is positive for a \ge 3, so there are no whole number solutions.

Image credit: Janet McKnight

Thanks to @samuelprime and @nodrogadog for pointing out mistakes in earlier versions of this post.

Imagining large numbers

One thousand

  • People: moderately sized school.
  • Dollars: price of a laptop computer.
  • Pounds: weight of a polar bear.
  • Miles: distance from St. Paul to Dallas.
  • Seconds: About 17 minutes.

One million

  • People: Population of San Jose, California. Participants in the  Million Man March.
  • Dollars: Cost of an expensive house or a CAT scanner.
  • Pounds: Maximum take-off weight of a 747.
  • Miles: Lifetime distance traveled by car (100 miles/day for 30 years).
  • Seconds: About 12 days.

One billion

  • People: Population of India.
  • Dollars: Net worth of JK Rowling, author of the Harry Potter books.
  • Pounds: The Golden GateBridge weighs about 2 billion pounds.
  • Miles: Distance to Saturn.
  • Seconds: About 32 years.

One trillion

  • People: The hypothetical populations of the world, if all land area on the globe were as densely populated as Hong Kong.
  • Dollars: Approximate cost of the Iraq war.
  • Pounds: World annual rice production.
  • Miles: One fifth of a light year.
  • Seconds: About 30,000 years. The earliest known cave paintings are about 30,000 years old.

One quadrillion

  • People: Number of ants in the world.
  • Dollars: Total world purchasing power for 15 years, at current levels of production.
  • Pounds: Total world coal reserves.
  • Miles: About 170 light years.
  • Seconds: About 30 million years.

Study guide for beginning algebra

Here is a study guide that I wrote when I was a TA for a beginning algebra class. I hope that someone finds it useful. algebra_review

Primes of the form 6k+1

Euclid’s proof of the infinitude of primes is justly famous. Here is one version of this proof:

Let P be a finite set of primes, and let N be the product of the numbers in P. Then N+1 is not divisible by any number in P, since it leaves a remainder of 1. But N+1 must be divisible by at least one prime, so P cannot contain all of the primes. Therefore the set of primes is infinite.

A variation of this argument shows that there are infinitely many primes of the form 6k - 1.

Let P be a finite set of primes of the form 6k - 1, and let N be the product of the primes in P. Consider the number 6N - 1. It is not divisible by 2 or 3, nor is it divisible by any number in P. But it is not possible that all prime factors of 6N - 1 have the form 6k + 1, because the product would have the form 6k + 1 as well.

Therefore, 6N - 1 has at least one prime factor of the form 6k - 1 that does not belong to P. Therefore, P cannot contain every prime of the form 6k - 1, so the set of primes of this form is infinite.

It takes a little bit more work to prove that there are infinitely many primes of the form 6k + 1. Here is a proof of that fact.

Let P be a finite set of primes of the form 6k + 1, and let N be a number that is divisible by every number in P. Assume that N is also divisible by 6. Let p be a prime divisor of N^2-N+1.

Note that (N^2-N+1)(N+1)=N^3+1. so p divides N^3+1, or in other words N^3 \equiv -1 \pmod{p} and so N^6 \equiv 1 \pmod{p}.

Recall that the order of N modulo p is the least positive k so that N^k \equiv 1 \pmod{p}. The order must divide 6. so k = 1, 2, 3, or 6. But N^3 \equiv -1 \pmod{p}, so the order cannot be 1 or 3.

Can the order be 2? If N^2 \equiv 1 \pmod{p} and N^3 \equiv -1 \pmod{p} then N \equiv -1 \pmod{p}. This would be bad, because then p would divide both N+1 and N^2-N+1; but \gcd(N+1,N^2-N+1) = \gcd(N+1,3) < p, contradiction.

Thus N has order 6 mod p, and the group of units mod p has order p-1, so 6 divides p-1, which means that p has the form 6k+1. Therefore, P does not contain all primes of the form 6k+1, so the set of primes of this form is infinite.

Follow

Get every new post delivered to your Inbox.

Join 1,705 other followers