🔢 mathematics

Subsequence Sums in Permutations

This paper establishes that for sufficiently large $n$ , every permutation of $\{1, 2, \ldots, n\}$ contains a 2-additive subsequence of any fixed length $k \geq 3$ , provides polynomial bounds for the required $n$ , determines the exact threshold of $n=18$ for monotone 2-additive subsequences of length three, and extends these results to products and inverse sums using arithmetic Ramsey theory techniques.

Original authors: Collier Gaiser, Paul Horn

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Collier Gaiser, Paul Horn

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 deck of cards numbered 1 to $n$ , shuffled into a completely random order. This shuffled deck is what mathematicians call a permutation.

For a long time, mathematicians have been asking a specific question about these shuffled decks: No matter how you shuffle them, if the deck is big enough, will you always be able to find a small group of cards hidden inside that follow a special math rule?

This paper, written by Collier Gaiser and Paul Horn, says "Yes," but with a twist. They found a new type of rule that always appears in large enough decks, and they figured out exactly how big the deck needs to be to guarantee this happens.

Here is the breakdown of their discovery using simple analogies:

1. The "Double-Your-Money" Rule

The authors are looking for a specific pattern they call a 2-additive subsequence.

Think of it like a magic trick with three numbers: $A, B, C$ .

If you add them all up ( $A + B + C$ ), the total should be exactly twice the first number ( $2 \times A$ ) OR twice the last number ( $2 \times C$ ).

The Big Discovery:
The paper proves that if you have a deck of cards that is "sufficiently large" (the exact size depends on how many cards you want in your group), you are guaranteed to find a group of $k$ cards that follows this rule.

The Catch: The cards don't have to be next to each other in the deck. They just have to appear in the correct order from left to right.
The Result: For any group size $k$ (as long as $k \ge 3$ ), there is a "magic number" $n$ . If your deck has more than $n$ cards, you cannot shuffle them in a way that avoids this pattern. It's unavoidable.

2. How Big Does the Deck Need to Be?

The authors didn't just say "it's big"; they calculated the limits.

The Upper Bound: They proved that if your deck is roughly proportional to $k^5$ (a polynomial size), you are guaranteed to find the pattern.
The Lower Bound: They also showed that if the deck is too small (specifically smaller than a certain formula), you can actually shuffle it to avoid the pattern.

A Specific Example (The "Magic Number" 18):
The paper zooms in on the smallest possible group: a group of three cards ( $k=3$ ).

They asked: "What is the smallest deck size where you are forced to find three cards where the sum is double the first or double the last?"
The Answer: 18.
If you have a deck of 17 cards, you can shuffle them in a very specific, tricky way to avoid this pattern.
But the moment you add the 18th card, no matter how you shuffle, you will inevitably find three cards that fit the rule.
Analogy: Imagine trying to arrange 17 people in a line so that no three of them satisfy a specific height-sum rule. You can do it. But if you add an 18th person, it becomes mathematically impossible to arrange them without creating that specific trio.

3. The "Monotone" Twist

The authors also looked at a stricter version of the game. What if the three cards you find must also be monotone?

Monotone means they are either strictly going up (like 2, 5, 8) or strictly going down (like 9, 4, 1).
They proved that even with this stricter rule, the magic number is still 18. If you have 18 cards, you can't avoid finding three cards that are both in the right order and follow the "double sum" rule.

4. Multiplication and Inverse Sums

The paper doesn't stop at addition. The authors used their findings to show that similar rules apply to other math operations:

Multiplication: If you look for a group where the product of the numbers equals the square of the first or last number, the same logic applies. If the deck is big enough, this pattern is unavoidable.
Inverse Sums: They also looked at adding fractions (like $1/A + 1/B + 1/C$ ). They proved that if the deck is big enough, you will find a group where the sum of the fractions equals twice the first or last fraction.

5. Why This Matters (In Math Terms)

Before this paper, mathematicians knew that you could shuffle a deck to avoid arithmetic progressions (like 2, 4, 6 or 5, 10, 15). You can hide those patterns.

However, this paper shows that while you can hide arithmetic progressions, you cannot hide these "2-additive" patterns. It's like saying: "You can hide a straight line in a messy pile of sand, but you can't hide a specific triangle shape."

Summary

The Problem: Can you shuffle a deck of numbers so that no small group follows a specific math rule?
The Answer: No. If the deck is big enough, the rule is unavoidable.
The Rule: The sum of the group equals twice the first or last number.
The Threshold: For a group of 3, you need at least 18 numbers to guarantee the rule appears.
The Extension: This logic also works for multiplication and fractions.

The paper provides the mathematical "safety net" that proves these patterns are inevitable in large enough collections of numbers, regardless of how chaotic the arrangement seems.

Technical Summary: Subsequence Sums in Permutations

