Coloring a sphere

[Tom Sirgedas]

Given a hex pattern on the plane, I think you can insert a thin repeating layer of tiles like this to alter the pattern.

I'm hoping you can mostly tile an icosahedron using this technique. Each edge of the icosahedron would have such a layer (or multiple layers?), allowing the hex patterns to match up. Only space near the vertices of the icosahedron would be left untiled.

If this is possible, then maybe that pattern can be projected to a sphere, if the entire pattern is flexible enough.

[Tom Sirgedas]

Here's the dual graph. You can see that the construction is pretty simple, you just delete some edges.

[Tom Sirgedas]

With a hexagonal grid, you can take large triangular sections and fit 6 of these sections together seamlessly. But, for tiling an icosahedron or sphere, it seems useful to fit 5 of these sections together. It's possible to slightly warp the hex grid to make the triangular sections 72 degrees each at the corner where the 5 meet.

The problem is that the hexagons don't match at the seams. You can easily make 4 of the seams match the color pattern, but the 5th seam will be wrong. However, this can be fixed! (And in a rotationally symmetric way, with colors being permuted). You can make each seam nearly match the pattern of the two triangles it separates, so that only two adjacent colors are swapped. Then, in the dual graph, simply delete some edges along the seam to resolve conflicts. This introduces some sizing constraints along the seam, but there is still some flexibility.

Below are the dual graph (white arrows correspond to edges that must be curved) and graph (black lines indicate that the edge/diagonal must have unit length).

[Tom Sirgedas]

Here are the colors at the seams. Note that there's always one error at the seam, where the 3rd and 4th elements (where 0 is always the first element) are swapped.

[Tom Sirgedas]

I think this same scheme can be in a symmetric way for the icosahedron, but I suspect 2 or more seams will be necessary at each icosahedron edge. It's hard to wrap my mind around the permutations.

[t.sir...@techsmith.com]

https://dustingmixon.wordpress.com/2020/05/11/polymath16-sixteenth-thread-writing-the-paper-and-chasing-down-loose-ends-ii/#comment-25502

From the polymath discussion, it seems that the pattern should be extendable to cover all 12 icosahedron faces without a problem!

[Tom Sirgedas]

There are 3 more configurations possible.

- The 5th/6th elements can be swapped instead of the 3rd/4th

- The left edge of the triangular wedges can border the hole, instead of the right edge

So, there are 4 configurations

[Aubrey de Grey]

Thanks Tom - great. I feel I am really close to a solution now (yeah, I know...) .In that uncoloured pentagon of 16 tiles, if each corner can be coloured the same as the middle of the opposite edge, I think we're done - basically the inner ring of hexagons can be collapsed to something like a Gibbs disk and the central pentagon made one of the two special colours. Looks like you can do that with a manageable number of rigidifications?

[Tom Sirgedas]

I haven't gotten anything to work yet. The above is really close, but not quite right.

[Aubrey de Grey]

Wow, that does look good. I’m not seeing where it fails - can you point it out?

[Tom Sirgedas]

There's a blue/yellow conflict highlighted.

Also, the red tiles look like they might be too close together, but I'm not sure on that one.

[Aubrey de Grey]

Thanks. Hm, I think my design may fix that. Basically the mapping between our designs is that you have the orange tiles a level further out and you fuse the resulting same-coloured tiles that share an edge. I have a picture now with all the rigid EDs - will send itby email

[Tom Sirgedas]

Yeah, some of the red tiles are slightly too close together, but they can be nudged apart.

Also, the blue/yellow conflict can be nudged to work as well. But all of these conflicts combined are too touchy to solve simultaneously with just manual nudging in the simulator.

I think I'll try adding rules in the simulator for just these vertices to see if it can resolve the conflicts, but I'll also add a few more layers to the whole graph to make sure it's all compatible.


I can try your design in the simulator once you send it

[Tom Sirgedas]

Hmm, my design is flawed, because the outermost curved edge matches the tile color of the unshown next layer of tiles, at the indentation of the outer layer.

[Aubrey de Grey]

Maybe we shuld attack this from the other end: start from the central hexagon and see how far out we can build using seven colours but without caring what the edges look like. Then we can look at stitching it to the regular tilings of the faces. If we get stuck too early, we will know this is not possible.

[Tom Sirgedas]

Yeah, I modified my searcher to search for a 7-coloring with 5-way rotational symmetry. Unfortunately, it finds very huge disks that follow the rules, but don't actually work. I tried manually verifying the disks in the simulator at increasingly large search depths. However, there are way too many for me to verify them all. So, I only verified a random sampling (like 50-100 or so graphs at each search depth.) I'm at a depth where the graphs have I think 56 tiles each, but most of the valid graphs seem like they will be dead ends soon.

I'll pursue that a bit more, but I have another idea where I'll manually start with a full graph, and let a SAT solver symmetrically color the graph and delete some edges. This would somewhat mimic my by-hand approach, and it has the advantage that the structure of the solution would be compatible with the rest of the graph by design. It still would need manual verification, but I doubt it will produce a ton of solutions.

[Tom Sirgedas]

 

