mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2016-12-08, 04:49   #1
WraithX
 
WraithX's Avatar
 
Mar 2006

11×43 Posts
Default 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.
WraithX is offline   Reply With Quote
Old 2016-12-08, 05:46   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·11·107 Posts
Default

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).

Batalov is offline   Reply With Quote
Old 2016-12-08, 06:10   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×11×107 Posts
Default

...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
Batalov is offline   Reply With Quote
Old 2016-12-08, 12:59   #4
WraithX
 
WraithX's Avatar
 
Mar 2006

11×43 Posts
Default

Quote:
Originally Posted by Batalov View Post
...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!
WraithX is offline   Reply With Quote
Old 2016-12-08, 15:21   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

are you trying to figure out the vertex problem that inspired graham's number ?
science_man_88 is offline   Reply With Quote
Old 2016-12-08, 17:02   #6
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Brady

2×33×7 Posts
Default

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).
jwaltos is offline   Reply With Quote
Old 2016-12-08, 17:48   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·11·107 Posts
Default

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<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 co-planar 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).
Batalov is offline   Reply With Quote
Old 2016-12-09, 03:41   #8
WraithX
 
WraithX's Avatar
 
Mar 2006

7318 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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:
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.
WraithX is offline   Reply With Quote
Old 2016-12-09, 13:02   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by WraithX View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-12-09, 14:40   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2016-12-10, 15:57   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1100001100012 Posts
Default

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]
https://plus.google.com/117663015413...ts/KJTgfjkTZCQ

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)
ATH is offline   Reply With Quote
Reply

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 2016-06-25 08:30
New Pattern Found in Mersenne Exponents PawnProver44 Miscellaneous Math 6 2016-03-11 22:52
Prime pattern thoughts jasong jasong 11 2013-02-13 01:36
A Pattern That Is Not davar55 Miscellaneous Math 36 2011-01-19 15:21
Initial Pattern 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.