Todd and Vishal’s blog

Solution to POW-13: Highly coincidental!

July 22, 2009 in Algebraic Geometry, Problem of the Week (POW) | Tags: elliptic curves, pascal's mystic hexagon | by Todd Trimble | 16 comments

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.

The Character of Physical Law

July 18, 2009 in Physics | Tags: character of physical law, cornell, messenger series, Richard P. Feynman, video lectures | by Vishal Lama | 2 comments

There is quite a buzz on the physics (and also math) blogospheres over the release of seven videotaped lectures, which were delivered by Richard P. Feynman as part of Cornell University’s Messenger Lecture Series of November 1964. The videos have been released by Microsoft Research with quite a few enhancements, though, I believe, they have been around on YouTube for quite some time.

I watched the first two video lectures, titled ‘Lecture 1: The Law of Gravitation – An Example of Physical Law‘ and ‘Lecture 2: The Relation of Mathematics and Physics‘. It goes without saying that they are spell-binding and brilliant! Of course, the textbook ‘The Feymnan Lectures on Physics‘ (which was followed later by a problem-solving supplement that I highly recommend) is such a joy to read, but if you wish to learn physics “face to face” from the master, then I exhort, nay implore, you to watch those video lectures.

(I came to know about the existence of the videos released by the Microsoft Research group from Terence Tao.)

POW-13: Highly coincidental!

July 10, 2009 in Problem of the Week (POW) | Tags: collinearity, linear coincidence | by Todd Trimble | 8 comments

It’s been an awfully long time since I’ve posted anything; time to finally break the silence.

This problem appeared elsewhere on the internet some months ago; some of you may have already seen it. I don’t want to say right away where I saw it, because there was some commentary which included some rough hints which I don’t want to give, but I’ll be sure to give credit when the solution is published. I’ll bet some of you will be able to find a solution, and will agree it’s quite cute. Here it is:

Given integers $m, n \geq 1$ , show that it is possible to construct a set of $m + n$ points in the plane, let’s say $x_1, \ldots, x_m, y_1, \ldots, y_n$ , so that no three points of the set are collinear, and for which there exist points $z_1, z_2, \ldots, z_{m+n-1}$ , all lying on a straight line, and arranged so that on the line between any $x_i$ and any $y_j$ , some $z_k$ lies between them.

So no $x_i$ can “see” any $y_j$ , because there’s always some $z_k$ blocking the view. As the proposer observed, the problem would be easy if we had $m n$ $z$ ’s to play with, one for each pair $(x_i, y_j)$ . But here there are only $m+ n-1$ $z$ ’s, so some of them will have to do more than their fair share, blocking the view between quite a few $(x, y)$ -pairs simultaneously. Thus, you have to arrange the $x$ ’s and $y$ ’s so that a lot of the lines between them will be coincident at a point $z$ , and subject to the constraint I italicized above.

Please submit solutions to topological[dot]musings[At]gmail[dot]com by Friday, July 17, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response.

A relation is an equivalence iff it is reflexive and euclidean

July 9, 2009 in Elementary Math Problem Solving | Tags: equivalence relation, euclidean, reflexive | by Vishal Lama | 8 comments

High-school students and undergraduates are (almost) always taught the following definition of an equivalence relation.

A binary relation $R$ on a set $A$ is an equivalence iff it satisfies

the reflexive property: for all $a$ in $A$ , $a R a$ ,
the symmetric property: for all $a, b$ in $A$ , if $a R b$ , then $b R a$ , and
the transitive property: for all $a, b, c$ in $A$ , if $a R b$ and $b R c$ , then $a R c$ .

However, there is another formulation of an equivalence relation that one usually doesn’t hear about, as far as I know. And, it is the following one.

A binary relation $R$ on a set $A$ is an equivalence iff it satisfies

the reflexive property: for all $a$ in $A$ , $a R a$ , and
the euclidean property: for all $a, b, c$ in $A$ , if $a R b$ and $a R c$ , then $b R c$ .

Exercise: Show that a binary relation $R$ on a set $A$ is reflexive, symmetric and transitive iff it is reflexive and euclidean.

The 54th Carnival of Mathematics

July 5, 2009 in Exposition, Math Topics, Philosophy & Logic | Tags: 54th Carnival of Mathematics, logic, math, philosophy | by Vishal Lama | 18 comments

Welcome to the 54th Carnival of Mathematics, and Happy Fourth of July to our American readers! Indeed, the carnival should have been hosted yesterday, and I apologize for being a day late.

Trivia: Today, we have the 234th Independence Day celebrations in the US, and ours is the 54th carnival. 2+3+4 = 5+4, see? Boy, do I feel so clever!