Here are two examples with I think with 61 tiles, and the third has 76 I think. I think an important feature for them to grow bigger is to not have too many rigid EDs, especially entangled groups of them. This gives flexibility to expand. Also, ideally, new layers can use a hexagonal pattern, meaning no EDs (though you'll always need a seam somewhere).

This approach is super tedious, and I think most of the graphs are subtly flawed anyways. But, it's convincing me a bit that a rotationally symmetric solution exists. It seems that as I search deeper, the candidates at each search depth slowly keep multiplying.

[Tom Sirgedas]

I turned the tiling into a SAT problem and gave it the most basic rules. The result gets very crumpled, I think because there are so many rigid EDs. I'll see if I can add some SAT rules to limit the number of rigid EDs allowed.

[Tom Sirgedas]

 

Cool, limiting the rigid EDs seems to work great. The first graph I got was unstable, but the simulator likes this second one! So, that's great news for a solution existing.

The SAT formula has 485708 clauses, so I'm not sure how much bigger I can make the "template". The template is the left image, but with all triangles.

The SAT rules allow freedom to pick colors, and delete edges in the template. BUT, the solver isn't allowed to delete consecutive edges (from the perspective of a vertex in the template). This simplifies the SAT formula and doesn't seem too useful anyways.

Our manual attempts used a template with fewer vertices, so that can be something to try.

[Tom Sirgedas]

Here's a few results with 6 layers around the center instead of 5. The simulator likes all of these, but it doesn't guarantee they're valid.

I think I'll try telling the solver what the colors on the outer layers should be

[Tom Sirgedas]

OK, I remapped the colors.

Here the outer ring matches the appropriate ring in the first configuration (the image on the right).

Unfortunately, the SAT solver is saying "no solution" when I tried fixing just 4 tiles in the next layer in instead. Maybe allowing more rigid edges or changing the template would help.

I think maybe specifying that layer is making it hard to lay out the 2 special colors efficiently? I'll try adding another layer and seeing if that can be fixed.

[Tom Sirgedas]

I only get a solution if I allow more rigid EDs, but here the outer two layers match colors with the first configuration (original graph). The simulator does NOT like this graph

[Tom Sirgedas]

Simulator likes this one though

[Tom Sirgedas]

OK, I recolored the 4 configurations so that they all follow the same color scheme.

Now the colors permute like this when rotating clockwise 72 degrees:

red -> blue -> yellow -> purple -> green

[Tom Sirgedas]

(zoomed version -- click to see full resolution)

I slotted a SAT solution into the config 4 graph, and the simulator likes it! The simulator only enforces distances between vertices, so curved edges and edge-to-vertex distances might be still be less than unit distance. 

[Aubrey de Grey]

Woo hoo!! What an achievement. It looks really quite simple in the end. I was never brave enough to put a rigid edge (as opposed to a diagonal) so close to the centre. Massive congrats. I don't see any non-rigids that look remotely short enough to endagner this tiling (do you?).

[Tom Sirgedas]

Thanks!! I allowed the solver to alter up to 5 layers away from the center, but I'm not sure how much it altered.

Yeah, it looks pretty good to me. I marked a few places that might need to be checked, but they all seem to be unlikely or easily nudged.

I'm sure there are a bunch more solutions. I never even tried removing some tiles from the template, but maybe that's not so important if this solution works.

So, now we have a tile pattern, but does it actually work on the sphere? Maybe I need a sphere version of the simulator?

[Aubrey de Grey]

I don't know about there being a bunch more solutions actually (unless one resorts to even bigger corner regions), given it was so hard to find this one - but as you say, who cares, one is enough.

I don't think there is any issue with mapping this onto a sphere. That would only arise if there were a cycle of rigid EDs around the centre that was somehow constrained to be rigid overall, like a hexagon with its centre, and you definitely don't have that. But post this to the blog and others will have a look too.

[Tom Sirgedas]

Here's an animation between config 4 and the SAT solution

[Aubrey de Grey]

Interesting! What is forcing that twist? - can't the centre just be maybe 20 degrees clockwise from how you have it?

[Tom Sirgedas]

i tried manually nudging the center and I can twist it a bit

[Aubrey de Grey]

Thanks. Some of the inter-tile distances are starting to look risky there...

Ah, here's a thought. Your simulator can work within additional constraints, specifically you maximised the 5-disc by stipulating how far out the perimeter vertices are. Can you stipulate that all inter-vertex distances that are not exactly 1 must not be within 1 +/- epsilon, and see how big you can nudge epsilon to? Of course the possibility will still remain that curves bring tiles too close together, but with a sizeable epsilon it will be easier to solidly eliminate that risk.

[Tom Sirgedas]

Hmm, yeah I'm thinking to make a simulator for this graph mapped to a sphere. I can play with adding specific distance rules, including an extra epsilon

[Tom Sirgedas]

It took me quite a while to wrap my head around around getting the color permutations right, but I think I got it.

The image is an icosahedron, with all 12 vertices colored. Opposite vertices share colors, so there are 6 colors in all. Cyan is the 7th color and it doesn't get permuted. (I thought orange was the 7th color for the longest time, oops!)

Each face of the icosahedron is divided into 3 quadrilaterals, and the hexagon tile pattern is drawn on each. The hex pattern is exactly the same for each quadrilateral, but with colors permuted in a way that matches how the icosahedron vertices get permuted.

The numbers on each quadrilateral aren't really important. But, 2113 means that the matrix transform for getting from 0000 to 2113 is A^2*B^1*C^1*D^4, where A,B,C,D are 3-d matrices. So, each of the 60 quadrilaterals effectively has a matrix and a color permutation associated with it.

Oh yeah, and I assigned colors so that they match up with the picture on the right. Like, in quadrilateral 0000, from left to right the colors go orange, red, cyan, green, yellow, blue, purple. This matches the left-to-right sequence in the top-right section of the tiling. You can check that all 5 quadrilaterals incident to the orange icosahedron vertex have a hex pattern that matches the tiling image.

Next, I'll position the hex pattern dots approximately at the tile centers, so that the hex pattern becomes continuous across the quadrilateral boundaries.

[Tom Sirgedas]

I mapped the hex patterns to each quadrilateral. The hex pattern spills out of the quadrilateral slightly. I made the dots bigger for the hex pattern associated with quadrilateral 0000. You can see that the dots spill into 1001.

The hex pattern for adjacent quadrilaterals on different icosahedron faces ALMOST matches, but two colors are swapped, so there will be a seam along those boundaries.

The dots near the icosahedron vertices are missing for now.

The quadrilaterals don't line up exactly, so you'll notice some double-dots near the quadrilateral perimeter. I think with the linear mapping I'm doing, this is unavoidable?? It's unfortunate, but I don't expect it to cause big problems.

Each quadrilateral is drawn with the same logic, just with a different color permutation and matrix transformation.

Growing the pattern by a multiple of 7 tiles seems to work without any special handling.

[Tom Sirgedas]

I further divided the quadrilateral into 2 triangles (with icosahedronal symmetry), so that I could pin the hex pattern to the center of the icosahedron face. So, now the pattern alignment within a single icosahedron face seems very good. Also, this allows the icosahedron to morph into a 120-face object, where all the vertices are the same distance from the origin. I think this will lessen the distortion when projecting the entire graph to a sphere.

[Tom Sirgedas]

Here's the dual graph, but with the seam's edges completely removed. Only 4 of every 14 edges need to be removed, but I think this is helpful to understand what's going on.

[Tom Sirgedas]

The tiles are laid out properly now, based on the dual graph. Still need to write a simulator to move the vertices into valid positions. Also, some edges need to be curved.

[Tom Sirgedas]

I got a basic simulator working. So far, it's only considering vertex distances.

Also, I'm not yet drawing curved edges. And there's drawing artifacts at the edge of the sphere.

Anyways, with the simulator so far, the smallest configuration seems to simulate fine for a sphere radius in the range [8.2, 9.77].

Extending the pattern allows for spheres with bigger radii to be tiled. The last image is showing a result with 5 extensions. You can see the "megatile" I'm using basically has 6 sides.

Oh, and when I attempt to simulate a small radius (47) for the large pattern, the hex pattern turns into something like this, which I think is invalid, even though the vertices are spaced properly.

[Aubrey de Grey]

Fantastic work Tom! That last pattern looks like it should work down to a certain minimum diameter of the small tiles. I guess the question is how large you need to go before the radius ranges doable with successive numbers of repeats start to overlap.

[Tom Sirgedas]

Thanks!

Yeah, I'm curious about finding the overlap. Though, I think shrinking the radius makes the pattern crumple in a somewhat arbitrary way. So, I probably won't be able to find the true smallest radius for a given tile pattern. But, I think the results will still be kind of interesting.

[Aubrey de Grey]

Right, it's bound to get gnarly at the extremes of such a range - probably each gap between ranges will need separate handling.

[Tom Sirgedas]

Oh yeah, I suppose it would be nice to have a coloring for every radius. I'm not so interesting in pursuing that, at least for now.

[Tom Sirgedas]

drawing curved edges works now

[Tom Sirgedas]

I found a nice way to calculate an arbitrarily accurate "zone of exclusion" on the surface of a sphere.

Also, my app now allows interactive nudging of vertices.

The simulator produces a slightly invalid graph on its own (for a radius of 9.5). But some quick nudging seems to easily fix the problems. I posted 7 images, one for each tile color. It's really nice to prove to myself that the tile spacing really is valid. Also, it helps identify rules that should be added to the simulator.

Here are the two conflicts the simulator doesn't yet handle (cyan and then purple):

[Tom Sirgedas]

The zones of exclusion are super-helpful when trying to minimize the sphere radius. Here R=8.1, and everything is squished and messy. But the zones of exclusion overlay makes the numerous problems obvious.

[Aubrey de Grey]

Hey Tom - given all this new power you have added to your simulator, I'm wondering whether you can use it to explore sphere-tiling with fewer colours. As of now, the records for how large a sphere can be that is tiled with 4, 5 or 6 colours are extremely boring (a tetrahedron, a square pyramid and a dodecahedron) - the only exception is an octahedral 4-colouring of a shpere with circumference exactly 4. I came quite close to a 36-tile 6-colouring but it wouldn't quite work. I would expect that any new design would only work with specific radii, but who knows?

[Tom Sirgedas]

Hmm, yeah, that might be fun to explore. I remember the 36-tile guy.

I don't know how to generate interesting candidates to test yet, but I'll give it some thought. If a design only works for one specific radius, then it's probably because there's a rigid network of rigid EDs.

[Tom Sirgedas]

I got the simulator to detect and nudge vertex-edge distance violations, for both "straight" and curved tile edges.

So, now output from the simulator seems very reliable so far. I mean that if the simulator tells me that the sum of the distance violations is .00000000001, then the graph is really valid. It still won't detect a distance violation caused by two curved edges being too close to each other, but I haven't noticed this being a problem. (Not sure if it's even possible with the pattern I'm using).

So, the image above is for radius=9, which seems to work fine. You can see that the zone of exclusions nearly overlaps a few red tiles, but the simulator prevents an overlap (to within a minuscule tolerance -- it might be nice to require a distance of 1.00001 or whatever where possible, like you suggested before, to remove any minuscule overlap).

But, getting this graph still required some manual nudging, otherwise the graph would crumple in a wrong way (when gradually reducing the radius from 9.5 to 9. Larger radii have unique and clean layouts, but smaller radii can be crumpled in many different ways).

The extra logic is making the simulator slowish, so simulating larger graphs will be a pain.

Anyways, the basic pattern seems to easily produce a valid result for radii in the range [9.00, 9.77]. I can output coordinates, or whatever, but I'm not sure in what format, or if it's even useful for anyone.

[Aubrey de Grey]

All great. I think requiring a minimum epsilon is quite important. If you can find a radius around 9.5ish that allows a respectable epsilon, like 0.01 or more, then you will have something that's good enough to convince everyone. I presume you still have full symmetry, i.e. the sphere surface divides into 60 regions each corresponding to 1/3 of a face of an icosahedron, yes? If so, then actually it would be good to describe the coordinates of the vertices of one such region, as there won't be an unmanageable number of them. (How many tiles do you have in total for this size of sphere?) Centre one pentagon at the North pole (x=y=0, z positive) and one other pentagon on x=0 and y positive, and then use polar coordinates.

In combination with Agoston's result, this will be the first time that anyone has shown, in any setting, that one can use fewer colours with an unscaleable tiling than with any scaleable one. So it's a big result. Let's plan to get it out in the last 2020 issue of Geombinatorics.

[Tom Sirgedas]

Okay, I'll work on adding a minimum epsilon! For graphs with induced rigid EDs it will cause trouble, but hopefully it won't otherwise cause trouble.

Yeah, 60-fold symmetry. My code is only keeping track of 62 vertices. It seems that there are 2012 tiles. 33 tiles are copied 60 times, plus 12 pentagons at each icosahedron vertex, plus 20 hexagons in the middle of each icosahedron face.

I like using euclidian 3D coordinates. The vertices of the icosahedron are at (±PHI, ±1, 0), (±1, 0, ±PHI), (0, ±PHI, ±1). Either way, the rigid EDs won't be exactly 1 unit apart without infinitely precise coordinates.

[Tom Sirgedas]

Okay, the padding was pretty straight-forward to add, and a padding of .01 didn't cause any trouble for this graph. So, the only errors should be vertices connected by rigid EDs not being EXACTLY distance 1 apart.

There are 62 vertices, and 60 matrices, so 3720 vertices in all. (Each matrix multiplies each vertex.)

The vertices and matrices are defined below. X axis points to the right, Y up, Z away from you.

How tile colors are permuted is not obvious. But, how I calculate it is that each icosahedron vertex is defined with a color, and when you pick one of the 60 matrices, the colors are permuted accordingly. So, the matrix will permute the icosahedron vertices, and the colors are permuted in the same way.

sphere radius = 9.5

a = (√5 - 1)/4 = 0.30901699437
b = .5
c = (√5 + 1)/4 = 0.80901699437

     | a  b  c|
m0 = |-b  c -a|
     |-c -a  b|
               
     | 1  0  0|
m1 = | 0 -1  0|
     | 0  0 -1|
     
     |-1  0  0|
m2 = | 0 -1  0|
     | 0  0  1|
     
     |-b -c -a|
m3 = | c -a -b|
     | a -b  c|


M = m3^{0,1,2} * m2^{0,1} * m1^{0,1} * m0^{0,1,2,3,4}  (60 matrices)

 0: -3.775502479886 -0.057755691602 -8.717353113443
 1: -4.115594485945 -0.540276579254 -8.545173096267
 2: -4.636369962558 -0.326640417681 -8.285371422443
 3: -3.389649875341 -0.205518565223 -8.872318515583
 4: -3.424607719004 -0.712025969777 -8.832614617954
 5: -3.917713528010 -0.858587611227 -8.611872504066
 6: -2.527022643533 -0.437393706490 -9.147286116909
 7: -2.872030488212 -1.040381501783 -8.995501498278
 8: -3.242768502831 -1.060915707624 -8.866166606734
 9: -3.036074193596 -0.105570809550 -9.001172606675
10: -1.975053504086 -0.874316210924 -9.251201804053
11: -2.197460459890 -1.370901829389 -9.140120114167
12: -2.702599970790 -1.398290466226 -8.999485383617
13: -2.478290418082 -0.447511031765 -9.160120658599
14: -1.315245616588 -1.164806721767 -9.336131654437
15: -1.565987228982 -1.774423749588 -9.200494788628
16: -2.079581675235 -1.749000684638 -9.103094894659
17: -1.650929244381 -0.881843043715 -9.313795438826
18: -3.745985055863  0.522144094227 -8.714640641249
19: -2.945159086021  0.408386212935 -9.022707944908
20: -3.223906287806  0.755140498571 -8.904279368644
21: -2.159940393296 -0.093573522135 -9.250724376683
22: -2.311081892314  0.537647410998 -9.198904051487
23: -1.520648006529 -0.317683875115 -9.372123910605
24: -1.648306545055  0.034256320852 -9.355849081618
25: -0.769955002642 -0.453791807837 -9.457866688056
26: -0.952513372773 -1.128255863250 -9.384548842738
27: -1.037573972589 -0.220304171877 -9.440598832874
28: -3.189080866314  0.913118148957 -8.902021033123
29: -2.778580421177  1.393358312113 -8.977084351677
30: -1.626256731648  0.538709203262 -9.344253926188
31: -2.005431752708  0.820657483870 -9.249581870517
32: -1.079758640714  0.485942813779 -9.425920690285
33: -0.226589771619 -0.030792491646 -9.497247437961
34: -0.600738708153 -0.390601155144 -9.472937439999
35: -0.388709862990  0.422179192564 -9.482650967519
36: -1.897684831964  1.034006173411 -9.250925548932
37: -2.396344206321  1.525023883788 -9.065419824735
38: -1.084041687873  1.093046820461 -9.374438770787
39: -1.450767159590  1.368917898479 -9.288236562226
40: -0.149288985120  0.850661057040 -9.460660049117
41: -0.628441712052  1.377052825729 -9.378634577043
42:  0.051338519746  0.875636556901 -9.459419906982
43: -2.048391466278  1.993586747350 -9.059785001956
44: -1.476955960123  1.854550524543 -9.199415385978
45: -1.687565110410  1.994324838359 -9.133717339464
46: -0.525125607650  1.638718292095 -9.342849964296
47: -0.829735822405  2.040490441277 -9.241100433610
48:  0.241523070694  1.289536413656 -9.408972443587
49: -0.116219713083  1.731325939410 -9.340182196821
50:  0.748898830968  1.364198888912 -9.371665376680
51: -1.524059351148  2.696465575844 -8.980886175232
52: -1.822191295133  2.933250571571 -8.850178527483
53: -0.796420429437  2.425225267159 -9.150628224505
54: -1.058281062994  2.736571199776 -9.035553068864
55:  0.106446495132  2.109436692428 -9.262232235499
56: -0.257406614078  2.546863687641 -9.148618867983
57:  0.738572833116  1.936537421595 -9.271155968106
58:  0.433019226446  2.242547778909 -9.221359650769
59: -0.883379115332  3.245577013054 -8.884586157550
60: -0.127559401664  2.981005495815 -9.019275737717
61: -0.462834052749  3.319859645624 -8.888999750983

[Aubrey de Grey]

That was fast! I think if you can go a bunch bigger with epsilon, like 0.05 or even 0.1, that would be even better.

[Tom Sirgedas]

I tried with .02 and even that didn't seem to be converging to an answer, or it was, but really slowly.

[Tom Sirgedas]

Hey, here's a simple-ish approach to finding sphere colorings for small spheres:

- first, find the dual graph

  - simulate 21 unit vectors in 3-D space, where vectors mutually repel each other

  - triangulate the vertices

  - SAT-solve for a coloring on the dual graph (with only a few rules)
    - minimize the number of rigid EDs (my rigid ED-counting with SAT clauses is a bit flawed, but good enough)
    - allow edges to be deleted, but no triangle can have more than one edge deleted
- create the graph from the dual graph

- simulate the graph by trying a few different radii and seeing if "works"

(This provides a graph with 21 tiles)

The graph above seems to work for radii in the range .88 to .998.

I wrote this code last week and mostly gave up on it because SAT-solving with 7 colors returned graphs that didn't work for 17 to 20 tiles. For 16 tiles it worked, but the graph was radius ~.825, which is smaller than the 6-colored dodecahedron. For 28 tiles it doesn't return an answer within a few days. For 21 tiles, it took 4 hours to find this result "with 11 rigid EDs" (there are more like 21 rigid EDs).

Anyways, my search technique isn't exhaustive, and depends on the initial unit vector positions, too.

I really like visualizing the results, but it's really awkward with a sphere :/

Here's a video of the graph. Let me know if there's a better way to present it!

https://youtu.be/c3MmnWgmuuc

[Tom Sirgedas]

Also, I simulated some of the polymath wiki shapes, and found that the dodecahedron doesn't work for .577 to .612, but a cube does. (I haven't verified by hand though.)

