Newsgroups: sci.math From: ag552@lafn.org (steve gray) Subject: Curious Polygon Construction Date: Sun, 15 Jan 1995 22:45:34 GMT Take a plane N-gon, G1, where N is prime. Let the vertices of G1 be G11, ... G1N. Draw a second N-gon whose vertices are: G2j = (G1j + G1(j+1))/2 (that is, vertices of G2 are the midpoints of the sides of G1.) Draw a third N gon, G3, whose vertices are given by G3j=(G2j + G2(j+2))/2. (This time instead of taking midpoints of sides connecting successive vertices, we take midpoints of lines connecting vertices separated by 1). Continue, each time skipping one more vertex, until the last N gon, GN, is given by GNj = (G(N-1)j + G(N-1)(j+N-1))/2. Show that GN is similar to, oriented like, and 2^(1-N) the linear size of G1. For N=3 this amounts to the original triangle G1, a first construction on its midpoints giving G2, and a second construction on the midpoints giving G3, which is 1/4 the size of G1. For N=17 the size ratio is 1/65536, so if the final N-gon is barely visible having sides .01", the starting N-gon is much larger than the biggest piece of paper in the world. Also the mere possibility of a proof using matrices (as a means of manipulating vectors) shows that the N-gons do not have to be planar, and in fact can be in any number of dimensions. This theorem, which I found in 1961, is an interesting combination of plane geometry and number properties, two fields not easily connected even in this not very deep sense. It can also be viewed as a theorem about products of certain matrices, but this is maybe less interesting. -- Steve Gray Graphics and Geometry Consultant Santa Monica CA PS - the original and final polygons have the same centroid, also. Is anyone interested in things like this? I originally posted in Geometry:Puzzles, but there were few respondents. Thanks, SG. -- Steve Gray Graphics and Geometry Consultant Santa Monica CA ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Curious Polygon Construction Date: 23 Jan 1995 17:59:03 GMT Gee, I hate to see an article not followed up. This is actually a nice construction. It's unusual to have a problem for which it's important that the number of sides be a prime, although it looks to me like mod-2 pseudoprimes (e.g. N=341) work too! In article <1995Jan15.224534.889@lafn.org>, steve gray wrote: > Take a plane N-gon, G1, where N is prime. Let the vertices >of G1 be G11, ... G1N. Draw a second N-gon whose vertices are: >G2j = (G1j + G1(j+1))/2 (that is, vertices of G2 are the midpoints >of the sides of G1.) Draw a third N gon, G3, whose vertices are >given by G3j=(G2j + G2(j+2))/2. (This time instead of taking >midpoints of sides connecting successive vertices, we take midpoints >of lines connecting vertices separated by 1). Continue, each time >skipping one more vertex, until the last N gon, GN, is given by >GNj = (G(N-1)j + G(N-1)(j+N-1))/2. > Show that GN is similar to, oriented like, and >2^(1-N) the linear size of G1. Let the kth polygon be G(k), with vertices G(k)_j where j ranges over the integers mod N. The construction is G(k+1)_j = (1/2)( G(k)_j + G(k)_{j+k} ). By induction on k it is clear that the vertices of this polygon are in the convex hull of the original vertices, and so may be expressed as G(k+1)_j = (1/2^k) ( Sum_r G(1)_{j+r} a(k+1)_r ) for some (small positive) integers a(k+1)_r. Note that the centroids of the polygons are all at the same point, so the statement that the polygons G(k) and G(1) are similar and have the same orientation is just the statement that G(k) is scaled from G(1) to the centroid (1/N)Sum G(1)_j. For this to be true for all choices of points G(1)_j it is necessary an sufficient that all coefficients a(k)_r be equal except a(k)_0, which must be different to avoid having the polygon collapse to a point. These coefficients may be calculated by a recurrence relation: we start with a(0)_r = 0 except a(0)_0=1, and thereafter a(k+1)_r = a(k)_r + a(k)_{r-k}. It's easiest to analyze these by lumping them together in a generating function: Let F_k(X) = Sum a(k)_r X^r. We have to do this with some care since the subscript r ranges over the integers mod N; that is, F_k is not an element of Z[X] but rather of the quotient ring Z[X]/(X^N-1). Anyway, the recurrence relation now simply states that F_{k+1} (X) = F_{k} (X) * ( 1 + X^k ) with F_0(X) = 1, so that each F_k is simply the product of the polynomials (1+X^i) for i < k. The property we need to prove is that F_k be of the form A + B(1+X+X^2+...+X^(N-1)) where A and B are integer constants with A<>0. Now, this ring R = Z[X]/( X^N - 1 ) may be decomposed using the integer factorization of X^N - 1 = Prod_{n|N} Phi_n(X), where Phi_n is the n-th cyclotomic polynomial. We have R isomorphic to the direct sum of the rings Z[X]/Phi_n = Z[zeta_n], where zeta_n is a primitive n-th root of unity (in \Qbar, wherever that is :-) ); the map from R into the direct sum just sends X to zeta_n. Observe that the polynomial at the end of the previous paragraph is sent to A in all these rings except the case n=1, where it is sent to A+BN. Thus the proof of the original conjecture is equivalent to the existence of a nonzero integer A with the property that a) For all n|N with n>1, F_N(zeta_n) = A b) F_N(1) is congruent to A mod N. Note that F_N(1) = Prod_{i