Ok, let’s begin, now!

We start off with a post, submitted by Shai Deshe, that presents a collection of YouTube videos explaining different kinds of infinities in set theory, causality vs conditionality in probability and some topology. The videos are the kind of ones that “math people” could use to explain a few mathematical concepts to their friends, family members and colleagues who may not be enamored of math very much but may still possess a lingering interest in it.

Experimental philosophy, according to the Experimental Philosophy Society, “involves the collection of empirical data to shed light on philosophical issues“. As such, a careful quantitative analyses of results of experiments are used to shed light on many philosophical issues/debates. Anthony Chemero wrote a post titled, ‘What Situationist Experiments Show‘, that links to a paper with the same title that he coauthored with John Campbell and Sarah Meerschaert. In the paper, the authors, through quantitative analyses of actual experimental data, argue that virtue ethics has not lost to the siuationist side, whose critiques of virtue theory are far from convincing.

Next, I would like to bring the readers’ attention to two math blogs that came into existence somewhat recently and which I think have a lot of really good mathematical content. They are Annoying Precision and A Portion of the Book. In my opinion, their blog posts contain a wealth of mathematical knowledge, especially for undergraduates (and graduate students too!), who, if inclined toward problem-solving, will enjoy the posts even more. Go ahead and dive into them!

At Annoying Precision, a project aimed at the “Generally Interested Lay Audience” that Qiaochu Yuan started aims “to build up to a discussion of the Polya enumeration theorem without assuming any prerequisites other than a passing familiarity with group theory.” It begins with GILA I: Group Actions and Equivalence Relations, the last post of the series being GILA VI: The cycle index polynomials of the symmetric groups.

Usually, undergrads hardly think integrals have much to do with combinatorics. At A Portion of the Book, Masoud Zargar has a very nice post that deals with the intersection of Integrals, Combinatorics and Geometry.

Tom Escent submitted a link to an article titled, “Introduction to Nerds on Wall Street“, which actually provides a very small snapshot of the book named, Nerds on Wall Street: Math, Machines and Wired Markets whose author is David J. Leinweber. I haven’t read the book yet, but based on generally good reviews, it seems like it chronicles the contribution of Quant guys to Wall Street over the past several decades. Should be interesting to Math and CS majors, I think.

Let’s have a post on philosophy and logic, shall we? At Skeptic’s Play, there is a discussion on Gödel’s modal ontological argument regarding the possibility of existence of God. As someone who has just begun a self-study of modal logic, I will recommend Brian K. Chellas’ excellent introduction to the subject, titled Modal Logic: An Introduction.

Then, there is the Daily Integral, a blog dealing with solving elementary integrals and which I think may be particularly useful for high-school students.

Let me close this carnival by asking the reader, “What do you think is the world’s oldest mathematical artifact?” There are several candidates, and according to The Number Warrior, candidate #1 is The Lebombo Bone, found in the Lebombo Mountains of South Africa and Swaziland, that dates back to 35,000 BC!

That’s all for now! Thanks to everyone who made submissons.

Number of idempotent endofunctions

March 28, 2009 in Elementary Math Problem Solving, Problem Corner, Puzzles | Tags: André Joyal, combinatorial species, endofunction, fixed point, generating function, idempotent | by Vishal Lama | 26 comments

Last summer, Todd and I discussed a problem and its solution, and I had wondered if it was fit enough to be in the POW-series (on this blog) when he mentioned that the problem might be somewhat too easy for that purpose. Of course, I immediately saw that he was right. But, a few days back, I thought it wouldn’t be bad if we shared this cute problem and its solution over here, the motivation being that some of our readers may perhaps gain something out of it. What is more, an analysis of an egf solution to the problem lends itself naturally to a discussion of combinatorial species. Todd will talk more about it in the second half of this post. Anyway, let’s begin.

PROBLEM: Suppose $A = \{ 1,2, \ldots , n \}$ , where $n$ is a positive natural number. Find the number of endofunctions $f: A \rightarrow A$ satisfying the idempotent property, i.e. $f \circ f = f$ .

It turns out that finding a solution to the above problem is equivalent to counting the number of forests with $n$ nodes and height at most $1$ , which I found here (click only if you wish to see the answer!) at the Online Encyclopedia of Integer Sequences. If you haven’t clicked on that link yet and wish to solve the problem on your own, then please stop reading beyond this point.

SOLUTION: There are two small (and related) observations that need to be made. And, both are easy ones.

Lemma 1: $f$ has at least one fixed point.

