AFTD Auto-Formalizing Theoretical Domains

multipartite_game_bob_bound_ge_min_threshold

theoremverifiedformalization

Let A ≥ 1, D ≥ 3 and r₁ ≥ r₂ ≥ … ≥ r_D ≥ 4 be integers, R_j = r₁ + … + r_j, P = A + Σ_{i=1}^{D} ⌈r_i/2⌉ and F_{D−2} = 2A + 1 + ⌈max(R_{D−2} − A + 1, 0)/2⌉. Then A + ⌊(A + R_{D−1} + 1)/2⌋ ≥ min(F_{D−2}, P). (Natural-number division: ⌈x/2⌉ = (x+1)/2, and the truncated R + 1 − A is max(R − A + 1, 0).)

Statement

theorem multipartite_game_bob_bound_ge_min_threshold (A D : ℕ) (r : ℕ → ℕ) (hA : 1 ≤ A)
    (hD : 3 ≤ D) (hmono : ∀ i j, 1 ≤ i → i ≤ j → j ≤ D → r j ≤ r i) (h4 : 4 ≤ r D) :
    min (2 * A + 1 + ((∑ i ∈ Finset.Icc 1 (D - 2), r i) + 1 - A + 1) / 2)
        (A + ∑ i ∈ Finset.Icc 1 D, (r i + 1) / 2) ≤
      A + (A + ∑ i ∈ Finset.Icc 1 (D - 1), r i + 1) / 2
