🔢 mathematics

Circular Super patterns and Zigzag constructions

This paper introduces circular $k$ -superpatterns—permutations containing all length- $k$ patterns under rotation—and proposes a construction method and a potential zigzag-based framework for building them.

Original authors: Hariprasad Manjunath, Raisa Dsouza

Published 2026-02-11

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Hariprasad Manjunath, Raisa Dsouza

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef, and you have a collection of secret recipes. Each recipe is a specific sequence of ingredients—for example, "Salt, Pepper, Garlic, Onion."

In the world of mathematics, these recipes are called patterns. A superpattern is like a "Master Grocery List" that is so comprehensive that no matter which recipe you pick, you can find all its ingredients in the correct order somewhere on that list.

This paper, written by researchers from Chanakya University, takes this idea and adds a twist: The Circular Twist.

1. The Concept: From a Line to a Ring

Normally, a list is linear—it has a beginning and an end. If your recipe is "Onion, Salt, Pepper," you can find it in a list like [Garlic, Onion, Salt, Pepper, Basil].

But what if the list was written on a circular ring (like a necklace or a clock face)? In a circle, there is no true "start" or "end." If you have a ring of ingredients, you can start reading from any point and go around. This makes the "Master List" much more powerful. A single circular list might contain many more recipes simply because you can "wrap around" the circle to find them.

The researchers are asking: "What is the shortest possible ring of numbers that contains every possible recipe of a certain length?"

2. The "Zigzag" Strategy: The Dance of Numbers

To build these master lists, the authors use a technique called a Zigzag Construction.

Imagine a dancer performing on a stage. Instead of moving in a straight line, the dancer moves in a rhythmic, back-and-forth pattern: High, Low, Medium-High, Medium-Low.

In math terms, they create a sequence of numbers that "zigzags" up and down using specific rules about whether numbers are even or odd (parity). This rhythmic movement is very efficient. Because the numbers are constantly jumping up and down in a predictable way, they "trap" almost every possible sequence of numbers within their dance steps. It’s like a net with very specific holes that catches every kind of fish.

3. The Main Discoveries

The paper does three main things:

The Shortcut Rule: They proved that if you already have a "Master List" for a small group of recipes, you can easily turn it into a "Master Ring" for a larger group just by adding one extra number and looping it.
The Parity Secret: They discovered that for certain lengths (specifically odd numbers), the "Zigzag Dance" works perfectly to create these circular master lists. They used a "Score Function"—think of this as a "Difficulty Rating" for each recipe—to prove that their zigzag pattern is efficient enough to catch everything.
The Mathematical Proof: They didn't just guess; they used logic to show that their zigzagging "Master Ring" is mathematically guaranteed to contain every possible pattern, even when you rotate the ring.

Summary Metaphor

Think of the researchers as architects designing a Universal Keyring.

Instead of making a separate key for every single lock in the world (which would be a massive, heavy ring), they are trying to design one clever, rhythmic, "zigzagging" key that, when turned in a circular motion, can unlock every single door. They have successfully figured out the mathematical "shape" of that perfect, efficient key.

Technical Summary: Circular Superpatterns and Zigzag Constructions

Authors: M. Hariprasad and Raisa Dsouza (Chanakya University, Bengaluru)

1. Problem Statement

The paper addresses a fundamental question in combinatorial pattern containment: What is the minimum length of a permutation that contains all possible patterns of length $k$ ? Such a permutation is known as a $k$ -superpattern.

While the linear version of this problem is well-studied (with established upper bounds like $L(k) \leq \frac{k(k+1)}{2}$ and conjectures regarding asymptotic growth), this paper introduces and explores a new variation: Circular $k$ -superpatterns. In this setting, permutations are treated as being arranged on a circle, meaning patterns are considered equivalent if one can be obtained from another via rotation (cyclic equivalence). The goal is to determine the minimal length $L_{circ}(k)$ required to contain all $k$ -length patterns up to rotation.

2. Methodology

The authors employ three primary mathematical approaches to tackle the problem:

Recursive Construction: They attempt to build circular superpatterns by leveraging existing knowledge of linear superpatterns.
Zigzag Framework Adaptation: They utilize and simplify the "zigzag word" framework originally proposed by Engen and Vatter. This involves constructing sequences of "runs" based on parity (even/odd) to embed patterns.
Score Function Analysis: The authors develop a "circular score function" based on "local costs." This function quantifies the number of additional zigzag runs required to embed a specific permutation. By analyzing the parity of these scores, they determine the feasibility of embeddings within a finite zigzag word.

3. Key Contributions and Results

A. General Upper Bound
The authors prove that a circular $k$ -superpattern can be constructed from a linear $(k-1)$ -superpattern.

Theorem: If $\pi$ is a linear $(k-1)$ -superpattern, then the permutation $\gamma = (L+1, \pi_1, \dots, \pi_L)$ is a circular $k$ -superpattern.
Result: This establishes the upper bound: $L_{circ}(k) \leq L(k-1) + 1$ .

B. Circular Score Function and Parity Properties
The authors extend the Engen-Vatter score function to the circular setting.

Circular Lift Identity: They prove that for any permutation $\sigma$ , the circular score of $\sigma$ and its incremented version $\sigma^+$ satisfy $S_c(\sigma) + S_c(\sigma^+) = 0$ .
Parity Constraint: For odd $k$ , they prove that $S_c(\sigma) \neq 0$ . This non-zero property is crucial because it guarantees that for any pattern, either the pattern itself or its incremented version will have a sufficiently low score to be embedded in a reduced number of zigzag runs.

C. Zigzag Construction for Odd $k$
The paper proposes a specific construction for odd $k$ using a modified zigzag word $zzc(k)$.

Construction: They take the zigzag word $zz(k-1, k-1)$, replace the terminal elements $(2, 1)$ with $(k, k-1)$ , and apply the "breaking ties" method to transform the word into a permutation.
Conjecture/Claim: They provide a detailed proof outline (Claim 1) suggesting that this construction $\gamma_k$ yields a circular $k$ -superpattern for odd $k$ .

4. Summary of Results (Table 1)

The paper provides explicit upper bounds for different contexts:

Context	Length Bound
Over alphabet $[k+1]$	$(k-1)(k+1)/2$
Over permutations	$\lfloor \frac{k^2+1}{2} \rfloor + 1$
Using linear $(k-1)$ superpattern	$L(k-1) + 1$

5. Significance

This work is significant because it expands the domain of pattern containment theory from linear structures to cyclic structures. By introducing the circular score function and proving the parity-based existence of embeddings for odd $k$ , the authors provide a theoretical foundation for constructing efficient superpatterns. This has potential implications in fields where cyclic symmetry is inherent, such as bioinformatics (circular DNA sequences) and network topology.