§2.2 (sorted pairing) — nonincreasing coefficients against sorted coordinates minimize the sum
ProvedUnequalHuffman.NPC.sorted_pairingcombinatoricsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be integers and integer coordinates (repetitions allowed). If the permutation sorts the coordinates nondecreasingly (), then for every permutation
i.e. pairing the largest coefficient with the smallest coordinate minimizes the sum over all assignments of the coefficients to the leaves.
Source (p. 10): "For a fixed tree and depth, pairing the largest coefficient with the smallest coordinate minimizes the sum over all assignments of those coefficients to the leaves."
Differences from the source:
- generalization: coordinates of the leaves at one depth of a tree (natural numbers) → arbitrary integers z : Fin m → ℤ; reason: the inequality does not use the tree; it specializes to leaf coordinates
- encoding: the sorted pairing; all assignments of the coefficients to the leaves → u antitone in the rank k, a permutation π with z ∘ π monotone; all permutations σ of Fin m; reason: assignments of m coefficients to m leaves are the permutations
Preamble
import Mathlib
Formal statement
namespace UnequalHuffman.NPC
/-- §2.2, "Why the coefficient rows are nonincreasing" (p. 10): for nonincreasing coefficients
`u₁ ≥ ⋯ ≥ u_m` and coordinates `z`, the sorted pairing (the `k`-th largest coefficient with the
`k`-th smallest coordinate, i.e. `z ∘ π` nondecreasing) minimizes `∑_k u_k · z_{σ(k)}` over all
assignments `σ`, with signed coefficients and repeated coordinates allowed. -/
theorem sorted_pairing {m : ℕ} (u : Fin m → ℤ) (hu : Antitone u) (z : Fin m → ℤ)
(π σ : Equiv.Perm (Fin m)) (hπ : Monotone (z ∘ π)) :
∑ k, u k * z (π k) ≤ ∑ k, u k * z (σ k) := by sorry
end UnequalHuffman.NPC
Source
Chandran and Gajjala, Binary Huffman Coding with Unequal Letter Costs Is NP-Complete, arXiv:2611.04444v1, p. 10, §2.2 (unnumbered claim)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.