General-position hypercube projections
I recently posted about finding solutions to the no-three-in-line problem of finding large general-position subsets of grids, by using the probabilistic method or by throwing an integer linear program solver at the problem. Another potential method for finding solutions involves finding large general-position subsets in higher dimensions, where it’s easier (there’s more room to move the points out of the way of each other), and then projecting back down while being careful not to introduce any new collinearities.
A particularly nice family of general-position subsets is given by the hypercubes. The vertices of a \(d\)-dimensional hypercube can be described as the points in \(d\)-dimensional space all of whose coordinates are zeros and ones. There’s no way for three such points to lie on a line, because the middle of the three points would have to have fractional coordinates somewhere between the zero-one coordinates of the outer two points. So for the purposes of the no-three-in-line problem these points are in general position.
A projection of a hypercube onto the integer grid can be described (up to translations) by choosing \(d\) two-dimensional vectors and letting the projected points be all sums of subsets of these vectors. There are \(2^d\) subsets (including the empty subset and the subset of all vectors), and their sums give \(2^d\) points in the plane. It’s always possible to choose a \(d\)-tuple of vectors that causes these \(2^d\) points to remain in general position, but the question is how small we can make these vectors in order to make the projection stay within a small grid.
For \(d\in\{2,3,4\}\) the answer is that we can fit the points into a grid of size \(2^{d-1}\times 2^{d-1}\). This is optimal because any smaller grid would cause more than two points to lie on the same horizontal or vertical grid line.
The simplicity of the \(4\)-dimensional projection (\(16\) points in an \(8\times 8\) grid with no three in line) makes me wonder whether this solution was the one Dudeney was trying to avoid in his 1917 statement of the problem, when he added the extra condition that the solutions (described in terms of pawns on a chessboard) must include pawns at e4 and d5.
Unfortunately the \(5\)-dimensional hypercube doesn’t have a general-position projection onto a \(16\times 16\) grid. The best my search software could find were several different \(18\times 19\) solutions. Here’s one of them:
Beyond these specific examples, it would be interesting to obtain asymptotic bounds on how big a grid is needed for all hypercubes.