.000000 - .577350 [5 colors] square pyramid

.000000 - .612372 [6 colors] cube

.612372 - .866025 [6 colors] dodecahedron 

[Aubrey de Grey]

Wow, I wassure we had checked the dodecahedron lower bound - evidently we messed up! Thanks - please post this on the polymath blog. As for the 21-tile thing, yay, very nice - and yes, I wonder if some symmetry can be extracted - I think at 2:15 where you highlight some symmetry, you have something - there is a red/blue/cyan vertex on the left at about 1:29 that I think is the counterpart of that yellow/orange/purple one?

[Tom Sirgedas]

oh yeah, i think you're right. I think those two vertices are the North and South pole, and spinning the globe 120-degrees only permute the colors (3-way symmetry), also flipping the North/South poles is probably symmetrical. So, 6 of the colors permute, and then the 7th color, green, has 3 tiles that lie on the equator. Cool, that makes the graph a lot more elegant and easier to understand. I'll make a nice visual for it when I have some time (and post on polymath). Also, I think I had some "padding" enabled in the simulator, so hopefully radius 1 is covered by this graph when the padding is removed.

Aaand... it seems useful to pick some symmetry in advance (like the 6-way symmetry), and then SAT-solve. Much bigger graphs could be searched this way (and results would be more elegant). Though, I'll need to give some thought to sphere symmetries. Like tetrahedron symmetry is confusing to think about (might be useful to 7-color with 28 tiles)?

