Documentation

ThreeMajority.AnyStartMajorization

Majorization and Schur-convex observables (BCEKMN17, Section 2.1) #

Majorizes x y (the paper's x ⪰ y): equal total sums, and for every j the sum of the j largest entries of x is at least that of y. It is stated without sorting: every sum of y over a set S is bounded by a sum of x over a set S' of the same size, which is the same as comparing the sums of the |S| largest entries.

SchurConvex φ: an observable of configurations that is monotone for the majorization of the configuration vectors (the paper's Schur-convex functions of c, for the preorder ⪯ on the configuration space 𝒞). Such an observable depends on the configuration only through its sorted configuration vector. The indicator of "at most κ colours" is one of them (schurConvex_numColours_le), which is how the comparison of Theorem 2 controls the number of remaining colours.

def ThreeMajority.Majorizes {ι : Type u_1} [Fintype ι] (x y : ι → ℝ) :

Vector majorization x ⪰ y (BCEKMN17, Section 2.1): equal sums, and the sum of the j largest entries of y is at most that of x for every j, in the sort-free form "every sum of y over a set is bounded by a sum of x over a set of the same size".

Equations
Instances For
    theorem ThreeMajority.Majorizes.refl {ι : Type u_1} [Fintype ι] (x : ι → ℝ) :
    theorem ThreeMajority.Majorizes.trans {ι : Type u_1} [Fintype ι] {x y z : ι → ℝ} (hxy : Majorizes x y) (hyz : Majorizes y z) :
    noncomputable def ThreeMajority.countVec {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) :
    σ → ℝ

    The configuration vector (c_a)_a of a configuration, as a real vector.

    Equations
    Instances For
      def ThreeMajority.SchurConvex {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (φ : (Fin n → σ) → ℝ) :

      A Schur-convex observable of configurations (BCEKMN17, Section 2.1): monotone for the majorization of the configuration vectors.

      Equations
      Instances For
        theorem ThreeMajority.numColours_le_of_majorizes {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] {c c' : Fin n → σ} (h : Majorizes (countVec c) (countVec c')) :

        A configuration whose vector majorizes another one has at most as many colours: the numColours c' largest entries of c' already sum to n, so c has all its mass on as many colours (BCEKMN17, Section 2.3, observation 1 after Lemma 1: consensus is maximal for ⪯).

        theorem ThreeMajority.schurConvex_numColours_le {n : ℕ} {σ : Type u_1} [Fintype σ] [DecidableEq σ] (κ : ℕ) :
        SchurConvex fun (c : Fin n → σ) => if numColours c ≤ κ then 1 else 0

        The indicator of "at most κ colours" is Schur-convex.