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