claimroutine

Equal-endpoint collisions contribute o(S)

Claim·§5.2 Three fixed pair experiments·inside propUpper score budget for pair experiments

Statement (paper)

The contribution to

D_i

of pairs with equal endpoints, to which the product formula was not applied, is

o(S)

for each

i\in\{Q,P,P\theta\}

. Precisely, it is at most

\frac{2}{d_{Q,\min}}(W_c+\E_\kappa H_q^*)

\frac{2}{d_{P,\min}}(W_c+\E_\mu H_p^*)

, and

\frac{2M}{d_{P,\min}}(W_c+\E_\mu H_p^*)

respectively, and each of these bounds is

o(S)

In plain English

The part of

D_i

coming from pairs with equal endpoints, where the product formula was not applied, is at most

\frac{2}{d_{Q,\min}}(W_c+\E_\kappa H_q^*)

for

Q

\frac{2}{d_{P,\min}}(W_c+\E_\mu H_p^*)

for

P

, and

\frac{2M}{d_{P,\min}}(W_c+\E_\mu H_p^*)

for

P\theta

. Each of these bounds is

o(S)

Why it's here

This disposes of the pairs the product formula cannot handle, so the bound on

D_i

only needs the product-formula part, which gives the

10\delta^2\lambda C_i

term. The collision probability is bounded using the uniform edge marginals and the

M/d(p)

collision bound of the pair-laws lemma. The first-moment bound

\E_\mu H_p^*+\E_\kappa H_q^*=O(S)

from the rare-exceptions lemma, together with

d_{Q,\min}^{-1}=o(1)

from the parameter choice, makes the bounds

o(S)

Classified routine:

A bookkeeping step inside the upper-budget proof. It combines the collision bound from the pair-laws lemma, the first-moment bound E H^* = O(S) from the rare-exceptions lemma, and d_{Q,min}^{-1} = o(1) from the parameter choice.

Uses

lemEdge marginals uniform; P-collision boundedlemChoice of hierarchy parameters K, L, klemRare exceptions: comparison, first moments, joint bounds

Used by

Nothing in the paper

Sources

PaperOpen

Section: §5.2 Three fixed pair experiments
Page: —
Label: —
Line: sections/04-budgets.tex:380

Leannot aligned

Phase 2 aligns this node to a Lean declaration.