A Short Proof to Defant and Kravitz’s theorem on the Length of Hitomezashi Loops

Qiuyu Ren Department of Mathematics, University of California, Berkeley, Berkeley, CA 94720, USA [email protected] and Shengtong Zhang Department of Mathematics, Stanford University, Stanford, CA 94305, USA [email protected]

Abstract.

We provide a shorter proof to Defant and Kravitz’s theorem (arXiv:2201.03461, Theorem 1.2) on the length of Hitomezashi loops modulo 8.

1. Introduction

Hitomezashi, a type of Japanese style embroidery, has recently attracted attention due to its interesting mathematical properties. We refer the reader to [1] and [2] for great surveys on the topic.

Following Section 1 of [1], we abstract the stitch patterns in a Hitomezashi artwork with graph-theoretic language.

Definition 1.1.

Consider the graph $\mathsf{Cloth}_{\mathbb{Z}}$ on $\mathbb{Z}\times\mathbb{Z}$ with $(i,j)$ adjacent to $(i,j\pm 1)$ and $(i\pm 1,j)$ . A Hitomezashi pattern is a subgraph of $\mathsf{Cloth}_{\mathbb{Z}}$ defined by two infinite sequences $\epsilon,\eta\in\{0,1\}^{\mathbb{Z}}$ , with edge set