[Aubrey de Grey]

Great. Do also try with six colours - I'm far from convinced that larger spheres are impossible. Also, if you're picking your radius in advance you will be unable to find examples where only a particular radius works (because the EDs link up all over the sphere) - maybe you can get around that by allowing some slop in the distances (the opposite of what you did with 0.01 for the large sphere). As for symmetries, hm, tricky. What about just trying to grow the basic 21-tile pattern by treating it as six triangles of three tiles plus the three green ones, and trying the same pattern with the triangles each being made of six tiles rather than three, plus some tiles at the equator? I have a feeling that some of the symmetries that work may be quite exotic - but I also suspect that good ones will appear pretty reliably irrespective of the initial vector positions. I suggest to try 24 next.

[Tom Sirgedas]

Yeah, it would be nice to get a bigger 6-colored sphere. I can give that a quick try at least. But, until recently I was pretty discouraged even with finding 7-colored spheres.

I'm not picking the radius in advance -- picking the radius is the final step. I try a few different radii in the simulator and see if anything works. The simulator tells me what the total error is (e.g. if two vertices must be less than 1 apart, but are actually 1.02 apart, this adds .02 to the total error), so this quickly gives me insight if the radius needs to be bigger or smaller.

I'm not constructing the graph myself, I let the SAT-solver do it. I'm not clever or patient enough for that, haha. I'll try just using 2-way symmetry to start, which hopefully with allow searching up to 30-some-tile spheres. But, I don't know how the 21-tile symmetry works exactly yet. There's some sort of North/South mirroring, but it's not exact. I'll study that first.

