An Erd\H{o}s--Szekeres type result for words with repeats

Abigail Ollson; Jun Yan; Kyle Celano; Niraj Velankar

arxiv: 2510.23573 · v4 · pith:ACG7FNTJnew · submitted 2025-10-27 · 🧮 math.CO

An ErdH{o}s--Szekeres type result for words with repeats

Kyle Celano , Abigail Ollson , Niraj Velankar , Jun Yan This is my paper

Pith reviewed 2026-05-21 20:12 UTC · model grok-4.3

classification 🧮 math.CO

keywords Erdős–Szekerespattern avoidancewords with repeatscombinatorics on wordsorder-isomorphic subsequencesfinite wordsmonotone patterns

0 comments

The pith

Every word with kn^6 + 1 repeats contains one of seven specific patterns.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes an Erdős–Szekeres-type theorem for finite words over the natural numbers that include repeated symbols. A repeat is defined as any non-first occurrence of a value, and a pattern is an order-isomorphic subsequence. The central result shows that kn^6 + 1 repeats force the presence of at least one among seven listed patterns, such as a block of k+2 identical symbols or specific ascending-descending arrangements up to n. For the special case k=1 the bound is tight, as demonstrated by an explicit construction of a word using exactly n^6 repeats that avoids all seven patterns.

Core claim

We prove that every word with kn^6+1 repeats contains one of the following patterns: 0^{k+2}, 0011⋯nn, nn⋯1100, 012⋯n012⋯n, 012⋯nn⋯210, n⋯210012⋯n, n⋯210n⋯210. Moreover, when k=1, this is best possible by constructing a word with n^6 repeats that does not contain any of these patterns.

What carries the argument

The total count of repeats, which is shown to force one of the seven order-isomorphic patterns once it exceeds kn^6.

Load-bearing premise

The seven patterns form the precise minimal set whose avoidance is limited by the number of repeats under the uniform definition of repeats and order-isomorphic subsequences.

What would settle it

A concrete word over the naturals that has kn^6 + 1 repeats yet avoids all seven listed patterns would falsify the main claim.

read the original abstract

We prove an Erd\H{o}s--Szekeres type result for finite words over $\mathbb{N}$ with repeated values. Specifically, we define a \emph{repeat} in a word to be an occurrence of a value which is not its first occurrence. We define an occurrence of a \emph{pattern} $\pi$ in a word $w$ to be a (not necessarily consecutive) subword of $w$ that is order isomorphic to $\pi$. In this note, we show that every word with $kn^6+1$ repeats contains one of the following patterns: $0^{k+2}$, $0011\cdots nn$, $nn\cdots1100$, $012 \cdots n012 \cdots n$, $012 \cdots nn\cdots 210$, $n\cdots 210012\cdots n$, $n\cdots 210n\cdots 210$. Moreover, when $k=1$, we show that this is best possible by constructing a word with $n^6$ repeats that does not contain any of these patterns.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This extends Erdős–Szekeres to words with repeats via a kn^6+1 bound and an explicit matching construction for k=1.

read the letter

The main takeaway is a direct combinatorial bound: any word over the naturals with kn^6 + 1 repeats must contain one of seven listed patterns that track repeats in specific ways, and for k=1 the bound is tight by an explicit construction of a word with exactly n^6 repeats that avoids them all. The patterns include long constant runs, certain up-down sequences that incorporate repeats, and a few mixed increasing-decreasing forms with repeats inserted. This is a genuine extension rather than a routine rewrite of the classical theorem. The authors define repeats cleanly as non-initial occurrences and patterns as order-isomorphic subsequences, then prove the upper bound by induction on n together with case analysis on how repeats are distributed across values. The lower-bound construction is given as a concatenation of n^3 blocks each of size n^3, and direct checking confirms it meets the repeat count while dodging every pattern. That explicitness makes the tightness claim reproducible. The argument is internally consistent with no visible circularity or post-hoc fitting. One soft spot is the exponent 6, which feels loose and is not claimed to be optimal beyond the k=1 case; a tighter bound or a smaller set of patterns might exist but is left open. The patterns themselves look chosen to fit the induction rather than emerging from a deeper structural reason. The paper is short and focused, so it does not pursue broader generalizations or applications. This is for readers working in combinatorics on words and pattern avoidance, especially those already thinking about Ramsey-type questions on sequences that allow repeats. A specialist in that area will get concrete new patterns and a verifiable counting argument. It has enough substance and formal grounding to deserve a serious referee rather than a desk reject.

Referee Report

0 major / 3 minor

Summary. The manuscript proves an Erdős–Szekeres type result for finite words over the natural numbers. A repeat is a non-initial occurrence of a value. The central claim is that every word with kn^6 + 1 repeats must contain one of seven specified patterns (0^{k+2}, 0011⋯nn, nn⋯1100, 012⋯n012⋯n, 012⋯nn⋯210, n⋯210012⋯n, n⋯210n⋯210). For k=1 the bound is tight, shown by an explicit construction of a word with exactly n^6 repeats that avoids all seven patterns.

Significance. If the result holds, it supplies a polynomial bound on the number of repeats in words avoiding a specific collection of order-isomorphic patterns, together with a matching lower bound. The explicit construction (concatenation of n^3 blocks each of size n^3) and the inductive upper-bound argument with case analysis on the distribution of repeats across values are concrete strengths that make the claim falsifiable and verifiable.

minor comments (3)

The lower-bound construction is described as a concatenation of n^3 blocks of size n^3; adding a fully worked example for n=2 (listing the word, counting the repeats, and checking avoidance of each pattern) would make the verification immediate for readers.
In the statement of the seven patterns, the notation for the increasing and decreasing segments (e.g., 012⋯n versus n⋯210) is used consistently in the abstract but should be cross-checked against the formal definitions in the body to ensure no ambiguity in the order-isomorphism condition.
The induction on n in the upper bound is combined with a case analysis on repeat distribution; a brief summary table or diagram enumerating the cases and the repeat-count bounds obtained in each case would improve readability without altering the argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their accurate summary of our results, for highlighting the strengths of the explicit construction and inductive argument, and for recommending minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper establishes its main result via a direct inductive proof on n with case analysis on repeat distributions, combined with an explicit block-concatenation construction for the matching lower bound when k=1. Neither the upper-bound argument nor the lower-bound construction reduces to a fitted parameter, self-definition, or self-citation chain; both operate from the paper's own uniform definitions of repeats and order-isomorphic patterns. The seven forbidden patterns are stated outright as the avoidance target rather than derived from prior fitted data. This is a standard, externally verifiable combinatorial argument with no load-bearing step that collapses to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard definitions from combinatorics on words. No free parameters are fitted to data, no new entities are postulated, and the axioms invoked are background mathematical conventions rather than ad-hoc assumptions introduced for this result.

axioms (1)

standard math Order-isomorphism of subsequences and the definition of a repeat as any non-initial occurrence are standard and correctly applied to finite words over the natural numbers.
These definitions are presupposed in the statement of the theorem and the construction.

pith-pipeline@v0.9.0 · 5729 in / 1471 out tokens · 54149 ms · 2026-05-21T20:12:09.418607+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

every word with kn^6 + 1 repeats contains one of the following patterns: 0^{k+2}, 0011⋯nn, nn⋯1100, 012⋯n012⋯n, ...
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Proof of Theorem 1.2 ... By Theorem 1.1 (Erdős–Szekeres), there is a subword ... monotone.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.