🔢 mathematics

Weakly Consecutive Sequences

This paper introduces weakly consecutive sequences as a rich class of permutations defined by divisibility constraints, proposes a constructive method using four starting sequences and three rules to generate them, and establishes bounds for their count while conjecturing that all such sequences can be formed through this process.

Original authors: Thomas Garrison, Chris Seiler, Andrew Knowles

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thomas Garrison, Chris Seiler, Andrew Knowles

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 have a row of numbered seats, from 1 to $k$ , and you need to assign a unique number to each seat (a permutation). Usually, you might just line them up in order: 1, 2, 3, 4... But what if you had a very specific rule about how numbers relate to their neighbors?

This paper introduces a special kind of seating arrangement called a Weakly Consecutive Sequence (WCS).

The Core Rule: The "Family Reunion" Analogy

Think of the numbers in your sequence as people at a family reunion. The rule is about divisibility, which we can think of as "family resemblance."

The Rule: If a number $X$ sits in a seat, and a number $D$ divides $X$ (meaning $D$ is a "family member" of $X$ ), then any seat that is exactly $D$ steps away from $X$ must also be occupied by a number that $D$ divides.
The Analogy: Imagine the number 2 is the "Even Family." If the number 4 (an even number) is sitting in seat #5, then the number in seat #3 (two steps left) and seat #7 (two steps right) must also be even numbers.
The "Weakly Consecutive" Part: The standard sequence (1, 2, 3, 4...) follows this rule perfectly. If 6 is in seat 6, then 3 steps away (seat 3) is 3, and 2 steps away (seat 4) is 4. They all respect the family rules. The paper asks: How many other ways can we shuffle the numbers so that these family rules are still obeyed?

The Discovery: Building Blocks and Tools

The authors found that while counting these sequences is hard, we can build them like LEGO sets. They discovered four specific "Starting Blocks" (base patterns) and three "Tools" (operations) to create new valid sequences from them.

The Four Starting Blocks

Depending on the total number of seats ( $k$ ), you might start with one of these four patterns:

The Straight Line: Just 1, 2, 3... $k$ . (Always works).
The 1-Inversion: If the number of seats is one less than a prime number, you can move the "1" to the very end. (e.g., 2, 3, 4, 5, 1).
The Twin Swap: If the number of seats relates to "Twin Primes" (like 5 and 7), you can swap specific pairs of numbers (like swapping the 2 and the 10, or the 5 and the 7) to create a new valid pattern.
The Sophie Germain Shuffle: If the numbers involve a special type of prime trio, you can move the 1 and 2 to the end and swap a few other numbers around.

The Three Tools

Once you have a starting block, you can use these tools to generate more:

The Twin Swap Tool: If you have a specific starting block (the Sophie Germain one), you can swap pairs of twin primes (like 17 and 19) if they are in the right spot.
The Power Swap Tool: This is the most powerful tool. If you have a number like 8 ( $2^3$ ) and 4 ( $2^2$ ), and they are close enough in the sequence, you can swap them. You can do this with other prime powers (like 9 and 3). This tool is like a multiplier; the more prime powers you can swap, the exponentially more sequences you can create.
The Mirror Tool: You can simply flip the whole sequence backwards. If 1-2-3-4-5 works, then 5-4-3-2-1 also works.

The Big Questions and Findings

1. How many sequences are there?
The authors call this number $N(k)$ .

For small numbers, it's easy to list them all (see Table 1 in the paper).
Usually, the number of sequences is a power of 2 (like 2, 4, 8, 16).
The Surprise: Sometimes, it's not a power of 2. For example, when there are 21 seats, there are exactly 12 sequences. When there are 81 seats, there are 40. The paper explains that these "weird" numbers happen when the special "Sophie Germain" starting block is available.

2. Can we make as many as we want?
Yes. The paper proves that as the number of seats ( $k$ ) gets larger, the number of possible sequences ( $N(k)$ ) can get arbitrarily large. You can find a length $k$ that allows for 1,000 sequences, or 1,000,000 sequences, though you might need a very large $k$ to do it.

3. The "Prime Power" Explosion
The most interesting finding is about the Power Swap Tool. The authors calculated how many times you can apply this swap for a given length.

They found that for some lengths, you can only swap a few times.
For other lengths, you can swap many times.
Because every swap doubles your options (you can swap or not swap), having many swap opportunities leads to a massive explosion in the number of sequences.

The Unproven Guesses (Conjectures)

The authors have a strong hunch (a conjecture) that every single valid sequence can be built using just those four starting blocks and three tools. They checked this with computers up to 500 seats, and it held true.

They also have a guess about the "Twin Prime" starting block (Block 4). They believe that for very long sequences, almost all of them come from this specific block, because it allows for the most complex swapping.

Summary

In simple terms, this paper is a map for a strange mathematical landscape. It defines a rule for shuffling numbers, finds the "seed" patterns that start the game, and provides the "moves" to generate every possible valid shuffle. It shows that while the rules seem simple, the number of ways to arrange the numbers grows wildly and unpredictably, driven by the hidden patterns of prime numbers.

Technical Summary: Weakly Consecutive Sequences

