Separating the two point variables (lem:qld-global-separate) #
An outcome g = α g₁ + β g₂ of the global measurement that is linear in the combining
coordinates (IsLinAB, lem:qld-global-linear) is good when g₁ reads only the x block and
g₂ only the z block: g = α g_X(x) + β g_Z(z) (IsGood). This file bounds the weight of the
linear outcomes that are not good, from the two ordered-product estimates of
lem:qld-global-products: the order X_a Z_b controls the outcomes whose g₂ reads a coordinate
outside the z block, and the order Z_b X_a those whose g₁ reads a coordinate outside the x
block.
The argument #
For a linear outcome and a base point u₀, the fibre {αa + βb = α g₁(u₀) + β g₂(u₀)} always
contains the diagonal pair (g₁(u₀), g₂(u₀)), and contains any other pair for at most q of the
q² values of (α, β). So the average over (α, β) of ‖(S ⊗ B_u(g(u))) Φ‖² is at most
2/q · ⟨S⟩ + W(g₁(u₀), g₂(u₀)), with W(a, b) = ‖(S ⊗ X_a Z_b) Φ‖² ≤ ⟨S ⊗ Z_b⟩. Averaging over
u₀, read as a uniform z block with the other coordinates uniform and independent
(sum_uniform_mixOn): for fixed z, u ↦ g₂(u) is a polynomial in the other coordinates
(LowIndDegPoly.restrictOff) which, if g₂ reads a coordinate outside the z block, is
non-constant except for a set of z of probability at most 4md/q (Schwartz--Zippel on a
nonzero coefficient), and where it is non-constant each value b is taken with probability at
most 4md/q, so E ⟨S ⊗ Z_{g₂(u)}(z)⟩ ≤ 8md/q · ⟨S⟩. Altogether
E_u ‖(S ⊗ B_u(g(u))) Φ‖² ≤ η ⟨S⟩ with η = (2 + 8md)/q, and the assembly of
lem:qld-global-linear gives (1 - 2η) · (weight of these outcomes) ≤ 2Δ. The other block is
the mirror image, with the roles of (X, a, α) and (Z, b, β) exchanged.
Stated in a bipartite model #
Stated in a bipartite model (Phase 5 of planning/mipco-track.md). As in
MIPRE/Background/QLD/Linear.lean, the state is that of a bipartite model K (the model in which
the low individual degree test is applied, padModel, or any other), the outcome G_g is a
projection of the first player's algebra, the families X, Z are projective measurements of the
second player's, G_g ⊗ D is K.πA (G.op g) * K.πB D, and the expectations ⟨S ⊗ D⟩ are Born
probabilities K.bornProb S D. The diagonal weight bound Z X Z ≤ Z holds in any star-ordered
ring, Z (1 - X) Z being a conjugate of a nonnegative element. The polynomial half is unchanged.
Coefficient vectors: constants, differences, restriction to a block #
The constant coefficient vector.
Instances For
Substituting the coordinates in T by those of z: the coefficient vector, in the
variables off T, of u ↦ g(z on T, u off T).
Instances For
The restricted vector evaluates as g at the point with the T coordinates from z.
Dependence on a coordinate outside T: some monomial of g has a nonzero exponent off
T.
Instances For
A vector depending on a coordinate off T has a nonzero coefficient vector at a nonzero pattern
supported off T.
Exchanging a block of coordinates #
The point with the coordinates in T taken from u' and the others from u.
Instances For
A uniform point is a uniform block with the other coordinates uniform and independent.
The positions of the z block.
Equations
Instances For
The positions of the x block.
Equations
Instances For
The two coefficient polynomials of a linear outcome #
The coefficient of α in an outcome: a polynomial in the coordinates other than α, β.
Equations
- MIPRE.QLD.gA hd g = g.coef MIPRE.QLD.abSet (MIPRE.QLD.patAB (MIPRE.QLD.oneD hd) 0)
Instances For
The coefficient of β in an outcome.
Equations
- MIPRE.QLD.gB hd g = g.coef MIPRE.QLD.abSet (MIPRE.QLD.patAB 0 (MIPRE.QLD.oneD hd))
Instances For
A linear outcome read at the combining coordinates is the linear form of its two coefficients.
The good outcomes: g = α g_X(x) + β g_Z(z), with g_X reading only the x block and
g_Z only the z block.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- One or more equations did not get rendered due to their size.
A linear outcome whose coefficient of α reads only the x block and whose coefficient of
β reads only the z block is good.
An outcome that is not good is not linear, or is linear with a coefficient reading a coordinate outside its block.
The linear fibre and the diagonal weight #
The diagonal weight: ‖(S ⊗ X_a Z_b) Φ‖² = ⟨S ⊗ Z_b X_a Z_b⟩ ≤ ⟨S ⊗ Z_b⟩.
The linear fibre: for the linear form α a₀ + β b₀, the fibre always contains the diagonal
pair (a₀, b₀), and any other pair for at most q of the q² values of (α, β); so the average
over (α, β) of the fibre weights is at most 2/q · ⟨S ⊗ 1⟩ plus the diagonal weight.
Conditioning on a block, the two averages and the assembly #
Conditioning on a block: if Op reads only the coordinates in T and the polynomial H
reads some coordinate outside T, then E_u ⟨S ⊗ Op_u(H(u))⟩ ≤ 8md/q · ⟨S ⊗ 1⟩: for fixed T
coordinates, H is a non-constant polynomial in the others except with probability 4md/q, and a
non-constant polynomial takes each value with probability at most 4md/q.
A linear outcome against the order X_a Z_b: the fibre contributes 2/q · ⟨S ⊗ 1⟩
beyond its diagonal pair, whose weight is at most E_{u₀} ⟨S ⊗ Z_{g₂(u₀)}(z)⟩.
A linear outcome whose β coefficient reads a coordinate outside the z block, against
the order X_a Z_b: E_u ‖(S ⊗ B_u(g(u))) Φ‖² ≤ (2 + 8md)/q · ⟨S ⊗ 1⟩.
A linear outcome against the order Z_b X_a: the mirror image, with the roles of
(X, a, α) and (Z, b, β) exchanged.
A linear outcome whose α coefficient reads a coordinate outside the x block, against
the order Z_b X_a.
The assembly, abstractly: if every bad outcome has E_u ‖(G_g ⊗ B_u(g(u))) Φ‖² ≤ η ⟨G_g⟩
and the products estimate ∑_g E_u ‖(G_g ⊗ (1 - B_u(g(u)))) Φ‖² ≤ Δ holds, then
(1 - 2η) · (weight of the bad outcomes) ≤ 2Δ.
lem:qld-global-separate, abstract form. With η = (2 + 2d + 8md)/q, if the two
ordered-product estimates hold with bounds Δ₁ (order X_a Z_b) and Δ₂ (order Z_b X_a),
then (1 - 2η) · (weight of the outcomes that are not good) ≤ 2Δ₁ + 2Δ₂.