Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Weighted sums with wedge factors assigned to channels

Definition
VWZClique_FoldedSum

by orz · Nov 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

clique-countingfine-grained-complexity

Three factorized channels with specified active binary factors are contracted using identities or partial swaps on two pivot pairs.

Definition code
import Definitions.Def_VWZClique_Contraction

namespace VWZClique
abbrev EdgeSlot := Fin 3 × Slot × Slot

def placedChannel {F : Type*} [Field F] {L : ℕ} (E : Finset EdgeSlot)
    (w : ChannelKey L → F) (h : Fin 3) (a b : Block L) : F :=
  let x : Slot → Bits L := Sum.elim a b
  (∏ i : Slot, w (h, .inl (i, x i))) *
    ∏ v ∈ E, if v.1 = h then w (h, .inr (v.2.1, v.2.2, x v.2.1, x v.2.2)) else 1

open Classical in
noncomputable def maskKernel {F : Type*} [Field F] {L : ℕ}
    (m : Option (Mask L)) (x y : PairBits L) : F :=
  match m with
  | none => if x = y then 1 else 0
  | some s => if swapOK s x y then 1 else 0

noncomputable def placedFold {F : Type*} [Field F] {L : ℕ} (E : Finset EdgeSlot)
    (a b : Option (Mask L)) (w : ChannelKey L → F) : F :=
  ∑ z₁ : Bits L, ∑ z₂ : Bits L, ∑ c : Block L,
    ∑ x : PairBits L, ∑ x' : PairBits L, ∑ y : PairBits L, ∑ y' : PairBits L,
      maskKernel a x x' * maskKernel (F := F) b y y' *
      placedChannel E w 0 (block x z₁) (block y z₂) *
      placedChannel E w 1 (block y' z₂) c * placedChannel E w 2 c (block x' z₁)

def wedgePlaced (E : Finset EdgeSlot) (left right : Fin 3) : Prop :=
  (left, Sum.inl 0, Sum.inl 2) ∈ E ∧ (right, Sum.inr 1, Sum.inr 2) ∈ E
end VWZClique
Source
V. Vassilevska Williams and O. Zamir, The k-Clique hypothesis is dead, for good (2026), Section 3.2, Lemma 3.2. https://zamir.prof/kclq.pdf
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (GPT-6), independent blind auditor

Edge slots. An edge slot is an ordered triple (h,i,j)(h,i,j)(h,i,j), where h∈{0,1,2}h\in\{0,1,2\}h∈{0,1,2} and i,ji,ji,j each belong to the six-element set S={ℓ0,ℓ1,ℓ2,r0,r1,r2}S=\{\ell_0,\ell_1,\ell_2,r_0,r_1,r_2\}S={ℓ0​,ℓ1​,ℓ2​,r0​,r1​,r2​}. The two slots can coincide, and exchanging distinct slots gives a different triple.

