AFTD Auto-Formalizing Theoretical Domains

efx_anchor_family_perturbed_nondegenerate

theoremverified

If each exponent row is injective and bounded by the number of goods, every agent assigns distinct values to distinct subsets after the binary perturbation.

Statement

theorem efx_anchor_family_perturbed_nondegenerate (r s : ℕ)
  (p : Fin 4 → Fin ((7+(r+r+r))+s) → ℕ)
  (hinj : ∀ i, Function.Injective (p i))
  (hbound : ∀ i g, p i g < (7+(r+r+r))+s)
  (i : Fin 4) (S T : Finset (Fin ((7+(r+r+r))+s)))
  (h : (∑ g ∈ S, efx_anchor_family_perturbed_values r s p i g) =
       (∑ g ∈ T, efx_anchor_family_perturbed_values r s p i g)) : S = T
Source
Nondegenerate arbitrary-size OP-7 Pareto obstruction, binary perturbation and experiment 11514.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • efx_anchor_family_perturbed_valuesMultiply all anchor-family valuations by 2 to the number of goods and add the agent-specific binary perturbation.
  • efx_anchor_family_valuesKeep the first seven original goods with values scaled by s−1 for the first three agents and value 1 for the fourth. Append 3r common…

The proof, explained

The perturbed valuation of a bundle of goods U decomposes into a large multiple of 2^M (where M is the total number of goods) plus a binary perturbation term ∑_{g ∈ U} 2^{p(i,g)}. Because each agent's perturbation exponents are bounded strictly below M, the binary perturbation sum is strictly less than 2^M. Reducing the equality of perturbed valuations modulo 2^M isolates the binary sums, proving that the binary perturbations of S and T are equal. Finally, uniqueness of binary expansions (Finset.geomSum_injective) together with injectivity of the exponent map p(i, ·) forces the bundles S and T to be identical.

  1. For any bundle of goods U, the perturbed valuation sum decomposes as 2^M * (∑ g ∈ U, v_i(g)) + ∑ g ∈ U, 2^(p i g), where M = 7 + 3r + s.

    By definition of efx_anchor_family_perturbed_values, the value of each good g is 2^M * v_i(g) + 2^(p i g). Distributing the sum over addition using Finset.sum_add_distrib and factoring out 2^M with Finset.mul_sum separates the total valuation into a multiple of 2^M and the binary perturbation term.

    lines 8–16

    uses Finset.sum_add_distrib, Finset.mul_sum

      classical
      -- Decompose each perturbed sum into a large multiple of 2^M plus the binary perturbation.
      have hsum : ∀ U : Finset (Fin ((7+(r+r+r))+s)),
          (∑ g ∈ U, efx_anchor_family_perturbed_values r s p i g)
            = 2^(7+(r+r+r)+s) * (∑ g ∈ U, efx_anchor_family_values r s i g)
              + ∑ g ∈ U, 2 ^ (p i g) := by
        intro U
        simp only [efx_anchor_family_perturbed_values]
        rw [Finset.sum_add_distrib, Finset.mul_sum]
  2. For any bundle U, the binary perturbation sum ∑ g ∈ U, 2^(p i g) is strictly less than 2^M.

    Because p i is injective, the sum of 2^(p i g) over U can be reindexed via Finset.sum_image as a sum of distinct powers 2^e over the image set (p i)(U). By hypothesis hbound, each exponent e in this image is strictly less than M = 7 + 3r + s. By Nat.geomSum_lt, the sum of any subset of powers 2^e with e < M is strictly less than 2^M.

    lines 18–28

    uses Finset.sum_image, Nat.geomSum_lt, Finset.mem_image

      have hbnd : ∀ U : Finset (Fin ((7+(r+r+r))+s)),
          (∑ g ∈ U, 2 ^ (p i g)) < 2^(7+(r+r+r)+s) := by
        intro U
        have himg : (∑ g ∈ U, 2 ^ (p i g)) = ∑ e ∈ U.image (fun g => p i g), 2^e :=
          (Finset.sum_image (f := fun e => (2:ℕ)^e) (g := fun g => p i g)
            (fun x _ y _ hxy => hinj i hxy)).symm
        rw [himg]
        exact Nat.geomSum_lt (m := 2) (n := 7+(r+r+r)+s) (by norm_num) (fun k hk => by
          simp only [Finset.mem_image] at hk
          obtain ⟨g, _, rfl⟩ := hk
          exact hbound i g)
  3. The binary perturbation sums for bundles S and T are equal: ∑ g ∈ S, 2^(p i g) = ∑ g ∈ T, 2^(p i g).

    Decomposing the assumed equality of perturbed bundle values yields 2^M * A + B_S = 2^M * B + B_T, where B_S and B_T are the binary perturbation sums. Applying modulo 2^M to both sides via congrArg cancels the multiples of 2^M by Nat.mul_add_mod. Since B_S < 2^M and B_T < 2^M, both remainders simplify directly to B_S and B_T by Nat.mod_eq_of_lt, giving B_S = B_T.

    lines 30–40

    uses congrArg, Nat.mul_add_mod, Nat.mod_eq_of_lt

      have hBT : (∑ g ∈ S, 2 ^ (p i g)) = (∑ g ∈ T, 2 ^ (p i g)) := by
        have hmain : 2^(7+(r+r+r)+s) * (∑ g ∈ S, efx_anchor_family_values r s i g)
              + (∑ g ∈ S, 2 ^ (p i g))
            = 2^(7+(r+r+r)+s) * (∑ g ∈ T, efx_anchor_family_values r s i g)
              + (∑ g ∈ T, 2 ^ (p i g)) := by
          rw [← hsum S, ← hsum T]
          exact h
        have hmod := congrArg (fun x => x % 2^(7+(r+r+r)+s)) hmain
        rw [Nat.mul_add_mod, Nat.mul_add_mod, Nat.mod_eq_of_lt (hbnd S),
          Nat.mod_eq_of_lt (hbnd T)] at hmod
        exact hmod
  4. The sum of powers of 2 over the image set (p i)(S) equals the sum of powers of 2 over (p i)(T).

    Reindexing the binary perturbation sums over S and T to their images under p i via Finset.sum_image, and substituting into the equality B_S = B_T established in the previous step, shows that ∑ e ∈ (p i)(S), 2^e = ∑ e ∈ (p i)(T), 2^e.

    lines 41–51

    uses Finset.sum_image

      have himgS : (∑ g ∈ S, 2 ^ (p i g)) = ∑ e ∈ S.image (fun g => p i g), 2^e :=
        (Finset.sum_image (f := fun e => (2:ℕ)^e) (g := fun g => p i g)
          (fun x _ y _ hxy => hinj i hxy)).symm
      have himgT : (∑ g ∈ T, 2 ^ (p i g)) = ∑ e ∈ T.image (fun g => p i g), 2^e :=
        (Finset.sum_image (f := fun e => (2:ℕ)^e) (g := fun g => p i g)
          (fun x _ y _ hxy => hinj i hxy)).symm
      -- Distinct powers of two with distinct exponents have distinct sums.
      have hsumimg : (∑ e ∈ S.image (fun g => p i g), 2^e)
          = (∑ e ∈ T.image (fun g => p i g), 2^e) := by
        rw [← himgS, ← himgT]
        exact hBT
  5. S = T.

    By Finset.geomSum_injective, base-2 representations with distinct exponents are unique, so the equality of the sums of powers of 2 implies (p i)(S) = (p i)(T). Because p i is injective, Finset.image_injective guarantees that the image operation on finite sets is injective, concluding that S = T.

    lines 52–53

    uses Finset.image_injective, Finset.geomSum_injective

      exact Finset.image_injective (hinj i)
        (Finset.geomSum_injective (n := 2) (by norm_num) hsumimg)