Proof: Pick any $i \in A$ and let $f(i) = j$ , where $j \in A$ . Then, using the idempotent property, we have $f(f(i)) = f(i)$ , which implies $f(j) = j$ . Therefore, $j$ is a fixed point, and this proves our lemma.

Lemma 2: The elements in $A$ that are not fixed points are mapped to fixed points of $f$ .

Proof: Suppose $j \in A$ is not a fixed point such that $f(j) = k$ . Then, using the idempotent property again, we immediately have $f(f(j)) = f(j)$ , which implies $f(k) = k$ , thereby establishing the fact that $k$ itself is a fixed point. Hence, $j$ (which is not a fixed point) is mapped to some fixed point of $f$ .

In both the lemmas above, the idempotent property “forces” everything.

Now, the solution is right before our eyes! Suppose $f$ has $m$ fixed points. Then there are $\displaystyle \binom{n}{m}$ ways of choosing them. And, each of the remaining $n - m$ elements of $A$ that are not fixed points are to be mapped to any one of the $m$ fixed points. And, there are a total of $m^{n-m}$ ways of doing that. So, summing over all $m$ , our final answer is $\displaystyle \sum_{m=0}^{n} \binom{n}{m} m^{n-m}$ .

Exponential Generating Function and Introduction to Species

Hi; Todd here. Vishal asked whether I would discuss this problem from the point of view of exponential generating functions (or egf’s), and also from a categorical point of view, using the concept of species of structure, which gives the basis for a categorical or structural approach to generatingfunctionology.

I’ll probably need to write a new post of my own to do any sort of justice to these topics, but maybe I can whet the reader’s appetite by talking a little about the underlying philosophy, followed by a quick but possibly cryptic wrap-up which I could come back to later for illustrative purposes.

Enumerative combinatorics studies the problem of counting the number $a_n$ of combinatorial structures of some type on an $n$ -element set, such as the number of idempotent functions on that set, or the number of equivalence relations, and so on. A powerful idea in enumerative combinatorics is the idea of a generating function, where we study the series $a_n$ by rolling them into a single analytic function, such as

$\displaystyle A(x) = \sum_{n \geq 0} \frac{a_n x^n}{n!},$

(this the so-called “exponential” generating function of $\{a_n\}_{n \geq 0}$ ). In many cases of interest, the function $A(x)$ will be recognizable in terms of operations familiar from calculus (addition, multiplication, differentiation, composition, etc.), and this can then be used to extract information about the series $a_n$ , such as explicit formulas, asymptotics, and so on. If you’ve never seen this idea in action, you should definitely take a look at Wilf’s book generatingfunctionology, or at the book Concrete Mathematics by Graham, Knuth and Patashnik.

Each of the basic operations one performs on analytic functions (addition, multiplication, composition, etc.) will, it turns out, correspond to some set-theoretic operation directly at the level of combinatorial structures, and one of the trade secrets of generating function technology is to have very clear pictures of the combinatorial structures being counted, and how these pictures are built up using these basic structural operations.

In fact, why don’t we start right now, and figure out what some of these structural operations would be? In other words, let’s ask ourselves: if $A(x)$ and $B(x)$ are generating functions for counting combinatorial structures of type (or species) $A$ and $B$ , then what types of structures would the function $A(x) + B(x)$ “count”? How about $A(x)B(x)$ ? Composition $A(B(x))$ ?

The case of $A(x) + B(x)$ is easy: writing

$\displaystyle A(x) + B(x) = \sum_{n \geq 0} \frac{a_n x^n}{n!} + \sum_{n \geq 0} \frac{b_n x^n}{n!} = \sum_{n \geq 0} \frac{(a_n + b_n) x^n}{n!},$

and thinking of $a_n$ as counting structures of type $A$ on an $n$ -element set, and $b_n$ as counting structures of type $B$ , the quantity $a_n + b_n$ counts elements in the disjoint union of the sets of $A$ -structures and $B$ -structures.

In the categorical approach we will discuss later, we actually think of structure types (or species of structure) $A$ as functors, which take an $n$ -element set $S$ to the set $A\left[S\right]$ of structures of type $A$ on $S$ . Here, we have to be a little bit careful about what categories we’re talking about, but the general idea is that if we have a bijection $f: S \to T$ from one $n$ -element set to another, then it should always be possible to “transport” $A$ -structures on $S$ to $A$ -structures on $T$ , simply by relabeling points along the bijection $f$ . So, let us define a species to be a functor

$A: FB \to Set$