[Tom Sirgedas]

the SAT solver quickly says "no solution" for 6-coloring this 24-vertex starting graph.

BUT, I'm not sure this starting graph is ideal. It's hard to tell if it's symmetrical or not. The yellow vertices have 5 neighbors, and cyan vertices have 6. The SAT solver is allowed to delete some edges and recolor the vertices.

[Tom Sirgedas]

For 30 vertices without a rigid ED limit, I DO get a 6-colored graph, but it's horribly invalid with all the rigid EDs.

[Tom Sirgedas]

OK, so here I rotated the sphere so that there's a North/South pole, and slightly modified the graph to make it actually symmetric (now there are exactly 18 rigid diagonals).

It seems to work for radii in the range .84 to 1.005.

The colors purple/yellow/blue and red/orange/cyan are permuted as the globe spins 120 degrees.

There's no North/South symmetry though. You can see that at the bottom there's band of tiles on the Southern hemisphere that goes blue/yellow/purple/blue/yellow/purple as the globe spins, where all six tiles have a similar shape. The corresponding red/cyan/orange/red/cyan/orange on the North hemisphere is goofier. (But this goofiness is needed to make room for the green tiles.)

[Aubrey de Grey]

Thanks. Right - I see that the purple/blue/yellow sextet are not precisely identical either, as the latitudes of vertices 21 and 28 are not the same - the shapes alternate. Cool that you pushed it beyond 1 - and, perhaps even more importantly, that the lower bound is less than the upper bound for the dodecahedron. It's a really elegant tiling.