Formalizes
arXiv:2610.12508 (The Game Chromatic Number of Complete Multipartite Graphs with Triples), Lemma 3.2.
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The inequality compares the candidate bound A + ⌊(A + R_{D-1} + 1)/2⌋ with min(F_{D-2}, P), where F_{D-2} = 2A + 1 + ⌈max(R_{D-2} − A + 1, 0)/2⌉ and P = A + ∑_{i=1}^D ⌈r_i / 2⌉. The proof splits into two cases based on whether A + 1 ≤ R_{D-1}. If A + 1 ≤ R_{D-1}, the candidate bound is bounded below by F_{D-2}, which holds by linear integer arithmetic after decomposing R_{D-1} = R_{D-2} + r_{D-1} and using r_{D-1} ≥ 4. If A + 1 > R_{D-1}, the candidate bound is bounded below by P, which follows from the helper inequality ∑_{i=1}^D ⌈r_i / 2⌉ ≤ R_{D-1} combined with R_{D-1} ≤ A.

  1. The sum ∑_{i=1}^D f(i) decomposes into ∑_{i=1}^{D-3} f(i) + f(D-2) + f(D-1) + f(D).

    Because D ≥ 3, the top indices D, D - 1, and D - 2 all exceed 1. We successively peel off each top element from the summation interval using Finset.sum_Icc_succ_top, rewriting D = (D - 1) + 1, D - 1 = (D - 2) + 1, and D - 2 = (D - 3) + 1.

    lines 1–16

    uses Finset.sum_Icc_succ_top

    lemma multipartite_game_bob_bound_sum_icc_decomp_three (D : ℕ) (hD : 3 ≤ D) (f : ℕ → ℕ) :
        ∑ i ∈ Finset.Icc 1 D, f i =
          (∑ i ∈ Finset.Icc 1 (D - 3), f i) + f (D - 2) + f (D - 1) + f D := by
      have h1 : D = (D - 1) + 1 := by omega
      have ha1 : 1 ≤ (D - 1) + 1 := by omega
      have h2 : D - 1 = (D - 2) + 1 := by omega
      have ha2 : 1 ≤ (D - 2) + 1 := by omega
      have h3 : D - 2 = (D - 3) + 1 := by omega
      have ha3 : 1 ≤ (D - 3) + 1 := by omega
      nth_rw 1 [h1]
      rw [Finset.sum_Icc_succ_top ha1]
      nth_rw 1 [h2]
      rw [Finset.sum_Icc_succ_top ha2]
      nth_rw 1 [h3]
      rw [Finset.sum_Icc_succ_top ha3]
      rw [← h3, ← h2, ← h1]
  2. The sum ∑_{i=1}^{D-1} f(i) decomposes into ∑_{i=1}^{D-3} f(i) + f(D-2) + f(D-1).

    Similarly, since D ≥ 3, we have D - 1 ≥ 2. We peel off the two highest terms f(D - 1) and f(D - 2) from the summation interval using Finset.sum_Icc_succ_top twice.

    lines 18–29

    uses Finset.sum_Icc_succ_top

    lemma multipartite_game_bob_bound_sum_icc_decomp_two (D : ℕ) (hD : 3 ≤ D) (f : ℕ → ℕ) :
        ∑ i ∈ Finset.Icc 1 (D - 1), f i =
          (∑ i ∈ Finset.Icc 1 (D - 3), f i) + f (D - 2) + f (D - 1) := by
      have h2 : D - 1 = (D - 2) + 1 := by omega
      have ha2 : 1 ≤ (D - 2) + 1 := by omega
      have h3 : D - 2 = (D - 3) + 1 := by omega
      have ha3 : 1 ≤ (D - 3) + 1 := by omega
      nth_rw 1 [h2]
      rw [Finset.sum_Icc_succ_top ha2]
      nth_rw 1 [h3]
      rw [Finset.sum_Icc_succ_top ha3]
      rw [← h3, ← h2]
  3. The sum ∑_{i=1}^{D-1} f(i) decomposes into (∑_{i=1}^{D-2} f(i)) + f(D-1).

    Since D ≥ 3, D - 1 = (D - 2) + 1 ≥ 1. Peeling off the single top term f(D - 1) using Finset.sum_Icc_succ_top gives the decomposition.

    lines 31–38

    uses Finset.sum_Icc_succ_top

    lemma multipartite_game_bob_bound_sum_icc_decomp_one (D : ℕ) (hD : 3 ≤ D) (f : ℕ → ℕ) :
        ∑ i ∈ Finset.Icc 1 (D - 1), f i =
          (∑ i ∈ Finset.Icc 1 (D - 2), f i) + f (D - 1) := by
      have h2 : D - 1 = (D - 2) + 1 := by omega
      have ha2 : 1 ≤ (D - 2) + 1 := by omega
      nth_rw 1 [h2]
      rw [Finset.sum_Icc_succ_top ha2]
      rw [← h2]
  4. The sum of ceiling-halves ∑_{i=1}^D ⌊(r_i + 1)/2⌋ is bounded above by the partial sum ∑_{i=1}^{D-1} r_i.

    We decompose both sides: the left-hand sum via multipartite_game_bob_bound_sum_icc_decomp_three into a sum over 1 … D - 3 plus three tail terms, and the right-hand sum via multipartite_game_bob_bound_sum_icc_decomp_two into a sum over 1 … D - 3 plus two tail terms. For indices 1 ≤ i ≤ D - 3, termwise comparison using Finset.sum_le_sum shows ⌊(r_i + 1)/2⌋ ≤ r_i. For the remaining indices, monotonicity gives r_D ≤ r_{D-1} ≤ r_{D-2}; combined with 4 ≤ r_D, linear integer arithmetic over ℕ (omega) verifies that ⌊(r_{D-2} + 1)/2⌋ + ⌊(r_{D-1} + 1)/2⌋ + ⌊(r_D + 1)/2⌋ ≤ r_{D-2} + r_{D-1}.

    lines 40–51

    uses multipartite_game_bob_bound_sum_icc_decomp_three, multipartite_game_bob_bound_sum_icc_decomp_two, Finset.sum_le_sum

    lemma multipartite_game_bob_bound_sum_div_two_le_sum (D : ℕ) (r : ℕ → ℕ) (hD : 3 ≤ D)
        (hmono : ∀ i j, 1 ≤ i → i ≤ j → j ≤ D → r j ≤ r i) (h4 : 4 ≤ r D) :
        ∑ i ∈ Finset.Icc 1 D, (r i + 1) / 2 ≤ ∑ i ∈ Finset.Icc 1 (D - 1), r i := by
      rw [multipartite_game_bob_bound_sum_icc_decomp_three D hD (fun i => (r i + 1) / 2)]
      rw [multipartite_game_bob_bound_sum_icc_decomp_two D hD r]
      have hsum : ∑ i ∈ Finset.Icc 1 (D - 3), (r i + 1) / 2 ≤ ∑ i ∈ Finset.Icc 1 (D - 3), r i := by
        apply Finset.sum_le_sum
        intro i _
        omega
      have hrD_le_rD1 : r D ≤ r (D - 1) := hmono (D - 1) D (by omega) (by omega) (by omega)
      have hrD1_le_rD2 : r (D - 1) ≤ r (D - 2) := hmono (D - 2) (D - 1) (by omega) (by omega) (by omega)
      omega
  5. We deduce 4 ≤ r(D - 1) and decompose R_{D-1} = R_{D-2} + r(D-1).

    From the monotonicity hypothesis (hmono) and 4 ≤ r_D (h4), we obtain 4 ≤ r_D ≤ r(D - 1). Applying multipartite_game_bob_bound_sum_icc_decomp_one expresses R_{D-1} = ∑_{i=1}^{D-1} r_i as (∑_{i=1}^{D-2} r_i) + r(D - 1).

    lines 53–64

    uses multipartite_game_bob_bound_sum_icc_decomp_one

    theorem multipartite_game_bob_bound_ge_min_threshold (A D : ℕ) (r : ℕ → ℕ) (hA : 1 ≤ A)
        (hD : 3 ≤ D) (hmono : ∀ i j, 1 ≤ i → i ≤ j → j ≤ D → r j ≤ r i) (h4 : 4 ≤ r D) :
        min (2 * A + 1 + ((∑ i ∈ Finset.Icc 1 (D - 2), r i) + 1 - A + 1) / 2)
            (A + ∑ i ∈ Finset.Icc 1 D, (r i + 1) / 2) ≤
          A + (A + ∑ i ∈ Finset.Icc 1 (D - 1), r i + 1) / 2 := by
      have _ := hA
      have hrD1 : 4 ≤ r (D - 1) := by
        have : r D ≤ r (D - 1) := hmono (D - 1) D (by omega) (by omega) (by omega)
        omega
      have hdecomp : ∑ i ∈ Finset.Icc 1 (D - 1), r i =
          (∑ i ∈ Finset.Icc 1 (D - 2), r i) + r (D - 1) :=
        multipartite_game_bob_bound_sum_icc_decomp_one D hD r
  6. When A + 1 ≤ R_{D-1}, the bound holds via the first argument of the minimum, F_{D-2}.

    We branch on whether A + 1 ≤ R_{D-1}. In this branch, since min(F_{D-2}, P) ≤ F_{D-2} by min_le_left, transitivity (le_trans) reduces the goal to showing F_{D-2} ≤ A + ⌊(A + R_{D-1} + 1)/2⌋. Rewriting R_{D-1} as R_{D-2} + r(D - 1), the inequality reduces to linear integer arithmetic over ℕ; since r(D - 1) ≥ 4, omega closes it.

    lines 65–68

    uses le_trans, min_le_left

      by_cases h : A + 1 ≤ ∑ i ∈ Finset.Icc 1 (D - 1), r i
      · apply le_trans (min_le_left _ _)
        rw [hdecomp] at h ⊢
        omega
  7. When A + 1 > R_{D-1}, the bound holds via the second argument of the minimum, P.

    In the alternative branch where ¬(A + 1 ≤ R_{D-1}), we have R_{D-1} ≤ A. Since min(F_{D-2}, P) ≤ P by min_le_right, transitivity (le_trans) reduces the goal to showing P ≤ A + ⌊(A + R_{D-1} + 1)/2⌋. By multipartite_game_bob_bound_sum_div_two_le_sum, the ceiling-half sum in P is at most R_{D-1}, so P ≤ A + R_{D-1}. Since R_{D-1} ≤ A, we have 2 * R_{D-1} ≤ A + R_{D-1} + 1, which implies R_{D-1} ≤ ⌊(A + R_{D-1} + 1)/2⌋, and omega closes the linear arithmetic goal.

    lines 69–72

    uses le_trans, min_le_right, multipartite_game_bob_bound_sum_div_two_le_sum

      · apply le_trans (min_le_right _ _)
        have hsum : ∑ i ∈ Finset.Icc 1 D, (r i + 1) / 2 ≤ ∑ i ∈ Finset.Icc 1 (D - 1), r i :=
          multipartite_game_bob_bound_sum_div_two_le_sum D r hD hmono h4
        omega