Problem Definition
The paper investigates "weakly consecutive sequences" (WCS), a specific class of permutations $\sigma$ of the set $\{1, \dots, k\}$ . A permutation is defined as weakly consecutive if, for any integers $i, j \in [k]$ and any integer $m$ , the condition $m \mid \sigma(i)$ and $m \mid (i-j)$ implies $m \mid \sigma(j)$ . Intuitively, this property ensures that the divisibility structure of the values is preserved relative to their positions; for instance, all elements at a distance divisible by $d$ from the position of $d$ must themselves be divisible by $d$ . The primary objective is to understand the structure of these sequences and determine $N(k)$ , the number of distinct WCS of length $k$ . The authors note that while $N(k)$ is often a power of 2, it exhibits irregular behavior (e.g., $N(21)=12$ , $N(81)=40$ ) and is difficult to characterize via a closed formula.

Methodology
The authors employ a constructive approach to generate and classify WCS. Their methodology relies on identifying a small set of "starting sequences" and a set of "rules" (operations) that preserve the weakly consecutive property.

Characterization Lemma: The paper establishes a fundamental equivalence (Lemma 2.2) stating that a permutation is weakly consecutive if and only if the set of indices $S_m^\sigma$ (indices congruent to the position of $m$ modulo $m$ ) equals the set of indices $T_m^\sigma$ (indices where the value is a multiple of $m$ ) for all $m$ . This "division slice" characterization is used to prove the validity of all subsequent constructions.
Starting Sequences: Four specific types of base permutations are identified, dependent on the arithmetic properties of $k$ $k$ :
- Consecutive: The identity sequence $(1, 2, \dots, k)$ .
- 1-Inversion: Valid when $k = p-1$ for a prime $p$ , resulting in $(2, 3, \dots, k, 1)$ .
- Twice Twin Prime: Valid when $k=2p$ or $2p+1$ for twin primes $p, p+2$ , involving swaps of positions for $2, 2p$ and $p, p+2$ .
- Twin Sophie Germain: Valid when $k=2p-1$ for primes $p, 2p+1, p+2$ , involving moving $1, 2$ to the end and swapping $p, p+2$ .
Generation Rules: Three operations are defined to generate new WCS from existing ones:
- Twin Prime Swap: Swaps twin primes $q, q+2$ in the upper half of the sequence (specifically for Starting Sequence 4).
- Prime Power Swap: Swaps $p^c$ and $p^{c-1}$ if $p^c \le k < p^c + p^{c-1}$ . This rule is applicable to any starting sequence.
- Trivial Reversal: Reverses the entire sequence.

Key Contributions and Results

Construction of WCS: The paper provides a systematic framework for generating WCS. The authors conjecture (Conjecture 5.1) that any WCS can be derived from one of the four starting sequences by applying the three rules. This has been computationally verified up to $k=500$ .
Bounds on $N(k)$ :
- Lower Bounds: By analyzing the "Prime Power Swap" rule, the authors derive a lower bound on the growth of $N(k)$ . They define $\#I(k)$ as the number of valid Prime Power Swaps for a given $k$ . Since each swap can be applied or not, $N(k) \ge 2^{\#I(k)}$ .
- Theorem 4.1 & Corollary 4.2: Using simultaneous Dirichlet approximation, the authors prove that for any $n$ , there exists a $k$ such that $\#I(k) \ge n$ . Specifically, they show there exists a $k \le 2^{n^2 \lg(\lg n)(1+o(1))}$ with $N(k) \ge n$ . This proves that $N(k)$ is an unbounded function of $k$ .
- Upper Bounds: Conversely, the paper demonstrates that $\#I(k)$ is not always large. Using probabilistic arguments involving uniform random variables and the distribution of prime powers, Theorem 4.8 shows that $\liminf_{k \to \infty} \#I(k) \le 1$ . This implies that for infinitely many $k$ , the number of Prime Power Swaps is minimal (at most 1), keeping $N(k)$ small.
Specific Values: The paper provides a table of $N(k)$ for $k \le 100$ , highlighting that non-power-of-2 values occur specifically when $k$ allows for the "Twin Sophie Germain" starting sequence and subsequent "Twin Prime Swaps."

Significance and Claims
The paper claims that the structure of weakly consecutive sequences is "surprisingly rich" despite the simple definition. The significance of the work lies in:

Unboundedness: Proving that the number of such sequences grows without bound, albeit erratically, as $k$ increases.
Structural Conjecture: Proposing that the entire set of WCS is generated by a finite set of base cases and local operations, linking the combinatorial structure directly to the distribution of prime numbers (specifically twin primes and Sophie Germain primes).
Asymptotic Behavior: The authors conjecture that if Dickson's conjecture and the first Hardy-Littlewood conjecture hold, Starting Sequence 4 (Twin Sophie Germain) will occur infinitely often and dominate the count of WCS for large $k$ , leading to $N(k)$ values significantly larger than the average case derived from Prime Power Swaps alone.
Modesty: The authors explicitly state that while they have verified their generation conjecture up to $k=500$ , they have not proven it generally. They also note that certain properties, such as whether every WCS must begin or end with 1 (Conjecture 5.2), remain unproven from first principles.

The paper concludes by framing the problem as a bridge between permutation combinatorics and number theory, suggesting that the density of WCS is deeply tied to the distribution of primes and the existence of specific prime constellations.