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 points and so on up to . Pick points , , , and so on up to . In this case we have blocking points at , , and so on by half-integers up to . Of course this solution doesn’t count because the first points lie on a line as do the points that follow, which violates the collinearity condition of the problem.

Here’s a picture of that scenario when :

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 points were on two lines, which is disallowed. Now the two lines here, and , form a degenerate conic . 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 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.

The line itself is . Which has the obvious -intercept . Now we need to pick a lot of and values to get repeated products. Place points at , , , , and so on above the negative powers of two. Place points at , , , , and so on above the positive powers of two. The blocking points are then at , , , , and so on up the -axis by powers of two. Presto!

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 . For , mark the intersection of the lines by . Then are collinear. (The reason for the strange indexing will be clear in a moment.)

**Pascal’s Mystic Hexagon, version B:** Consider any pentagon inscribed in a conic , with vertices marked . Choose any line through , and define and . Then the intersection is the sixth point of a hexagon inscribed in .

The following solution uses version B.

*Solution by Todd and Vishal*: For the sake of explicitness, let the conic be a circle and let the line (segment) be the diameter along . Choose two points on above and a point on below . The remaining points are determined recursively by a zig-zag procedure, where at each stage is the intersection , where , where , and . We will show the blocking condition is satisfied: for all , the point is on the line .

To get started, notice that the blocking condition is trivially satisfied up to the point where we construct . Mystic Hexagon B ensures that , as defined above, is blocked from by and from by . Then define as above. So far the blocking condition is satisfied.

Suppose the blocking condition is satisfied for the points . Define , as above. Then Mystic Hexagon B, applied to the pentagon consisting of points , shows that is blocked from by and from by .

This shows that could have been defined to be . Then Mystic Hexagon B, applied to the pentagon , shows that is blocked from by and from by . This shows could have been defined to be .

And so on up the inductive ladder: for , defining , Hexagon B applied to the pentagon shows that could have been defined to be . This shows the blocking condition is satisfied for , . We block from by defining as above, to extend up to .

Then, as prescribed above, we define , and repeat the preceding argument mutatis mutandis (interchanging ‘s and ‘s), to obtain the blocking conditions up to , . This completes the proof.

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 , *any* secant line , and any three initial points on to get started (with ‘s on one side of and 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 of any degree 3 polynomial in two variables. (We should actually be doing this as projective geometry, so I ought to write where is homogeneous of degree 3, but I think I’ll skip that.) For example, the union of three distinct lines is a cubic where is a product of three degree 1 polynomials. What is the dimension of the space of planar cubics? A cubic polynomial ,

has 10 coefficients. But the equation is equivalent to the equation for any nonzero scalar ; 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 ? The condition gives one linear equation on the coefficients , 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

we see three cubics passing through the 8 points , namely:

- where the conic 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 used respectively to define , and above, hence we would get

for some scalars . Thus, if a ninth point is in and , so that , then . Thus lies in as well, and if isn’t on , it must be on the line . Thus, “generically” we expect 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 planar curve and a degree planar curve either intersect in 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 curve and a degree curve either have a curve component in common, or they intersect in *at most* points. In particular, in the notation above, the cubics and intersect in 9 points, 6 of which are on the conic . Pick a seventh point on , away from those six, and let and . Then we see that the locus of the degree 3 polynomial

intersects the degree 2 conic in at least 7 points (namely, and ), greater than the expected number , which is impossible unless the loci of and have a component in common. But the conic has just one component — itself — so one can conclude that its defining degree 2 polynomial (I’ll call it ) must divide . Then we have

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

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 where is a polynomial of degree 3, the coefficients of 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 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 carries a continuous (abelian) group structure, if we think of it as the set of complex numbers of norm 1, where the group operation is complex multiplication. A torus 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 (in the complex plane , or rather the projective complex plane ) 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 are points on , then

if are collinear. [To be precise, one must select a point 0 on to serve as identity, and this point must be one of the nine inflection points of . When and coincide (are “infinitesimally close”), the line through and is taken to be tangent to ; when 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 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 which are solutions to a real cubic equation , then there is also a third real solution .) 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 “red” points (instead of my ), “blue” points (instead of my ), and “blocking” points which play the role of my .) The addition referred to is the addition law on an elliptic curve. I’ve taken the liberty of paraphrasing a bit.

“Choose points on the real points of an elliptic curve such that is in-between and . Then set

- red points: ,
- blue points: ,
- blocking points: ,

where is a real point on the elliptic curve very close to the identity. The pair , is blocked by , 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 . The singular points of its projective completion are at and the point where the -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 -axis, negative -axis.

