Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Pattern detection, monotone patterns, the patterns 312 and 231, and Sσ(n)S_\sigma(n)Sσ​(n)

Definition
PermutationStreams_Parity_Supplement_Patterns

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pattern-avoidancepermutationsstreaming

Pattern containment and avoidance are the published notions: a permutation π∈Sn\pi\in S_nπ∈Sn​ contains σ∈Sk\sigma\in S_kσ∈Sk​ if some positions a1<⋯<aka_1<\dots<a_ka1​<⋯<ak​ carry values πa1,…,πak\pi_{a_1},\dots,\pi_{a_k}πa1​​,…,πak​​ order-isomorphic to σ\sigmaσ, and avoids σ\sigmaσ otherwise.

  1. A pattern σ∈Sk\sigma\in S_kσ∈Sk​ is monotone if it is the identity i↦ii\mapsto ii↦i or the reversal i↦k+1−ii\mapsto k+1-ii↦k+1−i.
  2. 312312312 and 231231231 are the patterns of S3S_3S3​ in one-line notation (3,1,2)(3,1,2)(3,1,2) and (2,3,1)(2,3,1)(2,3,1).
  3. A one-pass algorithm with Boolean output detects σ\sigmaσ in permutations of [n][n][n] if on every π∈Sn\pi\in S_nπ∈Sn​ it answers true exactly when π\piπ contains σ\sigmaσ. Nothing is required on inputs that are not permutations (the promise).
  4. Sσ(n)S_\sigma(n)Sσ​(n) is the minimum number of bits of a deterministic one-pass algorithm that detects σ\sigmaσ in permutations of [n][n][n]:
Sσ(n)=min⁡{s∈N: ∃ a detecting algorithm with at most 2s states}.S_\sigma(n)=\min\{s\in\mathbb N:\ \exists\ \text{a detecting algorithm with at most }2^s\text{ states}\}.Sσ​(n)=min{s∈N: ∃ a detecting algorithm with at most 2s states}.

These are the objects of the paper's dichotomy theorem for fixed patterns.

Formalization Note Sσ(n)S_\sigma(n)Sσ​(n) is an sInf over ℕ. The set is nonempty (an automaton remembering the whole prefix detects σ\sigmaσ); if it were empty the value 000 would only falsify lower bounds, so no statement becomes vacuously true. Permutations are Equiv.Perm (Fin k); the reversal is Fin.revPerm.

Definition code
import Definitions.Def_PermutationStreams_Parity_Supplement_OnePass
import Definitions.Def_PatternRangeCounting1593_RangeCounting_Perm

namespace PermutationStreams.Parity.Supplement

open PatternRangeCounting1593.RangeCounting

/-- §3 p.5: a pattern `σ ∈ S_k` is monotone if it is increasing (the identity of `[k]`) or
decreasing (`i ↦ k + 1 - i`, which is `Fin.revPerm` in the 0-based encoding). -/
def IsMonotonePattern {k : ℕ} (σ : Equiv.Perm (Fin k)) : Prop :=
  σ = 1 ∨ σ = Fin.revPerm

/-- The pattern `312` (one-line notation `σ₁ = 3, σ₂ = 1, σ₃ = 2`), 0-based: `0 ↦ 2, 1 ↦ 0, 2 ↦ 1`. -/
def pat312 : Equiv.Perm (Fin 3) where
  toFun := ![2, 0, 1]
  invFun := ![1, 2, 0]
  left_inv := by decide
  right_inv := by decide

/-- The pattern `231` (one-line notation `σ₁ = 2, σ₂ = 3, σ₃ = 1`), 0-based: `0 ↦ 1, 1 ↦ 2, 2 ↦ 0`. -/
def pat231 : Equiv.Perm (Fin 3) where
  toFun := ![1, 2, 0]
  invFun := ![2, 0, 1]
  left_inv := by decide
  right_inv := by decide

/-- §1.2 p.2: a one-pass algorithm with Boolean output detects `σ` in permutations of `[n]` if on
every permutation `π` of `[n]` it answers `true` exactly when `π` contains `σ`. Inputs that are not
permutations (the promise) impose no requirement. -/
def OnePassAlg.Detects {n k : ℕ} {S : Type} (A : OnePassAlg n S Bool)
    (σ : Equiv.Perm (Fin k)) : Prop :=
  ∀ π : Equiv.Perm (Fin n), A.run π = true ↔ Contains σ π

/-- §1.2 p.2: `S_σ(n)`, the minimum number of bits used by a deterministic one-pass algorithm that
detects `σ` in permutations of `[n]`: the least `s` such that some detecting algorithm has at most
`2^s` states. (The set is nonempty for every `n`; were it empty, the value `0` would only make
lower bounds on `S_σ(n)` false, never true.) -/
noncomputable def spaceComplexity {k : ℕ} (σ : Equiv.Perm (Fin k)) (n : ℕ) : ℕ :=
  sInf {s : ℕ | ∃ (S : Type) (_ : Fintype S) (A : OnePassAlg n S Bool),
    A.Detects σ ∧ A.UsesBits s}

end PermutationStreams.Parity.Supplement
Source
Mark Braverman, Or Zamir, STOC 2027 submission #74 (October 2026), Parity and Pattern Detection in Permutation Streams, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/74.pdf (SHA-256 3f0b683e25232855e98d1caa358e35f2670633688d8a799e4d01a207aa5600ea), §1.2 p. 2 (S_σ(n)), §3 p. 5 (order-isomorphism, containment, avoidance, monotone patterns), §5 p. 9 (patterns 312, 231)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me