PP is strict sign testing for Gap-P

Let a PP machine use exactly $p(\mathrm{\mid }x\mathrm{\mid })$ random bits, padding unused bits if necessary, and let $a(x)$ and $r(x)$ be its accepting and rejecting choice-string counts. Then $g=a-r$ is in GapP by [L1], and $g(x)>0$ exactly when $a(x)>2^{p(\mathrm{\mid }x\mathrm{\mid })-1}$, the strict PP condition in [L2].

Conversely take a GapP machine for $g$, let $f$ count its accepting paths, and let $h$ count its rejecting paths (the latter is a #P count after exchanging final labels), so $g=f-h$. Choose a common polynomial bound $p(\mathrm{\mid }x\mathrm{\mid })$ on the number of binary choices. Encode each original path by its actual choice bits followed by only zeroes to length $p$; reject a nonzero unused suffix. This gives exactly one full-length encoding per original path and does not multiply either count when a branch halts early. Each normalized machine has $2^p$ total full-length paths. Construct a machine with one leading choice: on branch $0$ run the machine for $f$ with its labels unchanged; on branch $1$ run the machine for $h$ with accept and reject exchanged. It has $f(x)+(2^p-h(x))$ accepting paths out of $2^{p+1}$, a strict majority exactly when $f(x)-h(x)>0$.

Steps 1.1 and 1.2 prove the two implications, including the strict zero boundary.