Can you show the version with radius 0.84? It would be nice to see how the compression shifts the near-equatorial vertices.

Also, in these visualisations, I suggest you make the rigid EDs thicker, to be more obviously different from non-rigid edges. At present it is not immediately obvious that (for example) the green/orange boundary 21-31 is not rigid.

(Apropos, though, perhaps the maximal radius occurs when 21-31 is indeed 1? Is 21-28 also 1?).

No other news, I take it (6-tilings, or larger 7-tilings)? It would be so cool if you can find a sequence of designs that extends far enough to reach the range that can be done with the "large sphere" pattern. (I do remember that there are also gaps between the "large sphere" ranges for given numbers of stitches per icosahedron edge, for a few small such numbers - did you ever work out how many stitches per edge you need to go up to before those ranges start to overlap?)

[Tom Sirgedas]

Oh, I just noticed that the simulator isn't enforcing vertex-to-line distances. Above, the purple tiles are almost certainly too close. The green/purple edge can safely be curved though. Hmm. (I could enforce vertex-to-line distances, but that would push the vertex/line away from each other instead of just considering a curved line. Maybe I'll just display the vertex-to-line violations instead of enforcing them.)

21-31 is .964, but 21-28 is 1, when the radius is 1.005. 21-28 is .998048 when R = 1.004. Note that vertices 34, 31, 28 all have EDs to both 5 and 21. So 31 (the middle vertex) to 21 must have length < 1.

Hmm, 6 diagonals form an "equator", so it's a bit suspicious that R > 1. I suppose the diagonals must all be north of the equator.

No other news... I tried some 6-tilings but those are quickly rejected by the SAT solver. The SAT solver is too slow to 7-tile 24 tiles. Well, it's too slow when I want to minimize rigid EDs (and the graphs seem hopeless without minimizing rigid EDs). I should be able to search bigger graphs if I assume some symmetry.

did you ever work out how many stitches per edge you need to go up to before those ranges start to overlap

The simulator is kind of slow even for the base case "large sphere". I can probably get the range for the next larger sphere by simulating for a day or so (??).

[Aubrey de Grey]

Hey - what's the latest? Is it time to update the Polymath group?

[Tom Sirgedas]

