Lemma 5.2 — the 312 excess identity and 312-avoidance
OpenPermutationStreams.Parity.Supplement.lemma_5_2complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pattern-avoidancepermutationsstreaming
Let , , and with . Then
Consequently , and if and only if avoids the pattern .
Testing whether one integer statistic vanishes therefore decides 312-avoidance; together with Lemma 5.1 it gives the logarithmic-space detector for .
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
Preamble
import Definitions.Def_PermutationStreams_Parity_Supplement_Patterns import Definitions.Def_PermutationStreams_Parity_Supplement_Statistics
Formal statement
namespace PermutationStreams.Parity.Supplement
open PatternRangeCounting1593.RangeCounting
/-- Braverman–Zamir, STOC 2027 submission #74, Lemma 5.2, p.10. For every permutation `π` of
`[n]`, `E312(π) = ∑_{i<j, π_i < π_j < M_i} (π_j − π_i)`; consequently `E312(π) ≥ 0`, with equality
if and only if `π` avoids `312`. -/
theorem lemma_5_2 (n : ℕ) (π : Equiv.Perm (Fin n)) :
E312 π = ∑ q ∈ (Finset.univ : Finset (Fin n × Fin n)).filter
(fun q => q.1 < q.2 ∧ val π q.1 < val π q.2 ∧ val π q.2 < prefMax π q.1),
(val π q.2 - val π q.1) ∧
0 ≤ E312 π ∧ (E312 π = 0 ↔ Avoids pat312 π) := 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), §5.2 pp. 9–10, Lemma 5.2