Embedding regular polygons in a lattice - Online Technical Discussion Groups

Embedding regular polygons in a lattice
by Jack Heimrath

Introduction

Consider the following finite, square grid and triangle:

In[]:=

$EQ = "";eqRow[args__] := Panel@Row[{args}, $EQ]pgrid[args__] := Panel@Grid[args]prow[args__] := Panel@Row[args]labelPos[snap:{lo1_, hi1_}, loc:{lo2_, hi2_}] := With[ {tests = TrueQ/@{lo1≤lo2, hi1≤hi2}}, snap + .2 * (tests /. {True-1, False1})]DynamicModule[ {grid = Flatten[Table[{i, j}, {i, -5, 5}, {j, -5, 5}], 1], A, B, C, a, b, c, min = -5, max = 5}, Manipulate[ {a, b, c} = Flatten[Nearest[grid, #, 1]& /@ {A, B, C}, 1]; Panel[Column[ Show[ Graphics[ Directive[EdgeForm@Blue, Yellow], Triangle[{a, b, c}], Black, Text["A", labelPos[a, A]], Text["B", labelPos[b, B]], Text["C", labelPos[c, C]] , ImageMargins5, PlotLabel"Can you find an equilateral triangle whose vertices are lattice points?" ], ListPlot[grid, AspectRatio1, PlotStyleDarker@Green] , ImageSizeLarge, AxesTrue, Ticks({#, #}& @ Table[i,{i,-5,5}]) ], Column[ Row[ eqRow["{

A

1

,

A

2

}", a], eqRow["{

B

1

,

B

2

}", b], eqRow["{

C

1

,

C

2

}", c] , Spacer[5] ], pgrid@ {TraditionalForm[Abs["AB"]], $EQ, #, " ≈ ", N@#}&[Norm[a-b]], {TraditionalForm[Abs["AC"]], $EQ, #, " ≈ ", N@#}&[Norm[a-c]], {TraditionalForm[Abs["BC"]], $EQ, #, " ≈ ", N@#}&[Norm[b-c]]  ] , Center ]], {{A, {0, -2}}, Locator}, {{B, {1, 2}}, Locator}, {{C, {-3, 1}}, Locator}, AppearanceElementsNone, PaneledFalse ], SaveDefinitionsTrue]

Out[]=

The yellow triangle looks equilateral, but the side lengths displayed below the plot tell a different story — it is only isosceles — with the edge AC being slightly longer than the remaining two edges. Feel free to play around with the positions of the vertices A, B, and C and try to see if you can find a configuration which gives an equilateral triangle. It shouldn’t take too long to convince yourself that this is an impossible task, at least when you constrain yourself to such a small grid. But maybe, if we were working with a larger grid, it might be possible to find an equilateral triangle? In this demonstration we answer this question in the negative - no matter the size of the grid, no regular polygon other than a square can have all vertices coincide with points on a grid.

Visualizing Lattices and their Properties

We introduce some standard mathematical language which will hopefully make the ideas presented in this notebook easier to follow and understand. An (integer) lattice in n-dimensional space we will mean the collection of points

{(

x

1

,

x

2

,...,

x

n

)∈

n



:

x

1

,

x

2

,...,

x

n

∈}

. Simply put these are points in n-dimensional space whose coordinates are integers. We’ve already shown what this looks like in 2 dimensions, and here’s part of a 3-dimensional lattice:

In[]:=

latticeSlice[x_:5, y_:5, z_:5] := ListPointPlot3D[Flatten[Table[{i, j, k}, {i, -x, x}, {j, -y, y}, {k, -z, z}], 2], AspectRatio  1, Axes  True, Boxed  False, PlotStyle  Darker[Green], PlotLabel  "A lattice in 3 dimensions"]Rasterize@latticeSlice[]

Out[]=

In dimensions 4 and higher visualizing the lattice becomes impossible, but the same rules apply — lattice points are points with integer coordinates. From now on when talking about a lattice we will specifically mean the 2-dimensional lattice. In this particular case lattice points have what is know as a ring structure, that is they can be added and multiplied and the result of these operations is again a lattice point. The formulae for addition and multiplication are as follows: •

(

x

1

,

y

1

)+(

x

2

,

y

2

)=(

x

1

+

x

2

,

y

1

+

y

2

)

; •

(

x

1

,

y

1

)(

x

2

,

y

2

)=(

x

1

x

2

-

y

1

y

2

,

x

1

y

2

+

x

2

y

1

)

. Notice that if the coordinates on the left hand side are integers, then so are the coordinates on the right hand side. The multiplication formula may seem a bit mysterious if you hadn’t encountered it before, however if you’ve taken a course in Complex Analysis you’ll recognize that it is exactly the rule for multiplication of complex numbers. More formally we can say that our lattice is a sub-ring of the field of complex numbers. If this sounds arcane don’t worry — all we really need to know is that we can add points and that multiplying a point by

(0,1)

is equivalent to rotating it 90° counterclockwise around the origin, as can be seen below. Using this tool we can actually rotate a point 90° about any other point as well.

ClearAll[pointRotation];pointRotation[a:{_, _}, b:{_, _}:{0, 0}, angle_:Pi/2] := ListAnimate[ Table[ Module[ {range = Ceiling[1.1 Norm[b-a]], grid, c = RotationMatrix[angle].(a-b)+b, d = RotationMatrix[θ].(a-b)+b, ang = Which[a[[1]] === b[[1]] && a[[2]] >= b[[2]], Pi/2, a[[1]] === b[[1]], -Pi/2, True, ArcTan[(a-b)[[2]]/(a-b)[[1]]]]}, grid=Table[{i, j}, {i, b[[1]] - range, b[[1]] + range}, {j, b[[2]] - range, b[[2]] + range}]; Show[ ListPlot[grid, PlotStyleDarker@Green, TicksNone, AspectRatio1], Graphics[ PointSize[Large], Dashed, Red, Line[{b, d}], Point[d], Dashing[{}], Circle[b, Norm[a-b]/4, If[a[[1]]<b[[1]], Pi, 0]+{ang, θ+ang}], Blue, Line[{a, b, c}], Orange, Point[a], Point[b], Point[c], Text["A", a-.25], Text["B", b-.25], Text["C" , c-.25], Text["D", d+.25] , ImageSizeTiny, AspectRatio1 ] , PlotLabel->"Rotating point A "<>ToString[angle*180/Pi]<>"° counterclockwise about "<>If[b==={0,0}, "the origin.", "point B."]] ], {θ, 0, angle, Pi/120} ], SaveDefinitions  True]Row[{pointRotation[{4, 2}], pointRotation[{4, 2}, {1, 3}]}]

Out[]=

Let's also take a moment to see what addition "looks like" in our lattice. Treating our two points

(

x

1

,

y

1

),(

x

2

,

y

2

)

as vectors, addition is simply coordinatwise, or vector, addition:

In[]:=

DynamicModule[ {grid = Flatten[Table[{i, j}, {i, -5, 5}, {j, -5, 5}], 1], A, B, a, b, c, min = -5, max = 5}, Manipulate[ {a, b, c} = Flatten[Nearest[grid, #, 1]& /@ {A, B, A+B}, 1]; Panel[Column[ Show[ Graphics[ Lighter@Blue, Arrowheads[Small], Arrow[{{0, 0}, Dynamic[#]}]& /@ {a,b}, Black, Text["A", labelPos[a, A]], Text["B", labelPos[b, B]], Text["C", c+{-.3, .3}], Orange, Dashed, Arrow[{Dynamic@a, Dynamic@(a+b)}], Arrow[{Dynamic@b, Dynamic@(a+b)}], Red, Dashing[None], Arrow[{{0, 0}, Dynamic@(a+b)}] , ImageMargins5 ], ListPlot[grid, AspectRatio1, PlotStyleDarker@Green] , ImageSize  Large, Axes  True, Ticks  ({#, #}& @ Table[i, {i, min, max}]), PlotLabel  "Adding lattice points is the same as vector addition." ], Column[Row[ eqRow["A", a], eqRow["B", b], eqRow["C", c] , Spacer[5] ]] , Center ]], {{A, {2, 0}}, Locator}, {{B, {1, 2}}, Locator}, AppearanceElements  None, Paneled  False ], SaveDefinitions  True]

Out[]=

The important thing to notice here is that if we have a triangle given by some points

{(

x

1

,

y

1

),(

x

2

,

y

2

),(

x

3

,

y

3

)}

we can add the point

(-

x

1

,-

y

1

)

to all three of them to get a congruent triangle

{(0,0),(

x

2

-

x

1

,

y

2

-

y

1

),(

x

3

-

x

1

,

y

3

-

y

1

)}

, one of whose vertices is at the origin. In particular, if we have an equilateral triangle whose vertices belong to the lattice we can always translate it so that one of the vertices lies at the origin. This can be used to simplify some of the computations in the following proof.

The Case of the Equilateral Triangle

To prove that no three lattice points determine an equilateral triangle we argue by contradiction. Assume there exists an equilateral triangle with side length L whose vertices belong to a lattice. As mentioned before, we are free to assume that one vertex of the triangle, denoted by O, lies at the origin:

In[]:=

Module[ {O = {0, 0}, A = {1, 4}, B}, B = RotationMatrix[Pi/3].A; Graphics[ EdgeForm@Directive@Blue, Yellow, Triangle[{O, A, B}], Black, Text["O", O-.25], Text["A", A-.25], Text["B", B-.25], Red, PointSize[Large], Point[O], Point[A], Point[B] , PlotLabel  "An equilateral triangle with side length L. Assume its vertices\n are lattice points of some 2 dimensional lattice.", ImageSize -> 350 ]]

Out[]=

We’ve assumed the vertices of the triangle are lattice points, but we don’t know the scale or the orientation of the lattice. However, since we know that the sum and difference of two lattice points is also a lattice point, we can construct the points

C=B-A,D=-A,E=-B,F=A-B

and be sure they are also lattice points. It is not hard to see that the points

A,B,C,D,E,F

are the vertices of a regular hexagon:

In[]:=

Module[ {O = {0, 0}, A = {1, 4}, B, C, D, E, F}, B = RotationMatrix[Pi/3].A; C = B-A; D = -A; E = -B; F = A-B; Graphics[ EdgeForm@Directive@Blue, Yellow, Triangle[{O, A, B}], Black, Text["O", O-.3], Text["A", A-.3], Text["B", B-.3], Text["C  B-A", C-.3], Text["D  -A", D-.3], Text["E  -B", {E[[1]]+.3, E[[2]]-.3}], Text["F  A-B", F+.3], Red, PointSize[Large], Point/@{O, A, B, C, D, E, F}, Blue, Dashed, Line[{B, C, D, E, F, A}] , PlotLabel  "Given an equilateral triangle we can construct a regular hexagon \n whose vertices are also lattice points.", ImageSize -> 350 ]]

Out[]=

For our next step we make use of the fact that we can rotate points. Rotating each vertex of the hexagon 90° around its counterclockwise neighbor yields a new, smaller, but still regular hexagon. We are also guaranteed that the vertices of the smaller hexagon are lattice points.

In[]:=

ClearAll[smallerHexagon];smallerHexagon[a:{_, _}:{1, 4}, frameCount_:60, fps_:30] := ListAnimate[ Table[ Module[ {o = {0, 0}, b, c, d, e, f, points, rotatedPoints, rotatingPoints}, b = RotationMatrix[Pi/3].a; {c, d, e, f} = {b-a, -a, -b, a-b}; points = {a, b, c, d, e, f}; {rotatedPoints, rotatingPoints} = Table[RotationMatrix[#].(i[[1]]-i[[2]])+i[[2]], {i, Thread[List[points, RotateRight[points, 1]]]}]& /@ {Pi/2, θ}; Graphics[ EdgeForm@Directive@Blue, Yellow, Triangle[{o, a, b}], Blue, Line[RotateLeft[points, 1]], Darker@Green, Line[Join[rotatedPoints, {First[rotatedPoints]}]], Black, Text["O", o-.3], Text["A", {a[[1]], a[[2]]+.3}], Text["B", {b[[1]], b[[2]]+.3}], Text["C", {c[[1]], c[[2]]-.3}], Text["D", {d[[1]], d[[2]]-.3}], Text["E", {e[[1]], e[[2]]-.3}], Text["F", {f[[1]], f[[2]]+.3}], Darker@Gray, Dashed, Line/@Thread[List[RotateRight[points, 1], rotatingPoints]], Dashing[{}], PointSize[Large], Point/@rotatingPoints, Red, Point/@Join[{o}, points, rotatedPoints] , PlotLabel"Rotating each vertex 90° about its counterclockwise neighbour we\nfind a smaller hexagon whose vertices are once again lattice points." ] ], {θ, 0, Pi/2, Pi/(2 frameCount)} ], fps]smallerHexagon[10, 2]

Out[]=

We are now in position to derive the necessary contradiction. Let’s assume that the ratio of the length of the side of the smaller hexagon to the length of the side of the larger hexagon is ρ, where clearly

ρ<1

. We may now keep repeating the “shrinking procedure” to find successively smaller regular hexagons, all of whose vertices are lattice points. Clearly the side length of the

th

k

hexagon is

k-1

Lρ

, which tends to 0 as

k

tends to ∞. We know that our lattice points are separated by some distance d. But

k

Lρ

will eventually be smaller than d, which is clearly impossible! Thus there cannot exist an equilateral triangle (or regular hexagon for that matter) whose vertices are lattice points.

In[]:=

(* Computes the veritces of the specified number of nested regular ngons *)nestedPolygons[sides_Integer, layers_Integer:1, vertex1_:{2, 4}] /; sides ≥ 3 := Module[ {vertices, layerSeed, coords}, (* Given a vertex generates the layer that vertex belongs to *) vertices[v_, s_] := NestList[Simplify /@ (RotationMatrix[2*Pi/s].#&), v, s]; (* Given a vertex computes a vertex in the next layer *) layerSeed[v1_, s_] := Module[ {v2 = RotationMatrix[-2*Pi/s].v1}, RotationMatrix[Pi/2].(v1-v2)+v2 ]; (* Finds the vertices of the nested polygons *) coords = vertices[#, sides]& /@ NestList[layerSeed[#, sides]&, vertex1, layers]];(* Animates the shrinking procedure *)frames[sides_Integer, layers_Integer?Positive, frameCount_:60] /; (sides ≥ 3)&&(layers ≤ 3) := Module[ {colors = {Blue, Darker@Green, Orange, Purple}, background, θ = 0, Δθ = Pi/(2 frameCount), points}, points = nestedPolygons[sides, layers]; background = Riffle[Take[colors, Length@points], Line /@ points]; Table[ Graphics[Table[ background, Gray, PointSize[Medium], Join[ Table[Point[RotationMatrix[t].(points[[j, i+1]]-points[[j,i]])+points[[j, i]]], {i, sides}], Table[Line[{points[[j]][[i]], RotationMatrix[t].(points[[j]][[i+1]]-points[[j]][[i]])+points[[j]][[i]]}],{i,sides}] ] , {j, 1, layers} ]], {t, 0, Pi/2, Δθ} ]];ListAnimate[frames[6, 3, 10], 1.5]

Out[]=

What About Other Regular Polygons?

So far we’ve demonstrated that we cannot find an equilateral triangle or a regular hexagon whose vertices are lattice points. It turns out that the same construction that worked for hexagons works for almost all other regular polygons. Below we demonstrate the shrinking procedure for pentagons and heptagons.

In[]:=

Row[{ListAnimate[frames[5, 1, 10], 1.5], ListAnimate[frames[7, 1, 10], 1.5]}]

Out[]=

The main takeaway here is that, given a regular n-gon of side length L, we can construct a similar n-gon with side length

ρ(n)L

. Let’s see if we can figure out a formula for this

ρ(n)

factor — if we can show that it’s less than one we will have completed the proof.

Here’s our setup: assume we are given three consecutive vertices of a regular n-gon, call them

a

,

b

, and

c

. Without loss of generality we can assume

a=(0,0)

lies at the origin and we assume that

b=(

b

1

,

b

2

)

for some integers

b

1

and

b

2

. The interior angle of a regular n-gon is equal to

π1-

2

n

. Then the point

c

can be obtained by rotating

a

by

π1-

2

n

radians

about

b

.

In[]:=

ClearAll[a, b, c, rotate];rotate[a:{_, _}, b:{_, _}:{0, 0}, θ_] := RotationMatrix[θ].(a-b)+b;a = {0, 0};b = {b1, b2};c[n_] := rotate[a, b, Pi(1-2/n)];

The general formula for

c(n)

:

In[]:=

c[n]

Out[]=

b1-b1Cos1-

2

n

π+b2Sin1-

2

n

π,b2-b2Cos1-

2

n

π-b1Sin1-

2

n

π

An example in the case

b=(-1,0)

and

n=10

:

In[]:=

pointRotation[a, {-1, 0}, Pi(1-2/10)]

Out[]=

We need the coordinates of c to figure out where the shrinking procedure will send b.

Let us denote the square of the length of the side of our n-gon by L. Clearly L is equal to the square of the distance between two consecutive vertices of our n-gon.

In[]:=

ClearAll[L];L = Total[(b-a)^2]

Out[]=

2

b1

+

2

b2

The n-gon shrinking process takes each vertex p to a new vertex p’. To find the shrinking factor ρ(n) we first compute L’ — the square of the side length of the shrunk n-gon.

In[]:=

ClearAll[aPrime, bPrime, LPrime];aPrime = rotate[a, b, Pi/2];bPrime[n_] := rotate[b, c[n], Pi/2]LPrime[n_] := Total[(bPrime[n]-aPrime)^2]

With this we have found the general formula for the square of the length of the side of the shrunk n-gon:

In[]:=

LPrime[n]

Out[]=

2

b1+b1Cos1-

2

n

π-b2Cos1-

2

n

π-b1Sin1-

2

n

π-b2Sin1-

2

n

π

+

2

-b2-b1Cos1-

2

n

π-b2Cos1-

2

n

π-b1Sin1-

2

n

π+b2Sin1-

2

n

π

This seems quite complicated, but Simplifying the formula yields something much more tractable:

In[]:=

Simplify[LPrime[n]]

Out[]=

(

2

b1

+

2

b2

)3+2Cos

(-2+n)π

n

-2Sin

(-2+n)π

n



Since

L'=ρ(n)L

, to find

ρ(n)

we simply divide L’ by L.

In[]:=

ClearAll[ρ];ρ[n_] := Simplify[LPrime[n]]/Lρ[n]

Out[]=

3+2