Back in July, Sam Shah described a beautiful and haunting problem he had encountered at PCMI:

Put n evenly spaced points on a unit circle, with one point at (1,0). Then draw chords from this point to all the other points. Then multiply the chords’ lengths. What do you get?

Mimi Yang drew some great illustrations of the problem, and Mr. Ho made a very slick geogebra applet that illustrates and gets data at the same time.

Sam mentioned an extension problem:

Scale the circle vertically by a factor of $\sqrt{5}$. Scale all the chords too. What is the product of the lengths now?

Mr. Ho outdid himself by creating a geogebra applet for this one too. In fact, he lets you scale the ellipse in all kinds of ways.

It’s really this extension that’s the subject of this post. But first…

Background on the original problem

If you haven’t bumped into this problem yet and it’s not obvious to you how to solve it, you might want to experiment a bit, if nothing else then with Mr. Ho’s applets. I am going to talk about the problem’s results, which are awesome, so I’m warning you now that if the problem is new to you but you read on, I’m going to steal some of your fun.

People posted solutions in the comments to Sam’s original problem statement. The solutions fell into 2 categories:

1) Direct calculation of the product using trigonometry. These methods were able to produce a surprising conjecture about the product of lengths for n points, but were not able to prove it.

2) Recognition that if the points are treated as numbers in the complex plane, they are precisely the nth roots of unity, followed by exploitation of the algebra of the nth roots of unity. These methods were able to prove the conjecture. (For example: Andrew’s comment at Sam’s original post; gasstationwithoutpumps has his/her (?) own post on the subject.)

This is as far as I can get before stating the result; so – SPOILER ALERT.

For n points on the circle, the product of all these chords, most of which have irrational lengths, is a positive integer. Not any positive integer, but n itself.

Here is the roots-of-unity proof, which I’ve done my best to render in a way that’s accessible even if you’ve never worked with roots of unity before. You do need to be familiar with the geometry of complex numbers though.

If you interpret the n equally spaced points on the circle as complex numbers, then they are precisely the nth roots of 1: $\omega, \omega^2, \dots, \omega^{n-1}$ where $\omega$ is the first of the numbers you find if you go around the circle counterclockwise after you leave the positive real axis. (Think about what happens when you multiply this number by itself n times, to convince yourself of this.) Since the point from which all the chords emanate is the number 1, the product of the lengths is the absolute value of the product of the complex numbers $(1-\omega), (1-\omega^2), \dots, (1-\omega^{n-1})$. This product has a startlingly elegant form, which can be seen by noticing that this product is exactly the product $(z-\omega)(z-\omega^2) \dots (z-\omega^{n-1})$ evaluated at $z=1$; and that this product is exactly the monic polynomial that has $\omega, \omega^2, \dots, \omega^{n-1}$ as roots. What are they roots of? Oh right, unity. In other words, they are all zeros of the polynomial $z^n-1$. This polynomial also has 1 itself as a root (because 1 is an nth root of 1 too), so you have to divide it by a factor of $z-1$ in order to get the polynomial that has only the omegas as roots.

$z^n-1=(z-1)(z-\omega)(z-\omega^2)\dots(z-\omega^{n-1})$

$(z-\omega)(z-\omega^2)\dots(z-\omega^{n-1})=\frac{z^n-1}{z-1}=z^{n-1}+\cdots+z+1$

And now, evaluation of this at $z=1$ gives you 1+1+…+1 = n. The product of the chord lengths is the absolute value of this, but this is a positive real number so its absolute value is itself. Thus the product of the chord lengths is n. QED.

The ellipse extension

So everybody who produced a proof to the original problem did it by using the algebra of the nth roots of unity. The first thing that grabbed me about the ellipse extension is that while it is obviously closely related to the original problem, it immediately destroys the linchpin of this method. As soon as the circle gets stretched up to the ellipse, the points are no longer nth roots of unity!

The next thing that grabbed me about it was Tom’s comment on Sam’s original post:

I created my own Geogebra applet to investigate the problem with the ellipse (as you have it written I think). The products turn out to be very interesting:

The lengths of the cords are as follows for certain n:

n length
2 2=2*1
3 6=3*2
4 12=4*3
5 25= 5*5
6 48=6*8
7 91=7*13
8 168= 8*21
9 306=9*34
10 550=10*55

