AFTD Auto-Formalizing Theoretical Domains

nus_int_collision_preserving_const_of_minimal

theoremverified

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

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.

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

    lines 8–12

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

    lines 13–15

    uses finset_sum_collision_preserving_const_of_minimal

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

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