• Choose a category
• All
• Classic-Fiction

Imagine now that we extend the grid to three dimensions, i.e., a three-by-three-by-three grid. It turns out that in three dimensions the largest possible line-free configuration has 16 locations filled in. If we fill in 17 locations on the grid, then no matter which locations we fill in, it will be possible to draw a line through three dots somewhere on the grid. You can take my word for this, or, if you prefer, with a bit of work and three-dimensional imagination, you can convince yourself that this is the case.

Let’s make a leap now, and imagine extending the grid from three dimensions to an arbitrary number of spatial dimensions. We’ll give the number of dimensions a label—we’ll call it n. This extension is hard to visualize, hard enough that most mathematicians can’t do it, and they instead translate the problem into an algebraic form. I won’t do the algebraic translation here, but instead I’ll just explain the question we’re concerned with: what’s the size of the largest line-free configuration on a grid in n dimensions? We’ll give that size a name, calling it sn. Our discussion above indicates that s2 = 6 and s3 = 16, the sizes of the largest line-free configurations in two and three dimensions. In higher dimensions it rapidly gets extremely difficult to figure out the value of sn. Mathematicians have worked out the value of s2 and s3, as we’ve seen, and also, with more effort, s4, s5, and s6, but no one in the world knows what the exact value is for s7. And the situation gets even more complicated in still higher dimensions. But even though it is difficult to figure out an exact value for sn, the DHJ theorem gives us some partial information about how large sn is.

In particular, one consequence of the DHJ theorem is that as the number of dimensions n gets very large, the size sn of the largest line-free configuration is only a tiny fraction of the total number of locations on the grid. Put another way, as n gets large, filling in even a tiny fraction of the grid forces a line somewhere. It doesn’t matter how clever you are in filling in locations, there will be a line somewhere. To put the statement in slightly more formal terms, the DHJ theorem tells us that the fraction of the grid sn/3n occupied by the largest line-free configuration gets vanishingly small as n becomes large—it goes to zero in the limit of large n, to use the mathematical lingo.

This is an astonishing statement. As we’ve seen, in two and three dimensions we can fill in most of the grid before we’re forced to put three pieces in a line. Yet in high dimensions, DHJ tells us that a line is forced somewhere on the grid, even if only a tiny fraction of the grid is filled in. It’s not at all obvious that this should be the case, and yet the DHJ theorem tells us that it’s true.

I’ve been describing consequences of the DHJ theorem, in order to give you the flavor of what DHJ says. In fact, the full statement of the DHJ theorem is stronger than the consequences I’ve described so far. It doesn’t just work for three-by-three-by . . . grids, an analogous statement is true for m-by-m-by . . . grids, where m is any number at all. Furthermore, DHJ even tells us that the line will be a certain special type of line called a combinatorial line. I won’t define combinatorial lines here—see the references in the endnotes if you’d like an explanation of what a combinatorial line is. For now, it’s enough that they’re a special type of line. What the full statement of the DHJ theorem says is that as the number of dimensions n gets large, the fraction of the m × m × . . . grid occupied by the largest subset without a combinatorial line goes to zero. Put another way, as n gets large, filling in even a tiny fraction of the grid will force a combinatorial line somewhere.

Why should you care about DHJ? If you’re coming to DHJ without a lot of mathematical background knowledge, it perhaps seems like an obscure problem. DHJ seems like the kind of puzzle that might make a potentially fun (if difficult) diversion,