I haven't spent much time working on this. I did try to make the dual graph symmetrical ((x,y,z) maps to (-x,-y,-z), for vertices and edges, but colors are forced to be symmetrical), but that didn't allow larger graphs to be quickly SAT-solved like I expected, unfortunately.

Feel free to post in Polymath about this, or let me know what I should cover and I'll get to it eventually.

[Tom Sirgedas]

Starting with an icosahedron to tile, assign 6 colors to the 12 icovertices. Each pair of diametrically opposite icovertices get the same color. The 7th color, cyan, is unused here. These colors aren't directly used, but only control how colors will get permuted.

Now, all tiles placed will have 60 copies, following icosahedronic symmetry. Colors for the copies are relative to the chosen icovertex colors.




We want each face of the icosahedron to have a honeycomb pattern of tiles. We only have freedom to play on one icoface, and the others will be forced.
In the above image, the isolated red, blue, and yellow dots correspond to icovertices of those colors. It so happens that only 2 different honeycomb pattern permutations are possible. (One of them is shown above)

We can change the offset of the honeycomb pattern. For now, let's choose a red dot in the hex pattern to go to the red icovertex (which is the case in the above image). Now, let's pick a blue vertex to assign to the blue icovertex. 

Let's say we pick this one

Now, we really only care about two of these hex patterns and how they'll map here:

The two hex patterns must have a seam between them, and that seam must be symmetrical.  


Now I just rotated the image and adjusted the position of the seam between the two hex patters, so that it's halfway between the blue and red vertex.

Now all the dual graph vertices on the icosahedron (or the tiles of the Goldberg polyhedron) are defined and colored. Just the edges near the blue/red vertices may need special handling.

If the blue/red vertex distance is very small, then this structure doesn't make too much sense, but following it approximately can still give very nice results.

On Saturday, December 12, 2020 at 3:28:11 AM UTC-5 Tom Sirgedas wrote:

Starting with an icosahedron to tile, assign 6 colors to the 12 icovertices. Each pair of diametrically opposite icovertices get the same color. The 7th color, cyan, is unused here. These colors aren't directly used, but only control how colors will get permuted.

Now, all tiles placed will have 60 copies, following icosahedronic symmetry. Colors for the copies are relative to the chosen icovertex colors.



We want each face of the icosahedron to have a honeycomb pattern of tiles. We only have freedom to play on one icoface, and the others will be forced.
In the above image, the isolated red, blue, and yellow dots correspond to icovertices of those colors. It so happens that only 2 different honeycomb pattern permutations are possible. (One of them is shown above)

We can change the offset of the honeycomb pattern. For now, let's choose a red dot in the hex pattern to go to the red icovertex (which is the case in the above image). Now, let's pick a blue vertex to assign to the blue icovertex. 

Let's say we pick this one

Now, we really only care about two of these hex patterns and how they'll map here:

The two hex patterns must have a seam between them, and that seam must be symmetrical.

Now I just rotated the image and adjusted the position of the seam between the two hex patters, so that it's halfway between the blue and red vertex.

Now all the dual graph vertices on the icosahedron (or the tiles of the Goldberg polyhedron) are defined and colored. Just the edges near the blue/red vertices may need special handling.

If the blue/red vertex distance is very small, then this structure doesn't make too much sense, but following it approximately can still give very nice results.

[Tom Sirgedas]

Here's GP(2,1). It's not valid, but so close.


GP(2,2). Also, not valid, but close.

[Tom Sirgedas]

Hmm, so I was wrong that you can pick any blue dot. It has to be in the bottom right hex pattern.

Otherwise you'll get a "bad" hex pattern on each icoface.


Also, here are some boring videos where I explore some of these ideas:

here's an intro video: https://youtu.be/lRweGYsIUIA (~10 minutes)

here's a video constructing GP(7,1): https://youtu.be/TzIeo7rl69k (~9 minutes)

here's a video for GP(2,1) and GP(2,2): https://youtu.be/e367PZAGii4 (~6 minutes)

[Tom Sirgedas]

GP(4,3) works! Radii in the range [3.44, 4.25] all seem to work.

 

[Tom Sirgedas]

So the original sphere solution here is GP(11,5), and it uses the "blue dot" from the upper right hex

Hmm, well that probably isn't very clear what I mean.


Here the black boundary indicates where the hex pattern for one icoface is applied.

Normally the dashed line is sloping up slightly instead of sloping down, so that the red icovertex is above the blue one, relative to the seam (dashed line).

This apparently works, but the seam is a bit jagged near the icovertex. (This might be why it was tough to fill in the icovertex hole.(?))

[Tom Sirgedas]

 

Here's GP(11,3), which is basically an extension of GP(4,3)

The two images are slight variations (most noticeably if you look at the rigid EDs near the icovertices)

[Tom Sirgedas]

 

Here's the original tiled sphere recolored, on the left. If you look at the purple/cyan tile pairs above/below the equator you'll see that they swap positions below the equator.

But, my original tiling is a little goofy in that the 2 purple/cyan pairs crossing the equator (in the center) have the "wrong" arrangement. But it still works.

On the right side I "fixed" this.

Here's an animation between the two:

[Tom Sirgedas]

