lemmaroutine

Projected matrix-test pair is nearly uniform

Projected pair

(M,T)

o(1)

-close to uniform in total variation

lets witnesses move to the projected slice

Lemma·lem:projected-tv·§5.5 Transferring the chosen slice

Statement (paper)

Conditional on every

U

, the distribution of

(M,T)=(M_O\bar\pi,T_O\bar\pi)

has total variation distance

o(1)

from the unrestricted uniform distribution on

\Hom(L_U,K)\times\Hom(L_U,W)

, as

k

tends to infinity along cubes. The bound is uniform in

U

and the parity instance. The projection choices are averaged out in this comparison.

In plain English

Conditioned on any

U

, the pair

(M,T)=(M_O\bar\pi,T_O\bar\pi)

is within total variation distance

o(1)

of the uniform distribution on

\Hom(L_U,K)\times\Hom(L_U,W)

k\to\infty

along cubes. The bound is uniform in

U

and in the parity instance, and the projection choices are averaged out.

Why it's here

This lets later arguments replace the actual projected pair by a uniformly random pair of homomorphisms at only

o(1)

cost. It is what allows a witness chosen on one slice to be transferred to the projected slice, as used in the matrix decoding proposition and the transfer-of-witness lemma.

Classified routine:

A total-variation calculation showing that random projections of uniform linear maps are close to uniform, using standard counting of full-rank / surjective linear maps over finite fields. It is a technical step in the reduction, not one of the paper's headline ideas.

Uses

Nothing else in the paper

Used by

propMatrix test passing yields decoding strategieslemGood advice transfers to projected sliceclaimChoosing the cube k and parity error

Sources

PaperOpen

Section: §5.5 Transferring the chosen slice
Page: —
Label: lem:projected-tv
Line: sections/04-matrix.tex:468

Leannot aligned

Phase 2 aligns this node to a Lean declaration.