where $FB$ is the category of finite sets and bijections (not all functions, just bijections!), and $Set$ is the category of sets. In enumerative combinatorics, the set $A\left[S\right]$ is normally assumed to be finite, but in other applications of the notion of species, we actually allow a lot more latitude, and allow the functor $A$ to map into other categories $C$ , not just $Set$ (“ $C$ -valued species”). But if we stick for now just to set-valued species $A$ , $B$ , then we define the species $A + B$ by the functorial formula

$\displaystyle (A + B)\left[S\right] = A\left[S\right] \sqcup B\left[S\right]$

where $\sqcup$ denotes disjoint union. So addition of generating functions will correspond to the concrete operation of taking disjoint unions of sets of combinatorial species.

More interesting is the case of multiplication. Let’s calculate the product of two egf’s:

$\displaystyle A(x) B(x) = (\sum_{j \geq 0} \frac{a_j x^j}{j!})(\sum_{k \geq 0} \frac{b_k x^k}{k!}) = \sum_{n \geq 0} (\sum_{j + k = n} \frac{n!}{j! k!} a_j b_k) \frac{x^n}{n!}$

The question is: what type of structure does the expression $\displaystyle \sum_{j+k = n} \frac{n!}{j! k!} a_j b_k$ “count”? Look at the individual terms: the binomial coefficient $\displaystyle \frac{n!}{j! k!}$ describes the number of ways of decomposing an $n$ -element set into two disjoint subsets, one with $j$ elements and the other with $k$ , where $j$ and $k$ add to $n$ . Then, $a_j$ is the number of ways of putting an $A$ -structure on the $j$ -element part, and $b_k$ is the number of $B$ -structures on the $k$ -element part.

This suggests a new operation on structure types: given structure types or species $A, B$ , we define a new species $A \otimes B$ according to the formula

$\displaystyle (A \otimes B)\left[S\right] = \bigsqcup_{T \sqcup U = S} A\left[T\right] \times B\left[U\right]$

(that is, a structure of type $A \otimes B$ on a set $S$ is an ordered pair, consisting of an $A$ -structure on a subset of $S$ and a $B$ -structure on its complement). This functorial operation is usually called the “convolution product” of the combinatorial species $A, B$ : it is the concrete set-theoretic operation which corresponds to multiplication of generating functions.

Finally, let’s look at composition $A(B(x))$ . Here we make the technical assumption that $b_0 = 0$ (no $B$ -structures on the empty set!), so that we won’t have divergence issues blowing up in our faces: we want to remain safely within the realm of finitary structures. Okay, then, what type of combinatorial structure does this egf count?

Perhaps not surprisingly, this is rather more challenging than the previous two examples. In analytic function language, we are trying here to give a meaning to the Taylor coefficients of a composite function in terms of the Taylor coefficients of the original functions — for this, there is a famous formula attributed to Faà di Bruno, which we then want to interpret combinatorially. If you don’t already know this but want to think about this on your own, then stop reading! But I’ll just give away the answer, and say no more for now about where it comes from, although there’s a good chance you can figure it out just by staring at it for a while, possibly with paper and pen in hand.

Definition: Let $A, B: FB \to Fin$ be species (functors from finite sets and bijections to finite sets), and assume $B\left[\emptyset\right] = \emptyset$ . The substitution product $A \circ B$ is defined by the formula

$\displaystyle (A \circ B)\left[S\right] = \sum_{E \in Eq(S)} A\left[S/E\right] \times \prod_{c \in S/E} B\left[c\right]$

This clearly requires some explanation. The sum here denotes disjoint union, and $Eq(S)$ denotes the set of equivalence relations on the finite set $S$ . So $E$ here is an equivalence relation, which partitions $S$ into nonempty sets $c$ ( $E$ -equivalence classes). And the quotient $S/E$ denotes the set of such equivalence classes (so we think of each class $c$ as a point of $S/E$ ). What this formula says is that a structure of type $A \circ B$ on $S$ consists of a partition of $S$ into a bunch of non-empty blobs, a $B$ -structure on each blob, and then an $A$ -structure on the set of blobs.

It’s high time for an example! So let’s look at Vishal’s problem, and see if we can picture it in terms of these operations. We’re going to need some basic functions (or functors!) to apply these operations to, and out of thin air I’ll pluck the two basic ones we’ll need:

$\displaystyle E(x) = \exp(x) = \sum_{n \geq 0} \frac{x^n}{n!}$

$F(x) = x$

The first is the generating function for the series $e_n = 1$ . So for the species $E$ , there’s just one structure of type $E$ for each set $S$ (in categorical language, the functor $E: FB \to Set$ is the terminal functor). We can just think of that structure as the set $S$ itself, if we like, with no other structure appended thereon.

