---
# System prepended metadata

title: Folding Linearly Dependent Rel

---

## Folding Linearly Dependent Relations

Mara's attempt at explaining it

Originally the two main polynomials of Protogalaxy F and G (perturbator and combiner) are defined as follows:

$F(X) = \sum_{i \in \{0,\ldots,n-1\}} pow_i(\vec{\beta} + X\vec{\delta})f_i(\omega)$

$G(X) =  \sum_{i \in \{0,\ldots,n-1\}} pow_i(\vec{\beta*})f_i(L_0(X)\omega + L_1(X)\omega_1)$


Here we are in the case where $k=1$. $\omega$ is part of the relaxed instance (accumulator)  and $\omega_1$ is an instance produced from an actual circuit. We want to fold $\omega_1$ with the accumulator $\omega$. Also note that $pow_0(\vec{\beta}) = 1$ for any vector $\vec{\beta}$. 

Until now we viewed $f_i$ to represent the UGH relation at row $i$ in the execution trace. UGH is the sum of all the subrelations we use, batched by some challenges. This works when we only deal with linearly independent relations but becomes problematic when we fold something with both linearly independent and linearly dependent relations.

The $f_i$ are actually meant to be viewed as Protogalaxy constraints (insert better name).. so in the case of UGH instances the linearly dependent relation is a unique f_i by itself. 

Let's call the linearly dependent relation on $\omega$,  $g(\omega)$ and then we have $f_i(\omega)$, $i=0,..,n-1$ where $f_i$ is $UGH_i$ is the UGH relation applied at row $i$ . Note that I start $i$ from 0 to be consistent with the execution (i.e. row $i$ represents evaluations at point 0 in the boolean hypercube).

Then the two PG polynomials become

$F(X) = pow_0(\beta)g(\omega) + \sum_{i\in \{0,..,n-1\}} pow_{i+1}(\vec{\beta} X + \vec{\delta})f_i(\omega)$

$G(X) = pow_0(\beta*)g(\omega) + \sum_{i \in \{0,\ldots,n-1\}} pow_{i+1}(\vec{\beta*})f_i(L_0(X)\omega + L_1(X)\omega_1)$

The $i+1$ is on purpose

**Problem:** now we need an extra term of $pow$ 

**Naive Solution:**

If we have an accumulator of fixed size 

