Lemma 6.3 — a -state detector for every fixed pattern
OpenPermutationStreams.Parity.Supplement.lemma_6_3complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pattern-avoidancepermutationsstreaming
Let be a pattern and let be a real constant with for every integer , where is the set of permutations of avoiding (Theorem 6.2, of Marcus and Tardos, provides such a constant ). Then for every there is a deterministic one-pass streaming algorithm detecting in permutations of with at most
states. In particular it uses at most bits, which is .
This gives the linear upper bound in the second case of the pattern dichotomy.
Differences from the source:
- encoding: positions and values in [n] = {1,…,n}, π ∈ S_n → Equiv.Perm (Fin n), with position i and value π i read as i + 1 and π i + 1; reason: every formula is evaluated on the shifted 1-based values; same instances
- encoding: 'a deterministic one-pass streaming algorithm … with at most … states' → a clock-free OnePassAlg n S Bool with Fintype.card S ≤ 1 + (1 + C)^n, required correct only on permutations of [n]; reason: the paper's automaton (states q_w, q_yes) sees only the state and the arriving value, and bits are the logarithm of the state count
- reading: C_σ, the constant of Theorem 6.2 → every real C ≥ 1 with |Av_t(σ)| ≤ C^t for all t ≥ 0; reason: Theorem 6.2 only asserts that such a constant exists and the lemma uses nothing else about it
- generalization: it uses O_σ(n) bits → it uses at most ⌈n·log₂(1 + C)⌉ + 1 bits; reason: the explicit bound is what the lemma's proof gives by taking the logarithm of the state count, and it implies O_σ(n) with the σ-dependent constant log₂(1 + C) + 2
Preamble
import Definitions.Def_PermutationStreams_Parity_Supplement_Patterns
Formal statement
namespace PermutationStreams.Parity.Supplement
open PatternRangeCounting1593.RangeCounting
/-- Braverman–Zamir, STOC 2027 submission #74, Lemma 6.3, p.14, for the constant of Theorem 6.2:
for every pattern `σ ∈ S_k` and every real `C ≥ 1` with `|Av_t(σ)| ≤ C^t` for all `t ≥ 0`, and every
`n`, some deterministic clock-free one-pass algorithm detects `σ` in permutations of `[n]` with at
most `1 + (1 + C)^n` states; in particular it uses at most `⌈n log₂(1 + C)⌉ + 1 = O_σ(n)` bits. -/
theorem lemma_6_3 {k : ℕ} (σ : Equiv.Perm (Fin k)) (C : ℝ) (hC : 1 ≤ C)
(hAv : ∀ t : ℕ, ((Av t σ).card : ℝ) ≤ C ^ t) (n : ℕ) :
∃ (S : Type) (_ : Fintype S) (A : OnePassAlg n S Bool),
A.Detects σ ∧ (Fintype.card S : ℝ) ≤ 1 + (1 + C) ^ n ∧
A.UsesBits (⌈(n : ℝ) * Real.logb 2 (1 + C)⌉₊ + 1) := by sorry
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), §6.1 p. 14, Lemma 6.3 (with Theorem 6.2, p. 14)