**Notation:**
*The fold operation:*
Given a polynomial $h$ and $u\in F$ we define

$$fold(h,u)= \bar{u} h_{even}+ u h_{odd},$$
where $\bar{u}=1-u$.
**Crucial relation:**
Given $r,u\in F$ and polynomial $h$, define
$\alpha=h(r), \bar{\alpha}=h(-r)$ and
$\beta = fold(h,u)(r^2)$. Then
$$\beta = \bar{u}\frac{\alpha+\bar{\alpha}}{2} + u\frac{\alpha-\bar{\alpha}}{2r}. $$

In our version of Gemini, we mostly use this equality in the reverse direction deriving $h(r)$ from $h(-r)$ and $fold(h,u)(r^2)$. Precisely, we see from the above equation that
$$ \alpha = \frac{(u-\bar{u}r)\bar{\alpha}+ 2r \beta}{(\bar{u}r + u)} $$

For brevity, we denote below this RHS by
$derive(u,\bar{\alpha},\beta)$

Let $d=\log n$
Given this notation, we can concisely describe our optimized Gemini protocol:
(*Sidenote: I think there are some confusing typos in the version [here](https://hackmd.io/VpdZslmHRy-j11qnkebLnA?view#A-new-folding-argument)*)

Given polynomial $f$ of degree $<n$ and opening point $(u_0\ldots,u_{d-1})$ and the purported value $v=ml(f)(u_0,\ldots,u_{d-1})$
1. We define for each $j \in [d]$ $g_j=fold(g_{j-1},u_{j-1})$
2. $P$ sends commitments to $g_1,\ldots, g_{d-1}$
3. $V$ chooses random $r$
4. $P$ sends for $i\in [d-1]$, $\bar{\alpha}_i=g_i(-r^{2^i})$. And $\bar{\alpha}_0 = f(-r)$.
5. $V$ sets $\alpha_d=v$
6. $V$ derives the values $\alpha_0,\alpha_1,\ldots,\alpha_{d-1}$ going "backwards" via
$$\alpha_i = derive(u_i,\bar{\alpha}_i,\alpha_{i+1})$$
7. Using shplonk $P$ proves to $V$ the correctness of $$f(r)=\alpha_0,f(-r)=\bar{\alpha}_0,g_1(-r^2)=\bar{\alpha}_1,g_2(-r^4)=\bar{\alpha}_2,\ldots,g_{d-1}(-r^{2^{d-1}})=\bar{\alpha}_{d-1}$$

### Soundness issue:
In the above we don't check $\alpha_1,\ldots,\alpha_{d-1}$ using shplonk.

We give an example of why these checks should be added and how we can open to the wrong value.

We use $n=8$ so $d=3$.
We fix any $u=(u_0,u_1,u_2)$.
We take $f=0$.
we show we can successfully open $ml(f)(u)=v$ for any $v$.
It will be convenient to use the notations $g=g_1$, $h=g_2$. Also, to start use a challenge $r'$ and set $r=r'^2$ (so that $g$ is evaluated at $r$ rather than $r^2$)

We set $\alpha_0=\bar{\alpha}_0=\alpha_1=0$,
as an honest $P$ would get when starting with $f=0$.

we'll choose the coefficients of $g,h$ via a system of linear equations so that,
when setting "honestly" $\bar{\alpha}_1=g(r),\alpha_2=h(r^2),\bar{\alpha}_2=h(-r^2)$

we get

$$derive(u_1,\bar{\alpha}_1,\alpha_2)=0=\alpha_1$$

We denote by $g_0,g_1,g_2,g_3$, and $h_0,h_1$ the coefficients of $g,h$ respectively.

Let's set $\alpha=\alpha_1,\beta=\alpha_2,u=u_1$.
We have according to the derive formula:
$$ (\bar{u}r + u)\alpha = (u-\bar{u}r)\bar{\alpha}+ 2r \beta $$

So it suffices for us that

$$(u-\bar{u}r)\bar{\alpha}+ 2r \beta=0$$
Equivalently
$$P(r):=(u-\bar{u}r)g(-r)+ 2r h(r^2)=0$$
Since $r$ is chosen after $g,h$ are committed we want to make $P$ identically zero.
$P$ has degree four, and its coefficients are linear combinations of $g_0,g_1,g_2,g_3,h_0,h_1$.
Explicitly, if $P(X)=P_0 +P_1 X+ P_2 X^2 +P_3X^3 + P_4X^4$ then

calculation shows
$P_0= ug_0, P_1 = 2h_0 - \bar{u}g_0-ug_1$,
$P_2 = \bar{u}g_1+u g_2,P_3=2h_1-\bar{u}g_2-ug_3, P_4= \bar{u}g_3$

To zero out all coefficients of $P$, we can thus set
$g_0=0,g_1=2h_0/u,g_2=-\bar{u}g_1/u= -\bar{u}2h_0/u^2$
$g_3=0, h_1=\bar{u}g_2/2 = -\bar{u}^2 h_0/u^2$

Note that $h_0$ is still a free variable.

We choose $h_0$ so that
$$ \bar{u}_2 h_0 + u_2 h_1 = v$$

$P$ will send commitments to $g,h$, and the "honest" values $\bar{\alpha}_0=0, \bar{\alpha}_1=g(-r) \bar{\alpha}_2=h(-r^2)$

The application of $derive$ by $V$ will set
$\alpha_0=0=f(r')$.

So all shplonk checks will pass. It follows that $V$ will accept the proof for output $v$.

#### Converging to the implemented version (case d=2)
*(Written by Sergei before massive edit of the above, so might be out of context)*

Say $(u_0,u_1)$ is the evaluation point, and $v$ the claimed evaluation $ml(f)(u_0,u_1)$.
Then,
1. $P$ sends a commitment to $g_1$.
1. $V$ sends $r$.
2. $P$ sends the values $\bar{\alpha}_0=f(-r), \bar{\alpha}_1 = g(-r^2)$.
3. $V$ computes
$$\alpha_1 = g(r^2) = \frac{2 r^2 \cdot v - \bar{\alpha}_1 (r^2 (1-u_1) - u_1)}{r^2 ( 1- u_1) + u_1} $$
$$\alpha_0 = f(r) = \frac{2 r\cdot \alpha_1 - \bar{\alpha}_1(r (1 - u_0) - u_0)}{r(1-u_0) + u_0}$$
4. KZG check the values $\alpha_0$, $\bar{\alpha}_0$, and $\bar{\alpha}_1$

Note that the honest prover sends a commitment to
$g=fold(f,u_0):=(1-u_0) f_{even}+ u_0 f_{odd}$