AFTD Auto-Formalizing Theoretical Domains

halving_partition_length_le

theoremverifiedformalization

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).

  1. 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.

    lines 1–13

    uses List.length_singleton, List.getElem_cons_succ

    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 ih
  2. 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).

    lines 15–17

    uses Nat.div_div_eq_div_mul, pow_succ

    lemma 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]
  3. 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.

    lines 19–33

    uses zero_add, pow_one, le_rfl, Nat.div_le_div_right, Nat.le_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)
  4. 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].

    lines 34–46

    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_le
  5. For 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).

    lines 48–56

    uses List.length_cons, List.sum_cons, List.mem_cons_self, List.mem_cons_of_mem

    lemma 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
  6. 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.

    lines 58–73

    uses Finset.sum_range_succ, List.take_concat_get', List.sum_append, List.sum_singleton

    lemma 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
  7. 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⌋.

    lines 75–84

    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_zero

    lemma 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]
  8. 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|.

    lines 87–93

    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
  9. 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).

    lines 94–102

    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_eq

      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
  10. 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.

    lines 103–107

    uses List.length_drop, halving_partition_length_le_list_sum_ge_length, List.mem_of_mem_drop

      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)
  11. 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).

    lines 108–109

    uses Nat.digit_sum_le

      have 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.

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

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
See it in the graphDiscuss this resultChallenge it