Lemma 1 — the splitting V(C, k) consists of chains with properties (1.1)–(1.5)
ProvedAKSSorting.Core.splitV_speccombinatoricsp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1sorting-networks
Let be a chain on level with , let , and let , , be the splitting of Lemma 1 (one register of every leaf set of moved up to a level between and , two of them to each node of level ). Then is a chain for every , and:
- (1.1) ;
- (1.2) for ;
- (1.3) for , , and for ;
- (1.4) for every node with ,
- (1.5) for every of level ,
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: is a function on Fin (2^k). In (1.4) the paper's free index is . is evaluated at node ; together with the chain property this is the paper's "for some (all) ".
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.