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