Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The two-projection contribution

Definition
VWZClique_Contraction

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

clique-countingfine-grained-complexity

Three channels consist of products of unary and binary factors on two incident triples. Two rational product-basis projections are interpreted in the coefficient field.

Definition code
import Definitions.Def_VWZClique_Operators
import Definitions.Def_VWZClique_Weighted

namespace VWZClique
abbrev Slot := Fin 3 ⊕ Fin 3
abbrev Block (L : ℕ) := Fin 3 → Bits L
abbrev ChannelKey (L : ℕ) :=
  Fin 3 × ((Slot × Bits L) ⊕ (Slot × Slot × Bits L × Bits L))

def channel {F : Type*} [Field F] {L : ℕ} (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))) *
    ∏ i : Slot, ∏ j : Slot, w (h, .inr (i, j, x i, x j))

def block {L : ℕ} (x : PairBits L) (z : Bits L) : Block L :=
  fun i => if i = 0 then x.1 else if i = 1 then x.2 else z

def projected {F : Type*} [Field F] [CharZero F] {L : ℕ}
    (Λ : Finset (BasisLabel L)) (d : BasisLabel L → F) (x y : PairBits L) : F :=
  ∑ j ∈ Λ, d j * (basisEntry j x : F) * (basisEntry j y : F)

noncomputable def doubleProjection {F : Type*} [Field F] [CharZero F] {L : ℕ}
    (Λ Γ : Finset (BasisLabel L)) (d e : BasisLabel L → F)
    (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,
      projected Λ d x x' * projected Γ e y y' *
      channel w 0 (block x z₁) (block y z₂) *
      channel w 1 (block y' z₂) c * channel w 2 c (block x' z₁)
end VWZClique
Source
V. Vassilevska Williams and O. Zamir, The k-Clique hypothesis is dead, for good (2026), Section 3.3, equations (6)–(9). https://zamir.prof/kclq.pdf
Read-back

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

Slot. A slot belongs to one of two distinguishable copies of {0,1,2}\{0,1,2\}{0,1,2}. Write SSS for this six-element set.

Block. For every natural number LLL, a block assigns a length-LLL Boolean word to each of 0,1,20,1,20,1,2. It is an ordered triple of words. At L=0L=0L=0 there is exactly one block.

Channel key. For every natural number LLL, a key consists of h∈{0,1,2}h\in\{0,1,2\}h∈{0,1,2} together with either a slot and a length-LLL Boolean word, or an ordered pair of slots and an ordered pair of such words. A slot is one of two tagged copies of the three positions 0,1,20,1,20,1,2. The two kinds of keys are distinguished, and repeated slots or words are allowed.

Channel. For any field FFF, natural number LLL, field-valued table www on the keys just described, h∈{0,1,2}h\in\{0,1,2\}h∈{0,1,2} and two ordered triples a,ba,ba,b of length-LLL Boolean words, let uuu read the three words of aaa on the first three tagged slots and those of bbb on the second three. Writing superscripts to distinguish the two key kinds, the value is ∏i∈Swh(1)(i,ui)∏(i,j)∈S2wh(2)(i,j,ui,uj)\prod_{i\in S}w_h^{(1)}(i,u_i)\prod_{(i,j)\in S^2}w_h^{(2)}(i,j,u_i,u_j)∏i∈S​wh(1)​(i,ui​)∏(i,j)∈S2​wh(2)​(i,j,ui​,uj​). All six single slots and all 36 ordered slot pairs occur, including the six diagonal pairs.

Block constructor. For every natural number LLL, an ordered pair x=(x1,x2)x=(x_1,x_2)x=(x1​,x2​) of length-LLL Boolean words and one further such word zzz, the output assigns x1,x2,zx_1,x_2,zx1​,x2​,z to positions 0,1,20,1,20,1,2, respectively.

Projected entry. For any characteristic-zero field FFF, natural number LLL, finite set Λ\LambdaΛ of length-LLL strings over {0,1,2,3}\{0,1,2,3\}{0,1,2,3}, arbitrary field-valued coefficient function ddd on all such strings, and ordered pairs x,yx,yx,y of length-LLL Boolean words, the value is PΛ,d(x,y)=∑j∈Λd(j)bj(x)bj(y)P_{\Lambda,d}(x,y)=\sum_{j\in\Lambda}d(j)b_j(x)b_j(y)PΛ,d​(x,y)=∑j∈Λ​d(j)bj​(x)bj​(y), with rational entries interpreted in FFF. Here bj(x)=∏i=0L−1tji(x1i,x2i)b_j(x)=\prod_{i=0}^{L-1}t_{j_i}(x_{1i},x_{2i})bj​(x)=∏i=0L−1​tji​​(x1i​,x2i​). On Boolean pairs in order 00,01,10,1100,01,10,1100,01,10,11, the four rows t0,t1,t2,t3t_0,t_1,t_2,t_3t0​,t1​,t2​,t3​ are (1,0,0,0),(0,0,0,1),(0,1,1,0),(0,1,−1,0)(1,0,0,0),(0,0,0,1),(0,1,1,0),(0,1,-1,0)(1,0,0,0),(0,0,0,1),(0,1,1,0),(0,1,−1,0). The empty set gives zero and the empty coordinate product at L=0L=0L=0 is one.

Double projection. For any characteristic-zero field FFF, natural number LLL, finite sets Λ,Γ\Lambda,\GammaΛ,Γ of length-LLL four-symbol labels, coefficient functions d,ed,ed,e on all labels with values in FFF, and field-valued channel-key table www, put B(x,z)=(x1,x2,z)B(x,z)=(x_1,x_2,z)B(x,z)=(x1​,x2​,z). The defined scalar is

∑z1,z2,c,x,x′,y,y′PΛ,d(x,x′)PΓ,e(y,y′)H0(B(x,z1),B(y,z2))H1(B(y′,z2),c)H2(c,B(x′,z1)).\sum_{z_1,z_2,c,x,x',y,y'}P_{\Lambda,d}(x,x')P_{\Gamma,e}(y,y')H_0(B(x,z_1),B(y,z_2))H_1(B(y',z_2),c)H_2(c,B(x',z_1)).z1​,z2​,c,x,x′,y,y′∑​PΛ,d​(x,x′)PΓ,e​(y,y′)H0​(B(x,z1​),B(y,z2​))H1​(B(y′,z2​),c)H2​(c,B(x′,z1​)).

Each ziz_izi​ independently ranges over all length-LLL Boolean words, ccc over all ordered triples of words, and each of x,x′,y,y′x,x',y,y'x,x′,y,y′ over all ordered pairs of words. For two triples, HhH_hHh​ concatenates their words on the six tagged slots and multiplies the six unary table entries and all 36 ordered binary entries, including loops, using channel hhh and the words at the indicated slots. Each PA,f(v,v′)P_{A,f}(v,v')PA,f​(v,v′) sums f(j)bj(v)bj(v′)f(j)b_j(v)b_j(v')f(j)bj​(v)bj​(v′) over j∈Aj\in Aj∈A, where bjb_jbj​ multiplies the coordinate entries selected by jjj. For pair values 00,01,10,1100,01,10,1100,01,10,11 these rows for labels 0,1,2,30,1,2,30,1,2,3 are (1,0,0,0),(0,0,0,1),(0,1,1,0),(0,1,−1,0)(1,0,0,0),(0,0,0,1),(0,1,1,0),(0,1,-1,0)(1,0,0,0),(0,0,0,1),(0,1,1,0),(0,1,−1,0). Either empty label set gives zero. At L=0L=0L=0 each word, tuple of words and label space is a singleton and the coordinate products are one.

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