Monday, October 04, 2021

[tlbuipqj] planes through 4 vertices of a hypercube

we consider the Ramsey graph coloring problem made famous by Graham's number.

a d-dimensional hypercube has 2^d vertices, so its complete graph has binomial(2^d,2) edges.

it has f(d) planar subsets of 4 vertices, where f(d) = (6^d + 2^d - 2*4^d)/8 ; (OEIS A016283).  it is a little bit surprising this expression is always an integer (only need to check d = {0,1,2} because higher d cause the numerator to have enough factors of 2).

every planar subset of 4 vertices is always a parallelogram, but proving that fact is slightly nontrivial.  is it always a rectangle?

in 4D, consider a tesseract bounded by (0,0,0,0) and (1,1,1,1).  it has 16 vertices and 120 edges.  there are f(4) = 100 planar subsets of 4 vertices.  among them is this elegant square of side sqrt(2):

Is this the largest-area planar subset of 4 vertices in a 4D hypercube?  this square is somewhat aesthetically similar to the equilateral triangle hidden among the vertices of a 3D cube, but the triangle does not span opposite vertices of the cube as this square does in the tesseract.  (what is the 4D analogue of the regular hexagon hidden among the cross sections of a cube?  it is some 3D polyhedron.)

possibly of interest is the rotation group of the tesseract.  it has 192 elements.  the full automorphism group (future post zopdmbui) includes mirror images, so has order twice that, 2^d*(d!) (OEIS A000165), or 384 for d=4.  because of the factorial, this sequence grows faster than the number of planar subsets of 4 vertices.  this is somewhat surprising because, for a given planar subset, it seems one could rotate it in many different ways to generate other planar subsets.

the current lower bound for Graham's number is 13.  to disprove 13, i.e., to raise the lower bound, we need a 2-coloring of the edges and all diagonals of a 13-dimensional hypercube that avoids a planar K4 of the same color.  (alternatively, some non-constructive proof that such a coloring exists.)  there are 33550336 edges.  we would need to check f(13) = 1615810560 planar subsets of edges.

presumably such a coloring of the 12-dimensional hypercube exists.  8386560 edges, f(12) = 267904000 planar subsets of edges.

we investigate prime factorization of f(d) using Pari/GP.

addprimes([2540341408694303316943652119999, 225986911513165436959419576586387, 78236248423963530824630162507, 36548282222048342116048567, 20438550797700490833113893109377 ])

With the above large primes, Pari/GP can quickly factor f(3) through f(181).  the next unfactored number, f(182), is 468 bits.  every f(d) seems to be divisible by a high power of two, namely 2^(d-1) if d is odd and 2^(d-2) if d is even.  f(182)/2^180 is 288 bits.

if p is prime, then it seems p divides f(p).  also p divides f(p-1).  composite n divides f(n) for the following n up to 1000:

1 4 8 16 20 32 40 64 80 88 100 128 160 200 220 256 272 320 400 440 464 500 512 544 561 640 800 880 920 1000

No comments :