22 | July | 2009 | Todd and Vishal's blog

Huh — no solutions to POW-13 came in! I guess I was surprised by that.

Ah well, that’s okay. The problem wasn’t exactly trivial; there are some fairly deep and interesting things going on in that problem that I’d like to share now. First off, let me say that the problem comes from The Unapologetic Mathematician, the blog written by John Armstrong, who posted the problem back in March this year. He in turn had gotten the problem from Noam Elkies, who kindly responded to some email I wrote and had some pretty insightful things to say.

In lieu of a reader solution, I’ll give John’s solution first, and then mine, and then touch on some of the things Noam related in his emails. But before we do so, let me paraphrase what John wrote at the end of his post:

Here’s a non-example. Pick $m$ points $(1, 0), (2, 0), (3, 0)$ and so on up to $(m, 0)$ . Pick $n$ points $(1, 1)$ , $(2, 1)$ , $(3, 1)$ , and so on up to $(n, 1)$ . In this case we have $m+n-1$ blocking points at $(1, \frac1{2})$ , $(\frac{3}{2}, \frac1{2})$ , and so on by half-integers up to $(\frac{m+n}{2}, \frac1{2})$ . Of course this solution doesn’t count because the first $m$ points lie on a line as do the $n$ points that follow, which violates the collinearity condition of the problem.

Here’s a picture of that scenario when $m = n = 3$ :

pappusa

Does this configuration remind you of anything? Did somebody say “Pappus’s theorem“? Good. Hold that thought please.

Okay, in the non-example the first $m+n$ points were on two lines, which is disallowed. Now the two lines here, $y = 0$ and $y = 1$ , form a degenerate conic $y^2 - y = 0$ . Thinking in good algebraic geometry fashion, perhaps we can modify the non-solution by replacing the degenerate conic by an honest (smooth) nondegenerate conic, like an ellipse or something, so that at most two of the $m+n$ points are on any given line. This should put one in the mood for our first solution.

John Armstrong writes: Basically, I took the non-example and imagined bending back the two lines to satisfy the collinearity (pair-of-lines = degenerate conic, so non-example is degenerate example). The obvious pair of curves to use is the two branches of a hyperbola. But hyperbolas can be hard to work with, so I decided to do a projective transformation to turn it into a parabola.

So let’s consider points on a parabola. The points $(-i, i^2)$ and $(j, j^2)$ are connected by a line of slope

$\displaystyle \frac{j^2 - i^2}{j + i} = j - i$

The line itself is $y = (j-i)x + i j$ . Which has the obvious $y$ -intercept $(0, i j)$ . Now we need to pick a lot of $i$ and $j$ values to get repeated products. Place $m$ points at $(-1, 1)$ , $(-2, 4)$ , $(-4, 16)$ , $(-8, 64)$ , and so on above the negative powers of two. Place $n$ points at $(1, 1)$ , $(2, 4)$ , $(4, 16)$ , $(8, 64)$ , and so on above the positive powers of two. The blocking points are then at $(0, 1)$ , $(0, 2)$ , $(0, 4)$ , $(0, 8)$ , and so on up the $y$ -axis by powers of two. Presto! $\Box$

Very nice. My own solution was less explicit in the sense that I didn’t actually write down coordinates of points, but gave instead a general recipe which relies instead on the geometry of conics, in fact on a generalization of Pappus’s theorem known to me as “Pascal’s mystic hexagon“. I first learned about this from a wonderful book:

C. Herbert Clemens, A Scrapbook of Complex Curve Theory (2nd Edition), Graduate Studies in Mathematics 55, AMS (2002).

Pascal’s Mystic Hexagon, version A: Consider any hexagon inscribed in a conic, with vertices marked $x_1, x_2, x_3, y_1, y_2, y_3$ . For $i \neq j$ , mark the intersection of the lines $\overline{x_i y_j} \cap \overline{x_j y_i}$ by $z_{i+j-1}$ . Then $z_2, z_3, z_4$ are collinear. (The reason for the strange indexing will be clear in a moment.)