We can maybe guess that since implies collinear, that the two pieces of the -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 , but don’t jump to conclusions how this works!). If so, then we notice that if and lie on the parabola, then the line between them intersects the -axis at a point , 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 , with the linear part identified somehow with the subgroup , and the parabolic part with .

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

so that the identity element on the cubic is , and the inverse of is . The remainder of the abelian group structure on the cubic is defined as follows:

Undoubtedly this group law looks a bit strange! So let’s do a spot check. Suppose , , and are collinear. Then it is easily checked that , and each of the two equations

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 as a red point, as a blue point, and as blocking point. Take a point “sufficiently close” to the identity, say . Then

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

## 18 comments

Comments feed for this article

July 22, 2009 at 4:38 pm

John ArmstrongThe first of your pictures doesn’t seem to show up.

July 22, 2009 at 4:44 pm

Todd TrimbleThat’s strange and annoying, because I can see it fine, and I think Vishal said he saw it too. Will try to fix. (I guess you mean the Pappus configuration.)

July 22, 2009 at 6:36 pm

John ArmstrongNow it’s there.

July 23, 2009 at 1:49 am

Rick ReganJust a nit regarding your usage of terms. I wouldn’t call -8, for example, a “negative power of two” — it’s a power of two that’s negative (I wish I knew a term for it). As for your usage of “positive powers of two,” I think you mean “nonnegative powers of two,” since you are including 2^0.

