20161208, 04:49  #1 
Mar 2006
11×43 Posts 
Need help finding the pattern...
I'm trying to find a way to generate a list of all sets of 4 vertices that are coplanar inside of ndimensional unit cubes. Let's call the 4 coplanar vertices a K4.
For example: The 2d unit cube has 4 vertices, all of which are coplanar, so there is only 1 K4. The 3d unit cube has 8 vertices. This cube has 12 K4's; the 6 faces, plus 6 "faces" that are internal to the cube. The 4d unit cube has 16 vertices. This cube has 100 K4's; etc. Since these are unit cubes, each vertex is either at 0 or 1 on a given axis. So, for 2d, the vertex coordinates are: (0,0), (0,1), (1,0), (1,1) And for 3d, the vertex coordinates are: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1) This makes it easy to label each vertex in an ndimensional cube, we can just interpret the coordinates of each vertex as a binary number: So, for 2d, the vertices are: (0,0) = 00 = 0 (0,1) = 01 = 1 (1,0) = 10 = 2 (1,1) = 11 = 3 And so on for higher dimensional cubes. For the 3d cube, I was able to manually go through and create the list of 12 K4's. Here is the list: Code:
K4 1 = 0,1,2,3 K4 2 = 0,1,4,5 K4 3 = 0,1,6,7 K4 4 = 0,2,4,6 K4 5 = 0,2,5,7 K4 6 = 0,3,4,7 K4 7 = 1,2,5,6 K4 8 = 1,3,4,6 K4 9 = 1,3,5,7 K4 10 = 2,3,4,5 K4 11 = 2,3,6,7 K4 12 = 4,5,6,7 I tried looking at the 3d solutions as binary numbers, and I can see some patterns, but I don't know how to extend these patterns beyond 3d. Here is the binary version of the above table: Code:
K41: K42: K43: K44: K45: K46: 000 000 000 000 000 000 001 001 001 010 010 011 010 100 110 100 101 100 011 101 111 110 111 111 K47: K48: K49: K410: K411: K412: 001 001 001 010 010 100 010 011 011 011 011 101 101 100 101 100 110 110 110 110 111 101 111 111 
20161208, 05:46  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·11·107 Posts 
Vertices a, b, c, and d form a K4 iff det(ba, ca, da) = 0
(i.e. volume of that parallelepiped is zero) You can write a fast code that loops over all unique combinations of four vertices and output only those that have zero det. If you only need the # of K4s, you can check a few dimensions and then deduce a polynomial by finite differences (that's what I would do, being lazy and all). 
20161208, 06:10  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×11×107 Posts 
...also, as you have represented each vertice as a binary number, it follows that a^b^c^d = 0 (where ^ is XOR) _and_ a+d==b+c
To generate: Code:
n=3;m=2^n1;s=0;for(a=0,m,for(b=a+1,m,ab=bitxor(a,b);for(c=b+1,m,d=bitxor(ab,c);if(d>c && b+c==a+d,s++;print1(a," ",b," ",c," ",d," ; ")))));s 0 1 2 3 ; 0 1 4 5 ; 0 1 6 7 ; 0 2 4 6 ; 0 2 5 7 ; 0 3 4 7 ; 1 2 5 6 ; 1 3 4 6 ; 1 3 5 7 ; 2 3 4 5 ; 2 3 6 7 ; 4 5 6 7 ; 12 n=4;m=2^n1;s=0;for(a=0,m,for(b=a+1,m,ab=bitxor(a,b);for(c=b+1,m,d=bitxor(ab,c);if(d>c&&b+c==a+d,s++;print1(a," ",b," ",c," ",d," ; ")))));s 0 1 2 3 ; 0 1 4 5 ; 0 1 6 7 ; 0 1 8 9 ; 0 1 10 11 ; 0 1 12 13 ; 0 1 14 15 ; 0 2 4 6 ; 0 2 5 7 ; 0 2 8 10 ; 0 2 9 11 ; 0 2 12 14 ; 0 2 13 15 ; 0 3 4 7 ; 0 3 8 11 ; 0 3 12 15 ; 0 4 8 12 ; 0 4 9 13 ; 0 4 10 14 ; 0 4 11 15 ; 0 5 8 13 ; 0 5 10 15 ; 0 6 8 14 ; 0 6 9 15 ; 0 7 8 15 ; 1 2 5 6 ; 1 2 9 10 ; 1 2 13 14 ; 1 3 4 6 ; 1 3 5 7 ; 1 3 8 10 ; 1 3 9 11 ; 1 3 12 14 ; 1 3 13 15 ; 1 4 9 12 ; 1 4 11 14 ; 1 5 8 12 ; 1 5 9 13 ; 1 5 10 14 ; 1 5 11 15 ; 1 6 9 14 ; 1 7 8 14 ; 1 7 9 15 ; 2 3 4 5 ; 2 3 6 7 ; 2 3 8 9 ; 2 3 10 11 ; 2 3 12 13 ; 2 3 14 15 ; 2 4 10 12 ; 2 4 11 13 ; 2 5 10 13 ; 2 6 8 12 ; 2 6 9 13 ; 2 6 10 14 ; 2 6 11 15 ; 2 7 8 13 ; 2 7 10 15 ; 3 4 11 12 ; 3 5 10 12 ; 3 5 11 13 ; 3 6 9 12 ; 3 6 11 14 ; 3 7 8 12 ; 3 7 9 13 ; 3 7 10 14 ; 3 7 11 15 ; 4 5 6 7 ; 4 5 8 9 ; 4 5 10 11 ; 4 5 12 13 ; 4 5 14 15 ; 4 6 8 10 ; 4 6 9 11 ; 4 6 12 14 ; 4 6 13 15 ; 4 7 8 11 ; 4 7 12 15 ; 5 6 9 10 ; 5 6 13 14 ; 5 7 8 10 ; 5 7 9 11 ; 5 7 12 14 ; 5 7 13 15 ; 6 7 8 9 ; 6 7 10 11 ; 6 7 12 13 ; 6 7 14 15 ; 8 9 10 11 ; 8 9 12 13 ; 8 9 14 15 ; 8 10 12 14 ; 8 10 13 15 ; 8 11 12 15 ; 9 10 13 14 ; 9 11 12 14 ; 9 11 13 15 ; 10 11 12 13 ; 10 11 14 15 ; 12 13 14 15 ; 100 for(n=2,10,m=2^n1;s=0;for(a=0,m,for(b=a+1,m,ab=bitxor(a,b);\ for(c=b+1,m,d=bitxor(ab,c);if(d>c&&b+c==a+d,s++))));print(n" "s)) 2 1 3 12 4 100 5 720 6 4816 7 30912 8 193600 9 1194240 10 7296256 Last fiddled with by Batalov on 20161208 at 07:38 
20161208, 12:59  #4  
Mar 2006
11×43 Posts 
Quote:
I had seen the entry for the number of K4's in OEIS, but I couldn't find the actual sets of K4's. I wonder if it would be interesting enough to try to add to the OEIS? Like, one entry for n=3, and one entry for n=4. We could give the above code so people could then generate their own sequences for larger values of n. Although, it might be tough to add since it is a set of sets, and not just a set of numbers. For n=3 we can just concatenate the vertices to make that a set of numbers. And, I guess if we label each vertex as an alphanumeric then we could make it a set of "numbers" for n=4 [09af] and n=5 [09av]. I'd be interested to hear what you think about adding this sequence to the OEIS. Thanks again! 