mystic1

Pascal’s Mystic Hexagon, version B: Consider any pentagon inscribed in a conic $C$ , with vertices marked $x_1, x_2, x_3, y_1, y_2$ . Choose any line $L$ through $z_2 = \overline{x_1 y_2} \cap \overline{y_1 x_2}$ , and define $z_3 = L \cap \overline{y_1 x_3}$ and $z_4 = L \cap \overline{y_2 x_3}$ . Then the intersection $y_3 := \overline{x_1 z_3} \cap \overline{x_2 z_4}$ is the sixth point of a hexagon inscribed in $C$ .

The following solution uses version B.

Solution by Todd and Vishal: For the sake of explicitness, let the conic $C$ be a circle $x^2 + y^2 = 1$ and let the line (segment) $L$ be the diameter along $y = 0$ . Choose two points $x_1, x_2$ on $C$ above $L$ and a point $y_1$ on $C$ below $L$ . The remaining points are determined recursively by a zig-zag procedure, where at each stage $x_{n+1}$ is the intersection $C \cap \overline{y_1 z_{n+1}}$ , where $z_{2n} = L \cap \overline{x_{n+1} y_n}$ , where $y_{n+1} = C \cap \overline{x_1 z_{n+1}}$ , and $z_{2n+1} = L \cap \overline{x_{n+1} y_{n+1}}$ . We will show the blocking condition is satisfied: for all $i, j$ , the point $z_{i+j-1}$ is on the line $\overline{x_i y_j}$ .

To get started, notice that the blocking condition is trivially satisfied up to the point where we construct $z_1, z_2, y_2, z_3, x_3, z_4$ . Mystic Hexagon B ensures that $y_3$ , as defined above, is blocked from $x_1$ by $z_3$ and from $x_2$ by $z_4$ . Then define $z_5$ as above. So far the blocking condition is satisfied.

mystic2a

Suppose the blocking condition is satisfied for the points $x_1, \ldots, x_n, y_1, \ldots, y_n, z_1, \ldots, z_{2n-1}$ . Define $x_{n+1} = C \cap \overline{y_1 z_{n+1}}$ , as above. Then Mystic Hexagon B, applied to the pentagon consisting of points $y_1, y_2, y_3, x_{n-1}, x_n$ , shows that $x_{n+1}$ is blocked from $y_1$ by $z_{n+1}$ and from $y_2$ by $z_{n+2}$ .

This shows that $x_{n+1}$ could have been defined to be $C \cap \overline{y_2 z_{n+2}}$ . Then Mystic Hexagon B, applied to the pentagon $y_2, y_3, y_4, x_{n-1}, x_n$ , shows that $x_{n+1}$ is blocked from $y_2$ by $z_{n+2}$ and from $y_3$ by $z_{n+3}$ . This shows $x_{n+1}$ could have been defined to be $C \cap \overline{y_3 z_{n+3}}$ .

And so on up the inductive ladder: for $2 \leq i \leq n-1$ , defining $x_{n+1} = C \cap \overline{y_{i-1} z_{n+i-1}}$ , Hexagon B applied to the pentagon $y_{i-1}, y_i, y_{i+1}, x_{n-1}, x_n$ shows that $x_{n+1}$ could have been defined to be $C \cap \overline{y_i z_{n+i}}$ . This shows the blocking condition is satisfied for $1 \leq i \leq n+1$ , $1 \leq j \leq n-1$ . We block $x_{n+1}$ from $y_n$ by defining $z_{2n}$ as above, to extend up to $j = n$ .

Then, as prescribed above, we define $y_{n+1} = C \cap \overline{x_1 z_{n+1}}$ , and repeat the preceding argument mutatis mutandis (interchanging $x$ ‘s and $y$ ‘s), to obtain the blocking conditions up to $1 \leq i \leq n+1$ , $1 \leq j \leq n+1$ . This completes the proof. $\Box$

