# Optimizing Plookup: The Alternating Method

Multiplicative Subgrup:

$$ H = \{\omega, ... , \omega^{n-1}, \omega^n = 1\} $$

Involved Vectors:

$$ \boldsymbol{f} = (f_1, f_2, \dots, f_{n}) \in \mathbb{F}^n $$

$$ \boldsymbol{t} = (t_1, t_2, \dots, t_n) \in \mathbb{F}^n $$

$$ \boldsymbol{s} = (s_1, s_2, \dots, s_{2n}) \in \mathbb{F}^{2n} $$

We want to prove:

$$ \boldsymbol{f} \subset \boldsymbol{t}. $$

$$ \boldsymbol{s} \text{ is } (\boldsymbol{f}, \boldsymbol{t}) \text{ sorted by } \boldsymbol{t} $$

Let's define the vectors $\boldsymbol{h_1}, \boldsymbol{h_2} \in \mathbb{F}^n$ by:

$$ \boldsymbol{h_1} := (s_{1}, s_3, ...., s_{2n-1}) $$

$$ \boldsymbol{h_2} := (s_{2}, s_4 ...., s_{2n}) $$

Taking $\gamma = 0$ (to visualize an overview), the objective is to define a vector $\boldsymbol{Z}$ such that:
$$
\begin{array}{rcccccl}
\displaystyle
H = \{ & \omega & \omega ^2 & \omega ^3 & \dots & \omega^n &\}\\
& \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \\
\boldsymbol{Z} = \bigg[& 1, &
\frac{(1 + \beta)f_1 (t_1+\beta t_2)}{(s_1+\beta s_2)(s_2+\beta s_3)}, &
\frac{(1 + \beta)^2f_1f_2(t_1+\beta t_2)(t_2+\beta t_3)}{(s_1+\beta s_2)(s_2+\beta s_3)(s_3+\beta s_4)(s_4+\beta s_5)}, & \dots, &
\frac{(1 + \beta)^{n-1}f_1 \dots f_{n-1}(t_1+\beta t_2)(t_2+\beta t_3) \dots (t_{n-1} + \beta t_n)}{(s_1+\beta s_2)(s_2+\beta s_3) \dots (s_{2n-3}+\beta s_{2n-2})(s_{2n-2}+\beta s_{2n-1})} & \bigg]
\end{array}
$$

$$
Z(\omega^i) =
\begin{cases}
1, & \text{if }~ i=1 \\
\frac{\displaystyle (1+\beta)^{i-1} \prod_{j=1}^{i-1}{(\gamma + f_j)} \prod_{j=1}^{i-1}(\gamma(1+\beta) + t_j + \beta t_{j+1})}{ \displaystyle \prod_{j=1}^{i-1}(\gamma(1+\beta) + s_{2j-1} + \beta s_{2j})(\gamma(1+\beta) + s_{2j} + \beta s_{2j+1})}, & \text{if }~ i = 2, \dots, n
\end{cases}
$$

\begin{align*}
Z(X\omega) = Z(X)\frac{(1+\beta)(\gamma + f(X))(\gamma(1+\beta) + t(X) + \beta t(X\omega))}
{(\gamma(1+\beta) + {h_1}(X) + \beta {h_2}(X))(\gamma(1+\beta) + {h_2}(X) + \beta {h_1}(X\omega))}
\end{align*}

## Protocol

1. Prover sends the polynomials $h_1(X), h_2(X)$ to the idealizer.
1. Verifier sends random $\gamma, \beta \in \mathbb{F}$ to the prover.
1. Prover sends $Z(X)$ to the idealizer.
1. Verifier asks to the idealizer for the following checks:

$$ L_1(X) \left( Z(X) - 1\right) = 0 $$

$$ Z(\omega X) {(\gamma(1+\beta) + {h_1}(X) + \beta {h_2}(X))(\gamma(1+\beta) + {h_2}(X) + \beta {h_1}(X\omega))} - \\ - Z(X)(1+\beta)(\gamma + f(X))(\gamma(1+\beta) + t(X) + \beta t(X\omega)) = 0
$$

## Example

$$H = \{\omega, \omega^2, \omega^3\} $$

\begin{array}{l}
\boldsymbol{f} = (f_1, f_2, f_3) \\
\boldsymbol{t} = (t_1, t_2, t_3)\\
\boldsymbol{s} = (s_1, s_2, s_3, s_4, s_5, s_6) \\
\boldsymbol{h_1} = (s_1, s_3, s_5) \\
\boldsymbol{h_2} = (s_2, s_4, s_6)
\end{array}

