AFTD Auto-Formalizing Theoretical Domains

op_258_exists_divergent_capacity_covering

theoremverified

If a positive antitone profile a has infinite sum in ENNReal, then for any threshold n₀, there exists l ≥ 1 with 2^l ≥ n₀, pairwise disjoint sets of colours I_j for each hypercube layer j < l, and integer capacities cap(i) ≤ a_i * C(2^l, 2) whose sum on each layer j is at least 2^{2l - 2 - j}.

Statement

theorem op_258_exists_divergent_capacity_covering
    (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a)
    (hsum : (∑' i : ℕ+, ENNReal.ofReal (a i)) = ⊤) (n₀ : ℕ) :
    ∃ (l : ℕ) (hl : 1 ≤ l) (I : Fin l → Finset ℕ+) (cap : ℕ+ → ℕ),
      n₀ ≤ 2^l ∧
      (∀ j₁ j₂ : Fin l, j₁ ≠ j₂ → Disjoint (I j₁) (I j₂)) ∧
      (∀ j : Fin l, ∀ i ∈ I j, (cap i : ℝ) ≤ a i * ((2^l).choose 2 : ℝ)) ∧
      (∀ j : Fin l, 2^(2 * l - 2 - (j : ℕ)) ≤ ∑ i ∈ I j, cap i)
Source
step towards op_258_sum_ne_top_of_forces_three
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1
  • op_258_sum_ne_top_of_forces_threeIf a positive antitone profile a forces a monochromatic triangle K_3 on sufficiently large complete graphs, then the infinite sum of a_i…

The proof, explained

The proof uses a block-partitioning lemma (`op_258_exists_divergent_block_indices`) to obtain a hypercube dimension l ≥ 3 and strictly increasing indices r₀ < r₁ < … < r_l such that 2^l ≥ n₀, a(r_l) ≥ 1/2^(l-1), and each block I_j = (r_j, r_{j+1}] has profile sum at least 1/2^j. The layer sets are chosen as these blocks I_j, which are pairwise disjoint by the monotonicity of r, and the capacities are set to cap(i) = ⌊a_i * C(2^l, 2)⌋₊. Because a is antitone, every i ∈ I_j satisfies a_i ≥ a(r_l) ≥ 1/2^(l-1), which by `op_258_capacity_floor_ge` guarantees cap(i) ≥ 2^(2l - 2) * a_i; summing this over I_j produces the required layer capacity lower bound 2^(2l - 2 - j).

  1. There exist a dimension l ≥ 3 with 2^l ≥ n₀ and strictly increasing indices r₀ < r₁ < … < r_l partitioning an initial segment into blocks of sufficient weight.

    We invoke the lemma `op_258_exists_divergent_block_indices`. Using the infinite sum and antitonicity of a, it produces l ≥ 3 with 2^l ≥ n₀ and a strictly increasing sequence of indices r : Fin (l + 1) → ℕ+ such that a(r_l) ≥ 1/2^(l-1) and the sum of a over each block (r_j, r_{j+1}] is at least 1/2^j.

    lines 10–12

    uses op_258_exists_divergent_block_indices

      classical
      obtain ⟨l, hl3, r, hn0, hmono, hend, hblk⟩ :=
        op_258_exists_divergent_block_indices a hpos hanti hsum n₀
  2. Provide candidate witnesses: the dimension l, the layer sets I_j = (r_j, r_{j+1}], and the capacities cap(i) = ⌊a_i * C(2^l, 2)⌋₊.

    We instantiate the existential quantifier with l (where 1 ≤ l follows from 3 ≤ l), sets I_j defined as the half-open intervals (r_j, r_{j+1}], and capacities given by the floor of a_i * C(2^l, 2). The condition n₀ ≤ 2^l holds directly from the previous step, leaving the disjointness of the blocks, the capacity upper bound, and the layer capacity lower bound to be verified.

    lines 13–15

      refine ⟨l, by omega,
        fun j : Fin l => Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩),
        fun i => ⌊a i * ((2^l).choose 2 : ℝ)⌋₊, hn0, ?_, ?_, ?_⟩
  3. The sets I_{j₁} and I_{j₂} are pairwise disjoint whenever j₁ ≠ j₂.

    Assume without loss of generality that j₁ < j₂ (the case j₂ < j₁ is symmetric). Then j₁ + 1 ≤ j₂, so strict monotonicity of r implies r_{j₁+1} ≤ r_{j₂}. If an element x belonged to both I_{j₁} and I_{j₂}, we would have x ≤ r_{j₁+1} ≤ r_{j₂} from x ∈ I_{j₁}, but also r_{j₂} < x from x ∈ I_{j₂}, a contradiction.

    lines 16–30

    uses Finset.disjoint_left, Finset.mem_Ioc, lt_or_gt_of_ne, Fin.le_def, Nat.succ_le_of_lt, not_le.mpr, le_trans

      · intro j₁ j₂ hne
        rw [Finset.disjoint_left]
        intro x hx1 hx2
        rw [Finset.mem_Ioc] at hx1 hx2
        rcases lt_or_gt_of_ne hne with hlt | hgt
        · have hlt' : j₁.1 < j₂.1 := hlt
          have hle : (⟨j₁.1+1, by omega⟩ : Fin (l+1)) ≤ ⟨j₂.1, by omega⟩ := by
            rw [Fin.le_def]; exact Nat.succ_le_of_lt hlt'
          have h1 : r ⟨j₁.1 + 1, by omega⟩ ≤ r ⟨j₂.1, by omega⟩ := hmono.monotone hle
          exact (not_le.mpr hx2.1) (le_trans hx1.2 h1)
        · have hlt' : j₂.1 < j₁.1 := hgt
          have hle : (⟨j₂.1+1, by omega⟩ : Fin (l+1)) ≤ ⟨j₁.1, by omega⟩ := by
            rw [Fin.le_def]; exact Nat.succ_le_of_lt hlt'
          have h1 : r ⟨j₂.1 + 1, by omega⟩ ≤ r ⟨j₁.1, by omega⟩ := hmono.monotone hle
          exact (not_le.mpr hx1.1) (le_trans hx2.2 h1)
  4. For every layer j and element i ∈ I_j, cap(i) ≤ a_i * C(2^l, 2).

    Since a_i > 0 and the binomial coefficient C(2^l, 2) is non-negative, their product is non-negative. The inequality follows directly from the property of the floor function that ⌊x⌋₊ ≤ x for non-negative real numbers.

    lines 31–32

    uses Nat.floor_le, mul_nonneg, le_of_lt

      · intro j i hi
        exact Nat.floor_le (mul_nonneg (le_of_lt (hpos i)) (by positivity))
  5. For each element i ∈ I_j, the capacity satisfies the pointwise lower bound 2^(2l - 2) * a_i ≤ cap(i).

    For any i ∈ I_j = (r_j, r_{j+1}], we have i ≤ r_{j+1} ≤ r_l because j + 1 ≤ l. Since a is antitone, a_i ≥ a(r_l) ≥ 1/2^(l-1). Applying `op_258_capacity_floor_ge` with this lower bound on a_i yields 2^(2l - 2) * a_i ≤ ⌊a_i * C(2^l, 2)⌋₊ = cap(i).

    lines 33–44

    uses Finset.mem_Ioc, Fin.le_def, Nat.succ_le_of_lt, le_trans, op_258_capacity_floor_ge

      · intro j
        have hle : ∀ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩),
            (2:ℝ)^(2*l-2) * a i ≤ ((⌊a i * ((2^l).choose 2 : ℝ)⌋₊ : ℕ) : ℝ) := by
          intro i hi
          rw [Finset.mem_Ioc] at hi
          have hi_le : i ≤ r ⟨l, by omega⟩ := by
            have h1 : r ⟨j.1 + 1, by omega⟩ ≤ r ⟨l, by omega⟩ := by
              apply hmono.monotone
              rw [Fin.le_def]; exact Nat.succ_le_of_lt j.2
            exact le_trans hi.2 h1
          have hai : 1 / (2:ℝ)^(l-1) ≤ a i := le_trans hend (hanti hi_le)
          exact op_258_capacity_floor_ge l hl3 (a i) hai
  6. For each layer j, the sum of capacities over I_j is at least 2^(2l - 2 - j).

    Summing the pointwise lower bound over all i ∈ I_j gives 2^(2l - 2) * ∑_{i ∈ I_j} a_i ≤ ∑_{i ∈ I_j} cap(i). Since ∑_{i ∈ I_j} a_i ≥ 1/2^j by the block construction, multiplying by 2^(2l - 2) yields 2^(2l - 2) * (1/2^j) ≤ ∑_{i ∈ I_j} cap(i). Simplifying 2^(2l - 2) * 2^(-j) = 2^(2l - 2 - j) and casting the inequality to natural numbers completes the proof.

    lines 45–55

    uses Finset.sum_le_sum, Finset.mul_sum, mul_le_mul_of_nonneg_left, le_trans, one_div, pow_sub₀

        have hsum_le := Finset.sum_le_sum hle
        rw [← Finset.mul_sum] at hsum_le
        have key : (2:ℝ)^(2*l-2) * (1/(2:ℝ)^(j:ℕ)) ≤
            (2:ℝ)^(2*l-2) * (∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), a i) :=
          mul_le_mul_of_nonneg_left (hblk j) (by positivity)
        have hstep : (2:ℝ)^(2*l-2) * (1/(2:ℝ)^(j:ℕ)) ≤
            ∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩),
              ((⌊a i * ((2^l).choose 2 : ℝ)⌋₊ : ℕ) : ℝ) :=
          le_trans key hsum_le
        rw [one_div, ← pow_sub₀ (2:ℝ) (by norm_num) (by omega)] at hstep
        exact_mod_cast hstep