Finset.sum_Icc_succ_top
For natural numbers with a ≤ b + 1, the sum over [a, b + 1] equals the sum over [a, b] plus the top term f(b + 1).
multipartite_game_bob_bound_sum_icc_decomp_three
For D ≥ 3, the sum ∑_{i=1}^D f(i) decomposes into ∑_{i=1}^{D-3} f(i) + f(D-2) + f(D-1) + f(D).
multipartite_game_bob_bound_sum_icc_decomp_two
For D ≥ 3, the sum ∑_{i=1}^{D-1} f(i) decomposes into ∑_{i=1}^{D-3} f(i) + f(D-2) + f(D-1).
multipartite_game_bob_bound_sum_icc_decomp_one
For D ≥ 3, the sum ∑_{i=1}^{D-1} f(i) decomposes into ∑_{i=1}^{D-2} f(i) + f(D-1).
multipartite_game_bob_bound_sum_div_two_le_sum
For D ≥ 3, weakly decreasing r, and r_D ≥ 4, the sum of ceiling-halves ∑_{i=1}^D ⌊(r_i+1)/2⌋ is bounded by the partial sum ∑_{i=1}^{D-1} r_i.
Finset.sum_le_sum
If f(i) ≤ g(i) for all indices i in a finite set s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ s} g(i).
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
min_le_left
The minimum of two elements is bounded by the first: min(a, b) ≤ a.
min_le_right
The minimum of two elements is bounded by the second: min(a, b) ≤ b.

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

