Circular Super patterns and Zigzag constructions M Hariprasad , Raisa Dsouza Abstract Abstract: In this article, we introduce the notion of a circular k -superpatterns, permutations that contain all k length patterns upto rotation equivalence. We present a construction of circular superpattern using the linear (k-1) superpattern, explicitly giving the upper bound on the length. Motivated by the zigzag framework of Engen and Vatter, we adapt and simplify their score function to the circular setting and analyze its parity properties. For odd k we propose a candidate zigzag construction for circular superpattern supported by computational evidence for small k . Keywords: Permutations, Patterns, Super patterns AMS Classification: 05A05, 05A15, 68R05 1 Introduction The question ”What is the smallest length of a pattern that contains all patterns of length k ?” has been asked in different contexts: by Knuth et al in 1972 [ 5 ] , by Chung et al in 1992 [ 4 ] , by Ashlock and Tillotson in 1993 [ 2 ] and by Arratia in 1999 [ 1 ] . Arratia established an equivalence between two versions of the Stanley and Wilf conjecture on pattern avoidance. As a closely related but complementary problem, he also studied pattern containment and constructed a permutation of length k^{2} that contains all k -patterns, establishing an upper bound for the length, L_{k} , of such permutations. He also conjectured that assymptotically, L_{k}\sim\left(\dfrac{k}{e}\right)^{2} . Patterns that contain every length k permutation are called k -super patterns. The problem of constructing smaller superpatterns has attracted attention as a fundamental question in pattern containment. In 2007, Errikson et al [ 7 ] , showed that \left(\dfrac{k}{e}\right)^{2}\leq L_{k}\leq\left[\dfrac{2}{3}+O(1)\right]k^{2} and further conjectured that L_{k}\sim\dfrac{k^{2}}{2} . In 2009, Miller [ 9 ] gave a simple construction that showed that L_{k}\leq\dfrac{k(k+1)}{2} , lending some evidence to the conjecture by Errikson et al. In 2021, Engen and Vatter [ 6 ] proposed a construction of length \left\lceil\dfrac{k^{2}+1}{2}\right\rceil using an infinite zigzag word. They proved that every k -pattern is either a layered permutation or a distant inverse permutation , and gave embeddings of both types into the zigzag pattern. Their work revealed striking structural regularities in the space of permutations. Superpatterns containing layered permutations were also studedied by Gray [ 8 ] . An improved lower bound for L_{k} was given by Chroman et al [ 3 ] and they extended their approach to other universal type problems. In this article, we introduce the notion of a circular k -superpattern , which is effectively, a permutation written on a circle, where patterns are considered equivalent up to rotation. We present a simple construction that converts a linear (k-1) -superpattern into a circular k -superpattern, yielding an explicit upper bound on its length. We also simplify the score function of Engen and Vatter and extend it to the circular setting. Finally, we propose a zigzag parity construction that appears to generate circular superpatterns for odd k , and we verify this conjecture computationally for small values of k . The organization of the paper is as follows. Section 2 reviews background and notation. Section 3 presents the construction of a circular k -superpattern from a linear superpattern. Section 4 introduces the zigzag construction and parity-based score function. Section 5 states a conjecture and discusses open problems. 2 Background and Notations Let [n]=\{1,2,\dots,n\} , and let \mathbf{S}_{n} denote the set of all permutations on [n] . In this article, we are interested in permutations in their one-line notation; that is, a permutation \pi of \{1,2,\dots,n\} is written as \pi=(\pi_{1},\pi_{2},\dots,\pi_{n}) . Here \pi_{j} denotes the j -th element of \pi . To improve readability and avoid nested subscripts, when the index itself has a subscript (for example, j_{k} ), we use parentheses and write \pi(j_{k}) instead of \pi_{j_{k}} . This notation is used consistently throughout the paper. For a subset J=\{i_{1}k+1 suffices for constructions of length- k patterns. This zigzag sequence will form the basis for the constructions developed in the following sections. For a pattern \sigma=\sigma_{1}\sigma_{2}\cdots\sigma_{k} we denote the sequence \sigma^{+}=\sigma_{1}+1,\sigma_{2}+1,\cdots,\sigma_{k}+1 . The upperbounds we prove are summarized as Table 1 . Table 1: Upper bounds for k -cyclic superpattern length Over alphabet [k+1] Over permutations Length \displaystyle\frac{(k-1)(k+1)}{2} \displaystyle\Big\lceil\frac{k^{2}+1}{2}\Big\rceil+1 3 Circular k -superpatterns using linear k-1 superpattern In this section we construct a circular k -superpattern from a linear (k-1) -superpattern. This yields the general upper bound L_{\mathrm{circ}}(k)\leq L(k-1)+1. A numerical example at the end shows that this bound is not always tight. Theorem 3.1 . Let k\geq 2 . If \pi=(\pi_{1},\pi_{2},\dots,\pi_{L}) is a linear (k-1) -superpattern, then the permutation \gamma=(\,L+1,\;\pi_{1},\pi_{2},\dots,\pi_{L}\,) is a circular k -superpattern: every cyclic equivalence class of permutations of length k contains a representative that appears as an order-isomorphic subsequence of \gamma . Consequently, L_{\mathrm{circ}}(k)\leq L(k-1)+1. Proof. Write \gamma=(\gamma_{0},\gamma_{1},\dots,\gamma_{L}),\qquad\gamma_{0}=L+1,\;\gamma_{i}=\pi_{i}\ (1\leq i\leq L). Let \sigma\in\mathbf{S}_{k} be arbitrary. Every cyclic equivalence class contains a unique rotation whose first symbol is k , so there exists r such that \rho_{r}(\sigma)=(\,k,\,\tau_{1},\tau_{2},\dots,\tau_{k-1}\,), where \tau=(\tau_{1},\dots,\tau_{k-1})\in\mathbf{S}_{k-1} . Since \pi is a (k-1) -superpattern, there exist indices J^{\prime}=\{1\leq i_{1}\pi_{i_{t}}\qquad\text{for all }t, so the first element of \gamma|_{J} is the unique maximum, just as k is the unique maximum in \rho_{r}(\sigma) . The remaining entries of \gamma|_{J} are order-isomorphic to \tau . Therefore, \gamma|_{J} is order isomorphic to \rho_{r}(\sigma). Since \sigma was arbitrary, \gamma contains a representative of every cyclic equivalence class of \mathbf{S}_{k} and is therefore a circular k -superpattern. Finally, \gamma has length L+1 , so L_{\mathrm{circ}}(k)\leq L(k-1)+1. ∎ Remark 3.2 . Using the Engen–Vatter bound [ 6 ] for L(k-1) gives the explicit inequality, L_{\mathrm{circ}}(k)\;\leq\;\left\lceil\frac{(k-1)^{2}+1}{2}\right\rceil+1\;=\;\left\lceil\frac{k^{2}-2k+4}{2}\right\rceil. Example 3.3 . For k=4 , exhaustive search confirms that the minimal circular 4 -superpattern has length 6 , consistent with Theorem 3.1 . For k=5 , the permutation, (846271359) is a circular 5 -superpattern of length 9 , while the theorem gives L_{\mathrm{circ}}(5)\leq 10 . Thus the construction is close to optimal but not tight in this case. 4 Exact subsequence containment in Zigzag words We revisit the zigzag construction of Engen and Vatter [ 6 , Prop. 10] , presenting a streamlined formulation adapted to the circular framework. Our focus is the direct embedding of permutation patterns within finite zigzag words, emphasizing exact containment rather than order-isomorphic subsequences. Let \sigma\in\mathbf{S}_{k} be arbitrary. We examine its placement as a subsequence of \mathrm{zz}(m,q) , where (m,q) denote the number of runs and the alphabet width, respectively. We re-derive proposition 10 of Engen and Vatter that: For every \sigma\in\mathbf{S}_{k} , either \sigma or \sigma^{+} occurs as an exact subsequence of \mathrm{zz}(k,k+1) . Consequently, we prove that for odd k , For every \sigma\in\mathbf{S}_{k} , either \sigma or \sigma^{+} occurs as an exact cyclic subsequence of \mathrm{zz}(k-1,k+1) . 4.1 Parity and local cost. For each x\in\{1,2,\dots,q\} define its parity sign p_{x}=\begin{cases}\phantom{-}1,&\text{if $x$ is even},\\[3.0pt] -1,&\text{if $x$ is odd.}\end{cases} For x,y\in\{1,\dots,q\} the local cost C_{xy} quantifies how many additional zigzag runs are required to position the number y after x . It is defined by C_{xy}=\begin{cases}-1&\text{no additional run is required to position $y$ after $x$,}\\[3.0pt] \phantom{-}0&\text{one additional run is required to position $y$ after $x$,}\\[3.0pt] \phantom{-}1&\text{two additional runs are required to position $y$ after $x$.}\end{cases} Lemma 4.1 . For x,y\in\{1,\dots,q\} , the local cost function is given by C_{xy}=\delta_{xy}-\frac{(p_{x}p_{y}+1)}{2}\,\operatorname{sgn}(x-y)\,p_{x}, (4.1) where \operatorname{sgn}(t) denotes the sign of t . Proof. We verify that the right-hand side of ( 4.1 ) reproduces the required values of C_{xy} in each parity and order case. 1. Same parity, and y lies in the same run as x . If x,y are both odd and y>x , the zigzag order places y in the same run as x . Then p_{x}p_{y}=1 , \operatorname{sgn}(x-y)=-1 , and the right-hand side becomes \delta_{xy}-\frac{(1+1)}{2}(-1)p_{x}=0-(1)(-1)(-1)=-1, matching C_{xy}=-1 . The same argument holds when x,y are both even and yx , we obtain C_{xy}=1 . 4. The case x=y . Since a symbol cannot follow itself within the same zigzag pass, placing y=x again requires two additional runs. In this case \delta_{xy}=1 and \operatorname{sgn}(0)=0 , so C_{xx}=1-0=1 , as required. This covers all parity and ordering possibilities, establishing the formula. ∎ Definition 4.2 (Score function) . The score of a permutation, \sigma\in S_{k} is the minimum number of runs in a zigzag word containing \sigma minus the length of \sigma . Lemma 4.3 . For a permutation \sigma=(\sigma_{1},\sigma_{2},\dots,\sigma_{k}) , its score is given by the formula, S(\sigma)=\sum_{i=1}^{k-1}C_{\sigma_{i}\sigma_{i+1}}+C_{\cdot,\,\sigma_{1}}, (4.2) where the initial term is C_{\cdot,\,x}=\frac{1+p_{x}}{2}. Proof. Place the symbols of \sigma one by one, in the given order, using the following greedy rule: when placing the next symbol, place it in the earliest run (counting forward in the zigzag sequence) that preserves the relative order and parity constraints; if no such position in the current or immediately following run is possible, open additional runs as needed. By the definition of C_{\cdot,\sigma_{1}} , the greedy procedure requires exactly C_{\cdot,\sigma_{1}} extra runs before placing \sigma_{1} (this accounts for whether the first available run can accept \sigma_{1} or whether an additional run must be inserted first). After \sigma_{1} is placed, when we place \sigma_{2} the number of extra runs that the greedy procedure must open is by definition C_{\sigma_{1}\sigma_{2}} . Proceeding inductively, the greedy placement opens exactly C_{\sigma_{i}\sigma_{i+1}} extra runs when placing \sigma_{i+1} after \sigma_{i} . Therefore the total number of extra runs opened by this construction equals C_{\cdot,\sigma_{1}}+\sum_{i=1}^{k-1}C_{\sigma_{i}\sigma_{i+1}}. Since each symbol occupies one position in some run, the total number of runs used by this construction is k+\biggl(C_{\cdot,\sigma_{1}}+\sum_{i=1}^{k-1}C_{\sigma_{i}\sigma_{i+1}}\biggr). (4.3) The local costs are computed by using the parity and do not depend on choices made elsewhere. Hence, we can say that the minimum number of runs required to space \sigma is ( 4.3 ). This establishes, equation ( 4.2 ). ∎ Remark 4.4 . The sign convention follows that of Engen and Vatter, but omits the terms associated with repeated symbols, which do not occur in permutations. Lemma 4.5 ( Lift identity ) . S(\sigma)+S(\sigma^{+})=1 . Proof. For permutations, the local costs satisfy C_{x+1,\,y+1}=-\,C_{xy},\qquad C_{\cdot,\,x+1}=\frac{1-p_{x}}{2}. Consequently, S(\sigma^{+})+S(\sigma)=1. ∎ Theorem 4.6 . [ 6 , Proposition 10] For every permutation \sigma\in\mathbf{S}_{k} , either \sigma or \sigma^{+} occur as an exact subsequence of zz(k,k+1) . Proof. Let R(\sigma) be the minimum number of runs needed to place \sigma in a zigzag word. Then R(\sigma)=k+S(\sigma) and R(\sigma^{+})=k+S(\sigma^{+}). From the lift identity, we can conclude that either one of the scores is less than or equal to zero. That implies either \sigma or \sigma^{+} occur as subsequence of zz(k,k+1) . ∎ 1 3 4 2 1 3 4 2 Figure 1: zz(4,4) 1 3 5 4 2 1 3 5 4 2 1 3 5 Figure 2: zz(5,5) 4.2 Circular Score function We now extend the concept of the local cost to the circular superpattern setting and prove an analog of Theorem 4.6 in context. For a cyclic equivalence class of a permutation, define the local circular cost of placing elements in the zigzag word as in Section 4.1 : C_{xy}=\delta_{xy}-\frac{(p_{x}p_{y}+1)}{2}\,\operatorname{sgn}(x-y)\,p_{x}. Here, the cost of placing the first element is taken with respect to the last element, i.e., C_{\cdot,\sigma(1)}=C_{\sigma(k),\sigma(1)}. The circular score of the permutation \sigma is then defined by S^{c}(\sigma)=\sum_{i=1}^{k}C_{\sigma(i),\,\sigma((i+1)\bmod k)}. Any cyclic shift of \sigma preserves the multiset of consecutive pairs, and hence S^{c}(\sigma) is invariant under rotation. Lemma 4.7 ( Circular lift identity ) . For a permutation \sigma\in S_{k} , we have S^{c}(\sigma)+S^{c}(\sigma^{+})=0 . Proof. Since C_{(x+1)\bmod k,(y+1)\bmod k}=-C_{x,y} , we have S^{c}(\sigma^{+})=-S^{c}(\sigma) which gives us the desired identity. ∎ Lemma 4.8 . For odd k and a permutation \sigma\in S_{k} , S^{c}(\sigma)\neq 0 . Proof. Suppose, for contradiction, that S^{c}(\sigma)=0 . Then, by the circular lift identity, we also have S^{c}(\sigma^{+})=0 . The score depends only on consecutive pairs (x_{i},x_{i+1}) (with indices taken modulo k ) and on their parities p_{x_{i}}\in\{\pm 1\} . Let \xi_{i}=p_{x_{i}}p_{x_{i+1}},\qquad 1\leq i\leq k. If a consecutive pair has opposite parity, then \xi_{i}=-1 and C_{x_{i}x_{i+1}}=0 . If the pair has the same parity, then \xi_{i}=1 and C_{x_{i}x_{i+1}}=\pm 1 . Since S^{c}(\sigma)=0 , the positive and negative contributions to the score must cancel. This forces the number of zero-cost transitions (i.e., those with p_{x_{i}}p_{x_{(i+1)\bmod k}}=-1) ) to be odd. Consequently, \prod_{i=1}^{k}p_{x_{i}}p_{x_{(i+1)\bmod k}}=-1. On the other hand, by rearranging terms, we can write \prod_{i=1}^{k}\xi_{i}=\prod_{i=1}^{k}p_{x_{i}}p_{x_{i+1\bmod k}}=\prod_{i=1}^{k}p_{x_{i}}^{2}=1, since p_{x_{i}}^{2}=1 for all i . This is a contradiction. ∎ When k is even, a permutation \sigma\in S_{k} , having an alternating parity sequence (\text{even},\text{odd},\text{even},\text{odd},\dots) , yields S^{c}(\sigma)=0 . Theorem 4.9 . For k odd, every permutation \sigma of length k , or \sigma^{+} occurs as an exact subsequence of \mathrm{zz}(k-1,k+1) , up to cyclic permutation. Proof. Using the circluar lifting identity and the fact that S^{c}(\sigma)\neq 0 for odd k we have, S(\sigma)\leq-1\quad\text{or}\quad S(\sigma^{+})\leq-1. Therefore, either \sigma or \sigma^{+} can be placed using at most k-1 runs, which implies that it occurs as a subsequence of \mathrm{zz}(k-1,k+1) . ∎ 4.2.1 Even k case: When k is even, consider zz(k-1,k+1) . The C_{\cdot,x} argument no longer holds because the zigzag pattern is not symmetric (that is, the number of runs is odd). Therefore in this case we prove a weaker theorem than Theorem 4.9 . Theorem 4.10 . For k even, every pattern of length k occurs as an order isomorphic circular subsequence of zz(k-1,k+1) . Proof. Given any \sigma\in\mathbf{S}_{k} , consider its rotation \rho_{r}(\sigma) such that the last element is k . Identify k with the last element of zz(k-1,k+1) , that is k+1 . Let \tau=\rho_{r}(\sigma)|_{1:k-1} (the first k-1 elements of rotated permutation). Then \tau\in\mathbf{S}_{k-1} . From the Theorem 4.6 , either \tau or \tau^{+} occurs as an exact subsequence of zz(k-1,k) up to cyclic permutation. But, zz(k-1,k) is a subsequence of zz(k-1,k+1) . Therefore any \sigma has a rotation such that it occurs as a order isomorphic subsequence of zz(k-1,k+1) . ∎ 5 A construction for odd circular superpattern In this section, we give a construction to create an odd circular superpattern. We first recall the method (called breaking ties ) given by Engen and Vatter [ 6 ] to obtain a permutation from the corresponding zigzag word. For ease of notation, let \omega=zz(m,n) . The procedure of breaking ties is as follows: • We first view the zigzag word \omega in the (X,Y) -plane, as illustrated in Figures 1 and 2 . In this representation, each element \omega_{i} corresponds to the point (i,\omega_{i}) . • We refer to the Y -coordinates as levels . Starting from the rightmost element in the lowest level, we traverse each level from right to left. If the first element encountered in this traversal is (s,\omega_{s}) , we assign \zeta_{s}=1 . • More generally, if the j -th element visited in this traversal is (g,\omega_{g}) , then we assign \zeta_{g}=j . • Once all elements at one level are processed, we proceed to the next higher level and repeat the traversal until all levels have been exhausted. This procedure yields the desired permutation \zeta . It is illustrated for zz(3,3) in Figure 3 . 1 3 2 1 3 1 3 2 1 3 \omega \Longrightarrow 2.0 2.0 2.0 2.0 2.0 2 5 3 1 4 \zeta Figure 3: zz(3,3) and corresponding \zeta Engen and Vatter proved that for odd n , \zeta is a superpattern. For even n , the permutation \zeta obtained from zz(n,n) appended with 1, is a k -superpattern. 5.1 An odd circular superpattern We will now use the method of breaking ties to construct a circular superpattern. Let k be an odd number and consider the zigzag word \omega=(zz(k-1,k-1),1) . The last two elements of \omega are (2,1) . We replace them by (k,k-1) . Let the resulting word be \omega^{\prime} . Let \gamma_{k} be the permutation obtained by \omega^{\prime} following the procedure of breaking ties . Example 5.1 . When k=5 , we have \omega=1\,3\,4\,2\,1\,3\,4\,2\,1,\qquad\text{ and }\qquad\omega^{\prime}=1\,3\,4\,2\,1\,3\,4\,5\,4. This results into the permutation, \gamma_{5}=(2,5,8,3,1,4,7,9,6) . It is experimentally verified that \gamma_{5} is a 5-circular superpattern. This construction is formalized in Theorem 1 . Before proving the main result, we introduce the notions of distant inverse-descent and layered permutations , which play a central role in the proof. Definition 5.2 . [ 6 , Distant inverse-descent] We say that two entries \pi(j) and \pi(k) of the permutation \pi form an inverse-descent if j3 be odd and let L be the length of the zigzag word \mathrm{zz}(k-1,k-1) . Construct the word, \mathrm{zzc}(k)=(zz(k-1,k-1)|_{1:L-2},k,k-1) by replacing the terminal (2,1) of \mathrm{zz}(k-1,k-1) by (k,k-1) . Let \gamma be the permutation obtained from \mathrm{zzc}(k) by the process of breaking ties. Then \gamma is a circular k -superpattern. proof outline: Let \sigma be a pattern rotated in such a way that \sigma(k)=k . • Then if \sigma(k-1)=1 and it is using the last run in the zz(k-1,k-1) , the only such possibility is a decreasing permutation. We can show that rotation of \sigma a decreasing permutation appears in \gamma . This is precisely done by the Lemma 5.6 . • If \sigma(k-1)=m where 2