op_258_exists_divergent_block_indices
For a positive antitone sequence with infinite sum and a threshold n₀, there exists l ≥ 3 with 2^l ≥ n₀ and strictly increasing indices r₀ < r₁ < … < r_l such that a(r_l) ≥ 1/2^(l-1) and the sum of a over each block (r_j, r_{j+1}] is at least 1/2^j.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_Ioc
An element x belongs to the half-open interval (a, b] if and only if a < x and x ≤ b.
lt_or_gt_of_ne
In a linear order, two unequal elements satisfy a < b or b < a.
Fin.le_def
In Fin n, an element a is at most b if and only if the underlying natural numbers satisfy a ≤ b.
Nat.succ_le_of_lt
For natural numbers, if n < m then n + 1 ≤ m.
not_le.mpr
If a < b, then it is not the case that b ≤ a.
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Nat.floor_le
For a non-negative real x, its floor ⌊x⌋₊ satisfies ⌊x⌋₊ ≤ x.
mul_nonneg
The product of two non-negative numbers is non-negative.
le_of_lt
A strict inequality a < b implies the weak inequality a ≤ b.
op_258_capacity_floor_ge
For l ≥ 3, if x ≥ 1/2^(l-1), then 2^(2l - 2) * x ≤ ⌊x * C(2^l, 2)⌋₊.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finite set s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ s} g(i).
Finset.mul_sum
Multiplication distributes over finite sums: a * ∑_{i ∈ s} f(i) = ∑_{i ∈ s} a * f(i).
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c by a non-negative scalar a preserves the inequality: a * b ≤ a * c.
one_div
Division by a equals multiplication by its inverse: 1 / a = a⁻¹.
pow_sub₀
For a nonzero base a and n ≤ m, a^(m - n) = a^m * (a^n)⁻¹.

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

