(a)

(7 points) For \((a,b)\in \mathbb Z^2\), define \(T_{(a,b)}:\mathbb Z^2\to \mathbb Z^2\) by

\[ T_{(a,b)}(k,\ell )=(k+a,\ell +b). \]

Show that \(T_{(a,b)}\) is a transformation of \(\mathcal M_{\mathbb Z^2}\).

(b)

(7 points) Show that the inverse of a translation is a translation. More precisely, show that

\[ T_{(a,b)}^{-1}=T_{(-a,-b)}. \]

(c)

(7 points) Define

\[ R_x(k,\ell )=(-k,\ell ), \qquad R_y(k,\ell )=(k,-\ell ). \]

Show that \(R_x\) and \(R_y\) are transformations of \(\mathcal M_{\mathbb Z^2}\).

(d)

(6 points) Show that each of the transformations

\[ \operatorname {id},\qquad R_x,\qquad R_y,\qquad R_x\circ R_y \]

is its own inverse.

(e)

(7 points) Define \(S(k,\ell )=(\ell ,k)\). Show that \(S\) is a transformation of \(\mathcal M_{\mathbb Z^2}\).

(f)

(6 points) Show that \(S\) is its own inverse, i.e.

\[ S^{-1}=S. \]

Let \(F\) be a transformation of \(\mathcal M_{\mathbb Z^2}\).

(a)

(7 points) Let \(p\in \mathbb Z^2\). Show that \(F\) sends the four points adjacent to \(p\) to the four points adjacent to \(F(p)\).

Hint: Each point has exactly four adjacent points. Since \(F\) is injective and sends lines to lines, what happens to the four neighbors of \(p\)?

(b)

(7 points) Show that, by composing \(F\) on the left with a translation, we may assume that

\[ F(0,0)=(0,0). \]

Hint: If \(F(0,0)=(a,b)\), compose \(F\) with \(T_{(-a,-b)}\).

(c)

(7 points) Now assume that \(F(0,0)=(0,0)\). Show that \(F(1,0)\) must be one of

\[ (1,0),\quad (-1,0),\quad (0,1),\quad (0,-1). \]

(d)

(7 points) Show that, by composing \(F\) on the left with transformations chosen from

\[ \operatorname {id},\quad R_x,\quad R_y,\quad R_x\circ R_y,\quad S,\quad R_x\circ S,\quad R_y\circ S,\quad R_x\circ R_y\circ S, \]

we may assume that

\[ F(0,0)=(0,0) \qquad \text {and}\qquad F(1,0)=(1,0). \]

(e)

(7 points) Now assume that \(F(0,0)=(0,0)\) and \(F(1,0)=(1,0)\). Show that

\[ F(0,1)=(0,1) \qquad \text {or}\qquad F(0,1)=(0,-1). \]

Then explain why, by composing with \(R_y\) if necessary, we may assume that

\[ F(0,0)=(0,0),\qquad F(1,0)=(1,0),\qquad F(0,1)=(0,1). \]

Hint: First use part (a). To rule out \(F(0,1)=(-1,0)\), use the fact that \((1,0)\) and \((0,1)\) have two common adjacent points, while \((1,0)\) and \((-1,0)\) do not.

Let \(F\) be a transformation of \(\mathcal M_{\mathbb Z^2}\). Assume that

(a)

(8 points) Show that \(F(1,1)=(1,1)\).

Hint: The point \((1,1)\) is adjacent to both \((1,0)\) and \((0,1)\). It is the unique point, different from \((0,0)\), with this property.

(b)

(8 points) Show that \(F(-1,0)=(-1,0)\) and \(F(0,-1)=(0,-1)\).

Hint: By Problem 2(a), the remaining neighbors of \((0,0)\) must be sent to the remaining neighbors of \((0,0)\). To rule out switching them, use the fact that \((1,0)\) and \((0,-1)\) have two common adjacent points, while \((1,0)\) and \((-1,0)\) do not.

(c)

(9 points) Show, by induction, that

\[ F(k,0)=(k,0) \]

for every integer \(k\geq 0\).

Hint: This is similar to the proof for the integer line from lecture, but there is one extra difficulty. Once you know \(F(k-1,0)=(k-1,0)\) and \(F(k,0)=(k,0)\), use the line \(\{(k,0),(k+1,0)\}\) to restrict the possible values of \(F(k+1,0)\). Then use injectivity and compare the number of common adjacent points to rule out the wrong possibilities.

Please answer in a few complete sentences. Your responses will be anonymous.

(a)

Have you worked in groups on your homework? Are there any barriers that make it difficult for you to work in groups?

(b)

Did you enjoy the ungraded quizzes? If so, would you like to see more of them?

(c)

Would you like to have a recap class, even if it meant that we would cover less new content?

(a)

(Completing the proof for the square grid \(\dagger \)) Continue Problem 3 and show that the normalized transformation is the identity.

More precisely, let \(F\) be a transformation of \(\mathcal M_{\mathbb Z^2}\), and assume that

\[ F(0,0)=(0,0), \qquad F(1,0)=(1,0), \qquad F(0,1)=(0,1). \]

In Problem 3, you proved some first consequences of these assumptions. The goal is to prove that

\[ F(k,\ell )=(k,\ell ) \]

for every \((k,\ell )\in \mathbb Z^2\).

(i)

Show, using arguments similar to Problem 3(c), that \(F\) fixes the negative part of the horizontal axis and the entire vertical axis.

(ii)

Show that \(F(k,\ell )=(k,\ell )\) for every \(k,\ell \geq 0\).

Suggested strategy: Use induction on \(k+\ell \). The induction hypothesis should be: \(F(a,b)=(a,b)\) for every point \((a,b)\) with \(a,b\geq 0\) and \(a+b\leq n\). Then prove the result for a point \((k,\ell )\) with \(k,\ell \geq 0\) and \(k+\ell =n+1\).

Hint: If \(k,\ell \geq 1\), then \((k,\ell )\) is the unique point, different from \((k-1,\ell -1)\), adjacent to both \((k-1,\ell )\) and \((k,\ell -1)\).

(iii)

Adapt the same argument to the other three quadrants.

(iv)

Conclude that \(F=\operatorname {id}\).

(b)

(Higher-dimensional square grids \(\dagger \)) Consider the model with point set \(\mathbb Z^n\), where lines are edges between points that differ by \(1\) in exactly one coordinate. Describe the transformations of this model.

(c)

(Lattice lines in \(\mathbb Z^2\) \(\dagger \)) Consider the model with point set \(\mathbb Z^2\), where lines are subsets of the form

\[ v+\mathbb Z u=\{v+ku:k\in \mathbb Z\}, \]

where \(v\in \mathbb Z^2\) and \(u=(a,b)\in \mathbb Z^2\) satisfies \(a\mathbb Z+b\mathbb Z=\mathbb Z\). Equivalently, \(u\) is primitive, meaning \(\gcd (a,b)=1\). Can you describe the transformations of this model?

(d)

(A model with no nontrivial transformations \(\dagger \)) Can you construct a model satisfying axioms I1 and I2 whose only transformation is the identity?