mersenneforum.org Need help finding the pattern...
 Register FAQ Search Today's Posts Mark Forums Read

 2016-12-08, 04:49 #1 WraithX     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 n-dimensional unit cubes. Let's call the 4 coplanar vertices a K4. For example: The 2-d unit cube has 4 vertices, all of which are coplanar, so there is only 1 K4. The 3-d unit cube has 8 vertices. This cube has 12 K4's; the 6 faces, plus 6 "faces" that are internal to the cube. The 4-d 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 2-d, the vertex coordinates are: (0,0), (0,1), (1,0), (1,1) And for 3-d, 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 n-dimensional cube, we can just interpret the coordinates of each vertex as a binary number: So, for 2-d, 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 3-d 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 can probably manually go through the 4-d cube and create the list of 100 K4's, but that may take a while and is potentially error prone. Plus, that wouldn't help me with 5-d, or 6-d, or higher dimensional cubes which will have vastly more K4's! Can anyone help me find a way to generate the list of the vertices in all K4's in a given n-dimensional unit cube? I tried looking at the 3-d solutions as binary numbers, and I can see some patterns, but I don't know how to extend these patterns beyond 3-d. Here is the binary version of the above table: Code: K4-1: K4-2: K4-3: K4-4: K4-5: K4-6: 000 000 000 000 000 000 001 001 001 010 010 011 010 100 110 100 101 100 011 101 111 110 111 111 K4-7: K4-8: K4-9: K4-10: K4-11: K4-12: 001 001 001 010 010 100 010 011 011 011 011 101 101 100 101 100 110 110 110 110 111 101 111 111 This is part of a project that I'm working on for fun. Let me know if any of the above is unclear and I can try to clarify.
 2016-12-08, 05:46 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23·11·107 Posts Vertices a, b, c, and d form a K4 iff det(b-a, c-a, d-a) = 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).
 2016-12-08, 06:10 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23×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^n-1;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^n-1;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^n-1;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 This is OEIS https://oeis.org/A016283 = (6^n - 2*4^n + 2^n)/8 Last fiddled with by Batalov on 2016-12-08 at 07:38
2016-12-08, 12:59   #4
WraithX

Mar 2006

11×43 Posts

Quote:
 Originally Posted by Batalov ...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^n-1;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 for(n=2,10,m=2^n-1;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 This is OEIS https://oeis.org/A016283 = (6^n - 2*4^n + 2^n)/8
This is amazing! Thank you so much for the insights, and especially the code! I'm really impressed that you found it so quickly.

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 [0-9a-f] and n=5 [0-9a-v]. I'd be interested to hear what you think about adding this sequence to the OEIS. Thanks again!

 2016-12-08, 15:21 #5 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts are you trying to figure out the vertex problem that inspired graham's number ?
 2016-12-08, 17:02 #6 jwaltos     Apr 2012 Brady 2×33×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).
 2016-12-08, 17:48 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23·11·107 Posts Yes, this could make for a nice Project Euler-like 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
2016-12-09, 03:41   #8
WraithX

Mar 2006

7318 Posts

Quote:
 Originally Posted by science_man_88 are you trying to figure out the vertex problem that inspired graham's number ?
Graham's what?
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:

I'm planning on writing a program to 2-color various n-dimensional 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 2-color these n-cubes 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.

2016-12-09, 13:02   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by WraithX Graham's what? 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 2-color various n-dimensional 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 2-color these n-cubes 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.
watching a lot of numberphile gave it away.
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^n-1) ways to connect these vertices.
3) that means colouring with two colors there will be a total of 2^T(2^n-1) possible colorings.
4) the number of connection groups with 4 dots ( not all necessarily K4's) is then (2^n)*(2^n-1)*(2^n-2)*(2^n-3) /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
in fact in newer version there's even a forsubgroup call depending on the group properties.

Last fiddled with by science_man_88 on 2016-12-09 at 14:00

 2016-12-09, 14:40 #10 science_man_88     "Forget I exist" Jul 2009 Dumbassville 203008 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 3d-cube 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 2016-12-09 at 15:00
2016-12-10, 15:57   #11
ATH
Einyen

Dec 2003
Denmark

1100001100012 Posts

From: https://en.wikipedia.org/wiki/Graham%27s_number

Quote:
 Graham invented the quantity now known as Graham's number in conversation with Gardner. While Graham was trying to explain a result in Ramsey theory which he had derived with his collaborator Bruce Lee Rothschild, Graham found that the quantity now known as Graham's number was easier to explain than the actual number appearing in the proof. Because the number which Graham described to Gardner is larger than the number in the paper itself, both are valid upper bounds for the solution to the problem studied by Graham and Rothschild.[6]

Quote:
 However, when Graham published a paper on this puzzle, the number that shows up is not Graham's number, but something much smaller... though still insanely large: So I asked Graham. And the answer was interesting. He said he made up Graham's number when talking to Martin Gardner! Why? Because it was simpler to explain than his actual upper bound - and bigger, so it's still an upper bound!

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:

f7(11) where f(n) = 2 ^n 4 (n arrows)

compared to Graham's number G:

g64(4) where g(n) = 3 ^n 3 (n arrows)

 Similar Threads Thread Thread Starter Forum Replies Last Post matthewsx7 Miscellaneous Math 21 2016-06-25 08:30 PawnProver44 Miscellaneous Math 6 2016-03-11 22:52 jasong jasong 11 2013-02-13 01:36 davar55 Miscellaneous Math 36 2011-01-19 15:21 davar55 Puzzles 6 2007-06-12 00:00

All times are UTC. The time now is 21:55.

Wed May 5 21:56:00 UTC 2021 up 27 days, 16:36, 0 users, load averages: 3.12, 2.69, 2.70