---
# System prepended metadata

title: evaluation-form-algebra

---

- 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
	
			```rust
				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
			```rust
				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