Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.1.1 — one transposition of a reordering increases majorization

Proved
PalmQueueing.Ordering.majorization_interchange

by mikedeng1 · Oct 2, 2026 · Mathlib 0df444a (Lean v4.33.1)

majorizationprobabilityqueueingstatisticsstochastic-ordering

Lemma 4.1.1, the first of "two technical lemmas on majorization". Let x1≤⋯≤xnx_1 \le \dots \le x_nx1​≤⋯≤xn​ and y1≤⋯≤yny_1 \le \dots \le y_ny1​≤⋯≤yn​ be real numbers. Let γ\gammaγ be a permutation on {1,…,n}\{1,\dots,n\}{1,…,n} such that there exist some i,ji,ji,j, 1≤i<j≤n1 \le i < j \le n1≤i<j≤n, with γ(i)>γ(j)\gamma(i) > \gamma(j)γ(i)>γ(j), and let γ′\gamma'γ′ be obtained from γ\gammaγ by interchanging its values on iii and jjj. Then

(yγ′−x)≺(yγ−x).(4.1.16)(y_{\gamma'} - x) \prec (y_\gamma - x) . \tag{4.1.16}(yγ′​−x)≺(yγ​−x).(4.1.16)

Undoing one inversion of γ\gammaγ makes the difference vector less spread out in the majorization order. Iterating drives γ\gammaγ to the identity — which is Lemma 4.1.2, and which is what makes FIFO, the discipline whose permutation is the identity, the extremal one.

The proof is a convexity argument. Since yγ(i)−yγ(j)≥0y_{\gamma(i)} - y_{\gamma(j)} \ge 0yγ(i)​−yγ(j)​≥0 and xi−xj≤0x_i - x_j \le 0xi​−xj​≤0 there is 0≤ϵ≤10 \le \epsilon \le 10≤ϵ≤1 with ϵ(yγ(i)−yγ(j))+(1−ϵ)(xi−xj)=0\epsilon(y_{\gamma(i)} - y_{\gamma(j)}) + (1-\epsilon)(x_i - x_j) = 0ϵ(yγ(i)​−yγ(j)​)+(1−ϵ)(xi​−xj​)=0, and the two coordinates in which yγ′−xy_{\gamma'} - xyγ′​−x differs from yγ−xy_\gamma - xyγ​−x are then convex combinations of the corresponding two. So yγ′−xy_{\gamma'} - xyγ′​−x lies in the convex hull of the permutations of yγ−xy_\gamma - xyγ​−x, which is majorization by Property 4.1.1.

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Ordering_PartialOrders

/-!
# Lemma 4.1.1: one transposition of a reordering increases majorization (§4.1.3, p.266)
-/
Formal statement
namespace PalmQueueing.Ordering

/-- **Lemma 4.1.1** (p.266), the first of "two technical lemmas on majorization".

Let `x₁ ≤ x₂ ≤ … ≤ xₙ` and `y₁ ≤ y₂ ≤ … ≤ yₙ` be real numbers. Let `γ` be a permutation on
`{1, 2, …, n}` such that there exist some `i, j`, `1 ≤ i < j ≤ n`, with `γ(i) > γ(j)`, and let
`γ'` be the permutation obtained from `γ` by interchanging the values of `γ` on `i` and `j`:
`γ'(i) = γ(j)`, `γ'(j) = γ(i)`, and `γ'(k) = γ(k)` for `k ≠ i`, `k ≠ j`. Then

`(4.1.16)  (y_{γ'} − x) ≺ (y_γ − x)`.

Undoing one inversion of `γ` makes the difference vector `y_γ − x` **less spread out** in the
majorization order. Iterating drives `γ` to the identity, which is what Lemma 4.1.2 records and
what makes FIFO — the discipline whose permutation is the identity — the extremal one.

The proof is a convexity argument: since `y_{γ(i)} − y_{γ(j)} ≥ 0` and `x_i − x_j ≤ 0`, there is
`0 ≤ ε ≤ 1` with `ε(y_{γ(i)} − y_{γ(j)}) + (1 − ε)(x_i − x_j) = 0`, and the two coordinates of
`y_{γ'} − x` that differ from `y_γ − x` are then convex combinations of the corresponding two of
`y_γ − x`. So `y_{γ'} − x` lies in the convex hull of the permutations of `y_γ − x`, which is
majorization. -/
theorem majorization_interchange {n : ℕ} (x y : Fin n → ℝ)
    (hx : Monotone x) (hy : Monotone y)
    (g : Equiv.Perm (Fin n)) (i j : Fin n) (hij : i < j) (hgij : g j < g i)
    (g' : Equiv.Perm (Fin n))
    (hg'i : g' i = g j) (hg'j : g' j = g i)
    (hg'k : ∀ k : Fin n, k ≠ i → k ≠ j → g' k = g k) :
    Majorized (fun k => y (g' k) - x k) (fun k => y (g k) - x k) := by sorry

end PalmQueueing.Ordering
Source
Baccelli & Bremaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed., Springer 2003, p. 266, Lemma 4.1.1
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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