AFTD Auto-Formalizing Theoretical Domains

efx_pair_binary_no_one_split_nat

theoremverified

For the explicit binary nine-good matrix, every allocation encoded by the one-split construction fails a natural-number total-value EFX inequality.

Statement

theorem efx_pair_binary_no_one_split_nat : ∀ (r a b c d e f : Fin 4),
    ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 9, efx_pair_binary_one_split r a b c d e f g = j →
      (∑ h : Fin 9, if efx_pair_binary_one_split r a b c d e f h = j then efx_pair_binary_values i h else 0) ≤
      (∑ h : Fin 9, if efx_pair_binary_one_split r a b c d e f h = i then efx_pair_binary_values i h else 0) +
        efx_pair_binary_values i g)
Source
Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. Exact route obstruction from experiment 10993, not a counterexample to EFX existence; no novelty claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • efx_pair_binary_valuesA positive four-agent nine-good valuation matrix: the first two rows are (2,1,2,1,2,1,2,1,2), and the last two rows are (1,2,1,2,1,2,1,2,2).
  • efx_pair_binary_one_splitAssign the four old adjacent pairs among goods 0 through 7 and the new good 8 to arbitrary agents, except the pair indexed r may have its…
  • efx_pair_binary_no_one_split_zero_natFor the explicit binary nine-good matrix, every one-split allocation allowing only the old pair indexed 0 to split fails a natural-number…
  • efx_pair_binary_no_one_split_one_natFor the explicit binary nine-good matrix, every one-split allocation allowing only the old pair indexed 1 to split fails a natural-number…
  • efx_pair_binary_no_one_split_two_natFor the explicit binary nine-good matrix, every one-split allocation allowing only the old pair indexed 2 to split fails a natural-number…
  • efx_pair_binary_no_one_split_three_natFor the explicit binary nine-good matrix, every one-split allocation allowing only the old pair indexed 3 to split fails a natural-number…
Used by 1
  • efx_pair_binary_no_one_splitFor the explicit binary nine-good matrix cast to real values, no allocation encoded by the one-split construction is EFX.

The proof, explained

To prove that no allocation produced by the one-split construction satisfies the natural-number EFX inequality for the given binary valuation matrix, the argument proceeds by exhaustive case analysis on the template row parameter $r \in \{0, 1, 2, 3\}$. The case split yields four subgoals, each of which is immediately resolved by a pre-established lemma dedicated to that specific template row.

  1. It suffices to establish the result for each possible template row index $r \in \{0, 1, 2, 3\}$ individually.

    We introduce the template row parameter $r$ and perform an exhaustive case analysis on the four elements of $\mathrm{Fin}\ 4$, which divides the overall goal into four subgoals corresponding to $r = 0, 1, 2, 3$.

    lines 8–9

      intro r
      fin_cases r
  2. No one-split allocation with template row $r = 0$ satisfies the EFX property.

    The goal for $r = 0$ is closed immediately by applying the lemma `efx_pair_binary_no_one_split_zero_nat`.

    line 10

    uses efx_pair_binary_no_one_split_zero_nat

      · exact efx_pair_binary_no_one_split_zero_nat
  3. No one-split allocation with template row $r = 1$ satisfies the EFX property.

    The goal for $r = 1$ is closed immediately by applying the lemma `efx_pair_binary_no_one_split_one_nat`.

    line 11

    uses efx_pair_binary_no_one_split_one_nat

      · exact efx_pair_binary_no_one_split_one_nat
  4. No one-split allocation with template row $r = 2$ satisfies the EFX property.

    The goal for $r = 2$ is closed immediately by applying the lemma `efx_pair_binary_no_one_split_two_nat`.

    line 12

    uses efx_pair_binary_no_one_split_two_nat

      · exact efx_pair_binary_no_one_split_two_nat
  5. No one-split allocation with template row $r = 3$ satisfies the EFX property.

    The goal for $r = 3$ is closed immediately by applying the lemma `efx_pair_binary_no_one_split_three_nat`.

    line 13

    uses efx_pair_binary_no_one_split_three_nat

      · exact efx_pair_binary_no_one_split_three_nat
efx_pair_binary_no_one_split_zero_nat
For template row index 0, no parameter assignment produces an allocation satisfying the EFX inequality under the binary valuation matrix.
efx_pair_binary_no_one_split_one_nat
For template row index 1, no parameter assignment produces an allocation satisfying the EFX inequality under the binary valuation matrix.
efx_pair_binary_no_one_split_two_nat
For template row index 2, no parameter assignment produces an allocation satisfying the EFX inequality under the binary valuation matrix.
efx_pair_binary_no_one_split_three_nat
For template row index 3, no parameter assignment produces an allocation satisfying the EFX inequality under the binary valuation matrix.

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

open Function Finsettheorem efx_pair_binary_no_one_split_nat : ∀ (r a b c d e f : Fin 4),    ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 9, efx_pair_binary_one_split r a b c d e f g = j →      (∑ h : Fin 9, if efx_pair_binary_one_split r a b c d e f h = j then efx_pair_binary_values i h else 0) ≤      (∑ h : Fin 9, if efx_pair_binary_one_split r a b c d e f h = i then efx_pair_binary_values i h else 0) +        efx_pair_binary_values i g) := by  intro r  fin_cases r  · exact efx_pair_binary_no_one_split_zero_nat  · exact efx_pair_binary_no_one_split_one_nat  · exact efx_pair_binary_no_one_split_two_nat  · exact efx_pair_binary_no_one_split_three_nat
See it in the graphDiscuss this resultChallenge it