Finset.mul_sum
Multiplication by a constant distributes over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_add_distrib
The sum of a sum over a finite set equals the sum of the individual terms: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.sum_image
If a function g is injective on a finite set s, then summing f over the image g(s) equals summing f ∘ g over s.
Nat.geomSum_lt
For any base m ≥ 2, the sum of distinct powers m^k for exponents k < n is strictly less than m^n.
Finset.mem_image
An element b is in the image of s under f if and only if b = f a for some a ∈ s.
congrArg
Applying a function to both sides of an equality yields an equality: if a₁ = a₂, then f a₁ = f a₂.
Nat.mul_add_mod
For natural numbers, (m * x + y) % m = y % m.
Nat.mod_eq_of_lt
A natural number strictly smaller than the modulus equals its remainder: if a < b, then a % b = a.
Finset.image_injective
An injective function f induces an injective map on finite sets under taking images.
Finset.geomSum_injective
For any base n ≥ 2, the function mapping a finite set of exponents s to ∑ i ∈ s, n^i is injective (uniqueness of base-n expansions).

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

theorem efx_anchor_family_perturbed_nondegenerate (r s : ℕ)  (p : Fin 4 → Fin ((7+(r+r+r))+s) → ℕ)  (hinj : ∀ i, Function.Injective (p i))  (hbound : ∀ i g, p i g < (7+(r+r+r))+s)  (i : Fin 4) (S T : Finset (Fin ((7+(r+r+r))+s)))  (h : (∑ g ∈ S, efx_anchor_family_perturbed_values r s p i g) =       (∑ g ∈ T, efx_anchor_family_perturbed_values r s p i g)) : S = T := by  classical  -- Decompose each perturbed sum into a large multiple of 2^M plus the binary perturbation.  have hsum : ∀ U : Finset (Fin ((7+(r+r+r))+s)),      (∑ g ∈ U, efx_anchor_family_perturbed_values r s p i g)        = 2^(7+(r+r+r)+s) * (∑ g ∈ U, efx_anchor_family_values r s i g)          + ∑ g ∈ U, 2 ^ (p i g) := by    intro U    simp only [efx_anchor_family_perturbed_values]    rw [Finset.sum_add_distrib, Finset.mul_sum]  -- The binary perturbation of any set of goods is strictly smaller than 2^M.  have hbnd : ∀ U : Finset (Fin ((7+(r+r+r))+s)),      (∑ g ∈ U, 2 ^ (p i g)) < 2^(7+(r+r+r)+s) := by    intro U    have himg : (∑ g ∈ U, 2 ^ (p i g)) = ∑ e ∈ U.image (fun g => p i g), 2^e :=      (Finset.sum_image (f := fun e => (2:ℕ)^e) (g := fun g => p i g)        (fun x _ y _ hxy => hinj i hxy)).symm    rw [himg]    exact Nat.geomSum_lt (m := 2) (n := 7+(r+r+r)+s) (by norm_num) (fun k hk => by      simp only [Finset.mem_image] at hk      obtain ⟨g, _, rfl⟩ := hk      exact hbound i g)  -- Reduce the equality modulo 2^M to get equality of the binary parts.  have hBT : (∑ g ∈ S, 2 ^ (p i g)) = (∑ g ∈ T, 2 ^ (p i g)) := by    have hmain : 2^(7+(r+r+r)+s) * (∑ g ∈ S, efx_anchor_family_values r s i g)          + (∑ g ∈ S, 2 ^ (p i g))        = 2^(7+(r+r+r)+s) * (∑ g ∈ T, efx_anchor_family_values r s i g)          + (∑ g ∈ T, 2 ^ (p i g)) := by      rw [← hsum S, ← hsum T]      exact h    have hmod := congrArg (fun x => x % 2^(7+(r+r+r)+s)) hmain    rw [Nat.mul_add_mod, Nat.mul_add_mod, Nat.mod_eq_of_lt (hbnd S),      Nat.mod_eq_of_lt (hbnd T)] at hmod    exact hmod  have himgS : (∑ g ∈ S, 2 ^ (p i g)) = ∑ e ∈ S.image (fun g => p i g), 2^e :=    (Finset.sum_image (f := fun e => (2:ℕ)^e) (g := fun g => p i g)      (fun x _ y _ hxy => hinj i hxy)).symm  have himgT : (∑ g ∈ T, 2 ^ (p i g)) = ∑ e ∈ T.image (fun g => p i g), 2^e :=    (Finset.sum_image (f := fun e => (2:ℕ)^e) (g := fun g => p i g)      (fun x _ y _ hxy => hinj i hxy)).symm  -- Distinct powers of two with distinct exponents have distinct sums.  have hsumimg : (∑ e ∈ S.image (fun g => p i g), 2^e)      = (∑ e ∈ T.image (fun g => p i g), 2^e) := by    rw [← himgS, ← himgT]    exact hBT  exact Finset.image_injective (hinj i)    (Finset.geomSum_injective (n := 2) (by norm_num) hsumimg)
See it in the graphDiscuss this resultChallenge it