AFTD Auto-Formalizing Theoretical Domains

efx_allsource_three_pair_perturbed_nondegenerate

theoremverified

Each agent gives distinct values to distinct subsets of goods.

Statement

theorem efx_allsource_three_pair_perturbed_nondegenerate (i : Fin 4) (S T : Finset (Fin 9))
  (h : (∑ g ∈ S, efx_allsource_three_pair_perturbed_values i g) = ∑ g ∈ T, efx_allsource_three_pair_perturbed_values i g) : S = T
Source
Binary perturbation of the four-agent three-split barrier; experiment 11706 and the integer-gap projection.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The theorem establishes non-degeneracy: for each agent, distinct subsets of goods have distinct total valuations. The valuations are constructed so that modulo 512, each good's value is 2 raised to an assigned exponent from {0, ..., 8}, with each good receiving a distinct exponent. If two subsets S and T have the same valuation, their sums of powers of 2 are congruent modulo 512, and since the sum over all goods is only 511 < 512, these binary sums must be strictly equal. By the uniqueness of binary representation, the image sets of exponents must be identical, and injectivity of the exponent assignment concludes that S = T.

  1. For each agent i, the exponent function is injective. automation

    Assume two goods a and b have the same assigned exponent under agent i. Exhaustive case analysis over all 4 agents and all pairs of goods evaluates the defined matrix of exponents and confirms that a must equal b in every case.

    lines 9–10

      intro a b h
      fin_cases i <;> fin_cases a <;> fin_cases b <;> revert h <;> decide
  2. Each agent's valuation of a good is congruent to 2 raised to its exponent modulo 512. automation

    Exhaustive case analysis over all 4 agents and all 9 goods directly evaluates and verifies the modular congruence from the definitions.

    line 14

      fin_cases i <;> fin_cases g <;> decide
  3. For each agent i and subset of goods S, the sum of 2^(e(i, g)) over S is strictly less than 512. automation

    Since powers of two are non-negative, the sum over any subset S is bounded above by the sum over all nine goods. Exhaustive evaluation across all four agents confirms that this total sum is 511, which is strictly less than 512.

    lines 18–23

    uses Finset.sum_le_univ_sum_of_nonneg, Nat.zero_le

      calc
        ∑ g ∈ S, 2 ^ efx_allsource_three_pair_perturbed_nondegenerate_exp i g
          ≤ ∑ g : Fin 9, 2 ^ efx_allsource_three_pair_perturbed_nondegenerate_exp i g :=
            Finset.sum_le_univ_sum_of_nonneg (fun _ => Nat.zero_le _)
        _ < 512 := by
          fin_cases i <;> decide
  4. The sums of powers of two for subsets S and T are congruent modulo 512.

    Let e be the exponent function for agent i, which is injective by efx_allsource_three_pair_perturbed_nondegenerate_exp_inj. Summing the modular congruences for each good over S and T shows that the total valuations of S and T are congruent modulo 512 to their respective sums of powers of two. Since the valuations of S and T are assumed equal, transitivity gives that the two sums of powers of two are congruent modulo 512.

    lines 27–36

    uses efx_allsource_three_pair_perturbed_nondegenerate_exp_inj, Nat.ModEq.sum, efx_allsource_three_pair_perturbed_nondegenerate_modEq

      set e := efx_allsource_three_pair_perturbed_nondegenerate_exp i
      have he_inj : Function.Injective e := efx_allsource_three_pair_perturbed_nondegenerate_exp_inj i
      have hS : (∑ g ∈ S, efx_allsource_three_pair_perturbed_values i g) ≡
                (∑ g ∈ S, 2 ^ e g) [MOD 512] :=
        Nat.ModEq.sum (fun g _ => efx_allsource_three_pair_perturbed_nondegenerate_modEq i g)
      have hT : (∑ g ∈ T, efx_allsource_three_pair_perturbed_values i g) ≡
                (∑ g ∈ T, 2 ^ e g) [MOD 512] :=
        Nat.ModEq.sum (fun g _ => efx_allsource_three_pair_perturbed_nondegenerate_modEq i g)
      have hmod : (∑ g ∈ S, 2 ^ e g) ≡ (∑ g ∈ T, 2 ^ e g) [MOD 512] :=
        hS.symm.trans (h ▸ hT)
  5. The sums of powers of two over S and T are strictly equal.

    Unfolding modular equivalence to equality of remainders modulo 512 and applying the bound that both sums are strictly less than 512, each sum reduces to itself modulo 512, establishing that the two sums are strictly equal.

    lines 37–40

    uses efx_allsource_three_pair_perturbed_nondegenerate_sum_lt, Nat.ModEq, Nat.mod_eq_of_lt

      have ltS := efx_allsource_three_pair_perturbed_nondegenerate_sum_lt i S
      have ltT := efx_allsource_three_pair_perturbed_nondegenerate_sum_lt i T
      rw [Nat.ModEq] at hmod
      rw [Nat.mod_eq_of_lt ltS, Nat.mod_eq_of_lt ltT] at hmod
  6. The image sets e(S) and e(T) are equal.

    Rewriting the sums over S and T as sums of 2^k over the image sets e(S) and e(T) using the injectivity of e, we obtain equal binary sums. By the uniqueness of binary representation (geometric sums with base 2), the exponent sets e(S) and e(T) must be identical.

    lines 41–46

    uses Finset.sum_image, Finset.geomSum_injective

      have hgeom : (∑ k ∈ S.image e, 2 ^ k) = ∑ k ∈ T.image e, 2 ^ k := by
        rw [Finset.sum_image (fun x _ y _ h => he_inj h),
            Finset.sum_image (fun x _ y _ h => he_inj h),
            hmod]
      have himage : S.image e = T.image e :=
        Finset.geomSum_injective (by norm_num) hgeom
  7. The subsets of goods S and T are equal.

    Since e is injective, the image operation on finite sets is injective, which implies that S = T.

    line 47

    uses Finset.image_injective

      exact Finset.image_injective he_inj himage
