comparison_phi1_linearIndependent
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 2
- comparison_eval_ker_le_span_kappaEvery formal quadratic feature vector c in F_2 that evaluates to zero on every strict order (<phi_2(x), c> = 0 for all permutations x of…
- quadratic_comparison_evaluation_kernel_and_projectorLet n >= 3, N = C(n,2), nu_triangle = C(n,3). Strict orders on [n] are given by permutations x of Fin n (x i = rank of label i); for an…
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.
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.
uses
Fintype.linearIndependent_iffclassical rw [Fintype.linearIndependent_iff] intro g hg
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$.
uses
congrFun,Fintype.sum_option,comparison_phi1have 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
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$.
uses
ne_of_lt,Fin.ext_iff,Equiv.trans_apply,Equiv.swap_apply_left,Equiv.swap_apply_of_ne_of_ne,Ne.symmhave 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
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$.
uses
lt_irrefl,ne_of_lt,comparison_sign,Equiv.swap_apply_def,Fin.ext_iff,Fin.lt_defhave 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
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$.
uses
comparison_sign,Fin.lt_defhave 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]
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$.
uses
Finset.add_sum_erase,Finset.mem_univ,Finset.sum_congr,Finset.ne_of_mem_erasehave 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
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$.
uses
zero_mul,Finset.sum_const_zero,add_zerohave h0 := hx 1 simp only [hedge, zero_mul, Finset.sum_const_zero, add_zero] at h0
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.
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.
- In step 4, the verification that the swap of 0 and 1 preserves the relative order of x(p) and x(q) for all other edges involves a case split over the possible values of x(p) and x(q), which is handled automatically by `split_ifs <;> simp_all <;> omega`.
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.
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