A permutation of finite-sample ranks records every strict comparison
ProvedStabilityDichotomies.Bijunctive.rank_permutation_encodes_strict_sample_orderIf the numbers of strictly smaller entries in a finite real sample form a permutation of all possible ranks, then the sample values are distinct and comparing any two values is equivalent to comparing their ranks. In the cutoff-order analysis, this translates order-cell ranks directly into priority-versus-cutoff decisions.
Preamble
import Mathlib open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter Function
Formal statement
theorem StabilityDichotomies.Bijunctive.rank_permutation_encodes_strict_sample_order (n : ℕ) (x : Fin n → ℝ) (p : Equiv.Perm (Fin n))
(h : ∀ i, (Finset.univ.filter (fun j : Fin n => x j < x i)).card = (p i).val) :
∀ i j, p i < p j ↔ x i < x j := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, cutoff and priority order.