Extracting exactly linear combined codewords #

Blueprint lem:lidt-ldc-extraction, the paper's Step 4 of the proof of lem:ld-soundness for general ldc (ldt.tex, Claims 4 and 5 and the measurements H, G). The simultaneous test with r codewords is reduced to the single-codeword test in K + m variables by combining: a point (x, y) ∈ F^K × F^m is answered by ∑_{j < r} x_j b_j, where b ∈ F^r is the original point answer at y. The single-codeword theorem then returns a measurement R of polynomials g in the K + m variables, consistent with the combined point answers. This file turns R back into a measurement of r-tuples of polynomials in the m original variables.

The extraction #

A polynomial g(x, y) is exactly x-linear (IsXLin) if it is ∑_i x_i g_i(y): every monomial has exactly one x-variable, to the first power. extract reads off (g_1, …, g_r) from such a g and returns 0 otherwise; it is a deterministic relabelling of outcomes, so applied to a projective measurement it gives a projective measurement.

The estimate #

inconsistency_extract_right_le (and _left_le, the extracted measurement on the other party): the extracted tuple, evaluated at a uniform y, disagrees with the original point answer at most (K + m) d / q more often than g(x, y) disagrees with the combined answer at a uniform (x, y). Fix y, the original answer b and the outcome g, and average over x alone --- the Born probabilities do not see x, since the original point measurement is asked y only and R is asked nothing:

if g is exactly x-linear and its extracted tuple is b at y, there is nothing to prove;
if g is exactly x-linear and the tuple differs from b, then x ↦ g(x, y) and the combined answer are two different linear forms, so they agree at a uniform x with probability at most K d / q (pevY_eq_linPoly, then Schwartz--Zippel in K variables, card_agree_le);
if g is not exactly x-linear, a monomial with a forbidden x-part has a nonzero coefficient Q_g, a polynomial in y alone. Where Q_g(y) ≠ 0 the same Schwartz--Zippel step applies; and Q_g(y) = 0 has probability at most m d / q over y, which is paid once per outcome g, weighted by g's total Born weight, because summing the Born probabilities over b removes y (sum_agreeX_le, sum_uniform_badInd_le).

The paper splits the last case the same way (its Claims 4 and 5). The linear-forms case costs K d / q here rather than the paper's 1 / q: the same Schwartz--Zippel lemma serves all three cases, and the difference is absorbed by the final constants.

The partial evaluation #

pevY g y is the coefficient vector, in the K combining variables, of x ↦ g(x, y) (eval_pevY). It is what lets Schwartz--Zippel in K variables be applied with y fixed.

Extracting exactly linear combined codewords #

The extraction #

The estimate #

The partial evaluation #

Polynomials in the combining and original variables #

Schwartz--Zippel at a fixed y #

The operator form #

The extracted measurements, and the three conclusions #

Schwartz--Zippel at a fixed `y` #