I write, therefore I am
With this variation on a famous statement by the philosopher Descartes, I would like to express that writing about what happens in my life is important to me.
Hexagon and double pentagon chainYes, it is indeed possible to reduce the chain which alternating a face with six sides (a pentagon) and a pair of faces with fives sides (double pentagon). It took me some puzzling and programming, but I did find the following table:
001020 00 00 00 21 12 202020 00 00 00 21 12 100020 00 00 00 21 12 010002 12 21 00 010101 21 00 12 010200 00 12 21 112221 21 21 21 12 00 211122 12 12 12 00 21
The first row represent values around two faces with five sides on top of each other sharing one side. The values start from the left bottom and go round clockwise. The table shows how two of these patterns can be joined together side by side, creating a face with six sides in the middle. The numbers giving at the crossing are the values of the faces on top and on the bottom of the face with six sides. It shows that any sequence of values can be made. Furthermore it is the case (so I believe) that for any sequence that can occur in a planar graph, the chain can be made to close. It does not matter with which pattern in the first column you start. I do not have a proof for this, but for all sequences up to and including nine, it works usually in more than one way.
Euler characteristicWith the help of the Euler characteristic for planar graphs and some other properties, it is possible to derive a statement on the number of faces with a certain number of edges. If we define Ni as the number of faces with i edges, and only faces with five or more edges are allowed, than we can write down the following equaltion:
Note that the number of faces with six sides does not appear in this equation. The equation shows that the number of faces with five sides is always larger than the number of any other kind of faces, except for the number of faces with six sides, which can be any number. However, with the constrains I mentioned yesterday with respect to the Four colour theorem, it seems hard to construct planar graphs that meet the requirements taking into account the above equation. I have not been able to construct a planar graph yet, although I have to admit that I did not try very hard yet.Construction of planar triangulations with minimum degree 5 by G. Brinkmann and B. D. McKay. Through this I also found the program plantri for the generation of all kinds of triangular graphs, amongh those with minimum degree 5. This evening, I wrote a program to read the output of the program and check it for patterns that can be reduced, hoping that many graphs would contain patterns that can be reduced. However, I the only planar graph on 15 vertices already contained a pattern that could not be reduced. But it does contain an interesting kind of chain which alternates a face with six sides and a pair of faces with five sides. Maybe it can be reduced in some manner.
ReductionsIn the past week, I have found some more reductions with respect to the Four colour theorem. With reductions, I mean constructs that can be removed without affecting the colourability. Any closed chain of faces with six sides that touch on oppositing sides can be removed such that the corners not touching the other faces with six sides are connected. Also open chains that have end on both sides with a face with four sides can be removed. Actually, this is quite obvious, because if one the faces with four sides is removed, another faces with four sides appeares. And this process can be repeated until no square is left. Also two touching chains of three faces with five sides can be removed, leaving some connections. The same is true for two chains of five such faces. With this a dodecahedron graph can be reduced to three unconnected rings, for which can be coloured with only two colours. Also a chain of ten sides alternating connecting a side on the inside and the outside can be removed, by alternating removing and keeping a side, which can be done in two ways. Again, if this is applied to a dodecahedron graph, it results in five faces with four sides and two faces with five sides, which can be furthur reduced. I am looking into the properties of side chains with different lenghts.
Magnolia seedsThis morning, I discovered some berries on our magnolia in the back of the garden, and I took a close-up picture. In the evening I took these, and one that Annabel found on the other side, inside. I peeled the three berries and we put the black seeds inside a zip bag with some moist potting soil according some instructions we found on YouTube. We put the zip back in the shed in the backgarden instead of the refrigerator because it will be about the same temperature the coming months. From the description of the different magnolias, I get the impression we have magnolia stellata.
Four colour theoremIn the past weeks, I have been working on trying to proof the Four colour theorem, based on sequences of 0, 1, and 2. The idea is that if the faces (areas) of a planar graph can be coloured with at most four colours, it must be possible to label all the vertices with either 1 or 2 such that the sum of the labels of each face is a multiple of 3. If you start with just one vertex and label it with 1, you can lay a robe around it. Assuming that one can restrict to planar graphs were all vertices have degree 3, this robe will cross three faces, and we can assign a number to each part, which equals the sum of labels of the vertices of that face inside the robe. In the starting position all parts of the robe will be labelled 1. Thus we can assign the sequence 111 to the robe. Now the robe can be extended in a number of steps equal to the total number of vertices minus two, such that every time a new vertex is included inside the robe. After these steps, the robe will include all but one vertex. At each step the number of faces that crosses the robe will be increased by one, when the new vertex has only edge with the existing group of vertices, or decreased by one, when the new vertex has two edges with the existing group. When the number of faces that are crossed increases, the new vertex can be labeled with either 1 or 2, meaning that the number of sequences that can be assigned to the new robe position doubles. When the number of faces decreases, it is possible that some sequences on the robe in the original position can not be transformed into a sequence on the extended robe, and if it is possible, only one value can be assigned to the new vertex.
If the four colour theorem is true, it means that it is always possible to perform the above operation on any graph and end with a sequence 111 or 222 in the end (or possibly both) by a number of intermixed expansions (when the number of faces increase by one) and contractions (when the number of faces decreases by one). If we can proof this property of the set of sequences, than we can proof the four colour theorem. If the four colour theorem is true, any intermediat set of sequences can be contracted in any possible way. If we could just proof that for each such set being expanded in any possible way, has the same property, then the four colour theorem is proven. On first sight this would not look very difficult at all, but that is not the case. I made some attempt to prove this, and discovered that it cannot be proven for just any set of sequences that can be contracted in any possible way. This mean, that one has to discover some property of the sets of sequences that can be reaced by any number of intermixed expansions and contractions. There are simply an infinite number of them.
I started with some simple cases and discovered that it is always possible to remove a face with four edges. This means that the Four colour theorem only needs to be proven for graphs with only faces with five or more edges. (I discovered today that this was already known by Alfred Kempe.) I wrote a progam to investigate the kind of sequences on robes around certain graphs. The main function for calculating this is given a number of points, a string representing the graph, and a number of rotations that it should generate sequences for. The string giving the graph uses letter starting from 'a' to label the graph. If a sequence of letter is followed by an equal sign, the function checks if the values for these point add up to zero modulo three. If it is followed by a comma or at the end of the string the value of the points modulo three is added. The values for which the function is called are:
110112 * * ** * * * ** * * ** ** 112221 * * * * * * * ***** ** 112110 * * * * * * * ** * * * ** * 111222 * * * * * * * **** ** * 102102 * * * ** ** * * * * * * 102000 * * * * * * * * ** 101010 ** * * * * * * * * 000102 * * * * * * * * * * 000000 * * 001020 * * * * ** * * ** 012012 * * * ** ** * * * * * * 010002 * * * * * * * * * * 010101 * * * * * * ** * * 122211 * * * * * **** ** ** 122022 * * * * * ** * * * ** ** 101121 * * * * * * ** * * ** ** 011211 * * * ** * * * * * ** ** 121101 * * * * * * ** * * ** ** 120012 * * * * ** ** *** *** 100212 ** * * * * ** *** *** 001212 ** * * ** ** *** *** 012120 ** * * ** * ** *** ** 121200 ** * * ** ** ** *** * 121002 ** * * ** ** *** *** 120120 * * * ** * * * * ** * 100020 * * * * * * * * * 010200 * * * * * ** * * 110220 * * ** ** ** * * * ** * * 102201 * * ** ** ** * * * * * * * 011022 * ** ** ** * * * * * * ** 111111 *************** *This shows that there are many combinations of sequences that do meet the requirement that there is at least one of the sequences can be contracted in any possible way, but nevertheless do not contain one of the first thirteen sequences for the two joined faces with five edges (and five vertices).
Bug in compilerLooks like I found a bug in the Visual Studio 2008 where it seems that certain expressions in C++ are evaluated different when optimization is applied or not. The combination of a static cast to the type "unsigned char" and a comparison is causing the problem. The following expression, where str is a variable of type "char *":
if ((unsigned char)(*str) < ' ')The "char" type was introduced for the representation of characters. At first only the ANSI characters raging from 0 to 128 (not including). These values fit in 7 bits, so when the byte became the default smallest unit of storage consisting of 8 bits, there were two choices to extend the range. The implementors of C decided that the "char" type would be a signed type with values ranging from -127 to 128. Although this chouce gives you a 'small' integer with negative and positive values, it also has lead to many programming errors, because it is more natural to think that it ranges from 0 to 256. The type "unsigned char" ranges from 0 to 256, where the values 128 to 256 map on -127 to 0. Appearantly, it also has lead to errors in the machine code optimizer of Visual Studio 2008, which tries to find the most compact sequence of instructions for executing the program.
Wednesday, November 13, 2013
MushroomsI discovered some mushrooms in the lawn. I took this close-up picture of the largest mushroom. It is really not that big at all.
Komputerstrukturen 2aToday, I analyzed various pictures of the work Komputerstrukture 2a by Peter Struycken in order to check if the reproductions of this work are correct. I studied this on February 6. I spend several hours manually 'digitizing' the four pictures that were taken during the opening of Mondraanhuis on which the work was visible. There were two pictures at close distance with people in front of it only showing part of the work and two pictures taken from a distance, which contained the whole work, but at a low resolution due to the distance. Next I wrote a program that could compare the data from these pictures with a reproduction of the work. This program produced output with the data in which an underscore character is placed at locations that are different from the other pictures. I compared these with the original pictures and tried to fill them in again. This resulted in corrected versions. I added these to the program and compared them again. Later, I also included data from to newspaper articles with a close up picture of the work with Peter Struycken in front of it. Finally, all the data agreed with each other, leading to the conclusion that the reproductions of Komputerstrukture 2a do not contain errors.
TPPWAt the end of the afternoon, I received a small package with an artwork by Peter Struycken. It consist of a recreation of "Process of continuing changing television screen" that he made in 1989 as a commissioned work for the main hall of the VARA offices at Heuvellaan in Hilversum and which was later transfered to Groninger Museum where it is known under the title Vara-programma. The package contained a Cubieboard, which runs the program generating an ever changing sequence of images according to the TPPW program. Floris van Maanen has done the programming using Python. The front contained a print of one of the sequences, just as the box it was packaged in. I don't know if it was send as a birthday present, but I surely find it a very beautiful present.
I made this drawing of graph representing the transition table I constructed over the weekend. The arrows with the red triangle are the transitions for 1, and with the blue triangle the transitions for 2. The light grey lines, connecting opposite points, represent the transitions for 0 in both directions. The green lines represent some transitions for 211 or 122 and the purple lines for 221 or 112.
Even more sequencesAfter some puzzling, I constructed the following transition table:
0 1 2 a b c d b a e f c g h i d j k l e l j k f h i g g c d b h f a e i k l j j d b c k i g h l e f a
Given a sequence of 0, 1, and 2, the above table can be used to calculate the value for the sequence, by starting with 'a' and calculate for each element in the string another value by using the above table. Now it appears that whenever you end with 'a', that the sequence is a sequence that can be generated from 00. For sequence generated from 12, you get one of 'b', 'i', or 'k'. I guess it will not be very difficult to prove this, by the effect of rules for replacing two digits by three digits in the generation step. Below the table extended with the number of sequences ending at the given letters:
all 00 12 'b' 'i' 'k' 2 2 0 1 0 1 0 3 3 1 1 0 0 1 4 6 2 3 1 1 1 5 9 2 6 2 3 1 6 22 8 13 4 6 3 7 40 10 29 12 8 9 8 100 33 66 19 23 24 9 225 57 167 60 56 51 10 582 168 413 146 135 132 11 1464 366 1097 370 361 366 12 3960 1061 2898 951 984 963 13 10585 2646 7938 2714 2611 2613 14 29252 7514 21737 7226 7255 7256 15 80819 20209 60609 20285 20189 20135 16 226530 57233 169296 56520 56426 56350 17 636321 159080 477240 159376 158879 158985 18 1800562 451928 1348633 449392 449753 449488 19 5107480 1276870 3830609 1278053 1276311 1276245
When studying the transition one can see that each column has all the letters from 'a' to 'l' exactly once, meaning that they are permutations of each other. It is well known fact that any set of permutations is related to a finite group. The table can be used to construct the following group (with 12 elements):
* 0 12 21 22 01 10 1 11 20 02 2 0 * 21 12 10 1 22 01 20 11 2 02 12 21 * 0 1 10 01 22 02 2 11 20 21 12 0 * 01 22 1 10 2 02 20 11 22 01 10 1 2 20 11 02 12 0 21 * 01 22 1 10 11 02 2 20 0 12 * 21 10 1 22 01 02 11 20 2 21 * 12 0 1 10 01 22 20 2 02 11 * 21 0 12 11 02 2 20 21 12 0 * 1 22 10 01 20 2 02 11 12 21 * 0 01 10 22 1 02 11 20 2 0 * 21 12 22 1 01 10 2 20 11 02 * 0 12 21 10 01 1 22
In this table '*' stands for the empty sequence, and it also happens to be the identiy element. This is the Alternating group A4, because it is the Von Dyck group with, for example, a is 12, b is 10, c is 02 and a2 = b3 = c3 = abc = e.
Two more sequencesI continued working on the program working on sequences of 0, 1, and 2. I suspected that the sequences can be divided in two groups, namely those that can be generated from the sequence 00 and those that can be generated from the sequence 12. By generating, I mean a process of replacing two digits of a sequence by three, by inserting 0 in the middle and either adding 1 or 2 to all three digits (modulo 3). For example, given the sequence 0012 we can generate another sequence by taking 01 from this sequence, insert 0 in the middle (resulting in 001) and add 1 to each of them (resulting in 112) and replace the 01 in the original sequence with it, resulting in 01122. Sequence 01122 can thus be generated from the sequence 0012. It is clear that any sequence consisting three or more 0 cannot be generated from either 00 or 12, because in each generation step, there is always either a 1 or a 2 inserted. The program shows that it is indeed the case that the sequences that can be generated from 00 and 12 do not overlap for all sequences with length up to 14. I haven't found a mathematical proof that this is the case for all sequences. This leads to two sequences that are related to sequence A056353. It is remarkable that there are much fewer sequences that can be generated from 00 than from 12. The table below is taken from the output generated by the program
all 00 12 3 3 1 1 4 6 2 3 5 9 2 6 6 22 8 13 7 40 10 29 8 100 33 66 9 225 57 167 10 582 168 413 11 1464 366 1097 12 3960 1061 2898 13 10585 2646 7938 14 29252 7514 21737
Sequence A056353I wrote a program that produces the sequence A056353. The program calculates the number of sequences consisting of 0, 1, and 2, such that the sum is a multiple of 3. Furthermore, sequences that are rotated, reversed, or have 1 and 2 exchanged, are considered the same. The sequences for the first number of length are:
Trip to China 2010
-- contact -- Frans
My life as a hacker
The Art of Programming
HTML to LaTeX
eXtreme Programming Hamilton cycles