AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_fractional_assignment_col_sum

theoremverified

Every item is fully eaten under probabilistic serial: the column sums of the probabilistic serial assignment are 1.

Statement

theorem probabilistic_serial_fractional_assignment_col_sum (n : ℕ) (hn : 1 ≤ n) (pref : Fin n → Equiv.Perm (Fin n)) (j : Fin n) : ∑ i, probabilistic_serial_fractional_assignment n pref i j = 1
Source
step towards probabilistic_serial_line_metric_sharp_linear_distortion
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The probabilistic serial (PS) mechanism executes a sequence of phases, where in each phase agents eat their most preferred available item at unit rate until some item is exhausted. By induction on the phase index, an invariant is maintained: for every item, its remaining capacity plus the total fraction consumed so far always equals 1. Because capacities remain non-negative, the total fraction consumed of each item after n phases is at most 1. Since every agent receives a total allocation of 1, the sum of all item consumptions must equal n; because n quantities each at most 1 sum to n, every item must be fully consumed with a column sum of exactly 1.

  1. The state after k + 1 phases is the result of applying one phase transition to the state after k phases.

    The state after k phases is defined as the k-fold iterate of the phase function starting from the initial state (where all capacities are 1 and all consumed shares are 0). By `Function.iterate_succ_apply'`, the (k+1)-th iterate is the phase function applied to the k-th iterate.

    lines 40–43

    uses Function.iterate_succ_apply'

      show (probabilistic_serial_phase n pref)^[k+1] (fun x => 1, fun x x_1 => 0) =
          probabilistic_serial_phase n pref
            ((probabilistic_serial_phase n pref)^[k] (fun x => 1, fun x x_1 => 0))
      rw [Function.iterate_succ_apply']
  2. In any phase starting with non-negative item capacities, the amount of item j consumed during the phase does not exceed its remaining capacity.

    We split into cases on whether any agent is currently eating item j. If cnt(j) = 0, the consumption is T * 0 = 0, which is at most the remaining capacity s.1(j) by non-negativity. If cnt(j) > 0, item j belongs to the non-empty set S of actively eaten items. The phase duration T is defined as the infimum of s.1(j') / cnt(j') over all j' ∈ S, so T ≤ s.1(j) / cnt(j). Multiplying both sides by the positive quantity cnt(j) yields T * cnt(j) ≤ s.1(j).

    lines 50–80

    uses mul_zero, Nat.pos_of_ne_zero, Finset.mem_filter, Finset.mem_univ, dif_pos, Finset.inf'_le, mul_le_mul_of_nonneg_right, le_of_lt, div_mul_cancel₀, ne_of_gt

      by_cases hc : probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j = 0
      · rw [hc]; push_cast; rw [mul_zero]; exact hpos j
      · have hcpos : 0 < probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j :=
          Nat.pos_of_ne_zero hc
        have hmem : j ∈ probabilistic_serial_fractional_assignment_col_sum_S n pref s := by
          rw [probabilistic_serial_fractional_assignment_col_sum_S, Finset.mem_filter]
          exact ⟨Finset.mem_univ _, hcpos⟩
        have hcastpos : (0:ℝ) <
            (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by
          exact_mod_cast hcpos
        have hS : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).Nonempty :=
          ⟨j, hmem⟩
        have hT : probabilistic_serial_fractional_assignment_col_sum_T n pref s =
            (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS
              (fun j => s.1 j /
                (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) := by
          simp only [probabilistic_serial_fractional_assignment_col_sum_T]; exact dif_pos hS
        have hle : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS
              (fun j => s.1 j /
                (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) ≤
            s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) :=
          Finset.inf'_le _ hmem
        rw [hT]
        calc (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS
                (fun j => s.1 j /
                  (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) *
              (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)
            ≤ (s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) *
              (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) :=
              mul_le_mul_of_nonneg_right hle (le_of_lt hcastpos)
          _ = s.1 j := div_mul_cancel₀ (s.1 j) (ne_of_gt hcastpos)
  3. At every step k, the remaining capacity of each item is non-negative.

    By induction on k. At step 0, all item capacities are initialized to 1, which is non-negative. For the induction step, the capacity of item j at step k + 1 is its capacity at step k minus T * cnt(j). By the previous lemma (`probabilistic_serial_fractional_assignment_col_sum_T_mul_le`) and the induction hypothesis, T * cnt(j) does not exceed the capacity at step k, so the difference remains non-negative.

    lines 93–110

    uses probabilistic_serial_fractional_assignment_col_sum_state_succ, probabilistic_serial_fractional_assignment_col_sum_phase_eq, probabilistic_serial_fractional_assignment_col_sum_T_mul_le

      induction k with
      | zero => intro j; simp [probabilistic_serial_fractional_assignment_col_sum_cap,
          probabilistic_serial_phase_state]
      | succ k ih =>
          intro j
          have hcap : probabilistic_serial_fractional_assignment_col_sum_cap n pref (k+1) j =
              probabilistic_serial_fractional_assignment_col_sum_cap n pref k j -
                probabilistic_serial_fractional_assignment_col_sum_T n pref
                  (probabilistic_serial_phase_state n pref k) *
                (probabilistic_serial_fractional_assignment_col_sum_cnt n pref
                  (probabilistic_serial_phase_state n pref k) j : ℝ) := by
            simp only [probabilistic_serial_fractional_assignment_col_sum_cap,
              probabilistic_serial_fractional_assignment_col_sum_state_succ,
              probabilistic_serial_fractional_assignment_col_sum_phase_eq]
          have hle := probabilistic_serial_fractional_assignment_col_sum_T_mul_le n pref
            (probabilistic_serial_phase_state n pref k) (fun j => ih j) j
          rw [hcap]
          linarith
  4. In a single phase, the total fraction of item j consumed across all agents increases by T * cnt(j).

    Unfolding the phase update, agent i receives an additional share T of item j if agent i eats item j, and 0 otherwise. Distributing the sum over agents, we factor out T from the sum of indicators for whether agent i eats item j. By `Finset.sum_boole`, the sum of these indicators is precisely the count of agents eating item j, cnt(j).

    lines 119–141

    uses probabilistic_serial_fractional_assignment_col_sum_phase_eq, Finset.sum_add_distrib, Finset.sum_congr, Finset.mul_sum, Finset.sum_boole

      rw [probabilistic_serial_fractional_assignment_col_sum_phase_eq]
      simp only [Finset.sum_add_distrib]
      congr 1
      calc (∑ x, if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j
            then probabilistic_serial_fractional_assignment_col_sum_T n pref s else (0:ℝ))
          = ∑ x, probabilistic_serial_fractional_assignment_col_sum_T n pref s *
              (if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j
                then (1:ℝ) else 0) := by
            apply Finset.sum_congr rfl
            intro x _
            by_cases hx : probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j
            · simp [hx]
            · simp [hx]
        _ = probabilistic_serial_fractional_assignment_col_sum_T n pref s *
              (∑ x, (if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j
                then (1:ℝ) else 0)) := by
            rw [Finset.mul_sum]
        _ = probabilistic_serial_fractional_assignment_col_sum_T n pref s *
              (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by
            congr 1
            exact Finset.sum_boole
              (fun i => probabilistic_serial_fractional_assignment_col_sum_eats n pref s i j)
              Finset.univ
  5. At every step k, the remaining capacity of item j plus the total fraction of item j consumed across all agents equals 1.

    By induction on k. For k = 0, the initial capacity is 1 and the total fraction consumed is 0, summing to 1. In the inductive step from k to k + 1, the capacity of item j decreases by T * cnt(j) while the total consumed fraction increases by T * cnt(j) (by `probabilistic_serial_fractional_assignment_col_sum_col_phase`). The two changes cancel, preserving the sum of 1.

    lines 147–171

    uses probabilistic_serial_fractional_assignment_col_sum_state_succ, probabilistic_serial_fractional_assignment_col_sum_phase_eq, probabilistic_serial_fractional_assignment_col_sum_col_phase

      induction k with
      | zero => simp [probabilistic_serial_fractional_assignment_col_sum_cap,
          probabilistic_serial_fractional_assignment_col_sum_col, probabilistic_serial_phase_state]
      | succ k ih =>
          have hcap : probabilistic_serial_fractional_assignment_col_sum_cap n pref (k+1) j =
              probabilistic_serial_fractional_assignment_col_sum_cap n pref k j -
                probabilistic_serial_fractional_assignment_col_sum_T n pref
                  (probabilistic_serial_phase_state n pref k) *
                (probabilistic_serial_fractional_assignment_col_sum_cnt n pref
                  (probabilistic_serial_phase_state n pref k) j : ℝ) := by
            simp only [probabilistic_serial_fractional_assignment_col_sum_cap,
              probabilistic_serial_fractional_assignment_col_sum_state_succ,
              probabilistic_serial_fractional_assignment_col_sum_phase_eq]
          have hcol : probabilistic_serial_fractional_assignment_col_sum_col n pref (k+1) j =
              probabilistic_serial_fractional_assignment_col_sum_col n pref k j +
                probabilistic_serial_fractional_assignment_col_sum_T n pref
                  (probabilistic_serial_phase_state n pref k) *
                (probabilistic_serial_fractional_assignment_col_sum_cnt n pref
                  (probabilistic_serial_phase_state n pref k) j : ℝ) := by
            simp only [probabilistic_serial_fractional_assignment_col_sum_col,
              probabilistic_serial_fractional_assignment_col_sum_state_succ]
            exact probabilistic_serial_fractional_assignment_col_sum_col_phase n pref
              (probabilistic_serial_phase_state n pref k) j
          rw [hcap, hcol]
          linarith [ih]
  6. For every item j, the column sum of the final probabilistic serial assignment is at most 1.

    After n phases, the conservation invariant (`probabilistic_serial_fractional_assignment_col_sum_col_form`) gives cap(n, j) + col(n, j) = 1. Since capacity is non-negative (`probabilistic_serial_fractional_assignment_col_sum_cap_nonneg`), the column sum col(n, j) = 1 - cap(n, j) is at most 1.

    lines 175–182

    uses probabilistic_serial_fractional_assignment_col_sum_col_form, probabilistic_serial_fractional_assignment_col_sum_cap_nonneg

      let c : Fin n → ℝ := fun j => ∑ i, probabilistic_serial_fractional_assignment n pref i j
      have hle : ∀ j, c j ≤ 1 := by
        intro j
        have hinv := probabilistic_serial_fractional_assignment_col_sum_col_form n pref n j
        have hnn := probabilistic_serial_fractional_assignment_col_sum_cap_nonneg n pref n j
        have e : probabilistic_serial_fractional_assignment_col_sum_col n pref n j = c j := rfl
        rw [e] at hinv
        linarith
  7. The sum of all column sums of the assignment matrix equals n.

    Summing all column sums corresponds to summing all entries of the assignment matrix. Exchanging the order of summation (`Finset.sum_comm`) rewrites this as the sum over all n agents of their row sums. Since every agent's row sum is 1 (`probabilistic_serial_fractional_assignment_row_sum`), the total sum across all n agents is n.

    lines 183–188

    uses probabilistic_serial_fractional_assignment_row_sum, Finset.sum_comm

      have hrow : ∀ i, ∑ j, probabilistic_serial_fractional_assignment n pref i j = 1 :=
        fun i => probabilistic_serial_fractional_assignment_row_sum n hn pref i
      have htotal : ∑ j, c j = (n:ℝ) := by
        simp only [c]
        rw [Finset.sum_comm]
        simp [hrow]
  8. Every column sum equals 1: every item is fully consumed.

    Subtracting the total sum of column sums from n gives ∑_j (1 - c(j)) = n - n = 0. Since each column sum satisfies c(j) ≤ 1, each term 1 - c(j) is non-negative. A sum of non-negative real numbers is zero if and only if each term is zero (`Finset.sum_eq_zero_iff_of_nonneg`). Hence 1 - c(j) = 0, proving c(j) = 1 for every item j.

    lines 189–197

    uses Finset.sum_sub_distrib, Finset.sum_eq_zero_iff_of_nonneg, Finset.mem_univ

      have hd : ∑ j, (1 - c j) = 0 := by
        rw [Finset.sum_sub_distrib, htotal]
        simp
      have hnn : ∀ j ∈ (Finset.univ : Finset (Fin n)), 0 ≤ 1 - c j := by
        intro j _; linarith [hle j]
      have hz := (Finset.sum_eq_zero_iff_of_nonneg (s := Finset.univ) hnn).mp hd
      have hj := hz j (Finset.mem_univ j)
      show c j = 1
      linarith
Function.iterate_succ_apply'
Iterating a function n + 1 times equals applying the function once to the n-th iterate.
mul_zero
Multiplying any element by zero yields zero.
Nat.pos_of_ne_zero
A natural number is strictly positive if and only if it is non-zero.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the filtering predicate.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
dif_pos
A dependent if-then-else expression reduces to its 'then' branch when the condition is true.
Finset.inf'_le
The infimum of a function over a non-empty finite set is less than or equal to the function value at any element of the set.
mul_le_mul_of_nonneg_right
Multiplying both sides of an inequality by a non-negative value on the right preserves the inequality.
le_of_lt
A strict inequality implies the corresponding non-strict inequality.
div_mul_cancel₀
Dividing by a non-zero element and then multiplying by that element yields the original numerator.
ne_of_gt
If a is strictly greater than b, then a is not equal to b.
probabilistic_serial_fractional_assignment_col_sum_state_succ
The state of the probabilistic serial algorithm at step k + 1 is obtained by applying one phase update to the state at step k.
probabilistic_serial_fractional_assignment_col_sum_phase_eq
Unfolds the definition of a single phase transition, updating capacities by subtracting T * cnt and updating consumed shares by adding T for active agent-item pairs.
probabilistic_serial_fractional_assignment_col_sum_T_mul_le
In any phase starting with non-negative item capacities, the total consumption T * cnt(j) of item j during the phase cannot exceed its remaining capacity.
Finset.sum_add_distrib
The sum of a pointwise sum of two functions over a finite set equals the sum of their individual sums.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree at every index.
Finset.mul_sum
A constant factor can be factored out of or distributed into a finite sum.
Finset.sum_boole
The sum of an indicator (0-1) function over a finite set equals the cardinality of the subset satisfying the condition.
probabilistic_serial_fractional_assignment_col_sum_col_phase
The sum across all agents of the shares of item j consumed increases during one phase by exactly T * cnt(j).
probabilistic_serial_fractional_assignment_col_sum_col_form
At every step k, the remaining capacity of item j plus the total fraction of item j consumed so far equals 1.
probabilistic_serial_fractional_assignment_col_sum_cap_nonneg
At every step k, the remaining capacity of every item is non-negative.
probabilistic_serial_fractional_assignment_row_sum
Under the probabilistic serial mechanism, every agent receives a fractional assignment whose row sum across all items is 1.
Finset.sum_comm
The order of summation in a finite double sum can be exchanged.
Finset.sum_sub_distrib
The sum of a difference of two functions over a finite set equals the difference of their sums.
Finset.sum_eq_zero_iff_of_nonneg
A finite sum of non-negative real numbers is zero if and only if each individual term is zero.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_eats    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (i j : Fin n) : Prop :=  0 < s.1 j ∧ ∀ (j' : Fin n), 0 < s.1 j' → (pref i).symm j ≤ (pref i).symm j'private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_cnt    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (j : Fin n) : ℕ :=  (Finset.univ.filter    (fun i => probabilistic_serial_fractional_assignment_col_sum_eats n pref s i j)).cardprivate noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_S    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) : Finset (Fin n) :=  Finset.univ.filter    (fun j => 0 < probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j)private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_T    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) : ℝ :=  if h : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).Nonempty then    (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' h      (fun j => s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ))  else 0private theorem probabilistic_serial_fractional_assignment_col_sum_phase_eq    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) :    probabilistic_serial_phase n pref s =      (fun j => s.1 j - probabilistic_serial_fractional_assignment_col_sum_T n pref s *          (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ),       fun i j => s.2 i j +          if probabilistic_serial_fractional_assignment_col_sum_eats n pref s i j then            probabilistic_serial_fractional_assignment_col_sum_T n pref s else 0) := rflprivate theorem probabilistic_serial_fractional_assignment_col_sum_state_succ    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) :    probabilistic_serial_phase_state n pref (k + 1) =      probabilistic_serial_phase n pref (probabilistic_serial_phase_state n pref k) := by  show (probabilistic_serial_phase n pref)^[k+1] (fun x => 1, fun x x_1 => 0) =      probabilistic_serial_phase n pref        ((probabilistic_serial_phase n pref)^[k] (fun x => 1, fun x x_1 => 0))  rw [Function.iterate_succ_apply']private theorem probabilistic_serial_fractional_assignment_col_sum_T_mul_le    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (hpos : ∀ j, 0 ≤ s.1 j) (j : Fin n) :    probabilistic_serial_fractional_assignment_col_sum_T n pref s *      (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) ≤ s.1 j := by  by_cases hc : probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j = 0  · rw [hc]; push_cast; rw [mul_zero]; exact hpos j  · have hcpos : 0 < probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j :=      Nat.pos_of_ne_zero hc    have hmem : j ∈ probabilistic_serial_fractional_assignment_col_sum_S n pref s := by      rw [probabilistic_serial_fractional_assignment_col_sum_S, Finset.mem_filter]      exact ⟨Finset.mem_univ _, hcpos⟩    have hcastpos : (0:ℝ) <        (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by      exact_mod_cast hcpos    have hS : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).Nonempty :=      ⟨j, hmem⟩    have hT : probabilistic_serial_fractional_assignment_col_sum_T n pref s =        (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS          (fun j => s.1 j /            (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) := by      simp only [probabilistic_serial_fractional_assignment_col_sum_T]; exact dif_pos hS    have hle : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS          (fun j => s.1 j /            (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) ≤        s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) :=      Finset.inf'_le _ hmem    rw [hT]    calc (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS            (fun j => s.1 j /              (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) *          (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)        ≤ (s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) *          (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) :=          mul_le_mul_of_nonneg_right hle (le_of_lt hcastpos)      _ = s.1 j := div_mul_cancel₀ (s.1 j) (ne_of_gt hcastpos)private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_cap    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) : Fin n → ℝ :=  (probabilistic_serial_phase_state n pref k).1private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_col    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) (j : Fin n) : ℝ :=  ∑ i, (probabilistic_serial_phase_state n pref k).2 i jprivate theorem probabilistic_serial_fractional_assignment_col_sum_cap_nonneg    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) :    ∀ j, 0 ≤ probabilistic_serial_fractional_assignment_col_sum_cap n pref k j := by  induction k with  | zero => intro j; simp [probabilistic_serial_fractional_assignment_col_sum_cap,      probabilistic_serial_phase_state]  | succ k ih =>      intro j      have hcap : probabilistic_serial_fractional_assignment_col_sum_cap n pref (k+1) j =          probabilistic_serial_fractional_assignment_col_sum_cap n pref k j -            probabilistic_serial_fractional_assignment_col_sum_T n pref              (probabilistic_serial_phase_state n pref k) *            (probabilistic_serial_fractional_assignment_col_sum_cnt n pref              (probabilistic_serial_phase_state n pref k) j : ℝ) := by        simp only [probabilistic_serial_fractional_assignment_col_sum_cap,          probabilistic_serial_fractional_assignment_col_sum_state_succ,          probabilistic_serial_fractional_assignment_col_sum_phase_eq]      have hle := probabilistic_serial_fractional_assignment_col_sum_T_mul_le n pref        (probabilistic_serial_phase_state n pref k) (fun j => ih j) j      rw [hcap]      linarithprivate theorem probabilistic_serial_fractional_assignment_col_sum_col_phase    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (j : Fin n) :    (∑ i, (probabilistic_serial_phase n pref s).2 i j) =      (∑ i, s.2 i j) +        probabilistic_serial_fractional_assignment_col_sum_T n pref s *          (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by  rw [probabilistic_serial_fractional_assignment_col_sum_phase_eq]  simp only [Finset.sum_add_distrib]  congr 1  calc (∑ x, if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j        then probabilistic_serial_fractional_assignment_col_sum_T n pref s else (0:ℝ))      = ∑ x, probabilistic_serial_fractional_assignment_col_sum_T n pref s *          (if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j            then (1:ℝ) else 0) := by        apply Finset.sum_congr rfl        intro x _        by_cases hx : probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j        · simp [hx]        · simp [hx]    _ = probabilistic_serial_fractional_assignment_col_sum_T n pref s *          (∑ x, (if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j            then (1:ℝ) else 0)) := by        rw [Finset.mul_sum]    _ = probabilistic_serial_fractional_assignment_col_sum_T n pref s *          (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by        congr 1        exact Finset.sum_boole          (fun i => probabilistic_serial_fractional_assignment_col_sum_eats n pref s i j)          Finset.univprivate theorem probabilistic_serial_fractional_assignment_col_sum_col_form    (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) (j : Fin n) :    probabilistic_serial_fractional_assignment_col_sum_cap n pref k j +      probabilistic_serial_fractional_assignment_col_sum_col n pref k j = 1 := by  induction k with  | zero => simp [probabilistic_serial_fractional_assignment_col_sum_cap,      probabilistic_serial_fractional_assignment_col_sum_col, probabilistic_serial_phase_state]  | succ k ih =>      have hcap : probabilistic_serial_fractional_assignment_col_sum_cap n pref (k+1) j =          probabilistic_serial_fractional_assignment_col_sum_cap n pref k j -            probabilistic_serial_fractional_assignment_col_sum_T n pref              (probabilistic_serial_phase_state n pref k) *            (probabilistic_serial_fractional_assignment_col_sum_cnt n pref              (probabilistic_serial_phase_state n pref k) j : ℝ) := by        simp only [probabilistic_serial_fractional_assignment_col_sum_cap,          probabilistic_serial_fractional_assignment_col_sum_state_succ,          probabilistic_serial_fractional_assignment_col_sum_phase_eq]      have hcol : probabilistic_serial_fractional_assignment_col_sum_col n pref (k+1) j =          probabilistic_serial_fractional_assignment_col_sum_col n pref k j +            probabilistic_serial_fractional_assignment_col_sum_T n pref              (probabilistic_serial_phase_state n pref k) *            (probabilistic_serial_fractional_assignment_col_sum_cnt n pref              (probabilistic_serial_phase_state n pref k) j : ℝ) := by        simp only [probabilistic_serial_fractional_assignment_col_sum_col,          probabilistic_serial_fractional_assignment_col_sum_state_succ]        exact probabilistic_serial_fractional_assignment_col_sum_col_phase n pref          (probabilistic_serial_phase_state n pref k) j      rw [hcap, hcol]      linarith [ih]/-- Every item is fully eaten under probabilistic serial: the column sums of the PS assignment equal 1. -/theorem probabilistic_serial_fractional_assignment_col_sum (n : ℕ) (hn : 1 ≤ n) (pref : Fin n → Equiv.Perm (Fin n)) (j : Fin n) : ∑ i, probabilistic_serial_fractional_assignment n pref i j = 1 := by  let c : Fin n → ℝ := fun j => ∑ i, probabilistic_serial_fractional_assignment n pref i j  have hle : ∀ j, c j ≤ 1 := by    intro j    have hinv := probabilistic_serial_fractional_assignment_col_sum_col_form n pref n j    have hnn := probabilistic_serial_fractional_assignment_col_sum_cap_nonneg n pref n j    have e : probabilistic_serial_fractional_assignment_col_sum_col n pref n j = c j := rfl    rw [e] at hinv    linarith  have hrow : ∀ i, ∑ j, probabilistic_serial_fractional_assignment n pref i j = 1 :=    fun i => probabilistic_serial_fractional_assignment_row_sum n hn pref i  have htotal : ∑ j, c j = (n:ℝ) := by    simp only [c]    rw [Finset.sum_comm]    simp [hrow]  have hd : ∑ j, (1 - c j) = 0 := by    rw [Finset.sum_sub_distrib, htotal]    simp  have hnn : ∀ j ∈ (Finset.univ : Finset (Fin n)), 0 ≤ 1 - c j := by    intro j _; linarith [hle j]  have hz := (Finset.sum_eq_zero_iff_of_nonneg (s := Finset.univ) hnn).mp hd  have hj := hz j (Finset.mem_univ j)  show c j = 1  linarith
See it in the graphDiscuss this resultChallenge it