GP(8,5) is *extremely* elegant. In the dual graph only 2 edges need to be deleted! (each deletion shows up as 6 rigid EDs). (And, there are two ways to accomplish this -- but the one I'm showing allows a max radius of 8.008 instead of 7.96)

The radius can range from 6.7 to 8.008  (radii less than 6.7 might be possible, but simulating these is slow).

I'm pretty sure all spheres of the form GP(4+4k,3+2k) will be just as nice.

Unfortunately setting k=.5, for GP(6,4) doesn't seem to work. The tiles halfway between the blue/red icovertex can't seem to be resolved. 

(sorry forgot to draw "curved edges" for the r=8.008 image)

[Tom Sirgedas]

GP(12,7) is similarly elegant. It was tedious to input the vertices and get them to line up right. Maybe it really wouldn't be too hard to programmatically position the dual vertices.
radius range is [~9.5, 11.78]. Note there's a tiny tear at the center of the icoface, but it shouldn't have any effect.





Here's the wobbly dual graph I used. I think it partly explains why the hexes are squished how they are in the r = 9.5 image.

[Tom Sirgedas]

I can now generate the dual graph vertex coordinates by code. So the tile graphs are nearly valid even before simulation.

One reason they are slightly invalid is because tiles near the icovertices are more squished. This can be "fixed" by pushing vertices away from the nearest icovertex. So I push all vertices away from the icovertex depending on their current distance, such that vertices on the icoedge become evenly spaced. This works great!

Only the seam itself is invalid for a lot of radii (and the simulator fixes those issue with very local adjustments)

[Tom Sirgedas]

Here's GP(22,19), just to illustrate the seam (white line).

The seam is there because the top hex pattern and bottom hex pattern don't exactly match. Cyan and purple swap colors.

You can see that the seam is separating the cyan/purple pairs from purple/cyan pairs.

The seam's path can be adjusted simply by swapping the appropriate cyan/pairs. They are two ways at looking at the same thing.

Notice that the seam travels move easily "horizontally" than "vertically". This is because of the way the cyan/purple pairs are oriented.


If we "move" the blue icovertex to the blue tile pointed to by the yellow arrow, the seam wouldn't need to travel vertically at all. This corresponds to GP(24,13)

[Tom Sirgedas]

Here's GP(24,13)

[Tom Sirgedas]

Here's GP(10,6) which is GP(4m, 2m+1) for m=2.5

Running the seam straight like usual doesn't work here. And I don't think it can be fixed while assuming the 60-fold icosahedronal symmetry I've been using all along. But, let's consider if breaking that symmetry will help.

Each of the cyan-cyan conflicts is resolved by an up or down stitch, but you can't have two ups or downs in a row.

And the stitches on the end meet at the icovertex with 5 other stitches and they all need to be matching in terms of up/down.

So, I think we are still stuck.

However, we can make the seam more complicated to effectively get two ups/downs in a row:


This looks complicated, but it's simple in the dual graph. We're just deleting an extra edge (the red-yellow one):


But we want to apply this "parity hack" only once on the seam, so that means icosahedronal symmetry breaks, but only in a local patch on each seam/icoedge.
Unfortunately, I can't use my 60-fold-assuming sphere simulator to fully test this out. But GP(2m,m+1) should with this scheme as best I can tell (for m greater than 3 or so).

[Tom Sirgedas]

(just adding missing image)

This looks complicated, but it's simple in the dual graph. We're just deleting an extra edge (the red-yellow one):  

[Tom Sirgedas]

Here's a chart for the spheres that can be 7-colored so far. Everything above radius 5.65 can be 7-colored.

The radius 5.65 sphere has 912 tiles on a it. That's a lot of tiles. The tiles have an average area of 0.4398.

Below is a chart of GP(x,y). White dots indicate that the GP produced a successful tiling (after deleting some edges). Black dots mean I couldn't find a successful tiling, and there probably isn't one with icosahedral symmetry. The "symmetry break" means that the GP is likely to be successful by allowing icosahedral symmetry to be broken locally.

Note that almost all successful y-values are odd. Only GP(12,0) is even so far.

[Tom Sirgedas]

(ugh, if I paste an image to Google Groups, it looks like it's going to work but then it doesn't -- need to upload an image file instead)
(Just adding in the missing image)

Below is a chart of GP(x,y). White dots indicate that the GP produced a successful tiling (after deleting some edges). Black dots mean I couldn't find a successful tiling, and there probably isn't one with icosahedral symmetry. The "symmetry break" means that the GP is likely to be successful by allowing icosahedral symmetry to be broken locally.

Note that almost all successful y-values are odd. Only GP(12,0) is even so far.  

[Tom Sirgedas]

I updated my sphere simulator so that it handles symmetries other than icosahedral.

I thought a 5-way rotational symmetry could be useful for finding small spheres, and it was! The 16 tiles near the North and South Poles use the same layout as many icovertices did.

The sphere is valid for radii in [1.29, 1.36]. So not a big range. It uses 42 tiles, 6 per color.

In the images below, the white lines show the 5-way symmetry. Cyan and orange do not permute colors, but the other 5 colors do.

There's actually 10-way symmetry, since the North/South hemispheres are mirrors of each other. (I'm pretty sure there is (x,y,z) to (-x,-y,-z) symmetry, with only cyan/orange swapping colors)

At first I tried with 32 tiles -- with the 10 equator tiles missing, but that didn't work.

View with North/South Pole at top/bottom:


View from the top:

[Tom Sirgedas]

I made a simplified summary video about the 7-coloring paper to share on Facebook. Here it is: https://www.youtube.com/watch?v=a4syYMespTg

Here's the paper: https://arxiv.org/pdf/2107.11900.pdf