For $F$ , we have $f_n = 0$ unless $n = 1$ , where $f_1 = 1$ . So $F$ is the species for the one-element set structure (meaning that $F\left[S\right] = \emptyset$ unless $S$ has cardinality 1, in which case $F\left[S\right] = \{S\}$ ).

Okay, on to Vishal’s example. He was counting the number of idempotent functions $f: S \to S$ , and now, as promised, I want to determine the corresponding egf. You might be able to find it by looking at his formula, but obviously I want to use the ideas I’ve developed thus far, which focuses much more on the pictures. So, let’s picture $f: S \to S$ , first as Vishal did, by thinking of the elements of $S$ as ‘nodes’, and then drawing a directed edge from node $x$ to node $y$ if $f(x) = y$ . (Then, by idempotence of $f$ , $y$ will be a fixed point of $f$ . Let’s agree not to bother drawing an edge from $y$ to itself, if $y$ is already a fixed point.)

In this picture, we get a directed graph which consists of a disjoint union of “sprouts”: little bushes, each rooted at a fixed point of $f$ , whose only other nodes are “leaves” joined to the root by an edge. We can simplify the picture a little: if you put a circle around each sprout, you don’t need the edges at all: just mark one of the points inside as the root, and you know what to do.

So we arrive at a picture of an idempotent function on $S$ : a partition of $S$ into a collection of (nonempty) blobs, and inside each blob, one of the points is marked “root”. In terms of our operations, what does it mean to mark a point in a blob? It just means: break the blob into two pieces, where one piece is given the structure of “one-element set”, and the other piece is just itself. In terms of the ideas developed above, this means each blob carries a $F \otimes E$ structure; we’ll suggestively write this structure type as $X \otimes \exp(X)$ .

In this picture of idempotent $f$ , there is no extra combinatorial structure imposed on the set of blobs, beyond the set itself. In other words, in this picture, the set of blobs carries merely an “ $E$ -structure”, nothing more.

So, putting all this together, we picture an idempotent function on $S$ as a partition or equivalence relation on $S$ , together with an assignment of a marked point in each equivalence class. In the language of species operations, we may therefore identify the structure type of idempotent functions with

$E \circ (F \otimes E)$

or more suggestively, $\exp \circ (X \otimes \exp(X))$ . The exponential generating function is, of course, $e^{x e^x}$ !

In summary, the theory of species is a functorial calculus which projects onto its better-known “shadow”, the functional calculus of generating functions. That is to say, we lift operations on enumeration sequences $\{a_n\}$ , as embodied in their generating functions, directly up to the level of the sets we’re counting, where the functorial operations become both richer and more concrete. The functorial analogue of the generating function itself is called the “analytic functor” attached to the species (the species itself being the concrete embodiment of the enumeration).

Much more could be said, of course. Instead, here’s a little exercise which can be solved by working through the ideas presented here: write down the egf for the number of ways a group of people can be split into pairs, and give an explicit formula for this number. Those of you who have studied quantum field theory may recognize this already (and certainly the egf is very suggestive!) ; in that case, you might find interesting the paper by Baez and Dolan, From Finite Sets to Feynman Diagrams, where the functorial point of view is used to shed light on, e.g., creation and annihilation operators in terms of simple combinatorial operations.

The literature on species (in all its guises) is enormous, but I’d strongly recommend reading the original paper on the subject:

André Joyal, Une théorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1-82.

which I’ve actually referred to before, in connection with a POW whose solution involves counting tree structures. Joyal could be considered to be a founding father of what I would call the “Montreal school of combinatorics”, of which a fine representative text would be

F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-like Structures, Encyclopedia of Mathematics and its Applications 67, 1998.

More to come, I hope!

A Mathematical Chess (Dissection) Paradox

March 25, 2009 in Elementary Math Problem Solving, Problem Corner, Puzzles | Tags: cassini's identity, chess, dissection, fibonacci, mathematical, paradox | by Vishal Lama | Leave a comment

I thought I would share with our chess-loving readers the following interesting (and somewhat well-known) mathematical chess paradox , apparently proving that $64=65$ , and the accompanying explanation offered by Prof. Christian Hesse, University of Stuttgart (Germany). It shows a curious connection between the well-known Cassini’s identity (related to Fibonacci numbers) and the $8 \times 8$ chessboard ( $8$ being a Fibonacci number!). The connection can be exploited further to come up with similar paradoxes wherein any $F_n \times F_n$ -square can always be “rerranged” to form a $F_{n-1} \times F_{n+1}$ -rectangle such that the difference between their areas is either $+1$ or $-1$ . Of course, for the curious reader there are plenty of such dissection problems listed in Prof David Eppstein’s Dissection page.

