Unless there's something very wrong with my code, here's what I have so far. I'm assuming you want the "area" as defined by the winding rule, which means that some geometric areas may be counted multiple times. For instance, in a five-pointed star, the central pentagon, with winding number 2, counts double. Is this what you meant? Odd n=9 has the first solutions. Odd n=15 has many; here are some: 0 1 2 3 4 6 5 11 7 14 13 10 12 9 8 0 1 2 3 4 6 5 12 8 7 14 11 13 10 9 0 1 2 3 4 6 5 12 11 8 10 7 14 13 9 0 1 2 3 4 6 5 12 14 11 7 13 10 9 8 0 1 2 3 4 6 5 12 14 11 10 7 13 9 8 Odd n=21 has many; here are some: 0 1 2 3 4 5 6 7 8 16 10 15 14 13 12 20 19 18 17 11 9 0 1 2 3 4 5 6 7 8 16 14 13 12 20 19 18 17 11 10 15 9 0 1 2 3 4 5 6 7 8 16 15 13 12 20 14 19 18 17 11 10 9 0 1 2 3 4 5 6 7 8 16 15 14 12 20 19 13 18 17 11 10 9 0 1 2 3 4 5 6 7 8 16 15 14 13 18 12 20 19 17 11 10 9 So far I have not found any for any other odd values through n=31 (but I'll let them run overnight). Searching for symmetric solutions may well prove to find them more quickly than what I'm currently doing (just searching lexicographically). -tom On Fri, Jul 29, 2016 at 11:58 PM, Joerg Arndt <arndt@jjj.de> wrote:

The following might be helpful to determine which permutations of the roots of unity give a polygon with zero area.

Let A be the area, then 2 * A = = sum(i=0, n-1, x[i]*y[i+1] - x[i+1]*y[i] ) = sum(i=0, n-1, (x[i] + x[i+1]) * (y[i+1] - y[i]) ) = sum(i=1, n, x[i] * (y[i+1] - y[i-1]) ) where indices are taken modulo n This is from http://geomalgorithms.com/a01-_area.html which gives further references. I found this URL at

http://stackoverflow.com/questions/451426/how-do-i-calculate-the-area-of-a-2...

Best regards, jj

* James Propp <jamespropp@gmail.com> [Jul 30. 2016 08:11]:

...

For which n>2 does there exist a reentrant n-gon whose vertices are evenly spaced on a circle and whose signed area (aka algebraic area) is zero?

When n is even, there is an easy solution: draw a circuit from 1 to 2 to 3 to ... to n/2-1 to n/2 to n to n-1 to n-2 to ... to n/2+1 to 1 (here I'm numbering the n vertices cyclically).

For n=3, it's trivially impossible to find such an n-gon, and I've checked by brute force (using Mathematica) that there's no such n-gon when n=5 or n=7.

For n=9, there is such an n-gon (which I found through brute-force search): http://mathenchant.org/nonagon.pdf Mathematica assures me that 1/2 (-1/2 Sqrt[3] sin(\[Pi]/18)+1/2 sin(\[Pi]/9)-sin((2 \[Pi])/9)-2 sin(\[Pi]/18) sin((2 \[Pi])/9)-1/2 cos(\[Pi]/18)-1/2 Sqrt[3] cos(\[Pi]/9)+2 cos(\[Pi]/18) cos((2 \[Pi])/9)+2 sin(\[Pi]/9) cos(\[Pi]/9)) simplifies to 0, which implies the claim. Is there a nice (preferably trig-free) way to prove it? That is: is there a nice way to show that the total area of the three scalene black triangles equals the total area of the four nonscalene black triangles, maybe using dissection and area-preserving linear transformations, or maybe using algebraic tricks involving roots of unity?

I suspect that when n is prime, there's no such polygon. Can any of you find a proof?

Also, can any of you construct such a polygon with n=15? It'd be nice if the answer to my original question were "Precisely when n is composite".

Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ 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] --

31 factorial is really large; it could be a very long night... :-)

My CPU runs at 2.4 GHz. time-consuming) FullSimplify. How do you try to avoid getting false

positives and false negatives?

