equal_length_proportional_cake_prefix_volume
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]amongnagents is a measurable partition of[0, 1]intonbundlesC 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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- is_cake_allocationAn allocation of the cake
- Used by 1
- equal_length_proportional_cake_cutting_cut_complexity_lbFor every integer n ≥ 1, if C : Fin n → Set ℝ is an equal-length proportional cake allocation among n agents under the identical valuation…
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.
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.
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_lehave _ := 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
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.
uses
ENNReal.natCast_ne_tophave hn_ne_zero : (n : ENNReal) ≠ 0 := by norm_cast omega have hn_ne_top : (n : ENNReal) ≠ ⊤ := ENNReal.natCast_ne_top n
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.
uses
ENNReal.div_le_iff',sq,div_eq_mul_inv,ENNReal.mul_invhave 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
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.
uses
Finset.sum_const,Finset.card_fin,nsmul_eq_mul,sq,div_eq_mul_inv,ENNReal.mul_inv,ENNReal.mul_inv_cancelhave 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]
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.
uses
Disjoint.mono,Set.inter_subset_left,measurableSet_Icchave 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
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].
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]
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.
uses
Real.volume_Icc,sub_zero,ENNReal.ofReal_div_of_poshave 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
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.
uses
ENNReal.div_ne_top,ENNReal.one_ne_tophave 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
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.
uses
sq_pos_of_pos,ENNReal.ofReal_div_of_posrw [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
- The hypothesis `h_len` (that each bundle has total volume 1/n) is provided in the theorem statement and retained in line 9, but is never needed or used in the proof; proportionality on the prefix interval alone determines the prefix volume.
- Arithmetic in `ENNReal` explicitly checks that n is neither 0 nor ∞ to justify division and cancellation of factors.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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