Polymath16, sixteenth thread: Writing the paper and chasing down loose ends, II

This is the sixteenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

The paper writing has found a second wind between Philip Gibbs, Aubrey de Grey, Jaan Parts and Tom Sirgedas. For reference, I wanted to compile a list of related publications that have emerged since starting our project. (Feel free to any references I missed in the comments.) There has certainly been a bit of activity since Aubrey’s paper first hit the arXiv two years ago!

P. Ágoston, Probabilistic formulation of the Hadwiger–Nelson problem.

F. Bock, Epsilon-colorings of strips, Acta Math. Univ. Comenianae (2019) 88: 469-473.

G. Exoo, D. Ismailescu, A 6-chromatic two-distance graph in the plane, arXiv preprint arXiv:1909.13177 (2019).

G. Exoo, D. Ismailescu, The chromatic number of the plane is at least 5: A new proof, Discrete & Computational Geometry (2019): 1-11.

G. Exoo, D. Ismailescu, The Hadwiger-Nelson problem with two forbidden distances, arXiv preprint arXiv:1805.06055 (2018).

N. Frankl, T. Hubai, D. Pálvölgyi, Almost-monochromatic sets and the chromatic number of the plane, arXiv preprint arXiv:1912.02604 (2019).

M. J. H. Heule, Computing a Smaller Unit-Distance Graph with Chromatic Number 5 via Proof Trimming, arXiv preprint arXiv:1907.00929 (2019).

M. J. H. Heule, Searching for a Unit-Distance Graph with Chromatic Number 6, SAT COMPETITION 2018: 66.

M. J. H. Heule, Trimming Graphs Using Clausal Proof Optimization, In International Conference on Principles and Practice of Constraint Programming, pp. 251-267. Springer, Cham, 2019.

J. Parts. A small 6-chromatic two-distance graph in the plane, Geombinatorics, vol. 29, No. 3 (2020), pp.111-115.

J. Parts. Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane, Geombinatorics, vol. 29, No. 4 (2020), pp.137-166.

