Stitching Superpermutations

Year: 2023 Authors: Emily Dennett

Core claim

Superpermutations can function as intentional design elements for fiber art, producing symmetrical knitting and cross-stitch works.

Topics

superpermutations, knitting patterns, cross-stitch design, symmetry, fiber art

Domains

combinatorics, permutations, superpermutations, sequence construction, fiber art, textile design, knitting, cross-stitch

Methods

pattern permutation, recursive construction, grid visualization, laser cutting

Media

yarn, stitch patterns, wood boards, laser cutter

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2023 Conference Proceedings

Stitching Superpermutations

Emily Dennett

Upper School Mathematics, Columbus Academy, Ohio, USA; dennette@columbusacademy.org

Abstract

In this paper, I discuss my explorations in generating new knitting and cross-stitch patterns using superpermutations. The palindromic nature of the minimum superpermutations for $n=3$ and $n=4$ lead to a natural symmetry in the resulting patterns. I share two ways that I used superpermutations to generate new patterns.

The Search for New Patterns

As a fiber artist, I can spend hours looking through pattern libraries. Books such as Barbara Walker’s A Treasury of Knitting Patterns [6] contain thousands of stitch patterns that knitters can use to design garments. As a knitter, I’m thrilled by the idea of the sheer number of designs that could be created by using combinations of the motifs offered in these libraries. As a mathematician, however, I wondered how the patterns contained in these libraries could be used to generate even more patterns.

One way of creating new patterns from ones that were already in the library that seemed like an obvious choice was to permute the order that the rows of the pattern were knitted. For example, consider the fair isle knitting heart motif shown in figure 1a. The rows can be permuted to create the designs shown in Figures 1b -1d.

(a)

(b)

(c) Figure 1: Four permutations of a four row knitting motif. While these are all cyclic permutations, other permutations will be considered as well.

(d)

I quickly realized that not all permutations of a pattern would create a new design that I was interested in using in a knitting project. I also realized that knitting each of the permuted patterns could be quite cumbersome. A stitch design with $n$ rows would have $n!$ permutations and so it would take $n\cdot n!$ rows of knitting to see each of the permutations. For example, even a small 4-row heart would require 96 rows of knitting.

I began to scheme about how I could “stack” the permutations to save myself time. For example, if I knit the first pattern as shown in figure 1a and then knit the first row again, in those 5 rows of knitting I would be able to see two different permutations (Figure 1a and Figure 1b), saving myself three rows of knitting. In essence, I wanted the best of both worlds. I wanted to see each of the $n!$ permutations while knitting the fewest number of rows. It turns out, the sequence of rows I wanted to knit already existed in the mathematics literature and is known as a superpermutation!

Superpermutations

A superpermutation on $n$ symbols is a string that contains each of the $n!$ permutations of the $n$ symbols in a contiguous substring [3]. A recent area of mathematical research has been looking to determine the

Dennett

minimum length of a superpermutation on $n$ symbols. Minimal superpermutations for $n=1,2,3$ can be found easily through inspection (Table 1).

Table 1: Minimal Superpermutations for $n=1,2,3$

Daniel Ashlock and Jenett Tillotson published a way to construct superpermutations recursively [2]. The superpermutations that their construction method yields are palindromic, which furthered my interest in using them for artistic purposes. The superpermutations that their method constructs for $n=4$ and $n=5$ can be seen in Table 2.

Table 2: Minimal Superpermutations for $n=4$ and $n=5$

Ashlock and Tillotson [2] conjectured that the length of a minimal superpermutation on $n$ symbols was ${\sum }_{i=1}^{n}i!$ and that these minimal superpermutations were unique up to a renaming of the symbols. While this result holds true for $n\le 4$ , Ben Chaffin found that for $n=5$ , the formula provides the correct length of the minimal superpermutation, but that there are eight minimal superpermutations. Counterexamples for the minimum length proposed by Ashlock and Tillerson have been found for $n=6$ and $n=7$ [1]. The minimal length for superpermutations for $n\ge 6$ is an open question.

