Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.2 — Free-coordinate bijection

Proved
VWZClique.free_words

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

clique-countingfine-grained-complexity

The support of a partial swap is in bijection with pairs of free-coordinate strings. Under this bijection the two wedge-edge weights depend on the same free string and center. The statement is the local bijection used in the proof.

Preamble
import Definitions.Def_VWZClique_Free

open VWZClique
Formal statement
theorem VWZClique.free_words {L : ℕ} (m : Mask L) (x y : PairBits L) :
    swapOK m x y ↔ ∃! pq : Free m × Free m, expand m pq = (x,y) := by sorry
Source
V. Vassilevska Williams and O. Zamir, The k-Clique hypothesis is dead, for good (2026), Lemma 3.2, proof. https://zamir.prof/kclq.pdf
Read-back

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

For every natural number LLL, every mask mmm assigning either no value or an ordered Boolean quadruple to each of the LLL coordinates, and every pair of ordered word pairs x=(a,b)x=(a,b)x=(a,b) and y=(c,d)y=(c,d)y=(c,d) with a,b,c,da,b,c,da,b,c,d length-LLL Boolean words, the following are equivalent. First, at every coordinate iii where mmm specifies a quadruple, (ai,bi,ci,di)(a_i,b_i,c_i,d_i)(ai​,bi​,ci​,di​) equals that quadruple, and at every unspecified coordinate iii, ai=dia_i=d_iai​=di​ and bi=cib_i=c_ibi​=ci​. Second, there exists exactly one ordered pair (p,q)(p,q)(p,q) of Boolean assignments to the unspecified coordinates such that filling the four output words coordinatewise gives (x,y)(x,y)(x,y): the filling uses the specified quadruple wherever present and (pi,qi,qi,pi)(p_i,q_i,q_i,p_i)(pi​,qi​,qi​,pi​) everywhere else. A fully specified mask gives a singleton domain of assignment pairs. At L=0L=0L=0 every word is empty, the coordinate conditions are vacuous and the pair of empty assignments is unique.

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