halving_partition_length_le
For every positive integer n and every halving partition p of n, the length of p is at most Nat.log 2 n + (Nat.digits 2 n).sum.
Statement
theorem halving_partition_length_le (n : ℕ) (hn : 0 < n) (p : List ℕ)
(hp : is_halving_partition n p) :
p.length ≤ Nat.log 2 n + (Nat.digits 2 n).sum- Formalizes
- arXiv:2611.01243 Theorem 3
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_halving_partitionA sequence of positive integers $(p_1, \dots, p_k)$ is a halving partition of $n \ge 1$ if…
Read back from the Lean
For every natural number $n > 0$ and every list of natural numbers $p$, if $p$ is a "halving partition" of $n$ (satisfying is_halving_partition n p), then the length of $p$ is at most $\lfloor \log_2 n \rfloor$ plus the sum of the base-2 digits of $n$ (the Hamming weight of $n$).
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
The proof decomposes a halving partition p of n into its prefix of length h = ⌊log₂ n⌋ and the remaining suffix of length |p| - h. Along the halving chain, each element p[i] is shown by induction to be at least ⌊n / 2^(i + 1)⌋, which forces the prefix sum to be at least n - s₂(n), where s₂(n) is the binary digit sum of n. Since every part is a positive integer, the remaining suffix contributes at least |p| - h to the total sum n. Combining these two lower bounds gives n ≥ (n - s₂(n)) + (|p| - h), which rearranges to |p| ≤ ⌊log₂ n⌋ + s₂(n).
Adjacent elements in a chained list satisfy the chaining relation: R(l[i], l[i + 1]) for all i with i + 1 < |l|.
By induction on the chain hypothesis `List.IsChain R l`. An empty list is impossible because i + 1 < 0 is a contradiction; a singleton list has length 1, so i + 1 < 1 is also impossible. For a list starting with a and b, if i = 0 the relation holds directly by the constructor hypothesis `hab`, and if i is a successor we strip the head and apply the induction hypothesis to the tail.
uses
List.length_singleton,List.getElem_cons_succlemma halving_partition_length_le_isChain_getElem {α : Type*} {R : α → α → Prop} {l : List α} (h : List.IsChain R l) (i : ℕ) (hi : i + 1 < l.length) : R l[i] l[i+1] := by induction h generalizing i with | nil => contradiction | singleton a => simp only [List.length_singleton] at hi omega | cons_cons hab hchain ih => cases i with | zero => exact hab | succ i => rw [List.getElem_cons_succ, List.getElem_cons_succ] apply ih
Successive halving satisfies (n / 2^(i + 1)) / 2 = n / 2^(i + 2).
By `Nat.div_div_eq_div_mul`, dividing by 2^(i + 1) and then by 2 equals dividing by 2^(i + 1) * 2, which rewrites by `pow_succ` to 2^(i + 2).
uses
Nat.div_div_eq_div_mul,pow_succlemma halving_partition_length_le_div_pow_div_two (n i : ℕ) : (n / 2 ^ (i + 1)) / 2 = n / 2 ^ (i + 1 + 1) := by rw [Nat.div_div_eq_div_mul, ← pow_succ]
A halving partition p of n is non-empty, and its first part satisfies p[0] ≥ ⌊n / 2⌋.
From the definition of a halving partition, p cannot be empty because its elements are positive and sum to n. Its first element p[0] must be either n / 2 or (n + 1) / 2. Since n / 2 ≤ n / 2 by reflexivity and n / 2 ≤ (n + 1) / 2 by monotonicity of division, p[0] ≥ n / 2 = n / 2^(0 + 1) in both cases.
uses
zero_add,pow_one,le_rfl,Nat.div_le_div_right,Nat.le_succlemma halving_partition_length_le_part_ge_div_pow_two (n : ℕ) (p : List ℕ) (hp : is_halving_partition n p) (i : ℕ) (hi : i < p.length) : n / 2 ^ (i + 1) ≤ p[i] := by dsimp [is_halving_partition] at hp rcases hp with ⟨hpos, hsum, hrest⟩ cases p with | nil => contradiction | cons p1 pt => rcases hrest with ⟨hp1, hchain⟩ induction i with | zero => simp only [zero_add, pow_one] rcases hp1 with rfl | rfl · exact le_rfl · exact Nat.div_le_div_right (Nat.le_succ n)
By induction on i, each element of a halving partition satisfies p[i] ≥ ⌊n / 2^(i + 1)⌋.
Assuming p[i] ≥ n / 2^(i + 1), the halving chain condition gives p[i + 1] ≥ ⌊p[i] / 2⌋. By division monotonicity, ⌊(n / 2^(i + 1)) / 2⌋ ≤ ⌊p[i] / 2⌋. Since (n / 2^(i + 1)) / 2 = n / 2^(i + 2), transitivity yields n / 2^(i + 2) ≤ p[i + 1].
uses
halving_partition_length_le_isChain_getElem,Nat.div_le_div_right,Nat.le_succ,halving_partition_length_le_div_pow_div_two| succ i ih => have hi_lt : i < (p1 :: pt).length := by omega have ih_val := ih hi_lt have hrel := halving_partition_length_le_isChain_getElem hchain i (by omega) have hdiv_le : (p1 :: pt)[i] / 2 ≤ (p1 :: pt)[i + 1] := by rcases hrel with h1 | h2 · rw [h1] · rw [h2] exact Nat.div_le_div_right (Nat.le_succ _) have h_trans : (n / 2 ^ (i + 1)) / 2 ≤ (p1 :: pt)[i] / 2 := Nat.div_le_div_right ih_val rw [halving_partition_length_le_div_pow_div_two] at h_trans exact h_trans.trans hdiv_leFor any list of natural numbers whose elements are all at least 1, the list's length is at most its sum.
By induction on the list. The empty list has length 0 and sum 0. For a :: l, the head satisfies 1 ≤ a and the tail satisfies |l| ≤ sum(l) by the induction hypothesis; adding these yields |a :: l| = |l| + 1 ≤ sum(l) + a = sum(a :: l).
uses
List.length_cons,List.sum_cons,List.mem_cons_self,List.mem_cons_of_memlemma halving_partition_length_le_list_sum_ge_length (l : List ℕ) (h : ∀ x ∈ l, 1 ≤ x) : l.length ≤ l.sum := by induction l with | nil => simp | cons a l ih => simp only [List.length_cons, List.sum_cons] have ha : 1 ≤ a := h a (List.mem_cons_self ..) have hl : l.length ≤ l.sum := ih (fun x hx => h x (List.mem_cons_of_mem a hx)) omega
If p[i] ≥ f(i) for all i < k ≤ |p|, then the sum of the first k elements of p is at least ∑_{i < k} f(i).
By induction on k. The base case k = 0 is 0 ≤ 0. For k + 1, we split the range sum into ∑_{i < k} f(i) + f(k) and split the prefix of length k + 1 into take k p ++ [p[k]]. The induction hypothesis bounds the first k terms and the assumption gives f(k) ≤ p[k], so their sum bounds the prefix sum.
uses
Finset.sum_range_succ,List.take_concat_get',List.sum_append,List.sum_singletonlemma halving_partition_length_le_sum_take_ge_sum_range (p : List ℕ) (f : ℕ → ℕ) (k : ℕ) (hk : k ≤ p.length) (h : ∀ (i : ℕ) (hi : i < p.length), i < k → f i ≤ p[i]) : ∑ i ∈ Finset.range k, f i ≤ (p.take k).sum := by induction k with | zero => simp | succ k ih => rw [Finset.sum_range_succ] have hk' : k < p.length := by omega have htake := (List.take_concat_get' p k hk').symm rw [htake, List.sum_append, List.sum_singleton] have ih_le : ∑ i ∈ Finset.range k, f i ≤ (p.take k).sum := by apply ih (by omega) intro i hi_p hi_k exact h i hi_p (by omega) have hlast : f k ≤ p[k] := h k hk' (by omega) omega
The sum ∑_{i < ⌊log₂ n⌋} ⌊n / 2^(i + 1)⌋ equals n - s₂(n), where s₂(n) is the binary digit sum of n.
The base-2 identity for digit sums gives (2 - 1) * ∑_{i ≤ ⌊log₂ n⌋} ⌊n / 2^(i + 1)⌋ = n - s₂(n), which simplifies to ∑_{i ≤ ⌊log₂ n⌋} ⌊n / 2^(i + 1)⌋ = n - s₂(n). Splitting off the top term at index ⌊log₂ n⌋, that term is ⌊n / 2^(⌊log₂ n⌋ + 1)⌋ = 0 because n < 2^(⌊log₂ n⌋ + 1). Removing this zero term leaves the sum over i < ⌊log₂ n⌋.
uses
Nat.sub_one_mul_sum_log_div_pow_eq_sub_sum_digits,Nat.reduceSub,one_mul,Finset.sum_range_succ,Nat.div_eq_of_lt,Nat.lt_pow_succ_log_self,add_zerolemma halving_partition_length_le_sum_div_pow_two_eq (n : ℕ) : ∑ i ∈ Finset.range (Nat.log 2 n), n / 2 ^ (i + 1) = n - (Nat.digits 2 n).sum := by have h := @Nat.sub_one_mul_sum_log_div_pow_eq_sub_sum_digits 2 n simp only [Nat.reduceSub, one_mul] at h rw [← h] rw [Finset.sum_range_succ] have hzero : n / 2 ^ (Nat.log 2 n).succ = 0 := by apply Nat.div_eq_of_lt exact Nat.lt_pow_succ_log_self (by decide) n rw [hzero, add_zero]
Setting h = ⌊log₂ n⌋, either |p| ≤ h (which immediately proves the theorem) or h ≤ |p|.
We perform a case split on whether |p| ≤ h. If |p| ≤ h, the bound |p| ≤ h + s₂(n) is immediate because digit sums are non-negative. Otherwise, we assume h ≤ |p|.
theorem halving_partition_length_le (n : ℕ) (hn : 0 < n) (p : List ℕ) (hp : is_halving_partition n p) : p.length ≤ Nat.log 2 n + (Nat.digits 2 n).sum := by let h := Nat.log 2 n by_cases hlen : p.length ≤ h · omega have hh_le : h ≤ p.length := by omega
The sum of the first h elements of p is at least n - s₂(n).
Since p[i] ≥ ⌊n / 2^(i + 1)⌋ for all i < h ≤ |p|, Lemma 5 shows that the prefix sum of the first h elements is at least ∑_{i < h} ⌊n / 2^(i + 1)⌋. By Lemma 6, this sum equals n - s₂(n).
uses
List.sum_append,List.take_append_drop,halving_partition_length_le_sum_take_ge_sum_range,halving_partition_length_le_part_ge_div_pow_two,halving_partition_length_le_sum_div_pow_two_eqhave hp_sum : p.sum = n := hp.2.1 have hp_pos : ∀ x ∈ p, 1 ≤ x := fun x hx => hp.1 x hx have hsplit : p.sum = (p.take h).sum + (p.drop h).sum := by rw [← List.sum_append, List.take_append_drop] have htake_ge : ∑ i ∈ Finset.range h, n / 2 ^ (i + 1) ≤ (p.take h).sum := by apply halving_partition_length_le_sum_take_ge_sum_range p (fun i => n / 2 ^ (i + 1)) h hh_le intro i hi _ exact halving_partition_length_le_part_ge_div_pow_two n p hp i hi rw [halving_partition_length_le_sum_div_pow_two_eq n] at htake_ge
The sum of the remaining |p| - h elements of p is at least |p| - h.
The suffix `drop h p` has length |p| - h. Since every element of p is positive (≥ 1), every element of the suffix is at least 1. By Lemma 4, the sum of this suffix is at least its length |p| - h.
uses
List.length_drop,halving_partition_length_le_list_sum_ge_length,List.mem_of_mem_drophave hdrop_ge : p.length - h ≤ (p.drop h).sum := by rw [← List.length_drop] apply halving_partition_length_le_list_sum_ge_length intro x hx exact hp_pos x (List.mem_of_mem_drop hx)
The total length of p is at most ⌊log₂ n⌋ + s₂(n).
The total sum is n = sum(take h p) + sum(drop h p). Combining the lower bound sum(take h p) ≥ n - s₂(n) with sum(drop h p) ≥ |p| - h, and using s₂(n) ≤ n, linear integer arithmetic yields n ≥ (n - s₂(n)) + (|p| - h), which rearranges to |p| ≤ h + s₂(n).
uses
Nat.digit_sum_lehave hdigits_le : (Nat.digits 2 n).sum ≤ n := Nat.digit_sum_le 2 n omega
zero_add- The sum of zero and a number equals the number: 0 + a = a.
pow_one- Any base raised to power 1 equals itself: a^1 = a.
le_rfl- Inequality ≤ is reflexive: a ≤ a.
Nat.div_le_div_right- Division of natural numbers by a constant preserves order: if a ≤ b, then a / c ≤ b / c.
Nat.le_succ- Every natural number is at most its successor: n ≤ n + 1.
List.length_singleton- The length of a singleton list is 1: [a].length = 1.
List.getElem_cons_succ- Accessing index i + 1 of a prepended list gives the i-th element of the tail: (a :: as)[i + 1] = as[i].
Nat.div_div_eq_div_mul- Successive division equals division by the product: (m / n) / k = m / (n * k).
pow_succ- Exponentiation satisfies a^(n + 1) = a^n * a.
halving_partition_length_le_isChain_getElem- In a chained list satisfying IsChain R, consecutive elements satisfy the relation: R l[i] l[i+1].
halving_partition_length_le_div_pow_div_two- Halving ⌊n / 2^(i + 1)⌋ yields ⌊n / 2^(i + 2)⌋.
List.length_cons- Prepending an element increases list length by 1: (a :: as).length = as.length + 1.
List.sum_cons- The sum of a prepended list is the head plus the tail sum: (a :: l).sum = a + l.sum.
List.mem_cons_self- The head of a list belongs to the list: a ∈ a :: l.
List.mem_cons_of_mem- An element of a tail list is also an element of the prepended list: a ∈ l → a ∈ y :: l.
Finset.sum_range_succ- The sum over range (n + 1) splits into the sum over range n plus the term at n.
List.take_concat_get'- Taking i + 1 elements from a list equals taking i elements concatenated with the singleton [l[i]].
List.sum_append- The sum of concatenated lists is the sum of their individual sums: (l₁ ++ l₂).sum = l₁.sum + l₂.sum.
List.sum_singleton- The sum of a singleton list [x] is x.
Nat.sub_one_mul_sum_log_div_pow_eq_sub_sum_digits- For base p, (p - 1) times the sum of ⌊n / p^(i + 1)⌋ over all powers up to log_p n equals n minus the sum of digits of n in base p.
Nat.reduceSub- Compiler simplification rule evaluating subtraction of numeral constants (here, 2 - 1 = 1).
one_mul- Multiplying by 1 leaves a number unchanged: 1 * a = a.
Nat.div_eq_of_lt- If a < b, then integer division a / b equals 0.
Nat.lt_pow_succ_log_self- For any base b > 1, x is strictly less than b^(⌊log_b x⌋ + 1).
add_zero- Adding zero on the right leaves a number unchanged: a + 0 = a.
List.take_append_drop- Concatenating the first i elements of a list with the remaining elements gives back the list.
halving_partition_length_le_sum_take_ge_sum_range- If each element of a list p dominates f(i) for all i < k ≤ |p|, then ∑_{i < k} f(i) ≤ sum(take k p).
halving_partition_length_le_part_ge_div_pow_two- In any halving partition p of n, each element p[i] is at least ⌊n / 2^(i + 1)⌋.
halving_partition_length_le_sum_div_pow_two_eq- The sum of ⌊n / 2^(i + 1)⌋ for i from 0 to ⌊log₂ n⌋ - 1 equals n minus the sum of binary digits of n.
List.length_drop- Dropping i elements leaves a list of length |l| - i.
halving_partition_length_le_list_sum_ge_length- A list whose elements are all at least 1 has sum at least its length.
List.mem_of_mem_drop- Any element of drop i l is an element of the original list l.
Nat.digit_sum_le- The sum of digits of n in base p is at most n.
- Linear arithmetic over ℕ (the omega tactic) handles truncated subtractions in several places, notably to combine the lower bounds on the prefix and suffix sums and conclude that |p| ≤ h + s₂(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
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.
lemma halving_partition_length_le_isChain_getElem {α : Type*} {R : α → α → Prop} {l : List α} (h : List.IsChain R l) (i : ℕ) (hi : i + 1 < l.length) : R l[i] l[i+1] := by induction h generalizing i with | nil => contradiction | singleton a => simp only [List.length_singleton] at hi omega | cons_cons hab hchain ih => cases i with | zero => exact hab | succ i => rw [List.getElem_cons_succ, List.getElem_cons_succ] apply ihlemma halving_partition_length_le_div_pow_div_two (n i : ℕ) : (n / 2 ^ (i + 1)) / 2 = n / 2 ^ (i + 1 + 1) := by rw [Nat.div_div_eq_div_mul, ← pow_succ]lemma halving_partition_length_le_part_ge_div_pow_two (n : ℕ) (p : List ℕ) (hp : is_halving_partition n p) (i : ℕ) (hi : i < p.length) : n / 2 ^ (i + 1) ≤ p[i] := by dsimp [is_halving_partition] at hp rcases hp with ⟨hpos, hsum, hrest⟩ cases p with | nil => contradiction | cons p1 pt => rcases hrest with ⟨hp1, hchain⟩ induction i with | zero => simp only [zero_add, pow_one] rcases hp1 with rfl | rfl · exact le_rfl · exact Nat.div_le_div_right (Nat.le_succ n) | succ i ih => have hi_lt : i < (p1 :: pt).length := by omega have ih_val := ih hi_lt have hrel := halving_partition_length_le_isChain_getElem hchain i (by omega) have hdiv_le : (p1 :: pt)[i] / 2 ≤ (p1 :: pt)[i + 1] := by rcases hrel with h1 | h2 · rw [h1] · rw [h2] exact Nat.div_le_div_right (Nat.le_succ _) have h_trans : (n / 2 ^ (i + 1)) / 2 ≤ (p1 :: pt)[i] / 2 := Nat.div_le_div_right ih_val rw [halving_partition_length_le_div_pow_div_two] at h_trans exact h_trans.trans hdiv_lelemma halving_partition_length_le_list_sum_ge_length (l : List ℕ) (h : ∀ x ∈ l, 1 ≤ x) : l.length ≤ l.sum := by induction l with | nil => simp | cons a l ih => simp only [List.length_cons, List.sum_cons] have ha : 1 ≤ a := h a (List.mem_cons_self ..) have hl : l.length ≤ l.sum := ih (fun x hx => h x (List.mem_cons_of_mem a hx)) omegalemma halving_partition_length_le_sum_take_ge_sum_range (p : List ℕ) (f : ℕ → ℕ) (k : ℕ) (hk : k ≤ p.length) (h : ∀ (i : ℕ) (hi : i < p.length), i < k → f i ≤ p[i]) : ∑ i ∈ Finset.range k, f i ≤ (p.take k).sum := by induction k with | zero => simp | succ k ih => rw [Finset.sum_range_succ] have hk' : k < p.length := by omega have htake := (List.take_concat_get' p k hk').symm rw [htake, List.sum_append, List.sum_singleton] have ih_le : ∑ i ∈ Finset.range k, f i ≤ (p.take k).sum := by apply ih (by omega) intro i hi_p hi_k exact h i hi_p (by omega) have hlast : f k ≤ p[k] := h k hk' (by omega) omegalemma halving_partition_length_le_sum_div_pow_two_eq (n : ℕ) : ∑ i ∈ Finset.range (Nat.log 2 n), n / 2 ^ (i + 1) = n - (Nat.digits 2 n).sum := by have h := @Nat.sub_one_mul_sum_log_div_pow_eq_sub_sum_digits 2 n simp only [Nat.reduceSub, one_mul] at h rw [← h] rw [Finset.sum_range_succ] have hzero : n / 2 ^ (Nat.log 2 n).succ = 0 := by apply Nat.div_eq_of_lt exact Nat.lt_pow_succ_log_self (by decide) n rw [hzero, add_zero]/-- Upper bound on the length of any halving partition of n by floor(log_2 n) + s_2(n). -/theorem halving_partition_length_le (n : ℕ) (hn : 0 < n) (p : List ℕ) (hp : is_halving_partition n p) : p.length ≤ Nat.log 2 n + (Nat.digits 2 n).sum := by let h := Nat.log 2 n by_cases hlen : p.length ≤ h · omega have hh_le : h ≤ p.length := by omega have hp_sum : p.sum = n := hp.2.1 have hp_pos : ∀ x ∈ p, 1 ≤ x := fun x hx => hp.1 x hx have hsplit : p.sum = (p.take h).sum + (p.drop h).sum := by rw [← List.sum_append, List.take_append_drop] have htake_ge : ∑ i ∈ Finset.range h, n / 2 ^ (i + 1) ≤ (p.take h).sum := by apply halving_partition_length_le_sum_take_ge_sum_range p (fun i => n / 2 ^ (i + 1)) h hh_le intro i hi _ exact halving_partition_length_le_part_ge_div_pow_two n p hp i hi rw [halving_partition_length_le_sum_div_pow_two_eq n] at htake_ge have hdrop_ge : p.length - h ≤ (p.drop h).sum := by rw [← List.length_drop] apply halving_partition_length_le_list_sum_ge_length intro x hx exact hp_pos x (List.mem_of_mem_drop hx) have hdigits_le : (Nat.digits 2 n).sum ≤ n := Nat.digit_sum_le 2 n omega