Problem Statement
This paper investigates the existence of specific arithmetic subsequences within permutations of the set $\{1, 2, \dots, n\}$ . While classical arithmetic Ramsey theory (e.g., van der Waerden's theorem) guarantees monochromatic arithmetic progressions in sufficiently large colored sets, Entringer and Jackson (1973) demonstrated that permutations can avoid monotone 3-term arithmetic progressions (3-APs). The authors ask whether other arithmetic properties, specifically "additive" subsequences, are unavoidable in large permutations.

A sequence of positive integers $(a_1, a_2, \dots, a_k)$ is defined as $\ell$ -additive if the sum of its terms satisfies $\sum_{i=1}^k a_i = \ell a_1$ or $\sum_{i=1}^k a_i = \ell a_k$ . The primary focus is on 2-additive subsequences (where the sum equals twice the first or last term) and their monotone variants. The paper addresses two main questions:

For a fixed length $k \ge 3$ , does there exist an $n$ such that every permutation of $\{1, \dots, n\}$ contains a 2-additive subsequence of length $k$ ?
What are the precise thresholds and bounds for the existence of such subsequences, particularly when restricted to monotone sequences?

Methodology
The authors employ a combination of combinatorial arguments, case analysis, and techniques from arithmetic Ramsey theory.

Combinatorial Construction and Contradiction: The core proofs for existence (Theorems 1.1 and 1.3) rely on constructing specific subsets of permutations and using proof by contradiction. By analyzing the relative positions of elements (using $L_p(s)$ and $R_p(s)$ to denote elements to the left and right of $s$ in a permutation $p$ ), the authors demonstrate that avoiding a 2-additive subsequence forces a structural contradiction in the permutation's layout.
Bounding Techniques: To establish upper bounds for the smallest $n$ (denoted $f(k, 2)$ ), the authors define a set of "dangerous" sums derived from the first $2k-1$ elements of a permutation. They utilize the least common multiple (LCM) of these sums to determine a threshold $N_k$ beyond which a 2-additive subsequence is forced.
Lower Bounds and Counterexamples: Lower bounds are established by explicitly constructing permutations of size $n-1$ that lack the desired subsequences.
Asymptotic Analysis: The paper uses the Prime Number Theorem (via Rosser's results) to derive lower bounds on the number of such subsequences in large permutations.
Transformation Arguments: To extend results to products and inverse sums, the authors use standard transformations mapping additive properties in $\{1, \dots, n\}$ to multiplicative properties in $\{2^1, \dots, 2^n\}$ and inverse-additive properties in $\{L_n/1, \dots, L_n/n\}$ (where $L_n$ is the LCM of $1$ to $n$ ).

Key Contributions and Results

Existence of 2-Additive Subsequences (Theorem 1.1):
For any fixed $k \ge 3$ , if $n$ is sufficiently large, every permutation of $\{1, \dots, n\}$ contains a 2-additive subsequence of length $k$ .
- Bounds: The paper provides polynomial bounds for the smallest such $n$ $n$ , denoted $f(k, 2)$ $f (k, 2)$ .
  - Lower bound: $f(k, 2) \ge (k-1)(3k-4)/2$ .
  - Upper bound: $f(k, 2) \le 9(k-2)(k^2-k)^2/4$ .
- Exact Value for $k=3$ : The authors prove that $f(3, 2) = 5$ . Every permutation of $\{1, \dots, 5\}$ contains a 2-additive subsequence of length 3, while a counterexample exists for $n=4$ .
Monotone 2-Additive Subsequences (Theorem 1.3):
The paper addresses the stricter condition where the subsequence must be monotone.
- Result: If $n \ge 18$ , every permutation of $\{1, \dots, n\}$ contains a monotone 2-additive subsequence of length 3.
- Sharpness: The value 18 is optimal; a specific permutation of $\{1, \dots, 17\}$ is constructed that avoids such subsequences.
- Open Question: It remains unknown if this holds for monotone 2-additive subsequences of length $k \ge 4$ .
General $\ell$ -Additive Subsequences:
- If $k = \ell$ , the identity permutation $(1, 2, \dots, n)$ contains no $\ell$ -additive subsequence of length $k$ .
- The paper resolves two specific mixed cases:
  - $f(4, 3) = 8$ (Every permutation of 8 elements has a 3-additive subsequence of length 4).
  - $f(3, 4) = 13$ (Every permutation of 13 elements has a 4-additive subsequence of length 3).
- The general case for $k \neq \ell$ with $k, \ell \ge 4$ is left as an open question.
Counting Subsequences:
The authors provide bounds on the minimum number of $\ell$ -additive subsequences of length $k$ in any permutation of size $n$ :
- Upper Bound: $O(n^{k-1})$ .
- Lower Bound: $\Omega(n / \log n)$ (assuming $f(k, \ell)$ exists), derived using prime number distribution arguments.
- Specific bounds for monotone 2-additive subsequences of length 3 are given as $n/[18(\log n - \log 18 + 2)] - 6 \le G(3, 2, n) \le \frac{1}{18}n^2 + \frac{7}{6}n$ .
Extensions to Products and Inverse Sums:
Using arithmetic Ramsey theory transformations, the paper extends the additive results to:
- Multiplicative: Every large enough permutation has a subsequence where the product is the square of the first or last term (2-multiplicative).
- Inverse-Additive: Every large enough permutation has a subsequence where the sum of reciprocals is twice the reciprocal of the first or last term.
- The paper notes that for monotone 2-multiplicative subsequences of length 3, the threshold is at most 32 (and exactly 32, as a counterexample exists for $n=31$ ).

Significance and Claims
The paper claims to establish the first Schur-Rado-type results specifically for permutations, demonstrating that while permutations can avoid monotone arithmetic progressions (3-APs), they cannot avoid 2-additive subsequences of arbitrary length. The work provides the first polynomial bounds for the existence of these structures and determines exact thresholds for small cases ( $k=3$ ).

The authors modestly frame their contribution as a foundation for further study. They highlight that the general case for $k \neq \ell$ remains open and that the behavior of monotone 2-additive subsequences for lengths $k > 3$ is unknown. The paper positions these findings as a step toward understanding the interplay between permutation structure and arithmetic properties, suggesting future directions in weighted subsequence sums and the refinement of thresholds for multiplicative and inverse-additive variants.