Finset.sum_le_univ_sum_of_nonneg
A finite sum of non-negative terms over a subset is at most the sum over the entire universe.
Nat.zero_le
Every natural number is non-negative.
Nat.ModEq.sum
Congruence modulo n is preserved under finite sums.
Nat.ModEq
The definition of modular equivalence: a ≡ b [MOD n] means a % n = b % n.
Nat.mod_eq_of_lt
If a natural number is strictly less than the modulus, its remainder modulo that number is itself.
Finset.sum_image
The sum of f over the image of a set under an injective map equals the sum of f ∘ g over the set.
Finset.geomSum_injective
Subsets of natural numbers are uniquely determined by the sum of powers of n for n ≥ 2 (uniqueness of base-n representation).
Finset.image_injective
Taking the image under an injective map is injective on finite sets.
efx_allsource_three_pair_perturbed_nondegenerate_exp_inj
For each agent, the exponent assignment is injective.
efx_allsource_three_pair_perturbed_nondegenerate_modEq
The valuation of any good for any agent is congruent modulo 512 to 2 raised to the good's assigned exponent.
efx_allsource_three_pair_perturbed_nondegenerate_sum_lt
The sum of 2 raised to the exponent assignment over any subset of goods is strictly less than 512.

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

Lean’s trace was cut to the first 400 of 752 tactics.

def efx_allsource_three_pair_perturbed_nondegenerate_exp : Fin 4 → Fin 9 → ℕ :=  ![![7, 8, 0, 1, 2, 3, 4, 5, 6],    ![0, 1, 7, 8, 2, 3, 4, 5, 6],    ![0, 1, 2, 3, 7, 8, 4, 5, 6],    ![0, 1, 2, 3, 4, 5, 7, 8, 6]]lemma efx_allsource_three_pair_perturbed_nondegenerate_exp_inj (i : Fin 4) :    Function.Injective (efx_allsource_three_pair_perturbed_nondegenerate_exp i) := by  intro a b h  fin_cases i <;> fin_cases a <;> fin_cases b <;> revert h <;> decidelemma efx_allsource_three_pair_perturbed_nondegenerate_modEq (i : Fin 4) (g : Fin 9) :    efx_allsource_three_pair_perturbed_values i g ≡ 2 ^ efx_allsource_three_pair_perturbed_nondegenerate_exp i g [MOD 512] := by  fin_cases i <;> fin_cases g <;> decidelemma efx_allsource_three_pair_perturbed_nondegenerate_sum_lt (i : Fin 4) (S : Finset (Fin 9)) :    ∑ g ∈ S, 2 ^ efx_allsource_three_pair_perturbed_nondegenerate_exp i g < 512 := by  calc    ∑ g ∈ S, 2 ^ efx_allsource_three_pair_perturbed_nondegenerate_exp i g      ≤ ∑ g : Fin 9, 2 ^ efx_allsource_three_pair_perturbed_nondegenerate_exp i g :=        Finset.sum_le_univ_sum_of_nonneg (fun _ => Nat.zero_le _)    _ < 512 := by      fin_cases i <;> decidetheorem efx_allsource_three_pair_perturbed_nondegenerate (i : Fin 4) (S T : Finset (Fin 9))  (h : (∑ g ∈ S, efx_allsource_three_pair_perturbed_values i g) = ∑ g ∈ T, efx_allsource_three_pair_perturbed_values i g) : S = T := by  set e := efx_allsource_three_pair_perturbed_nondegenerate_exp i  have he_inj : Function.Injective e := efx_allsource_three_pair_perturbed_nondegenerate_exp_inj i  have hS : (∑ g ∈ S, efx_allsource_three_pair_perturbed_values i g) ≡            (∑ g ∈ S, 2 ^ e g) [MOD 512] :=    Nat.ModEq.sum (fun g _ => efx_allsource_three_pair_perturbed_nondegenerate_modEq i g)  have hT : (∑ g ∈ T, efx_allsource_three_pair_perturbed_values i g) ≡            (∑ g ∈ T, 2 ^ e g) [MOD 512] :=    Nat.ModEq.sum (fun g _ => efx_allsource_three_pair_perturbed_nondegenerate_modEq i g)  have hmod : (∑ g ∈ S, 2 ^ e g) ≡ (∑ g ∈ T, 2 ^ e g) [MOD 512] :=    hS.symm.trans (h ▸ hT)  have ltS := efx_allsource_three_pair_perturbed_nondegenerate_sum_lt i S  have ltT := efx_allsource_three_pair_perturbed_nondegenerate_sum_lt i T  rw [Nat.ModEq] at hmod  rw [Nat.mod_eq_of_lt ltS, Nat.mod_eq_of_lt ltT] at hmod  have hgeom : (∑ k ∈ S.image e, 2 ^ k) = ∑ k ∈ T.image e, 2 ^ k := by    rw [Finset.sum_image (fun x _ y _ h => he_inj h),        Finset.sum_image (fun x _ y _ h => he_inj h),        hmod]  have himage : S.image e = T.image e :=    Finset.geomSum_injective (by norm_num) hgeom  exact Finset.image_injective he_inj himage
See it in the graphDiscuss this resultChallenge it