148 thoughts on “Polymath16, sixteenth thread: Writing the paper and chasing down loose ends, II

  1. Repost of my latest offering regarding Jaan’s 6-tiling:

    Thanks Jaan! But I’m still not reproducing this.

    I agree with you about Mathematica – I too am using FindMaximum and being careful about ranges.

    If we orient things following Pritikin and place the centre of a diamond at the origin, then here is my notation:

    – the sharp corners of that diamond are at (0,+/-d)
    – the blunt corners of that diamond are at (+/-e,0)
    – the tip of the arrowhead at y=0 is at (c,0)
    – the back of that arrowhead is at (b,0)
    – the “trailing tip” of that arrowhead is at (r,s)
    – the back of the arrowhead at y=1/4 is at (g,1/4)

    Then we have four distinct diameters of large tiles, which give the constraints:

    (c-e)^2 + (1/2)^2 is at most 1
    g^2 + (1/4 – d)^2 is at most 1
    (r-e)^2 + (1/2 – s)^2 is at most 1
    (b+g-r)^2 + (1/4 + s – d)^2 is at most 1

    with all seven values positive, and with c,b,r,g in increasing order and less than 1. In practice d,e,s are less than 0.1 and g,r,b,c are more than 0.8.

    Also we have a “Bock-esque” situation in the neighbourhood of ((b+g)/2,3/8), where two large tiles meet that need to be 1 away from tiles on the far side of relevant diamonds, giving:

    (b+g)^2 + (3/4 + 2*d)^2 is at least 4
    (b+g+e)^2 + (3/4 + d)^2 is at least 4
    (b+g+2e)^2 + (3/4)^2 is at least 4

    This is all without curving any edges of diamonds or arrowheads, but you said that that makes only a small difference (6899 to 6906). Undulation of the inter-arrowhead edges is needed (at least if any of the things that are >=4 are exactly 4), but does not introduce any additional constraints.

    So, I’ve hunted around the search space and the best I have is this:

    {6690.97, {d -> 0.0124893, r -> 0.873218, b -> 0.872363,
    c -> 0.871225, g -> 0.971385, e -> 0.00519998, s -> 0.00346665}}

    But I think I must be missing your sweet spot, because with this setup we have

    (b+g+e)^2 + (3/4 + d)^2 = 4

    which means that the edges of the diamonds must curve OUTWARDS, as I said in my earlier post, which means they will not be 12-gons as you say.

    1. Why don’t you want to try 12-vertex diamonds? For example, we add a pair of vertices (i, f) and (j, h). In this case, the set of constraints will change, and instead of (0, d) and (e, 0) in >=4-constraints there will be new vertices.

      1. My reasoning is that the only situation in which the addition of a vertex will help is when the line (or arc) that it would bisect is not already constrained, i.e. in which some part of it it could be curved (or its radius of curvature changed) in either direction without creating a unit-distance pair of points. In the best construction I’ve found, the edge of a diamonds is an arc of radius 2 that is exactly 1 from an arc of radius 1 that forms part of an inter-arrowhead boundary between two large tiles. Thus, it can only be made more curved, not straighter.

      2. Not sure I understand your reasoning. I can answer so. First of all, you cared about pulling distant tiles to a distance of 2. This is correct. But there is another task: to make the tiles more convex. This can give an increase in the fraction of the colored plane. And this is achieved using 12-vertex diamonds. How about such a reasoning?

      3. The problem is that in this case the curvature makes the DIAMONDS more convex, i.e. it makes the diamonds bigger and DECREASES the fraction of the plane that is covered by the big tiles. The only way that this could be advantgeous is if there is an accompanying reduction in the size of the arrowheads – but there isn’t, because their vertices (and edges) are constrained by the vertices of the diamond, i.e. by d and e in my notation.

    2. In my case diamonds are non-convex.
      OK. I’d better show my solution. Although it would be better to wait for the picture.
      Consider a 15-gon whose vertices are numbered counterclockwise from 1, starting at your vertex (0, d). But I will use my notation. In fact, we need to consider the 19-gon, but for now we will not pay attention to the wavy inclined edges. Due to the symmetry of the 15-gon, it is enough to consider one “diagonal”, as in your case. We get the following restrictions: 16 distances between vertices 1…4 and 8…11 should be no more than 1 (you can remove some of these constraints, but we will be not greedy). The distance between the distant edges 2-3 (in contrast to yours 1-4 in my notation) should be at least 2, while these edges themselves must be parallel.
      It remains to introduce some variables and express through them the coordinates of the vertices 1…4 and 8…11. I used the following notation:
      {(0,a), (f,b), (f_2,b_2), (c,0), … , (h-l_2,w/2), (h-2d_2(h-g)/w,w/2+d_2), (g+2d(h-g)/w), (g-l,w), …}
      Here g, h, w are macro parameters (describing the base 5-gon), the rest are small values (describing corrections). (I will replace these notations in the future, they just appeared historically.) Here is the solution vector:
      {6985.43, {a->0.013326, c->0.005483, b->0.010031, f->0.000820, b_2->0.003322, f_2->0.003590, g->0.872081, h->0.972098, l->0.000572, d->0.003276, l_2->0.000509, d_2->0.003290, w->0.500000}}

      1. Thanks. Couple of questions:

        1) There is a y-coordinate missing in “(g+2d(h-g)/w)”. Should it be “w-d_2”?

        2) “d” appears only in “(g+2d(h-g)/w)”. Should “h-2d_2(h-g)/w” actually be “h-2d(h-g)/w”?

        I’m assuming yes to both.

        OK, so the mapping from your variables to mine is as follows, where I have written your variables in capitals and mine in lower case:

        A = d
        C = e
        H-L_2 = g
        H-2D(H-G)/W = b+g-r
        D_2 = s
        G+2D(H-G)/W = r
        G-L = c

        So then, inserting your numbers I get:

        d = 0.013326
        e = 0.005483
        s = 0.003290
        c = 0.872081 – 0.000572 = 0.871509
        g = 0.972098 – 0.000509 = 0.971589
        r = 0.877412
        b = H+G-g = 0.872590

        But when I calculate the relevant distances, I get two diagonals that are more than 1:

        (0,a) to (h-l_2,w/2) comes out as 1.00099
        (c,0) to (g+2d(h-g)/w,w-d_2) comes out as 1.00698

        I’m pretty sure this is not just a significant-digits issue.

      2. I’m sorry: missed coordinate is (g+2*d(h-g)/w, w-d). Parameters d and d_2 are slightly different.
        Now my check (where you get more than 1):
        (0.972098-0.000509)^2+(.25-0.013326)^2 = 1
        (0.872081+2*0.003276(0.972098-0.872081)/.5-0.005483)^2 + (.5-0.003276)^2 = 1

      3. Thanks, but wait, in that case your arrowheads are not all the same – the one at w/2 is slightly taller than the one at w, since d_2 is slightly larger than d – which is not allowed.

        First: I am assuming that the tile whose vertices you are enumerating has symmetry across y=w/2, so that the vertices you have not listed are (0,w-a), (c,w), (h-2d_2(h-g)/w,w/2-d_2), (g+2d(h-g)/w, d) and (g-l,0). Right?

        Now, consider the big tile on the other side of the (h,w/2) – (g,w) line. What are the coordinates of its vertices? I can see only two possibilities, depending on what you do with l and l_2: either there are vertices at (g+l, w), (h+l_2, 3w/2) and (h+l_2, w/2) or else at (g+l_2, w), (h+l, 3w/2) and (h+l_2, w/2). In both cases, the other vertices are (h-2d_2(h-g)/w, w/2+d_2), (g+2d(h-g)/w, w-d), (g+2d(h-g)/w, w+d), (h-2d_2(h-g)/w, 3w/2-d_2), (h+g-c, 3w/2), (h+g, 3w/2-a), (h+g, w/2+a) and (h+g-c, w/2). And that’s a problem, because effectively d and d_2 have been swapped (whether or not l and l_2 have also been swapped), so you have some diagonals >1. In particular, (h+g-c, 3w/2) to (h-2d_2(h-g)/w, w/2+d_2) is 1.00698.

      4. Correction (though irrelevant): I should have said “or else at (g+l_2, w), (h+l, 3w/2) and (h+l, w/2)”.

      5. Ah, a more relevant correction – I withdraw my calculation of that diagonal, I messed up my d and d_2. However, it remains true that d and d_2 must be equal in order that all the big tiles are the same shape. With the numbers you provided, they are so close to being equal that everything almost works: the only diagonal that is not quite equal to 1 is (c,0) to (g+2d(h-g)/w,w-d), which is 0.999996.

        However, your distances that need to be at least 2 are all around 2.002, which means that the edges of the diamonds can indeed be concave not convex, which in turn means that it makes sense to include those additional vertices. So, what does this mean? I think there must still be something wrong. Your values for a and c are considerably larger than mine (d and e in my notation) – you have 0.013326 and 0.005483 whereas I have 0.0124893 and 0.00519998. Therefore, I think my convex diamonds fit inside your concave ones. (Indeed, I think they have to do so, in order to maintain the required distance 2 between diamonds.) So the only way that this can be compensated is if your arrowheads are quite a lot smaller than mine. And they are smaller… your d and d_2 average 0.003283, whereas my s is 0.003505, and similarly your l+l_2 = 0.001081, whereas my b-c = 0.001138. That looks like a much smaller difference – but of course we only need to balance a small part of the difference between your diamonds and mine, because yours are concave and mine are convex. So maybe you’re right… I am going to check now.

      6. Correction is right. But why not allowed?
        All tiles lie entirely inside 5-gons such as {(0, 0), (g, 0), (h, w/2), (g, w), (0, w)}, except for some small wavy region. (However, for our purposes, we can equate d = d_2, this will not greatly affect the result.) The points you are talking about have coordinates (1.838696, 0.75) and (0.970781, 0.253290), the distance between them is 0.998600.

      7. d != d2 is not allowed because each arrowhead plays two roles: its concave vertex is a vertex of one large tile, and its tip is a different vertex of two other tiles. Therefore, the distance between its trailing tips is both d and d_2, depending on which tiles you’re considering.

    3. … And now it seems I’ve found a bug in my formulae. I took the doubled width of diamonds in the diagonal direction. It turns out that you are right. Tomorrow I’ll recalculate it.

      1. …Hm, no, it’s all right here. No, I can’t do this after midnight. Tomorrow with fresh head.

  2. Question on terminology. We often use a set of distances (such as 1 or 2) between which tiles should be placed. Constraints can be either external or internal for these tile elements. It would be nice to have some kind of collective name for such an object. Maybe it already exists? If not, we can enter our own. For example, call it a spacer. How better?

  3. Here’s a thought about the chromatic number of the surface of a large sphere (CNSLS), specifically the lower bound. At present, we know that our various 5-chromatic graphs cannot be drawn on a sphere because they contain rigid unit hexagons – or, more generally, cycles of at least three rigid graphs in which each consecutive pair of graphs shares two vertices (thanks Domotor). But we also have, thanks to Jaan, a 5-chromatic graph that fits within a strip of width 1.4, which is too thin to contain even a Moser spindle. I’m guessing it probably does contain more complex “fat cycles” (as I’m going to call these), but maybe not? If we can find a 5-chromatic graph that lacks any such cycles, we can try explicitly embedding it vertex by vertex (picking the sphere radius arbitrarily) – and if we find we can’t, we will have learned something about rigidity. The only minor problem is that an efficient algorithm for such a check seems a bit tricky… any ideas anyone?

    1. Embedding UDG’s on the surface of the sphere is way harder. It was a conjecture that a UDG on a sphere can have only a linear number of edges. This was disproved with a tricky construction, and this ‘repeated spindling around the same point’ is still the only known method to give a superlinear number of edges. So if you want to embed big graphs, then I would try this method. Literature:
      Erdos-Hickerson-Pach: https://doi.org/10.1080/00029890.1989.11972243
      Swanepoel-Valtr: https://pdfs.semanticscholar.org/0b23/77d04c603400a244004846993c70aeed910e.pdf
      Also note that back in 2018 we tried this with Tamas Hubai and failed.

  4. OK, wow, it’s true! I have verified that your numbers give what you say they give, and FindMaximum essentially agrees. It is telling me (without curves) that the best locations for your (f,b) and (f_2,b_2) are such as to make the distance between (f_2,b_2) and (h+g-f_2,3/4-b_2) equal to exactly 4, which means that the edge between (f,b) and (f_2,b_2) does need to be convex with radius 2. But when I add the curves I find that that does more harm than good and it’s best to fix the
    parallelogram {(f,b), (f_2,b_2), (h+g-f,3/4-b), (h+g-f_2,3/4-b_2)} to be a rectangle, so that the edge between (f,b) and (f_2,b_2) is straight. In the end I get a vector of:

    {6988.84, {d -> 0.0133288, r -> 0.873408, b -> 0.872597, c -> 0.871509, g -> 0.97159, e -> 0.00548404, s -> 0.00330229, f_2 -> 0.00360292, b_2 -> 0.00330158, f -> 0.000837821, b -> 0.00996455}}

    (Note that this is my notation except for your extra vertices, and that my “s” corresponds to both your d and your d_2.)

    Can you confirm this?

    Congratulations on this remarkable tiling. I would NEVER have guessed that the distance between, in your notation, (-c,0) and (h+g,3/4+a) would be more than 2 in the optimal solution.

    1. Minor edit – I wrote “it’s best to fix the
      parallelogram {(f,b), (f_2,b_2), (h+g-f,3/4-b), (h+g-f_2,3/4-b_2)} to be a rectangle” but I meant “it’s best to fix the
      parallelogram {(-f,-b), (-f_2,-b_2), (h+g+f,3/4+b), (h+g+f_2,3/4+b_2)} to be a rectangle”.

    2. Grrr damn, apologies everyone, I posted the wrong vector. THe correct one is:

      {6988.78, {d -> 0.013329, r -> 0.873408, b -> 0.872597, c -> 0.87151,
      g -> 0.97159, e -> 0.00548414, s -> 0.00330235, f_2 -> 0.00357713,
      b_2 -> 0.00334723, f -> 0.000827508, b -> 0.0100059}}

    3. Hmm, our results still don’t match. We need to figure out why.
      You are talking about “distance between (f_2, b_2) and (h + g-f_2,3 / 4-b_2)”. I think it needs to be corrected. Did you meant (-f_2, -b_2) and (h + g+f_2,3 / 4+b_2)?

      1. Then this is wrong, since it is necessary to consider distances (not less than 2) between (-f, -b) and (h + g+f_2,3 / 4+b_2) . And (-f_2, -b_2) and (h + g+f,3 / 4+b).

      2. Yes, I did that. Those are the edges of the parallelogram. I have been assuming that the parallelogram is nearly a rectangle, so that its long sides can be exactly 2. I am also going to try the case where the parallelogram is more oblique than that, i.e. where one of the diagonals is exactly 2 but the long edges are greater than 2, but I didn’t try it yet.

      3. No, the diagonals cannot be equal to 2. Then one of the edges will be less than 2.

      4. I’ve now tried the case of a more oblique parallelogram (with one diagonal equal to 2 and the edges allowed to be greater than 2) and I’m pretty sure it is worse, whichever diagonal is made equal to 2. (But I’ve been wrong before :-))

      5. No. No diagonal can be equal to 2. Otherwise, some edge (that is, the distance between the tiles) will be less than two.

      6. The distance between the tiles can be kept equal to 2 by making the short edges of the parallelogram convex, with radius 2, centred on the ends of the shorter diagonal. (I’m right now trying the intermediate case where the diagonals are greater than 2 but not equal to each other.)

    4. Let’s name the points (-f, -b) and (-f_2, -b_2) as -2 and -3, respectively. And the points (h + g + f, 3/4 + b) and (h + g + f_2, 3/4 + b_2) as 2 ‘and 3’. It should be noted that points -2 and -3 are mirror images of points 2 and 3 relative to (0, 0), this leads to the fact that point -2 is located below point -3. Therefore, the distance 2 must be between the points -3 and 2 ‘, as well as -2 and 3’. In addition, the edges -2 …- 3 and 2 ‘… 3’ must be parallel. This can be obtained by equating distances -2 … 2 ‘and -3 … 3’.

      1. Yes again. The four points make a parallelogram, which may or may not be a rectangle; I find that the optimum is when it is indeed a rectangle.

    5. And I do not agree that d and d_2 must necessarily coincide. It’s just that my arrows contain 6 vertices instead of 4.

      1. Aha! Why didn’t you say so before? 🙂 But then, wait, how do you know that both of the “side” vertices define the same h and g? Surely you need h_2 and g_2 too? (Of course you only need one new variable, because h_2+g_2 = h+g.)

      2. OK, I’m confused now. In my understanding of the arrowheads, i.e. with four vertices, their long edges are arcs centred on (c,0) and their short edges are arcs centred on (0,a). If they actually have six vertices, one of those edges must consist of two segments instead of one. Which one, and why?

      3. Woah. I need a picture for that. I can’t see any way that arcs of radius less than 1 could ever be optimal.

      4. From the very beginning I said that we need a picture. But everything is simple here. We consider almost parallel edges (and not what we observe in Reuleaux polygons).

      5. I’m going to bed. We have at least 5 unsolved questions: arrow shape, additional variables, rounding edges, how to set distance 2, discrepancy between results.

    6. I substituted your values, and I got the relative fraction of the colored plane 6985.69. How do you calculate areas and what parameter do you maximize?

      1. Incorrect name. This is the reciprocal of the relative fraction of the uncolored plane.

      2. I get 6985.39 when I don’t curve any edges. It rises to 6988.78 when I add curves (to both edges of my arrowheads and two of the three edges of my diamonds – in all cases my curves are of radius 1 and concave. I compute the area by explicitly computing the areas of the slivers between the straight edge and the curve: slice[z_, r_] := 2*ArcSin[z/(2*r)]*r^2/2 – (z*Sqrt[r^2 – z^2/4]/2) where z is the distance between the two points and r is the radius of curvature.

        I realised overnight that I can probably get a slight further improvement, though, and I may even understand why you sometimes have radii less than 1. I’ll report back soon.

      3. Yeah. This is a completely different matter. Now our results without curving differ by only 0.04. I get 6985.43. This is still a significant discrepancy, and we need to figure out where it comes from. In addition, as I said, using your values I got 6985.69. Perhaps this is a remapping error.
        Now about curving. I get 6992.06. I think I understand how you curve the edges using the radius 1. But you can do it differently. Imagine a disk of radius 0.5, through the center of which two straight lines are drawn, cutting off two circular sectors. This shows that a radius of 0.5 also works. And this gives additional area.

      4. Right. Right now I am implementing a further generalisation of your radius=0.5 concept; it is complicated so I will explain it properly when I have got it working.

      5. I’m confused by that radius 0.5 concept as well, and I’m like 99.9% sure that any arc of a solid color with a radius less than 1 is always going to be a disadvantage, because it effectively creates a double colored space. Any point at distance 1 to the inside of the small arc (up to where you could press a radius 1 arc against the small arc) would also necessarily be at distance one to the arc itself in at least one place, or two places. If the inside of that arc in that place and the arc have two different colors, those points are effectively double-colored.

        Is there something I’m missing here?

      6. Yeah, it’s counterintuitive, but it’s true when one is fattening two edges at the same time. As an example, consider a unit-diameter circle, draw a square of side 1/Sqrt[2] inside it, and delete the two slivers on opposite sides of the square. That leaves you with a shape that has four corners, a diameter of 1, and two edges that are curves of radius 0.5, and an area of about 0.64. Now, suppose we also delete the other two slivers, and instead draw three new arcs of radius 1: two centred on adjacent vertices of the square, which meet in a fifth point, and then one centred on that fifth point and going between the two aforementioned vertices. That gives you a figure with five corners, again a diameter of 1, and three edges that are curves of radius 1 – and an area of, as it turns out, only about 0.62. So what Jaan was saying (and I now agree) is that if you start out specifying the four points, and you want to “fatten” two opposite edges, the optimum way to do it is not (not necessarily, anyway) with curves of radius 1. I’m currently generalising this (as best I can…) for the class of arbitrary quadrilaterals whose diagonals are both 1 and whose edges are all at most 1.

      7. Oh, so you’re using these arcs just to minimize the area of one specific target color. Right, then pretty much everything is fair game, or at least would seem to be. It’s still a bit strange to think that introducing deliberate inefficiencies into the coloring is helpful to minimizing the area of a 7th color. Almost sounds like there could be something related to a proof of an impossible 6-tiling going on, but that’s not my window to lean out of.

  5. I’ve been meaning to bump my attempted theorem of necessary tiles against a prof in the university I’m studying at now, see how that goes, but unsurprisingly the current pandemic has postponed those plans for a bit.

    I’ve just finished something else to show here though. I’ve been hard at work to make a third video, but instead of trying to prove anything or introduce any new ideas I’ve programmed a solid framework for rendering tilings and computing their exclusion zones with just a few lines of well defined code.
    The video shows a bunch of plane tilings that require 7 or 8 colors, and how exactly the exclusion zones look and why they fit together. The purpose is mostly intuition fuel (and looking nice), although while making it I also realized that the triangle grid with 8 colors can seamlessly be transformed to a square grid, with a still working trapezoid grid in between.

    Also you’ve been talking about a… 6-tiling? As in a tiling that would prove CNP to be 6 or less? Either way, since you were talking about pictures for that, with the code for that video I’d be able to help. If you can provide the tiling to me in an arcpolygon format, as well as the offset vectors for the tiles I can put this together into code that can be rendered and animated at a whim. Since the exclusion zones can be computed automatically from any tile I have coded I can also render and show those for your tiling, per color.

    1. We are talking about coloring the plane in 6 colors, when the uncolored fraction of the plane remains. The challenge is to minimize this fraction.

    2. Bernhard, could you try to do something similar for Coulson’s tiling of 3D-space? Including exclusion zones. (In the future, one could play with 14 colors, to see how much space remains uncolored. But there is no visual intuition at all.)
      Link: D. Coulson, ‘A 15-colouring of 3-space omitting distance one’

      1. I could, I probably will, but don’t hold your breath. Although the video itself just shows old stuff with a very new paintjob, behind the scenes I had to re-invent arcpolygons and the math around it from scratch, because proper information and definitions of those are nigh impossible to come across, although it’s out there for sure. Somewhere.

        Something like 18 months ago or so I manually created 3D exclusion zones in SketchUp guided by that exact paper, the outer boundary at least, so I know how I’d define the format as well already. And while I now have a solid grasp of how to go around figuring out that math and putting it into code, it remains a beastly task. I’d first have to learn how to properly do manim stuff in 3D too. Being able to share models and plugins in SketchUp would have its upsides, but at the end of the day SketchUp isn’t really a perfect tool what with its licenses and lacking model backwards compatibility.
        Then there’s cross sections to worry about… those are a thing in Sketchup and would make analyzing according models and exclusion zones actually fairly comfortable and visually intuitive. I don’t know about those in manim. And now that I thought of it I definitely want that in manim, but there’s a decent chance I’d have to program that myself too.

        If it were my paid job and I wouldn’t have my studies towards being a geneticist to do I could probably do it in… a month or two of full-time work?
        I’ll start this as a side project but let me set realistic expectations. A year? Maybe two? Something thereabouts I figure. If it ever reaches maturity it’ll be on my YT channel, and the code, just like my current code alredy, will be open for anyone on my github.

  6. We continue with the 6-coloring of the maximum fraction of the plane. It remains to understand the small effects.
    About the arrows. When I got the previous result (6899, and 6906), I was considering convex tiles, without wavy edges. In this case, the resulting tile fits entirely inside the pentagon {(0, 0), (g, 0), (h, w / 2), (g, w), (0, w)}. The slope of the inclined edges is determined by the parameters {g, h, w}. (On the question of why additional variables are not needed.) The parameters d and d2, which determine the position of the additional vertices on the inclined lines, do not depend on each other in any way. And the arrow is obtained from three different tiles. In this case, the optimal values of d and d2 turn out to be different, which gives 6-vertex arrows.
    In the case of non-convex tiles, it seems that nothing prevents d and d2 from becoming the same. But if I add the corresponding constraint to FindMaximum, I get a slightly smaller result. The difference is about 0.004. Perhaps this is already a limitation of the optimization method or its parameters. I have no other explanation yet.

    1. Thanks. I’m nearly ready with my new version – more soon. But meanwhile, regarding the 6-vertex arrowheads: I think I understand, but my point is that you are unnecessarily placing all the four vertices with y-coordinates slightly more than w/2 (from one arrowhead) and slightly less than w (from another arrowhead) on the same line. What I was saying earlier is that if you extend the line betwen the vertex with y-coordinate w-d and the one with y-coordinate w/2+d up and down to w and w/2, you will get x-coordinates g and h, fine, but if you extend the line betwen the vertex with y-coordinate w-d_2 and the one with y-coordinate w/2+d_2 up and down to w and w/2 you may get different values for g and h. Those two lines must intersect at ((g+h)/2,3w/4), but they do not need to have the same slope (i.e., be the same line). That’s why I said you need an extra parameter.

      1. No – the arrowheads still have six vertices that way – and the big tile remains convex so long as the slopes of the two inter-arrowhead lines are in the right order.

      2. Thank you. But then, the vertex that you designated as y = w-d is not needed, and can be discarded, since from one of the vertices located on the opposite side of the tile, the unit distance will be both to the vertex y = w-d and to the vertex y = w-d_2. (If this is not so, we simply lose part of the area.) In other words, all the intermediate vertices between y = w and y = w-d_2 are simply discrete curving options. Or am I missing something?

      3. The picture differs only in that the vertices y = w-d and y = w/2+d lie on a line between x = g and x = h. In the case of convex tiles, this gives an optimal result.

      4. I still don’t see how that can be. The five points at y = w (the one with x < g), w-d, w-d_2, w/2+d_2 and w/2 (the one with x < h) are all at distance 1 from some vertex on the opposite side of the tile, near to (0,0) – yes? Can you please list which points (your a, your c and the two points between them) are at distance 1 from each of those five points?

    2. Here is one tile and inner unit distances. All small-scale quantities are increased 10 times.

      Here is a real size picture of diamond.

      Here is a real size of arrow for convex tiles (6899).

      1. Thanks Jaan!

        OK, that is what I was imagining. In the top picture you show 15 vertices, but really the tile has 17 vertices, because vertex 6 includes one at y=d and one at y=d_2, and similarly for vertex 10. Let’s call the ones at d “6a” and the one at d_2 “6b”. I’m claiming that the distance between 6b and the 12-13-14-15 diamond is not optimal, i.e. it is less than 1 from all of them.

      2. Yes, the distance from “6b” to “13” is less than 1. But the tile does not contain the vertex “6b”. This is the vertex from a completely different tile. Just it lies on the edge “6-7”. Therefore, each tile still has 15 vertices. (You can draw an arbitrary number of points on any edge, and finally come to the conclusion that the tile has an infinite number of vertices.)

      3. Ah, I see – there is a problem with our terminologies, because you are considering the diamonds and arrowheads as “gaps” whereas I am considering them as small tiles. But either way, I claim that the tiling can be (very slightly!) improved by making the distance between 13 and 6b equal to exactly 1.

      4. 1. I think there are two different ways to define the concept of a vertex. Firstly, as a point at which three or more edges converge, if not a single tile is considered, but a set of connected tiles. In this sense, there is a vertex “6b”, but there is no vertex “6”, as well as “2” and “3”. Secondly, as the break points of the border of the tile. In this case, there is no vertex “6b”. In any case, the number of tile vertices is no more than 15. Yes, this is a problem of terminology. I don’t know how to get around it.
        2. And I bet that you worsen the result, not improve it.

      5. In your case, the distance between “6” and “13” will become less than 1, and the area of the arrow will increase.

      6. Right. The only way to get exactly 1 everywhere is with curves. I have nearly completed my construction and characterisation (it has a few extra “break-point” vertices in addition to yours). Stand by!

      7. I look forward to it.

        From definition of polygon:
        “The segments of a polygonal circuit are called its edges or sides, and the points where two edges meet are the polygon’s vertices or corners.”
        I suggest to use words “sides” and “corners” for description of a single tile, and leave the concepts “edges” and “vertices” for the tiling as a whole, where the vertex is the point at which three or more edges meet.

  7. OK, finally I offer the following definition and calculation of what I think (though I do not remotely claim to have proven) may be the truly optimal optimisation of the celebrated Pritikin tiling (which, let us not forget, was originally conceived by Ed Pegg, as reported in the Soifer book). The summary result is that I believe that the best construction is exactly Jaan’s but with d=d_2, so the arrowheads have no corners other than their vertices. He is correct (and it makes sense) that d=d_2 is not optimal if we do not curve any edges (I get 6985.23468, to be precise, relative to Jaan’s 6985.43). However, I am correct that it is optimal if we do curve edges: my final number is 6992.16555 as against Jaan’s 6992.06. My coordinates, using the labels in Jaan’s picture, are:

    1 = (0,0.013343547466)
    2 = (0.00082693666926,0.0099987220231)
    3 = (0.0035745404852,0.0033448254424)
    4 = (0.0054885276613,0)
    8 = (0.97159339411,1/4)
    9 = (0.97076645743,1/4 + 0.0033448254584)
    10 = (0.87342791863,1/2 – 0.0033448254584)
    11 = (0.87151393145,1/2)

    I’ll put the gory details, which involved introducing ten more parameters that all collapsed in the best case, into a separate post.

  8. OK, here goes with the gory details…

    First, terminology (which, as already noted by both Jaan and me, can be confusing for tilings). I think the best option is to avoid using the terms “vertex” and “edge” at all.Instead, I will always use the term “junction” to denote points where three (or more, but that’s not relevant for this tiling) tiles meet. Following Jaan’s suggestion I will use the term “corner” to denote points on the boundary between exactly two tiles at which that boundary has zero radius of curvature, i.e. the gradient changes discontinuously. I will also need to refer to a third type of point: one at which the gradient of the boundary does not change discontinuously but the radius of curvature does. I will call this a “quasi-corner”. All boundaries will consist of segments with constant radius of curvature (we won’t have any spirals, in other words), so a quasi-corner is simply a point at which a boundary’s radius of curvature changes between two different (non-zero) values.

    OK, here goes. Broadly, the system is as shown in the first of Jaan’s three pictures of today, so I will use his numbering of the junctions and corners. Note that I will use “6” and “10” to denote the junctions at the trailing tips of arrowheads, so “6b” in the terminology of my previous post. My system has all the same diameters (pairs of junctions exactly 1 apart) as Jaan’s, except that I am making junction 13 exactly 1 from 6b rather than from 6a. Note that in my earlier construction a few days ago, I unnecessarily required some extra inter-junction distances to be exactly 1, namely 4-10, 1-9, 15-7 and 12-8 (and their reflections in y=1/4, obviously). This lost me quite a lot, so please don’t try to compare the present construction with that.

    The essence of the construction is to incorporate corners and quasi-corners into the short boundaries (i.e. those that are parts of the perimeter of either diamonds or arrowheads) so as to make the big tiles have a diameter of exactly 1 in all directions, except for four angular intervals: between 4-11 and 5-12, between 1-8 and 15-8, between 2-9 and 3-10 and between 13-6 and 14-7. There is nothing new to say about 4-11 to 5-12 or 1-8 to 15-8. The other two intervals are the diagonal directions in which same-coloured big tiles come within 1 of each other: I will call them the inter-tile directions.

    In the inter-tile directions, we are interested in distances between counterparts in other tiles of vertices 2 and 3 (and 13 and 14, of course). Specifically, denote the reflections of 2 and 3 in the origin as 2′ and 3′ respectively, and denote the translations of 2 and 3 vertically by a distance of 3/4 and horizontally by the sum of the x-coordinates of 6 and 7 as 2″ and 3″ respectively. These four vertices form a parallelogram 2’3’2″3″, where 2’3″ and 3’2″ are exactly 2 and 2’2″ and 3’3″ are at least 2. It remains to ensure that no pair of points anywhere else on the boundaries 2’3′ and 2″3″ are less than 2 apart. If 2’3’2″3″ is a rectangle, the 2-3 boundary (for any version of 2 and 3) can just be straight, and we’re done.

    Otherwise, in order to maintain a distance of exactly 2 in all the directions between 2’2″ and 3’3″, it’s more complicated, but it’s still perfectly possible. I’ll assume 2’2″ is less than 3’3″ (the construction is exactly analogous if we make the opposite assumption). We identify points X’ and X”, located so that X’2″ and 2’X” are exactly 2 and X’X” = 2’2″; thus, X’2’X”2″ is a rectangle. Then we draw 2’X’ and 2″X” as straight lines and 3’X’ and 3″X” as arcs of radius 2 centred at 2″ and 2′ respectively; thus, X’ and X” are quasi-corners. This suffices to keep all same-coloured tiles 1 apart, so long as the (hitherto straight) boundary 9-10 is replaced by a sequence 9-A-B-C-D-10 in which 9-A, B-C and D-10 are straight lines and A-B and C-D are arcs of radius 1 centred on 2′ and 2″ respectively (thus making B and C quasi-corners). A and D need to be far enough around their respective arcs so that 9-A and D-10 do not intersect the unit circles around 3″ and 3′ respectively, but that’s all. BC is parallel to 2’X and 2″X” (and midway between them).

    Now for the other angular intervals. We have two quadrilaterals of interest: 3-4-10-11, and 1-2-8-9. (Also 14-15-7-8 and 13-12-6-5, which are the same.) Here the situation is more complicated than the case just examined, because we do not need the short edges of the quadrilateral to be parallel. Our goal is to bend those boundaries so as to optimise the tiling, which involves making the arrowheads and diamonds concave.

    As Jaan noted earlier, the best way to do this can potentially involve boundaries with radius of curvature less than 1. My construction (which I have not proven to be optimal, but I think it must be very close) is as follows:

    1) The construction is the same for both quadrilaterals, so let’s just consider a quadrilateral ABCD, with AB and CD being the short edges that we’re going to bend. We know that its diagonals (AC and BD) are exactly 1 and AD and BC are at most 1.

    2) First we consider the case where AD=BC, i.e. AB and CD are parallel and ABCD is an isosceles trapezium. Here the construction is easy: we replace AB with an arc of radius AB/(AB+CD) and we replace CD with an arc of radius CD/(AB+CD). It’s easy to see that this keeps the diameter to 1, because the maximum distance between the arcs AB and CD in any direction is always a line that passes through the intersection between AC and BD (call that point E), which is simply a rotation of AE plus a rotation of EC. I haven’t proved that this maximises the area of ABCD, but I’m pretty sure it does.

    3) Now consider AD!=BC, i.e. AB and CD are not parallel. Let’s assume, wlog, that BC is longer than AD. We now choose a point P such that PC = 1 and PD that is at least AD and at most BC. Then we identify the point Q such that BQ = 1 and PQ = BC. This means that PBCQ is an isosceles trapezium whose diagonals are both 1, and APBCQD is a convex hexagon. We now draw AP and QD as arcs of radius 1 (centred on C and B respectively) and PB and CQ are arcs of radius PB/(PB+CQ) and CQ/(PB+CQ) as in the previous case. Thus, P and Q are quasi-corners. Again it’s easy to see that the diameter is 1 in all directions between AC and BD. But the point here is that we have a new degree of freedom, because of the range of locations we can choose for P.

    So when we compare this structure to Jaan’s, basically I an introducing three additional points to optimise, namely the quasi-corners between vertices 1 and 2, 3 and 4 and 8 and 9. The one between 10 and 11 basically substitutes for Jaan’s point at y = w-d.

    OK… results. We now have 21 variables (not including Jaan’s “w”, which is clearly fixed to be 1/2), so perhaps it’s not surprising that Mathematica struggles. But I obtained reliable behaviour once I looked individually at each of the 27 cases (three pairs of lengths that can each be either equal or ranked either way). Aaaand, it turns out that ALL the quasi-corners collapse in the best case. In other words, in the best case all our quadrilaterals of interest are rectangles with diagonals exactly 1 (except for 2’3’2″3″, which is a rectangle with long sides exactly 2). Bit of an anticlimax… but I guess it was worth doing.

    1. So. This is a lot of work. But so far I have not fully understood what we have come to (correct me where I am wrong).
      1) You introduced many additional degrees of freedom compared to the original 15-gon, but in the end you had to return to this good old 15-gon. At the same time, you came to a result that is more by 0.1, and now we need to understand what causes this difference.
      2) If I understand your 2X3 construction correctly, you want to make the X3 arc concave. In this case, the distance 2’3 ” will be strictly less than 2. Is this so?

      Last night I sat with a sheet of paper and I got another crazy idea that might work. But today I will not have the opportunity to test it.

      1. Thanks.

        1) Yes, we should try to understand the difference. I optimised with curved edges directly. Did you optimise with straight edges and then add the slivers? When I do that wiith d=d_2 I get 6985.37757 and 6992.0266, and I’m betting that with d != d_2 one can get a little more (for both).

        2) The hexagon 2’X’3’2″x”3″ is convex. The edges 3’X’ and 3″X” are arcs of radius 2, so they make the diamond concave at that boundary. The other edges are all straight. The distance 2’3″ is exactly 2. The overall hexagon consists of a central rectangle 2’X’2″X” plus two sectors of radius 2.

      2. 1) Yes, I thought the same thing. Everything as you described. And this is probably the case. But one need to check everything. A lot of different (close but not matching) estimates have accumulated. For example, I get about 6885.43 for both d = d_2 and d!=d_2, the difference is only 0.004 and this differs from your estimate. And not only this.
        2) That’s OK. I drew a little wrong picture.

    2. So. Before I did a very sloppy calculation. Some things were supposed, but not checked. And you will laugh, but I just figured out how to display the result with higher resolution. Now we have the following:
      1) I repeated your result 6985.2346760 and 6992.1655504 for the case of joint optimization of the 15-gon and the curving segments of the short sides of the tile.
      2) I got a slightly different, but close, result for separate optimization: 6985.3775668 and 6992.026378 (my) vs. 6985.37757 and 6992.266 (yours). Moreover, if we do not assume further curving of the short sides of the tile, then we can get 6985.429624 for d!=d_2 and 6985.426227 for d=d_2. In this case, the curving radius cannot be less than 1 and after curving we get 6988.746463 for d!=d_2.
      3) My new idea is somewhat similar to yours. It consists in the fact that we can free the common point of the opposite sectors of the circle and allow the sectors to be slightly inclined, not strictly opposite. Further, the sectors in each pair can have different radii (the sum of the radii is 1). Verification showed that this does not provide improvement.
      4) One can continue the generalization further and allow for each direction on the plane its own radius. As a result, we obtain a continuous dependence of the radius on the direction. This is an infinite number of degrees of freedom. Then one can try to optimize this function. I do not know if this can give anything. Based on the results already obtained, there is reason for doubt.

      1. Great. Concerning (4), yes, that is what I meant when I referred to spirals, and I agree that it is unlikely to help, though I don’t immediately see a way to prove that the construction using only sectors and fattened isosceles trapezia is optimal.

        Shall we move on to the 5-tile pattern?

      2. Yes, we will do it. But first, I need to prepare a good start. This task looks much more complicated than the case of 5 colors. And this is a nightmare, how much time we spent on an elementary case of 6 colors. Therefore, I want to start with a picture and distinct designations. And with a good initial solution. But this is not ready yet.

      3. I’m hoping that some of the principles we learned last week will translate to the 5-colour case… but yes, it is really daunting.

  9. Right guys, I am feeling a bit better now about spending so long last week on optimising Pritikin, because the ideas involved have led me to a really nice result. We were talking recently about 7-tiling an arbitrarily large sphere, but we also have the question of how large a sphere can be k-tiled for smaller k, for which the current results are the ultra-boring tetrahedron, square pyramid and dodecahedron. I’ve just realised that Philip’s 6-disc can be used for each face of a dodecahedron, giving a 312-tile tiling of a shere of diameter, um, quite big. Here are a picture of a region, and the details.

    First we note that Philip’s disc can be extended quite a lot with the addition of 10 very small tiles of a seventh colour. (Interestingly, they can all be one colour: they come in Siamese pairs.) They are the small dark-shaded triangles denoted 7a, 7b, 7c in the figure. So here’s where it gets interesting. If we ask what colours the next ring of tiles can be, we see that the four at the top are analogous to the ones below them: 1,3,4,1 adjoins 6,5,2,6. It’s easy to see that this works all the way round. So now, suppose we take a dodecahedron and replace a face with a 6-disc. Then, the neighbouring faces of the dodecahedron can also be replaced by 6-discs, and everything works – the midpoint of each edge of the dodecahedron has four tiles meeting that are the colours not used for the centres of the dodecahedron-faces that meet at that edge, and the symmetry of the original 6-tiling does the rest.

    So it remains only to determine that the colour-7 tiles vanish when we do this. That’s easy to see, because (in the plane) those tiles are entirely above the line (in the plane) between two adjacent tips of the 6-discs, which equivalently means it would be entirely above those small tiles if we were considering the adjoining 6-disc with central tile coloured 1. (I hope that makes sense!)

    So the radius of the sphere is, um, I think something around 4. Can someone come up with an exact formula?

    Also, can we use our 5-discs to get a better result for a 5-sphere?

    Also also, obviously pentagons can’t be used to tile the plane, but can we fill in the gaps with large tiles not using colour 7, i.e. can this design be the basis of a tiling of the plane that beats Pritikin? I’m not sure what the area of the small tiles is, but I suspect it is small enough. A dense tiling of the plane with pentagons allows each pentagon to share three edges with other pentagons, and we just noted that small tiles at shared edges go away, so effectively each pentagon has only four small tiles rather than ten. I have run out of time for today but I’ll look more at this soon.

      1. If anyone is interested, here is my (hopefully essentially correct) proof:


        I have spent quite a long time trying to obtain colourings with 8 (or at least with 9 or 10) colours for all large enough spheres, but I haven’t succeeded yet, so the best colouring I know of that does not only work for spheres of bounded radius is still 15, which follows from the colouring of the 3-dimensional space.

        I was also interested in the proof of the tiling-based chromatic number of the plane being at least 6 (so I could possibly use it for constructing a similar proof for spheres in the general tiling case (as Dömötör wrote, I was only considering the “nice” tilings considered by Thomassen)), but sadly the Townsend paper isn’t openly accessible as far as I know (it has been published in Geombinatorics), while the one by Coulson (that is also listed in the wiki as a proof for TCNP\ge 6) only considers convex polygonal tiles (unless I completely misunderstood something).

      2. Many thanks Peter – wow, this looks very impressive – I will study it thoroughly when I have more time. I can email you the Townsend paper if you email me at aubrey@sens.org.

        Meanwhile, I was so astonished by your finding that large spheres are hard to tile even with more than eight colours that I had a go. I believe I have a tiling with 11 colours, using the classic “geodesic dome” tiling with 12 pentagons and a lot of hexagons; I don’t think the variation in size of tiles arising from the curvature is enough to make problems, but please shout if you think it does.

        Let the tiling be such that there are 3n+1 hexagons in a chain between each pair of pentagons. Assign each of colours 1 through 6 to two opposite pentagons. Then assign each of 7 though 11 to the chains of hexagons joining pairs of pentagons, i.e. to edges of the mega-icosahedron; say we use colour x for a chain between pentagons of colours y and z, we colour the hexagons x,z,y,x,z…y,x. Assign each colour to six edges such that each vertex uses each edge-colour once; the midpoints of edges with the same colour end up being at the vertices of an octahedron. Then consider the hexagons within a face of the mega-icosahedron, i.e. the triangular grid of hexagons that is bounded by three inter-pentagon chains. 2/3 (or so) of these hexagons are a multiple of three hexagons away from some hexagon on an inter-pentagon chain; assign them to the same colour as that chain-hexagon. (In some cases two such chain-hexagons identify the same face-hexagon, but they are the same colour so there’s no problem.) The remaining hexagons in the triangle can then be coloured using the three vertex-colours not used by the pentagons at the triangle’s vertices. This seems to create no conflicts in the neighbourhood of vertices or chains.

        Here’s a quick ASCII-picture, with n=3, centred on a pentagon of colour 1 that I have denoted with a *, and the edge-colours are t,u,v,x,y. Note that this is the whole of the five faces of the mega-icosahedron – the 120 degrees between 7 o’clock and 11 o’clock is just one such face, stretched vertically, so as to allow the other four faces to be shown as equilateral triangles. Thus, all five corners of the grid shown are pentagons.

        Please let me know if I have hereby redeemed myself after yesterday’s debacle!

      3. Heh, looks like posts go to moderation purgatory even with just one hyperlink, if they also contain an email address…

      4. Thanks Aubrey, I sent you an e-mail about the Townsend paper.

        I also had quite a few tries on making colourings based on dividing an icosahedron (or even an octahedron) to tiles, and apply a colouring in which no two neighbours or second neighbours have the same colour, and some of them seemed to work (my primary goal was to find an 8-colouring, so I did not try giving colourings with much more colours for a very long time):

        For example below you can find a 10-colouring of an icosahedron (I am not fully sure it is correct, I might have overlooked something in it (the tiles near the borders of the net were made in an ad hoc manner, which makes it much harder to check the correctness), but I think it can be generalized by dividing the colouring to clusters around the blue tiles and if we take a larger icosahedron, we can simply copy the clusters along the borders of the net, while those in the interior will be coloured with an Isbell colouring as they are in this colouring).

        You can also find a 9-colouring of an octahedron (it can be generalized much easier as it is much more regular), I have also tried to make similar colourings for icosahedrons.


        But sadly it seems to me, that simply projecting such colourings from an icosahedron to a sphere from their common center causes more distortion in the colouring as one would think (not to mention octahedrons):

        The circumradius of an icosahedron of edge length 1 is \sin\left(\frac{2\pi}{5}\right), so if we name its center O, one of its vertices A and the midpoint of a face having A as a vertex M, then |OM|=\sqrt{{|OA|}^2-{|AM|}^2}=\sqrt{\sin\left(\frac{2\pi}{5}\right)-\frac{1}{3}} meaning that for any sufficiently small segment sufficiently close to M, projecting it to the circumscribed sphere will scale its length by a factor sufficiently close to \frac{\sin\left(\frac{2\pi}{5}\right)}{\sqrt{\sin^2\left(\frac{2\pi}{5}\right)-\frac{1}{3}}}. Also, if we take a sufficiently small segment starting from A, the projection to the circumsphere is almost like an orthogonal projection, so its length will be scaled by a factor sufficiently close to \frac{\sqrt{\sin\left(\frac{2\pi}{5}\right)-\frac{1}{3}}}{\sin\left(\frac{2\pi}{5}\right)}. So in total the ratio between the images of two segments of the same length can be arbitrarily close to \frac{\sin\left(\frac{2\pi}{5}\right)^2}{\sin^2\left(\frac{2\pi}{5}\right)-\frac{1}{3}}\approx1.5836. And even though Isbell’s colouring is scalable, the ratio of the distance of two tiles of the same colour and the diameter of a tile is \frac{\sqrt{7}}{2}\approx1.3229. So here even if all pairs of tiles of the same colour have graph distance at least 3 in their adjacency graph, it is not necessarily enough for a large enough sphere (it depends on how those with graph distance 3 are located).

        (Side note: Dömötör also told me a few times while I was working on the proof for the Thomassen type chromatic number of the spheres being at least 8 that it might be easier to only look at a large enough disk in which no tiles with 5 neighbours occur and get a contradiction from that, and the above means that he might have been right.)

        Of course the above does not mean that by using some trickier projection, one could not make a good colouring on spheres.

        The good news is that it seems that in your colouring, pairs of tiles of surface distance \frac{\sqrt{7}}{2} only occur such a way that the two tiles are separated by an edge of the icosahedron, so even if it is not good for spheres (I haven’t calculated it yet), it is possible that some modification around the edges (like replacing the edges with very long, narrow rectangular faces and the vertices with small pentagons) resolves the situation. Anyhow, it needs a bit more calculation, but it is completely possible that based on your colouring all large enough spheres can also be coloured.

      5. Thanks so much Peter! Very nice colourings.

        I’m confused by your scaling calculation, though. The way I did it was just to look at the ratio of the radii of an icosahedron’s circumscribed sphere (which is sin(2*pi/4) as you say) and its inscribed sphere, which is (Sqrt[3]/12)*(3+Sqrt[5]). The ratio of these two numbers is 1.258, which is less than the scaleability factor of the Isbell tiling. The value that you get seems to be the square of this – and indeed, you seem to be expanding the tiles near M but also shrinking the ones near A. What am I not understanding?

      6. Yes, exactly. All segments near M go to nearly parallel segments after projection, and they are scaled with 1.258… compared to their original length, because as you wrote, that is the ratio of the circumradius and the inradius (I wrote it in a bit more complicated way, but we are talking about the same thing). But also, those near A, which are directed towards M go into segments roughly at the same place, but their direction is not parallel with the original one, thus they shrink with the same ratio as with what the other ones were expanded:

        If we take such a segment AP, then its image will be a segment AP’, where \angle{P'AP} tends to $90^{\circ}-\angle{MAO}=\angle{AOM}$ if P tends to A. The projection that takes AP to AP’ is almost an orthogonal projection (it tends to it if P tends to A), so the ratio of the projection tends to \cos(\angle{AOM})=\frac{OM}{OA}\approx1.258... if P tends to A.

        So in total the ratio of the two images is the square of 1.258… (unless I am overlooking something).

      7. Ah, I see, you’re taking into account that the tiles near the icosahedron’s vertices are inclined relative to the circumscribed sphere, so they will shrink when you project them onto the sphere. Fair enough. But I’m pretty sure it’s OK, because of the specifics of which same-coloured pairs of tiles are at the Isbell distance – namely, they are juxtaposed almost perpendicular to icosahedron edges, so the shrinking will not significantly reduce their separation. Right?

      8. [reposting in the right place!]

        Ha, we posted at the same moment. Yes, thank you. The hexagons near to the pentagons must clearly be somewhat distorted anyway. But maybe it still doesn’t work? I don’t have a rigorous mentalimage of this yet.

      9. Me neither. It needs a bit of more calculation to tell if it works or not. But as I already wrote, if it doesn’t, it is still possible to replace the edges with long, narrow rectangles, but it makes the calculation even uglier.

      10. OK, I now feel convinced that the difficulties arising from the stretching and shrinking that arises from projecting onto the sphere can be resolved simply. We consider each face of the un-sphericalised mega-ico separtely; a face is tiled with a standard honeycomb of congruent hexagons, with half-hexagons along the edges and a kite at each corner. Suppose that there are N half-hexagons along an edge. First, we define a diameter d for the hexagons, and a number x around 1/3 (let’s just say 1/pi), and we identify the six points on the edges that are dNx from a vertex. We then draw lines from each of those points, perpendicular to the edge on which they appear, so as to divide the face into seven regions, namely a central triangle, three rectangles and three kites at the corners. Then we do the same thing with a different value x’ that is just a little bit more than x, call it x(1+y). We then map all the vertices of our tiling according to y – in othe words we expand the kites uniformly by a factor x’/x, we shrink the central triangle by a factor (1-2x)/(1-2x’), and we change the aspect ratio of the rectangles accordingly. Finally we project this deformed grid onto the sphere. After some rough calculations, I’m pretty sure that there is a respectable range of values for d and y that makes every Isbell pair (including those that cross between regions or between faces) further apart than any hexagons diameter.

      11. Yes, I also think this will work (if I understand it correctly, this is a different formulation of the same colouring I recommended by replacing the edges with long, narrow rectangles (it uses a different polyhedron, but results in the same colouring after projection), but your formulation may be better for the calculations).

        I was considering such modifications, while making colourings (and other modifications of the shapes of tiles near the border), but I could not obtain an icosahedron colouring which only contains bad pairs on different faces, so I didn’t do the exact calculation.

    1. Wow. But I do not believe it yet. Let’s turn to the picture. Apparently, the edge (or side) between tile 1 from the bottom row 34134 and, say, adjacent tile 5 should give a straight line, since this tile 5 has a common vertex (or corner) with tile 1 from an neighbouring face of the dodecahedron. And this is possible only when the radius of the ball is the same as that of square pyramid. Or I’m wrong?

      1. Thanks Jaan for having a look. No, it’s OK. In the plane, the rigid diagonals of the tiles coloured 1 and 5 go between a {1,5,4} junction (call it A) and a {1,3,5,6} junction (at 2 o’clock on the central tile of the main disc; call it B) and between A and a {1,5,7} junction (call it C) respectively. As you say, there would be a “fattening conflict” at the 1-5 tile boundary if tile 7 did not exist, because the angle made by those diagonals is slightly less than 180 degrees. But the curvature of the sphere fixes that: the circle with its centre at the centre of the sphere that passes through B and C also passes through A, i.e. that angle is now exactly 180 degrees, so there is no fattening conflict any more. This happens because viewed from the centre of the disc, A is slightly clockwise of C, even though viewed from B it is slightly anticlockwise.

      2. I do not understand yet. Let me clarify. We consider the sphere and coloring in 6 colors after the disappearance of small tiles (with color 7). We continue to denote the junctions: {1,5,4} – A, {1,3,5,6} – B, {1,5,2} – D, {1,3,5,6} – E, and {A, D, E} are the corners of tile 1 from the bottom row of the picture, {A, B, D} are the corners of tile 5 from the adjacent row above. Tiles 1 and 5 share a common AD side. Both junctions B and E connect tiles with colors 1 and 5. As a result, we get a chain of colors 5-1-5-1 (from bottom to top, from right to left). Is it right so far?

    2. Ha, we posted at the same moment. Yes, thank you. The hexagons near to the pentagons must clearly be somewhat distorted anyway. But maybe it still doesn’t work? I don’t have a rigorous mentalimage of this yet.

  10. Good. We continue with my notation. We have a rhombus with sides AB, BD, EA, ED, which are all equal to 1. And we have a side AD, all points of which must also be at a distance of 1 from points B and E. So?

    1. Ahhhh… now I understand your challenge – I had not looked at the 1,2,5 junction. Hm… I need to think about this, but it does seem to invalidate the construction as I described it so far. Thanks!

      1. Yes, I think that this is possible only when large circumference of the sphere (or how is it called?) has length 4. That is, when the radius of the sphere is (2/pi).

      2. Correction of terminology. I thought (apparently wrong), that you meant half-sphere naming it squared pyramid. In this case the whole sphere is octahedron, of course.

      3. I suggest to think about whether it is possible to wind many layers of your 312-tile dodecahedron onto a sphere of radius (2/pi)? Or are there even more problems with self-intersections? But it could be an interesting multi-layer sphere (instead of boring octahedron), if you’re lucky.

  11. Funny question: what is the minimum number of colors required for proper coloring of “6992”-tiling (including diamonds and arrows)? Looks like 9 colors is enough. Who finds less?

    1. I think nine is correct. Reciprocal question: what is the largest number you can get while still only using seven colours, i.e. by stretching the tiling vertically and compressing it horizontally so that the small tiles can all be the same colour? (Clearly it must not have any arrowheads, only diamonds.)

      1. Hey, it was my question.
        I’m doing it now. And again faced with the instability of the solution while maximizing. I’m trying to understand which system of constraints leads to a quick and stable result. The same problem appears in the case of 5 colors, so we need to understand simpler examples. I decided to start from the very beginning and gradually increase the complexity of the tiles. Here are the current results so you can check them out.
        1. Classic 7-gon of Pritikin: 5681.489884345 for 7 colors (vs. 302.0962 by Edward Pegg), 6197.579308329 for 8 colors.
        2. Pritikin’s 7-gon with wavy inclined sides (11-gon in fact): 5782.990890412 for 7 colors, 6295.897444136 for 8 colors (with side-2-rectangle constraint I get more stable solution, but only 5780.207842396 and 6294.390840579).

      2. Great work Jaan! I had not actually noticed that Pegg’s original design allowed the small tiles to be all the same colour – we must mention that in the paper.

        Ah, but I don’t understand the last pair of numbers. What is the difference between “with side-2-rectangle constraint” and “classic 7-gon of Pritikin”? In my understanding, they are the same thing.

      3. There is a difference. But let me explain this a bit later. By the way, the parameter w was introduced (a long time ago) precisely for 7 colors task. And I have not finished. There will be options with a 12-sided diamond and curving.

      4. So far, a stable solution is obtained for a 9-gon with wavy inclined sides (13-gon in fact), but here I must also check these wavy sides. Diamond has 8 corners. There are problems with the 12-corner diamond. It seems like I know why: the functions of sides of diamonds are changing. For a non-curved 9-gon, I got 5976.095681162, after curving of some short sides 5977.261894810.
        Now about the terminology. I call a classic 7-gon the one without curving and without wavy sides, that is, an usual 7-gon with straight sides. Next, I examined a 7-gon with curved inclined sides and the usual 4-corner diamonds. There are options on how to set a distance of length 2: the sides of diamonds can form a rectangle, or a parallelogram. After that I tried to increase the number of corners of diamonds.
        I will continue further.

      5. I played with a 12-gonal diamond a little more. It looks like it is collapsing into an 8-gonal diamond. So the best solution that I get for 7 colors so far is 5977.261894810. Aubrey, could you confirm this result?
        I also think that the cause of the unstable solution is the appearance of vanishingly small quantities that lead to degeneration of matrices and division by 0 in the process of optimization. But so far I can’t solve this problem.

      6. While I was preparing a detailed answer, (it seems) I’ve found the reason for the poor convergence of the solution. I was let down by my generosity. I used constraints of the form =4 between all possible corners, in addition I used similar constraints between all points and line segments. It turned out that if I leave only constraints of the form ==1 and ==4, then this improves the convergence of the solution by several orders of magnitude.
        I propose the following notation. We take the original image of the 15-gon given earlier. In the case of 7 colors, the pairs of corners 8–9 and 10–11 are collapsed into two corners. I don’t want to use other notations, so I just drop the corners 9 and 10, and leave 8 and 11. To work with constraints of length 2, we need to mark the tiles of the diagonal row around two neighbor diamonds. Let it be tiles a, b, c, d (from left to right, from bottom to top), with b being the base tile (drawn earlier), a – its reflection relative to the origin, d – the tile shifted by (g+h, 1.5w) relative to the base tile b. Then the necessary points of the plane are denoted by a pair of letter-number.
        For 7 colors with reduced set of constraints {| b1-b8 |==1, | b2-b8 |==1, | b3-b11 |==1, | b4-b11 |==1, | d3-a2 |== 2, | d2-a3 |== 2, | d2-a2 |==| d3-a3 |} the result is 6043.112467879 (if I was not mistaken somewhere).

      7. Yeah, latex ate part of the text. It was written …used constraints of the form “equal or less than 1” and “equal or more than 4″…

      8. Um, you also need 2*|b4 – b12| == |b1 – b15| + 1, right? Please confirm before I get on this.

      9. Hm, I’m not reproducing it. I’m getting a maximum of 5874.62, with points 1..4,8,11 being at (0,0.0142901), (0.000655472,0.0116867), (0.00398441,0.00390976), (0.00631691,0), (0.970063,1/4+a/2) and (0.863933,1/2+a). My central parallelogram does not collapse, though it is a rectangle (the parallelogram is slightly smaller but the gain is outweighed by the radius-2 slivers). What are your coordinates?

      10. Thanks, Aubrey. I am not surprised. Whenever I run optimization, I get a new result. It is like a random number generator. Our results may coincide accidentally, but we will never know the right one.
        I substituted your values and got 6042.52977236409. But some distances are slightly more than 1. I also got almost your 5874.63162557873, if instead of w, I use 0.5 when calculating the total area.

      11. Hm, I’m not having any such problems with reproducibility. Also, I’m checking the lengths of diagonals arising from the returned values and they are all coming out exactly right (well, to within 10^-15). I think you must have a bug somewhere.

      12. Ah, damn, I maligned you! I was the one with the bug – I was indeed calculating the number using w=1/2. I now obtain 6043.112468 with (0,0.0143908), (0.000721488,0.0115263), (0.00400433,0.00385627), (0.00630569,0), (0.970075,1/4+a/2), (0.863862,1/2+a).

      13. I guess now is the time to switch our attention to five colours. I’m simultaneously pursuing several other strands of the paper, as you can see, but I’ll try to do something.

      14. Something we must not forget in the paper: I just realised that the slanted edge 9-10 in Jaan’s picture is not precisely parallel to the edge 2-3 – the slopes are about 2.4996 and 2.4217 respectively (this is for the standard 6992 case). This means that there needs to be a zigzag in the middle of the 9-10 edge, so that the central section is exactly parallel to 2-3. So our large tiles get four extra vertices.

  12. I have circulated a draft note by email on upper bounds in higher dimensions. This note can be included in a polymath paper. The results have appeared in earlier threads and are in the wiki.

    Aubrey asked some general questions so I will post some partial answers here to keep it open.

    We found new upper bounds for 5 and 6 dimensions using permutohedron tesselations and linear colourings, adding to previous published bounds in 2, 3, and 4 dimensions. For up to 5 dimensions the search is exhaustive so we know these are the best bounds of this (very restricted) type

    A permutohedron in n-dimensions is an n-dimensional polytope formed from vertices whose coordinates in n+1 dimensions are the permutations of the first n+1 positive integers. The minimum width of the permutohedron is \sqrt{n(n+1)} and its diameter is \sqrt{n(n+1)(n+2)/3} . If it is rescaled to have unit diameter then the minimum width is \sqrt{3/(n+2)} . At n=10 this is 1/2

    We need to find all “dangerous” cells that have points within unit distance of a central cell in the tesselation. For from 2 and 10 dimensions this will be the touching cells and the next layer out that touches those cells. There should be a formula for the the number of cells in these layers which we can find to give us the number of dangerous cells up to n=10. For n >= 11 some additional cells from the next layer must be included but this is well beyond where we can currently search anyway.

    1. Thanks Philip! You already corrected yourself in email regarding the third layer, so let me just save others the trouble of pointing out that we get third-layer cells in the danger set even as soon as n=4.

  13. I have coded up the geodesic dome as a graph with the faces as vertices and edges between faces that share a boundary or that both share a boundary with the same third face, and I’m throwing it at my Mathematica SAT solver for increasing numbers of hexagons between pentagons – and the big news is that it’s very rapidly returning SAT for 9 colours for every length (though it’s getting pretty slow by now at building the graphs and clauses). I’m not checking 8 colours yet because that already got really slow even for n=3 (it is SAT for n=1 and 2); I’ll try that overnight. I’m up to n=16 so far, i.e. comfortably into Peter’s radius-18 territory. (Reassuringly, it’s always returning UNSAT for 7 colours.)

    Turning this into a colouring for arbitrary size may be hard, though… if I get time I’ll have a look at the small cases and see if I can discern any pattern, but the speed with which solutions are being found leads me to fear that there will be a lot of randomness and nothing will leap out without massive serendipity. If I get an 8-colouring for n=3, I’m hoping things may be better in that regard, since evidently if such colourings do exist they are rare.

    Note that I am only looking at the simple case where there is a straight chain of hexagons between edges; I have not explored the skewed cases such as the one Peter shows on his Google Drive page. Presumably those are also worth checking wrt 8 colours.

  14. Update: the geodesic sphere with three hexagons between pentagons cannot be 8-coloured. My solver established that in ten minutes; it was undecided on the four-hexagon sphere when I aborted it after two hours.

    I’m now asking what happens when we replace each vertex of the mega-ico by a Gibbs disc; this can be done quite efficiently starting from the geodesic graph, by just removing the five vertices (i.e. hexagons) neighbouring each pentagon-vertex and adding 240 new edges (20 for each pentagon). (It only makes sense when the initial geodesic sphere has at least five hexagons in the inter-pentagon chain.) Sadly I am not getting any improvement on the simple geodesic sphere: with n=5 it is hanging for 8 colours. I think there is a good chance of improvement using Peter’s skewed design though (and variants thereof). I’ll try to get to that soon.

    1. That is surprising! I would have guessed that it becomes 8-colorable for very small n. Is it possible that for larger n the program would run faster because it would have more freedom?

      1. Possible, but equally it could go more slowly if at small n it is still truly not 8-colorable. But my intuition is that skewing makes a big difference, allowing Isbell-style colourings to encroach closer to the Gibbs regions.

  15. Philip tells me he has posted something here – Dustin, is it in purgatory? [I found it in the spam folder. -DGM] It is a brief writeup of the work on upper bound in higher dimensions, extending Radoicic and Toth, which will be a sectionin the paper.

    Meanwhile I too have been looking at higher-dimension tilings and I’m fairly hopeful of progress. I have been looking at the Weaire–Phelan structure, hereafter WPS (see Wikipedia for details), which was shown to have a fractionally lower surface-to-volume ratio than the permutohedral (“Kelvin”) structure, and which I think has a slightly smaller set of prohibited neighbours (for both types of cell) than the 65 we get for permutohedra, by virtue of the fact that 1/4 of the cells are dodecahedra rather than tetradecahedra. That won’t translate into a tighter upper bound, of course, because the presence of any tetradecahdra limits it to 15. However, I’m more optimistic when we generalise the WPS to higher dimensions. I’m proceeding as follows:

    If I’m not mistaken, the WPS tiling of R^3 can be described as the Voronoi tiling arising, for all triplets {i,j,k} of integers, from “type A” points (4i,4j,4k) and (4i+2,4j+2,4k+2), which lie at the centres of the dodecahedra, and “type B” points (4i,4j+2,2k+1), (2i+1,4j,4k+2) and (4i+2,2j+1,4k), which lie at the centres of the tetradecahedra. For our purposes the key degree of freedom is that the planes separating type-A cells from type-B cells need not be exactly midway between their respective points: we can choose how far along the AB line they sit, i.e. shrink or grow the type-A cells, so as to make both types have the same diameter. (I think the fact that B cells necessarily have a width of 2 makes this optimal.)

    I think the best generalisation of this to R^n is to have type A points be those with all coordinates 0 mod 4 or all coordinates 2 mod 4, and, for all i in 1..n, to have the type B points be those at 0 mod 4 for dimension i mod n, 2 mod 4 for dimension i+1 mod n, and 1 mod 2 for all other dimensions. This seems to give type B cells a width of 2 for any n, and type A cells a width of Sqrt[n+2]. Where it gets interesting is with the diameters. I think type A cells have a diameter that is an at most logarithmically-increasing (or even bounded?) multiple of Sqrt[n+2], because each type A cell has a pretty dense packing of B cells around it. But this also applies to type B cells – I think their diameter is bounded at slightly more than Sqrt[10], or at worst rises logarithmically in n. (There are n times as many type B cells as type A, so maybe it isn’t crazy that the dimensions of type B would grow more slowly? Or is this offset by their constant width?) This would mean that when we shrink the type A cells to make the diameters equal, we shrink them more for higher n – in other words, we end up with a diameter/width increasing more slowly than O(Sqrt[n]), which would surely translate into a better chromatic number than for permutohedra. But I haven’t fully convinced myself of all this yet – all help welcome.

  16. No luck yet with skewing… but I have noticed that there’s a conflict (just one, it seems) in Peter’s attempt at a 10-tiling of a skewed icosahedron:

    I’ll try to get Mathematica to render some 9-colourings soon.

      1. Looks good! Meanwhile I have figured out an elegant way to encode skewing, so I will try a few more things today. I will also export the clause lists for these graphs so that those with superior SAT solvers can attack CN=8 for the various spheres.

  17. Everyone: the burst of activity stimulated by the plan to write an all-encompassing upper-bounds paper leads me to propose a slight change of plan. I had (more or less) promised Soifer that we would submit in time for his next issue, but it’s now clear that if we were to try to do that the result would be horribly rushed and incomplete. Therefore, I propose that we aim for the following issue, which may allow us to present properly polished discussions of the various outstanding areas (5-proportion, 6-disk, n-sphere, non-permutohedron tilings)as well as the areas where we are already satisfied that we have closure (4-strip, 5-disk, 6-proportion, permutohedra). I will pacify Soifer with a writeup of my 59-vertex 6-chromatic thing in R^3, which was not really part of the Polymath project anyway and which I think I can get done in time for the upcoming issue.

    Unless anyone objects today, I will notify Soifer accordingly.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s