i have further results in the minimum area convex lattice polygon search, up to n=512 i said i was done with it after n=128, but i wasn't - i ran the same old programs up to n=256 from january to march last year, but did not trust the results, so i left them dangling these further results use incremental algorithms that are much smaller and way much faster than the ones i used last year and the years before (i wrote and ran these new ones in march and april this year, after dreaming about the problem for some unknown reason, on the fastest two of the old machines and on two newer slightly faster ones) i have minimum area and minimum L1-perimeter results for 3<=n<=512, with adequate margin to believe them (margin 10 for perimeter and 9 for area) margin is the difference between the maximum edge L1-length in a polygon and the a priori search bound b, which is used to constrain the program to consider only edges (d, n) with d > 0, n >= 0, gcd(d, n) = 1, and d+n < b (with the convention that gcd(0,x) = x for any integer x), and their three other rotations by multiples of pi/2 (-n, d) (-d, -n) (n, -d) i had to impose some such bound, since all SL(2,Z)-images of a convex lattice polygon are convex lattice polygons with the same area (but not the same edge lengths and perimeter), so the search would otherwise be infinite my minimum area program looks for polygons with minimum area, then minimum maximum edge L1-length among those with the same area, then minimum L1-perimeter among those of the same area and maximum edge length (this ordering is different from my earlier search criterion, but it is more consistent with the search bound, and it almost always finds the same polygon anyway) there is exactly one exception for n<=512, at n=275 my minimum perimeter program looks for polygons with minimum perimeter, then minimum maximum edge L1-length among those with the same perimeter, then minimum L1-area among those of the same perimeter and maximum edge length (this ordering is also different from my earlier search criterion, but it is more consistent with the search bound, and it frequently finds the same polygon, but not always) there are many differences for n<=512 (over a hundred), but all are small i am still making the as yet unproven assumption that for odd n, there is a minimum area polygon and a minimum perimeter polygon for which the two polyhalves are both minimal (corners are defined by the quadrant containing the edges, and polyhalves are two successive corners) and have almost the same number of vertices (by analogy with the case of even n, in which it was proven that there is a minimum area polygon with two identical minimal polyhalves, one rotated by pi radians and translated to fit) the reason i believe this assertion is that for n<=49 odd, several earlier versions of these programs found many such examples, in every case, without making that assumption i thought that if my program can search for area, then it can also search for perimeter - it is a simple coding change - but perimeter, as it turns out, is much simpler i have devised a construction that seems to generate almost minimum perimeter polygons for all n, giving a pretty close upper bound on area (within 3.6% for n<=256, except for 4.3% for n=24) and perimeter (off by exactly 1 or 2 for all odd n<=256, and exact when n is even) this construction provides a close upper bound for area, and transforms the search for minimum area (well, really only for a good bound) to a computation with number-theoretic sums (mainly combinations of the euler phi function) all of these computations are simpler with L1-lengths, since the L1-perimeter of a convex polygon is the same as the perimeter of the circumscribed axis-parallel rectangle (though i chose it because the values are always integers in this program search, and because it directly relates to the edge bound) on a related note, the asymptotic shape of the minimum area polygon cannot be easily defined, since there are always infinitely many of them (all SL(2,Z)-images), and the one from the papers (by Baranyi and others) is not the one my program finds, which is the one with minimum maximum edge length - that one seems to tend towards a near circle (i expect that the one from the papers is an easily found SL(2,Z)-image of the one my program finds) curiosities: (0) the maximum edge length for the minimum area polygon suddenly decreases after a run of generally increasing values the minimum maximum edge length is not monotonic - it has two major recessions 17 to 13 at n=171 to 178 27 to 21 at n=417 to 418 (i have made pictures of this) (1) the minimum area polygon with the two different orderings differs for exactly one case for n<=512, namely at n=275 there is a minimum area 376330.5 polygon for n=275 with a smaller perimeter 2936 but longest edge 20 than the perimeter 2938 for a polygon with longest edge 19 (2) the minimum perimeter polygon with the two different orderings differs for many values of n the new ordering never has a maximum edge length more than one different from the old ordering, though it frequently delays the onset of larger maximum edge lengths when compared to the old ordering as n increases (3) intermediate files for b=031 get up to 12GB, for b=036 get up to 42GB, and for b=041 are expected to get up to 89GB (they are already at 65GB for p=186) it should be noted that these intermediate files are produced in such a way that there are always two of them - the old one that is being read, and the new one that is being produced, so the size required is twice the individual file size (the program scripts actually remove the old file after it has been read completely) it should also be noted that the b=041 runs are not expected to change the results in any way, only the margin of the area search (these runs are taking over five hours each at p=186) (4) intermediate files for b=028 that keep all the edge information (so the programs can determine the minimal polygons, not just their parameters) are expected to get up to 130GB (these runs are taking over six hours each at p=089, so we expect them to take a very long time) these last few expectations will take a few weeks to corroborate or refute, since the polygon parameter search that has already finished does not provide the edges of the best polygon, only its parameters (this simplification is a major part of the speedup) if anyone would like the files that show the results, i can send them or maybe send them out to the list (they are each about 550 lines of ascii text) more soon, cal Chris Landauer Aerospace Integration Science Center The Aerospace Corporation cal@aero.org