<!--
By the continous method:
\begin{array}{l}
Z(\omega) = 1 \\
Z(\omega^2) = \displaystyle \frac{(1+\beta)(\gamma + f_1)(\gamma(1+\beta) + t_1 + \beta t_2)}
{(\gamma(1+\beta) + s_1 + \beta s_2)(\gamma(1+\beta) + s_4 + \beta s_5)} \\
Z(\omega^3) =
\displaystyle \frac{(1+\beta)^2(\gamma + f_1)(\gamma + f_2)(\gamma(1+\beta) + t_1 + \beta t_2)(\gamma(1+\beta) + t_2 + \beta t_3)}
{(\gamma(1+\beta) + s_1 + \beta s_2)(\gamma(1+\beta) + s_2 + \beta s_3)(\gamma(1+\beta) + s_4 + \beta s_5)(\gamma(1+\beta) + s_5 + \beta s_6)}
\end{array}

So, to complete the grand-product (which is intended to be completed at $Z(\omega^4) = Z(\omega)$), we only need the factor $(\gamma + f_3)$ in the numerator, and $(\gamma(1+\beta) + s_3 + \beta s_4)$ in the denominator.
-->

By the alternating method:
\begin{array}{l}
Z(\omega) = 1 \\
Z(\omega^2) = \displaystyle \frac{(1+\beta)(\gamma + f_1)(\gamma(1+\beta) + t_1 + \beta t_2)}
{(\gamma(1+\beta) + s_1 + \beta s_2)(\gamma(1+\beta) + s_2 + \beta s_3)} \\
Z(\omega^3) =
\displaystyle \frac{(1+\beta)^2(\gamma + f_1)(\gamma + f_2)(\gamma(1+\beta) + t_1 + \beta t_2)(\gamma(1+\beta) + t_2 + \beta t_3)}
{(\gamma(1+\beta) + s_1 + \beta s_2)(\gamma(1+\beta) + s_2 + \beta s_3)(\gamma(1+\beta) + s_3 + \beta s_4)(\gamma(1+\beta) + s_4 + \beta s_5)}
\end{array}

So, to complete the grand-product (which is intended to be completed at $Z(\omega^4) = Z(\omega)$), we only need the factor $(\gamma + f_3)$ in the numerator, and $(\gamma(1+\beta) + s_5 + \beta s_6)$ in the denominator.

Usign the relation:
\begin{align*}
Z(X\omega) &= Z(X)\frac{(1+\beta)(\gamma + f(X))(\gamma(1+\beta) + t(X) + \beta t(X\omega))}
{(\gamma(1+\beta) + {h_1}(X) + \beta {h_2}(X)(\gamma(1+\beta) + {h_2}(X) + \beta {h_1}(X\omega))}
\end{align*}
we obtain more than these two factors:
\begin{align*}
Z(\omega^4) &= \displaystyle \frac{(1+\beta)^3(\gamma + f_1)(\gamma + f_2)(\gamma + f_3)(\gamma(1+\beta) + t_1 + \beta t_2)(\gamma(1+\beta) + t_2 + \beta t_3)(\gamma(1+\beta) + t_3 + \beta t_1)}
{(\gamma(1+\beta) + s_1 + \beta s_2)(\gamma(1+\beta) + s_2 + \beta s_3)(\gamma(1+\beta) + s_3 + \beta s_4)(\gamma(1+\beta) + s_4 + \beta s_5)(\gamma(1+\beta) + s_5 + \beta s_6)(\gamma(1+\beta) + s_6 + \beta s_1)} \\
&= \displaystyle \frac{(1+\beta)^3(\gamma + f_1)(\gamma + f_2)(\gamma + f_3)(\gamma(1+\beta) + t_1 + \beta t_2)(\gamma(1+\beta) + t_2 + \beta t_3)}
{(\gamma(1+\beta) + s_1 + \beta s_2)(\gamma(1+\beta) + s_2 + \beta s_3)(\gamma(1+\beta) + s_3 + \beta s_4)(\gamma(1+\beta) + s_4 + \beta s_5)(\gamma(1+\beta) + s_5 + \beta s_6)},
\end{align*}
where we have used that $t_3 = s_6$ and $t_1 = s_1$, i.e., the last element of $\boldsymbol{t}$ is equal to the last element of $\boldsymbol{s}$ and the same happens for the first element.

In general, in the case that $\deg(t(X)) = \deg(f(X))$ there will be one more factor $(\gamma + f_j)$ than the rest in the definition of $Z(X)$.
This is the reason why in Plookup $\deg(t(X)) = \deg(f(X)) + 1$.

###### tags: `Plookup`