Pattern detection, monotone patterns, the patterns 312 and 231, and
DefinitionPermutationStreams_Parity_Supplement_Patternscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pattern-avoidancepermutationsstreaming
Pattern containment and avoidance are the published notions: a permutation contains if some positions carry values order-isomorphic to , and avoids otherwise.
- A pattern is monotone if it is the identity or the reversal .
- and are the patterns of in one-line notation and .
- A one-pass algorithm with Boolean output detects in permutations of if on every it answers true exactly when contains . Nothing is required on inputs that are not permutations (the promise).
- is the minimum number of bits of a deterministic one-pass algorithm that detects in permutations of :
These are the objects of the paper's dichotomy theorem for fixed patterns.
Formalization Note is an sInf over ℕ. The set is nonempty (an automaton remembering the whole prefix detects ); if it were empty the value 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)