Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

First-order permutation-equivariant linear layers

Open
QAlgorithms.Papers.Independent.Intakenext100.P94.first_order_layer

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let n≥1n\ge1n≥1, let ξ:R→R\xi:\mathbb R\to\mathbb Rξ:R→R be the fixed shared pointwise nonlinearity, and let L:Rn→RnL:\mathbb R^n\to\mathbb R^nL:Rn→Rn be linear. Permutations act by (σf)i=fσ−1(i)(\sigma f)_i=f_{\sigma^{-1}(i)}(σf)i​=fσ−1(i)​. Then LLL is equivariant if and only if there are real weights w0,w1w_0,w_1w0​,w1​, chosen independently of the input, such that

(Lf)i=w0fi+w1∑j=1nfjfor every f,i.(Lf)_i=w_0f_i+w_1\sum_{j=1}^n f_j\qquad\text{for every }f,i.(Lf)i​=w0​fi​+w1​j=1∑n​fj​for every f,i.

Consequently the layer output is fiout=ξ(w0fi+w1∑jfj)f_i^{\rm out}=\xi(w_0f_i+w_1\sum_jf_j)fiout​=ξ(w0​fi​+w1​∑j​fj​). This gives the complete linear layer form; at n=1n=1n=1 the coefficients are redundant. The paper credits this result to Zaheer et al. (2017).

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P94
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P94

open scoped BigOperators

attribute [local instance] Classical.propDecidable

/-- Theorem 1, source PDF p.4 (proof p.13), restating Zaheer et al. (2017).
The weights describe the linear map before a possibly noninjective xi; n=1 is allowed. -/
theorem first_order_layer (n : ℕ) (hn : 1 ≤ n) (xi : ℝ → ℝ)
    (L : Tensor n 1 →ₗ[ℝ] Tensor n 1) :
    (L ∈ equivariantLinearMaps (permutationTensorAction (n := n) (k := 1)) permutationTensorAction ↔
      ∃ w0 w1 : ℝ, ∀ F i, L F ![i] = w0 * F ![i] + w1 * ∑ j, F ![j]) ∧
    (L ∈ equivariantLinearMaps (permutationTensorAction (n := n) (k := 1)) permutationTensorAction →
      ∃ w0 w1 : ℝ, ∀ F i,
        pointwise xi (L F) ![i] = xi (w0 * F ![i] + w1 * ∑ j, F ![j])) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P94

end
Source
The general theory of permutation equivarant neural networks and higher order graph variational encoders, arXiv:2004.03990v1, PDF p. 4, Theorem 1 (§3): first order layer
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For every natural number n≥1n\ge1n≥1, every function ξ:R→R\xi:\mathbb R\to\mathbb Rξ:R→R, and every real-linear map LLL on the space of real functions on one-entry tuples from {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1}, identify such a function FFF with its coordinates FiF_iFi​. For a permutation sss of {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1}, define (s⋅F)i=Fs−1(i)(s\cdot F)_i=F_{s^{-1}(i)}(s⋅F)i​=Fs−1(i)​. The theorem asserts both that

[∀s,F, L(s⋅F)=s⋅(LF)]⟺[∃w0,w1∈R, ∀F,i, (LF)i=w0Fi+w1∑j=0n−1Fj],\bigl[\forall s,F,\ L(s\cdot F)=s\cdot(LF)\bigr] \quad\Longleftrightarrow\quad \bigl[\exists w_0,w_1\in\mathbb R,\ \forall F,i,\ (LF)_i=w_0F_i+w_1\sum_{j=0}^{n-1}F_j\bigr],[∀s,F, L(s⋅F)=s⋅(LF)]⟺[∃w0​,w1​∈R, ∀F,i, (LF)i​=w0​Fi​+w1​j=0∑n−1​Fj​],

and that, if LLL satisfies the equivariance condition on the left, then there exist real numbers w0,w1w_0,w_1w0​,w1​ such that, for every FFF and iii,

ξ((LF)i)=ξ ⁣(w0Fi+w1∑j=0n−1Fj).\xi((LF)_i)=\xi\!\left(w_0F_i+w_1\sum_{j=0}^{n-1}F_j\right).ξ((LF)i​)=ξ(w0​Fi​+w1​j=0∑n−1​Fj​).

Here applying ξ\xiξ pointwise means applying it separately to each real coordinate. No regularity or linearity is required of ξ\xiξ, and uniqueness of the weights is not asserted. The case n=1n=1n=1 is included.

Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 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