proofs
Provedalphamulti-device-learningpartitioning

Gradient partitioning delivers the replicated sums bit for bit

For all α∈Type⁡\htmlData{mx=1}{\alpha \in \htmlData{mx=0}{\operatorname{Type}}}, op:α→α→α\htmlData{mx=5}{\mathit{op} : \htmlData{mx=0}{\alpha} \mathrel{\htmlData{mx=4}{\to}} \htmlData{mx=1}{\alpha} \mathrel{\htmlData{mx=3}{\to}} \htmlData{mx=2}{\alpha}}, owners,r∈N\htmlData{mx=1}{\mathit{owners}, r \in \htmlData{mx=0}{\mathbb{N}}}, v:N→N→α\htmlData{mx=5}{v : \htmlData{mx=0}{\mathbb{N}} \mathrel{\htmlData{mx=4}{\to}} \htmlData{mx=1}{\mathbb{N}} \mathrel{\htmlData{mx=3}{\to}} \htmlData{mx=2}{\alpha}}, t∈CombineTree⁡\htmlData{mx=1}{t \in \htmlData{mx=0}{\operatorname{CombineTree}}} and idx∈N\htmlData{mx=1}{\mathit{idx} \in \htmlData{mx=0}{\mathbb{N}}}:

eval⁡(t)(pointwise⁡(op),o↦projectOwner⁡(owners,r,v(o)),idx)=eval⁡(t)(pointwise⁡(op),v,r+idx⋅owners)\begin{aligned} & \htmlData{mx=16}{\htmlData{mx=3}{\operatorname{eval}\left(\htmlData{mx=2}{t}\right)}(\htmlData{mx=6}{\htmlData{mx=4}{\operatorname{pointwise}}(\htmlData{mx=5}{\mathit{op}})}, \htmlData{mx=14}{o \mapsto \htmlData{mx=13}{\htmlData{mx=7}{\operatorname{projectOwner}}(\htmlData{mx=8}{\mathit{owners}}, \htmlData{mx=9}{r}, \htmlData{mx=12}{\htmlData{mx=10}{v}(\htmlData{mx=11}{o})})}}, \htmlData{mx=15}{\mathit{idx}})} \\ & \quad \htmlData{mx=0}{=} \htmlData{mx=29}{\htmlData{mx=19}{\operatorname{eval}\left(\htmlData{mx=18}{t}\right)}(\htmlData{mx=22}{\htmlData{mx=20}{\operatorname{pointwise}}(\htmlData{mx=21}{\mathit{op}})}, \htmlData{mx=23}{v}, \htmlData{mx=28}{\htmlData{mx=24}{r} + \htmlData{mx=27}{\htmlData{mx=25}{\mathit{idx}} \cdot \htmlData{mx=26}{\mathit{owners}}}})} \end{aligned}
What the notation means · or point at any symbol
Type
Type: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Type)
NNatural numbers
The natural numbers 0, 1, 2, …. In Lean they start at 0. (Nat)
x ∈ TVariables
owners, r range over natural numbers: the statement must hold for every choice. ((owners r : Nat))
CombineTree
CombineTree: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (CombineTree)
e.feval
eval of t: Lean's dot notation e.eval means eval applied to e. (t.eval)
=Equality
eval(pointwise(op), o ↦ projectOwner(owners, r, v(o)), idx) and eval(pointwise(op), v, r + idx · owners) are the same. (t.eval (pointwise op) (fun o => project…)
⟹Implies
If α, then α. (Between types, A → B is the type of functions from A to B.) (α → α)
pointwise
pointwise: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (pointwise)
f(x)Function application
pointwise applied to op. Lean writes f x; papers write f(x). (pointwise op)
x ↦ f(x)Function (λ-abstraction)
The function sending o to projectOwner(owners, r, v(o)). Lean writes fun x => …; papers write x ↦ …. (fun o => projectOwner owners r (v o))
projectOwner
projectOwner: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (projectOwner)
+Addition
r plus idx · owners. (r + idx * owners)
·Multiplication
idx times owners. (idx * owners)

Reducing every owner's projection onto owner r's coordinates (dpoProject) over a combine tree gives, word for word, the full elementwise sum of those coordinates over the same tree and order, for any combining operation (binary64 addition included): each coordinate owner's delivered sums equal the replicated sums exactly. Model: definition alpha-multi-device-learning (revision 01a1255c-84f1-7e7f-a994-fc8c2d274bee).

How it was proved

Proved
10 October 2026
By
Ajax
Checked by
Lean's kernel (Lean 4.33.1, with Mathlib); the proof is signed and replays offline
Axioms
propext
Proof
31 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.

More proved statements