- assumes [[pairing-index]]

- Adding new variables to a multilinear polynomial
- added variables should have co-efficient 0, meaning they don't affect the evaluation result, they just increase the domain.

- general idea
- adding a new variable means adding a new direction.
- to add a new direction, you duplicate the current space and only changing the bit at the new direction index
- this is exactly equal to the formulation of pairing index.
- this means the pairing index will tell you how to duplicate elements in the new space.

- algorithm
- initialize new space with all zeros
- generate the pair in the direction of the newly inserted variable
- each pair corresponds to each element of the old evaluation array respectively
- each element in the old evaluation array will be copied into both positions indicated by the pairing index

				fn add_var(old_eval, index) {
					let mut result = vec![0; new_eval_len];
					for (i, (left, right)) in pair_index.enumerate() {
						result[left] = old[i];
						result[right] = old[i];
					}
				}

- example
- we have $f(a, c) = 2a + 3c$ and we want to add new direction b
- evaluation array for $f(a, c)$ = [0, 3, 2, 5]
- zero initialized result array for $f(a, b, c)$ = [0, 0, 0, 0, 0, 0, 0, 0]
- pairing index for $f(a, b, c)$ in direction of b:
- 0 -> 2
- first element in old should be mapped to 0 and 2 in new
- 1 -> 3
- next element in old should be mapped to 1 and 3 in new
- 4 -> 6
- 5 -> 7
- assuming we want to update (0, 2)
- result[0] = old[0]
- result[2] = old[0]
- we can repeat this for all pairs
- we get the following: [0, 3, 0, 3, 2, 5, 2, 5]
- check our work
- f(a, b, c) = 2a + 0b + 3c
- evaluated over the boolean hypercube we have:
- [0, 3, 0, 3, 2, 5, 2, 5] (exactly matches our computed result)

- adding variables with co-efficients
- if we see adding variables as duplicating faces and putting them in the same direction
- then a zero coefficient variable addition represents duplicating but putting them on top of one another hence no difference in var = 0 or var = 1
- to add the variable with a coefficient, we need to add the coefficient to every node in the new face

- algorithm
- same as adding single variable, but the copy should add the coefficient

				fn add_var(old_eval, index, coefficient) {
					let mut result = vec![0; new_eval_len];
					for (i, (left, right)) in pair_index.enumerat() {
																	result[left] = old[i];
						result[right] = old[i] + coefficient;
					}
				}

- example
- f(a, b) = 2a + 4b
- evaluation_array = [0, 4, 2, 6]
- we want to add 5c to get $f(a, b, c) = 2a + 4b + 5c$
- expected_evaluation_array = [0, 5, 4, 9, 2, 7, 6, 11]
- pairing index for $f(a, b, c)$ in direction c
- [(0, 1), (2, 3), (4, 5), (6, 7)]
- for (0, 1)
- copy first element from evaluation array in index 0
- copy to index 1 but add coefficient 5
- do the same for all other pairs
- result = [0, 5, 4, 9, 2, 7, 6, 11]
- matches the expected evaluation array

- another approach is to extend $f(a, b)$ to $f(a, b, c)$ but set c to have coefficient 0
- then create another polynomial for the term you want to add e.g. 5b -> [0, 5]
- extend this polynomial to have the same shape as your target $f(a, b, c)$ by adding 0a and 0c
- then do element wise addition to get the target.
- e.g.
- $f(a, b) = 2a + 4b$ = [0, 4, 2, 6]
- extend to c
- $f(a, b, c)$ = [0, 0, 4, 4, 2, 2, 6, 6]
- $f(c)$ = 5c = [0, 5]
- extend to $f(b, c)$ = [0, 5, 0, 5]
- extend to $f(a, b, c)$ = [0, 5, 0, 5, 0, 5, 0, 5]
- result
- [0, 0, 4, 4, 2, 2, 6, 6] + [0, 5, 0, 5, 0, 5, 0, 5] = [0, 5, 4, 9, 2, 7, 6, 11]
- same result

- Addition, Multiplication of evaluation form multilinear polynomials
- to add or multiply two evaluation form multilinear polynomials, figure out the target function signature.
- move both operands to that target signature, then just apply the operation element wise.
- example
- $f_1(a) = 6a$ [0, 6] and $f_2(a, b) = 4a + 5ab$ [0, 0, 4, 9]
- the expected result should be $f_r(a, b) = 10a + 5ab$
- with the following expected evaluation array: [0, 0, 10, 15]
- the target function signature is $f(a, b)$
- so we move $f_1(a)$ to $f_1(a, b)$
- [0, 0, 6, 6]
- $f_2(a, b)$ is already in target signature
- now we can just do element wise addition to get the target result
- [0, 0, 6, 6] + [0, 0, 4, 9] = [0, 0, 10, 15]
- same as the expected.

- for multiplication, to remain multilinear then the operands must not share common variables
- $f(a, b) \cdot f(c, d)$ -> $f(a, b, c, d)$
- $f(a, b) \cdot f(b, c)$ will not result in a multilinear target because b will be a power of 2 i.e $b^2$

- Adding multiple variables at once
- if we see the pairing index as instructions for duplication, adding multiple variables at once means we need to compose instructions.
- [ ] compare the running time of repeated variable insertion vs at once
- we could do this via instruction rewrites I believe
-

- Dealing with space complexity when we add more variables