Minesweeper tactics

March 5, 2009 in Uncategorized | by Todd Trimble | 22 comments

This being a mathematics blog, I’m sure a lot of readers out like to play Minesweeper. I’ve just obtained a personal best today (94 seconds on expert level) which, as Minesweeper buffs know, is nowhere close to world-class levels, but which made me happy anyway, as I’d never broken into the double digits before today!

It seems to me that world-class competitors must know some tricks with the mouse which I’ve never bothered to master, particularly because my laptop doesn’t have a mouse but rather a touchpad. This being the case, I keep my right index finger on the touchpad to guide the cursor, and the left index finger to click. I always left-click: that is, in my style of play, I [practically] never flag squares for bombs; I click only on non-bomb squares. For it’s well-known, or at least it should be, that the program doesn’t care if you identify where the bombs are — you get full credit for only identifying all the numbered squares.

To play in this style well, one needs to be fluent in a number of tactical tricks, which I don’t have good names for, but which in my personal argot I call things like “1-2-1″, “1-2-2-1″, “rule of three”, to name just a few. But that’s not what I set out to discuss, really. What I’d really like to hear from good players is: what opening strategies do you use?

The personal best I just set came after deciding on a new opening strategy. What I had been doing is clicking along border squares. Under that strategy, one could of course just keep clicking until one opens up an area, but often I would add to that the observation that if one clicked on a 1, thus leading to, e.g.,

x 1 x (–> border row)
x x x

then one could then click on the non-border square just adjacent to the 1, with only a 1 in 5 chance of setting off a bomb. If one then hits another 1:

x 1 x
x 1 x
x x x

then one can immediately open up the line of squares on the third rank, leading to a configuration such as

x 1 x
x 1 x
1 1 1

or better. This is often a cheap and quick way of opening up squares or otherwise getting a tactical toehold.

The new strategy I began using today is not to click along the border, but to click along the ranks or files adjacent to the border. Under this strategy, if one lands on a 1, leading to

x x x (–> border row)
x 1 x
x x x

then one can click on the border square adjacent to the 1, with only a 1 in 8 chance of setting off a bomb. If one does not set off a bomb, that square has to be a 1:

x 1 x
x 1 x
x x x

and then one can proceed as before. So I’ve just lowered my odds of hitting a bomb, plus a very small fractional gain in processing time that comes with the certain knowledge that it’s a 1 if not a bomb. So far the strategy has paid off well!

I’d like to hear other people’s opening strategies, and also I’d like to know some statistics. For example, considered over the space of expert-level games, what is the probability of getting a 1, a 2, and so on? Does anyone know? (It seems this would be very difficult computing analytically — one is probably better off using a Monte Carlo simulation. But I don’t have the wherewithal to set that kind of thing up.)

Happy Co-Valentine’s Day!

February 14, 2009 in Uncategorized | Tags: arrows, love, Valentine's day | by Vishal Lama | 4 comments

Love is like PI – natural, irrational and very important!
- Lisa Hoffman

Happy Co-Valentine's Day

Valentine’s Day is usually associated with romantic love, but I think such an idea although wonderful is somewhat restrictive. This time of the year, I believe, is also about letting people close and dear to you know how much you love and care about them! Keeping that in mind, I wish my parents a Happy Valentine’s Day and hope that my younger brother, Vishant, has a great Valentine’s Day too!

I also sincerely hope that Todd gets to spend a great Valentine weekend with his wife and family! And, here’s hoping that all our readers and my friends (including Aditya, Pawan and Kenji!) will today not hesitate in expressing their love to their near and dear ones.

And very importantly, here’s wishing Carolyn an unforgettable Valentine’s Day! Thanks for being my Valentine even though you are thousands of miles away!!

[I do hope Todd will forgive me for posting something completely non-mathematical. In my defense, this post has at least a reference to PI and category theory! ]

Solution to POW-12: A graph coloring problem

January 4, 2009 in Problem of the Week (POW), Puzzles | by Todd Trimble | 19 comments

The solutions are in! This problem of the week was interesting for me: the usual pattern has been that I pose problems that I’ve solved myself at some point in the past, giving me a kind of “inside edge” on understanding the solutions that come in. But, as I said in POW-12, the difference this time is that the solution I knew of came from someone else (Arin Chaudhuri). What was interesting for me — and given the circumstances, it was probably inevitable — is that some of the solutions we received forced me to make contact with some mathematics I’d only heard about but never studied. Let me get to that in a minute.

Another interesting thing for me — speaking now with my category theorist’s hat on — is how utterly simple and conceptual Arin’s proof was! I was pleased to see that regular problem solver Philipp Lampe also spotted it. Wait for it…