What this argument shows (with Hexagon B doing all the heavy lifting) is that no cleverness whatsoever is required to construct the desired points: starting with any nondegenerate conic $C$ , any secant line $L$ , and any three initial points $x_1, x_2, y_1$ on $C$ to get started (with $x_1, x_2$ ‘s on one side of $L$ and $y_1$ on the other), the whole construction is completely forced and works no matter what!

Which may lead one to ask: what is behind this “miracle” called Pascal’s Mystic Hexagon? Actually, not that much! Let me give a seat-of-the-pants argument for why one might expect it to hold, and then give a somewhat more respectable argument.

Define a planar cubic to be the locus $P(x, y) = 0$ of any degree 3 polynomial $P$ in two variables. (We should actually be doing this as projective geometry, so I ought to write $P(x, y, z) = 0$ where $P$ is homogeneous of degree 3, but I think I’ll skip that.) For example, the union of three distinct lines is a cubic where $P$ is a product of three degree 1 polynomials. What is the dimension of the space of planar cubics? A cubic polynomial $P(x, y)$ ,

$a_0 + a_1 x + a_2 y + a_3 x^2 + a_4 x y + a_5 y^2 + a_6 x^3 + a_7 x^2 y + a_8 x y^2 + a_9 y^3,$

has 10 coefficients. But the equation $P(x, y) = 0$ is equivalent to the equation $\lambda P(x, y) = 0$ for any nonzero scalar $\lambda$ ; modding out by scalars, there are 9 degrees of freedom in the space of cubics. What is the dimension of the space of cubics passing through a given point $(x, y) = (a, b)$ ? The condition $P(a, b) = 0$ gives one linear equation on the coefficients $a_0, \ldots, a_9$ , so we cut down a degree of freedom, and the dimension would be 8. Similarly, if we ask for the dimension of cubics passing through 8 given points, we get a system of eight linear equations, and we cut down by eight degrees of freedom: in general, the space of cubics through 8 points is “expected” to be (is “almost always”) 1-dimensional, in fact, a (projective) line.

In the configuration for Pascal’s Mystic Hexagon, version A

mystic1

we see three cubics passing through the 8 points $x_1, x_2, x_3, y_1, y_2, y_3, z_2, z_3$ , namely:

$A = \overline{x_1 y_2} \cup \overline{x_2 y_3} \cup \overline{x_3 y_1}$
$B = \overline{x_2 y_1} \cup \overline{x_3 y_2} \cup \overline{x_1 y_3}$
$C \cup L$ where the conic $C$ is defined by a degree 2 polynomial

Since we expect that the space of cubics through these eight points is a line, we should have a linear relationship between the cubic polynomials $P, Q, R$ used respectively to define $A, B$ , and $C \cup L$ above, hence we would get

$\lambda P(x, y) + \mu Q(x, y) = R(x, y)$

for some scalars $\lambda, \mu$ . Thus, if a ninth point $z_4 = (a, b)$ is in $A$ and $B$ , so that $P(a, b) = Q(a, b) = 0$ , then $R(a, b) = 0$ . Thus $z_4$ lies in $C \cup L$ as well, and if $z_4$ isn’t on $C$ , it must be on the line $L$ . Thus, “generically” we expect $z_2, z_3, z_4$ to be collinear, whence Hexagon A.

This rough argument isn’t too far removed from a slightly more rigorous one. There’s a general result in projective algebraic geometry called Bézout’s theorem, which says that a degree $m$ planar curve and a degree $n$ planar curve either intersect in $m n$ points (if you count them right, “with multiplicity”) or they have a whole curve component in common. (Fine print: to make this generally true, you have to work in the projective plane, and you have to work over an algebraically closed field.) A much weaker result which removes all the fine print is that a degree $m$ curve and a degree $n$ curve either have a curve component in common, or they intersect in at most $m n$ points. In particular, in the notation above, the cubics $A$ and $B$ intersect in 9 points, 6 of which are on the conic $C$ . Pick a seventh point $(a, b)$ on $C$ , away from those six, and let $\lambda = Q(a, b)$ and $\mu = -P(a, b)$ . Then we see that the locus of the degree 3 polynomial

