Analyzing the number of phases required

The number of phases used in the Positive solution is characterized by the following theorem.

Theorem 7   The Positive solution uses at most ${\rm OPT}(G)+1$ phases to well-represent any distribution $G\in {\cal U} \cup \widehat{\cal M} \cup \left\{F \Big\vert r^F \neq \frac{3}{2} \mbox{ and } m_3^F < 2m_2^F - 1\right\}$.

Proof:Since $S^{(n)}\subset {\cal T}^{(n)}$ (by Lemma 1), it suffices to prove that if a distribution $G\in {\cal T}^{(n)}$, then at most $n+1$ phases are needed. When an input distribution $G\in {\cal U} \cup \widehat{\cal M}$, the Positive solution is the same as the Complete solution, and hence requires the same number of phases, which is at most ${\rm OPT}(G)+1$. When $G\in\left\{F \Big\vert r^F > \frac{3}{2} \mbox{ and } m_3^F < 2m_2^F - 1\right\}$, the number of phase used in the Positive solution is $2=\mbox{OPT}(G)$. When $G\in\left\{F \Big\vert r^F < \frac{3}{2} \mbox{ and } m_3^F < 2m_2^F - 1\right\}$, it is immediate, from the construction of the solution, that the Positive solution requires at most one more phase than the Complete solution. For this $G$, the Complete solution requires ${\rm OPT}(G)$ phases, and hence the Positive solution requires ${\rm OPT}(G)+1$ phases.     width 1ex height 1ex depth 0pt