Skip to content

Random Local Codes Generic No-Zero Coordinates

Claim/Theorem

In the random local-code model of Leverrier and Zemor's Theorem 18, the no-zero-coordinate condition needed by [[connected-basis-for-nonzero-coordinate-code.md]] is generic.

More precisely, fix large \(\Delta\) and \(r=\lfloor \rho\Delta\rfloor\) with \(0<\rho<1/2\). Let:

  • \(C_A\) be the code generated by a uniform random \(r\times \Delta\) generator matrix,
  • \(C_B\) be the kernel of a uniform random \(r\times \Delta\) parity-check matrix.

Then, for a fixed coordinate:

  • the probability that this coordinate is zero in \(C_A\) is exactly \(2^{-r}\),
  • the probability that this coordinate is zero in \(C_B^\perp\) is exactly \(2^{-r}\),
  • the probability that this coordinate is zero in \(C_A^\perp\) is at most \(2^{r-\Delta}\),
  • the probability that this coordinate is zero in \(C_B\) is at most \(2^{r-\Delta}\).

By a union bound over the \(\Delta\) coordinates,

\[ \Pr[\text{some zero coordinate in one of }C_A,C_B,C_A^\perp,C_B^\perp] \;\le\; 2\Delta\,2^{-r}+2\Delta\,2^{r-\Delta}, \]

which tends to 0 as \(\Delta\to\infty\) for any fixed \(\rho\in(0,1/2)\). Therefore the same random model used to obtain Theorem 18 generically also provides the local no-zero-coordinate condition needed to choose connected local bases and make the gadget-boundary constant positive.

After the addition of [[dual-distance-excludes-zero-coordinates.md]] and [[tensor-product-preserves-no-zero-coordinates.md]], this node is no longer the main route for the current frontier: the paper's own Theorem 17 distance assumptions already imply the same no-zero-coordinate property deterministically once \(\Delta\) is large enough that \(\delta\Delta\ge 2\).

Dependencies

  • [[connected-basis-for-nonzero-coordinate-code.md]]

Conflicts/Gaps

  • This is a generic-probability statement, not an explicit deterministic construction of the local codes.
  • The argument only addresses the no-zero-coordinate property. It does not replace the paper's distance and robustness conditions.
  • The claim is tuned to the random model of Theorem 18 and does not by itself say that every natural deterministic choice of local codes has the same property. For the current frontier, it is now best treated as a corollary rather than the main gadget lemma.

Sources

  • 10.48550/arXiv.2202.13641