AFTD Auto-Formalizing Theoretical Domains

multipartite_game_threshold_minimizer_small_excess

theoremverifiedformalization

Let A ≥ 1, D ≥ 3 and r₁ ≥ … ≥ r_D ≥ 4 be integers, R_j = r₁ + … + r_j (R₀ = 0), q_j = ⌈max(R_j − A + 1, 0)/2⌉ and F_j = 2A + 2D − 2j − 3 + q_j. Then some index i ∈ {0, …, D−2} attains min_{0≤k≤D−2} F_k and has q_i ≤ 1.

Statement

theorem multipartite_game_threshold_minimizer_small_excess (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) :
    ∃ i ≤ D - 2,
      (∀ k ≤ D - 2,
        2 * A + 2 * D - 2 * i - 3 + ((∑ j ∈ Finset.Icc 1 i, r j) + 1 - A + 1) / 2 ≤
          2 * A + 2 * D - 2 * k - 3 + ((∑ j ∈ Finset.Icc 1 k, r j) + 1 - A + 1) / 2) ∧
      ((∑ j ∈ Finset.Icc 1 i, r j) + 1 - A + 1) / 2 ≤ 1
Formalizes
arXiv:2610.12508 (The Game Chromatic Number of Complete Multipartite Graphs with Triples), Lemma 2.2.
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To find a minimizer i ∈ {0, …, D - 2} of F with excess at most 1, we choose i to be the smallest minimizer on that range using the well-ordering of ℕ. If the excess at i exceeded 1, then i ≥ 1, so the monotonicity and lower bound on r imply r_i ≥ 4. Stepping down to i - 1 then increases the linear term -2k by 2 while decreasing the excess term by at least 2, showing that F(i - 1) ≤ F(i) and making i - 1 another minimizer, which contradicts the minimality of i.

  1. Define the objective function F and the minimizer property p

    We define F(k) = 2A + 2D - 2k - 3 + ((∑_{j=1}^k r_j) + 1 - A + 1)/2 and let p(n) express that n ≤ D - 2 and F(n) ≤ F(k) for all k ≤ D - 2.

    lines 8–11

      classical
      let F : ℕ → ℕ := fun k =>
        2 * A + 2 * D - 2 * k - 3 + ((∑ j ∈ Finset.Icc 1 k, r j) + 1 - A + 1) / 2
      let p : ℕ → Prop := fun n => n ≤ D - 2 ∧ ∀ k ≤ D - 2, F n ≤ F k
  2. There exists a minimizer of F in {0, …, D - 2}

    The discrete interval {0, …, D - 2} is nonempty because it contains 0 (by Nat.zero_le and Finset.mem_Iic). By Finset.exists_min_image, F attains its minimum on this finite set, giving some index n satisfying p(n).

    lines 12–16

    uses Nat.zero_le, Finset.mem_Iic, Finset.exists_min_image

      have hex : ∃ n, p n := by
        have hne : (Finset.Iic (D - 2)).Nonempty := ⟨0, Finset.mem_Iic.2 (Nat.zero_le _)⟩
        obtain ⟨n, hn, hmin⟩ := Finset.exists_min_image (Finset.Iic (D - 2)) F hne
        simp only [Finset.mem_Iic] at hn hmin
        exact ⟨n, hn, hmin⟩
  3. Let i be the least minimizer of F on {0, …, D - 2}

    By Nat.find on the existence of a minimizer, we define i as the smallest natural number satisfying p, and Nat.find_spec verifies that p(i) holds.

    lines 17–18

    uses Nat.find_spec

      let i := Nat.find hex
      have hpi : p i := Nat.find_spec hex
  4. If the excess at i exceeds 1, then i ≥ 1

    We assume for contradiction that the excess term at i is strictly greater than 1. If i were 0, the sum over {1, …, 0} would be empty by Finset.Icc_eq_empty_of_lt and evaluate to 0 by Finset.sum_empty. With A ≥ 1, the numerator (0 + 1 - A + 1) is at most 1, so division by 2 yields 0, contradicting that the excess is > 1. Thus i ≥ 1.

    lines 19–26

    uses Finset.Icc_eq_empty_of_lt, Finset.sum_empty

      have hqi : ((∑ j ∈ Finset.Icc 1 i, r j) + 1 - A + 1) / 2 ≤ 1 := by
        by_contra! hq
        have hi1 : 1 ≤ i := by
          by_contra! hi0
          have hi_eq : i = 0 := by omega
          rw [hi_eq] at hq
          simp only [Finset.Icc_eq_empty_of_lt (by decide : 1 > 0), Finset.sum_empty] at hq
          omega
  5. The summand r_i is at least 4

    Since 1 ≤ i ≤ D - 2 ≤ D, the monotonicity hypothesis hmono yields r(D) ≤ r(i). Combining this with r(D) ≥ 4 gives r(i) ≥ 4.

    lines 27–29

        have hr : 4 ≤ r i := by
          have : r D ≤ r i := hmono i D hi1 (by omega) (by omega)
          omega
  6. Splitting off the last term gives ∑_{j=1}^i r_j = (∑_{j=1}^{i-1} r_j) + r_i

    The set {1, …, i} is rewritten as insert i {1, …, i - 1} via Finset.mem_Icc and Finset.mem_insert. Then Finset.sum_insert pulls out r(i) since i ∉ {1, …, i - 1}.

    lines 30–37

    uses Finset.mem_Icc, Finset.mem_insert, Finset.sum_insert

        have hsum : ∑ j ∈ Finset.Icc 1 i, r j = (∑ j ∈ Finset.Icc 1 (i - 1), r j) + r i := by
          have : Finset.Icc 1 i = insert i (Finset.Icc 1 (i - 1)) := by
            ext x
            simp only [Finset.mem_Icc, Finset.mem_insert]
            omega
          rw [this, Finset.sum_insert]
          · ring
          · simp; omega
  7. F(i - 1) ≤ F(i) automation

    In passing from i to i - 1, the term -2k increases by 2, but the sum inside the excess term decreases by r(i) ≥ 4, which reduces the integer-divided excess by at least 2. The omega decision procedure verifies that F(i - 1) ≤ F(i) in truncated natural number arithmetic.

    lines 38–41

        have hF_le : F (i - 1) ≤ F i := by
          dsimp [F]
          rw [hsum]
          omega
  8. The excess at i is at most 1

    Since F(i - 1) ≤ F(i) and i is a minimizer, transitivity (le_trans) shows that i - 1 is also a minimizer, so p(i - 1) holds. However, i - 1 < i, so Nat.find_min states that ¬p(i - 1), a contradiction. Hence the excess at i is at most 1.

    lines 42–46

    uses le_trans, Nat.find_min

        have hpi_prev : p (i - 1) := by
          refine ⟨by omega, fun k hk => ?_⟩
          exact le_trans hF_le (hpi.2 k hk)
        have hnot : ¬ p (i - 1) := Nat.find_min hex (by omega)
        exact hnot hpi_prev
  9. There exists an index i ≤ D - 2 that minimizes F and has excess at most 1

    The index i satisfies i ≤ D - 2, minimizes F, and has excess at most 1, which provides the desired witness.

    line 47

      exact ⟨i, hpi.1, hpi.2, hqi⟩