My philosophy is don't worry, be happy. Every additional vertex introduces an error of at most 2^-51 or something like that, so I check the final area against 0 with an epsilon of about 1e-8, and then print the computed final area with the solution. If it's on the order of 1e-15, I'm not certain it's zero, but close enough to report. I'll let Bill and his posse do the hard bits of proving the result. (Or I'll throw multiprecision arithmetic at it. Anyone want to write a Mathematica procedure that takes a permutation, applies it to the roots of unity and computes the area, using high-precision math?) If multiprecision math says the area is < 1e-10000, I'm inclined to view it as zero, at least provisionally. -tom -- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --

Here are the rotational symmetry searches I've done. The 'no's are for exhaustive complete searches. Searches that have not yet found solutions, but are still running, are not listed. So far it looks like, for prime m, n has a rotationally symmetrical solution of order m if n is divisible by m^2. n sym solution found? 9 3 yes 15 1 yes 15 3 no 15 5 no 21 1 yes 21 3 no 21 7 no 25 5 yes 27 3 yes 27 9 yes 33 11 no 35 5 no 35 7 no 39 13 no 45 9 no 45 15 yes 49 7 yes 51 17 no 57 19 no 63 21 yes 69 23 no 75 15 yes 75 25 no 81 27 yes (Sorry for spamming the list; I'll stop now.) -tom On Sat, Jul 30, 2016 at 10:28 AM, Tom Rokicki <rokicki@gmail.com> wrote:

Oddly, there appear to be a lot of n=15 solutions, but none of them have rotational symmetry (like the n=9 case did).

-tom

On Sat, Jul 30, 2016 at 9:42 AM, Tom Rokicki <rokicki@gmail.com> wrote:

...

31 factorial is really large; it could be a very long night... :-)

...

My CPU runs at 2.4 GHz.

time-consuming) FullSimplify. How do you try to avoid getting false

...

positives and false negatives?

My philosophy is don't worry, be happy. Every additional vertex introduces an error of at most 2^-51 or something like that, so I check the final area against 0 with an epsilon of about 1e-8, and then print the computed final area with the solution. If it's on the order of 1e-15, I'm not certain it's zero, but close enough to report. I'll let Bill and his posse do the hard bits of proving the result. (Or I'll throw multiprecision arithmetic at it. Anyone want to write a Mathematica procedure that takes a permutation, applies it to the roots of unity and computes the area, using high-precision math?) If multiprecision math says the area is < 1e-10000, I'm inclined to view it as zero, at least provisionally.

-tom

-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --

-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --

-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --

I wrote: 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?

The answer is YES: e.g., 1,4,3,6,5,8,7,2,1. Jim Propp

It's a nice approach, but I'm missing a step near the end. Why is it true that When n is prime, the *only* integer linear relationships between

the imaginary parts of roots of unity are generated by relationships of the form:

Im[w^k] + Im[w^-k] = 0

? Note that Adam is talking about the *nontrivial* roots of unity. After all, the relation Im[w^0] = 0 has an odd number of terms. But this doesn't mar Adam's argument because w^(a_0 - a_1), ... are all unequal to 1 (which is I suppose what Adam was getting at by saying "Note that none of these terms are zero"). Jim Propp

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> 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> 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] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Where can we see the images? On Wed, Aug 10, 2016 at 11:00 AM, Tom Rokicki <rokicki@gmail.com> wrote:

Yes, oops. Apologies.

On Wed, Aug 10, 2016 at 9:57 AM, Allan Wechsler <acwacw@gmail.com> 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> 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> 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] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ 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] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

Implicit attachments, I suspect --- so cropped by the server? WFL On 8/10/16, Tom Rokicki <rokicki@gmail.com> 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/1G3FL1Pcc8RgZ0DZOxibSonMGSJtrYOc6OUwXjThE...

-tom

On Wed, Aug 10, 2016 at 10:12 AM, Mike Stay <metaweta@gmail.com> wrote:

...

Where can we see the images?

On Wed, Aug 10, 2016 at 11:00 AM, Tom Rokicki <rokicki@gmail.com> wrote:

...

Yes, oops. Apologies.

On Wed, Aug 10, 2016 at 9:57 AM, Allan Wechsler <acwacw@gmail.com> 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> 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> 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] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ 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] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

_______________________________________________ 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] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

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 <javascript:;> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Mike Stay - metaweta@gmail.com <javascript:;> http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun