Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — the splitting V(C, k) consists of chains with properties (1.1)–(1.5)

Proved
AKSSorting.Core.splitV_spec

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1sorting-networks

Let CCC be a chain on level iii with N(C)≥2N(C)\ge 2N(C)≥2, let 0≤j<i0\le j<i0≤j<i, and let V(C,k)V(C,k)V(C,k), 0≤k≤i0\le k\le i0≤k≤i, be the splitting of Lemma 1 (one register of every leaf set of CCC moved up to a level between jjj and i−1i-1i−1, two of them to each node of level jjj). Then V(C,k)V(C,k)V(C,k) is a chain for every 0≤k≤i0\le k\le i0≤k≤i, and:

  1. (1.1) l(V(C,k))=kl(V(C,k))=kl(V(C,k))=k;
  2. (1.2) (∪V(C,k))∩(∪V(C,k′))=∅(\cup V(C,k))\cap(\cup V(C,k'))=\emptyset(∪V(C,k))∩(∪V(C,k′))=∅ for k≠k′k\ne k'k=k′;
  3. (1.3) N(V(C,k))=1N(V(C,k))=1N(V(C,k))=1 for j<k<ij<k<ij<k<i, N(V(C,j))=2N(V(C,j))=2N(V(C,j))=2, and N(V(C,k))=0N(V(C,k))=0N(V(C,k))=0 for 0≤k<j0\le k<j0≤k<j;
  4. (1.4) for every node t′t't′ with j≤l(t′)≤ij\le l(t')\le ij≤l(t′)≤i,
V(C,l(t′))(t′)⊆⋃l(t)=i, t≺t′C(t);V(C,l(t'))(t')\subseteq\bigcup_{l(t)=i,\ t\prec t'}C(t);V(C,l(t′))(t′)⊆l(t)=i, t≺t′⋃​C(t);
  1. (1.5) for every ttt of level iii,
∣ C(t)∩⋃0≤k<i(∪V(C,k))∣=1.\Bigl|\,C(t)\cap\bigcup_{0\le k<i}\bigl(\cup V(C,k)\bigr)\Bigr|=1 .​C(t)∩0≤k<i⋃​(∪V(C,k))​=1.

The splitting moves exactly one register out of each leaf set, and only to ancestors of that leaf.

Formalization Note (1.1) is carried by the type: V(C,k)V(C,k)V(C,k) is a function on Fin (2^k). In (1.4) the paper's free index kkk is l(t′)l(t')l(t′). N(⋅)N(\cdot)N(⋅) is evaluated at node 000; together with the chain property this is the paper's "for some (all) xxx".

Preamble
import Mathlib
import Definitions.Def_AKSSorting_Core_IsChain
import Definitions.Def_AKSSorting_Core_splitV
Formal statement
namespace AKSSorting.Core

/-- Lemma 1 (Ajtai–Komlós–Szemerédi 1983, pp. 3–4). Let `C` be a chain on level `i`,
`0 ≤ j < i`, and `N(C) ≥ 2`. Then `V(C, k)` is a chain for all `0 ≤ k ≤ i` ((1.1),
`l(V(C, k)) = k`, is carried by the type `Fin (2 ^ k) → Finset R`), and
* (1.2) `∪V(C, k)` and `∪V(C, k')` are disjoint for `k ≠ k'`;
* (1.3) `N(V(C, k)) = 1` for `j < k < i`, `N(V(C, j)) = 2`, `N(V(C, k)) = 0` for `k < j`;
* (1.4) for every node `t'` with `j ≤ l(t') ≤ i`,
  `V(C, l(t'))(t') ⊆ ⋃_{l(t) = i, t ≺ t'} C(t)`;
* (1.5) for every `t ∈ Dom(C)`, `|C(t) ∩ ⋃_{0 ≤ k < i} ∪V(C, k)| = 1`. -/
theorem splitV_spec {R : Type} [LinearOrder R] {i j : ℕ} (C : Fin (2 ^ i) → Finset R)
    (hC : IsChain C) (hj : j < i) (hN : 2 ≤ chainN C) :
    (∀ k ≤ i, IsChain (splitV C j k)) ∧
    (∀ k ≤ i, ∀ k' ≤ i, k ≠ k' →
      Disjoint (chainUnion (splitV C j k)) (chainUnion (splitV C j k'))) ∧
    ((∀ k, j < k → k < i → chainN (splitV C j k) = 1) ∧
      chainN (splitV C j j) = 2 ∧
      (∀ k, k < j → chainN (splitV C j k) = 0)) ∧
    (∀ k, j ≤ k → k ≤ i → ∀ t' : Fin (2 ^ k), splitV C j k t' ⊆ subtreeUnion C k t') ∧
    (∀ t : Fin (2 ^ i),
      (C t ∩ (Finset.range i).biUnion fun k => chainUnion (splitV C j k)).card = 1) := by sorry

end AKSSorting.Core
Source
Ajtai, Komlós, Szemerédi, Sorting in c log n parallel steps, Combinatorica 3 (1983), pp. 3-4, Lemma 1
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

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