Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Lemma E.13 — Newton's identities, and power sums of orders 1,…,M≥n1,\dots,M \ge n1,…,M≥n determine a multiset of nnn reals

Proved
PartialHomog.Threshold.lemma_E_13_power_sums

by Shuze Chen · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

algebraic-complexityarithmetic-circuitsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

(1) Newton's identities. In a commutative ring SSS, let x=(x1,…,xn)x=(x_1,\dots,x_n)x=(x1​,…,xn​) and y=(y1,…,yn)y=(y_1,\dots,y_n)y=(y1​,…,yn​) have equal elementary symmetric functions ek(x)=ek(y)e_k(x)=e_k(y)ek​(x)=ek​(y) for 1≤k≤M1\le k\le M1≤k≤M. Then their power sums agree:

∑jxjp=∑jyjp(1≤p≤M).\sum_j x_j^p=\sum_j y_j^p\qquad(1\le p\le M).j∑​xjp​=j∑​yjp​(1≤p≤M).

(2) Let x,y∈Rnx,y\in\mathbb R^nx,y∈Rn with n≤Mn\le Mn≤M and ∑jxjp=∑jyjp\sum_jx_j^p=\sum_jy_j^p∑j​xjp​=∑j​yjp​ for 1≤p≤M1\le p\le M1≤p≤M. Then {x1,…,xn}={y1,…,yn}\{x_1,\dots,x_n\}=\{y_1,\dots,y_n\}{x1​,…,xn​}={y1​,…,yn​} as multisets.

In the proof of Lemma E.13, (1) is applied to the rational functions cij/ℓjc_{ij}/\ell_jcij​/ℓj​ with M=D−3M=D-3M=D−3, and (2) to the multisets {cij/αj}j∈G\{c_{ij}/\alpha_j\}_{j\in G}{cij​/αj​}j∈G​, ∣G∣≤D−3|G|\le D-3∣G∣≤D−3.

Formalization Note Families are indexed by Fin n; eke_kek​ 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
  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me