AFTD Auto-Formalizing Theoretical Domains

comparison_phi1_linearIndependent

theoremverified

The constant function 1 and the comparison signs d_e, e an edge of [n], are linearly independent real functions on strict orders (permutations of Fin n).

Statement

theorem comparison_phi1_linearIndependent (n : ℕ) :
    LinearIndependent ℝ
      (fun i : comparison_feature1 n => fun x : Equiv.Perm (Fin n) => comparison_phi1 x i)
Source
Step of arXiv:2610.34762 (Quantum ordinal selection with two comparisons), Section 3.1, Lemma 1 (quadratic_comparison_evaluation_kernel_and_projector)
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • comparison_phi1The real linear evaluation vector phi_1(x) : comparison_feature1 n → ℝ of a strict order x (a permutation of Fin n giving the ranks): its…
  • comparison_feature1The type indexing the orthonormal coordinate basis of the formal linear feature space F_1 = span{1, d_e}: Option (comparison_edge n),…
  • comparison_edgeThe type of edges of the label set [n] = Fin n: the subtype of pairs (a, b) in Fin n × Fin n with a < b, each unordered edge {a, b} being…
  • comparison_signThe real-valued comparison sign d_e(x) of a strict order. A strict order on the labels Fin n is given by a permutation x : Equiv.Perm (Fin…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 2

The proof, explained

To prove that the constant function 1 and the comparison signs d_e of all edges e are linearly independent, we consider a vanishing linear combination g(none) + ∑_e g(some e) d_e = 0. For any edge e₀ = (a, b) with a < b, we construct two permutations x and y that map (a, b) to (0, 1) and (1, 0) respectively while agreeing on all other pairs. Swapping the values 0 and 1 flips the comparison sign of e₀ between 1 and -1 but leaves the comparison sign of every other edge unchanged, so subtracting the relation evaluated at y from the relation evaluated at x isolates 2 g(some e₀) = 0. With all edge coefficients shown to be zero, evaluating at the identity permutation forces the constant coefficient g(none) = 0 as well.

  1. Linear independence of the feature functions reduces to showing that if a linear combination vanishes identically on all permutations, each coefficient must be zero.

    By `Fintype.linearIndependent_iff`, a finite family of functions is linearly independent if and only if any linear combination $\sum_i g(i)\phi_i = 0$ has $g(i) = 0$ for all $i$. We assume such a linear combination with coefficient function $g$ vanishing on all permutations.

    lines 4–6

    uses Fintype.linearIndependent_iff

      classical
      rw [Fintype.linearIndependent_iff]
      intro g hg
  2. For every permutation x, the vanishing relation evaluates to g(none) + ∑_e g(some e) * comparison_sign(x, e) = 0.

    Applying the assumed functional equality pointwise to any permutation $x$ via `congrFun`, and splitting the sum over the option type into the `none` component (which evaluates to 1 by definition of `comparison_phi1`) and the `some e` components using `Fintype.sum_option`, yields this scalar identity for each $x$.

    lines 7–11

    uses congrFun, Fintype.sum_option, comparison_phi1

      have hx : ∀ x : Equiv.Perm (Fin n),
          g none + ∑ e : comparison_edge n, g (some e) * comparison_sign x e = 0 := by
        intro x
        have := congrFun hg x
        simpa [Fintype.sum_option, comparison_phi1] using this
  3. For any edge e₀ = (a, b) with a < b, there exist permutations x and y such that x(a) = 0, x(b) = 1, and y = swap(0, 1) ∘ x.

    Since $a < b < n$, the index set has at least two elements $0$ and $1$. We set $\sigma = \operatorname{swap}(a, 0)$, which maps $a$ to $0$. Since $a \neq b$, $\sigma(b) \neq 0$. Next, we define $x = \operatorname{swap}(\sigma(b), 1) \circ \sigma$, which sends $b$ to $1$ while keeping $x(a) = 0$ because $\sigma(b) \neq 0$ and $0 \neq 1$. We then define $y$ by swapping the values $0$ and $1$ after applying $x$.

    lines 12–33

    uses ne_of_lt, Fin.ext_iff, Equiv.trans_apply, Equiv.swap_apply_left, Equiv.swap_apply_of_ne_of_ne, Ne.symm

      have hedge : ∀ e : comparison_edge n, g (some e) = 0 := by
        intro e0
        obtain ⟨⟨a, b⟩, hab⟩ := e0
        have hab' : a < b := hab
        have hb := b.isLt
        have hav : a.val < b.val := hab'
        let i0 : Fin n := ⟨0, by omega⟩
        let i1 : Fin n := ⟨1, by omega⟩
        let σ : Equiv.Perm (Fin n) := Equiv.swap a i0
        let x : Equiv.Perm (Fin n) := σ.trans (Equiv.swap (σ b) i1)
        let y : Equiv.Perm (Fin n) := x.trans (Equiv.swap i0 i1)
        have hσb : σ b ≠ i0 := by
          intro h
          have : σ b = σ a := by simp [σ, h]
          exact (ne_of_lt hab') (σ.injective this).symm
        have hxa : x a = i0 := by
          have h01 : i0 ≠ i1 := by simp [i0, i1, Fin.ext_iff]
          simp only [x, Equiv.trans_apply, σ, Equiv.swap_apply_left]
          rw [Equiv.swap_apply_of_ne_of_ne (Ne.symm hσb) h01]
        have hxb : x b = i1 := by
          simp only [x, Equiv.trans_apply, Equiv.swap_apply_left]
        have hy : ∀ j, y j = Equiv.swap i0 i1 (x j) := fun j => rfl
  4. For any edge f ≠ e₀, the comparison signs under x and y are identical: comparison_sign(y, f) = comparison_sign(x, f).

    Let $f = (p, q)$ with $p < q$ be distinct from $(a, b)$. Since $y$ is obtained from $x$ by transposing the values $0$ and $1$, the relative order of $y(p)$ and $y(q)$ could only differ from that of $x(p)$ and $x(q)$ if $\{x(p), x(q)\} = \{0, 1\}$. But by injectivity of $x$, having $(x(p), x(q)) = (0, 1)$ would mean $(p, q) = (a, b)$, contradicting $f \neq e_0$; and $(x(p), x(q)) = (1, 0)$ would mean $(p, q) = (b, a)$, contradicting $p < q$ and $a < b$. Thus the transposition of $0$ and $1$ cannot reverse the comparison sign of any edge other than $e_0$.

    lines 34–55

    uses lt_irrefl, ne_of_lt, comparison_sign, Equiv.swap_apply_def, Fin.ext_iff, Fin.lt_def

        have key : ∀ f : comparison_edge n, f ≠ ⟨(a, b), hab⟩ →
            comparison_sign y f = comparison_sign x f := by
          intro f hf
          obtain ⟨⟨p, q⟩, hpq⟩ := f
          have hpq' : p < q := hpq
          have hne : ¬ (x p = i0 ∧ x q = i1) := by
            rintro ⟨h1, h2⟩
            apply hf
            have : p = a := x.injective (h1.trans hxa.symm)
            have : q = b := x.injective (h2.trans hxb.symm)
            subst_vars; rfl
          have hne2 : ¬ (x p = i1 ∧ x q = i0) := by
            rintro ⟨h1, h2⟩
            have : p = b := x.injective (h1.trans hxb.symm)
            have : q = a := x.injective (h2.trans hxa.symm)
            subst_vars
            exact absurd (hpq'.trans hab') (lt_irrefl _)
          have hpq_ne : x p ≠ x q := fun h => (ne_of_lt hpq') (x.injective h)
          simp only [comparison_sign, hy]
          rw [Equiv.swap_apply_def, Equiv.swap_apply_def]
          simp only [Fin.ext_iff, Fin.lt_def, i0, i1] at hne hne2 hpq_ne ⊢
          split_ifs <;> simp_all <;> omega
  5. The comparison sign of e₀ is 1 under x and -1 under y.

    Under $x$, we have $x(a) = 0 < 1 = x(b)$, so $\operatorname{comparison\_sign}(x, e_0) = 1$. Under $y$, the values are transposed to $y(a) = 1$ and $y(b) = 0$, so $y(a) > y(b)$, which gives $\operatorname{comparison\_sign}(y, e_0) = -1$.

    lines 56–59

    uses comparison_sign, Fin.lt_def

        have hsx : comparison_sign x ⟨(a, b), hab⟩ = 1 := by
          simp [comparison_sign, hxa, hxb, i0, i1, Fin.lt_def]
        have hsy : comparison_sign y ⟨(a, b), hab⟩ = -1 := by
          simp [comparison_sign, hy, hxa, hxb, i0, i1, Fin.lt_def]
  6. Every edge coefficient vanishes: g(some e) = 0 for all edges e.

    We evaluate the vanishing relation at $x$ and at $y$. In each sum, we separate the $e_0$ term from the rest using `Finset.add_sum_erase`. Since the remaining sums over all $f \neq e_0$ agree under $x$ and $y$, subtracting the equation for $y$ from that for $x$ eliminates both the constant term $g(\text{none})$ and the common remaining sum, leaving $g(\text{some } e_0) - (-g(\text{some } e_0)) = 2 g(\text{some } e_0) = 0$. By linear arithmetic, $g(\text{some } e_0) = 0$.

    lines 60–70

    uses Finset.add_sum_erase, Finset.mem_univ, Finset.sum_congr, Finset.ne_of_mem_erase

        have h1 := hx x
        have h2 := hx y
        rw [← Finset.add_sum_erase _ _ (Finset.mem_univ ⟨(a, b), hab⟩)] at h1 h2
        have hrest : ∑ e ∈ Finset.univ.erase ⟨(a, b), hab⟩, g (some e) * comparison_sign y e =
            ∑ e ∈ Finset.univ.erase ⟨(a, b), hab⟩, g (some e) * comparison_sign x e := by
          apply Finset.sum_congr rfl
          intro f hf
          rw [key f (Finset.ne_of_mem_erase hf)]
        rw [hrest, hsy] at h2
        rw [hsx] at h1
        linarith
  7. The constant function coefficient g(none) is zero.

    Evaluating the vanishing linear relation at the identity permutation and substituting $g(\text{some } e) = 0$ for all edges $e$, the entire summation over the edges vanishes, leaving $g(\text{none}) = 0$.

    lines 71–72

    uses zero_mul, Finset.sum_const_zero, add_zero

      have h0 := hx 1
      simp only [hedge, zero_mul, Finset.sum_const_zero, add_zero] at h0
  8. Every coefficient g(i) is zero, completing the proof of linear independence.

    By case analysis on $i \in \operatorname{comparison\_feature1}(n)$, $i$ is either `none` (for which $g(\text{none}) = 0$) or `some e` (for which $g(\text{some } e) = 0$). Hence all coefficients are zero.

    lines 73–76

      intro i
      cases i with
      | none => exact h0
      | some e => exact hedge e
Fintype.linearIndependent_iff
A finite family of vectors is linearly independent if and only if any linear combination equal to zero has all coefficients equal to zero.
congrFun
If two functions are equal, their values on any given input are equal.
Fintype.sum_option
The sum of a function over `Option α` equals its value at `none` plus the sum of its values over all `some a`.
comparison_phi1
The feature map that maps `none` to 1 and `some e` to the comparison sign of the edge `e`.
ne_of_lt
In a strict order, if a < b then a ≠ b.
Fin.ext_iff
Two elements of `Fin n` are equal if and only if their underlying natural number values are equal.
Equiv.trans_apply
Applying the composition of two equivalences equals applying the second to the value of the first.
Equiv.swap_apply_left
A swap of a and b sends a to b.
Equiv.swap_apply_of_ne_of_ne
A swap of a and b fixes any element that is neither a nor b.
Ne.symm
If a ≠ b, then b ≠ a.
lt_irrefl
Strict inequality is irreflexive: no element is strictly less than itself.
comparison_sign
Returns 1 if the permutation preserves the order of the edge endpoints, and -1 if it reverses them.
Equiv.swap_apply_def
The definition of a transposition: swap(a, b)(x) is b if x = a, a if x = b, and x otherwise.
Fin.lt_def
A strict inequality a < b in `Fin n` is equivalent to the inequality of their underlying natural numbers.
Finset.add_sum_erase
Separating a chosen element out of a finite sum leaves the sum over the remaining elements.
Finset.mem_univ
Every element of a finite type belongs to its universal set `Finset.univ`.
Finset.sum_congr
Two sums are equal if their index sets match and their terms agree on every element.
Finset.ne_of_mem_erase
An element belonging to a set with `a` removed is not equal to `a`.
zero_mul
Zero multiplied by any element is zero.
Finset.sum_const_zero
The sum of zeros over a finite set is zero.
add_zero
Adding zero to an element leaves it unchanged.

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 comparison_phi1_linearIndependent (n : ℕ) :    LinearIndependent ℝ      (fun i : comparison_feature1 n => fun x : Equiv.Perm (Fin n) => comparison_phi1 x i) := by  classical  rw [Fintype.linearIndependent_iff]  intro g hg  have hx : ∀ x : Equiv.Perm (Fin n),      g none + ∑ e : comparison_edge n, g (some e) * comparison_sign x e = 0 := by    intro x    have := congrFun hg x    simpa [Fintype.sum_option, comparison_phi1] using this  have hedge : ∀ e : comparison_edge n, g (some e) = 0 := by    intro e0    obtain ⟨⟨a, b⟩, hab⟩ := e0    have hab' : a < b := hab    have hb := b.isLt    have hav : a.val < b.val := hab'    let i0 : Fin n := ⟨0, by omega⟩    let i1 : Fin n := ⟨1, by omega⟩    let σ : Equiv.Perm (Fin n) := Equiv.swap a i0    let x : Equiv.Perm (Fin n) := σ.trans (Equiv.swap (σ b) i1)    let y : Equiv.Perm (Fin n) := x.trans (Equiv.swap i0 i1)    have hσb : σ b ≠ i0 := by      intro h      have : σ b = σ a := by simp [σ, h]      exact (ne_of_lt hab') (σ.injective this).symm    have hxa : x a = i0 := by      have h01 : i0 ≠ i1 := by simp [i0, i1, Fin.ext_iff]      simp only [x, Equiv.trans_apply, σ, Equiv.swap_apply_left]      rw [Equiv.swap_apply_of_ne_of_ne (Ne.symm hσb) h01]    have hxb : x b = i1 := by      simp only [x, Equiv.trans_apply, Equiv.swap_apply_left]    have hy : ∀ j, y j = Equiv.swap i0 i1 (x j) := fun j => rfl    have key : ∀ f : comparison_edge n, f ≠ ⟨(a, b), hab⟩ →        comparison_sign y f = comparison_sign x f := by      intro f hf      obtain ⟨⟨p, q⟩, hpq⟩ := f      have hpq' : p < q := hpq      have hne : ¬ (x p = i0 ∧ x q = i1) := by        rintro ⟨h1, h2⟩        apply hf        have : p = a := x.injective (h1.trans hxa.symm)        have : q = b := x.injective (h2.trans hxb.symm)        subst_vars; rfl      have hne2 : ¬ (x p = i1 ∧ x q = i0) := by        rintro ⟨h1, h2⟩        have : p = b := x.injective (h1.trans hxb.symm)        have : q = a := x.injective (h2.trans hxa.symm)        subst_vars        exact absurd (hpq'.trans hab') (lt_irrefl _)      have hpq_ne : x p ≠ x q := fun h => (ne_of_lt hpq') (x.injective h)      simp only [comparison_sign, hy]      rw [Equiv.swap_apply_def, Equiv.swap_apply_def]      simp only [Fin.ext_iff, Fin.lt_def, i0, i1] at hne hne2 hpq_ne ⊢      split_ifs <;> simp_all <;> omega    have hsx : comparison_sign x ⟨(a, b), hab⟩ = 1 := by      simp [comparison_sign, hxa, hxb, i0, i1, Fin.lt_def]    have hsy : comparison_sign y ⟨(a, b), hab⟩ = -1 := by      simp [comparison_sign, hy, hxa, hxb, i0, i1, Fin.lt_def]    have h1 := hx x    have h2 := hx y    rw [← Finset.add_sum_erase _ _ (Finset.mem_univ ⟨(a, b), hab⟩)] at h1 h2    have hrest : ∑ e ∈ Finset.univ.erase ⟨(a, b), hab⟩, g (some e) * comparison_sign y e =        ∑ e ∈ Finset.univ.erase ⟨(a, b), hab⟩, g (some e) * comparison_sign x e := by      apply Finset.sum_congr rfl      intro f hf      rw [key f (Finset.ne_of_mem_erase hf)]    rw [hrest, hsy] at h2    rw [hsx] at h1    linarith  have h0 := hx 1  simp only [hedge, zero_mul, Finset.sum_const_zero, add_zero] at h0  intro i  cases i with  | none => exact h0  | some e => exact hedge e
See it in the graphDiscuss this resultChallenge it