20161208, 15:21  #5 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
are you trying to figure out the vertex problem that inspired graham's number ?

20161208, 17:02  #6 
Apr 2012
Brady
2×3^{3}×7 Posts 
Always nice to see an `asked and answered` requiring something of a `Eulerian` insight.
Aside from an online search or tossing a program into a machine initially, here are a few books that once read and memorized to varying degrees may provide insight: Finch's Mathematical Constants, Hamming's Numerical Methods (Dover) and Documenta Geigy  Scientific Tables..and Frederickson's Dissections: Plane and Fancy. From abstract numerical patterns to codification and application to visualization of forms, by looking at certain structures you can [almost] instinctively feel what mode of inquiry will and won't make the cut (pun). 
20161208, 17:48  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·11·107 Posts 
Yes, this could make for a nice Project Eulerlike problem. I quite enjoyed it.
I 'grok'ed that a^b^c^d = 0 is a superset of the wanted set, and then observed that a+d=b+c (with a<b<c<d) takes care of the unwanted "binary carries" (example "1 2 4 7" and "2 3 5 6" pass the a^b^c^d = 0 test but are not coplanar obviously). a+d=b+c appears to work to fit the exact problem at hand but I didn't prove it (at least to myself). 
20161209, 03:41  #8  
Mar 2006
731_{8} Posts 
Quote:
But seriously, well spotted! What gave it away? I've been interested in Graham's number for a long time. I've seen several good videos about it on YouTube, including a few that feature Ron Graham himself. The YouTube channel Numberphile has 5 videos on it that they've collected into the following playlist: https://www.youtube.com/watch?v=HX8b...FLIB5q&index=1 I'm planning on writing a program to 2color various ndimensional cubes to see how difficult it is to come up with counterexamples. I read a couple of the papers mentioned on the Graham's number Wikipedia page. One of them provided counterexamples for n=3 to 12. Once I figured out how to interpret their counterexamples, I realized that I would need to know how to generate all K4's so I could write my own generator/verifier. Which is what led to this thread. I'm not sure what the best way to 2color these ncubes will be, but I'll be trying several different methods. If anyone else is interested I can post my code here and we can try to generate our own counterexamples for n >= 13. 

