- the goal is to create a general structure that allows for polynomial composition that is correct, efficient and easy to use
- the immediate use is to represent the f(b, c) polynomial in the [[gkr]] protocol, so I'd start my analysis from there and see if I can generalize later.
- $f(b, c) = add(b, c)(w(b) + w(c)) + mul(b, c)(w(b) \cdot w(c))$
- we can further simplify to
- $f(b, c) = add(b, c)w_1(b, c) + mul(b, c)w_2(b, c)$
- where $w_1(b, c) = w(b) + w(c)$ and $w_2(b, c) = w(b) \cdot w(c)$

- in the very specific case we have three types of polynomials
- unit polynomials - represents a single [[multilinear-extension|mle]].
- sum polynomials - holds a collection of [[multilinear-extension|mle]]s that are assumed to be added to one another.
- product polynomials - holds a collection of [[multilinear-extension|mle]]s that are assumed to be multiplied with one another.

- we are making a tradeoff between full representation (add and multiply everything out) vs [[decomposition]]
- #todo explore the cost model for decomposition vs multiplying out (there is a tradeoff space here).

- rust enums could be used to achieve infinite composition
- see very rough experiment: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=19dcde23b698067275a1ea78f51ba53a

- more importantly, I need to define the constraints when composing

- [[polynomial-composition-constraints]]
- the only identifiable feature of the [[multilinear-extension|mle]]s right now is the number of variables that they have.
- we don't know if two [[multilinear-extension|mle]]s share the same variables (no variable labelling), hence we have to assume.

- [[uniform-variable-constraint]]
- one constraint that could be had is that all [[multilinear-extension|mle]] in the composed polynomial have the same variables
- the following equation fits that:
- $f(b, c) = add(b, c)w_1(b, c) + mul(b, c)w_2(b, c)$
- how do we enforce such a constraint?
- when constructing product, sum or unit, they ensure all the composed polynomials have the same number of variables and they themselves inherit that number.

- NOTE: it is possible to combine polynomials with different variables will just need an extra labelling step to make everything work.
- might also require some kind of compile time formula parsing to make the UX better.
- but for the first version will stick to the [[uniform-variable-constraint]]

- max variable degree calculation (assuming [[uniform-variable-constraint]])
- for unit polynomials the degree is basically 1
- for sum polynomials the degree is the highest degree of the component polynomials
- for product polynomials, the degree is the sum of the degrees of the component polynomials

- methods to implement
- evaluate
- partial_evaluate
- n_vars
- deg
- reduce
- fully evaluates the polynomial (multiply and sum everything out in the [[2HC]]) and returns the final vector
- the [[hypercube|HC]] can be generalized later.