Nat.zero_le
every natural number is at least 0
Finset.mem_Iic
an element x belongs to the downward closed interval Iic a if and only if x ≤ a
Finset.exists_min_image
every nonempty finite set has an element minimizing a given function into a linearly ordered codomain
Nat.find_spec
the witness returned by Nat.find satisfies the predicate
Finset.Icc_eq_empty_of_lt
the interval [a, b] is empty when b < a
Finset.sum_empty
the sum of any function over the empty set is 0
Finset.mem_Icc
an element x belongs to [a, b] if and only if a ≤ x ≤ b
Finset.mem_insert
an element x belongs to insert a s if and only if x = a or x ∈ s
Finset.sum_insert
the sum over insert a s is f(a) plus the sum over s, provided a ∉ s
le_trans
the order relation ≤ is transitive
Nat.find_min
no natural number strictly smaller than Nat.find satisfies the predicate

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

theorem multipartite_game_threshold_minimizer_small_excess (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) :    ∃ i ≤ D - 2,      (∀ k ≤ D - 2,        2 * A + 2 * D - 2 * i - 3 + ((∑ j ∈ Finset.Icc 1 i, r j) + 1 - A + 1) / 2 ≤          2 * A + 2 * D - 2 * k - 3 + ((∑ j ∈ Finset.Icc 1 k, r j) + 1 - A + 1) / 2) ∧      ((∑ j ∈ Finset.Icc 1 i, r j) + 1 - A + 1) / 2 ≤ 1 := by  classical  let F : ℕ → ℕ := fun k =>    2 * A + 2 * D - 2 * k - 3 + ((∑ j ∈ Finset.Icc 1 k, r j) + 1 - A + 1) / 2  let p : ℕ → Prop := fun n => n ≤ D - 2 ∧ ∀ k ≤ D - 2, F n ≤ F k  have hex : ∃ n, p n := by    have hne : (Finset.Iic (D - 2)).Nonempty := ⟨0, Finset.mem_Iic.2 (Nat.zero_le _)⟩    obtain ⟨n, hn, hmin⟩ := Finset.exists_min_image (Finset.Iic (D - 2)) F hne    simp only [Finset.mem_Iic] at hn hmin    exact ⟨n, hn, hmin⟩  let i := Nat.find hex  have hpi : p i := Nat.find_spec hex  have hqi : ((∑ j ∈ Finset.Icc 1 i, r j) + 1 - A + 1) / 2 ≤ 1 := by    by_contra! hq    have hi1 : 1 ≤ i := by      by_contra! hi0      have hi_eq : i = 0 := by omega      rw [hi_eq] at hq      simp only [Finset.Icc_eq_empty_of_lt (by decide : 1 > 0), Finset.sum_empty] at hq      omega    have hr : 4 ≤ r i := by      have : r D ≤ r i := hmono i D hi1 (by omega) (by omega)      omega    have hsum : ∑ j ∈ Finset.Icc 1 i, r j = (∑ j ∈ Finset.Icc 1 (i - 1), r j) + r i := by      have : Finset.Icc 1 i = insert i (Finset.Icc 1 (i - 1)) := by        ext x        simp only [Finset.mem_Icc, Finset.mem_insert]        omega      rw [this, Finset.sum_insert]      · ring      · simp; omega    have hF_le : F (i - 1) ≤ F i := by      dsimp [F]      rw [hsum]      omega    have hpi_prev : p (i - 1) := by      refine ⟨by omega, fun k hk => ?_⟩      exact le_trans hF_le (hpi.2 k hk)    have hnot : ¬ p (i - 1) := Nat.find_min hex (by omega)    exact hnot hpi_prev  exact ⟨i, hpi.1, hpi.2, hqi⟩
See it in the graphDiscuss this resultChallenge it