Analyzing the number of phases required

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

Theorem 4   The Simple solution uses at most ${\rm OPT}(G)+1$ phases to well-represent a distribution $G\in {\cal PH}_3^-$.

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. If $G\in {\cal T}^{(n)}\cap\left({\cal U}\cup {\cal M}\right)$, then $m_2^G>\frac{n+1}{n}$. Also, if ${G}\in {\cal T}^{(n)}\cap {\cal L}$, then

$$m_2^W = \frac{m_2^G}{2m_2^G-1} > \frac{n+1}{n}.$$

Thus, by (2.6), the EC distribution provided by the Simple solution has at most $n+1$ phases.     width 1ex height 1ex depth 0pt