Lemma 4 — one round of expander comparisons is an ε-halver
ProvedAKSSorting.Core.halver_propertyLet and be disjoint sets of registers, , and let be a expander on for some . Let be the set of elementary steps "if the content of is greater than the content of , exchange them", one for each edge of with , . Start from an injective assignment of contents to registers and perform all steps of , each exactly once, in an arbitrary order. Write for the set of final contents of the registers in . Then:
- if is a lower section of with , then
- if is an upper section of with , then .
So after one round, all but an -fraction of any initial segment of small elements sits in , and symmetrically for large elements in . This approximate halving is the only use of expanders in the AKS network.
Formalization Note The order of the steps is a list steps whose members are exactly the pairs with , adjacent in , without repetitions; the conclusion must hold for every such list. The lemma is stated for every expander with any degree bound, which covers the paper's fixed choice . Contents come from an arbitrary linearly ordered type and the initial position is injective, as in the paper's "one-to-one map of onto ".
import Mathlib import Definitions.Def_AKSSorting_Core_compareExchange import Definitions.Def_AKSSorting_Core_IsExpander import Definitions.Def_AKSSorting_Core_IsLowerSection
namespace AKSSorting.Core
/-- Lemma 4 (Ajtai–Komlós–Szemerédi 1983, p. 7; proved on p. 9). Let `A, B` be disjoint sets of
registers, `ε > 0`, and `G` any `⟨k, ε⟩` expander on `⟨A, B⟩`. Perform every elementary step
of `E_ε(A, B)` — for every edge `{a, b}` of `G` with `a ∈ A`, `b ∈ B`, the compare-exchange that
leaves the smaller content in `a` — exactly once, in an arbitrary order `steps`, starting from
the position `F`. With `F'` the resulting position:
* if `S` is a lower section of `Cont(A ∪ B)` with `|S| ≤ |A|`, then `|S − Cont(A)| ≤ ε|S|`;
* if `S` is an upper section of `Cont(A ∪ B)` with `|S| ≤ |B|`, then `|S − Cont(B)| ≤ ε|S|`. -/
theorem halver_property {R : Type} [DecidableEq R] {α : Type} [LinearOrder α]
(A B : Finset R) (hAB : Disjoint A B) (ε : ℝ) (hε : 0 < ε) (k : ℕ) (G : SimpleGraph R)
(hG : IsExpander G A B k ε) (steps : List (R × R))
(hsteps : ∀ p : R × R, p ∈ steps ↔ (p.1 ∈ A ∧ p.2 ∈ B ∧ G.Adj p.1 p.2))
(hnodup : steps.Nodup) (F : R → α) (hF : Function.Injective F) :
let F' := steps.foldl (fun x p => compareExchange p.1 p.2 x) F
(∀ S : Finset α, IsLowerSection ((A ∪ B).image F') S → S.card ≤ A.card →
((S \ A.image F').card : ℝ) ≤ ε * S.card) ∧
(∀ S : Finset α, IsUpperSection ((A ∪ B).image F') S → S.card ≤ B.card →
((S \ B.image F').card : ℝ) ≤ ε * S.card) := by sorry
end AKSSorting.Core
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.