$T(x, y) = \lambda P(x, y) + \mu Q(a, b) = 0$

intersects the degree 2 conic $C$ in at least 7 points (namely, $x_1, x_2, x_3, y_1, y_2, y_3$ and $(a, b)$ ), greater than the expected number $3 \cdot 2$ , which is impossible unless the loci of $T$ and $C$ have a component in common. But the conic $C$ has just one component — itself — so one can conclude that its defining degree 2 polynomial (I’ll call it $C(x, y)$ ) must divide $T$ . Then we have

$T(x, y) = \lambda P(x, y) + \mu Q(x, y) = C(x, y)L(x, y)$

for some degree 1 polynomial $L$ , so the last three of the nine points of intersection $A \cap B$ , which are zeroes of $P$ and $Q$ , must be zeroes of the linear polynomial $L$ , and hence are collinear. Thus we obtain Pascal’s Mystic Hexagon, version A. $\Box$

It’s clear then that what makes the Mystic Hexagon tick has something to do with the geometry of cubic curves. With that in mind, I’m now going to kick the discussion up a notch, and relate a third rather more sophisticated construction on cubics which basically subsumes the first two constructions. It has to do with so-called “elliptic curves“.

Officially, an elliptic curve is a smooth projective (irreducible) cubic “curve” over the complex numbers. I put “curve” in quotes because while it is defined by an equation $P(x, y) = 0$ where $P$ is a polynomial of degree 3, the coefficients of $P$ are complex numbers as are the solutions to this equation. We say “curve” in the sense that locally it is like a “line”, but this is the complex line $\mathbb{C}$ we’re talking about, so from our real number perspective it is two-dimensional — it actually looks more like a surface. Indeed, an elliptic curve is an example of a Riemann surface. It would take me way too far afield to give explanations, but when you study these things, you find that elliptic curves are Riemann surfaces of genus 1. In more down-to-earth terms, this means they are tori (toruses), or doughnut-shaped as surfaces. Topologically, such tori or doughnuts are cartesian products of two circles.

Now a circle or 1-dimensional sphere $S^1$ carries a continuous (abelian) group structure, if we think of it as the set of complex numbers $\{z: |z| = 1\}$ of norm 1, where the group operation is complex multiplication. A torus $S^1 \times S^1$ also carries a group structure, obtained by multiplying in each of the two components. Thus, given what we have said, an elliptic curve also carries a continuous group structure. But it’s actually much better than that: one can define a group structure on a smooth complex cubic $C$ (in the complex plane $\mathbb{C}^2$ , or rather the projective complex plane $P^2(\mathbb{C})$ ) not just by continuous operations, but by polynomially defined operations, and the definition of the group law is just incredibly elegant as a piece of geometry. Writing the group multiplication as addition, it says that if $a, b, c$ are points on $C$ , then

$a + b = -c \qquad (a + b + c = 0)$

if $a, b, c$ are collinear. [To be precise, one must select a point 0 on $C$ to serve as identity, and this point must be one of the nine inflection points of $C$ . When $a$ and $b$ coincide (are “infinitesimally close”), the line through $a$ and $b$ is taken to be tangent to $C$ ; when $a, b, c$ coincide, this is a line of inflection.]

This is rather an interesting thing to prove, that this prescription actually satisfies the axioms for an abelian group. The hardest part is proving associativity, but this turns out to be not unlike what we did for Pascal’s Mystic Hexagon: basically it’s an application of Bézout’s theorem again. (In algebraic geometry texts, such as Hartshorne’s famous book, the discussion of this point can be far more sophisticated, largely because one can and does define elliptic curves as certain abstract 1-dimensional varieties or schemes which have no presupposed extrinsic embeddings as cubic curves in the plane, and there the goal is to understand the operations intrinsically.)

