# Aggregated Sum (Column) PIP V2

See a better rendering here: [https://hackmd.io/MutGHZgETA6DZlX4hw-WYg](https://hackmd.io/MutGHZgETA6DZlX4hw-WYg)

## Example (Single Column)

Consider the column ${\mathbf{a}} = (51,23,13,17,31)$.

Now, $\langle \mathbf{a}, \mathbf{1} \rangle = 51 + 23 + 13 + 17 + 31$. This is how we did column sums in Proof of Concept. However, for the sake of batchability, we wish to replace all inner products with sumcheck.

For the sake of sanity, we will pad ${\mathbf{a}}$ so that it's length is a power of 2. So, ${\mathbf{a}} = (51, 23, 13, 17, 31, 0, 0,0)$. **It may be advantageous to partition columns based on power's of two for this reason**.

Let $f_{\mathbf{a}}$ be the multilinear extension of ${\mathbf{a}}$; $f_{\mathbf{a}}: \mathbb{F}^{\log(8)} \rightarrow \mathbb{F}$.

Now, $\langle \mathbf{a}, \mathbf{1} \rangle = \displaystyle\sum_{h \in \{0,1\}^3} f_{\mathbf{a}}(h)$. Thus, we can view the sum of a column as a sumcheck.

**Note**: in many of the usage of sumcheck we have that the computed sum is 0. However, the sum of the column may be nonzero. As such, it is necessary to include the claimed sum for each sumcheck proof for batching.

### Structure

Input: ${\mathbf{a}}$
New, output variable: $s \in \mathbb{Z}$ (claimed sum)
Additional constraints: None.

### Security Integrity

Single column SUM inherits perfect completeness and soundness from the sumcheck protocol. We note that the sumcheck protocol has soundness bound $\frac{d\log(n)}{p}$ for $d$ the maximum degree (variable) degree of the polynomial. Since we are using multilinear extensions, then the soundness bound is $\frac{\log(n)}{p}$.

## Example (Expression with Sum)

Consider the Table `table` with columns `A`, `B` and `C`. Also, consider the SQL-query

SELECT SUM(a*b*c+2) FROM table

Note that this query computes the column ``a*b*c+2``. This column has been considered and computed in [Degree 3 Example](https://github.com/spaceandtimelabs/proofs/blob/a6f1af81a45a6b7568633e5eb5fde7caafb1216d/docs/v2/projection-evaluation-protocol.md). We are interested in seeing how these computations get batched downstream with the SUM PIP.

Graphically, our query can be viewed as:

  graph TD;
      A[a * b]-->C[a * b * c];
      C--> D[a * b * c + 2];
      D-->E[SUM];

### Structure

Input: ${\mathbf{a}}, {\mathbf{b}}, {\mathbf{c}}$
New, output variable: $s \in \mathbb{Z}$ (claimed sum)
Additional constraints: None.

## Explicit Numeric Example
Take
- ${\mathbf{a}} = (1,2,3)$
- ${\mathbf{b}} = (2,3,4)$
- ${\mathbf{c}} = (2,1,3)$.

So, $\text{SUM}({\mathbf{a}}\boxtimes {\mathbf{b}} \boxtimes {\mathbf{c}} + {\mathbf{2}}) = 52.$