So the conjecture would then be

n n*F_n

where F_n is the n’th Fibonacci number.

WHAT???

(As an aside, the type of reaction I had to Tom’s comment is something we should be cultivating in students. Observation of an unexpected pattern leads naturally to a feverish search for an explanation. This is why it’s so important not to treat a pattern noticed as an established fact: this kills the students’ natural wonderment about the why of the pattern.)

Mr. Ho confirmed Tom’s calculations with his own applet. He had a look at other scale factors besides $\sqrt{5}$ but didn’t find anything. At this point, the problem officially had itself ensconced semi-permanently in the back of my brain. How (the hell) are the frickin Fibonacci numbers arising? If you know something about the Fibonacci numbers, you know that they’re related to the golden ratio, which is related to $\sqrt{5}$, so that kind of makes sense, but c’mon now, only kind of. It’s not like the connection is jumping out at me.

Still, I couldn’t justify spending a lot of time on the problem. I try to stick with math problems that fit into a program of study I’ve given myself, and this one didn’t obviously do that. Nonetheless, it was lodged in my head firmly enough for me to describe it to my excellent colleague Japheth Wood (News from the Math Wizard). The next day, he sent me the following in an email:

Update on the stretched diagonals problem. I wrote a short program in
Python to do some calculations, and I found out the following
patterns, when sqrt{5} is replaced by sqrt{4a+1}:

Conjecture: The product of the diagonals of the stretched n-gon is P_n
= n*T_n, where T_n is an integer sequence defined by:
T_1 = T_2 = 1 and T_{n+2} = T_{n+1} + a*T_n
* This is true in the case of the non-stretched circle: a = 0, and
this recurrence gives P_n = n * 1, which is known.
* This seems true in the PCMI case. 5 = 4*1 + 1, so a = 1, and the
recurrence is Fibonacci.
* The other cases where a is an integer seem true by data I’ve collected.
* The conjecture even seems true when a is not an integer.

# WHAT??!!?

Okay, now the time had obviously come for me to give this problem some serious love. Japheth had just a) exploded onto a completely new level my sense that there’s a lot going on here, and b) given me enough of a direction that I knew some real elbow grease would pay off. I spent quite a few hours this weekend with the problem. What I found is still nowhere near a proof, but it strengthens Japheth’s conjecture and suggests some lines for further investigation. Here’s what I did:

First I found some closed forms for Japheth’s recursive sequence $T_n$:

Closed form #1: Using a standard method involving encoding the recursion $T_{n+2}=T_{n+1}+aT_n$ into a matrix and then diagonalizing the matrix (which I learned – like all the linear algebra I know – from Michael Artin’s Algebra, chapters 3 and 4), I found that

$T_n=\frac{u^n-v^n}{u-v}$

where $u$ and $v$ are the two roots of the polynomial $x^2-x-a$. I didn’t end up using this result but I think it’s very pretty. I’m sure it’s well-known but it’s new to me.

Closed form #2: I got a different formula by directly calculating the first few values of $T_n$ in terms of a, and looking for patterns:

$T_1=1$
$T_2=1$
$T_3=1+a$
$T_4=1+2a$
$T_5=1+3a+a^2$

I put this in a table for ease of calculation and pattern-searching:

$n$ $T_n=$ $1$ $a$ $a^2$ $a^3$ $a^4$
1 1
2 1
3 1 1
4 1 2
5 1 3 1
6 1 4 3
7 1 5 6 1
8 1 6 10 4
9 1 7 15 10 1

This is just a downward-slanted Pascal’s triangle! (Look at what the recursion $T_{n+2}=T_{n+1}+aT_n$ does to a pair of rows to get the next row; this tells you why.) It follows that

$T_n=\displaystyle\sum_{k=0}^{\left \lfloor (n-1)/2 \right \rfloor} \binom{n-k-1}{k} a^k$

The next thing I did was to reason as follows: in the original circle problem, all the power of the roots-of-unity method came from knowing the polynomial $x^n-1$ that has these numbers as roots. Now that the circle has been stretched to an ellipse, the points no longer represent roots of unity; but if I could find the polynomial that had these numbers as roots…

I assumed that $a$ would be such that $\sqrt{4a+1}$ would be a real number, so that using it as the vertical stretch factor would make geometric sense. I put no other restrictions on $a$. Then I just started calculating:

