While this submission is a draft, it cannot be used by other submissions.

Proof of `A lower bound on the iteration number of k-WL`

groundedproofs/Lax119563Proofs/Counter/Main.lean · lax-119563

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Fix k=K+1≥3k = K + 1 ≥ 3 and compile the counter implicit parity system counterKℓcounter K ℓ (main location carrying all 2(k−1)ℓ2^{(k-1)ℓ} counter values, three equality schemas per increment position, endpoints initialized 00 and 11) with the row-space compiler.

  • Its conflict round ττ is finite and at least 2(k−1)ℓ2^{(k-1)ℓ} (counterconflictRoundcounter_conflictRound, via a potential argument along the chain of equalities).
  • Its size parameter is at most CK2ℓC_K 2^ℓ (sizeParameterlesizeParameter_le): the coordinates of the domain of an increment at position jj have fixed bits in the rows below ⌊j/K⌋⌊j/K⌋, which bounds both the domain size and the rank of the restricted check matrix.
  • Duplicator survives τ−1τ - 1 rounds of the bijective (k+1)(k+1)-pebble game, so the graphs have equal size nn and, by the game characterization, every distinguishing round rr satisfies τ≤r+kτ ≤ r + k; Spoiler wins eventually, so kk-WL distinguishes the graphs.
  • Hence nk−1≤(CCK2ℓ)k−1≤(CCK)k−1τ≤(CCK)k−1(k+1)rn^{k-1} ≤ (C C_K 2^ℓ)^{k-1} ≤ (C C_K)^{k-1} τ ≤ (C C_K)^{k-1}(k+1) r.
  • Since kk-WL distinguishes two graphs after at most 2nk2 n^k rounds if at all (existsdistinguishesAfterleexists_distinguishesAfter_le), τ≤2nk+kτ ≤ 2 n^k + k, so choosing ℓℓ large forces n≥n0n ≥ n₀.