Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for The general theory of permutation equivarant neural networks and higher order graph variational encoders

Definition
QAlgorithms_Papers_Independent_Intakenext100_P94

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

prove2quantum

The objects the formalized statements of The general theory of permutation equivarant neural networks and higher order graph variational encoders (arXiv:2004.03990) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • Perm
  • Tensor
  • permutationTensorAction: Simultaneous inverse reindexing, source PDF p.2, Eq.(2).
  • equivariantLinearMaps: Linear intertwiners, source PDF pp.3–4; no bias or nonlinearity is counted.
  • supportedSpace: Tensors supported on a specified equality pattern (PDF pp.3,15).
  • DistinctSpace
  • distinctAction: The distinct-index space is preserved under the source's action.
  • pointwise: Shared pointwise nonlinearity; this is applied after the linear map (PDF p.3).
  • tensorRowSum: Row, column, total and trace contractions (PDF pp.4–5).
  • colSum
  • totalSum
  • activationTraceSum
  • sevenFormula: Theorem 2's seven terms, evaluated only off the diagonal (PDF p.4).
  • fifteenFormula: Corollary 4's fifteen terms, including the trace overbars (PDF p.5).
  • IsRealIrreducible: A real irreducible model means a nonzero representation with no proper, nonzero invariant real linear subspace (PDF p.4).
  • ModelsInequivalent: Models are inequivalent if no invertible intertwiner exists (PDF p.4).
  • FourierBlocks
  • fourierColumnAction: Each column is acted on by the same irreducible model (PDF p.4).
  • FourierWeights
  • applyBlocks: Fourier-space right multiplication; source PDF p.4, Theorem 3.
  • finalPoints: The subgroup fixing the final k points individually, PDF p.12. The embedding is typed and the natural subtraction is protected by k≤n.
  • pointStabilizer
  • Cosets
  • quotientValues: Representative formula with well-definedness asserted by Propositions 5–7; choosing out does not assume the desired bijection or intertwining conclusion.
  • cosetTranslate
  • vectorValues
  • realYoung: Real Young symmetrizer: same concrete row/column permutation sets as the accepted Specht construction, with real scalars as required by PDF p.4.
  • realSpecht
  • HasTensorType: An actual equivariant isomorphism to copies of concrete real Specht ideals. The group acts by left translation inside each ideal. No Fourier coordinates or multiplicities are assumed as an input field (PDF p.4).
  • secondShapes: Printed partition order, source PDF p.4.
  • thirdShapes
  • pairPattern: The three exactly-two-equal patterns are indexed by their singleton position.
  • IsRecipe: A contraction partitions the three input slots into equality blocks; each block is named by its least slot. A selected subset of blocks is retained, and the others are summed. This is precisely the four contraction lists on pp.15–16.
  • Recipe
  • Retained
  • PlacedRecipe: Every injection of the retained slots into the available output slots is used.
  • contractionKernel: Coefficient kernel for one contraction: equal input indices within a block, retained blocks fixed to the selected output entries; other blocks summed freely. Distinct blocks are not required to receive distinct vertex labels.
  • ThirdIndex: 77 generic terms, three sets of 37 pair-supported corrections, and 15 all-diagonal corrections (PDF p.16, Table 4).
  • thirdKernel: Equality-supported corrections are added to the generic formula. The pair index names the singleton output slot; Fin 3 addition is cyclic.
  • thirdFormula: Concrete weighted contraction construction, source PDF pp.15–16.
  • promote: Zero-extension promotion along an injective correspondence, PDF p.6, Eq.(6). Off-image values are explicitly zero; overlapping children add their contributions.
  • relabelEmbedding: The correspondence itself is relabelled, not held fixed (PDF pp.5–6).
  • tensorOuterProduct: Outer product permits higher tensor order; no contraction or bias is implicit.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_SpechtModules

/-!
The accepted-library basename matches reported by the previous check describe
different concepts: Dependency50.P09.tensorAction is a quantum superoperator
tensor product; Gap48.P28.intertwinerSpace is a complex three-representation
Clebsch–Gordan matrix space; Renew46.P15.rowSum is a GT-pattern row sum;
Information100.P53.traceSum is a pairwise discrimination trace-norm bound;
Information100.P26.Blocks is a positive coordinate-block decomposition;
Claimed50.P13.blockAction is a tensor power of a quantum channel;
Information100.P07.Weights is a probability predicate; and the outer products
in Information100.P19/P26 conjugate a complex vector. None is the real tensor,
two-action linear-map space, Fourier multiplicity data or order-raising product
of this paper. Their exact bodies were compared before retaining these local
constructions under distinct descriptive names. No frozen body is duplicated.
-/

noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P94

open scoped BigOperators

attribute [local instance] Classical.propDecidable

abbrev Perm (n : ℕ) := Equiv.Perm (Fin n)

abbrev Tensor (n k : ℕ) := (Fin k → Fin n) → ℝ

/-- Simultaneous inverse reindexing, source PDF p.2, Eq.(2). -/
def permutationTensorAction {n k : ℕ} (s : Perm n) : Tensor n k →ₗ[ℝ] Tensor n k where
  toFun F := fun t => F (fun a => s.symm (t a))
  map_add' _ _ := rfl
  map_smul' _ _ := rfl

example {n k : ℕ} (F : Tensor n k) : permutationTensorAction (1 : Perm n) F = F := rfl

/-- Linear intertwiners, source PDF pp.3–4; no bias or nonlinearity is counted. -/
def equivariantLinearMaps {G E H : Type*} [AddCommGroup E] [Module ℝ E]
    [AddCommGroup H] [Module ℝ H] (A : G → E →ₗ[ℝ] E)
    (B : G → H →ₗ[ℝ] H) : Submodule ℝ (E →ₗ[ℝ] H) where
  carrier := {L | ∀ s x, L (A s x) = B s (L x)}
  zero_mem' := by simp
  add_mem' := by
    intro L M hL hM s x
    simp only [LinearMap.add_apply, map_add, hL s x, hM s x]
  smul_mem' := by
    intro c L hL s x
    simp only [LinearMap.smul_apply, map_smul, hL s x]

/-- Tensors supported on a specified equality pattern (PDF pp.3,15). -/
def supportedSpace {n k : ℕ} (P : (Fin k → Fin n) → Prop) :
    Submodule ℝ (Tensor n k) where
  carrier := {F | ∀ t, ¬ P t → F t = 0}
  zero_mem' := by simp
  add_mem' := by intro F G hF hG t ht; simp [hF t ht, hG t ht]
  smul_mem' := by intro c F hF t ht; simp [hF t ht]

abbrev DistinctSpace (n k : ℕ) := supportedSpace (n := n) (k := k) Function.Injective

/-- The distinct-index space is preserved under the source's action. -/
def distinctAction {n k : ℕ} (s : Perm n) : DistinctSpace n k →ₗ[ℝ] DistinctSpace n k where
  toFun F := ⟨permutationTensorAction s F.val, by
    intro t ht
    apply F.property
    intro hi
    apply ht
    intro a b hab
    exact hi (congrArg s.symm hab)⟩
  map_add' _ _ := by rfl
  map_smul' _ _ := by rfl

/-- Shared pointwise nonlinearity; this is applied after the linear map (PDF p.3). -/
def pointwise {n k : ℕ} (xi : ℝ → ℝ) (F : Tensor n k) : Tensor n k := fun t => xi (F t)

/-- Row, column, total and trace contractions (PDF pp.4–5). -/
def tensorRowSum {n : ℕ} (F : Tensor n 2) (i : Fin n) : ℝ := ∑ j, F ![i,j]

def colSum {n : ℕ} (F : Tensor n 2) (i : Fin n) : ℝ := ∑ j, F ![j,i]

def totalSum {n : ℕ} (F : Tensor n 2) : ℝ := ∑ i, ∑ j, F ![i,j]

def activationTraceSum {n : ℕ} (F : Tensor n 2) : ℝ := ∑ i, F ![i,i]

/-- Theorem 2's seven terms, evaluated only off the diagonal (PDF p.4). -/
def sevenFormula {n : ℕ} (w : Fin 7 → ℝ) (F : Tensor n 2) (i j : Fin n) : ℝ :=
  w 0 * F ![i,j] + w 1 * F ![j,i] + w 2 * tensorRowSum F i + w 3 * colSum F i +
    w 4 * colSum F j + w 5 * tensorRowSum F j + w 6 * totalSum F

