Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.2 — the 312 excess identity and 312-avoidance

Open
PermutationStreams.Parity.Supplement.lemma_5_2

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

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

Let π∈Sn\pi\in S_nπ∈Sn​, Mi=max⁡{π1,…,πi}M_i=\max\{\pi_1,\dots,\pi_i\}Mi​=max{π1​,…,πi​}, and E312(π)=∑i=1nT(Mi−πi)−W(π)E_{312}(\pi)=\sum_{i=1}^nT(M_i-\pi_i)-W(\pi)E312​(π)=∑i=1n​T(Mi​−πi​)−W(π) with T(d)=d(d+1)/2T(d)=d(d+1)/2T(d)=d(d+1)/2. Then

E312(π)=∑i<jπi<πj<Mi(πj−πi).E_{312}(\pi)=\sum_{\substack{i<j\\ \pi_i<\pi_j<M_i}}(\pi_j-\pi_i).E312​(π)=i<jπi​<πj​<Mi​​∑​(πj​−πi​).

Consequently E312(π)≥0E_{312}(\pi)\ge0E312​(π)≥0, and E312(π)=0E_{312}(\pi)=0E312​(π)=0 if and only if π\piπ avoids the pattern 312312312.

Testing whether one integer statistic vanishes therefore decides 312-avoidance; together with Lemma 5.1 it gives the logarithmic-space detector for 312312312.

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

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