hihi, all - Some time ago, William Thurston made some suggestions to me about my computer searches for minimum area convex lattice polygons, and I have just caught up to them. I have some questions about them also. I haven't put the new programs and the detailed results out to the web yet, but that should happen this month. IN the meantime, I have appended the best results so far. Thurston's suggestions (reformatted) are indented. The programs do not try to normalize for SL(2,Z) directly. Instead, they take the observation that those actions stretch out the polygon into increasingly narrow shapes with large perimeter and long edges, and use the edge bounds (used as a strict upper bound on the maximum l1-length of an edge) to limit these images in a completely heuristic way. The programs look for smallest area polygons within those limits. A filled convex polygon is associated with a unique filled ellipse with the same center of mass and second moments. I assume that ``second moments'' are second central moments. It turns out that among the smallest area polygons my programs found, the constructed ellipses all have the same area when the original polygons are SL(2,Z)-related (this fact surprised me). This agreed with the separate SL(2,Z)-reduction program I wrote to find out how many different classes the programs found (either 1 or 2 for all n<= 50; the first cases with 2 are n=07, 11, 15, 20). I have a polynomial invariant question here about SL(2,Z). If I have a 2x2 matrix A = (a b), (c d) what polynomial functions of a, b, c, d are invariant under all of SL(2,Z) (i.e., when A is right-multiplied by elements of the group)? It is clear that det A is, and it seems easy to prove that there can't be any odd degree terms. What I wonder is whether or not all of the invariant polynomials can be expressed as polynomials in det A (it seems reasonable to me, and I vaguely recollect reading something like that a long time ago). Some of the resulting ellipses are circles (for n=04, 08, 16, 32, 40) and a few have vertical major axes (for n=20, 36). Up to translation and scaling, there is a 2-dimensional family of ellipses (depending on the slope of the major axis and the eccentricity). Since slope is to be preserved, I assume the same scale factor on each axis. The angles for the major axis range from -88.9 to +90.0 degrees, and the nonzero eccentricities range from 0.426102 to 0.999962 (and there are a few zeroes, the simplest of which correspond to the square for n=04 and the ``stop sign'' for n=08). This family is otherwise known as the hyperbolic plane. Since the slope is in Real union {inf} and the eccentricity is in [0,1), I'm not so sure how this mapping works. Also, since we can't generally recover the polygon from the ellipse, I assume that we need some work to show that the action below is well-defined. The action of SL(2,Z) on the hyperbolic plane has a non-compact quotient, and I don't see why one should expect the answers to stay in a compact portion. Is the action of SL(2,Z) on the hyperbolic plane, as defined by its action in the original polygon space, the same as the usual one? I'd guess so, because otherwise moving to the hyperbolic plane wouldn't tell us much. This action is still pretty unfamiliar to me. It would be interesting to see a scatter-plot of the optimal answers. One way to do this would be to fit the ellipse (this is straightforward), normalize by scaling so that the product of major and minor axis lengths is 1, then transform by SL(2,Z) to make the major axis minimal. For now the program just computes the minimum among the polygons it reads (which are the output of one of the search programs). It also normalizes the axis product to be 4 instead of 1 (since I forgot that my symbols a and b in the program were the semi-major and semi-minor axis lengths). In all cases my programs have found so far, the ellipses with the minimum scaled major axis length correspond to polygons with the minimum perimeter among those found with the minimum area (this fact also surprised me), though there are can be polygons with the same minimum perimeter that do not have ellipses with the minimum scaled major axis length. Plot the topmost end point of the major axis, which is a point in the upper half plane. The results are appended below. There are discussions of this action lots of places, and it's easy to do the normalization under SL(2,Z). Limiting the answers to a compact portion of this quotient space is tantamount to bounding the search. This comment is what intrigues me, of course, since it might help turn the systematic searches into parts of a proof. more later, cal Chris Landauer Aerospace Integration Science Center The Aerospace Corporation cal@aero.org ================ PS - search results so far These results are from a systematic search in all cases not marked random. The edge bound is 10 (r=10) in all cases not marked otherwise. The edge lengths and perimeters are always l1-lengths (manhattan distance) The minimum perimeter found and the minimum longest edge length found are not necessarily from the same minimum are polygon. min min min longest number of area perim edge min area polygons found found found within edge bound 3 0.5 4 2 -- 4 1.0 4 1 17 5 2.5 8 2 -- 6 3.0 8 2 16 7 6.5 12 3 116 8 7.0 12 2 23 9 10.5 16 3 20 10 14.0 18 3 38 11 21.5 22 3 164 12 24.0 24 3 12 13 32.5 28 4 50 14 40.0 30 3 60 15 51.5 34 4 114 16 59.0 36 3 15 17 75.5 42 5 72 18 87.0 44 4 50 19 106.5 50 5 72 20 121 52 4 44 21 144.5 60 5 24 22 164 62 5 72 23 193.5 66 5 8 (r=07) 24 210 72 5 6 25 248.5 76 5 8 (r=07) 26 274 80 5 28 27 315.5 86 5 8 (r=07) 28 345 90 5 14 29 394.5 94 5 8 (r=06) 30 430 98 5 20 31 485.5 104 5 -- random (r=06) 32 523 108 5 5 33 594.5 114 5 -- random (r=06) 34 632 118 5 20 35 715.5 126 6 -- random (r=07) 36 749 128 5 10 37 845.5 134 6 -- random (r=07) 38 890 138 5 8 (r=09) 39 994.5 144 6 -- random (r=07) 40 1039 148 5 1 (r=09) 41 1170.5 156 6 -- random (r=07) 42 1222 162 7 4 (r=09) 43 1439.5 186 7 -- random (r=08) 44 1412 176 7 2 (r=09) 45 1596.5 190 7 -- random (r=08) 46 1620 192 7 8 (r=09) 47 1851.5 204 7 -- random (r=08) 48 1838 208 8 4 (r=09) 49 2104.5 216 7 -- random (r=08) 50 2088 218 8 4 (r=09) When the edge bound is only one more than the minimum longest edge found among the smallest area polygons found, as for n=48, 50, and all odd n>=29, I am much less confident of the minimum areas; it seems quite possible that a larger edge bound could find a smaller minimum area (and that has happened in the past during this search as I made the programs faster). Of course, that may be true for any other n as well, but I don't think so (modulo the correctness of the programs). ================ PPS - scaled ellipse results Remember, these ellipses are not in the original polygon space. They are centered at the origin, and have the same area (since they are all normalized to have major * minor axis = 4). The smallest major axes among all scaled ellipses corresponding to the minimum area polygons found by the program all occur for minimum perimeter polygons (among the minimum area polygons found). major major axis polygon perim^2/ n axis top point perim polygon area 03 1.316074 (0.930605,0.930605) 4 32.000000 04 1.000000 (0.000000,1.000000) 4 16.000000 05 1.170029 (-0.827336,0.827336) 8 25.600000 06 1.316074 (-0.930605,0.930605) 8 21.333333 07 1.057951 (-0.405820,0.977021) 12 22.153846 08 1.000000 (0.000000,1.000000) 12 20.571429 09 1.316074 (-0.930605,0.930605) 16 24.380952 10 1.276103 (-1.132887,0.587374) 18 23.142857 11 1.113000 (1.079827,0.269710) 22 22.511628 12 1.316074 (-0.930605,0.930605) 24 24.000000 13 1.286294 (-1.176975,0.518924) 28 24.123077 14 1.130489 (-0.537790,0.994378) 30 22.500000 15 1.096602 (-1.031715,0.371618) 34 22.446602 16 1.000000 (0.000000,1.000000) 36 21.966102 17 1.178813 (-0.714809,0.937363) 42 23.364238 18 1.145206 (-1.079858,0.381319) 44 22.252874 19 1.232943 (-0.987570,0.738143) 50 23.474178 20 1.183680 (0.000000,1.183680) 52 22.347107 21 1.316074 (-0.930605,0.930605) 60 24.913495 22 1.234094 (1.188690,0.331669) 62 23.439024 23 1.180256 (-0.023118,1.180030) 66 22.511628 24 1.316074 (0.930605,0.930605) 72 24.685714 25 1.217086 (-0.285925,1.183024) 76 23.243461 26 1.223329 (0.757037,0.960952) 80 23.357664 27 1.209842 (-0.513052,1.095671) 86 23.442155 28 1.272557 (1.100463,0.639048) 90 23.478261 29 1.128287 (0.516335,1.003209) 94 22.397972 30 1.186850 (0.994061,0.648425) 98 22.334884 32 1.000000 (0.000000,1.000000) 108 22.302103 34 1.063232 (1.026016,0.278842) 118 22.031646 36 1.100984 (1.100984,0.000000) 128 21.874499 38 1.051365 (0.258304,1.019141) 138 21.397753 40 1.000000 (0.000000,1.000000) 148 21.081809 42 1.057275 (0.847674,0.631885) 162 21.476268 44 1.104776 (0.781194,0.781194) 176 21.937677 46 1.220786 (1.081700,0.565901) 192 22.755556 48 1.274360 (1.120531,0.606964) 208 23.538629 50 1.222431 (1.056386,0.615131) 218 22.760536 ================