Proof of Lemma E.13 — Newton's identities, and power sums of orders determine a multiset of reals
ProvedPartialHomog.Threshold.lemma_E_13_power_sumsalgebraic-complexityarithmetic-circuitsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
(1) Newton's identities. In a commutative ring , let and have equal elementary symmetric functions for . Then their power sums agree:
(2) Let with and for . Then as multisets.
In the proof of Lemma E.13, (1) is applied to the rational functions with , and (2) to the multisets , .
Formalization Note Families are indexed by Fin n; is Multiset.esymm of the multiset univ.val.map x; multiset equality is univ.val.map x = univ.val.map y.
Differences from the source:
- generalization: Newton's identities applied to rational functions c_ij/ℓ_j over ℝ (the field ℝ(z)) → any commutative ring S; reason: Newton's identities express p_k as an integer polynomial in e_1, …, e_k; S = FractionRing ℝ[z] is the source's case
- encoding: the multiset {c_ij/α_j}_{j∈G} and |G| ≤ D − 3 power sums → families
Fin n → ℝwith n ≤ M and orders 1 ≤ p ≤ M; reason: relabelling: n = |G|, M = D − 3
Preamble
import Mathlib
Formal statement
namespace PartialHomog.Threshold
/-- Proof of Lemma E.13 (p. 27): (1) Newton's identities: in a commutative ring, if two families
`x, y` of `n` elements have equal elementary symmetric functions of every degree `1 ≤ k ≤ M`,
they have equal power sums of every order `1 ≤ p ≤ M`; (2) two families of `n ≤ M` real
numbers with equal power sums of every order `1 ≤ p ≤ M` are equal as multisets. -/
theorem lemma_E_13_power_sums {S : Type*} [CommRing S] :
(∀ (n M : ℕ) (x y : Fin n → S),
(∀ k, 1 ≤ k → k ≤ M →
(Finset.univ.val.map x).esymm k = (Finset.univ.val.map y).esymm k) →
∀ p, 1 ≤ p → p ≤ M → ∑ j, x j ^ p = ∑ j, y j ^ p) ∧
(∀ (n M : ℕ) (x y : Fin n → ℝ), n ≤ M →
(∀ p, 1 ≤ p → p ≤ M → ∑ j, x j ^ p = ∑ j, y j ^ p) →
Finset.univ.val.map x = Finset.univ.val.map y) := by sorry
end PartialHomog.Threshold
Source
Spiizer, Partial Homogenization and the Structure of Optimal Algebraic Algorithms, STOC 2027 submission (manuscript sha256 33096d05…), p. 27 (PDF 29), proof of Lemma E.13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.