Menu

Lorenz Milla

Recent Work in Squared Squares

In April 2012, Lorenz Milla completed searches of the 13 and 14 vertex, 31 edge polyhedral graph classes, using Stuart Anderson's noddy (node analysis on electrical nets) software and found 61 new SPSSs of order 30 (there are all up 75 SPSSs derived from the 31 edge, 14 vertex graphs, and none from the 31 edge, 13 vertex graphs).

2013 March and April; Lorenz Milla and Stuart Anderson enumerated simple squared squares of order 30. Lorenz used plantri (McKay/Brinkmann) to generate graphs, and Stuart Anderson's sqfind to find squared squares and his sqt to encode the dissections. Lorenz ran the programs on 17 dual core computers over the Easter school holidays. Some 6756 new SPSSs were found, combined with the known 13810 SPSSs of order 30 (including 9189 SPSSs found in Jan/Feb 2013 by James Williams) there are 20566 order 30 SPSSs in total. Simple Imperfect Squared Squares (SISSs) of order 30 were also enumerated. The total for order 30 SISSs is 667403. A total of 193130 order 30 (Compound Imperfect Squared Squares) CISSs was also found - unlike the SPSS and SISS counts, the CISS count is not a complete enumeration.

2013 May, Lorenz Milla and Stuart Anderson enumerated CPSSs of order 30. Lorenz processed 13, 14, and 15 vertex, 2-connected, minimum degree 3, 31 edge graphs of order 30 (8,377,405,224 graphs), then Stuart and Lorenz processed half each of the 16 vertex, 2-connected, minimum degree 3, 31 edge graphs (35,873,044,824 graphs) to find 941 CPSSs, with 5668 CPSS isomers in order 30. Stuart and Lorenz both wrote new software; they implemented a technique of Tutte's, used by Duijvestijn in his thesis, that factors the Kirchhoff matrix determinant of a graph into a product of 3 numbers as follows; 2, a square free number and a square number (this is a necessary condition for a graph to produce a squared square). This method resulted in a 3x speed up of the search. This part of the search was implemented as a program called sqfree, available on the downloads page. Lorenz also produced new software to produce the all isomers of the most common types of CPSSs and identify the canonical tablecode representative from the isomers of a CPSS.

2013 June, July, August; Lorenz Milla and Stuart Anderson rewrote the software to improve the efficiency of the determinant factorisation technique recommended by William Tutte in his writings to speed up squared square searches. Lorenz replaced the Boost library with C arrays and handwritten linear algebra routines; LU decomposition was replaced with LDL decomposition (planar maps have symmetrical matrices, so LDL Cholesky decomposition is possible and twice as fast as LU decomposition). Lorenz also wrote a plantri plugin to filter graphs using the determinant factorisation technique as they were produced, he was also able to speed up the routines in the sqfind and sqt programs and combine the plantri plugin and sqfind into a single program mandrill (a combination of the names Milla and Anderson). The end result was squared square software 35 times faster than what was used several months ago. This made it possible to complete the enumeration of order 31 and 32 compound perfect (CPSSs), simple perfect (SPSSs) and simple imperfect squared squares (SISSs) in under 2 months. The computations were done by Lorenz on his computers. There are 54541 SPSSs in order 31 and 144161 SPSSs in order 32. There are 17351 order 31 CPSS isomers and 2788 order 31 CPSSs (isomer classes), 52196 order 32 CPSS isomers and 7941 order 32 CPSSs (isomer classes).

Lorenz wrote a paper, Smallest Squared Squares (Pdf) In this paper we have a look at squared squares with small integer sidelengths, where the only restriction is that any two subsquares of the same size are not allowed to share a full border. We prove that there are exactly two such squared squares (and their mirrored versions) up to and including size 17x17. They are shown in Figure 1 (page 2). This result was used to provide a lower bound on squared square size for the mandrill programs.

A Short Biography

Currently, I'm working as a teacher for Mathematics and Physics at the Elisabeth-von-Thadden-Schule in Heidelberg, My diploma thesis (attached, in German).