distinct_subset_sums_powers_of_two_upper_bound
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).
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).
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
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.
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
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.
uses
Finset.sum_filter,Finset.mem_coe,Finset.mem_filter,Nat.div_add_mod,Finset.sum_imagehave 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
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.
uses
congr_fun,Finset.sum_apply,Finset.geomSum_injectivehave 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
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.
uses
Finset.mem_filter,Finset.mem_image_of_mem,Finset.mem_image.mp,Nat.div_add_modconstructor · 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
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.
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
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).
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
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).
uses
Finset.sup_le_iff,Nat.le_pred_of_lt,Nat.div_le_div_right,le_trans,Nat.pow_le_pow_right,Nat.zero_leunfold 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
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.
/-- 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 _