BLR acceptance implies agreement with a linear function

Put $h=(-1{)}^f$ and $M={\max }_a\widehat{h}(a)$. The finite nonempty index set has $2^n$ elements, so a maximizing index exists. Parseval and $h^2=1$ give ${\sum }_a\widehat{h}(a{)}^2=1$. Hence ${\sum }_a\widehat{h}(a{)}^3\le M{\sum }_a\widehat{h}(a{)}^2=M$, since each coefficient is at most $M$ and every square is nonnegative. This is a signed maximum, not a maximum absolute value.

If $\alpha$ is the actual acceptance probability, the cubic identity gives $M\ge 2\alpha -1\ge 2\rho -1$. At a maximizing index $a$, $\widehat{h}(a)=\mathbb{E}(-1{)}^{f(x)+a\cdot x}=2\mathrm{Pr}[f(x)=a\cdot x]-1$. Therefore agreement is at least $\rho$. Substituting $\rho =1-\epsilon$ proves the rejection formulation; conversely setting $\epsilon =1-\rho$ in that formulation gives the agreement formulation. These are equivalent parametrizations of a guarantee, not a claim that distance determines acceptance exactly.

For $f={\mathrm{\ell }}_a$, distributivity modulo two gives ${\mathrm{\ell }}_a(x)+{\mathrm{\ell }}_a(y)={\mathrm{\ell }}_a(x+y)$ for every pair, so completeness is perfect. This includes $a=0$ and the sole linear function in dimension zero. At $\rho =1$ or $\epsilon =0$, the guarantee in the previous step likewise gives exact agreement.

If $f$ is farther than $\delta$ from every linear function, its acceptance probability cannot exceed $1-\delta$: otherwise it is greater than $1\mathrm{/}2$, and step 2.1 applied with $\rho =\alpha$ would give distance at most $1-\alpha <\delta$. Independent trials of a fixed function have all-accept probability ${\alpha }^k\le (1-\delta {)}^k$. Taking complements proves the repetition bound. For $k=0$ the always-accept empty repetition has rejection probability zero, equal to the bound; for $k=1$ this is the single-test bound.