% ===================================================================== % Sections 2-6: local structure, angle identities, convex dissections % and chords, boundary pieces, pinwheel skeletons, and the complete % classification for k = 3 and k = 4 pieces. % Insertable into the A389392 manuscript: it only needs the macros and % theorem environments defined in the preamble of nota_completitud.tex % and the notation of Section 1 (T, n, A, B, C, \trap{b}{s}, G). % ===================================================================== \section{Local structure and two angle identities}\label{sec:local} For a vertex $v$ of $G$ let $a(v)$ (resp.\ $c(v)$) be the number of pieces having a corner at $v$ with angle $60^\circ$ (resp.\ $120^\circ$), and let $h(v)$ be the number of pieces containing $v$ in the relative interior of one of their sides. Since every piece has two corners of each kind, \begin{equation}\label{eq:ac} \sum_{v} a(v)=\sum_{v} c(v)=2k . \end{equation} \begin{lemma}[local structure]\label{lem:local} \begin{enumerate}[label=\textup{(\alph*)}] \item At a corner of $T$ we have $(a,c,h)=(1,0,0)$. \item At a boundary vertex we have $h=0$ and $(a,c)\in\{(1,1),(3,0)\}$; we say that the vertex is of type $B_1$ or $B_3$. A $B_1$ vertex is incident with exactly one interior edge; a $B_3$ vertex is incident with exactly two, which form angles of $60^\circ$ with the side of $T$ and with each other. \item At an interior vertex we have $h\le 1$ and $a+2c+3h=6$. Hence $(a,c,h)$ is one of $(1,1,1)$, $(3,0,1)$, $(0,3,0)$, $(2,2,0)$, $(4,1,0)$, $(6,0,0)$, and we say that the vertex is of type $\mathrm{T}$, $\mathrm{T}'$, $\mathrm{Y}$, $\mathrm{X}$, $\mathrm{W}$, $\mathrm{Z}$, respectively. The degrees of these vertices are $3,4,3,4,5,6$. \end{enumerate} At a vertex $Q$ of type $\mathrm{T}$ two of the three edges are collinear; the straight segment they form is the \emph{line} of $Q$, and the third edge is the \emph{stem} of $Q$. The piece containing $Q$ in the relative interior of a side lies on the side of the line opposite to the stem. At a vertex of type $\mathrm{Y}$ any two of the three edges form an angle of $120^\circ$. \end{lemma} \begin{proof} The pieces containing $v$ cover a neighbourhood of $v$ in $T$. Each of them contributes an angle of $60^\circ$ or $120^\circ$ (if $v$ is one of its corners) or of $180^\circ$ (if $v$ lies in the relative interior of one of its sides), and these contributions add up to $60^\circ$, $180^\circ$ or $360^\circ$ in cases (a), (b), (c), respectively. In (a) an angle of $60^\circ$ cannot be split. In (b), a piece containing $v$ in the relative interior of a side has this side on $\partial T$, because the piece lies in $T$; it then covers a half-disc around $v$, so no piece has a corner at $v$, and $v$ would not be a vertex. In (c), two such pieces would have their sides on a common line and lie on opposite sides of it, and again no piece would have a corner at $v$. The remaining assertions are arithmetic: an interior vertex has degree $a+c+h$, the number of pieces around it, and a boundary vertex has degree $a+c+1$; at a vertex of type $\mathrm{T}$ the piece with angle $180^\circ$ determines the line, and the stem separates the two pieces with angles $60^\circ$ and $120^\circ$. \end{proof} We write $B_1,B_3,t,t',y,x,w,z$ for the numbers of vertices of the respective types, and $B=B_1+B_3$ for the number of boundary vertices. \begin{lemma}[angle identities]\label{lem:identities} For every $k$-tiling of $T$, \begin{align} y&=1+B_3+t'+w+2z, \label{eq:I1}\\ B_1+3B_3+t+3t'+2x+4w+6z&=2k-3. \label{eq:I2} \end{align} In particular, every tiling has a vertex of type $\mathrm{Y}$. \end{lemma} \begin{proof} By Lemma~\ref{lem:local}, $a(v)-c(v)$ equals $1$ at the corners of $T$; $0$ at vertices of types $B_1$, $\mathrm{T}$, $\mathrm{X}$; $3$ at vertices of types $B_3$, $\mathrm{T}'$, $\mathrm{W}$; $6$ at vertices of type $\mathrm{Z}$; and $-3$ at vertices of type $\mathrm{Y}$. By \eqref{eq:ac} the sum of all these numbers is $0$, which is \eqref{eq:I1}. Next we add up all angles at all vertices in two ways. Piece by piece, each piece contributes $360^\circ$ at its corners and $180^\circ$ for every vertex lying in the relative interior of one of its sides, so the total is $360k+180(t+t')$ degrees. Vertex by vertex, the total is $3\cdot 60+180B+360(t+t'+y+x+w+z)$ degrees. Hence \[ 2k=1+B_1+B_3+t+t'+2(y+x+w+z), \] and eliminating $y$ by means of \eqref{eq:I1} gives \eqref{eq:I2}. \end{proof} \section{Dissections of convex polygons, full strips and chords}\label{sec:chords} \begin{lemma}\label{lem:twoconvex} If a convex polygon $P$ is the union of two convex polygons $P_1,P_2$ with disjoint interiors, then there is a line $\ell$ such that $P_1$ and $P_2$ are the intersections of $P$ with the two closed half-planes bounded by $\ell$. \end{lemma} \begin{proof} By the separation theorem there is a line $\ell$ with $P_i\subseteq H_i$, where $H_1,H_2$ are the closed half-planes bounded by $\ell$. A point of $P$ in the interior of $H_1$ does not lie in $P_2$, hence lies in $P_1$; taking closures, $P\cap H_1\subseteq P_1\subseteq P\cap H_1$. The same argument applies to $P_2$. \end{proof} \begin{lemma}[lattice chords]\label{lem:chords} Let $P$ be a convex polygon with sides on lattice lines, and let $\sigma$ be a lattice segment joining two points of $\partial P$ and meeting the interior of $P$. \begin{enumerate}[label=\textup{(\alph*)}] \item If $P$ is an equilateral triangle, then $\sigma$ is parallel to a side and cuts off an equilateral triangle. \item If $P=\trap{b}{s}$, then exactly one of the following holds: \textup{(i)} $\sigma$ is parallel to the bases and joins the two legs, and both parts are trapezoids; \textup{(ii)} $\sigma$ is parallel to a leg $\lambda$ and joins the two bases, the part adjacent to $\lambda$ is a parallelogram and the other part is a trapezoid; \textup{(iii)} $\sigma$ cuts off an equilateral triangle at one of the two $60^\circ$ corners. \item If $P$ is a parallelogram, then either $\sigma$ is parallel to two sides of $P$ and both parts are parallelograms, or $\sigma$ lies in the third lattice direction and either joins two opposite sides (both parts are then trapezoids) or cuts off an equilateral triangle at a $60^\circ$ corner. \end{enumerate} \end{lemma} \begin{proof} (a) The endpoints of $\sigma$ lie on two different sides, so $\sigma$ is parallel to the third side. (b) After a symmetry of the lattice, $P=\{0\le y\le s,\ x\ge 0,\ x+y\le b\}$. A lattice segment through an interior point lies on a line $y=c$, $x=c$ or $x+y=c$. A segment on $y=c$ joins the legs, as in (i). A segment on $x=c$ joins $y=0$ to the short base $y=s$ if $c\le b-s$, which is case (ii) with the parallelogram $\{0\le x\le c\}$; otherwise it joins $y=0$ to the leg $x+y=b$ and cuts off a triangle at $(b,0)$. Segments on $x+y=c$ are treated symmetrically. (c) After a symmetry, $P=\{0\le x\le p,\ 0\le y\le q\}$ with $60^\circ$ corners at $(0,0)$ and $(p,q)$; segments on $x=c$ or $y=c$ give two parallelograms, and a segment on $x+y=c$ joins opposite sides if $\min(p,q)\le c\le\max(p,q)$ and cuts off a triangle at $(0,0)$ or at $(p,q)$ otherwise. \end{proof} \begin{corollary}\label{cor:convex} \begin{enumerate}[label=\textup{(\alph*)}] \item No equilateral triangle is tiled by fewer than three trapezoids. \item If a trapezoid is tiled by two trapezoids, they are separated by a segment of type \textup{(i)}; we call such a segment a \emph{parallel cut}. \item If a parallelogram is tiled by two trapezoids, they are separated by a segment in the third lattice direction joining two opposite sides. \end{enumerate} \end{corollary} \begin{proof} A trapezoid is not a triangle. By Lemma~\ref{lem:twoconvex}, a tiling of a convex polygon by two convex pieces is given by a single segment $\sigma$ as in Lemma~\ref{lem:chords}. In case (a) one of the parts is a triangle; in cases (b) and (c) the listed alternatives are the only ones in which both parts are trapezoids. \end{proof} A \emph{full strip} is a piece having $60^\circ$ corners at two corners of $T$. \begin{lemma}\label{lem:strip} A full strip with corners at $A$ and $B$ is $\trap{n}{s}$ with long base $AB$ and legs on $AC$ and $BC$; its complement in $T$ is the equilateral triangle of side $n-s$ at $C$, which is tiled by the other pieces. A tiling has at most one full strip. \end{lemma} \begin{proof} The long base of a trapezoid joins its two $60^\circ$ corners, and its legs leave these corners along the sides of $T$. Two full strips would both contain a neighbourhood in $T$ of a common corner of $T$. \end{proof} A \emph{chord} of a tiling is a segment contained in the union of the boundaries of the pieces, joining two points of $\partial T$, and not contained in $\partial T$. \begin{lemma}[no chords]\label{lem:nochord} Every chord is parallel to a side of $T$ and cuts off a corner triangle $T_1$; every piece lies in $T_1$ or in the trapezoid $T\setminus T_1$. If $k\le 5$ and the tiling has no full strip, then it has no chord. \end{lemma} \begin{proof} The only lattice directions pointing from a corner of $T$ into $T$ run along the sides of $T$. Hence a chord ends at non-corner points of two different sides of $T$, so it is parallel to the third side and cuts off a corner triangle $T_1$. The chord does not meet the interior of any piece, so every piece lies on one side of it. By Corollary~\ref{cor:convex}(a), $T_1$ contains at least three pieces, so the trapezoid $T\setminus T_1=\trap{n}{s'}$ contains at most two. If it consists of one piece, this piece is a full strip. If it consists of two pieces, they are separated by a parallel cut (Corollary~\ref{cor:convex}(b)), and the piece containing the long base of $T\setminus T_1$, which is a whole side of $T$, is a full strip. \end{proof} \section{Boundary pieces and frames}\label{sec:boundary} \begin{lemma}[boundary pieces]\label{lem:bdry} Assume that the tiling has neither a full strip nor a chord. Then: \begin{enumerate}[label=\textup{(\alph*)}] \item the corners $A,B,C$ lie in three different pieces, the \emph{corner pieces}; each of them has exactly two sides on $\partial T$, namely its long base and one leg, lying on the two sides of $T$ through its corner; \item every other piece has at most one side on $\partial T$; \item no side of a piece lying on $\partial T$ contains a boundary vertex in its relative interior; \item every side of $T$ contains a boundary vertex; in particular $B\ge 3$; \item if $m$ denotes the number of non-corner pieces having a side on $\partial T$, then \begin{equation}\label{eq:m} m=B-3\qquad\text{and}\qquad f:=k-3-m\ \ge 0 , \end{equation} where $f$ is the number of pieces without a side on $\partial T$. \end{enumerate} \end{lemma} \begin{proof} (a) A piece containing two corners of $T$ has $60^\circ$ corners there (Lemma~\ref{lem:local}(a)), so it would be a full strip. The two sides of the corner piece $Q_A$ through $A$ are its long base and a leg, and they lie on $AB$ and $AC$. The short base of $Q_A$ is parallel to its long base and does not pass through $A$, so it does not lie on $\partial T$. If, say, the long base is $AD\subset AB$, the other leg starts at $D$ in the direction of $BC$, and it lies on $BC$ only if $D=B$, i.e.\ only if $Q_A$ is a full strip. The case of a long base on $AC$ is symmetric. (b) A convex polygon has at most one side on a given line, so two sides of a piece lying on $\partial T$ lie on different sides of $T$. If these two sides of the piece share an endpoint, this endpoint is a corner of $T$. Otherwise they are opposite sides of the piece; they are not its bases, which are parallel, so they are its legs. But then its short base joins two points on different sides of $T$ and is a chord. (c) This is Lemma~\ref{lem:local}(b). (d) The side of $Q_A$ on $AB$ has length less than $n$ (a long base of length $n$ would make $Q_A$ a full strip), so its endpoint other than $A$ is a boundary vertex on $AB$. (e) The boundary edges of $G$ form a cycle with $3+B$ edges, and each of them lies in exactly one piece. By (a)--(c), the corner pieces contain exactly six of them and every other piece contains at most one. \end{proof} \begin{lemma}[frames]\label{lem:frame} Assume that the tiling has neither a full strip nor a chord, and that $m=0$. Then $B_3=0$ and $B_1=3$, and after a reflection of $T$ the corner pieces are \begin{align*} Q_A&=\{x\ge 0,\ 0\le y\le s_A,\ x+y\le n-s_B\},\\ Q_B&=\{y\ge 0,\ x\ge s_C,\ n-s_B\le x+y\le n\},\\ Q_C&=\{0\le x\le s_C,\ y\ge s_A,\ x+y\le n\}, \end{align*} where $s_A,s_B,s_C\ge 1$ are their legs; their long bases are $n-s_B$, $n-s_C$ and $n-s_A$. Put $S=s_A+s_B+s_C$. The remaining pieces tile the triangle $\{x\ge s_C,\ y\ge s_A,\ x+y\le n-s_B\}$ of side $n-S$ if $Sn$, and there are no remaining pieces if $S=n$. \end{lemma} \begin{proof} By \eqref{eq:m} we have $B=3$, so by Lemma~\ref{lem:bdry}(d) every side of $T$ contains exactly one boundary vertex and is the union of the two sides of corner pieces lying on it. Suppose that the boundary vertex on $AB$ is of type $B_3$. Then $Q_A$ and $Q_B$ both have $60^\circ$ corners there, so both have their long bases on $AB$. Since every corner piece has exactly one long base and one leg on $\partial T$, one of the sides $AC$, $BC$ then consists of two legs, whose endpoints meet at the boundary vertex of that side with angles $120^\circ+120^\circ>180^\circ$, which is absurd. Hence the three boundary vertices are of type $B_1$, and every side of $T$ contains exactly one long base. There are only two ways of assigning bijectively to each corner piece a side of $T$ through its corner, namely $(Q_A,Q_B,Q_C)\mapsto(AB,BC,CA)$ and $(Q_A,Q_B,Q_C)\mapsto(AC,BA,CB)$, and they are exchanged by a reflection. In the first case the corner pieces are as displayed, with their long bases $b_A,b_B,b_C$ in place of $n-s_B,n-s_C,n-s_A$; the condition that each side of $T$ is covered exactly once reads $b_A+s_B=b_B+s_C=b_C+s_A=n$. Finally, a point $(x,y)\in T$ with $y>s_A$ lies in $Q_C$ if and only if $x\le s_C$, and otherwise it lies in $Q_B$ if and only if $x+y\ge n-s_B$; a point with $ys_C$, $y>s_A$, $x+yn-s_B$ (non-empty if and only if $S>n$). \end{proof} \begin{corollary}\label{cor:mge1} Assume that the tiling has neither a full strip nor a chord. If $k=3$, then $m=0$ and $S=n$. If $k\in\{4,5\}$, then $m\ge 1$. \end{corollary} \begin{proof} By \eqref{eq:m}, $m\le k-3$. If $m=0$, the $k-3$ non-corner pieces tile the triangle of Lemma~\ref{lem:frame}. For $k=3$ this triangle is empty, so $S=n$. For $k\in\{4,5\}$ it would be a triangle tiled by one or two trapezoids, contradicting Corollary~\ref{cor:convex}(a). \end{proof} \section{Pinwheel skeletons and interior edges}\label{sec:skeleton} Let $P$ be a vertex of type $\mathrm{Y}$. The three edge directions at $P$ contain no pair of opposite directions, so each edge at $P$ is contained in a maximal straight segment of $G$ having $P$ as an endpoint; we call these three segments the \emph{arms} of $P$. \begin{lemma}[pinwheel skeleton]\label{lem:skeleton} Suppose that the three arms of a $\mathrm{Y}$ vertex $P$ end at points $D_1,D_2,D_3$ of $\partial T$. Then the $D_i$ are boundary vertices lying on the three different sides of $T$, and the arms divide $T$ into three trapezoids $R_1,R_2,R_3$, each containing one corner of $T$. Each arm is a leg of one of the two regions adjacent to it and the short base of the other. \end{lemma} We call $R_1,R_2,R_3$ a \emph{pinwheel skeleton}. For a region $R_i$, its two arms are its \emph{leg-arm} and its \emph{base-arm} (the latter contains its short base), and the leg of $R_i$ lying on $\partial T$ is its \emph{boundary leg}. \begin{proof} An arm cannot end at a corner of $T$, since it would reach the corner along a side of $T$; and two arms meet only at $P$. Let $R$ be the region bounded by two arms $PD_i$, $PD_j$ and by an arc of $\partial T$ from $D_i$ to $D_j$ containing $r$ corners of $T$. Then $R$ is a convex polygon with angle $120^\circ$ at $P$, angles $\alpha_i,\alpha_j\in\{60^\circ,120^\circ\}$ at $D_i$ and $D_j$, and angle $60^\circ$ at each of the $r$ corners, so that $120+\alpha_i+\alpha_j+60r=180(r+1)$, i.e.\ $\alpha_i+\alpha_j=60+120r$. This forces $r=1$ and $\{\alpha_i,\alpha_j\}=\{60^\circ,120^\circ\}$; thus $R$ is a quadrilateral whose two $60^\circ$ corners are adjacent, i.e.\ a trapezoid. If $\alpha_i=60^\circ$, the long base of $R$ is the segment of $\partial T$ between $D_i$ and the corner, $PD_i$ is a leg of $R$ and $PD_j$ is its short base. Finally, the two regions adjacent to an arm $PD_i$ have angles adding up to $180^\circ$ at $D_i$, so exactly one of them has an angle of $60^\circ$ there. \end{proof} For a vertex $v$ let $\iota(v)$ be the number of interior edges at $v$; thus $\iota(v)=1$ or $2$ if $v$ is of type $B_1$ or $B_3$, and $\iota(v)=\deg v$ if $v$ is interior. Let $H$ be the graph formed by the interior vertices and the edges joining two of them, and let $e_H$ be its number of edges. \begin{lemma}[interior edges]\label{lem:slots} Assume that the tiling has no chord. Then \begin{equation}\label{eq:slots} \sum_{v\ \mathrm{interior}}\iota(v)-2e_H=B_1+2B_3 . \end{equation} Moreover: \begin{enumerate}[label=\textup{(\alph*)}] \item two vertices are joined by at most one edge, and no vertex of type $\mathrm{Y}$ lies on a triangle of edges; \item if two edges at a vertex $Q$ of type $\mathrm{T}$ end at boundary vertices, then one of them is the stem of $Q$ and the other one lies on the line of $Q$; no vertex of type $\mathrm{T}$ has three such edges. \end{enumerate} \end{lemma} \begin{proof} An interior edge joining two boundary vertices would be a chord, so every interior edge has one or two interior endpoints, and counting the endpoints of interior edges gives \eqref{eq:slots}. (a) Edges are straight segments. Three edges forming a triangle lie on lattice lines, so the triangle is equilateral and its angles are $60^\circ$, whereas two edges at a $\mathrm{Y}$ vertex form an angle of $120^\circ$. (b) Otherwise the line of $Q$ would be a chord. \end{proof} \section{Three and four pieces}\label{sec:k34} \begin{theorem}[three pieces]\label{thm:k3} Every $3$-tiling of $T$ is a \emph{pinwheel}: up to a reflection of $T$ there are positive integers $s_A,s_B,s_C$ with $s_A+s_B+s_C=n$ such that, with \[ D=(n-s_B,0),\quad E=(s_C,n-s_C),\quad F=(0,s_A),\quad P=(s_C,s_A), \] the pieces are \[ ADPF=\trap{n-s_B}{s_A},\qquad BEPD=\trap{n-s_C}{s_B},\qquad CFPE=\trap{n-s_A}{s_C}, \] with long bases $AD$, $BE$, $CF$. Each of the segments $PD$, $PE$, $PF$ is a leg of one piece and the short base of another. Conversely, every such triple defines a $3$-tiling. \end{theorem} \begin{proof} A full strip would leave a triangle tiled by two trapezoids (Lemma~\ref{lem:strip}), which is impossible by Corollary~\ref{cor:convex}(a). Hence there is no full strip and, by Lemma~\ref{lem:nochord}, no chord. By Corollary~\ref{cor:mge1}, $m=0$ and $S=n$, so the pieces are the three corner pieces of Lemma~\ref{lem:frame}; using $n-s_B-s_A=s_C$ one checks that their corners are the listed points. The statement about $PD,PE,PF$ is read off directly (or from Lemma~\ref{lem:skeleton}), and the converse is immediate. \end{proof} \begin{theorem}[four pieces]\label{thm:k4} Every $4$-tiling of $T$ is of exactly one of the following two forms: \begin{enumerate} \item[\textup{(A)}] a full strip $\trap{n}{s}$ together with a pinwheel of the triangle of side $n-s$; \item[\textup{(B)}] a pinwheel in which one of the three pieces is divided into two by a parallel cut. \end{enumerate} \end{theorem} \begin{proof} If there is a full strip, the remaining triangle carries a $3$-tiling, which is a pinwheel by Theorem~\ref{thm:k3}; this is (A). Assume that there is no full strip. Then there is no chord (Lemma~\ref{lem:nochord}), and Corollary~\ref{cor:mge1} and \eqref{eq:m} give $m=1$, $f=0$ and $B=4$. Substituting $B_1=4-B_3$ into \eqref{eq:I2} yields $2B_3+t+3t'+2x+4w+6z=1$. Hence $B_3=0$, $B_1=4$, $t=1$, all the other counts vanish, and $y=1$ by \eqref{eq:I1}. Let $P$ be the $\mathrm{Y}$ vertex and $Q$ the $\mathrm{T}$ vertex. By \eqref{eq:slots}, $3+3-2e_H=4$, so $e_H=1$: the segment $PQ$ is an edge, and each of $P$ and $Q$ has two further edges, which end at boundary vertices. By Lemma~\ref{lem:slots}(b), the edge $QP$ lies on the line of $Q$, which continues beyond $Q$ to a boundary vertex, and the stem of $Q$ ends at a boundary vertex. Thus all three arms of $P$ end on $\partial T$, and Lemma~\ref{lem:skeleton} provides a pinwheel skeleton. The stem of $Q$ is the only interior edge not contained in an arm; it lies in one region, which it divides into two pieces, while the other two regions are single pieces. By Corollary~\ref{cor:convex}(b), the stem is a parallel cut of its region; this is (B). The two forms are disjoint, because only in (A) does a piece have long base $n$. \end{proof} \begin{remark}\label{rem:A389392} Theorem~\ref{thm:k4} is exactly the exhaustiveness statement that the constructive description of Categories~A and~B in OEIS A389392 takes for granted, and Theorem~\ref{thm:k3} is a complete proof of the pinwheel lemma. Only Sections~\ref{sec:local}--\ref{sec:k34} are needed for this purpose. \end{remark}