Pin Classes I: Growth Rates

This paper investigates permutation classes formed by finite subpermutations of infinite pin sequences, proving that they possess proper growth rates and providing a method to calculate them.

The Gist

Imagine you are an architect trying to design a city. But instead of buildings, your city is made of permutations—which are just fancy ways of saying "ordered lists of numbers."

In the world of mathematics, there's a huge question: How fast does a city of these number-lists grow? If you have a rule that says "you can't build a skyscraper shaped like this specific pattern," how many different cities can you still build as they get bigger? Sometimes the answer is "a lot" (exponential growth), and sometimes it's "infinite" (factorial growth).

This paper, written by Ben Jarvis, is about a specific, very interesting type of city called a "Pin Class."

Here is the story of the paper, broken down into simple concepts:

1. The Pin Sequence: A Game of "Pin the Tail"

Imagine you are playing a game where you have to place dots on a piece of paper.

• You start with a center point (the origin).
• You place the first dot in one of the four corners (quadrants) around the center.
• Then, you have to place the next dot. But there's a rule: You must place it so that it "pins" the previous dots against the edge of a growing box.

Think of it like a game of Jenga or Pac-Man. Every time you place a new dot, it has to be the "most extreme" point in a specific direction (Up, Down, Left, or Right) relative to all the dots you've already placed. It has to "pin" the existing group against the imaginary walls of the box.

If you follow a specific set of instructions (a "Pin Word") like "Start Top-Right, then go Left, then Up, then Down...", you create a unique pattern of dots. This pattern is a Pin Permutation.

2. The Infinite City (Pin Classes)

The paper isn't just about one pattern; it's about infinite patterns. Imagine you have an infinite instruction manual that tells you where to place dots forever.

• The City: The "Pin Class" is the collection of every possible small city you can find inside that infinite pattern.
• The Question: As these cities get bigger, how many different versions of them exist? Do we have 10, 100, or 1,000,000 different cities of size 100?

3. The Big Mystery: Do They Have a "True" Growth Rate?

Mathematicians have known for a long time that if you forbid a pattern, the number of cities you can build grows exponentially (like $2^n$or$3^n$). But there was a nagging doubt: Is the growth rate smooth and steady, or does it wobble?

Imagine a runner.

• Smooth: They run exactly 10 meters every second.
• Wobbly: They run 10 meters, then 12, then 9, then 11. The average is 10, but the instant speed changes.

For a long time, mathematicians didn't know if Pin Classes had a "smooth" growth rate (a Proper Growth Rate) or if they just had an "average" speed (an Upper Growth Rate) that wobbled around.

The Paper's Main Discovery:
Ben Jarvis proves that Pin Classes always have a smooth, steady growth rate. They don't wobble. If you know the infinite instruction manual, you can calculate the exact speed at which these cities grow.

4. The Secret Weapon: The "Box Sum"

To solve this, the author invents a new way of looking at these cities. He introduces the idea of a "Centred Permutation."

