AFTD Auto-Formalizing Theoretical Domains

distinct_subset_sums_powers_of_two_upper_bound

theoremverifiedformalization

For all integers k ≥ 1 and n ≥ 1, there exists an admissible sequence a : Fin n → Fin k → ℕ whose maximum entry is at most 2^(Nat.ceil (n / k) - 1).

Statement

theorem distinct_subset_sums_powers_of_two_upper_bound (k n : ℕ) (hk : 1 ≤ k) (hn : 1 ≤ n) :
    ∃ (a : Fin n → Fin k → ℕ),
      distinct_subset_sums_admissible a ∧
      vector_seq_max_entry a ≤ 2 ^ (Nat.ceil ((n : ℝ) / (k : ℝ)) - 1)
Formalizes
arXiv:2610.26970 line 140
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • distinct_subset_sums_admissibleA sequence of vectors a : Fin n → Fin k → ℕ is admissible if any two subsets S, T ⊆ Fin n with the same subset sum ∑_{i ∈ S} a_i = ∑_{i ∈…
  • vector_seq_max_entryThe maximum entry max_{i, j} a_i(j) of a vector sequence a : Fin n → Fin k → ℕ, defined as the supremum of a i j over all pairs (i, j).

Read back from the Lean

For all natural numbers $k$ and $n$ with $1 \le k$ and $1 \le n$, there exists a sequence of $n$ vectors of dimension $k$ with natural number entries (a function $a : \text{Fin } n \to \text{Fin } k \to \mathbb{N}$) such that: 1. $a$ has distinct subset sums: for all subsets $S, T \subseteq \text{Fin } n$, if $\sum_{i \in S} a(i) = \sum_{i \in T} a(i)$ (with addition defined pointwise on $\text{Fin } k \to \mathbb{N}$), then $S = T$; and 2. The maximum entry among all components of all vectors $a(i)$ (the supremum of $a(i)(j)$ over all $(i, j) \in \text{Fin } n \times \text{Fin } k$) is at most $2^{\lceil n / k \rceil - 1}$ (where the ceiling is taken over the real quotient $n / k$).

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 constructs an explicit candidate sequence a : Fin n → Fin k → ℕ where the j-th component of a(i) is 2^(i / k) if i ≡ j (mod k) and 0 otherwise. To show admissibility, two subsets S, T with equal vector sums must have equal sums in each coordinate j, which corresponds to identical sums of distinct powers of two over the quotients {i / k | i ≡ j (mod k)}. By the uniqueness of binary representations, these quotient sets coincide, and since an index i is uniquely determined by its quotient and remainder modulo k, this forces S = T. Finally, the maximum entry is bounded by observing that any index satisfies i ≤ n - 1, so i / k ≤ (n - 1) / k ≤ ⌈n / k⌉ - 1, which bounds the entries 2^(i / k) by 2^(⌈n / k⌉ - 1).

  1. It suffices to show that the candidate sequence a(i)_j = 2^(i / k) (when i % k = j) and 0 otherwise is admissible and satisfies the maximum entry bound.

    We define the sequence a : Fin n → Fin k → ℕ by setting coordinate j of the i-th vector to 2^(i / k) when i % k = j and 0 otherwise. Providing a as the witness for the existential quantifier, the goal splits into two parts: showing that a is admissible (all subset sums are distinct) and showing that its maximum entry is at most 2^(⌈n / k⌉ - 1).

    lines 6–8

      let a : Fin n → Fin k → ℕ := fun i j => if i.1 % k = j.1 then 2 ^ (i.1 / k) else 0
      use a
      constructor
  2. To establish admissibility, assume ∑_{i ∈ S} a(i) = ∑_{i ∈ T} a(i); to prove S = T, it suffices to show that any element x belongs to S if and only if it belongs to T, and we define j = x % k as its coordinate index.

    We introduce two subsets S, T ⊆ Fin n and the hypothesis that their vector sums coincide. By extensionality, S = T reduces to showing x ∈ S ↔ x ∈ T for an arbitrary element x. We compute the remainder j = x % k, which satisfies j < k by Nat.mod_lt since k ≥ 1, making j a valid coordinate index in Fin k.

    lines 9–13

    uses Nat.mod_lt

      · intro S T hST
        ext x
        have hj_lt : x.1 % k < k := Nat.mod_lt x.1 (by omega)
        let j : Fin k := ⟨x.1 % k, hj_lt⟩
        have hj : x.1 % k = j.1 := rfl
  3. For any subset U ⊆ Fin n, the coordinate sum ∑_{i ∈ U} a(i)_j equals the sum of powers of two ∑_m 2^m over the image of {i ∈ U | i % k = j} under i ↦ i / k.

    Unfolding the definition of a, the terms in the sum ∑_{i ∈ U} a(i)_j are zero whenever i % k ≠ j, so by Finset.sum_filter the sum restricts to the filtered subset of indices with remainder j. On this subset, the quotient map i ↦ i / k is injective: if two indices p and q have the same quotient and remainder j, the division algorithm p = k * (p / k) + (p % k) (Nat.div_add_mod) proves p = q. Using Finset.sum_image, we can rewrite the sum of 2^(i / k) over this subset into a sum of distinct powers 2^m over the set of quotients.

    lines 14–29

    uses Finset.sum_filter, Finset.mem_coe, Finset.mem_filter, Nat.div_add_mod, Finset.sum_image

        have h_sum (U : Finset (Fin n)) :
            ∑ m ∈ (U.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k), 2 ^ m =
            (∑ i ∈ U, a i j) := by
          dsimp [a]
          rw [← Finset.sum_filter]
          have hinj : Set.InjOn (fun (i : Fin n) => i.1 / k) ↑(U.filter (fun i => i.1 % k = j.1)) := by
            intro p hp q hq (hpq : p.1 / k = q.1 / k)
            simp only [Finset.mem_coe, Finset.mem_filter] at hp hq
            have hp_mod : p.1 % k = j.1 := hp.2
            have hq_mod : q.1 % k = j.1 := hq.2
            ext
            calc p.1
              _ = k * (p.1 / k) + p.1 % k := (Nat.div_add_mod p.1 k).symm
              _ = k * (q.1 / k) + q.1 % k := by rw [hpq, hp_mod, hq_mod]
              _ = q.1 := Nat.div_add_mod q.1 k
          exact Finset.sum_image hinj
  4. The set of quotients {i / k | i ∈ S, i % k = j} equals the set of quotients {i / k | i ∈ T, i % k = j}.

    Evaluating the vector equality ∑_{i ∈ S} a(i) = ∑_{i ∈ T} a(i) at coordinate j via congr_fun and Finset.sum_apply shows that the j-th coordinate sums for S and T are equal. Applying the previous identity to both sides equates two sums of distinct powers of two. Because base-2 representations are unique (Finset.geomSum_injective), the two underlying finite sets of exponents must be identical.

    lines 30–38

    uses congr_fun, Finset.sum_apply, Finset.geomSum_injective

        have hST_j : (∑ i ∈ S, a i j) = (∑ i ∈ T, a i j) := by
          have h := congr_fun hST j
          rw [Finset.sum_apply, Finset.sum_apply] at h
          exact h
        have h_img_sum :
            ∑ m ∈ (S.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k), 2 ^ m =
            ∑ m ∈ (T.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k), 2 ^ m := by
          rw [h_sum S, h_sum T, hST_j]
        have h_img_eq := Finset.geomSum_injective (by decide) h_img_sum
  5. If x ∈ S, then x ∈ T.

    Suppose x ∈ S. Since x % k = j, x belongs to the filtered subset {i ∈ S | i % k = j} by Finset.mem_filter, so its quotient x / k belongs to the image set of exponents (Finset.mem_image_of_mem). Because the exponent sets for S and T are equal, x / k is in the exponent set for T. By Finset.mem_image.mp, there exists y ∈ T with y % k = j and y / k = x / k. Reconstructing the numbers from their quotients and remainders via Nat.div_add_mod yields x = y, hence x ∈ T.

    lines 39–57

    uses Finset.mem_filter, Finset.mem_image_of_mem, Finset.mem_image.mp, Nat.div_add_mod

        constructor
        · intro hxS
          have hx_filt : x ∈ S.filter (fun i => i.1 % k = j.1) := by
            rw [Finset.mem_filter]
            exact ⟨hxS, hj⟩
          have hx_img : x.1 / k ∈ (S.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k) :=
            Finset.mem_image_of_mem _ hx_filt
          rw [h_img_eq] at hx_img
          rcases Finset.mem_image.mp hx_img with ⟨y, hy, hy_div⟩
          rw [Finset.mem_filter] at hy
          have hy_mod : y.1 % k = j.1 := hy.2
          have hxy : x = y := by
            ext
            calc x.1
              _ = k * (x.1 / k) + x.1 % k := (Nat.div_add_mod x.1 k).symm
              _ = k * (y.1 / k) + y.1 % k := by rw [← hy_div, hj, hy_mod]
              _ = y.1 := Nat.div_add_mod y.1 k
          rw [hxy]
          exact hy.1
  6. If x ∈ T, then x ∈ S, completing the proof that a is admissible.

    By the exact same argument in reverse, if x ∈ T then x / k belongs to the exponent set for T, which equals that for S. There exists y ∈ S with the same quotient and remainder j, so x = y ∈ S. Together with the forward implication, this proves S = T, establishing admissibility.

    lines 58–75

    uses Finset.mem_filter, Finset.mem_image_of_mem, Finset.mem_image.mp, Nat.div_add_mod

        · intro hxT
          have hx_filt : x ∈ T.filter (fun i => i.1 % k = j.1) := by
            rw [Finset.mem_filter]
            exact ⟨hxT, hj⟩
          have hx_img : x.1 / k ∈ (T.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k) :=
            Finset.mem_image_of_mem _ hx_filt
          rw [← h_img_eq] at hx_img
          rcases Finset.mem_image.mp hx_img with ⟨y, hy, hy_div⟩
          rw [Finset.mem_filter] at hy
          have hy_mod : y.1 % k = j.1 := hy.2
          have hxy : x = y := by
            ext
            calc x.1
              _ = k * (x.1 / k) + x.1 % k := (Nat.div_add_mod x.1 k).symm
              _ = k * (y.1 / k) + y.1 % k := by rw [← hy_div, hj, hy_mod]
              _ = y.1 := Nat.div_add_mod y.1 k
          rw [hxy]
          exact hy.1
  7. The inequality (n - 1) / k ≤ ⌈n / k⌉ - 1 holds.

    By Nat.div_mul_le_self, ((n - 1) / k) * k ≤ n - 1. Since n ≥ 1, we have n - 1 < n (Nat.sub_lt), so ((n - 1) / k) * k < n by lt_of_le_of_lt. Dividing by k > 0 (Nat.cast_pos.mpr) over the reals via lt_div_iff₀ and Nat.cast_lt.mpr shows that ((n - 1) / k : ℝ) < n / k. Hence by Nat.lt_ceil.mpr, (n - 1) / k < ⌈n / k⌉, which for integers implies (n - 1) / k ≤ ⌈n / k⌉ - 1 (Nat.le_sub_one_of_lt).

    lines 76–87

    uses Nat.cast_pos.mpr, Nat.div_mul_le_self, Nat.sub_lt, lt_of_le_of_lt, lt_div_iff₀, Nat.cast_lt.mpr, Nat.lt_ceil.mpr, Nat.le_sub_one_of_lt

      · have h_bound : (n - 1) / k ≤ Nat.ceil ((n : ℝ) / (k : ℝ)) - 1 := by
          have hk0 : 0 < (k : ℝ) := Nat.cast_pos.mpr hk
          have hmul : (n - 1) / k * k ≤ n - 1 := Nat.div_mul_le_self (n - 1) k
          have hlt : n - 1 < n := Nat.sub_lt hn (by decide)
          have hlt2 : (n - 1) / k * k < n := lt_of_le_of_lt hmul hlt
          have h_lt : (((n - 1) / k : ℕ) : ℝ) < (n : ℝ) / (k : ℝ) := by
            rw [lt_div_iff₀ hk0]
            calc (((n - 1) / k : ℕ) : ℝ) * (k : ℝ)
              _ = (((n - 1) / k * k : ℕ) : ℝ) := by push_cast; rfl
              _ < (n : ℝ) := Nat.cast_lt.mpr hlt2
          have hceil : (n - 1) / k < Nat.ceil ((n : ℝ) / (k : ℝ)) := Nat.lt_ceil.mpr h_lt
          exact Nat.le_sub_one_of_lt hceil
  8. The maximum entry of the sequence a is at most 2^(⌈n / k⌉ - 1).

    Unfolding vector_seq_max_entry, Finset.sup_le_iff reduces the bound to checking that every entry a(i)_j ≤ 2^(⌈n / k⌉ - 1). If i % k ≠ j, the entry is 0, which is at most the bound by Nat.zero_le. If i % k = j, the entry is 2^(i / k). Since i < n, we have i ≤ n - 1 (Nat.le_pred_of_lt), so i / k ≤ (n - 1) / k (Nat.div_le_div_right). Chaining this with the bound from the previous step via le_trans gives i / k ≤ ⌈n / k⌉ - 1, and monotonicity of powers of two (Nat.pow_le_pow_right) yields 2^(i / k) ≤ 2^(⌈n / k⌉ - 1).

    lines 88–97

    uses Finset.sup_le_iff, Nat.le_pred_of_lt, Nat.div_le_div_right, le_trans, Nat.pow_le_pow_right, Nat.zero_le

        unfold vector_seq_max_entry
        rw [Finset.sup_le_iff]
        rintro ⟨i, j⟩ -
        dsimp [a]
        split_ifs with h
        · have hi : i.1 ≤ n - 1 := Nat.le_pred_of_lt i.isLt
          have hdiv : i.1 / k ≤ (n - 1) / k := Nat.div_le_div_right hi
          have hle : i.1 / k ≤ Nat.ceil ((n : ℝ) / (k : ℝ)) - 1 := le_trans hdiv h_bound
          exact Nat.pow_le_pow_right (by decide) hle
        · exact Nat.zero_le _
Nat.mod_lt
For any natural numbers x and y > 0, the remainder x % y is strictly less than y.
Finset.sum_filter
Summing a function over elements of a finite set satisfying a predicate equals summing the if-then-else function over the entire set.
Finset.mem_coe
An element belongs to a finite set coerced to a set if and only if it belongs to the finite set.
Finset.mem_filter
An element belongs to a filtered subset if and only if it belongs to the original set and satisfies the predicate.
Nat.div_add_mod
The division algorithm for natural numbers: n * (m / n) + m % n = m.
Finset.sum_image
If a function is injective on a finite set, the sum of values over the image equals the sum of the composite function over the domain set.
congr_fun
Equal functions take equal values at any argument.
Finset.sum_apply
Evaluating a sum of functions at a point equals the sum of their individual values at that point.
Finset.geomSum_injective
For any base b ≥ 2, a sum of distinct powers ∑_{i ∈ s} b^i uniquely determines the finite set of exponents s.
Finset.mem_image_of_mem
If an element belongs to a finite set, its image under a function belongs to the image set.
Finset.mem_image.mp
If an element belongs to the image of a finite set under a function, it is the image of some element in that set.
Nat.cast_pos.mpr
If a natural number is strictly positive, its embedding into the real numbers is strictly positive.
Nat.div_mul_le_self
For any natural numbers m and n, integer division satisfies (m / n) * n ≤ m.
Nat.sub_lt
Subtracting a strictly positive natural number from another strictly positive natural number yields a strictly smaller result.
lt_of_le_of_lt
Transitivity of strict inequality with non-strict inequality: if a ≤ b and b < c, then a < c.
lt_div_iff₀
For a positive number c in a linearly ordered field, a < b / c holds if and only if a * c < b.
Nat.cast_lt.mpr
If a < b for natural numbers, then their real embeddings satisfy a < b.
Nat.lt_ceil.mpr
If the real embedding of a natural number m is strictly less than a real number x, then m < ⌈x⌉.
Nat.le_sub_one_of_lt
If a < b for natural numbers, then a ≤ b - 1.
Finset.sup_le_iff
The supremum of a function over a finite set is at most a bound if and only if every value is at most that bound.
Nat.le_pred_of_lt
If n < m for natural numbers, then n ≤ m - 1.
Nat.div_le_div_right
Integer division of natural numbers preserves the non-strict inequality ordering: if a ≤ b, then a / c ≤ b / c.
le_trans
Transitivity of preorder: if a ≤ b and b ≤ c, then a ≤ c.
Nat.pow_le_pow_right
For a base n > 0, the power function is monotonic in the exponent: if i ≤ j, then n^i ≤ n^j.
Nat.zero_le
Every natural number is at least zero.

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

/-- Powers-of-two upper bound: there exists an admissible sequence with maximum entry at most 2^(ceil(n/k) - 1). -/theorem distinct_subset_sums_powers_of_two_upper_bound (k n : ℕ) (hk : 1 ≤ k) (hn : 1 ≤ n) :    ∃ (a : Fin n → Fin k → ℕ),      distinct_subset_sums_admissible a ∧      vector_seq_max_entry a ≤ 2 ^ (Nat.ceil ((n : ℝ) / (k : ℝ)) - 1) := by  let a : Fin n → Fin k → ℕ := fun i j => if i.1 % k = j.1 then 2 ^ (i.1 / k) else 0  use a  constructor  · intro S T hST    ext x    have hj_lt : x.1 % k < k := Nat.mod_lt x.1 (by omega)    let j : Fin k := ⟨x.1 % k, hj_lt⟩    have hj : x.1 % k = j.1 := rfl    have h_sum (U : Finset (Fin n)) :        ∑ m ∈ (U.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k), 2 ^ m =        (∑ i ∈ U, a i j) := by      dsimp [a]      rw [← Finset.sum_filter]      have hinj : Set.InjOn (fun (i : Fin n) => i.1 / k) ↑(U.filter (fun i => i.1 % k = j.1)) := by        intro p hp q hq (hpq : p.1 / k = q.1 / k)        simp only [Finset.mem_coe, Finset.mem_filter] at hp hq        have hp_mod : p.1 % k = j.1 := hp.2        have hq_mod : q.1 % k = j.1 := hq.2        ext        calc p.1          _ = k * (p.1 / k) + p.1 % k := (Nat.div_add_mod p.1 k).symm          _ = k * (q.1 / k) + q.1 % k := by rw [hpq, hp_mod, hq_mod]          _ = q.1 := Nat.div_add_mod q.1 k      exact Finset.sum_image hinj    have hST_j : (∑ i ∈ S, a i j) = (∑ i ∈ T, a i j) := by      have h := congr_fun hST j      rw [Finset.sum_apply, Finset.sum_apply] at h      exact h    have h_img_sum :        ∑ m ∈ (S.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k), 2 ^ m =        ∑ m ∈ (T.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k), 2 ^ m := by      rw [h_sum S, h_sum T, hST_j]    have h_img_eq := Finset.geomSum_injective (by decide) h_img_sum    constructor    · intro hxS      have hx_filt : x ∈ S.filter (fun i => i.1 % k = j.1) := by        rw [Finset.mem_filter]        exact ⟨hxS, hj⟩      have hx_img : x.1 / k ∈ (S.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k) :=        Finset.mem_image_of_mem _ hx_filt      rw [h_img_eq] at hx_img      rcases Finset.mem_image.mp hx_img with ⟨y, hy, hy_div⟩      rw [Finset.mem_filter] at hy      have hy_mod : y.1 % k = j.1 := hy.2      have hxy : x = y := by        ext        calc x.1          _ = k * (x.1 / k) + x.1 % k := (Nat.div_add_mod x.1 k).symm          _ = k * (y.1 / k) + y.1 % k := by rw [← hy_div, hj, hy_mod]          _ = y.1 := Nat.div_add_mod y.1 k      rw [hxy]      exact hy.1    · intro hxT      have hx_filt : x ∈ T.filter (fun i => i.1 % k = j.1) := by        rw [Finset.mem_filter]        exact ⟨hxT, hj⟩      have hx_img : x.1 / k ∈ (T.filter (fun i => i.1 % k = j.1)).image (fun i => i.1 / k) :=        Finset.mem_image_of_mem _ hx_filt      rw [← h_img_eq] at hx_img      rcases Finset.mem_image.mp hx_img with ⟨y, hy, hy_div⟩      rw [Finset.mem_filter] at hy      have hy_mod : y.1 % k = j.1 := hy.2      have hxy : x = y := by        ext        calc x.1          _ = k * (x.1 / k) + x.1 % k := (Nat.div_add_mod x.1 k).symm          _ = k * (y.1 / k) + y.1 % k := by rw [← hy_div, hj, hy_mod]          _ = y.1 := Nat.div_add_mod y.1 k      rw [hxy]      exact hy.1  · have h_bound : (n - 1) / k ≤ Nat.ceil ((n : ℝ) / (k : ℝ)) - 1 := by      have hk0 : 0 < (k : ℝ) := Nat.cast_pos.mpr hk      have hmul : (n - 1) / k * k ≤ n - 1 := Nat.div_mul_le_self (n - 1) k      have hlt : n - 1 < n := Nat.sub_lt hn (by decide)      have hlt2 : (n - 1) / k * k < n := lt_of_le_of_lt hmul hlt      have h_lt : (((n - 1) / k : ℕ) : ℝ) < (n : ℝ) / (k : ℝ) := by        rw [lt_div_iff₀ hk0]        calc (((n - 1) / k : ℕ) : ℝ) * (k : ℝ)          _ = (((n - 1) / k * k : ℕ) : ℝ) := by push_cast; rfl          _ < (n : ℝ) := Nat.cast_lt.mpr hlt2      have hceil : (n - 1) / k < Nat.ceil ((n : ℝ) / (k : ℝ)) := Nat.lt_ceil.mpr h_lt      exact Nat.le_sub_one_of_lt hceil    unfold vector_seq_max_entry    rw [Finset.sup_le_iff]    rintro ⟨i, j⟩ -    dsimp [a]    split_ifs with h    · have hi : i.1 ≤ n - 1 := Nat.le_pred_of_lt i.isLt      have hdiv : i.1 / k ≤ (n - 1) / k := Nat.div_le_div_right hi      have hle : i.1 / k ≤ Nat.ceil ((n : ℝ) / (k : ℝ)) - 1 := le_trans hdiv h_bound      exact Nat.pow_le_pow_right (by decide) hle    · exact Nat.zero_le _
See it in the graphDiscuss this resultChallenge it