/-- Existence of divergent profile capacity coverings for hypercube layers. -/theorem op_258_exists_divergent_capacity_covering    (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a)    (hsum : (∑' i : ℕ+, ENNReal.ofReal (a i)) = ⊤) (n₀ : ℕ) :    ∃ (l : ℕ) (hl : 1 ≤ l) (I : Fin l → Finset ℕ+) (cap : ℕ+ → ℕ),      n₀ ≤ 2^l ∧      (∀ j₁ j₂ : Fin l, j₁ ≠ j₂ → Disjoint (I j₁) (I j₂)) ∧      (∀ j : Fin l, ∀ i ∈ I j, (cap i : ℝ) ≤ a i * ((2^l).choose 2 : ℝ)) ∧      (∀ j : Fin l, 2^(2 * l - 2 - (j : ℕ)) ≤ ∑ i ∈ I j, cap i) := by  classical  obtain ⟨l, hl3, r, hn0, hmono, hend, hblk⟩ :=    op_258_exists_divergent_block_indices a hpos hanti hsum n₀  refine ⟨l, by omega,    fun j : Fin l => Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩),    fun i => ⌊a i * ((2^l).choose 2 : ℝ)⌋₊, hn0, ?_, ?_, ?_⟩  · intro j₁ j₂ hne    rw [Finset.disjoint_left]    intro x hx1 hx2    rw [Finset.mem_Ioc] at hx1 hx2    rcases lt_or_gt_of_ne hne with hlt | hgt    · have hlt' : j₁.1 < j₂.1 := hlt      have hle : (⟨j₁.1+1, by omega⟩ : Fin (l+1)) ≤ ⟨j₂.1, by omega⟩ := by        rw [Fin.le_def]; exact Nat.succ_le_of_lt hlt'      have h1 : r ⟨j₁.1 + 1, by omega⟩ ≤ r ⟨j₂.1, by omega⟩ := hmono.monotone hle      exact (not_le.mpr hx2.1) (le_trans hx1.2 h1)    · have hlt' : j₂.1 < j₁.1 := hgt      have hle : (⟨j₂.1+1, by omega⟩ : Fin (l+1)) ≤ ⟨j₁.1, by omega⟩ := by        rw [Fin.le_def]; exact Nat.succ_le_of_lt hlt'      have h1 : r ⟨j₂.1 + 1, by omega⟩ ≤ r ⟨j₁.1, by omega⟩ := hmono.monotone hle      exact (not_le.mpr hx1.1) (le_trans hx2.2 h1)  · intro j i hi    exact Nat.floor_le (mul_nonneg (le_of_lt (hpos i)) (by positivity))  · intro j    have hle : ∀ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩),        (2:ℝ)^(2*l-2) * a i ≤ ((⌊a i * ((2^l).choose 2 : ℝ)⌋₊ : ℕ) : ℝ) := by      intro i hi      rw [Finset.mem_Ioc] at hi      have hi_le : i ≤ r ⟨l, by omega⟩ := by        have h1 : r ⟨j.1 + 1, by omega⟩ ≤ r ⟨l, by omega⟩ := by          apply hmono.monotone          rw [Fin.le_def]; exact Nat.succ_le_of_lt j.2        exact le_trans hi.2 h1      have hai : 1 / (2:ℝ)^(l-1) ≤ a i := le_trans hend (hanti hi_le)      exact op_258_capacity_floor_ge l hl3 (a i) hai    have hsum_le := Finset.sum_le_sum hle    rw [← Finset.mul_sum] at hsum_le    have key : (2:ℝ)^(2*l-2) * (1/(2:ℝ)^(j:ℕ)) ≤        (2:ℝ)^(2*l-2) * (∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩), a i) :=      mul_le_mul_of_nonneg_left (hblk j) (by positivity)    have hstep : (2:ℝ)^(2*l-2) * (1/(2:ℝ)^(j:ℕ)) ≤        ∑ i ∈ Finset.Ioc (r ⟨j.1, by omega⟩) (r ⟨j.1 + 1, by omega⟩),          ((⌊a i * ((2^l).choose 2 : ℝ)⌋₊ : ℕ) : ℝ) :=      le_trans key hsum_le    rw [one_div, ← pow_sub₀ (2:ℝ) (by norm_num) (by omega)] at hstep    exact_mod_cast hstep
See it in the graphDiscuss this resultChallenge it