claimroutine

Bipartite Cayley graph on shifts

Claim·§6.1 Initial tests that exclude small violation sets·inside lemSparse parity checks force large supports

Statement (paper)

Let

d_G=\min(m,D_0)

and

q_G=\min\{2^a:a\in\mathbb Z_{\ge0},\ 2^a d_G\ge m\}=2^{\ell_G}

, so that

m\le q_Gd_G<2m

. For any shifts

s_1,\ldots,s_{d_G}\in\{0,1\}^{\ell_G}

, the bipartite graph whose left and right vertex sets are two copies of

\{0,1\}^{\ell_G}

, with one edge

(u,j)

from each left vertex

u

u\oplus s_j

for every

j\in[d_G]

(parallel edges kept distinct), has

q_Gd_G\in[m,2m)

edges and is

d_G

-regular, since every vertex on either side has exactly one incident edge at each port

j

In plain English

With

d_G=\min(m,D_0)

and

q_G=2^{\ell_G}

the least power of two with

q_Gd_G\ge m

, any choice of shifts

s_1,\ldots,s_{d_G}\in\{0,1\}^{\ell_G}

gives a

d_G

-regular bipartite graph on two copies of

\{0,1\}^{\ell_G}

, joining

u

u\oplus s_j

for each

j

, with

q_Gd_G\in[m,2m)

edges.

Why it's here

This fixes the graph format that the later claims work with: the edge count lies in

[m,2m)

, so edges can index the

m

columns, and the degree

d_G\le D_0

bounds the row weights. Because the graph is determined by the shifts alone, the remaining task is to choose shifts with small Fourier bias, which the next claim addresses.

Classified routine:

Elementary counting fact about bipartite Cayley graphs on the group Z_2^l with a chosen set of shifts: each port gives a perfect matching, so the graph is d_G-regular with q_G d_G edges. The bound m ≤ q_G d_G < 2m follows from q_G being the least power of two with q_G d_G ≥ m.

Uses

Nothing else in the paper

Used by

claimSmall-bias shifts exist and can be found

Sources

PaperOpen

Section: §6.1 Initial tests that exclude small violation sets
Page: —
Label: —
Line: main_full_version.tex:3281

Leannot aligned

Phase 2 aligns this node to a Lean declaration.