March 11, 2015

Explaining Huffman’s Impossible Pyramid

I read about Huffman’s Pyramid from the consistently excellent blog Futility Closet. Huffman’s Pyramid is a drawing of a figure that cannot exist.

However, the impossibility of this figure is hardly obvious. Here is the reason: if the slanting lines were extended, then they would have to meet at the apex of a pyramid. However, the lines do not meet. Contradiction!

Are you convinced yet? If you are, then your geometric intuition is stronger than mine, and you can probably stop reading now. But if you are skeptical, as I was, then please continue reading.

First, we should ask this question: What exactly do we mean by an impossible figure? Surely a figure can’t be impossible if we can draw it. Sometimes we can even make a physical model of an impossible object, such as this impossible triangle sculpture in Perth.

I think that what we mean by an impossible figure is that the figure appears to have contradictory properties. The sculpture shown above is not actually a triangle, but it appears to be a triangle from a certain angle, and this apparent shape is inconsistent with other things that we can observe about the sculpture.

Let’s consider Huffman’s Pyramid again. We’ll label the points to make it easier to talk about.

The drawing appears to represent a polyhedron with two triangular faces and three quadrilateral faces. The triangular faces are ABC and DEF. The quadrilateral faces are ABED, BCFE, and CADF. It also appears that AD and BE intersect at I, AD and CF intersect at G, and BE and CF intersect at H. If we accept this interpretation of the drawing, then the shape that it represents is impossible.

Here’s why. Consider the plane Π containing the face ABED. The plane contains G, since G is on the line AD. The plane also contains H and I, since they are on the line BE. Therefore, Π contains the triangle GHI. Similarly, the plane containing the face BCFE must also contain the triangle GHI. But there is only one plane that contains the triangle GHI, so the two planes must be the same. Therefore, the entire shape lies in a plane, and it cannot be a polyhedron.

This seems to suggest that pentahedra can’t be too irregular. It would be interesting to explore this notion further.

Edit: Greg Ross suggests that the figure might be possible if there is another hidden edge. Can anyone explain this?

5 Comments

July 11, 2014

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.

“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.

“That is correct. On my planet, we write 5² = 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

“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, 5³ = 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 5⁴ = 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.

1 Comment

May 18, 2014

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.)

October 14, 2013

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?

1 Comment

October 13, 2013

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.

October 8, 2013

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?

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$ .

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$ .

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.

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.

1 Comment

September 1, 2013

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}$

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_i$ . QED.

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

15 Comments

August 31, 2013

Ice cream quiz

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

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.

2 Comments

August 30, 2013

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.

5 Comments

August 30, 2013

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

1 Comment

	Anonymous on How much water is in the …
	involution on Sums of periodic function…
	Anonymous on Sums of periodic function…
	avatarbizarre on Fibonacci Pigeons
	First Day Math Probl… on Sums of consecutive integ…