• Imagine your city has a special "Town Hall" (the origin) in the middle.
• He discovers that you can build complex cities by gluing smaller, simpler cities together onto this Town Hall. He calls this the "Box Sum" (or 'sum).

Think of it like Lego.

• You have small, indestructible Lego bricks (the "indecomposable" pieces).
• You can snap them together to build huge structures.
• The paper shows that for Pin Classes, there is a very specific, almost mechanical rule for how these bricks snap together.

5. The "Recurrent" vs. "Non-Recurrent" Problem

There are two types of infinite instruction manuals:

1. Recurrent (The Looping Tape): The instructions repeat in a pattern forever (e.g., "Left, Up, Right, Down, Left, Up..."). These are easy to study because the pattern is predictable. The author shows how to calculate their growth rate easily using a formula.
2. Non-Recurrent (The Chaotic Tape): The instructions never repeat (e.g., "Left, Up, Right, Down... then a huge gap... then Left, Up..."). These are messy and unpredictable.

The Masterstroke:
The author realizes that even if the whole tape is chaotic, the core of the tape (the parts that repeat infinitely often) acts like a "skeleton" for the city.

• He proves that the growth rate of the messy, chaotic city is exactly the same as the growth rate of its clean, repeating skeleton.
• This allows him to take the messy, non-repeating cities, strip away the chaos, find the repeating core, and calculate the growth rate using the easy method.

6. Why Does This Matter?

• Solving a Puzzle: It solves a major open problem in mathematics about whether these specific types of number-patterns have steady growth rates.
• Counter-Examples: Pin classes are great at creating "weird" mathematical objects that break other rules. Knowing their growth rates helps mathematicians understand the limits of what is possible in the world of patterns.
• The "Liouville V": The paper even calculates the growth rate for a specific, very strange city called the "Liouville V," showing that even the most chaotic-looking patterns have a hidden, steady heartbeat.

Summary Analogy

Imagine you are trying to predict the traffic flow in a city.

• Some cities have a perfect grid (Recurrent Pin Classes). You can easily count the cars.
• Other cities have chaotic, winding roads that never repeat (Non-Recurrent Pin Classes). It seems impossible to count the cars.

Ben Jarvis discovered that even in the chaotic city, the traffic flow is determined by the few main highways that loop endlessly. If you count the cars on those main highways, you know the exact speed of the entire city.

The Bottom Line: No matter how complicated the infinite pattern of dots looks, the number of ways to arrange them grows at a perfectly steady, calculable speed. The chaos has a rhythm after all.

Technical Summary

Here is a detailed technical summary of the paper "Pin Classes I: Growth Rates" by Ben Jarvis.

1. Problem Statement

The paper addresses a fundamental open problem in the field of permutation patterns: Do all proper permutation classes possess a "proper" growth rate?

• Context: A permutation class is a set of permutations closed under pattern containment. The growth rate of a class $C$ is defined as $\lim_{n \to \infty} \sqrt[n]{|C_n|}$, where $|C_n|$ is the number of permutations of length $n$ in the class.
• The Gap: The Marcus-Tardos Theorem (2004) guarantees that every proper permutation class has a finite upper growth rate. However, it does not guarantee that the upper and lower growth rates are equal (i.e., that the limit exists).
• Focus: The author investigates Pin Classes, a specific family of permutation classes generated by infinite "pin words." These classes are structurally significant because they relate to simple permutations, infinite antichains, and well-quasi-ordering. The paper aims to prove that every pin class has a proper growth rate and to provide a method for calculating it.

2. Methodology

The paper employs a multi-stage approach combining combinatorial structure theory, generating functions, and analytic methods.

A. Centred Permutations and the $\boxplus$-Sum

• Centred Permutations: The author introduces "centred permutations" (permutations with a designated origin point). This allows the plane to be divided into four quadrants relative to the origin.
• The $\boxplus$-Sum: A new operation, the "box-sum" ($\boxplus$), is defined for centred permutations. It involves inflating the origin of one permutation with another.
• $\boxplus$-Decomposition: The paper establishes that centred pin permutations can be uniquely decomposed (up to commutativity of specific "one-quadrant" permutations) into a sequence of $\boxplus$-indecomposable components. This structure is crucial for enumeration.

B. Pin Words and Pin Classes

• Pin Words: Infinite words over the alphabet $\{1, 2, 3, 4, u, d, l, r\}$ (representing quadrants and directions) that generate permutations via a specific geometric construction (placing points to slice the bounding rectangle of previous points).
• Pin Classes: The class of all permutations contained in the infinite diagram generated by a specific infinite pin word $w$.
• Recurrent vs. Non-Recurrent:
  • Recurrent Pin Words: Every finite factor of the word appears infinitely often. These generate $\boxplus$-closed classes.
  • Non-Recurrent Pin Words: Factors may appear only finitely often. These classes are not necessarily $\boxplus$-closed.

C. Enumeration Strategy

1. For Recurrent Classes:

   • The author proves that recurrent pin classes are $\boxplus$-closed.
   • Using the Generating Function Specification (Theorem 2.23), the generating function $f(z)$ of the class is derived from the generating function of its $\boxplus$-indecomposables ($g(z)$) and the "amended G-sequence" ($G(z)$), which accounts for commutativity between opposite quadrants.
   • $f(z) = \frac{1}{1 - G(z)}$.
   • The growth rate is the reciprocal of the radius of convergence of $f(z)$.

2. For Non-Recurrent Classes:

   • The author introduces the $\boxplus$-interior ($C_w^\boxplus$), defined as the $\boxplus$-closure of the set of recurrent $\boxplus$-indecomposables within the class.
   • Sandwiching Argument: The paper proves that the growth rate of the full pin class $C_w$ is "sandwiched" between the growth rate of its $\boxplus$-interior and the growth rate of the $\boxplus$-closure of the class.
   • Limit Argument: By truncating the infinite pin word and taking the limit as the truncation point moves to infinity, the author shows that the growth rates of the approximating $\boxplus$-closed classes converge to the growth rate of the $\boxplus$-interior.

3. Key Contributions

Theoretical Proofs

• Existence of Proper Growth Rates: The main theorem (Theorem 4.12) proves that every pin permutation class (whether generated by recurrent or non-recurrent words) has a proper growth rate. This resolves the existence question for this large family of classes.
• Classification of Pathologies: The paper provides a complete classification of "collisions" (distinct pin words generating the same permutation) and "$\boxplus$-decomposable" pin words (words generating reducible permutations). This allows for the precise correction of enumeration counts.
• The Finite Prefix Lemma: Establishes that the growth rate of a pin class is invariant under finite prefixes of the defining pin word.

Computational Procedures

• Algorithm for Growth Rates: A step-by-step procedure (Procedure 3.39) is provided to calculate the growth rate of any recurrent pin class:
  1. Enumerate pin factors of the defining word.
  2. Subtract counts for $\boxplus$-decomposables and collisions (using the classified lists).
  3. Construct the amended G-sequence $G(z)$.
  4. Solve $G(z) = 1$ for the smallest positive real root; the growth rate is its reciprocal.
• Explicit Examples: The paper calculates growth rates for several specific classes, including:
  • Increasing Oscillations ($O$): Growth rate $\kappa \approx 2.20557$ (the minimum possible for pin classes).
  • Classes $V(1, k)$: A family of two-quadrant classes with growth rates converging to $\nu_L \approx 3.28277$.
  • The Widdershins Spiral ($W$): A four-quadrant class with growth rate $\approx 3.48806$.
  • The Complete Pin Class ($P$): The class of all pin permutations, with growth rate $\omega_\infty \approx 5.24112$.

The Liouville V

• The paper analyzes a non-recurrent class called the Liouville V ($V_L$), generated by a word with increasingly long gaps between repetitions.
• It demonstrates that the growth rate of this non-recurrent class is exactly $\nu_L$, the accumulation point of the $V(1, k)$ sequence. This proves that $\nu_L$ is an accumulation point of pin class growth rates from both above and below.

4. Results

• Bounds: The growth rate of any pin class $C_w$ satisfies $\kappa \leq \text{gr}(C_w) \leq \omega_\infty$, where $\kappa \approx 2.20557$ and $\omega_\infty \approx 5.24112$.
• Accumulation Points: The set of pin class growth rates is not discrete; it contains accumulation points (specifically $\nu_L$).
• Rationality: For recurrent pin classes, the generating functions are rational, implying algebraic growth rates. For non-recurrent classes, the generating functions may not be rational, but the growth rates still exist.

5. Significance

• Resolution of a Major Open Problem: By proving that pin classes have proper growth rates, the paper provides strong evidence and a structural framework for the broader conjecture that all proper permutation classes have proper growth rates.
• Structural Insight: The introduction of the $\boxplus$-sum and the analysis of $\boxplus$-interiors provide powerful new tools for analyzing the asymptotic behavior of complex permutation classes that are not easily handled by traditional basis-based methods.
• Connection to Antichains: Pin classes are linked to the construction of infinite antichains. Understanding their growth rates helps in constructing well-quasi-ordered classes with specific enumeration properties, a topic of high interest in combinatorics.
• Future Directions: The paper sets the stage for a sequel (referenced as [10]) that will classify the growth rates of two-quadrant pin classes and explore the "phase transition" at $\nu_L$ where uncountably many distinct classes appear.

In summary, Ben Jarvis's paper establishes a rigorous framework for the enumeration and growth rate analysis of pin classes, proving the existence of proper growth rates for this entire family and providing explicit computational methods to determine them.