\{\{(i,j),(i+1,j):i\equiv\eta_{j}\bmod{2}\}\bigcup\{\{(i,j),(i,j+1)\}:j\equiv\epsilon_{i}\bmod{2}\}.

A Hitomezashi loop is a cycle in a Hitomezashi pattern. A Hitomezashi path is a path in a Hitomezashi pattern. In this paper, all cycles and paths have an orientation.

In [1], Defant and Kravitz obtained the following beautiful result about the length of the loop.

Theorem 1.2 ([1], Theorem 1.2).

Every Hitomezashi loop has length congruent to $4$ modulo $8$ .

Refer to caption — Figure 1. Part of a Hitomezashi pattern. The $\{0,1\}$ -labels denote values of $\epsilon$ and $\eta$ on each horizontal and vertical line. The red edges form a Hitomezashi loop, while the green edges form a Hitomezashi path. Note the red loop has length $20$ , congruent to $4$ modulo $8$ .

Their proof uses a complicated induction scheme, relying on additional structural results about the loop in [3]. Given the simplicity of the theorem statement, we believe a shorter proof would be of interest.

In this paper, we present a two-page, self-contained proof of Theorem 1.2. Our main innovation is to induct on a different class of objects we call “Hitomezashi excursions”. This avoids many of the technical difficulties in [1], which inducts on Hitomezashi loops.

2. The proof

We first collect some simple lemmata.

Lemma 2.1.

On a Hitomezashi path, the edges starting at $(i,j)$ and $(i^{\prime},j^{\prime})$ are parallel if and only if $i+j\equiv i^{\prime}+j^{\prime}\bmod{2}$ .

Proof.

Consecutive edges on the path are orthogonal and have different parity of $i+j$ . ∎

Lemma 2.2 ([1], Proposition 2.3).

Let $\mathcal{C}$ be a Hitomezashi path. Then all edges of $\mathcal{C}$ on a vertical line $x=a$ have the same direction, and the $y$ -coordinates of their starting vertices have the same parity.

Proof.

Let $y_{1}$ and $y_{2}$ be the starting $y$ -coordinates of two such edges. By Lemma 2.1, we have $y_{1}\equiv y_{2}\bmod{2}$ . The parities of $y_{i}$ determine the direction of the corresponding edges, so the lemma holds. ∎

We also need the following topological observation. Let $\mathcal{H}_{a}$ denote the half plane $\mathcal{H}_{a}:=\{(x,y):x\geq a\}$ .

Lemma 2.3.

Suppose two continuous paths in $\mathcal{H}_{a}$ , one connecting $(a,y_{1})$ and $(a,y_{3})$ and the other connecting $(a,y_{2})$ and $(a,y_{4})$ , are disjoint. Then we cannot have $y_{1}\leq y_{2}\leq y_{3}\leq y_{4}$ .∎

We now introduce the “excursion”. See Figure 2 for a visualization.

Definition 2.4.

Let $a$ be an integer. A (Hitomezashi) $a$ -excursion is a Hitomezashi path with at least three vertices, whose start and end vertices lie on the vertical line $x=a-1$ , and all other vertices lie in $\mathcal{H}_{a}$ .

Induction on excursions is much easier than induction on loops, as we illustrate in the next lemma.

Lemma 2.5.

The length of an $a$ -excursion from $(a-1,i)$ to $(a-1,j)$ is congruent to $2\left|j-i\right|+1$ modulo $8$ .

Proof.

Consider such an excursion $\mathcal{C}$ . Let $\left|\mathcal{C}\right|$ denote its length. We argue by induction on $\left|\mathcal{C}\right|$ . When $\left|\mathcal{C}\right|=3$ , we must have $\left|j-i\right|=1$ , so the result holds trivially.

Suppose the result holds for all excursions with smaller length than $\mathcal{C}$ . Reversing the orientation of $\mathcal{C}$ and switch $i,j$ if necessary, assume $i<j$ . Let $i=y_{0},y_{1},\cdots,y_{t}$ be the starting $y$ -coordinate of the edges of $\mathcal{C}$ lying on the vertical line $x=a$ , in the order they appear when traversing $\mathcal{C}$ . By Lemma 2.2, we have

(1)

i\equiv y_{\ell}\equiv j+1\bmod 2,\forall 0\leq\ell\leq t.

and all edges of $\mathcal{C}$ on the vertical line $x=a$ are in the same direction. We split into two cases.

Case 1: They point in the positive $y$ -direction. In this case, for each $\ell\in[t-2]$ , the excursion $\mathcal{C}$ contains disjoint paths $(a,i+1)\to(a,y_{\ell})$ , $(a,y_{\ell}+1)\to(a,y_{\ell+1})$ , and $(a,y_{\ell+1}+1)\to(a,j)$ , all lying $\mathcal{H}_{a}$ and are disjoint. By Lemma 2.3, we must have

i<y_{\ell}<y_{\ell+1}<j.

Thus we have

i=y_{0}<y_{1}<\cdots<y_{t}=j-1.

Case 2: They point in the negative $y$ -direction. In this case, let $s$ be the smallest integer in $[t]$ such that $y_{s-1}<y_{s}$ . Then clearly $y_{s-1}<y_{s-2}<\cdots<y_{0}.$ For any $i\in[t-1]$ with $i>s$ , $\mathcal{C}$ contains disjoint paths $(a,y_{s-1}-1)\to(a,y_{s})$ and $(a,y_{s}-1)\to(a,y_{i})$ lying in $\mathcal{H}_{a}$ . By Lemma 2.3, we must have $y_{s-1}<y_{i}<y_{s}$ . Furthermore, $\mathcal{C}$ contains disjoint paths $(a,y_{s}-1)\to(a,y_{i})$ and path $(a,y_{i}-1)\to(a,y_{i+1})$ lying in $\mathcal{H}_{a}$ . Thus, we must have $y_{i+1}<y_{i}$ . To summarize, we have

y_{s-1}<\cdots<y_{0}=i<y_{t}=j+1<y_{t-1}<\cdots<y_{s}.

We partition $\mathcal{C}$ by the $(t+1)$ edges starting at $(a,y_{i})(0\leq i\leq t)$ . Removing these edges, $\mathcal{C}$ is partitioned into the edges $(a-1,i)\to(a,i)$ , $(a,j)\to(a-1,j)$ , and $(a+1)$ -excursions $\mathcal{C}_{i}(i\in[t])$ . Furthermore, each $\mathcal{C}_{i}$ has strictly smaller length than $\mathcal{C}$ , so they satisfy the induction hypothesis. We have

\left|\mathcal{C}\right|=3+t+\sum_{\ell=1}^{t}\left|\mathcal{C}_{\ell}\right|.

We now consider the two cases above. In Case 1, $\mathcal{C}_{\ell}$ is an excursion from $(a,y_{\ell-1}+1)$ to $(a,y_{\ell})$ , so we have $\left|\mathcal{C}_{\ell}\right|\equiv 2\left|y_{\ell}-y_{\ell-1}-1\right|+1\equiv 2(y_{\ell}-y_{\ell-1})-1\bmod{8}.$ Thus

\left|\mathcal{C}\right|\equiv 3+t+\sum_{\ell=1}^{t}(2(y_{\ell}-y_{\ell-1})-1)\equiv 3+2(y_{t}-y_{0})\equiv 2(j-i)+1\bmod{8}.

In Case 2, $\mathcal{C}_{\ell}$ is an $(a+1)$ -excursion from $(a,y_{\ell-1}-1)$ to $(a,y_{\ell})$ , so for any $\ell\in[t]$ ,

\left|\mathcal{C}_{\ell}\right|\equiv 2\left|y_{\ell}-y_{\ell-1}+1\right|+1\equiv\begin{cases}2(y_{\ell}-y_{\ell-1})+3,\ell=s\\ 2(y_{\ell-1}-y_{\ell})-1,\ell\neq s\end{cases}\bmod{8}.

Thus

\left|\mathcal{C}\right|\equiv 3+t+(2(y_{s}-y_{s-1})+3)+\sum_{\ell\neq s,\ell\in[t]}(2(y_{\ell-1}-y_{\ell})-1)\equiv 4y_{s}-4y_{s-1}-2j+2i+5\bmod{8}.

By (1), we have $y_{s}-y_{s-1}\equiv 0\bmod{2}$ and $i-j\equiv 1\bmod{2}$ , so

\left|\mathcal{C}\right|\equiv 2(j-i)+1\bmod{8}.

In both cases, the induction hypothesis holds for $\mathcal{C}$ , so the induction step is complete. ∎

Proof of Theorem 1.2.

Consider a Hitomezashi Loop $\mathcal{L}$ . Let $a=\min_{(x,y)\in\mathcal{L}}x$ . By Lemma 2.2, we can orient $\mathcal{L}$ such that all edges lying on $x=a$ point downward. Let $y_{0},\cdots,y_{t-1}$ be the $y$ -coordinates of the starting vertices of edges of $\mathcal{L}$ lying on the vertical line $x=a$ , in the order they appear when traversing $\mathcal{L}$ , with $y_{0}$ being the largest among them. Define $y_{t}=y_{0}$ .

For each $i\in[t-2]$ , $\mathcal{L}$ contain disjoint paths $(a,y_{0}-1)\to(a,y_{i})$ and $(a,y_{i}-1)\to(a,y_{i+1})$ lying in $\mathcal{H}_{a}$ . Since $y_{i},y_{i+1}$ are less than $y_{0}$ , we must have $y_{i+1}<y_{i}$ by Lemma 2.3. Thus $y_{0}>y_{1}>\cdots>y_{t-1}$ .

Removing the $t$ edges on $x=a$ , $\mathcal{L}$ is divided into $(a+1)$ -excursions $\mathcal{C}_{i}$ from $(a,y_{i-1}-1)$ to $(a,y_{i})$ for $i\in[t]$ . By Lemma 2.5, we have

	$\displaystyle\left\|\mathcal{L}\right\|$	$\displaystyle=t+\sum_{i=1}^{t}\left\|\mathcal{C}_{i}\right\|\equiv t+\sum_{i=1}^{t}(2\left\|y_{i-1}-1-y_{i}\right\|+1)$
		$\displaystyle\equiv t+\sum_{i=1}^{t-1}(2y_{i-1}-2y_{i}-1)+(2y_{0}-2y_{t-1}+3)$
		$\displaystyle\equiv 4(y_{0}-y_{t-1})+4\bmod{8}.$

By Lemma 2.1, all $y_{i}$ ’s have the same parity. So $\left|\mathcal{L}\right|$ is congruent to $4$ modulo $8$ . ∎

Acknowledgement

Shengtong Zhang is supported by the Craig Franklin Fellowship in Mathematics at Stanford University.

References

[1] Colin Defant and Noah Kravitz. Loops and regions in hitomezashi patterns, arxiv:2201.03461, 2022.
[2] B. Haran [Numberphile]. Hitomezashi stitch patterns – numberphile, Youtube Video, 2021.
[3] Gábor Pete. Corner percolation on $\mathbb{Z}^{2}$ and the square root of 17. The Annals of Probability, 36(5), 2008.