To celebrate the discovery of a superpermutation on seven symbols of length 5,906, Matt Parker released a video that included an audio representation of the superpermutation where each symbol was represented by one note of an octave [5]. However, I was unable to find any previous work that visualized a superpermutation other than by listing digits.

Creating a New Pattern Using a Superpermutation

After reading about Ashlock and Tillotson’s [2] construction of superpermutations, I was no longer interested in using a superpermutation to save time in visualizing each permutation of a pattern, I was now interested in using a superpermutation as an intentional design element.

A consideration when designing a piece of knitting using a superpermutation was the size of the finished object and the number of rows that would be used to create the two-color design on the finished piece. Since superpermutation lengths grow quickly as $n$ increases, the number of knitted rows for n > 6 would be much greater than is reasonable for most knitted items.

Another design consideration when using knitted rows to represent elements that will be permuted is that I wanted each row of the base motif to be distinct. Since each row would represent one of the symbols in the permutation, if two of them were identical then it would not be possible to discern from the finished design which symbol was being represented by some rows.

I decided to knit a hat with a superpermutation of the heart motif that is seen in Figure 1a repeated around the hat. I appreciated that the heart itself had a vertical line of symmetry, while the resulting design from the palindromic nature of the superpermutation has a horizontal line of symmetry. One repetition of

Stitching Superpermutations

the design, created by forming the minimal superpermutation on the rows of the heart motif and the completed hat, are shown in Figure 2.

Figure 2: One repetition of a design created using a superpermutation and the resulting knitted item

Superpermutation Squares

To push the idea of using superpermutations to create designs further, I decided I wanted to create a design based upon a square grid where each row and column of the grid represented a superpermutation. As discussed earlier, for $n\le 4$ , there is a unique minimal superpermutation up to renaming. Therefore, to create such a grid, I created minimal superpermutations that began with each digit by renaming the elements of the superpermutation. The resulting grid of digits for $n=3$ and $n=4$ are shown below in Figure 3.

Figure 3: Grids where each row and column is a superpermutation for $n=3$ and $n=4$ .

To create a design based upon these grids, that resulted in a final product that was also square, each digit needed to be represented by a square of stitches. While each digit could be represented in numerous ways, each resulting in a different final design, I chose to represent 1 by a vertical 1-by- $n$ rectangle, 2 by a vertical 2-by- $n$ rectangle, or $k$ by a vertical $k$ -by- $n$ rectangle. Figure 4 shows the visual representation of the digits for $n=4$ .

Dennett

Figure 4: Visual representations of the digits 1, 2, 3, and 4 in a 4-by-4 block

I wanted to see the resulting patterns for both $n=3$ and $n=4$ on the same scale, which was difficult to do through knitting due to their vastly different dimensions. Instead, I used a laser cutter to create a 28-by-28 grid and a 133-by-133 grid on two pieces of wood. I then cross-stitched the designs onto the board. The resulting pieces of art are shown in Figure 5.

Summary and Conclusions

I really enjoyed this exploration of using superpermutations to create new designs for fiber art projects and the art that resulted. There are still several avenues that could be explored in this area. For example, in what other ways can digits be represented? For $n\ge 5$ , can a superpermutation square be created that uses more than one of the distinct minimal superpermutations?

References

[1] Anonymous 4chan Poster, R. Houston, J. Pantone, and V. Vatter, “A lower bound on the length of the shortest superpattern.” Oct. 25, 2018, https://oeis.org/A180632/a180632.pdf [2] D. Ashlock and J. Tillotson. “Construction of small superpermutations and minimal injective superstrings.” Congressus Numerantium, 1993, pp. 91 - 98. [3] R. Houston. “Tackling the Minimal Superpermutation Problem.” Aug. 22, 2014, https://arxiv.org/abs/1408.5108 [4] N. Johnston. “All minimal superpermutations on five symbols have been found”, 2014, http://www.njohnston.ca/2014/08/all-minimal-superpermutations-on-five-symbols-have-been-found/ [5] M. Parker. “New superpermutations discovered!” Mar. 11, 2019, https://www.youtube.com/watch?v=_tpNuulTeSQ [6] B. Walker. A Treasury of Knitting Patterns. Schoolhouse Press, 1998.