I’ve written several articles about the naming and definition of the powers of two (for example, this one: http://www.exploringbinary.com/the-powers-of-two/ ). I would love any feedback you have.

July 23, 2009 at 1:56 am

Qiaochu YuanI wish I’d thought more about this problem! Noam’s solution is extremely nice.

July 23, 2009 at 6:05 am

Todd TrimbleRick, I agree, but the nit you pick refers to something in an email from one mathematician to another another, where no effort was made to tidy up mathematical English. I liked the rough informality of the original and left that in; both John and I know the point you’re making. (What neither of us knew when he wrote that email is that it would eventually be published by me.)

While I’m on the topic, I should say I’m grateful to everyone mentioned in the post for giving me permission to quote their email.

Qiaochu, the elliptic curve solution is indeed awesome; that one was due to Roger Alperin, Joe Buhler, and Adam Chalcraft. Noam’s solution (which I didn’t give) was given in email to Joe Buhler as follows: “My construction is elementary: start from the vertices of a regular (r+b)-gon, and put black points on the r+b points at infinity that contain each line joining two of the vertices (these lines fall into r+b parallel groups). Then find a line L through one of the black points that separates the vertices into r points on one side and b on the other; color them red and blue respectively, and apply a projective transformation that makes L the line at infinity, and discard the one black point that remains at infinity. Now the black points are collinear but the red and blue ones aren’t.”

Nice as the elliptic curve solution is, I wouldn’t consider it elementary. I do think it’s cool how these things can be seen on a variety of levels.

July 25, 2009 at 8:24 pm

Todd TrimbleThe exercise I gave at the end (was it too hard? too obvious to merit any comment?) sort of reminds me of another fun thing to work out.

Many of you will have seen the simple form of children’s art where an array of strings arranged in a regular pattern outlines a curve. For example, if you tie a string between each of the following pairs of points: (10, 0) and (0, 0), (9, 0) and (0, 1), (8, 0) and (0, 2), etc., you get the outline of a nice curve symmetric about the line y = x. More mathematically, the x-parametrized collection of lines between (x, 0) and (0, 10-x) envelopes a certain curve. What kind of curve is it?

July 26, 2009 at 10:45 pm

Vishal LamaTodd,

What kind of curve is it?It’s a curve that’s

almosta parabola but not quite(!), assuming I didn’t make any terrible mistakes in my computations.July 26, 2009 at 11:32 pm

Todd TrimbleI’d be very interested in following up on that! But let’s see if anyone else wants to say anything about it first.

July 27, 2009 at 12:43 am

Vishal LamaOk, I am now pretty sure I am wrong! I will come back to that question, later.

July 27, 2009 at 1:06 am

Vishal LamaOk, I was indeed wrong. The curve is a

parabola, after all!July 27, 2009 at 4:25 pm

Todd TrimbleSorry, Vishal, I just wanted to see if someone else was going to add anything. Go ahead: you were saying?

July 27, 2009 at 9:21 pm

Todd TrimbleOkay, Vishal outlined his solution to me privately, and yes, it is indeed a parabola as he was saying. So what was I on about, anyway, when I proposed that exercise?

Two words: projective dual.

Let me explain. There are two ways of thinking about a planar curve: the continuum of points sitting on it, and the continuum of lines tangent to it. The usual representation is the first one, where we describe the locus of points on in some way, and then use this to derive the nature of the tangent lines. You know the drill: take two points on the curve, consider the secant line which joins them, and then let the points approach each other. In the limit we get the tangent line.

In the problem I posed, we have information on the tangent lines instead (these are the lines connecting to ), and we want to get information on the points. So, we dualize! That is, we swap the roles of line and point, and swap the operations of meet and join, and… you probably already get the idea.

Thus, given two (tangent) lines to :

we take their meet or intersection to obtain a “secant point” to the curve, and then watch what happens as the tangent lines approach one another (let ). The limit of the secant points is a point on the curve where the two coinciding tangents graze by.

After some high-school algebra in computing the intersection of the lines and taking the limit, you get a parametric form for the curve in a nice neat form:

and then, staring at this, you see that is quadratic in . This means the curve is a parabola in the -plane [in standard upright position]. The curve we have is a 45 degree rotation of that according to the linear transformation , so the curve is an oblique or slanted parabola.

Why am I mentioning all this? I don’t know — I was just reminded of the fact that the geometry of conics is closely connected with projective duality, in the following beautiful way. Take a conic in the plane (really, projective plane), let’s say an ellipse. Take a secant line which intersects in two points. Then, the tangents to those points intersect in a “secant point” exterior to the curve. This sets up at least a partial function that takes lines which pass through the interior of to points in the exterior, and this process is reversible. This is called “taking the projective dual”.

This process doesn’t seem to work if the line doesn’t intersect (i.e., is exterior to ). Algebraically, this is a consequence of our working over the reals: not all quadratic equations have solutions. The process would work fine if we worked over the complex numbers instead. (Special case: where instead of a secant line we have a tangent line. There the projective dual is the point at which it is tangent!) Thus, over the complex numbers, the process above gives full projective duality, and by that I mean that there’s a theorem: the dual (w.r.t. ) of the line joining two points is the meet of the lines dual to the two points. So duality w.r.t. a conic swaps meets and joins.

But now we can cleverly slip in full duality over the reals through a back door. If for example we have a line exterior to , mark two points on . These are exterior to . Their projective duals are lines passing through the interior of ; mark their intersection. Then define that intersection to be the dual, ! This is well-defined, i.e., independent of the points chosen on to get at the interior lines.

Ultimately, geometric projective duality in the plane boils down to algebraic linear duality on a three-dimensional space, induced by a nondegenerate bilinear form whose quadratic form defines a conic in the projective plane. The algebraic duality interchanges lines and planes in 3-space.

July 28, 2009 at 12:04 am

Vishal LamaTodd,

I am really glad you showed this. In fact, the method you just showed had been my first line of thought/attack when pondering over the problem. The idea was to write down the equation of the family of straight lines (tangents to the curve) in terms of the parameter , and then find the intersection of two lines corresponding to parameters and by taking the limit , thus obtaining the coordinates of the points on the curve. After that, I got , where in the problem you gave.

But, then, I got thrown off (which in hindsight was sort of stupid!) when I didn’t keep in mind that the parabola was symmetric about the line . (I know, I know, it was bad!) And, then I used the more standard technique to obtain the same answer(!) but in a form that looked quite right.

Anyway, thanks so much for bringing up the topic of projective dual!

July 28, 2009 at 2:46 pm

Todd TrimbleYou’re welcome!

Since the little problem at the end of my post hasn’t received any response, I’ll go ahead and give my solution. It’s very simple: mark four other points on the circle; label them , and label the given point with

twolabels: and . Thus, we are thinking of the five points on the conic as really six points of an inscribed hexagon, with the given point considered as a double point (or two points “infinitesimally close” to one another). The line we are trying to construct, the tangent line at the given point, can be thought of as the line between the two points infinitesimally close to one another.Undeterred, now begin drawing the mystic hexagon configuration. That is (using notation as in the post), construct the intersections

and we would construct , except that we don’t know where that last line is: that’s the tangent line we’re trying to construct. But that’s okay, because we are assured by the mystic hexagon theorem (version A) that wherever is, it’s on the line through and , which we have. So: we may define

and then the tangent line through is the line joining to . Try it!!

Notice that this works for any conic; we don’t need a circle particularly.

August 14, 2009 at 10:28 am

Math World | Solution to POW-13: Highly coincidental![…] Read the rest here: Solution to POW-13: Highly coincidental! […]

October 18, 2011 at 4:25 pm

ThomasTT: Conc. the Strugatsky-novel, see the email.

July 18, 2014 at 8:11 am

David SpeyerYou might want to look at Green and Tao: On sets defining few ordinary lines http://arxiv.org/abs/1208.4714 . Here is a weak statement of their result: Fix a constant c>0. Consider arrangements of n points in the plane such that, out of the lines they define, all but cn pass through another point. Then all but d of the points lie on a cubic (where d depends on c), and are arranged in the manner of your x_i, y_j and z_k.