20161209, 13:02  #9  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
thinking about it last night kept me awake for a bit if my intuition about it is correct I have the following: 1) an n dimensional cube will have N=2^n vertices 2) using the numberphile friendship theorem video there will be T(2^n1) ways to connect these vertices. 3) that means colouring with two colors there will be a total of 2^T(2^n1) possible colorings. 4) the number of connection groups with 4 dots ( not all necessarily K4's) is then (2^n)*(2^n1)*(2^n2)*(2^n3) /24. 5) from the same video on friendships as before every group of 6 vertices will have at least three connected in one of the two colors. etc. in PARI/gp it's not that hard to make sets of subsets in theory but it might be hard to get rid of duplicates: Code:
my(d1=[a,b,c],d=d1);until(#d>9,d=setbinop((x,y)>concat(x,y),d1,d));d Last fiddled with by science_man_88 on 20161209 at 14:00 

20161209, 14:40  #10 
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
and of course half of the colourings just switch the colors from the other half so the number of unique colorings if you don't care what color it is is cut in half. edit: and then you can cut down using rotation and reflections the front face of a 3dcube being all one color is the same as the rotation of that face to any of its other sides it has 6 faces so without those you cut by the number of exterior faces etc.
Last fiddled with by science_man_88 on 20161209 at 15:00 
20161210, 15:57  #11  
Einyen
Dec 2003
Denmark
110000110001_{2} Posts 
From: https://en.wikipedia.org/wiki/Graham%27s_number
Quote:
Quote:
Original paper: http://www.math.ucsd.edu/~ronspubs/71_04_n_ramsey.pdf The bound is on page 290 using an "Ackermann"like function. It seems that: F(12,3) = F(11,4) = 2^^^^^^^^^^^4 (11 arrows) so the bound is something like: f^{7}(11) where f(n) = 2 ^^{n} 4 (n arrows) compared to Graham's number G: g^{64}(4) where g(n) = 3 ^^{n} 3 (n arrows) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime Number Pattern, Probably not but have a look please.  matthewsx7  Miscellaneous Math  21  20160625 08:30 
New Pattern Found in Mersenne Exponents  PawnProver44  Miscellaneous Math  6  20160311 22:52 
Prime pattern thoughts  jasong  jasong  11  20130213 01:36 
A Pattern That Is Not  davar55  Miscellaneous Math  36  20110119 15:21 
Initial Pattern  davar55  Puzzles  6  20070612 00:00 