lemma multipartite_game_bob_bound_sum_icc_decomp_three (D : ℕ) (hD : 3 ≤ D) (f : ℕ → ℕ) :    ∑ i ∈ Finset.Icc 1 D, f i =      (∑ i ∈ Finset.Icc 1 (D - 3), f i) + f (D - 2) + f (D - 1) + f D := by  have h1 : D = (D - 1) + 1 := by omega  have ha1 : 1 ≤ (D - 1) + 1 := by omega  have h2 : D - 1 = (D - 2) + 1 := by omega  have ha2 : 1 ≤ (D - 2) + 1 := by omega  have h3 : D - 2 = (D - 3) + 1 := by omega  have ha3 : 1 ≤ (D - 3) + 1 := by omega  nth_rw 1 [h1]  rw [Finset.sum_Icc_succ_top ha1]  nth_rw 1 [h2]  rw [Finset.sum_Icc_succ_top ha2]  nth_rw 1 [h3]  rw [Finset.sum_Icc_succ_top ha3]  rw [← h3, ← h2, ← h1]lemma multipartite_game_bob_bound_sum_icc_decomp_two (D : ℕ) (hD : 3 ≤ D) (f : ℕ → ℕ) :    ∑ i ∈ Finset.Icc 1 (D - 1), f i =      (∑ i ∈ Finset.Icc 1 (D - 3), f i) + f (D - 2) + f (D - 1) := by  have h2 : D - 1 = (D - 2) + 1 := by omega  have ha2 : 1 ≤ (D - 2) + 1 := by omega  have h3 : D - 2 = (D - 3) + 1 := by omega  have ha3 : 1 ≤ (D - 3) + 1 := by omega  nth_rw 1 [h2]  rw [Finset.sum_Icc_succ_top ha2]  nth_rw 1 [h3]  rw [Finset.sum_Icc_succ_top ha3]  rw [← h3, ← h2]lemma multipartite_game_bob_bound_sum_icc_decomp_one (D : ℕ) (hD : 3 ≤ D) (f : ℕ → ℕ) :    ∑ i ∈ Finset.Icc 1 (D - 1), f i =      (∑ i ∈ Finset.Icc 1 (D - 2), f i) + f (D - 1) := by  have h2 : D - 1 = (D - 2) + 1 := by omega  have ha2 : 1 ≤ (D - 2) + 1 := by omega  nth_rw 1 [h2]  rw [Finset.sum_Icc_succ_top ha2]  rw [← h2]lemma multipartite_game_bob_bound_sum_div_two_le_sum (D : ℕ) (r : ℕ → ℕ) (hD : 3 ≤ D)    (hmono : ∀ i j, 1 ≤ i → i ≤ j → j ≤ D → r j ≤ r i) (h4 : 4 ≤ r D) :    ∑ i ∈ Finset.Icc 1 D, (r i + 1) / 2 ≤ ∑ i ∈ Finset.Icc 1 (D - 1), r i := by  rw [multipartite_game_bob_bound_sum_icc_decomp_three D hD (fun i => (r i + 1) / 2)]  rw [multipartite_game_bob_bound_sum_icc_decomp_two D hD r]  have hsum : ∑ i ∈ Finset.Icc 1 (D - 3), (r i + 1) / 2 ≤ ∑ i ∈ Finset.Icc 1 (D - 3), r i := by    apply Finset.sum_le_sum    intro i _    omega  have hrD_le_rD1 : r D ≤ r (D - 1) := hmono (D - 1) D (by omega) (by omega) (by omega)  have hrD1_le_rD2 : r (D - 1) ≤ r (D - 2) := hmono (D - 2) (D - 1) (by omega) (by omega) (by omega)  omegatheorem multipartite_game_bob_bound_ge_min_threshold (A D : ℕ) (r : ℕ → ℕ) (hA : 1 ≤ A)    (hD : 3 ≤ D) (hmono : ∀ i j, 1 ≤ i → i ≤ j → j ≤ D → r j ≤ r i) (h4 : 4 ≤ r D) :    min (2 * A + 1 + ((∑ i ∈ Finset.Icc 1 (D - 2), r i) + 1 - A + 1) / 2)        (A + ∑ i ∈ Finset.Icc 1 D, (r i + 1) / 2) ≤      A + (A + ∑ i ∈ Finset.Icc 1 (D - 1), r i + 1) / 2 := by  have _ := hA  have hrD1 : 4 ≤ r (D - 1) := by    have : r D ≤ r (D - 1) := hmono (D - 1) D (by omega) (by omega) (by omega)    omega  have hdecomp : ∑ i ∈ Finset.Icc 1 (D - 1), r i =      (∑ i ∈ Finset.Icc 1 (D - 2), r i) + r (D - 1) :=    multipartite_game_bob_bound_sum_icc_decomp_one D hD r  by_cases h : A + 1 ≤ ∑ i ∈ Finset.Icc 1 (D - 1), r i  · apply le_trans (min_le_left _ _)    rw [hdecomp] at h ⊢    omega  · apply le_trans (min_le_right _ _)    have hsum : ∑ i ∈ Finset.Icc 1 D, (r i + 1) / 2 ≤ ∑ i ∈ Finset.Icc 1 (D - 1), r i :=      multipartite_game_bob_bound_sum_div_two_le_sum D r hD hmono h4    omega
See it in the graphDiscuss this resultChallenge it