/-- Corollary 4's fifteen terms, including the trace overbars (PDF p.5). -/
def fifteenFormula {n : ℕ} (w : Fin 15 → ℝ) (F : Tensor n 2) (i j : Fin n) : ℝ :=
  w 0 * F ![i,j] + w 1 * F ![j,i] + w 2 * tensorRowSum F i + w 3 * colSum F i +
    w 4 * colSum F j + w 5 * tensorRowSum F j + w 6 * totalSum F + w 7 * activationTraceSum F +
    w 8 * F ![i,i] + w 9 * F ![j,j] +
    if i = j then w 10 * F ![i,i] + w 11 * activationTraceSum F + w 12 * totalSum F +
      w 13 * tensorRowSum F i + w 14 * colSum F i else 0

example {n : ℕ} (F : Tensor n 2) (i : Fin n) : tensorRowSum F i = ∑ j, F ![i,j] := rfl

/-- A real irreducible model means a nonzero representation with no proper,
nonzero invariant real linear subspace (PDF p.4). -/
def IsRealIrreducible {n d : ℕ}
    (rho : Perm n →* Module.End ℝ (Fin d → ℝ)) : Prop :=
  0 < d ∧ ∀ S : Submodule ℝ (Fin d → ℝ),
    (∀ s x, x ∈ S → rho s x ∈ S) → S = ⊥ ∨ S = ⊤

/-- Models are inequivalent if no invertible intertwiner exists (PDF p.4). -/
def ModelsInequivalent {n d e : ℕ}
    (rho : Perm n →* Module.End ℝ (Fin d → ℝ))
    (eta : Perm n →* Module.End ℝ (Fin e → ℝ)) : Prop :=
  ¬ ∃ U : (Fin d → ℝ) ≃ₗ[ℝ] (Fin e → ℝ), ∀ s x, U (rho s x) = eta s (U x)

abbrev FourierBlocks {I : Type*} (d tau : I → ℕ) :=
  (a : I) → Matrix (Fin (d a)) (Fin (tau a)) ℝ

/-- Each column is acted on by the same irreducible model (PDF p.4). -/
def fourierColumnAction {n : ℕ} {I : Type*} {d tau : I → ℕ}
    (rho : (a : I) → Perm n →* Module.End ℝ (Fin (d a) → ℝ))
    (s : Perm n) (F : FourierBlocks d tau) : FourierBlocks d tau :=
  fun a r c => rho a s (fun b => F a b c) r

abbrev FourierWeights {I : Type*} (tau upsilon : I → ℕ) :=
  (a : I) → Matrix (Fin (tau a)) (Fin (upsilon a)) ℝ

/-- Fourier-space right multiplication; source PDF p.4, Theorem 3. -/
def applyBlocks {I : Type*} {d tau upsilon : I → ℕ}
    (w : FourierWeights tau upsilon) (F : FourierBlocks d tau) : FourierBlocks d upsilon :=
  fun a => F a * w a

example {I : Type*} {d tau upsilon : I → ℕ} (F : FourierBlocks d tau)
    (w : FourierWeights tau upsilon) (a : I) : applyBlocks w F a = F a * w a := rfl

/-- The subgroup fixing the final k points individually, PDF p.12.
The embedding is typed and the natural subtraction is protected by k≤n. -/
def finalPoints {n k : ℕ} (hkn : k ≤ n) : Fin k ↪ Fin n where
  toFun a := ⟨n - 1 - a.val, by omega⟩
  inj' := by intro a b h; apply Fin.ext; have := congrArg Fin.val h; dsimp at this; omega

def pointStabilizer {n k : ℕ} (e : Fin k ↪ Fin n) : Subgroup (Perm n) where
  carrier := {s | ∀ a, s (e a) = e a}
  one_mem' := by intro a; rfl
  mul_mem' := by intro s t hs ht a; change s (t (e a)) = e a; rw [ht, hs]
  inv_mem' := by
    intro s hs a
    apply s.injective
    simpa using (hs a).symm

abbrev Cosets {n k : ℕ} (e : Fin k ↪ Fin n) :=
  Quotient (QuotientGroup.leftRel (pointStabilizer e))

/-- Representative formula with well-definedness asserted by Propositions 5–7;
choosing out does not assume the desired bijection or intertwining conclusion. -/
def quotientValues {n k : ℕ} (e : Fin k ↪ Fin n) (F : Tensor n k) : Cosets e → ℝ :=
  fun q => F (fun a => q.out (e a))

def cosetTranslate {n k : ℕ} (e : Fin k ↪ Fin n) (s : Perm n) (q : Cosets e) : Cosets e :=
  Quotient.mk _ (s * q.out)

def vectorValues {n : ℕ} (hn : 1 ≤ n) (f : Fin n → ℝ) :
    Cosets (finalPoints hn) → ℝ :=
  quotientValues (finalPoints hn) (fun t => f (t 0))

example {n k : ℕ} (e : Fin k ↪ Fin n) : (1 : Perm n) ∈ pointStabilizer e :=
  (pointStabilizer e).one_mem

/-- Real Young symmetrizer: same concrete row/column permutation sets as the
accepted Specht construction, with real scalars as required by PDF p.4. -/
def realYoung {n : ℕ} (lambda : QAlgorithms.Schur.Partition n n) :
    Matrix (Perm n) (Perm n) ℝ := fun g h =>
  ∑ a ∈ QAlgorithms.Schur.rowPermutations lambda,
    ∑ b ∈ QAlgorithms.Schur.columnPermutations lambda,
      if g = h * a * b then (((Equiv.Perm.sign b : ℤˣ) : ℤ) : ℝ) else 0

