Wow, Mathematica can do that? Thanks, Bill, very nice! On Wed, Aug 17, 2016 at 7:18 AM, Bill Gosper <billgosper@gmail.com> wrote:
Pending the discovery of some high-powered Mathematica solution, you could always display the full-res B&W polygon next to an el-crudo winding number color legend: gosper.org/pentadecagon.png (Where turns[L_List] := Total[Mod[RotateLeft[#] - # &@Arg@L + π, 2π] - π]/2/π .) --rwg
On 2016-08-16 06:27, James Propp wrote:
I agree with Allan: pictures that show the different winding numbers around different regions should be in the final write-up, and using color might give some very nice pictures. But there's a non-trivial programming problem here. Are there any off-the-shelf graphics packages that play nicely with reentrant polygons?
Tom's pictures remind me of the Klein disk model, and so I am led to wonder: do all these closed paths that encircle signed area zero retain the zero-signed-area property if we replace the line segments by circular arcs perpendicular to the boundary? (I guess there are two flavors of this question, depending on whether you measure Euclidean area or hyperbolic area.)
Jim Propp
On Wednesday, August 10, 2016, Allan Wechsler <acwacw@gmail.com> wrote:
It would be glorious if you could color-code the different winding-numbers, so we could see the +1's and -1's balancing (as well as the occasional 2's and 3's).
On Wed, Aug 10, 2016 at 1:19 PM, Tom Rokicki <rokicki@gmail.com <javascript:;>> wrote:
The images show in my email, not sure why you aren't seeing them.
The following link should work:
https://docs.google.com/document/d/1G3FL1Pcc8RgZ0DZOxibSonMGSJtrY Oc6OUwXjThEj2c/edit?usp=sharing
-tom
On Wed, Aug 10, 2016 at 10:12 AM, Mike Stay <metaweta@gmail.com <javascript:;>> wrote:
Where can we see the images?
On Wed, Aug 10, 2016 at 11:00 AM, Tom Rokicki <rokicki@gmail.com <javascript:;>> wrote:
Yes, oops. Apologies.
On Wed, Aug 10, 2016 at 9:57 AM, Allan Wechsler <acwacw@gmail.com <javascript:;>> wrote:
> Tom, where you say "polynomial" above, do you always mean "polygon"? > > > On Wed, Aug 10, 2016 at 12:24 PM, Tom Rokicki <rokicki@gmail.com <javascript:;>> wrote: > > > Consider a possibly re-entrant polynomial on n equally-spaced points > around > > a circle. James Propp asks, with a signed winding-number definition of > > signed area, for what n can we create a polynomial of zero area? > > > > For even n > 2, an easily solution is to connect the points in the order > > (1, 2, 3, ..., n/2, n, n-1, n-2, ..., n/2+1). > > > > Adam P. Goucher showed that for prime n, no solution is possible. > > > > This note completes the solution for all n by showing that, for all > > composite odd n, a solution exists. We give an explicit construction. > > > > To explain our construction, there are two key insights, and then a bit > of > > engineering. The first insight is a remarkably simple equation to > compute > > the area. The second is identification of a specific sum of triangles > that > > always sum to zero. > > > > Normally when we compute the area of a polygon using the normal > > winding-number definition of area, we add a series of trapezoids from > the x > > axis, as follows: > > > > 1/2 sum_i (x_{i+1}-x_i) (y_{i+1}+y_i) > > > > where the +1 is interpreted modulo n and the i ranges from 0 to n-1. But > > there's nothing special about using trapezoids from the x axis; we can as > > easily just sum triangles from the center of the circle around which the > > points are splayed. The area of a triangle with an angle of theta > between > > two legs of length 1 is simply 1/2 sin(theta), so the area can be > specified > > as just > > > > 1/2 sum_i sin(theta_{i+1}-theta_{i}) > > > > Let us define the original set of points p_0..p_{n-1} as > theta=p_i*tau/n, > > with x=cos(theta), y=sin(theta). The polygon can be defined by a > > permutation of these points (s_0, s_1, ..., s_{n-1}), so for instance for > > n=4 the polygon (0, 1, 3, 2) connects in sequence p_0, p_1, p_3, p_2 > and > > then goes back to p_0. The relevant angles can be computed from the gap > > sequence, which is just the sequence of differences between the point > > indices, going around the polygon, so in this case the gap sequence is > (1, > > 2, -1, -2). The area is just half the sum of the sines of these values. > > Since the sine function is odd, this sum of the sines of this gap > sequence > > is clearly zero. > > > > This brings us to our second insight. The sum of the sines of a set of > > angles equally spaced around the circle is zero. That is, for any n>1 > and > > any a, > > > > sum_i sin(a+i*tau/n)=0. > > > > As an example, sin(5)+sin(5+tau/3)+sin(5+2*tau/3) is zero. If this is > not > > obvious to you, visualize the center of mass of a series of point unit > > masses distributed evenly around a circle of radius 1; the sine function > > gives the y component of the moment imparted by a particular mass. > > > > So if we can arrange that the gaps can be partitioned into subsets so > that > > the angles derived from those gaps in each subset are equally distributed > > around zero, the total area will be zero. > > > > [image: t-9.png] > > > > Let us consider the solution that Propp provided, for n=9. This solution > > (after suitable reflection/rotation) visited the points in the order (0, > 1, > > 5, 3, 4, 8, 6, 7, 2), which generates the gap sequence (1, 4, 7, 1, 4, 7, > > 1, 4, 7). The area is then > > > > 3/2 (sin(tau/9)+sin(4 tau/9)+sin(7 tau/9)) > > > > Since the three points at tau/9, 4 tau/9, and 7 tau/9 are evenly > > distributed around the circle, the sum of the sines is zero and thus so > is > > the total area. > > > > So all we need to do is find a gap sequence that can be partitioned into > > subsets each consisting of angles that are evenly distributed around the > > circle. That gap sequence must be such that every point in the set is > hit > > exactly once and joins back to the first point. > > > > As a warmup we will cover all odd squares greater than 1. Let n be such > a > > square, and call the square root a. The gap sequence (1, 1+a, 1+2a, ..., > > 1+(a-1)a) repeated a times generates a polygon that hits each point once > > and joins back to the first point. We'll prove the second part first. > > > > The sum of the points 1, 1+a, 1+2a, ..., 1+(a-1)a is simply > > a+a(a)(a-1)/2=1/2a(a^2-a+2). > > > > The sum of the full gap sequence is a times this. Since a^2-a+2 is > always > > even, this final sum is always divisible by a^2 and thus always brings us > > back to the first point. > > > > To prove the first part, we divide the points visited into a subsets each > > with a points. The first subset is {p_0, p_a, p_{2a}, ...}. The second > > subset is {p_1, p_{a+1}, p_{2a+1}, ...}. The polygon always visits a > point > > in the first subset, then a point in the second subset, and so on and so > > forth, because each gap is equal to 1 modulo a, and thus s_i = i (mod a). > > So we visit a points in each subset. We need to show those points are > > distinct. > > > > The points we visit in the first subset are always separated around the > > polygon by the sum of the gaps modulo n, and this sum is 1/2a(a^2-a+2). > If > > this visits all the points in the first subset, then it will visit all > the > > points in all subsets, because the visit order in the other subsets are > > just a rotation of the visit order in the first subset. > > > > At time ai we will visit point 1/2ai(a^2-a+2) which is in the first > > subset. If 1/2(a^2-a+2) is relatively prime to a, we will visit all the > > points. This formula is equal to a(a-1)/2+1. Since a is odd, a-1 is > > divisible by 2, and thus 1/2(a^2-a+2)=1 modulo a. > > > > For example, for n=25, the sequence is (1, 6, 11, 16, 21) repeated 5 > times, > > and the resulting figure is > > > > [image: t-25.png] > > > > This is a construction for odd squares that always generates a polynomial > > that is rotationally symmetric of order a. It is straightforward to > extend > > this to any odd composite that has a repeated factor; we omit the details > > here. We can extend this construction to work for all odd composite > > numbers. We do this by adding an even number of additional subsets and > > engineering a workable order of those additional points. > > > > For the odd composite numbers, we will let a be the smallest prime factor > > of n; since a is odd, that factor will also be odd. We define b to be > > n/a. We create b subsets of the n points; the first subset is {p_0, p_b, > > p_{2b}, ...}, and so on. Let u be the sequence (1, b+1, 2b+1, ..., > > (a-1)b+1). Let s*i for a sequence s and an integer i be the sequence s > > repeated i times. Let d=(b-a)/2 (note that it is always an integer). > The > > sequence we use is > > > > (u, (1, 1)*d, u, (b+1, (a-1)b+1)*d, u, (2b+1, (a-2)b+1)*d, ..., u, > > ((a-1)b+1, b+1)*d) > > > > This generates b gaps each of 1, b+1, 2b+1, ..., (a-1)b+1. We add pairs > of > > gaps such that each pair is exactly 2 mod n, so our earlier argument that > > we cover all of the points in the first subset still works. We can split > > the additional subsets of points into pairs. For the first subset of > each > > pair we always visit the points in exactly the same order as we do of the > > first subset overall. In the second subset of each pair, we visit the > > points in a reversed-and-shifted order, starting with the first point, > then > > the last, then the one before the last, and on down to the second point. > > > > For example, the total sequence for n=15, with a=3 and b=5 is > > > > (1, 6, 11, 1, 1, 1, 6, 11, 6, 11, 1, 6, 11, 11, 6) > > > > In this case, u is (1, 6, 11), and the pairs we add are (1, 1), (6, 11), > > and (11, 6). The resulting image is > > > > [image: t-15.png] > > > > The construction we show here is only one possible polynomial; there are > > many more. For instance, the values in u can be permuted arbitrarily, as > > long as the same value of u is used throughout the sequence. > > > > We finish with a solution for n=121. > > > > [image: t-121.png] > > > > > > On Sat, Jul 30, 2016 at 2:21 PM, James Propp < jamespropp@gmail.com <javascript:;>> > wrote: > > > > > Tom, > > > > > > So far it looks like, for prime m, n has a > > > > rotationally symmetrical solution of order m > > > > if n is divisible by m^2. > > > > > > > > > And a rotationally symmetrical solution of order m^r if n is divisible > by > > > m^(r+1) (still assuming that m is prime), right? > > > > > > If we're looking at symmetrical solutions, we should probably include > > even > > > values of n back in the game. For instance, when n=8 is there a > solution > > > with fourfold symmetry? > > > > > > Jim Propp > > > _______________________________________________
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --