AFTD Auto-Formalizing Theoretical Domains

equal_length_proportional_cake_prefix_volume

theoremverified

In any equal-length proportional cake allocation C : Fin n → Set ℝ for n ≥ 1 under the identical valuation profile where each agent values only the prefix [0, 1/n], each bundle C i has prefix Lebesgue measure volume (C i ∩ Set.Icc 0 (1 / n)) equal to ENNReal.ofReal (1 / n^2).

Statement

theorem equal_length_proportional_cake_prefix_volume (n : ℕ) (hn : 1 ≤ n)
    (C : Fin n → Set ℝ)
    (h_alloc : is_cake_allocation n C)
    (h_len : is_equal_length_allocation n C)
    (h_prop : is_prop_lb_proportional n C)
    (i : Fin n) :
    MeasureTheory.volume (C i ∩ Set.Icc 0 (1 / (n : ℝ))) = ENNReal.ofReal (1 / ((n : ℝ) ^ 2))
Source
scout/2610-19733-exact-cut-complexity-of-equal-length-proportional-cake-cutt.md:385
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • is_cake_allocationAn allocation of the cake [0, 1] among n agents is a measurable partition of [0, 1] into n bundles C i.
  • is_equal_length_allocationAn allocation is equal-length if each bundle has Lebesgue measure equal to 1 / n.
  • is_prop_lb_proportionalAn allocation is proportional with respect to the identical valuation profile where each agent's value is n * λ(S ∩ [0, 1/n]) if each…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

Read back from the Lean

Let $n$ be a natural number such that $1 \le n$. Let $C : \text{Fin } n \to \text{Set } \mathbb{R}$ be an allocation of $[0, 1]$ into $n$ pieces (that is, each $C i$ is measurable, they are pairwise disjoint, and their union is $[0, 1]$). Suppose that $C$ is an equal-length allocation (every $C i$ has Lebesgue volume $1/n$) and satisfies the proportional lower-bound condition (for all $j \in \text{Fin } n$, $(1 : \text{ENNReal}) / n \le n \cdot \text{volume}(C j \cap [0, 1/n])$). Then for any $i \in \text{Fin } n$, the Lebesgue volume of $C i \cap [0, 1/n]$ is equal to $1 / n^2$ (as an extended non-negative real).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By proportionality under the lower-bound valuation profile, each agent's prefix bundle C j ∩ [0, 1/n] must have volume at least 1/n^2. Because the bundles C j partition the cake [0, 1] and [0, 1/n] ⊆ [0, 1], these prefix bundles form a disjoint partition of [0, 1/n], meaning their volumes sum to the total volume of [0, 1/n], which is 1/n. Since n non-negative terms each bounded below by 1/n^2 sum to n * (1/n^2) = 1/n < ∞, every term must attain its lower bound exactly.

  1. If g ≤ f pointwise on Fin n, their sums are equal, and the total sum is finite, then f = g everywhere.

    Line 9 stores the hypothesis `h_len`. Lines 10–29 establish the helper lemma `h_eq_of_sum_eq`: suppose for contradiction that f k ≠ g k for some index k. Since g k ≤ f k, this means g k < f k. Decomposing both sums by isolating the k-th term from the remaining n - 1 terms, the sum of the remaining terms of g is at most that of f, and is finite because it is bounded by the finite total sum. Adding g k < f k strictly preserves inequality, yielding ∑ j, g j < ∑ j, f j, contradicting the assumption that the sums are equal.

    lines 9–29

    uses lt_of_le_of_ne, Ne.symm, Finset.add_sum_erase, Finset.sum_le_sum, ne_of_lt, lt_of_le_of_lt, Finset.sum_le_sum_of_subset, Finset.subset_univ, ENNReal.add_lt_add_of_lt_of_le

      have _ := h_len
      have h_eq_of_sum_eq (k : Fin n) (f g : Fin n → ENNReal)
          (h_le : ∀ j, g j ≤ f j)
          (h_sum : ∑ j, f j = ∑ j, g j)
          (h_top : (∑ j, g j) ≠ ⊤) :
          f k = g k := by
        by_contra h_ne
        have h_lt : g k < f k := lt_of_le_of_ne (h_le k) (Ne.symm h_ne)
        have h_split_f : ∑ j, f j = f k + ∑ j ∈ Finset.univ.erase k, f j :=
          (Finset.add_sum_erase Finset.univ f (Finset.mem_univ k)).symm
        have h_split_g : ∑ j, g j = g k + ∑ j ∈ Finset.univ.erase k, g j :=
          (Finset.add_sum_erase Finset.univ g (Finset.mem_univ k)).symm
        have h_rest_le : ∑ j ∈ Finset.univ.erase k, g j ≤ ∑ j ∈ Finset.univ.erase k, f j :=
          Finset.sum_le_sum (fun j _ => h_le j)
        have h_rest_ne_top : (∑ j ∈ Finset.univ.erase k, g j) ≠ ⊤ := by
          apply ne_of_lt
          exact lt_of_le_of_lt (Finset.sum_le_sum_of_subset (Finset.subset_univ _)) (lt_top_iff_ne_top.mpr h_top)
        have h_strict : ∑ j, g j < ∑ j, f j := by
          rw [h_split_g, h_split_f]
          exact ENNReal.add_lt_add_of_lt_of_le h_rest_ne_top h_lt h_rest_le
        exact (ne_of_lt h_strict) h_sum.symm
  2. In ENNReal, n is nonzero and finite.

    Since 1 ≤ n, linear arithmetic confirms n ≠ 0, and the coercion of any natural number into ENNReal is finite.

    lines 30–33

    uses ENNReal.natCast_ne_top

      have hn_ne_zero : (n : ENNReal) ≠ 0 := by
        norm_cast
        omega
      have hn_ne_top : (n : ENNReal) ≠ ⊤ := ENNReal.natCast_ne_top n
  3. For every bundle C j, the volume of C j ∩ [0, 1/n] is at least 1 / n^2.

    The proportionality hypothesis `h_prop` asserts 1 / n ≤ n * volume (C j ∩ [0, 1/n]). Dividing both sides by n and rewriting (1 / n) / n as 1 / n^2 establishes the pointwise lower bound.

    lines 34–40

    uses ENNReal.div_le_iff', sq, div_eq_mul_inv, ENNReal.mul_inv

      have h_le : ∀ j, (1 : ENNReal) / ((n : ENNReal) ^ 2) ≤ MeasureTheory.volume (C j ∩ Set.Icc 0 (1 / (n : ℝ))) := by
        intro j
        have hj := h_prop j
        have h1 := (ENNReal.div_le_iff' hn_ne_zero hn_ne_top).mpr hj
        rw [sq, div_eq_mul_inv, ENNReal.mul_inv (Or.inl hn_ne_zero) (Or.inl hn_ne_top),
            ← mul_assoc, ← div_eq_mul_inv, ← div_eq_mul_inv]
        exact h1
  4. The sum of the lower bounds over all n agents equals 1 / n.

    Summing the constant 1 / n^2 over Fin n yields n * (1 / n^2). Expanding n^2 and cancelling n * n⁻¹ simplifies this product to 1 / n.

    lines 41–45

    uses Finset.sum_const, Finset.card_fin, nsmul_eq_mul, sq, div_eq_mul_inv, ENNReal.mul_inv, ENNReal.mul_inv_cancel

      have h_sum_g : ∑ _j : Fin n, (1 : ENNReal) / ((n : ENNReal) ^ 2) = 1 / (n : ENNReal) := by
        rw [Finset.sum_const, Finset.card_fin, nsmul_eq_mul]
        rw [sq, div_eq_mul_inv, ENNReal.mul_inv (Or.inl hn_ne_zero) (Or.inl hn_ne_top)]
        rw [one_mul, ← mul_assoc, ENNReal.mul_inv_cancel hn_ne_zero hn_ne_top, one_mul,
            div_eq_mul_inv, one_mul]
  5. The prefix intersections C j ∩ [0, 1/n] are pairwise disjoint and measurable.

    Disjointness follows because the original bundles C j are pairwise disjoint and shrinking to a subset preserves disjointness. Measurability follows because each C j is measurable and the interval [0, 1/n] is measurable.

    lines 46–52

    uses Disjoint.mono, Set.inter_subset_left, measurableSet_Icc

      have hd' : ((Finset.univ : Finset (Fin n)) : Set (Fin n)).PairwiseDisjoint (fun j => C j ∩ Set.Icc 0 (1 / (n : ℝ))) := by
        intro x _ y _ hxy
        refine Disjoint.mono (Set.inter_subset_left) (Set.inter_subset_left) ?_
        exact h_alloc.2.1 x y hxy
      have hm' : ∀ j, MeasurableSet (C j ∩ Set.Icc 0 (1 / (n : ℝ))) := by
        intro j
        exact (h_alloc.1 j).inter measurableSet_Icc
  6. The sum of the volumes of all prefix intersections equals the volume of [0, 1/n].

    By finite additivity for disjoint measurable sets, the sum of their volumes equals the volume of their union. Distributing intersection over the union gives (⋃ j, C j) ∩ [0, 1/n] = [0, 1] ∩ [0, 1/n]. Since 1 ≤ n implies [0, 1/n] ⊆ [0, 1], this intersection is exactly [0, 1/n].

    lines 53–65

    uses MeasureTheory.measure_biUnion_finset, Set.iUnion_inter, Set.inter_eq_self_of_subset_right, Set.mem_Icc, le_trans, div_le_one_of_le₀

      have h_sum_f : ∑ j, MeasureTheory.volume (C j ∩ Set.Icc 0 (1 / (n : ℝ))) = MeasureTheory.volume (Set.Icc 0 (1 / (n : ℝ))) := by
        have h_biu := MeasureTheory.measure_biUnion_finset (μ := MeasureTheory.volume) hd' (fun b _ => hm' b)
        rw [← h_biu]
        have h_union : (⋃ b ∈ (Finset.univ : Finset (Fin n)), C b ∩ Set.Icc 0 (1 / (n : ℝ))) = Set.Icc 0 (1 / (n : ℝ)) := by
          simp only [Finset.mem_univ, Set.iUnion_true]
          rw [← Set.iUnion_inter, h_alloc.2.2]
          apply Set.inter_eq_self_of_subset_right
          intro x hx
          rw [Set.mem_Icc] at hx ⊢
          refine ⟨hx.1, le_trans hx.2 ?_⟩
          have hn' : (1 : ℝ) ≤ (n : ℝ) := Nat.one_le_cast.mpr hn
          exact div_le_one_of_le₀ hn' (by linarith)
        rw [h_union]
  7. The volume of the interval [0, 1/n] is 1 / n.

    The Lebesgue measure of [0, 1/n] is ofReal (1 / n - 0) = ofReal (1 / n). Since n > 0, this equals ofReal 1 / ofReal n = 1 / n in ENNReal.

    lines 66–70

    uses Real.volume_Icc, sub_zero, ENNReal.ofReal_div_of_pos

      have h_vol_S : MeasureTheory.volume (Set.Icc (0 : ℝ) (1 / (n : ℝ))) = 1 / (n : ENNReal) := by
        rw [Real.volume_Icc, sub_zero]
        have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn
        rw [ENNReal.ofReal_div_of_pos hn_pos]
        simp
  8. The volume of bundle C i intersected with [0, 1/n] equals 1 / n^2 in ENNReal.

    Both the sum of the volumes and the sum of the lower bounds equal 1 / n, which is finite. Applying the helper lemma h_eq_of_sum_eq to the pointwise inequality shows that each term equals the lower bound 1 / n^2.

    lines 71–80

    uses ENNReal.div_ne_top, ENNReal.one_ne_top

      have h_sum_eq : ∑ j, MeasureTheory.volume (C j ∩ Set.Icc 0 (1 / (n : ℝ))) =
          ∑ _j : Fin n, (1 : ENNReal) / ((n : ENNReal) ^ 2) := by
        rw [h_sum_f, h_vol_S, h_sum_g]
      have h_top : (∑ _j : Fin n, (1 : ENNReal) / ((n : ENNReal) ^ 2)) ≠ ⊤ := by
        rw [h_sum_g]
        exact ENNReal.div_ne_top ENNReal.one_ne_top hn_ne_zero
      have h_res := h_eq_of_sum_eq i
        (fun j => MeasureTheory.volume (C j ∩ Set.Icc 0 (1 / (n : ℝ))))
        (fun _ => 1 / ((n : ENNReal) ^ 2))
        h_le h_sum_eq h_top
  9. The volume of C i ∩ [0, 1/n] equals ENNReal.ofReal (1 / n^2).

    Since n > 0 implies n^2 > 0, the real division 1 / n^2 transfers into ENNReal as ofReal 1 / ofReal (n^2) = 1 / n^2, matching the calculated bundle volume.

    lines 81–85

    uses sq_pos_of_pos, ENNReal.ofReal_div_of_pos

      rw [h_res]
      have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn
      have hn2_pos : 0 < (n : ℝ) ^ 2 := sq_pos_of_pos hn_pos
      rw [ENNReal.ofReal_div_of_pos hn2_pos]
      simp
lt_of_le_of_ne
if a ≤ b and a ≠ b, then a < b
Ne.symm
inequality is symmetric: a ≠ b implies b ≠ a
Finset.add_sum_erase
a sum over a finite set s splits into the term at an element a ∈ s plus the sum over s \ {a}
Finset.sum_le_sum
if f(j) ≤ g(j) for all j in a finite set, then ∑ j, f(j) ≤ ∑ j, g(j)
ne_of_lt
strict inequality implies inequality: a < b implies a ≠ b
lt_of_le_of_lt
if a ≤ b and b < c, then a < c
Finset.sum_le_sum_of_subset
in a canonically ordered monoid, a sum over a subset is at most the sum over the superset
Finset.subset_univ
every finite set of elements of a finite type is a subset of the universal set
ENNReal.add_lt_add_of_lt_of_le
in [0, ∞], if c ≠ ∞, a < b, and c ≤ d, then a + c < b + d
ENNReal.natCast_ne_top
the coercion of a natural number into [0, ∞] is finite (not ∞)
ENNReal.div_le_iff'
for nonzero finite y, x / y ≤ z if and only if x ≤ y * z
sq
the square a ^ 2 is defined as a * a
div_eq_mul_inv
division is multiplication by the inverse: a / b = a * b⁻¹
ENNReal.mul_inv
(a * b)⁻¹ = a⁻¹ * b⁻¹ when neither factor creates an undefined 0 * ∞ product
Finset.sum_const
summing a constant b over a finite set s gives |s| • b
Finset.card_fin
the cardinality of Fin n is n
nsmul_eq_mul
scalar multiplication by a natural number n equals multiplication by the coerced natural n
ENNReal.mul_inv_cancel
a * a⁻¹ = 1 for any nonzero finite a in [0, ∞]
Disjoint.mono
if a ⊆ b, c ⊆ d, and b and d are disjoint, then a and c are disjoint
Set.inter_subset_left
the intersection s ∩ t is a subset of s
measurableSet_Icc
any closed interval [a, b] in ℝ is measurable
MeasureTheory.measure_biUnion_finset
the measure of a pairwise disjoint finite union of measurable sets is the sum of their measures
Set.iUnion_inter
intersection distributes over unions: (⋃ i, t i) ∩ s = ⋃ i, (t i ∩ s)
Set.inter_eq_self_of_subset_right
if t ⊆ s, then s ∩ t = t
Set.mem_Icc
x ∈ [a, b] if and only if a ≤ x and x ≤ b
le_trans
transitivity of ordering: a ≤ b and b ≤ c imply a ≤ c
div_le_one_of_le₀
if a ≤ b and 0 ≤ b, then a / b ≤ 1
Real.volume_Icc
the Lebesgue measure of [a, b] is ofReal (b - a)
sub_zero
subtracting zero leaves an element unchanged: a - 0 = a
ENNReal.ofReal_div_of_pos
for positive y, ofReal (x / y) = ofReal x / ofReal y
ENNReal.div_ne_top
if x ≠ ∞ and y ≠ 0, then x / y ≠ ∞
ENNReal.one_ne_top
1 ≠ ∞ in [0, ∞]
sq_pos_of_pos
if a > 0, then a ^ 2 > 0

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

/-- In any equal-length proportional allocation under the lower-bound valuation profile, each bundle has prefix volume 1/n^2. -/theorem equal_length_proportional_cake_prefix_volume (n : ℕ) (hn : 1 ≤ n)    (C : Fin n → Set ℝ)    (h_alloc : is_cake_allocation n C)    (h_len : is_equal_length_allocation n C)    (h_prop : is_prop_lb_proportional n C)    (i : Fin n) :    MeasureTheory.volume (C i ∩ Set.Icc 0 (1 / (n : ℝ))) = ENNReal.ofReal (1 / ((n : ℝ) ^ 2)) := by  have _ := h_len  have h_eq_of_sum_eq (k : Fin n) (f g : Fin n → ENNReal)      (h_le : ∀ j, g j ≤ f j)      (h_sum : ∑ j, f j = ∑ j, g j)      (h_top : (∑ j, g j) ≠ ⊤) :      f k = g k := by    by_contra h_ne    have h_lt : g k < f k := lt_of_le_of_ne (h_le k) (Ne.symm h_ne)    have h_split_f : ∑ j, f j = f k + ∑ j ∈ Finset.univ.erase k, f j :=      (Finset.add_sum_erase Finset.univ f (Finset.mem_univ k)).symm    have h_split_g : ∑ j, g j = g k + ∑ j ∈ Finset.univ.erase k, g j :=      (Finset.add_sum_erase Finset.univ g (Finset.mem_univ k)).symm    have h_rest_le : ∑ j ∈ Finset.univ.erase k, g j ≤ ∑ j ∈ Finset.univ.erase k, f j :=      Finset.sum_le_sum (fun j _ => h_le j)    have h_rest_ne_top : (∑ j ∈ Finset.univ.erase k, g j) ≠ ⊤ := by      apply ne_of_lt      exact lt_of_le_of_lt (Finset.sum_le_sum_of_subset (Finset.subset_univ _)) (lt_top_iff_ne_top.mpr h_top)    have h_strict : ∑ j, g j < ∑ j, f j := by      rw [h_split_g, h_split_f]      exact ENNReal.add_lt_add_of_lt_of_le h_rest_ne_top h_lt h_rest_le    exact (ne_of_lt h_strict) h_sum.symm  have hn_ne_zero : (n : ENNReal) ≠ 0 := by    norm_cast    omega  have hn_ne_top : (n : ENNReal) ≠ ⊤ := ENNReal.natCast_ne_top n  have h_le : ∀ j, (1 : ENNReal) / ((n : ENNReal) ^ 2) ≤ MeasureTheory.volume (C j ∩ Set.Icc 0 (1 / (n : ℝ))) := by    intro j    have hj := h_prop j    have h1 := (ENNReal.div_le_iff' hn_ne_zero hn_ne_top).mpr hj    rw [sq, div_eq_mul_inv, ENNReal.mul_inv (Or.inl hn_ne_zero) (Or.inl hn_ne_top),        ← mul_assoc, ← div_eq_mul_inv, ← div_eq_mul_inv]    exact h1  have h_sum_g : ∑ _j : Fin n, (1 : ENNReal) / ((n : ENNReal) ^ 2) = 1 / (n : ENNReal) := by    rw [Finset.sum_const, Finset.card_fin, nsmul_eq_mul]    rw [sq, div_eq_mul_inv, ENNReal.mul_inv (Or.inl hn_ne_zero) (Or.inl hn_ne_top)]    rw [one_mul, ← mul_assoc, ENNReal.mul_inv_cancel hn_ne_zero hn_ne_top, one_mul,        div_eq_mul_inv, one_mul]  have hd' : ((Finset.univ : Finset (Fin n)) : Set (Fin n)).PairwiseDisjoint (fun j => C j ∩ Set.Icc 0 (1 / (n : ℝ))) := by    intro x _ y _ hxy    refine Disjoint.mono (Set.inter_subset_left) (Set.inter_subset_left) ?_    exact h_alloc.2.1 x y hxy  have hm' : ∀ j, MeasurableSet (C j ∩ Set.Icc 0 (1 / (n : ℝ))) := by    intro j    exact (h_alloc.1 j).inter measurableSet_Icc  have h_sum_f : ∑ j, MeasureTheory.volume (C j ∩ Set.Icc 0 (1 / (n : ℝ))) = MeasureTheory.volume (Set.Icc 0 (1 / (n : ℝ))) := by    have h_biu := MeasureTheory.measure_biUnion_finset (μ := MeasureTheory.volume) hd' (fun b _ => hm' b)    rw [← h_biu]    have h_union : (⋃ b ∈ (Finset.univ : Finset (Fin n)), C b ∩ Set.Icc 0 (1 / (n : ℝ))) = Set.Icc 0 (1 / (n : ℝ)) := by      simp only [Finset.mem_univ, Set.iUnion_true]      rw [← Set.iUnion_inter, h_alloc.2.2]      apply Set.inter_eq_self_of_subset_right      intro x hx      rw [Set.mem_Icc] at hx ⊢      refine ⟨hx.1, le_trans hx.2 ?_⟩      have hn' : (1 : ℝ) ≤ (n : ℝ) := Nat.one_le_cast.mpr hn      exact div_le_one_of_le₀ hn' (by linarith)    rw [h_union]  have h_vol_S : MeasureTheory.volume (Set.Icc (0 : ℝ) (1 / (n : ℝ))) = 1 / (n : ENNReal) := by    rw [Real.volume_Icc, sub_zero]    have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn    rw [ENNReal.ofReal_div_of_pos hn_pos]    simp  have h_sum_eq : ∑ j, MeasureTheory.volume (C j ∩ Set.Icc 0 (1 / (n : ℝ))) =      ∑ _j : Fin n, (1 : ENNReal) / ((n : ENNReal) ^ 2) := by    rw [h_sum_f, h_vol_S, h_sum_g]  have h_top : (∑ _j : Fin n, (1 : ENNReal) / ((n : ENNReal) ^ 2)) ≠ ⊤ := by    rw [h_sum_g]    exact ENNReal.div_ne_top ENNReal.one_ne_top hn_ne_zero  have h_res := h_eq_of_sum_eq i    (fun j => MeasureTheory.volume (C j ∩ Set.Icc 0 (1 / (n : ℝ))))    (fun _ => 1 / ((n : ENNReal) ^ 2))    h_le h_sum_eq h_top  rw [h_res]  have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn  have hn2_pos : 0 < (n : ℝ) ^ 2 := sq_pos_of_pos hn_pos  rw [ENNReal.ofReal_div_of_pos hn2_pos]  simp
See it in the graphDiscuss this resultChallenge it