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(a)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
================