n=2: The points are at 1 and -1; no change when you stretch. The polynomial is $g(z)=(z-1)(z+1) = z^2-1$.

n=3: The points are at 1 and $\frac{-1 \pm \sqrt{3} \mathrm{i}}{2}$. Vertical stretching by a factor of $\sqrt{4a+1}$ makes the latter two into $\frac{-1 \pm \sqrt{4a+1}\sqrt{3} \mathrm{i}}{2}$. So, multiply:

$g(z)=(z-1) \left ( z- \left ( \frac{-1 + \sqrt{4a+1}\sqrt{3} \mathrm{i}}{2} \right ) \right ) \left ( z- \left ( \frac{-1 - \sqrt{4a+1}\sqrt{3} \mathrm{i}}{2} \right ) \right )$

When all is said and done, this simplifies to

$g(z) = z^3 + 3az - (3a+1)$

And so on. I made it to n=8. Let me tell you, n=7 was a dirty job. I looked for ways to make things easier – for example, I wrote the points as $\cos(2\pi k/n)+\mathrm{i}\sqrt{4a+1}\sin(2\pi k/n)$ so that I could take advantage of some symmetry, cross-cancellation and trig identities, and for n=7 I found the polynomial that has $\cos(2\pi k/7)$ as roots, which then gave me some symmetric expressions in the $\cos(2\pi k/7)$s that showed up in the final product, without needing to actually calculate the value of each $\cos(2\pi k/7)$. But still. That case alone had to have taken me at least 2 hours. I messed up several times, thankfully in ways that contradicted each other. But I got my data:

$n$ $g(z)$
1 $z-1$
2 $z^2-1$
3 $z^3+3az-(3a+1)$
4 $z^4+4az^2-(4a+1)$
5 $z^5+5az^3+5a^2z-(5a^2+5a+1)$
6 $z^6+6az^4+9a^2z^2-(9a^2+6a+1)$
7 $z^7+7az^5+14a^2z^3+7a^3z-(7a^3+14a^2+7a+1)$
8 $z^8+8az^6+20a^2z^4+16a^3z^2-(16a^3+20a^2+8a+1)$

Clear patterns are emerging in the structure of these polynomials, what with how
a) the powers of $z$ are falling by 2 and of $a$ are rising by 1
b) the constant term is the negative of the sum of the coefficients of the other terms

Together, these mean we could really regard the whole thing as a sum of terms of the form

$\mathrm{coefficient}*a^k(z^{n-2k}-1)$

The last thing to do is figure out what’s going on with the coefficients. The lead coefficient is always 1, the next (provided it contains a $z$) is counting numbers, and the next (again, provided $z$ is involved) – the sequence 5, 9, 14, 20 – is increasing by counting numbers. This is an echo of the Pascal’s Triangle, so I looked for an expression for these numbers in terms of chooses. I found one: the $k+1$th coefficient of the $n$th polynomial (i.e. the coefficient of the $a^kz^{n-2k}$ term) seems to be

$\dbinom{n-k+1}{k} - \dbinom{n-k-1}{k-2}$

So, without further ado –

Conjecture:

* If you take the unit circle and place n evenly-spaced points along it, the first at (1,0)
* And you then scale everything vertically by a factor of $\sqrt{4a+1}$, where $a$ is any real number such that $\sqrt{4a+1}$ is real
* And you then regard each of these scaled points as a complex number,
* The monic polynomial $g(z)$ with these numbers as roots will be equal to

$\displaystyle\sum_{k=0}^{\left \lfloor (n-1)/2 \right \rfloor} \left [ \dbinom{n-k+1}{k} - \dbinom{n-k-1}{k-2} \right ] a^k (z^{n-2k} - 1)$

If this conjecture is correct, Japheth’s conjecture follows. (For those of you who like that sort of thing, how does it follow?) So proving this conjecture would settle all the outstanding questions (e.g. it would prove the Fibonacci pattern in the $\sqrt{4a+1}=\sqrt{5}$ case).

But I have no idea how to prove it. Why are the powers of $a$ showing up? How about the chooses? What’s going on here?

Thoughts?

(Darryl Young and Bowen Kerins, the writers of the PCMI problem set, are invited to give the rest of us hints!)

Advertisements