Solution I by Philipp Lampe, University of Bonn: The answer is 8.

Among the eight neighbors of an arbitrary vertex, all colors of an admissible coloring must occur. Thus, 8 is an upper bound for the maximum number of colors one can use. We have to show that there is an admissible coloring with eight colors.

The vertices of the 8-dimensional cube may be represented by vectors $(a_1, a_2, \ldots, a_8)$ with $a_i$ in $\{0,1\}$ , in other words as vectors in $\mathbb{F}_{2}^8$ , the 8-dimensional vector space over the field $\mathbb{F}_2 = \{0, 1\}$ with two elements (i.e., the integers modulo 2). Two such vectors $u, v$ are neighbors iff their coordinate vectors differ in exactly one place, in other words if $u = v + e_i$ considered modulo 2, where $e_i$ is one of the eight standard basis elements (with $i$ -th coordinate 1, and the other coordinates 0).

Now let our “colors” be the 8 elements $x_1, x_2, \ldots, x_8$ of $\mathbb{F}_{2}^3$ , the 3-dimensional vector space over $\mathbb{F}_2$ . Let the vertex “coloring”

$C: \mathbb{F}_{2}^8 \to \mathbb{F}_{2}^3$

be the unique $\mathbb{F}_2$ -linear map such that $C(e_i) = x_i$ ; that is, define the color of a vertex/vector by

$\displaystyle C\left(a_1,\ldots, a_8\right) = \sum_{i=1}^{8} a_i x_i$

Now, if $v$ is any vector, the colors of its neighbors are $C(v + e_i) = C(v) + C(e_i) = C(v) + x_i$ . The colors of these neighbors are all distinct since the $x_i$ are distinct. Hence all 8 colors are represented among the colors of the neighbors of any given vertex $v$ , QED.

What I love about this solution it is how natural it is. I’ll say a little more about this in remarks below.

But I also learned a thing or two by studying the next solution. It relies on the theory of Hamming codes, with which I was not conversant. Up to some small edits, here is exactly what Sune Jakobsen submitted:

Solution II by Sune Jakobsen (first-year student), University of Copenhagen: Since each vertex only has 8 neighbors, the answer cannot be greater that 8.

Now we construct such a coloring with 8 colors. An 8-dimensional cube can be represented by the graph with vertices in $\{0, 1\}^8$ , and with an edge between them iff the Hamming distance between them is 1. We color a vertex with color 8 if the seven first bits in the vertex is a “correct” Hamming message (cf. Hamming code (7,4)), and color it in color $i$ if the first seven bits give a correct Hamming message upon changing bit $i$ . This is a well-defined coloring, since each element in $\{0, 1\}^7$ is either a correct Hamming message, or is Hamming distance 1 away to exactly one correct Hamming message.

It remains to show that no vertex is neighbor to two vertices of the same color. The Hamming distance between these two vertices is 2, thus the Hamming distance between the first 7 bits of two neighbors must be 1 or 2. If two neighbors had the same color $i$ , then by definition one would get two correct Hamming messages by changing bit $i$ in both of them, and the Hamming distance between these messages would be the same as before — either 1 or 2. But the distance between any two correct Hamming messages is at least 3. Contradiction.

Remarks:

1. Let me give a little background to Sune’s solution. Mathematically, the Hamming code called “(7, 4)” is the image of injective linear map

$G: \mathbb{F}_{2}^4 \to \mathbb{F}_{2}^7$

given by the $7 \times 4$ matrix

1101
1011
1000
0111
0100
0010
0001

The Hamming code is what is known as an “error-correcting code”. Imagine that you want to send a 4-bit message (each bit being a 0 or 1) down a transmission line, but that due to noise in the line, there is the possibility of a bit being flipped and the wrong message being received. What can you do to help ensure that the intended message is received?

The answer is to add some “parity check bits” to the message. In the code (7, 4), one adds in three parity checks, so that the transmitted message is 7 bits long. What one does is apply the matrix $G$ to the 4-vector, to get a 7-vector (remember we’re working modulo 2), and this 7-vector is sent down the line. Assuming only a moderate amount of noise in the transmission line, perhaps the 7-bit message will remain intact or perhaps a single bit will be flipped, more rarely two bits will be flipped (and we’ll assume the event that more than two are flipped has negligible probability). Now, the Hamming encoding $G$ is rigged up so that if the 7-bit vector is received as sent, then the parity checks will report 0 errors. If the parity checks report an error, they report precisely where the error occurred if the received vector was off by one bit. (If two flips occurred, then the receiver can still detect from the parity checks that an error occurred. The parity checks can never detect how many bits were flipped, but if the receiver assumes correctly that just one bit got flipped, he can restore the intended message with accuracy. If three or more got flipped, then the receiver got the wrong message, but he would never know it if the parity checks reported back 0 errors.)