Placed channel. For any field FFF and natural number LLL, put B={0,1}LB=\{0,1\}^LB={0,1}L and S={ℓ0,ℓ1,ℓ2,r0,r1,r2}S=\{\ell_0,\ell_1,\ell_2,r_0,r_1,r_2\}S={ℓ0​,ℓ1​,ℓ2​,r0​,r1​,r2​}. Take any finite E⊆{0,1,2}×S2E\subseteq\{0,1,2\}\times S^2E⊆{0,1,2}×S2, channel h∈{0,1,2}h\in\{0,1,2\}h∈{0,1,2}, and ordered triples A,D∈B3A,D\in B^3A,D∈B3. Write tℓk=Akt_{\ell_k}=A_ktℓk​​=Ak​ and trk=Dkt_{r_k}=D_ktrk​​=Dk​ for k=0,1,2k=0,1,2k=0,1,2. The input www assigns arbitrary field values to all single-slot keys (h,i,u)(h,i,u)(h,i,u) and all ordered two-slot keys (h,i,j,u,v)(h,i,j,u,v)(h,i,j,u,v), with i,j∈Si,j\in Si,j∈S and u,v∈Bu,v\in Bu,v∈B, for each of the three channels. The placed channel is Ch(A,D)=∏i∈Sw(h,i,ti)∏(h′,i,j)∈E, h′=hw(h,i,j,ti,tj)C_h(A,D)=\prod_{i\in S}w(h,i,t_i)\prod_{(h',i,j)\in E,\,h'=h}w(h,i,j,t_i,t_j)Ch​(A,D)=∏i∈S​w(h,i,ti​)∏(h′,i,j)∈E,h′=h​w(h,i,j,ti​,tj​). An empty second product equals one. For L=0L=0L=0, the unique possible string is empty.

Mask kernel. For any field FFF, natural number LLL, ordered pairs x,yx,yx,y of length-LLL bit strings, and optional mask mmm, the value Km(x,y)∈FK_m(x,y)\in FKm​(x,y)∈F is zero or one. If mmm is absent, it is one exactly when x=yx=yx=y. A present mask has one entry for each of the LLL coordinates, each entry either blank or an ordered quadruple of bits. The kernel is one exactly when every blank coordinate iii satisfies (x1(i),x2(i))=(y2(i),y1(i))(x_1(i),x_2(i))=(y_2(i),y_1(i))(x1​(i),x2​(i))=(y2​(i),y1​(i)) and every specified quadruple at iii equals (x1(i),x2(i),y1(i),y2(i))(x_1(i),x_2(i),y_1(i),y_2(i))(x1​(i),x2​(i),y1​(i),y2​(i)). In each case it is zero otherwise. At L=0L=0L=0 it is one for either choice of mask presence.

Placed fold. For any field FFF, natural number LLL, string set B={0,1}LB=\{0,1\}^LB={0,1}L, and six slots S={ℓ0,ℓ1,ℓ2,r0,r1,r2}S=\{\ell_0,\ell_1,\ell_2,r_0,r_1,r_2\}S={ℓ0​,ℓ1​,ℓ2​,r0​,r1​,r2​}, take a finite E⊆{0,1,2}×S2E\subseteq\{0,1,2\}\times S^2E⊆{0,1,2}×S2, optional masks a,ba,ba,b, and arbitrary FFF-valued weights w(h,i,u)w(h,i,u)w(h,i,u) and w(h,i,j,u,v)w(h,i,j,u,v)w(h,i,j,u,v) for all channels h∈{0,1,2}h\in\{0,1,2\}h∈{0,1,2}, slots i,j∈Si,j\in Si,j∈S, and strings u,v∈Bu,v\in Bu,v∈B. For A,D∈B3A,D\in B^3A,D∈B3, assign tℓk=Ak,trk=Dkt_{\ell_k}=A_k,t_{r_k}=D_ktℓk​​=Ak​,trk​​=Dk​ for k=0,1,2k=0,1,2k=0,1,2, and put Ch(A,D)=∏i∈Sw(h,i,ti)∏(h′,i,j)∈E, h′=hw(h,i,j,ti,tj)C_h(A,D)=\prod_{i\in S}w(h,i,t_i)\prod_{(h',i,j)\in E,\,h'=h}w(h,i,j,t_i,t_j)Ch​(A,D)=∏i∈S​w(h,i,ti​)∏(h′,i,j)∈E,h′=h​w(h,i,j,ti​,tj​). For p,q∈B2p,q\in B^2p,q∈B2, Km(p,q)K_m(p,q)Km​(p,q) is the indicator of equality if mmm is absent. If mmm is present it is the indicator that, at every coordinate, the ordered bits of qqq reverse those of ppp for a blank mask entry, or the four bits of (p,q)(p,q)(p,q) in order equal the specified quadruple for a filled entry. Write T(p,z)=(p1,p2,z)T(p,z)=(p_1,p_2,z)T(p,z)=(p1​,p2​,z). The placed fold is the field element

∑z1,z2∈B ∑c∈B3 ∑x,x′,y,y′∈B2Ka(x,x′)Kb(y,y′) C0(T(x,z1),T(y,z2)) C1(T(y′,z2),c) C2(c,T(x′,z1)).\sum_{z_1,z_2\in B}\ \sum_{c\in B^3}\ \sum_{x,x',y,y'\in B^2} K_a(x,x')K_b(y,y')\,C_0(T(x,z_1),T(y,z_2))\,C_1(T(y',z_2),c)\,C_2(c,T(x',z_1)).z1​,z2​∈B∑​ c∈B3∑​ x,x′,y,y′∈B2∑​Ka​(x,x′)Kb​(y,y′)C0​(T(x,z1​),T(y,z2​))C1​(T(y′,z2​),c)C2​(c,T(x′,z1​)).

All seven variables range independently. At L=0L=0L=0 the sum has one term and both indicators equal one.

Placed wedge. For any finite set EEE of triples (h,i,j)(h,i,j)(h,i,j) consisting of a channel h∈{0,1,2}h\in\{0,1,2\}h∈{0,1,2} and two ordered slots from {ℓ0,ℓ1,ℓ2,r0,r1,r2}\{\ell_0,\ell_1,\ell_2,r_0,r_1,r_2\}{ℓ0​,ℓ1​,ℓ2​,r0​,r1​,r2​}, and any channel indices s,t∈{0,1,2}s,t\in\{0,1,2\}s,t∈{0,1,2}, the predicate requires both (s,ℓ0,ℓ2)∈E(s,\ell_0,\ell_2)\in E(s,ℓ0​,ℓ2​)∈E and (t,r1,r2)∈E(t,r_1,r_2)\in E(t,r1​,r2​)∈E. The indices s,ts,ts,t may coincide.

Human review
  • Endorsed by Shuze Chen · Nov 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by orz · Nov 20, 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