def realSpecht {n : ℕ} (lambda : QAlgorithms.Schur.Partition n n) :
    Submodule ℝ (Perm n → ℝ) := LinearMap.range (Matrix.toLin' (realYoung lambda))

/-- An actual equivariant isomorphism to copies of concrete real Specht ideals.
The group acts by left translation inside each ideal. No Fourier coordinates
or multiplicities are assumed as an input field (PDF p.4). -/
def HasTensorType {n k r : ℕ} (S : Submodule ℝ (Tensor n k))
    (lambda : Fin r → QAlgorithms.Schur.Partition n n) (tau : Fin r → ℕ) : Prop :=
  ∃ U : S ≃ₗ[ℝ] ((a : Fin r) → Fin (tau a) → realSpecht (lambda a)),
    ∀ (s : Perm n) (F : S), ∃ G : S,
      G.val = permutationTensorAction s F.val ∧
      ∀ a c g, (U G a c).val g = (U F a c).val (s.symm * g)

/-- Printed partition order, source PDF p.4. -/
def secondShapes (n : ℕ) : Fin 4 → List ℕ := ![[n], [n-1,1], [n-2,2], [n-2,1,1]]

def thirdShapes (n : ℕ) : Fin 7 → List ℕ :=
  ![[n], [n-1,1], [n-2,2], [n-2,1,1], [n-3,3], [n-3,2,1], [n-3,1,1,1]]

example {n : ℕ} (lambda : QAlgorithms.Schur.Partition n n) :
    realSpecht lambda = LinearMap.range (Matrix.toLin' (realYoung lambda)) := rfl

/-- The three exactly-two-equal patterns are indexed by their singleton position. -/
def pairPattern {n : ℕ} (a : Fin 3) (t : Fin 3 → Fin n) : Prop :=
  t (a+1) = t (a+2) ∧ t a ≠ t (a+1)

/-- A contraction partitions the three input slots into equality blocks; each
block is named by its least slot. A selected subset of blocks is retained, and
the others are summed. This is precisely the four contraction lists on pp.15–16. -/
def IsRecipe (p : (Fin 3 → Fin 3) × Finset (Fin 3)) : Prop :=
  (∀ a, p.1 a ≤ a ∧ p.1 (p.1 a) = p.1 a) ∧ ∀ a ∈ p.2, p.1 a = a

example : IsRecipe ((id : Fin 3 → Fin 3), Finset.univ) := by simp [IsRecipe]

abbrev Recipe := {p : (Fin 3 → Fin 3) × Finset (Fin 3) // IsRecipe p}

abbrev Retained (p : Recipe) := {a : Fin 3 // a ∈ p.val.2}

/-- Every injection of the retained slots into the available output slots is used. -/
abbrev PlacedRecipe (r : ℕ) := Σ p : Recipe, (Retained p ↪ Fin r)

/-- Coefficient kernel for one contraction: equal input indices within a block,
retained blocks fixed to the selected output entries; other blocks summed freely.
Distinct blocks are not required to receive distinct vertex labels. -/
def contractionKernel {n r : ℕ} (p : PlacedRecipe r)
    (t : Fin r → Fin n) (u : Fin 3 → Fin n) : ℝ :=
  if (∀ a b, p.1.val.1 a = p.1.val.1 b → u a = u b) ∧
      (∀ a : Retained p.1, u a.val = t (p.2 a)) then 1 else 0

/-- 77 generic terms, three sets of 37 pair-supported corrections, and 15
all-diagonal corrections (PDF p.16, Table 4). -/
abbrev ThirdIndex := PlacedRecipe 3 ⊕ ((Fin 3 × PlacedRecipe 2) ⊕ PlacedRecipe 1)

/-- Equality-supported corrections are added to the generic formula. The pair
index names the singleton output slot; Fin 3 addition is cyclic. -/
def thirdKernel {n : ℕ} (p : ThirdIndex) (t u : Fin 3 → Fin n) : ℝ :=
  match p with
  | .inl q => contractionKernel q t u
  | .inr (.inl (a,q)) =>
    if t (a+1) = t (a+2) then contractionKernel q ![t (a+1),t a] u else 0
  | .inr (.inr q) =>
    if ∀ a b, t a = t b then contractionKernel q ![t 0] u else 0

/-- Concrete weighted contraction construction, source PDF pp.15–16. -/
def thirdFormula {n : ℕ} (w : ThirdIndex → ℝ) (F : Tensor n 3) : Tensor n 3 :=
  fun t => ∑ p : ThirdIndex, w p * ∑ u : Fin 3 → Fin n, thirdKernel p t u * F u

example {n : ℕ} (F : Tensor n 3) : thirdFormula (fun _ => 0) F = 0 := by
  ext t
  simp [thirdFormula]

/-- Zero-extension promotion along an injective correspondence, PDF p.6, Eq.(6).
Off-image values are explicitly zero; overlapping children add their contributions. -/
def promote {m n k : ℕ} (chi : Fin m ↪ Fin n) (F : Tensor m k) : Tensor n k :=
  fun t => ∑ u : Fin k → Fin m, if (fun a => chi (u a)) = t then F u else 0

/-- The correspondence itself is relabelled, not held fixed (PDF pp.5–6). -/
def relabelEmbedding {m n : ℕ} (chi : Fin m ↪ Fin n) (s : Perm n) (p : Perm m) :
    Fin m ↪ Fin n where
  toFun i := s (chi (p.symm i))
  inj' := s.injective.comp (chi.injective.comp p.symm.injective)

/-- Outer product permits higher tensor order; no contraction or bias is implicit. -/
def tensorOuterProduct {n k l : ℕ} (F : Tensor n k) (G : Tensor n l) :
    ((Fin k ⊕ Fin l) → Fin n) → ℝ :=
  fun t => F (fun a => t (.inl a)) * G (fun b => t (.inr b))

example {m n : ℕ} (chi : Fin m ↪ Fin n) (s : Perm n) (p : Perm m) (i : Fin m) :
    relabelEmbedding chi s p i = s (chi (p.symm i)) := rfl

end QAlgorithms.Papers.Independent.Intakenext100.P94
Source
The general theory of permutation equivarant neural networks and higher order graph variational encoders, arXiv:2004.03990v1, https://arxiv.org/abs/2004.03990v1
Read-back

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

QAlgorithms.Papers.Independent.Intakenext100.P94.Cosets

For all natural numbers n,kn,kn,k and every injection e:{0,…,k−1}↪{0,…,n−1}e:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}e:{0,…,k−1}↪{0,…,n−1}, this denotes the quotient of the permutation group SnS_nSn​ by the equivalence relation s∼ts\sim ts∼t if and only if s−1t∈Hes^{-1}t\in H_es−1t∈He​, where He={u∈Sn:∀a, u(e(a))=e(a)}H_e=\{u\in S_n:\forall a,\ u(e(a))=e(a)\}He​={u∈Sn​:∀a, u(e(a))=e(a)}. Its elements are therefore the left cosets sHesH_esHe​. If k=0k=0k=0, then He=SnH_e=S_nHe​=Sn​ and the quotient has one element, including when n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P94.DistinctSpace

For all natural numbers n,kn,kn,k, DistinctSpace(n,k)\mathrm{DistinctSpace}(n,k)DistinctSpace(n,k) is the real subspace of real-valued functions on tuples t:[k]→[n]t:[k]\to[n]t:[k]→[n], where [r]={0,…,r−1}[r]=\{0,\ldots,r-1\}[r]={0,…,r−1}, that vanish whenever ttt is not injective, meaning whenever two distinct tuple positions have the same index. Values on injective tuples are unrestricted. When k>nk>nk>n, every tuple is noninjective or there are no tuples, so this is the zero vector space. When k=0k=0k=0, the empty tuple is injective and the space is naturally identified with R\mathbb RR, including when n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P94.FourierBlocks

For any index type III and functions d,τ:I→Nd,\tau:I\to\mathbb Nd,τ:I→N, this abbreviation denotes the space of families F=(Fa)a∈IF=(F_a)_{a\in I}F=(Fa​)a∈I​ in which each FaF_aFa​ is a real matrix with d(a)d(a)d(a) rows and τ(a)\tau(a)τ(a) columns, indexed respectively by {0,…,d(a)−1}\{0,\ldots,d(a)-1\}{0,…,d(a)−1} and {0,…,τ(a)−1}\{0,\ldots,\tau(a)-1\}{0,…,τ(a)−1}. No finiteness assumption is imposed on III, and either matrix dimension may be zero. If III is empty, there is exactly one such family.

QAlgorithms.Papers.Independent.Intakenext100.P94.FourierWeights

For any index type III and functions τ,υ:I→N\tau,\upsilon:I\to\mathbb Nτ,υ:I→N, this abbreviation denotes the space of families w=(wa)a∈Iw=(w_a)_{a\in I}w=(wa​)a∈I​ of real matrices, where waw_awa​ has τ(a)\tau(a)τ(a) rows and υ(a)\upsilon(a)υ(a) columns, indexed respectively by {0,…,τ(a)−1}\{0,\ldots,\tau(a)-1\}{0,…,τ(a)−1} and {0,…,υ(a)−1}\{0,\ldots,\upsilon(a)-1\}{0,…,υ(a)−1}. The type III need not be finite, and zero matrix dimensions are allowed. If III is empty, there is exactly one such family.

QAlgorithms.Papers.Independent.Intakenext100.P94.HasTensorType

For all natural numbers n,k,rn,k,rn,k,r, every real vector subspace SSS of the functions on tuples t:{0,…,k−1}→{0,…,n−1}t:\{0,\ldots,k-1\}\to\{0,\ldots,n-1\}t:{0,…,k−1}→{0,…,n−1}, every family (λa)a<r(\lambda_a)_{a<r}(λa​)a<r​ of Young diagrams each having exactly nnn cells and first-column length at most nnn, and every family of natural numbers (τa)a<r(\tau_a)_{a<r}(τa​)a<r​, this defines the following proposition. For each aaa, use the cell-numbering bijection supplied by the finite-cardinality construction to define the permutations RaR_aRa​ preserving each numbered cell's row and the permutations CaC_aCa​ preserving each numbered cell's column; let Va⊆RSnV_a\subseteq\mathbb R^{S_n}Va​⊆RSn​ be the image of the matrix Ya(g,h)=∑u∈Ra∑v∈Ca1{g=huv}sgn⁡(v)Y_a(g,h)=\sum_{u\in R_a}\sum_{v\in C_a}\mathbf 1_{\{g=huv\}}\operatorname{sgn}(v)Ya​(g,h)=∑u∈Ra​​∑v∈Ca​​1{g=huv}​sgn(v). There exists a real linear isomorphism U:S→∏a<r∏c<τaVaU:S\to\prod_{a<r}\prod_{c<\tau_a}V_aU:S→∏a<r​∏c<τa​​Va​ such that, for every permutation s∈Sns\in S_ns∈Sn​ and every F∈SF\in SF∈S, there exists G∈SG\in SG∈S satisfying G(t)=F(b↦s−1(t(b)))G(t)=F(b\mapsto s^{-1}(t(b)))G(t)=F(b↦s−1(t(b))) for every tuple ttt, and satisfying (UG)a,c(g)=(UF)a,c(s−1g)(UG)_{a,c}(g)=(UF)_{a,c}(s^{-1}g)(UG)a,c​(g)=(UF)a,c​(s−1g) for every a<ra<ra<r, c<τac<\tau_ac<τa​, and g∈Sng\in S_ng∈Sn​. There are no positivity assumptions on n,k,rn,k,rn,k,r or the τa\tau_aτa​; empty index sets are included, and if r=0r=0r=0 or every τa=0\tau_a=0τa​=0, the target of the required isomorphism is the zero vector space.

QAlgorithms.Papers.Independent.Intakenext100.P94.IsRealIrreducible

For natural numbers n,dn,dn,d and a representation ρ\rhoρ of the permutation group of {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} on Rd\mathbb R^dRd, meaning a map into real-linear endomorphisms that preserves identity and multiplication, this predicate means that d>0d>0d>0 and that every real-linear subspace S⊆RdS\subseteq\mathbb R^dS⊆Rd satisfying

∀s, ∀x∈S,ρ(s)x∈S\forall s,\ \forall x\in S,\quad \rho(s)x\in S∀s, ∀x∈S,ρ(s)x∈S

is either {0}\{0\}{0} or all of Rd\mathbb R^dRd. The parameter nnn may be zero; dimension d=0d=0d=0 makes the predicate false.

QAlgorithms.Papers.Independent.Intakenext100.P94.IsRecipe

For a pair p=(f,A)p=(f,A)p=(f,A), where f:{0,1,2}→{0,1,2}f:\{0,1,2\}\to\{0,1,2\}f:{0,1,2}→{0,1,2} is a function and A⊆{0,1,2}A\subseteq\{0,1,2\}A⊆{0,1,2} is a finite set, this predicate requires that f(a)≤af(a)\le af(a)≤a and f(f(a))=f(a)f(f(a))=f(a)f(f(a))=f(a) for every a∈{0,1,2}a\in\{0,1,2\}a∈{0,1,2}, and that f(a)=af(a)=af(a)=a for every a∈Aa\in Aa∈A. The order is the usual order 0<1<20<1<20<1<2. The set AAA may be empty and need not contain every fixed point of fff.

QAlgorithms.Papers.Independent.Intakenext100.P94.ModelsInequivalent

For natural numbers n,d,en,d,en,d,e and representations ρ\rhoρ and η\etaη of the permutation group of {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} on Rd\mathbb R^dRd and Re\mathbb R^eRe, respectively, each preserving identity and multiplication as a map into real-linear endomorphisms, this predicate means that there is no real-linear isomorphism U:Rd→ReU:\mathbb R^d\to\mathbb R^eU:Rd→Re satisfying

∀s, ∀x∈Rd,U(ρ(s)x)=η(s)(Ux).\forall s,\ \forall x\in\mathbb R^d,\quad U(\rho(s)x)=\eta(s)(Ux).∀s, ∀x∈Rd,U(ρ(s)x)=η(s)(Ux).

No irreducibility or positivity assumptions are imposed on the dimensions; n,d,en,d,en,d,e may be zero. In particular, when d=e=0d=e=0d=e=0, the unique linear isomorphism satisfies the displayed condition, so this predicate is false.

QAlgorithms.Papers.Independent.Intakenext100.P94.Perm

For every natural number nnn, Perm(n)\mathrm{Perm}(n)Perm(n) denotes the permutations of the set [n]={0,…,n−1}[n]=\{0,\ldots,n-1\}[n]={0,…,n−1}, meaning its bijections to itself. This includes n=0n=0n=0, when [n][n][n] is empty and has exactly one permutation.

QAlgorithms.Papers.Independent.Intakenext100.P94.PlacedRecipe

For every natural number rrr, this is the type of data (f,A,e)(f,A,e)(f,A,e), where f:{0,1,2}→{0,1,2}f:\{0,1,2\}\to\{0,1,2\}f:{0,1,2}→{0,1,2} satisfies f(a)≤af(a)\le af(a)≤a and f(f(a))=f(a)f(f(a))=f(a)f(f(a))=f(a) for every aaa, A⊆{0,1,2}A\subseteq\{0,1,2\}A⊆{0,1,2} is a finite set satisfying f(a)=af(a)=af(a)=a for every a∈Aa\in Aa∈A, and e:A→{0,…,r−1}e:A\to\{0,\ldots,r-1\}e:A→{0,…,r−1} is injective. The set AAA may be empty. When r=0r=0r=0, it must be empty; in general, injectivity requires ∣A∣≤r|A|\le r∣A∣≤r.

QAlgorithms.Papers.Independent.Intakenext100.P94.Recipe

This is the type of pairs (f,A)(f,A)(f,A), where f:{0,1,2}→{0,1,2}f:\{0,1,2\}\to\{0,1,2\}f:{0,1,2}→{0,1,2} and A⊆{0,1,2}A\subseteq\{0,1,2\}A⊆{0,1,2} is a finite set, satisfying f(a)≤af(a)\le af(a)≤a and f(f(a))=f(a)f(f(a))=f(a)f(f(a))=f(a) for every aaa, and f(a)=af(a)=af(a)=a for every a∈Aa\in Aa∈A. Thus the data include a function with these order and idempotence conditions and a possibly empty chosen subset of its fixed points.

QAlgorithms.Papers.Independent.Intakenext100.P94.Retained

For a pair p=(f,A)p=(f,A)p=(f,A) with f:{0,1,2}→{0,1,2}f:\{0,1,2\}\to\{0,1,2\}f:{0,1,2}→{0,1,2}, f(a)≤af(a)\le af(a)≤a, f(f(a))=f(a)f(f(a))=f(a)f(f(a))=f(a) for every aaa, and AAA a finite subset of the fixed points of fff, this is the type whose elements are precisely the indices a∈Aa\in Aa∈A. It is empty when AAA is empty.

QAlgorithms.Papers.Independent.Intakenext100.P94.Tensor

For all natural numbers nnn and kkk, Tensor(n,k)\mathrm{Tensor}(n,k)Tensor(n,k) is the real vector space of all real-valued functions on the set of functions [k]→[n][k]\to[n][k]→[n], where [r]={0,…,r−1}[r]=\{0,\ldots,r-1\}[r]={0,…,r−1}. Thus a tensor assigns a real number to every ordered kkk-tuple of indices in [n][n][n], with repetitions allowed. When k=0k=0k=0, there is one empty tuple, so this space is naturally identified with R\mathbb RR, including when n=0n=0n=0. When n=0n=0n=0 and k>0k>0k>0, there are no such tuples, so the space consists only of the zero function.

QAlgorithms.Papers.Independent.Intakenext100.P94.ThirdIndex

For r∈{1,2,3}r\in\{1,2,3\}r∈{1,2,3}, let PrP_rPr​ be the type of triples (f,A,e)(f,A,e)(f,A,e), where f:{0,1,2}→{0,1,2}f:\{0,1,2\}\to\{0,1,2\}f:{0,1,2}→{0,1,2} satisfies f(a)≤af(a)\le af(a)≤a and f(f(a))=f(a)f(f(a))=f(a)f(f(a))=f(a) for every aaa, AAA is a finite subset of the fixed points of fff, and e:A→{0,…,r−1}e:A\to\{0,\ldots,r-1\}e:A→{0,…,r−1} is injective. This defines the disjoint union

P3 ⊔ (({0,1,2}×P2) ⊔ P1).P_3\ \sqcup\ \bigl((\{0,1,2\}\times P_2)\ \sqcup\ P_1\bigr).P3​ ⊔ (({0,1,2}×P2​) ⊔ P1​).

Its elements therefore carry a tag specifying either data from P3P_3P3​, a chosen index a∈{0,1,2}a\in\{0,1,2\}a∈{0,1,2} together with data from P2P_2P2​, or data from P1P_1P1​. In each case AAA may be empty; the tags distinguish elements from different summands even when their other data agree.

QAlgorithms.Papers.Independent.Intakenext100.P94.activationTraceSum

For every natural number nnn and every real-valued function FFF on ordered pairs from [n]={0,…,n−1}[n]=\{0,\ldots,n-1\}[n]={0,…,n−1}, this defines the real number ∑i∈[n]F(i,i)\sum_{i\in[n]}F(i,i)∑i∈[n]​F(i,i), the sum of its values on tuples with equal coordinates. When n=0n=0n=0, the sum is empty and equals zero.

QAlgorithms.Papers.Independent.Intakenext100.P94.applyBlocks

For any index type III, functions d,τ,υ:I→Nd,\tau,\upsilon:I\to\mathbb Nd,τ,υ:I→N, a family www of real τ(a)×υ(a)\tau(a)\times\upsilon(a)τ(a)×υ(a) matrices, and a family FFF of real d(a)×τ(a)d(a)\times\tau(a)d(a)×τ(a) matrices, this definition returns the family of real d(a)×υ(a)d(a)\times\upsilon(a)d(a)×υ(a) matrices given by right multiplication in each block:

(applyBlocks⁡(w,F))a=Fawa,(applyBlocks⁡(w,F))a(r,c)=∑b=0τ(a)−1Fa(r,b)wa(b,c).\bigl(\operatorname{applyBlocks}(w,F)\bigr)_a=F_aw_a, \qquad \bigl(\operatorname{applyBlocks}(w,F)\bigr)_a(r,c) =\sum_{b=0}^{\tau(a)-1}F_a(r,b)w_a(b,c).(applyBlocks(w,F))a​=Fa​wa​,(applyBlocks(w,F))a​(r,c)=b=0∑τ(a)−1​Fa​(r,b)wa​(b,c).

No finiteness assumption is imposed on III, and all dimensions may be zero. When τ(a)=0\tau(a)=0τ(a)=0, the displayed sum is empty and every output entry in that block is zero.

QAlgorithms.Papers.Independent.Intakenext100.P94.colSum

For every natural number nnn, every real-valued function FFF on ordered pairs from [n]={0,…,n−1}[n]=\{0,\ldots,n-1\}[n]={0,…,n−1}, and every i∈[n]i\in[n]i∈[n], this defines the real number ∑j∈[n]F(j,i)\sum_{j\in[n]}F(j,i)∑j∈[n]​F(j,i), where F(j,i)F(j,i)F(j,i) denotes evaluation at the tuple whose first coordinate is jjj and second coordinate is iii. For n=0n=0n=0, there is no index iii to supply.

QAlgorithms.Papers.Independent.Intakenext100.P94.contractionKernel

For any natural numbers n,rn,rn,r, let p=(f,A,e)p=(f,A,e)p=(f,A,e), where f:{0,1,2}→{0,1,2}f:\{0,1,2\}\to\{0,1,2\}f:{0,1,2}→{0,1,2} satisfies f(a)≤af(a)\le af(a)≤a and f(f(a))=f(a)f(f(a))=f(a)f(f(a))=f(a) for every aaa, AAA is a finite subset of its fixed points, and e:A→{0,…,r−1}e:A\to\{0,\ldots,r-1\}e:A→{0,…,r−1} is injective. For tuples t:{0,…,r−1}→{0,…,n−1}t:\{0,\ldots,r-1\}\to\{0,\ldots,n-1\}t:{0,…,r−1}→{0,…,n−1} and u:{0,1,2}→{0,…,n−1}u:\{0,1,2\}\to\{0,\ldots,n-1\}u:{0,1,2}→{0,…,n−1}, this defines the real number 111 exactly when both conditions hold:

∀a,b∈{0,1,2},f(a)=f(b) ⟹ ua=ub,∀a∈A,ua=te(a);\forall a,b\in\{0,1,2\},\quad f(a)=f(b)\ \Longrightarrow\ u_a=u_b, \qquad \forall a\in A,\quad u_a=t_{e(a)};∀a,b∈{0,1,2},f(a)=f(b) ⟹ ua​=ub​,∀a∈A,ua​=te(a)​;

otherwise it defines 000. There is no requirement that different values of fff give different entries of uuu. If AAA is empty, the second condition is vacuous; if r=0r=0r=0, AAA must be empty and ttt is the empty tuple. If n=0n=0n=0, there is no possible triple uuu.

QAlgorithms.Papers.Independent.Intakenext100.P94.cosetTranslate

For all natural numbers n,kn,kn,k, every injection e:{0,…,k−1}↪{0,…,n−1}e:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}e:{0,…,k−1}↪{0,…,n−1}, every permutation s∈Sns\in S_ns∈Sn​, and every left coset qqq of He={u∈Sn:∀a, u(e(a))=e(a)}H_e=\{u\in S_n:\forall a,\ u(e(a))=e(a)\}He​={u∈Sn​:∀a, u(e(a))=e(a)}, this defines a coset by taking the equivalence class of srqs r_qsrq​, where rqr_qrq​ is the chosen representative of qqq and permutation multiplication is composition. Thus the resulting coset is (srq)He(s r_q)H_e(srq​)He​. If k=0k=0k=0, the quotient has one element and this operation returns that element.

QAlgorithms.Papers.Independent.Intakenext100.P94.distinctAction

For all natural numbers n,kn,kn,k and every permutation sss of [n]={0,…,n−1}[n]=\{0,\ldots,n-1\}[n]={0,…,n−1}, this defines a real-linear map on the space of real-valued functions FFF on tuples t:[k]→[n]t:[k]\to[n]t:[k]→[n] that vanish on noninjective tuples. Its value is the function

(s⋅F)(t)=F(a↦s−1(t(a))),(s\cdot F)(t)=F\bigl(a\mapsto s^{-1}(t(a))\bigr),(s⋅F)(t)=F(a↦s−1(t(a))),

which also vanishes on noninjective tuples. When k=0k=0k=0, this map fixes every function on the single empty tuple; when k>nk>nk>n, it acts on the zero vector space.

QAlgorithms.Papers.Independent.Intakenext100.P94.equivariantLinearMaps

For any types G,E,HG,E,HG,E,H, where EEE and HHH are additive commutative groups equipped with real module structures, and any families of real-linear endomorphisms As:E→EA_s:E\to EAs​:E→E and Bs:H→HB_s:H\to HBs​:H→H indexed by s∈Gs\in Gs∈G, this defines the real subspace of real-linear maps L:E→HL:E\to HL:E→H satisfying

∀s∈G  ∀x∈E,L(As(x))=Bs(L(x)).\forall s\in G\;\forall x\in E,\qquad L(A_s(x))=B_s(L(x)).∀s∈G∀x∈E,L(As​(x))=Bs​(L(x)).

No group structure on GGG or action laws for either family are assumed. If GGG is empty, the condition is vacuous and the subspace contains every real-linear map E→HE\to HE→H.

QAlgorithms.Papers.Independent.Intakenext100.P94.fifteenFormula

For any natural number nnn, fifteen real weights w0,…,w14w_0,\ldots,w_{14}w0​,…,w14​, a real tensor FFF indexed by functions {0,1}→{0,…,n−1}\{0,1\}\to\{0,\ldots,n-1\}{0,1}→{0,…,n−1}, and indices i,j∈{0,…,n−1}i,j\in\{0,\ldots,n-1\}i,j∈{0,…,n−1}, write FijF_{ij}Fij​ for its value on the function with values i,ji,ji,j in that order. The definition assigns

w0Fij+w1Fji+w2∑bFib+w3∑aFai+w4∑aFaj+w5∑bFjb+w6∑a,bFab+w7∑aFaa+w8Fii+w9Fjj+{w10Fii+w11∑aFaa+w12∑a,bFab+w13∑bFib+w14∑aFai,i=j,0,i≠j.\begin{aligned} &w_0F_{ij}+w_1F_{ji} +w_2\sum_bF_{ib}+w_3\sum_aF_{ai} +w_4\sum_aF_{aj}+w_5\sum_bF_{jb} +w_6\sum_{a,b}F_{ab} +w_7\sum_aF_{aa} +w_8F_{ii}+w_9F_{jj}\\ &\qquad+ \begin{cases} w_{10}F_{ii}+w_{11}\sum_aF_{aa}+w_{12}\sum_{a,b}F_{ab} +w_{13}\sum_bF_{ib}+w_{14}\sum_aF_{ai},&i=j,\\ 0,&i\ne j. \end{cases} \end{aligned}​w0​Fij​+w1​Fji​+w2​b∑​Fib​+w3​a∑​Fai​+w4​a∑​Faj​+w5​b∑​Fjb​+w6​a,b∑​Fab​+w7​a∑​Faa​+w8​Fii​+w9​Fjj​+{w10​Fii​+w11​∑a​Faa​+w12​∑a,b​Fab​+w13​∑b​Fib​+w14​∑a​Fai​,0,​i=j,i=j.​​

Every summation index ranges over {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1}. No condition is imposed on FFF or on whether i=ji=ji=j. The case n=0n=0n=0 is allowed, but supplies no indices i,ji,ji,j.

QAlgorithms.Papers.Independent.Intakenext100.P94.finalPoints

For all natural numbers n,kn,kn,k and a hypothesis k≤nk\le nk≤n, this defines an injection e:{0,…,k−1}↪{0,…,n−1}e:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}e:{0,…,k−1}↪{0,…,n−1} by e(a)=n−1−ae(a)=n-1-ae(a)=n−1−a, where subtraction is natural-number subtraction, truncated at zero. Thus the indices are sent, in order, to n−1,n−2,…,n−kn-1,n-2,\ldots,n-kn−1,n−2,…,n−k. When k=0k=0k=0, including when n=0n=0n=0, this is the empty injection.

QAlgorithms.Papers.Independent.Intakenext100.P94.fourierColumnAction

For any natural number nnn, any index type III, any functions d,τ:I→Nd,\tau:I\to\mathbb Nd,τ:I→N, a family of representations ρa\rho_aρa​ of the permutation group of {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} on Rd(a)\mathbb R^{d(a)}Rd(a), a permutation sss of that set, and a family FFF of real d(a)×τ(a)d(a)\times\tau(a)d(a)×τ(a) matrices, this definition returns the family of matrices whose entries are

(s⋅F)a(r,c)=[ρa(s)(b↦Fa(b,c))]r.(s\cdot F)_a(r,c) =\left[\rho_a(s)\bigl(b\mapsto F_a(b,c)\bigr)\right]_r.(s⋅F)a​(r,c)=[ρa​(s)(b↦Fa​(b,c))]r​.

Thus ρa(s)\rho_a(s)ρa​(s) is applied separately to each column of FaF_aFa​. Each representation preserves identity and multiplication as a map into real-linear endomorphisms; no irreducibility assumption is made. The type III need not be finite, nnn may be zero, and zero row or column dimensions are allowed, with no entries to specify in those blocks.

QAlgorithms.Papers.Independent.Intakenext100.P94.pairPattern

For any natural number nnn, any index a∈{0,1,2}a\in\{0,1,2\}a∈{0,1,2}, and any triple t:{0,1,2}→{0,…,n−1}t:\{0,1,2\}\to\{0,\ldots,n-1\}t:{0,1,2}→{0,…,n−1}, this predicate says that

ta+1=ta+2andta≠ta+1,t_{a+1}=t_{a+2}\quad\text{and}\quad t_a\ne t_{a+1},ta+1​=ta+2​andta​=ta+1​,

where the index additions are taken modulo 333. Thus the two positions other than aaa have equal entries, and position aaa has a different entry. For n=0n=0n=0 there are no such triples, and for n=1n=1n=1 no triple satisfies the predicate.

QAlgorithms.Papers.Independent.Intakenext100.P94.permutationTensorAction

For all natural numbers n,kn,kn,k and every permutation sss of [n]={0,…,n−1}[n]=\{0,\ldots,n-1\}[n]={0,…,n−1}, this defines the real-linear map on real-valued functions FFF on the tuples t:[k]→[n]t:[k]\to[n]t:[k]→[n] given by

(s⋅F)(t)=F(a↦s−1(t(a))).(s\cdot F)(t)=F\bigl(a\mapsto s^{-1}(t(a))\bigr).(s⋅F)(t)=F(a↦s−1(t(a))).

When k=0k=0k=0, this map fixes every function on the single empty tuple. When n=0n=0n=0 and k>0k>0k>0, its domain and codomain are the zero vector space.

QAlgorithms.Papers.Independent.Intakenext100.P94.pointStabilizer

For all natural numbers n,kn,kn,k and every injection e:{0,…,k−1}↪{0,…,n−1}e:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}e:{0,…,k−1}↪{0,…,n−1}, this defines the subgroup HeH_eHe​ of the permutation group SnS_nSn​ consisting exactly of those permutations sss satisfying s(e(a))=e(a)s(e(a))=e(a)s(e(a))=e(a) for every a∈{0,…,k−1}a\in\{0,\ldots,k-1\}a∈{0,…,k−1}. These permutations fix each point in the image of eee individually. If k=0k=0k=0, the condition is vacuous and He=SnH_e=S_nHe​=Sn​, also when n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P94.pointwise

For all natural numbers n,kn,kn,k, any function ξ:R→R\xi:\mathbb R\to\mathbb Rξ:R→R, and any real-valued function FFF on tuples t:[k]→[n]t:[k]\to[n]t:[k]→[n], where [r]={0,…,r−1}[r]=\{0,\ldots,r-1\}[r]={0,…,r−1}, this defines the function t↦ξ(F(t))t\mapsto\xi(F(t))t↦ξ(F(t)). No linearity or other condition is imposed on ξ\xiξ. When k=0k=0k=0, it applies ξ\xiξ to the value at the single empty tuple; when n=0n=0n=0 and k>0k>0k>0, the result is the unique function on the empty tuple set.

QAlgorithms.Papers.Independent.Intakenext100.P94.promote

For arbitrary natural numbers m,n,km,n,km,n,k, an injection χ:[m]↪[n]\chi:[m]\hookrightarrow[n]χ:[m]↪[n], and any real tensor F:([k]→[m])→RF:([k]\to[m])\to\mathbb RF:([k]→[m])→R, where [r]={0,…,r−1}[r]=\{0,\ldots,r-1\}[r]={0,…,r−1}, the definition produces a tensor on [n][n][n] by

promote⁡χ(F)(t)=∑u:[k]→[m]{F(u),χ∘u=t,0,χ∘u≠t.\operatorname{promote}_{\chi}(F)(t) =\sum_{u:[k]\to[m]} \begin{cases} F(u),&\chi\circ u=t,\\ 0,&\chi\circ u\ne t. \end{cases}promoteχ​(F)(t)=u:[k]→[m]∑​{F(u),0,​χ∘u=t,χ∘u=t.​

Because χ\chiχ is injective, this is F(u)F(u)F(u) for the unique matching tuple uuu, if one exists, and 000 if none exists. All three parameters may be zero, subject to the existence of χ\chiχ; when k=0k=0k=0, there is exactly one empty tuple in each tuple space and its scalar value is preserved, while any sum over an empty tuple space is 000.

QAlgorithms.Papers.Independent.Intakenext100.P94.quotientValues

For all natural numbers n,kn,kn,k, every injection e:{0,…,k−1}↪{0,…,n−1}e:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,n-1\}e:{0,…,k−1}↪{0,…,n−1}, and every real-valued function FFF on the set of tuples t:{0,…,k−1}→{0,…,n−1}t:\{0,\ldots,k-1\}\to\{0,\ldots,n-1\}t:{0,…,k−1}→{0,…,n−1}, this defines a real-valued function on the left cosets of He={s∈Sn:∀a, s(e(a))=e(a)}H_e=\{s\in S_n:\forall a,\ s(e(a))=e(a)\}He​={s∈Sn​:∀a, s(e(a))=e(a)} by assigning to a coset qqq the value F(a↦rq(e(a)))F(a\mapsto r_q(e(a)))F(a↦rq​(e(a))), where rq∈Snr_q\in S_nrq​∈Sn​ is the chosen representative of qqq supplied by the quotient representative operation. No support or invariance hypothesis on FFF is required. If k=0k=0k=0, the result is the constant value of FFF at the unique empty tuple.

QAlgorithms.Papers.Independent.Intakenext100.P94.realSpecht

For every natural number nnn and every Young diagram λ\lambdaλ with exactly nnn cells and first-column length at most nnn, this defines a real vector subspace of the functions Sn→RS_n\to\mathbb RSn​→R. Using the cell-numbering bijection c:cells⁡(λ)→{0,…,n−1}c:\operatorname{cells}(\lambda)\to\{0,\ldots,n-1\}c:cells(λ)→{0,…,n−1} supplied by the finite-cardinality construction, let RλR_\lambdaRλ​ and CλC_\lambdaCλ​ be the permutations preserving, respectively, the row and column coordinates of every numbered cell, and set Yλ(g,h)=∑a∈Rλ∑b∈Cλ1{g=hab}sgn⁡(b)Y_\lambda(g,h)=\sum_{a\in R_\lambda}\sum_{b\in C_\lambda}\mathbf 1_{\{g=hab\}}\operatorname{sgn}(b)Yλ​(g,h)=∑a∈Rλ​​∑b∈Cλ​​1{g=hab}​sgn(b). The defined subspace consists exactly of the functions vvv for which there exists a function w:Sn→Rw:S_n\to\mathbb Rw:Sn​→R satisfying v(g)=∑h∈SnYλ(g,h)w(h)v(g)=\sum_{h\in S_n}Y_\lambda(g,h)w(h)v(g)=∑h∈Sn​​Yλ​(g,h)w(h) for every g∈Sng\in S_ng∈Sn​. The definition also applies when n=0n=0n=0.

QAlgorithms.Papers.Independent.Intakenext100.P94.realYoung

For every natural number nnn and every Young diagram λ\lambdaλ with exactly nnn cells and first-column length at most nnn, this defines a real matrix YλY_\lambdaYλ​ with rows and columns indexed by SnS_nSn​. Choose the cell-numbering bijection c:cells⁡(λ)→{0,…,n−1}c:\operatorname{cells}(\lambda)\to\{0,\ldots,n-1\}c:cells(λ)→{0,…,n−1} supplied by the finite-cardinality construction; let RλR_\lambdaRλ​ consist of permutations aaa for which c−1(a(i))c^{-1}(a(i))c−1(a(i)) and c−1(i)c^{-1}(i)c−1(i) have the same row coordinate for every iii, and let CλC_\lambdaCλ​ consist of permutations bbb for which those cells have the same column coordinate for every iii. For every g,h∈Sng,h\in S_ng,h∈Sn​, the entry is Yλ(g,h)=∑a∈Rλ∑b∈Cλ1{g=hab}sgn⁡(b)Y_\lambda(g,h)=\sum_{a\in R_\lambda}\sum_{b\in C_\lambda}\mathbf 1_{\{g=hab\}}\operatorname{sgn}(b)Yλ​(g,h)=∑a∈Rλ​​∑b∈Cλ​​1{g=hab}​sgn(b), with the sign interpreted as a real number. The definition includes n=0n=0n=0, when λ\lambdaλ is empty and the row and column preservation conditions are vacuous.

QAlgorithms.Papers.Independent.Intakenext100.P94.relabelEmbedding

For any natural numbers m,nm,nm,n, any injection χ:[m]↪[n]\chi:[m]\hookrightarrow[n]χ:[m]↪[n], any permutation sss of [n][n][n], and any permutation ppp of [m][m][m], where [r]={0,…,r−1}[r]=\{0,\ldots,r-1\}[r]={0,…,r−1}, the definition returns the injection

relabelEmbedding⁡(χ,s,p):[m]↪[n],i⟼s(χ(p−1(i))).\operatorname{relabelEmbedding}(\chi,s,p):[m]\hookrightarrow[n], \qquad i\longmapsto s\bigl(\chi(p^{-1}(i))\bigr).relabelEmbedding(χ,s,p):[m]↪[n],i⟼s(χ(p−1(i))).

Thus it composes p−1p^{-1}p−1, then χ\chiχ, then sss. Zero values of mmm or nnn are included whenever the given injection exists; for m=0m=0m=0, the resulting injection has empty domain.

QAlgorithms.Papers.Independent.Intakenext100.P94.secondShapes

For every natural number nnn, this defines a function on the four indices 0,1,2,30,1,2,30,1,2,3, whose respective values are the lists [n][n][n], [n−1,1][n-1,1][n−1,1], [n−2,2][n-2,2][n−2,2], and [n−2,1,1][n-2,1,1][n−2,1,1]. Subtraction is natural-number subtraction, truncated at zero. The definition includes n=0n=0n=0 and all other small values of nnn; it imposes no requirement that these lists be row lengths of Young diagrams.

QAlgorithms.Papers.Independent.Intakenext100.P94.sevenFormula

For any natural number nnn, seven real weights w0,…,w6w_0,\ldots,w_6w0​,…,w6​, a real tensor FFF indexed by functions {0,1}→{0,…,n−1}\{0,1\}\to\{0,\ldots,n-1\}{0,1}→{0,…,n−1}, and indices i,j∈{0,…,n−1}i,j\in\{0,\ldots,n-1\}i,j∈{0,…,n−1}, write FijF_{ij}Fij​ for the value on the function taking 000 to iii and 111 to jjj. The definition assigns the real number

w0Fij+w1Fji+w2∑b=0n−1Fib+w3∑a=0n−1Fai+w4∑a=0n−1Faj+w5∑b=0n−1Fjb+w6∑a,b=0n−1Fab.w_0F_{ij}+w_1F_{ji} +w_2\sum_{b=0}^{n-1}F_{ib} +w_3\sum_{a=0}^{n-1}F_{ai} +w_4\sum_{a=0}^{n-1}F_{aj} +w_5\sum_{b=0}^{n-1}F_{jb} +w_6\sum_{a,b=0}^{n-1}F_{ab}.w0​Fij​+w1​Fji​+w2​b=0∑n−1​Fib​+w3​a=0∑n−1​Fai​+w4​a=0∑n−1​Faj​+w5​b=0∑n−1​Fjb​+w6​a,b=0∑n−1​Fab​.

There is no requirement that i≠ji\ne ji=j or that FFF vanish on the diagonal. The parameter n=0n=0n=0 is allowed, but then there are no indices i,ji,ji,j at which to evaluate this definition.

QAlgorithms.Papers.Independent.Intakenext100.P94.supportedSpace

For all natural numbers n,kn,kn,k and every predicate PPP on the tuples t:[k]→[n]t:[k]\to[n]t:[k]→[n], where [r]={0,…,r−1}[r]=\{0,\ldots,r-1\}[r]={0,…,r−1}, this defines the real subspace of real-valued functions FFF on those tuples satisfying ∀t, ¬P(t)⇒F(t)=0\forall t,\ \neg P(t)\Rightarrow F(t)=0∀t, ¬P(t)⇒F(t)=0. Values at tuples satisfying PPP are unrestricted. When k=0k=0k=0, the condition concerns the single empty tuple, whose value must be zero exactly when that tuple fails PPP. When n=0n=0n=0 and k>0k>0k>0, the tuple set is empty and the space consists only of the zero function.

QAlgorithms.Papers.Independent.Intakenext100.P94.tensorOuterProduct

For arbitrary natural numbers n,k,ln,k,ln,k,l, a real tensor F:([k]→[n])→RF:([k]\to[n])\to\mathbb RF:([k]→[n])→R, and a real tensor G:([l]→[n])→RG:([l]\to[n])\to\mathbb RG:([l]→[n])→R, where [r]={0,…,r−1}[r]=\{0,\ldots,r-1\}[r]={0,…,r−1}, the definition returns a real function on tuples indexed by the disjoint union [k]⊔[l][k]\sqcup[l][k]⊔[l], given by

(F⊠G)(t)=F(a↦t(inl⁡(a))) G(b↦t(inr⁡(b))).(F\mathbin{\boxtimes}G)(t) =F\bigl(a\mapsto t(\operatorname{inl}(a))\bigr)\, G\bigl(b\mapsto t(\operatorname{inr}(b))\bigr).(F⊠G)(t)=F(a↦t(inl(a)))G(b↦t(inr(b))).

All parameters may be zero: an order-zero tensor is a scalar evaluated at the unique empty tuple, and if n=0n=0n=0 while k+l>0k+l>0k+l>0, there are no tuples ttt at which to evaluate the output.

QAlgorithms.Papers.Independent.Intakenext100.P94.tensorRowSum

For every natural number nnn, every real-valued function FFF on ordered pairs from [n]={0,…,n−1}[n]=\{0,\ldots,n-1\}[n]={0,…,n−1}, and every i∈[n]i\in[n]i∈[n], this defines the real number ∑j∈[n]F(i,j)\sum_{j\in[n]}F(i,j)∑j∈[n]​F(i,j), where F(i,j)F(i,j)F(i,j) denotes evaluation at the tuple whose first coordinate is iii and second coordinate is jjj. For n=0n=0n=0, there is no index iii to supply.

QAlgorithms.Papers.Independent.Intakenext100.P94.thirdFormula

For any natural number nnn, let [n]={0,…,n−1}[n]=\{0,\ldots,n-1\}[n]={0,…,n−1}; a tensor of order three is an arbitrary function F:[n]3→RF:[n]^3\to\mathbb RF:[n]3→R. A recipe is a pair (q,R)(q,R)(q,R), where q:[3]→[3]q:[3]\to[3]q:[3]→[3] satisfies q(a)≤aq(a)\le aq(a)≤a and q(q(a))=q(a)q(q(a))=q(a)q(q(a))=q(a) for every aaa, and R⊆[3]R\subseteq[3]R⊆[3] consists only of fixed points of qqq. A placed recipe with rrr positions is such a recipe together with an injection e:R↪[r]e:R\hookrightarrow[r]e:R↪[r]. For a placed recipe P=(q,R,e)P=(q,R,e)P=(q,R,e), a tuple v:[r]→[n]v:[r]\to[n]v:[r]→[n], and u:[3]→[n]u:[3]\to[n]u:[3]→[n], define CP(v,u)C_P(v,u)CP​(v,u) to be 111 if both q(a)=q(b)⇒u(a)=u(b)q(a)=q(b)\Rightarrow u(a)=u(b)q(a)=q(b)⇒u(a)=u(b) for every a,b∈[3]a,b\in[3]a,b∈[3] and u(a)=v(e(a))u(a)=v(e(a))u(a)=v(e(a)) for every a∈Ra\in Ra∈R, and 000 otherwise; distinct values of qqq impose no inequality requirement on uuu. Let III be the disjoint union of the placed recipes with three positions, pairs consisting of a∈[3]a\in[3]a∈[3] and a placed recipe with two positions, and placed recipes with one position. For t,u:[3]→[n]t,u:[3]\to[n]t,u:[3]→[n], define KP(t,u)=CP(t,u)K_P(t,u)=C_P(t,u)KP​(t,u)=CP​(t,u) in the first component; K(a,P)(t,u)=CP((t(a+1),t(a)),u)K_{(a,P)}(t,u)=C_P((t(a+1),t(a)),u)K(a,P)​(t,u)=CP​((t(a+1),t(a)),u) if t(a+1)=t(a+2)t(a+1)=t(a+2)t(a+1)=t(a+2), and 000 otherwise, in the second component; and KP(t,u)=CP((t(0)),u)K_P(t,u)=C_P((t(0)),u)KP​(t,u)=CP​((t(0)),u) if all three coordinates of ttt are equal, and 000 otherwise, in the third component, where addition in the indices a+1,a+2a+1,a+2a+1,a+2 is modulo 333. For arbitrary weights w:I→Rw:I\to\mathbb Rw:I→R, the definition returns the tensor

thirdFormula⁡(w,F)(t)=∑P∈Iw(P)∑u:[3]→[n]KP(t,u)F(u).\operatorname{thirdFormula}(w,F)(t) =\sum_{P\in I}w(P)\sum_{u:[3]\to[n]}K_P(t,u)F(u).thirdFormula(w,F)(t)=P∈I∑​w(P)u:[3]→[n]∑​KP​(t,u)F(u).

The parameter n=0n=0n=0 is included; in that case there are no triples ttt or uuu, and the output is the unique function on the empty set.

QAlgorithms.Papers.Independent.Intakenext100.P94.thirdKernel

For any natural number nnn, take triples t,u:{0,1,2}→{0,…,n−1}t,u:\{0,1,2\}\to\{0,\ldots,n-1\}t,u:{0,1,2}→{0,…,n−1} and a tagged index ppp of one of three forms: q∈P3q\in P_3q∈P3​, (a,q)∈{0,1,2}×P2(a,q)\in\{0,1,2\}\times P_2(a,q)∈{0,1,2}×P2​, or q∈P1q\in P_1q∈P1​, where PrP_rPr​ consists of data q=(f,A,e)q=(f,A,e)q=(f,A,e) with f:{0,1,2}→{0,1,2}f:\{0,1,2\}\to\{0,1,2\}f:{0,1,2}→{0,1,2}, f(b)≤bf(b)\le bf(b)≤b, f(f(b))=f(b)f(f(b))=f(b)f(f(b))=f(b) for every bbb, AAA a finite subset of the fixed points of fff, and e:A→{0,…,r−1}e:A\to\{0,\ldots,r-1\}e:A→{0,…,r−1} injective. For an rrr-tuple vvv, define Cq(v,u)C_q(v,u)Cq​(v,u) to be 111 if f(b)=f(c)f(b)=f(c)f(b)=f(c) implies ub=ucu_b=u_cub​=uc​ for every b,c∈{0,1,2}b,c\in\{0,1,2\}b,c∈{0,1,2}, and ub=ve(b)u_b=v_{e(b)}ub​=ve(b)​ for every b∈Ab\in Ab∈A, and to be 000 otherwise. The defined real-valued kernel is

Kp(t,u)={Cq(t,u),p is in the P3 summand,Cq([ta+1,ta],u),p=(a,q) is in the middle summand and ta+1=ta+2,0,p=(a,q) is in the middle summand and ta+1≠ta+2,Cq([t0],u),p is in the P1 summand and all entries of t are equal,0,p is in the P1 summand and the entries of t are not all equal.K_p(t,u)= \begin{cases} C_q(t,u),&p\text{ is in the }P_3\text{ summand},\\ C_q([t_{a+1},t_a],u),&p=(a,q)\text{ is in the middle summand and }t_{a+1}=t_{a+2},\\ 0,&p=(a,q)\text{ is in the middle summand and }t_{a+1}\ne t_{a+2},\\ C_q([t_0],u),&p\text{ is in the }P_1\text{ summand and all entries of }t\text{ are equal},\\ 0,&p\text{ is in the }P_1\text{ summand and the entries of }t\text{ are not all equal}. \end{cases}Kp​(t,u)=⎩⎨⎧​Cq​(t,u),Cq​([ta+1​,ta​],u),0,Cq​([t0​],u),0,​p is in the P3​ summand,p=(a,q) is in the middle summand and ta+1​=ta+2​,p=(a,q) is in the middle summand and ta+1​=ta+2​,p is in the P1​ summand and all entries of t are equal,p is in the P1​ summand and the entries of t are not all equal.​

Index additions in the middle summand are modulo 333, and [ta+1,ta][t_{a+1},t_a][ta+1​,ta​] has entries in that stated order. The middle summand requires no inequality involving tat_ata​, so it also applies when all entries of ttt are equal. Empty sets AAA impose no matching conditions, and for n=0n=0n=0 there are no possible input triples t,ut,ut,u.

QAlgorithms.Papers.Independent.Intakenext100.P94.thirdShapes

For every natural number nnn, this defines a function on the seven indices 0,1,…,60,1,\ldots,60,1,…,6, whose respective values are the lists [n][n][n], [n−1,1][n-1,1][n−1,1], [n−2,2][n-2,2][n−2,2], [n−2,1,1][n-2,1,1][n−2,1,1], [n−3,3][n-3,3][n−3,3], [n−3,2,1][n-3,2,1][n−3,2,1], and [n−3,1,1,1][n-3,1,1,1][n−3,1,1,1]. Every subtraction is natural-number subtraction, truncated at zero. All natural numbers nnn, including zero, are allowed, and the definition imposes no condition that the resulting lists describe Young diagrams.

QAlgorithms.Papers.Independent.Intakenext100.P94.totalSum

For every natural number nnn and every real-valued function FFF on ordered pairs from [n]={0,…,n−1}[n]=\{0,\ldots,n-1\}[n]={0,…,n−1}, this defines the real number ∑i∈[n]∑j∈[n]F(i,j)\sum_{i\in[n]}\sum_{j\in[n]}F(i,j)∑i∈[n]​∑j∈[n]​F(i,j), summing over all ordered pairs, including those with equal coordinates. When n=0n=0n=0, the sum is empty and equals zero.

QAlgorithms.Papers.Independent.Intakenext100.P94.vectorValues

For every natural number nnn, a hypothesis 1≤n1\le n1≤n, and every function f:{0,…,n−1}→Rf:\{0,\ldots,n-1\}\to\mathbb Rf:{0,…,n−1}→R, this defines a real-valued function on the left cosets of H={s∈Sn:s(n−1)=n−1}H=\{s\in S_n:s(n-1)=n-1\}H={s∈Sn​:s(n−1)=n−1} by q↦f(rq(n−1))q\mapsto f(r_q(n-1))q↦f(rq​(n−1)), where rq∈Snr_q\in S_nrq​∈Sn​ is the chosen representative of qqq. The hypothesis excludes n=0n=0n=0; for n=1n=1n=1, both the underlying index set and the coset space have one element.

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