subtitle: end of an obsession
Minimum Area Convex Lattice Polygons For 3 <= n <= 128
I am pleased to announce the end (finally!) of my patience (and computing
resources) with this problem. I have run programs for the last three years to
compute minimum area convex lattice polygons, and I have results for n<=128,
with much confidence (but not proofs) for all of them. The following
discussion explains my confidence assessment.
The confidence levels are necessary because the problem is not amenable to a
simple finite search.
Every SL(2,Z) image of a convex lattice polygon is a convex lattice polygon
with the same area, so the search must be artificially limited. Since the
SL(2,Z) images have arbitrarily long polygon edges, I chose to use the maximum
length of the edges in a polygon as a search limit (it obviously makes the
search finite). I used the L1 length to make the computation simple and the
lengths integers; Linfinity would produce the same results with slightly
different structure. Length always means L1 length here.
The search program found all minimum area convex lattice polygons (just
polygons henceforth) with a fixed number n of edges and a strict bound b on
the edge length. If the areas of two polygons were equal, it used the one
with the smaller perimeter (sum of edge lengths), and of the perimeters were
equal, it used the one with the smaller maximum edge length, and if those were
equal, it used the one found earlier. This ordering defined the ``best''
polygon with a given number of edges.
The ``margin'' is the difference between the search bound and the maximum edge
length of the best polygon. The confidence measure for the results is the
margin: margin at least 3 is good, margin 2 or less is worrisome, and margin 1
is the smallest possible (because the edge bound b is a strict bound), so it
is completely uninformative.
Margin 2 is worrisome because in several instances, margin 2 results for a
given b were superseded by margin 1 results for b+1 (so edge bound b gave the
same minimum area as b-1, but the b+1 search found a smaller minimum area).
For example, for n=27, b=7, the same minimum area 315.5 is found as for b=6,
so the margin is 2, but for b=8, a new smaller area 312.5 is found with
maximum edge length 7. The same thing happens for n=29, 31, 33 and other,
larger n (mostly odd n). In every one of these cases, the perimeter of the
newly found polygon is larger than the old one (though not a lot larger),
leading me to think about running the same search but for minimum perimeter
polygons (the algorithms would need only a trivial change to the ``best''
ordering).
On the other hand, that peculiarity never happened with margin 3 results.
They were not superseded when b was further increased in any of the examples
that were run with any of the programs I wrote. The ``much confidence''
written above means that the relevant margins are all at least 5.
Theory
There is a theorem that when n is even, there are minimum area polygons that
are centrally symmetric. I observed in many earlier runs that the same is
almost true when n is odd, so my programs have assumed that, though I have not
proven it.
Therefore, strictly speaking, all of these search results are only upper
bounds (since they produce example polygons), but I have much confidence that
all of them are exact, as described earlier.
Similarly, if there were also a theorem that said something like ``among the
minimum area polygons, there is at least one with a maximum edge length less
than B(n)'' for some explicit function B(n) that is not too large, then the
same program could be run more definitively.
Algorithms
The algorithms have evolved from a more or less direct simulation of which
edge to choose, to a backtracking algorithm that took about two years to run
all the cases for b=13 (and many of the smaller cases for b=14), to an
incremental dynamic programming approach that ran all earlier cases with
search bound b=14 in seven months, to a slight modification of the approach
that has run all of the earlier cases and much more (with an even larger
search bound b=16) in the last two months on just one machine. This last
version is many orders of magnitude faster than the first version I wrote.
Computing
I used 10 of my commodity PCs, most ranging from 3.0GHz to 3.6GHz, and having
4GB of memory and 1TB of disk space (four of them are older 2GHz desktops and
two are slow laptops that were used for some of the program development and
other experiments). Between 1 and 8 (more than that flipped the circuit
breaker in my home) of them have been running continuously (except for power
failures) since early December of 2003, when the first math-fun e-mail
announced the problem, and that the case n=11 was not yet completely decided
(I thought to myself, ``I can do that'').
One of the computers is a dual 3.0GHz G4 Mac running OS X, the older, slower
ones run SuSe Linux, and all of the non-Macs run FreeBSD (my favorite version
of UNIX). The programs were all written in what I call C-- (my own personal
portable subset of C), with identical source code on each system on each
machine. The slow machines were perfectly adequate for the smaller searches,
but could not manage the data flow, volume or disk activity in the larger
ones, and bogged down more than the problem should have required.
I needed to make a change to the operating system kernel before it would
correctly report cpu times in excess of about 137 hours (it is a simple 64-bit
counter overflow that has apparently been in UNIX since BSD days at Berkeley
on the VAXen), but my changes have been working smoothly and accurately for
more than three years now. The last versions of the program do not need that
change, since they run much faster.
Discussion
The scripts that run the search programs face a difficult space-time tradeoff.
The file sizes generated in each of the largest cases I ran are up to 80GB,
though the programs only took 20 hours or so to run each case (each different
value of the number n of sides). Earlier versions generated much smaller
files, but took hundreds or even thousands of cpu hours (and were therefore
too often interrupted by power failures and needed to be restarted from the
most recent checkpoint; I only reluctantly put the checkpointing and recovery
code into the programs because it makes them much more complicated, but I lost
two almost 1800cpu hour runs before that).
Extending the search to b=20 is a barrier for now, since the best estimate
that I have for the largest of the generated file sizes is well over 10TB (and
the margins I already have mean I really only need to run the program with
b=20 for the largest n, say 112<=n<=128 to get adequate margins in that
range).
I also have timing and progress statistics for almost of the runs of all of
the programs on all of the machines, which I have used to make pretty accurate
predictions of cpu and elapsed times for the larger cases (so I didn't get too
impatient with them), and some preliminary notions of how to improve the
simple timing models I used.
**Breaking News**
I just found (18 December) a simplification that makes the program files much
smaller (the ratio decreases rapidly as n grows, and the asymptotic ratio
appears to be less than 1/60), and therefore the programs can run very much
faster and the code can be made much simpler (no checkpointing or complicated
sets of intermediate files). I've rewritten all the programs and scripts
accordingly, and in the first 6 hours it ran all of the b=20 cases I had run
before (up to n=44), and much more.
This program script finished in about 4 days, and produced margins at least 5
for all n up to 128, and was weakly verified by a check run (same program,
different area thresholds).
Just to get an alternative view, I did run the minimum perimeter search, and
have those results also. The margins are at least 9 for all n<=128, and the
corresponding areas are within a few percent of the computed minimum areas in
all cases. This leads to the notion that pretty good upper bounds for the
minimum area for much larger n can be obtained relatively cheaply using the
minimum perimeter search, since for all n <= 128, we only need to use edge
bound 12 to find them, and slightly larger edge bounds to get reasonable
margins.
It is also curious that for all n up to 20, and several more up to and
including n=43, the minimum area polygon is also a minimum perimeter one,
since it does not happen for any larger n (and I did not expect it to happen
as much as it did).
b=20 results
all lengths are L1-lengths
||(x, y)|| = |x| + |y|
min perim polygon has minimum perimeter,
and minimum area among those with the minimum perimeter,
and minimum maximum edge length among those with the minimum perimeter and area
min area polygon has minimum area,
and minimum perimeter among those with the minimum area,
and minimum maximum edge length among those with the minimum area and perimeter
min perim polygon min area polygon (if different)
min max min max
n area perim edge area perim edge
03 0.5 4 02
04 1 4 01
05 2.5 8 02
06 3 8 02
07 6.5 12 03
08 7 12 02
09 10.5 16 03
10 14 18 03
11 21.5 22 03
12 24 24 03
13 32.5 28 04
14 40 30 03
15 51.5 34 04
16 59 36 03
17 75.5 42 05
18 87 44 04
19 106.5 50 05
20 121 52 04
21 149.5 58 05 144.5 60 05
22 167 60 04 164 62 05
23 193.5 66 05
24 219 68 04 210 72 05
25 252.5 74 05 248.5 76 05
26 280 78 05 274 80 05
27 318.5 84 05 312.5 88 07
28 346 88 05 345 90 05
29 394.5 94 05 391.5 96 07
30 430 98 05
31 485.5 104 05 483.5 106 07
32 523 108 05
33 589.5 114 05 588.5 120 07
34 632 118 05
35 704.5 124 06
36 749 128 05
37 844.5 134 06 835.5 136 07
38 890 138 05
39 994.5 144 06 977.5 146 07
40 1039 148 05
41 1139.5 156 07
42 1225 160 06 1222 162 07
43 1325.5 168 07
44 1421 172 06 1412 176 07
45 1540.5 180 07 1525.5 182 07
46 1657 184 06 1620 192 07
47 1764.5 192 07 1746.5 196 07
48 1903 196 06 1838 208 08
49 2027.5 204 07 1984.5 212 08
50 2156 210 07 2088 218 08
51 2287.5 218 07 2244.5 228 09
52 2416 224 07 2357 234 08
53 2561.5 232 07 2522.5 246 09
54 2702 238 07 2651 244 08
55 2868.5 246 07 2811.5 258 09
56 3009 252 07 2953 260 08
57 3198.5 260 07 3121.5 276 09
58 3360 266 07 3278 278 09
59 3545.5 274 08 3495.5 282 09
60 3717 280 07 3612 296 09
61 3925.5 288 08 3865.5 302 09
62 4102 294 07 4020 308 09
63 4326.5 302 08 4239.5 320 11
64 4507 308 07 4439 322 09
65 4756.5 316 08 4682.5 332 11
66 4970 322 07 4902 334 09
67 5231.5 330 08 5156.5 346 11
68 5445 336 07 5387 348 09
69 5730.5 344 08 5661.5 368 11
70 5980 350 07 5898 362 09
71 6277.5 358 08 6179.5 368 09
72 6527 364 07 6418 376 09
73 6772.5 374 08 6729.5 382 09
74 7065 380 08 6974 390 09
75 7327.5 390 08 7307.5 394 09
76 7619 396 08 7557 404 09
77 7942.5 406 09 7905.5 408 09
78 8221 412 08 8182 420 09
79 8578.5 422 09 8536.5 426 09
80 8839 428 08 8835 434 09
81 9255.5 438 09 9215.5 442 09
82 9589 444 08 9512 450 09
83 9985.5 454 09 9916.5 458 09
84 10353 460 08 10218 464 09
85 10725.5 470 09 10660.5 474 09
86 11201 476 08 10984 482 09
87 11562.5 486 09 11450.5 492 10
88 12063 492 08 11759 500 09
89 12577.5 502 09 12263.5 510 10
90 12874 510 09 12635 516 09
91 13294.5 520 09 13141.5 528 11
92 13694 528 09 13525 532 09
93 14155.5 538 09 14052.5 546 11
94 14586 546 09 14448 550 09
95 15115.5 556 09 14996.5 562 10
96 15487 564 09 15399 568 09
97 16052.5 574 09 15979.5 578 11
98 16508 582 09 16415 588 10
99 17089.5 592 10 17009.5 602 11
100 17557 600 09 17473 608 10
101 18173.5 610 10 18072.5 624 11
102 18676 618 09 18570 626 10
103 19320.5 628 10 19171.5 638 11
104 19823 636 09 19683 644 10
105 20528.5 646 10 20346.5 660 11
106 21096 654 09 20896 666 11
107 21812.5 664 10 21563.5 682 11
108 22385 672 09 22134 688 11
109 23181.5 682 10 22828.5 706 12
110 23786 690 09 23404 710 11
111 24636.5 700 10 24120.5 722 11
112 25203 708 09 24743 730 11
113 25869.5 720 11 25456.5 776 13
114 26575 728 10 26103 752 11
115 27241.5 740 11 26826.5 798 13
116 27987 748 10 27500 808 13
117 28680.5 760 11 28245.5 824 13
118 29459 768 10 28958 830 13
119 30192.5 780 11 29790.5 840 13
120 30971 788 10 30432 856 13
121 31882.5 800 11 31322.5 858 13
122 32745 808 10 32038 872 13
123 33489.5 820 11 32869.5 888 15
124 34537 828 10 33659 890 13
125 35330.5 840 11 34538.5 904 15
126 36473 848 10 35367 908 13
127 37217.5 860 11 36264.5 922 15
128 38427 868 10 37095 904 11
end of file results-b20perim.txt
