file announce.txt announcement of search results changed 16:10-11:25 PST, 23 December 2005 at argus changed 11:05-11:15 PST, 23 December 2005 at argus changed 10:20-10:30 PST, 23 December 2005 at argus created 00:00-01:10 PST, 23 December 2005 at argus 0. Abstract 1. Problem 1.1. Complication SL(2,z) 2. Approach 2.1. Edge Length Bound 2.2. Polygon Ordering 2.3. Corners 2.4. Algorithm 3. Simplifications 3.1. Fractions 3.2. Even Theorem and Odd Heuristic 3.3. Normalization 4. More Complications: Margin 5. More Algorithms: Random 6. New Algorithms 6.1. Dynamic Programming 6.2. Current State 7. Results 0. Abstract This note describes my progress and results on the minimum area convex lattice polygon problem. My programs have results up to n=100, with some confidence. I have realized that this note is fairly cryptic as an explanation, and yet it is still too long. More details are available 8-). 1. Problem To find the minimum area convex lattice polygons with n sides for small n (polygon = convex lattice polygon in the rest of this note). 1.1. Complication SL(2,Z) Since SL(2,Z) preserves area, all SL(2,Z) images of a minimum area polygon are also minimum area polygons. That means that there are infinitely many different minimum area polygons for each n. 2. Approach 2.1. Edge Length Bound I addressed the SL(2,Z) problem by running searches with an imposed maximum edge length bound b to reduce the search to a finite number of possibilities. This means that my results tell us almost nothing about how many SL(2,Z)-classes of minimum area polygons there are, since there is no theorem about class representatives with small maximum edge length (in many but not all small cases, my programs found more than one such class). 2.2. Polygon Ordering My programs use an ordering among the polygons first by smaller area, then by same area and smaller perimeter, and finally by same area and perimeter and smaller maximum edge length. Note that the ordering of polygons by area is different from the ordering by perimeter. It frequently occurs that the minimum area polygons do not have the minimum perimeter. So a minimum polygon has minimum area among polygons with n sides, but also minimum perimeter among the polygons with minimum area, and also minimum maximum edge length among the polygons with minimum area and perimeter. There is no assumption that a minimum polygon is unique. 2.3. Corners My programs always consider polygons as enumerated from the vertex with the least y value (and the one with the least x value if there are two least y values), in a counter-clockwise order. This means that the angle of the oriented edge vector is increasing from at least 0 to just under 2*pi. Each edge can be identified as belonging to a corner, representing the number of pi/2 clockwise rotations required to change the oriented edge vector into one that moves up (positive y) and to the right (non-negative x). This is the same as the first quadrant, modulo the boundary rules just mentioned. 2.4. Algorithm The first algorithm I wrote attempted to move an edge around in the lattice and keep adding new edges with larger angle. It was good enough to extend the results up to n=17 or so, but quickly ran out of steam. 3. Simplifications Other hints and messages on math-fun led me to two important simplifications and a potential simplification that I could not use (though it took me a long time to figure that out). 3.1. Fractions An edge of a minimum area polygon has no interior lattice points, so the edge coordinates are relatively prime. We can identify each corner0 edge with a fraction n/d, where 0<=n, 1<=d, gcd(n,d) = 1, and we decided to use the L1 length, so our edge length bound is n+d < b (it is a historical artifact that the inequality is strict). The number nf of such fractions is easy to count nf(1) = 0; nf(b+1) = nf(b) + phi(b), so nf(b) = sum(1<=d<=b-1) phi(d), which we give as a small table here b nf(b) 1 0 2 1 3 2 4 4 5 6 6 10 7 12 8 18 9 22 10 28 11 32 12 42 3.2. Even Theorem and Odd Heuristic Somebody mentioned on math-fun a theorem that for n even, there were always edge-symmetric minimum area polygons. That means, in my corner terminology, that corner2 is the negative of corner0 and corner3 is the negative of corner1. I also noticed that for odd n up to about 21, there were always minimum area polygons with corner0 plus corner1 being almost half the sides, so I assumed that in all subsequent searches. Using this restriction also ignores many potential SL(2,Z)-classes of minimum polygons. 3.3. Normalization If the polygon start vertex (least y value, and least x value if there are two least y values) is moved to the origin, then there are elements of SL(2,Z) that will move the next vertex to (1, 0), so we could make the assumption that the first edge is [1, 0]. The reason my programs can't use that assumption is that there is no control over the maximum edge length of the resulting polygon. Omitting that assumption made the searches much longer, but did occasionally find better polygons. 4. More Complications: Margin Because my programs use an edge length bound, my original strategy was to gradually increase it until no better polygons are found. However, the following peculiar phenomenon occurs: for n=27, 29, 31, 33, with edge bound 6, my programs found minimum polygons with maximum edge length of 5. For the same n, with edge bound 7, the same minimum polygons were found, so I thought that the programs were done with those cases. However, when the program was run with edge bound 8, better polygons were found for all of these n, with maximum edge length of 7. So the concept of margin now becomes important as a measure of confidence. The margin of a result is the difference between the edge length bound and the maximum edge length found for a minimum polygon. The peculiar phenomenon shows that margin 2 is not enough. This phenomenon has not occurred for any other n, and my programs are currently working on extending the results to margin 4 or 5. 5. More Algorithms: Random The backtrack programs take a long time (the last one currently running has used over 1600 hours of cpu time so far, and we expect it to use about 2000), so I rewrote the backtracking algorithm into a random program, that would make a random next choice instead of the next available choice. In large cases, the random found several polygons better than any of the systematic searches had. 6. New Algorithms This was the state of affairs for almost two years, as I occasionally posted some partial results to math-fun (without a lot of confidence in the larger values). These program were running almost continuously on between two and six of my fast computers (high-end commodity Intel PCs running FreeBSD 5.4, all between 3GHz and 3.6GHz, each with 4GB of memory and at least 1TB of disk space) and a few others, for the entire two years, stopped only two or three times by city power failures, usually for less than a day (my multiple UPS arrangement made the dozen or so shorter power blips during that time irrelevant). 6.1. Dynamic Programming In October, after some data mining of the program performance parameters (I always collect these for medium and large programs, if only to know or at least predict when they might finish), I finally hit upon a useful improvement of the backtracking program. I realized that my programs were finding all the same partial polygons, over and over again, and that if they could save them, it would greatly speed up the execution. Well, the tradeoff here was between the Scylla of more time than there is (heat death of the universe pales in comparison) and the Charybdis of more space than I have (I only have 8TB of disk space at home), and after several explorations that ran up against each extreme (the predictive models I made using the performance parameter measurements were part of this assessment; I didn't have to wait for it to happen 8-)), I finally found the obvious: I use dynamic programming to build p-maps (sequences of p edges that could be part of a polygon), p-halves (sequences of p edges that could be half of a polygon), and polygons. The dynamic programming approach leads to much faster systematic searches. In two months, I have confirmed all my previous results from the previous two years up to n=99 (and improved some that had margin 1), superseded all previous random program results, and extended the margin to at least 3 for all even n up to 100, all odd n up to 87. The dynamic programming approach also leads to a possible explanation of the half-size heuristic: if the area of half a polygon grows much faster than linearly, then the best combined area is nearly split evenly among the parts (don't take this argument too seriously; it needs some background definitions to be more precise, and it is still not a proof). 6.2. Current State My programs have computed results for all n up to 100, currently with margin at least 3 for all n, except 91, 93, 97, 99 (which have margin 2). The programs are currently running to extend the margin to at least 4 for all n up to 100 (with the same four exceptions), and to extend the results up to n=112 with b=14, which should give margin at least 2 for that range (the largest maximum edge length for n<=100 is 11, and I expect to see 12 a few times for odd n<=112; I hope not to see any 12's for even n or any 13's at all). These runs are either simply confirmatory (for n <= 100) or speculative (for n > 100), so I thought I'd share what I have. 7. Results This table contains my current results. The ``max edge bound used'' shows the largest edge bound used in a completed systematic search for the given n, so it can be used to compute the margin for that n. The ``running now'' heading is for cases that will run when program scripts that are already started get to them. end of file announce.txt