efx_allsource_three_pair_perturbed_nondegenerate
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
- efx_allsource_three_pair_perturbed_valuesA binary nondegenerate perturbation of the four-pair instance.
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.
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.
intro a b h fin_cases i <;> fin_cases a <;> fin_cases b <;> revert h <;> decide
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.
fin_cases i <;> fin_cases g <;> decideFor 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.
uses
Finset.sum_le_univ_sum_of_nonneg,Nat.zero_lecalc ∑ 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
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.
uses
efx_allsource_three_pair_perturbed_nondegenerate_exp_inj,Nat.ModEq.sum,efx_allsource_three_pair_perturbed_nondegenerate_modEqset 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)
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.
uses
efx_allsource_three_pair_perturbed_nondegenerate_sum_lt,Nat.ModEq,Nat.mod_eq_of_lthave 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
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.
uses
Finset.sum_image,Finset.geomSum_injectivehave 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
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.
uses
Finset.image_injectiveexact 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
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.
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