nus_int_collision_preserving_const_of_minimal
If A is NUS, no proper subset of A is NUS, and x : G → ℤ is constant across additive collisions on A, then x is constant on A.
Statement
theorem nus_int_collision_preserving_const_of_minimal {G : Type*} [AddCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) (hmin : ∀ B : Finset G, B ⊂ A → ¬ finset_has_no_unique_sums B) {x : G → ℤ} (hx : ∀ a ∈ A, ∀ b ∈ A, ∀ c ∈ A, ∀ d ∈ A, a + b = c + d → x a + x b = x c + x d) : ∀ a ∈ A, ∀ b ∈ A, x a = x b
- Source
- step towards nus_min_card_ge_near_quadratic
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- finset_sum_collision_preserving_const_of_minimalIf A is NUS, no proper subset of A is NUS (A is inclusion-minimal), and x is a rational collision-preserving weight on A, then x is…
- finset_has_no_unique_sumsA has no unique sums (is NUS): |A| ≥ 2 and every sum a + b with a, b ∈ A has at least two representations as an unordered pair from A.
- finset_sum_collision_preservingA rational-valued function x on A is collision-preserving if it satisfies every additive collision: x a + x b = x c + x d whenever a + b =…
The proof, explained
To prove that an integer-valued collision-preserving weight x on an inclusion-minimal NUS set A is constant, the proof reduces to the rational case. It first embeds x into ℚ and verifies that the collision-preserving property continues to hold. Applying the previously established rational theorem finset_sum_collision_preserving_const_of_minimal yields that the rational cast of x is constant on A, from which the injectivity of the integer-to-rational cast concludes that x itself is constant.
The rational-valued function a ↦ (x a : ℚ) is collision-preserving on A.
Let a, b, c, d ∈ A with a + b = c + d. By the hypothesis hx, the integer sum equality x a + x b = x c + x d holds. Casting this equality to ℚ establishes that the rational embedding of x preserves sum collisions on A.
have hxQ : finset_sum_collision_preserving A (fun a => (x a : ℚ)) := by intro a ha b hb c hc d hd habcd dsimp norm_cast exact hx a ha b hb c hc d hd habcd
For all a, b ∈ A, x a = x b.
Given any two elements a, b ∈ A, applying finset_sum_collision_preserving_const_of_minimal to the rational-valued weight function shows that (x a : ℚ) = (x b : ℚ). Injectivity of the cast from ℤ to ℚ then immediately yields x a = x b.
uses
finset_sum_collision_preserving_const_of_minimalintro a ha b hb have h := finset_sum_collision_preserving_const_of_minimal hA hmin hxQ a ha b hb exact_mod_cast h
finset_sum_collision_preserving_const_of_minimal- If a finite set A has no unique sums, is inclusion-minimal with respect to this property, and a rational-valued weight function preserves sum collisions on A, then that weight function is constant on A.
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.
/-- Integer form of the rational rank statement: on an inclusion-minimal NUS set every integer-valued collision-preserving weight is constant. -/theorem nus_int_collision_preserving_const_of_minimal {G : Type*} [AddCommMonoid G] [DecidableEq G] {A : Finset G} (hA : finset_has_no_unique_sums A) (hmin : ∀ B : Finset G, B ⊂ A → ¬ finset_has_no_unique_sums B) {x : G → ℤ} (hx : ∀ a ∈ A, ∀ b ∈ A, ∀ c ∈ A, ∀ d ∈ A, a + b = c + d → x a + x b = x c + x d) : ∀ a ∈ A, ∀ b ∈ A, x a = x b := by have hxQ : finset_sum_collision_preserving A (fun a => (x a : ℚ)) := by intro a ha b hb c hc d hd habcd dsimp norm_cast exact hx a ha b hb c hc d hd habcd intro a ha b hb have h := finset_sum_collision_preserving_const_of_minimal hA hmin hxQ a ha b hb exact_mod_cast h