How does this work? By having the receiver apply a parity-check matrix $H$ to the received message, given by the $3 \times 7$ matrix

1010101
0110011
0001111

In the first place, $HG = 0$ , and so if the message received belongs to the image of $G$ (is a “correct Hamming message” in the terminology of Solution II), which will indeed be the case if there were no errors in the transmission, then $H$ applied to the message will produce the zero vector. In the case where one bit got flipped in the transmission, $H$ applied to the received vector will return a nonzero 3-vector, but the beauty of the Hamming code is that the 3-vector will spell out in binary the bit the error occurred (for example, if the output vector is $(0 1 1)^t$ , then error occurred in the bit with binary number 011, that is bit 3). In that case, the receiver flips that bit to restore the original message. In these two cases, the original 4 bits are then read off as the 3rd, 5th, 6th, and 7th coordinates of the (possibly corrected) 7-vector.

By the way, Sune reminded us that Hamming codes also came up in a post by Greg Muller over at The Everything Seminar, who used the existence of a Hamming code in every dimension $2^k - 1$ to solve general hat-guessing puzzles.

2. Within minutes of posting the original problem, we received a message from David Eppstein, who reported that the solution of 8 colors is essentially contained in a paper he coauthored with T. Givaris (page 4); his solution is close in spirit to Sune’s.

Arin Chaudhuri also surmised the connection to Hamming codes, and mentions that the problem (in a slightly different formulation) originally came from a friend of a friend, who blogs about a number of related problems on this page. Presumably the author had things like error-correcting codes in mind.

3. Sune and David noted that their solutions generalize to show that on the $2^k$ -dimensional cube (for any $k$ ), it is possible to color the vertices with $2^k$ colors (the maximum number possible) so that all of the colors show up as colors of the neighbors of any given vertex.

This is very easy to see by adapting Philipp’s method. Indeed, for each $k$ just take the color set to be the $\mathbb{F}_2$ -vector space $S = \mathbb{F}_{2}^k$ . The set of vertices of the $2^k$ -dimensional cube may identified with the $\mathbb{F}_2$ -vector space $V(S)$ generated by the set $S$ (as basis), and the desired coloring is then just the $\mathbb{F}_2$ -linear map $C: V(S) \to S$ that extends the identity function on $S$ . As mathematical constructions go, you can’t get much more canonical than that! No fuss, no muss — it’s a purely categorical construction (categorists call it a counit of an adjunction). So then why didn’t I see that myself?

4. We’re still not sure what the story is in other dimensions. If $a_n$ is the maximum number of admissible colors in dimension $n$ , then about all any one of us knows right now is that $a_n = n$ for $n = 2^k$ , $a_n$ is weakly monotone increasing, and that $a_n < n$ if $n$ is not a power of 2. There’s a conjecture afloat that $a_n = 2^{\left[\log_2 n\right]}$ where $\left[x\right]$ is the floor function, but for now that should be treated as a wild guess. If anyone has further information, please let us know!

Solved by Arin Chaudhuri, David Eppstein, Sune Jakobsen, and Philipp Lampe. Thanks to all those who wrote in!

	John Armstrong on Inclusion-Exclusion Principle:…
	ALEEFA on Inclusion-Exclusion Principle:…
	Rashad on A relation is an equivalence i…
	Todd Trimble on Boolean algebras, Boolean ring…
	Vishal Lama on Boolean algebras, Boolean ring…
	Todd Trimble on Boolean algebras, Boolean ring…
	Vishal Lama on Boolean algebras, Boolean ring…
	Todd Trimble on Solution to POW-12: A graph co…
	Kifayat ullah on Solution to POW-12: A graph co…
	Bill Bartmann on Free Boolean algebras, truth t…
	Ragib Zaman on Integration Bee, Challenging…
	Scott Carnahan on The Character of Physical…
	baji on Pedagogy: Concrete and Abstrac…
	Math World \| Solutio… on Solution to POW-13: Highly…
	Calling All Math Blo… on The 54th Carnival of Math…

November 2009
M	T	W	T	F	S	S
« Jul
						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

Todd and Vishal’s blog

Exponential Generating Function and Introduction to Species

Our other blog

Visitors to this blog

Blog Stats

Current Online Readers

Recent Comments

Top Posts

Archives

c

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

Spam Blocked

Admin/Users Login

Pages