In the special case where $C$ is defined by a cubic polynomial with real coefficients, we can look at the locus of real solutions (or “real points”), and it turns out that this prescription for the group law still works on the real locus, in particular is still well-defined. (Basically for the same reason that if you have two real numbers $a, b$ which are solutions to a real cubic equation $p(x) = 0$ , then there is also a third real solution $c$ .) There is still an identity element, which will be an inflection point of the cubic.

Okay, here is a third solution to the problem, lifted from one of Noam Elkies’ emails. (The original formulation of the problem spoke in terms of $r$ “red” points (instead of my $x_1, \ldots, x_m$ ), $b$ “blue” points (instead of my $y_1, \ldots, y_n$ ), and “blocking” points which play the role of my $z_1, \ldots, z_{m+n-1}$ .) The addition referred to is the addition law on an elliptic curve. I’ve taken the liberty of paraphrasing a bit.

“Choose points $B, R$ on the real points of an elliptic curve such that $-(B+R)$ is in-between $B$ and $R$ . Then set

red points: $R + i P$ , $0 \leq i \leq r-1$
blue points: $B + j P$ , $1 \leq j \leq b-1$
blocking points: $-(R+B+kP)$ , $0 \leq k \leq r+b-2$

where $P$ is a real point on the elliptic curve very close to the identity. The pair $R + i P$ , $B + j P$ is blocked by $-(R + B + (i + j)P$ , because these three points are collinear, and the smallness of P guarantees that the blocking point is actually between the red point and blue point, by continuity.”

Well, well. That’s awfully elegant. (According to Noam’s email, it came out of a three-way conversation between Roger Alperin, Joe Buhler, and Adam Chalcraft. Edit: Joe Buhler informs me in email that Joel Rosenberg’s name should be added. More at the end of this post.) Noam had given his own slick solution where again the red and blue points sit on a conic and the blocking points lie on a line not tangent to the conic, and he observed that his configuration was a degenerate cubic, leading him to surmise that his example could in a sense be seen as a special case of theirs.

How’s that? The last solution took place on a smooth (nondegenerate) cubic, so the degenerate cubic = conic+line examples could not, literally speaking, be special cases. Can the degenerate examples be seen in terms of algebraic group structures based on collinearity?

The answer is: yes! As you slide around in the space of planar cubics, nondegenerate cubics (the generic or typical case) can converge to cubics which are degenerate in varying degrees (including the case of three lines, or even a triple line), but the group laws on nondegenerate cubics based on collinearity converge to group laws, even in degenerate cases! (I hadn’t realized that.) You just have to be careful and throw away the singular points of the degenerate cubic, but otherwise you can basically still use the definition of the group law based on collineation, although it gets a little tricky saying exactly how you’re supposed to add points on a line component, such as the line of conic+line.

So let me give an example of how it works. It seems convenient for this purpose to use John Armstrong’s model which is based on the parabola+line, specifically the locus of $(y - x^2)x = 0$ . The singular points of its projective completion are at $(0, 0)$ and the point where the $y$ -axis meets the line at infinity. After throwing those away, what remains is a disjoint union of four pieces: right half of parabola, left half of parabola, positive $y$ -axis, negative $y$ -axis.

We can maybe guess that since $a + b + c = 0$ implies $a, b, c$ collinear, that the two pieces of the $y$ -axis form a subgroup for the group law we are after (also, these two pieces together should suggest the two halves of the multiplicative group of nonzero reals $\mathbb{R}^*$ , but don’t jump to conclusions how this works!). If so, then we notice that if $a$ and $b$ lie on the parabola, then the line between them intersects the $y$ -axis at a point $c$ , so then the parabolic part would not be closed under multiplication.

One is then led to consider that the group structure of this cubic overall is isomorphic to the group $\{-1, 1\} \times \mathbb{R}^*$ , with the linear part identified somehow with the subgroup $\{1\} \times \mathbb{R}^*$ , and the parabolic part with $\{-1\} \times \mathbb{R}^*$ .

I claim that the abelian group structure on the punctured $y$ -axis should be defined by

$(0, x) + (0, y) := (0, - x y)$

so that the identity element on the cubic is $(0, -1)$ , and the inverse of $(0, x)$ is $(0, 1/x)$ . The remainder of the abelian group structure on the cubic is defined as follows:

$(s, s^2) + (t, t^2) := (0, -1/(s t))$

$(0, x) + (s, s^2) := (-s/x, s^2/x^2)$

Undoubtedly this group law looks a bit strange! So let’s do a spot check. Suppose $(0, a)$ , $(s, s^2)$ , and $(t, t^2)$ are collinear. Then it is easily checked that $a = -s t$ , and each of the two equations

$(0, a) + (s, s^2) = (t^{-1}, t^{-2}) = -(t, t^2)$

$(s, s^2) + (t, t^2) = (0, 1/a) = -(0, a)$

is correct according to the group law, so the three collinear points do add to the identity and everything checks out.

All right, let’s retrieve John’s example as a special case. Take $R = (1, 1)$ as a red point, $B = (-1, 1)$ as a blue point, and $-(B + R) = (0, 1)$ as blocking point. Take a point $P$ “sufficiently close” to the identity, say $(0, -1/2)$ . Then

$R + i P = (1, 1) + (0, -1/2^i) = (2^i, 2^{2i})$

$B + j P = (-1, 1) + (0, -1/2^j) = (-2^j, 2^{2j})$

which was John’s solution.

Another long post from yours truly. I was sorry no solutions came from our readers, but if you’d like another problem to chew on, here’s a really neat one I saw just the other day. Feel free to discuss in comments!

Exercise: Given a point on a circle, show how to draw a tangent to the point using ruler only, no compass. Hint: use a mystic hexagon where two of the points are “infinitesimally close”.

Added July 25: As edited in above, Joel Rosenberg also had a hand in the elliptic curves solution, playing an instrumental role in establishing some of the conjectures, such as that $r + b - 1$ is the minimal number of blocking points under certain assumptions, and (what is very nice) that the elliptic curves solution is the most general solution under certain assumptions. I thank Joe Buhler for transmitting this information.

	Strong equidistribut… on Platonic Solids and Euler…
	m.s.mohamed ansari on The 54th Carnival of Math…
	Convictions ·… on Continued fraction for e
	Wayne J. Mann on Solution to POW-12: A graph co…
	erneststephen on The 54th Carnival of Math…
	anhtraisg on p^q + q^p is prime
	prof dr drd horia or… on My first post
	prof drd horia orasa… on My first post
	prof dr mircea orasa… on Inequality with log
	notedscholar on Self-referential Paradoxes, In…
	prof dr mircea orasa… on Inequality with log
	prof dr mircea orasa… on Inequality with log
	prof dr mircea orasa… on 2010 in review
	kenji on Basic category theory, I
	prof dr mircea orasa… on Solution to POW-10: Another ha…

M	T	W	T	F	S	S
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Daily Archive

Solution to POW-13: Highly coincidental!

Our other blog

Visitors to this blog

Blog Stats

Wikio Ranking

Current Online Readers

Recent Comments

Top Posts

Archives

Categories

Blogroll

chess

Computers and Technology

Elementary Math Problem Solving

Fun, Humor

Higher Mathematics

Math Education

Non-technical

Opinions

People in Computer Science

People in mathematics

Philosophy & Logic

Physics

Politics, News

Sciences

Useful general links

Useful Math Links

Tag Cloud

Admin/Users Login

Pages