# Polynomial Coefficients and Degree Analysis

This is a guide related to how polynomial operations affect the degree and the coefficients of the resulting polynomial. This guide is meant to provide further understanding specifically to the operations and constraints set in [zk-fhe circuits](https://github.com/enricobottazzi/zk-fhe).

### Polynomial Multiplication

Let's consider the multiplation of two polynomials $F(x) * G(x) = H(x)$. $F$ and $G$ are polynomial of equal degree $n$. Assume that the coefficients of $F$ and $G$ are in the range $[0, Q)$

$F(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_0$
$G(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_{1}x + b_0$

- Polynomial $H$ will have degree $2n$

$H(x) = c_nx^{2n} + c_{n-1}x^{2n - 1} + ... + c_{1}x + c_0$

- The coefficients of $H$ are calculate as follows: $c_k = \sum_{i+j=k} a_i \cdot b_j$The sum is taken over all the pairs $a_i$ and $b_j$ such that the sum of the indexes is equal to $k$

Now, let's determine which $c_k$ will have the most elements in its sum.

- For values of $k$ such that $k < n$ the number of pairs $(i, j)$ such that $i + j = k$ increseas as $k$ increases. This is intuitive because there are more ways to partition a number into two non-negative integers as the number increases.
- For values of $k$ such that $k > n$ the number of pairs $(i, j)$ such that $i + j = k$ decreases as $k$ increases. This is because the maximum value that $i$ and $j$ can take is $n$. So the number of pairs start to decrease. Think of $k = 2n$, in that case there's only one pair which is $(i=n, j=n)$
- At $k=n$ there's the maximum number of pairs $(i, j)$ such that $i + j = k$. Specifically, there are $n+1$ pairs that satisfy this condition.
- Considering that max value that $a_i$ and $b_j$ can take is $Q - 1$ and that $c_{n} = \sum_{i=0}^{n} a_i * b_{n - i}$ $max(c_n) = (Q - 1) * (Q - 1) * (n + 1)$.

### Polynomial Addition

Let's consider the addition of two polynomials $F(x) + G(x) = H(x)$. $F$ and $G$ are polynomial of equal degree $n$. Assume that the coefficients of $F$ and $G$ are in the range $[0, Q)$

$F(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_0$
$G(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_{1}x + b_0$

- Polynomial $H$ will have degree (at most) $n$
- The coefficients of $H$ are calculate as follows: $c_k = a_k + b_k$.
- The max value that a coefficient $c_k$ can take is $max(c_k) = (Q - 1) + (Q - 1)$

### Polynomial Scalar Multiplication

Let's consider the scalar multiplication between a polynomial and a scalar $r \cdot F(x) = H(x)$. $F$ is a polynomial of degree $n$. Assume that the coefficients of $F$ are in the range $[0, Q)$ and that $r$ is in the range $[0, P)$

$F(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_0$

- Polynomial $H$ will have degree (at most) $n$
- The coefficients of $H$ are calculate as follows: $c_k = r \cdot a_k$.
- The max value that a coefficient $c_k$ can take is $max(c_k) = (P - 1) \cdot (Q - 1)$

### Polynomial Division

Let's consider the polynomial division between a polynomial $F(x)$ of degree $2 * n - 2$ and a monic polynomial $G(x) = x^n + 1$ of degree $n$. Assume that the coefficients of $F$ are in the range $[0, Q)$. The division will return a quotient $H(x)$ and a remainder $R(x)$ such that $F(x) = G(x) * H(x) + R(x)$.

- From the previous equation, it is evident that Polynomial $H$ must have degree $m - n$ such that the polynomial multiplication between $G$ and $H$ returns a polynomial of degree $n + m - n = m$
- The degree of the remainder polynomial $R$ is strictly less than the degree of the divisor polynomial $G$. Why is that?
- The process of dividing a polynomial $F$ by another polynomial $G$ involves subtracting multiples of $G$ from $F$ until you get to the remainder $R$. In the process you progressively reduce the degree of the part of $F$ being consider until it is less than the degree of $G$. That's when your remaining part of $F$ is equal to the remainder $R$.
- Also note that the division between two polynomials of degree $m$ and a $n$ such that $m \gt n$ can be always carried and it will result in a non-zero quotient

To analyse the range in which the coefficients of the Polynomial $H$ live, let's analyse how the process of performing [Euclidian Division](https://en.wikipedia.org/wiki/Polynomial_long_division#:~:text=The%20process%20of%20getting%20the,an%20algorithm%20for%20Euclidean%20division) work through an example. This is the polynomial division that I want to perform. As you can see $F$ and $G$ polynomials meet the requirement defined here.


After the first "round" of division this will be the result. As you noticed we already found out the highest degree term of the quotient $H$, this will always be in the range $[0, Q)$ as this is calculated by dividing a number in the range $[0, Q)$ by 1.

The new divided in now a polynomial with a degree one minus the degree of the original dividend. Note that **there can be negative elements** in the divided after one round of division


After the second "round" of division we add a new coefficient to $H$. This, again, will always be in the range $[0, Q)$ as this is calculated by dividing a number in the range $[0, Q)$ by 1.

The new divided in now a polynomial with a degree one minus the degree of the previous dividend. Note that, following the subtraction, a new negative element could have emerged in the new dividend (altough that was not the case).


After the third, and last round of division, we add the last coefficient to $H$ and reduced the dividend by a further degree. Since the degree of the dividend is now less than the degree of the divisor, the division stops and the remaining dividend becomes the remainder.


Throught the division, negative elements appared inside the dividend. More specifically they can appear starting from the coefficient of degree $(2*n-2) - (n) = n-2$ until the coefficient of degree 0. There are the only coefficients that get affected by the subtraction. On the other side the quotient is the result of dividing the leading coefficient of the dividend by 1. As long as this leading coefficient is in the $[0, Q)$ the coefficients of the quotient will always be in the range $[0, Q)$. But the division stops as soon as the dividend hits a degree below the degree of the quotient. In this case the division stops when dividend is a polynomial of degree $n-1$. Because the coefficients that are potentially negative are the ones at the degrees from $n-2$ to $0$ and because the division stops when dividend is a polynomial of degree $n-1$, there will never be the case in which a coefficient of the quotient is the result of dividing a negative number by 1. Therefore we can conclude that the coefficients of the quotient will always be in the range $[0, Q)$.

We can take the same example to analyse the range in which the coefficients of the remainder polynomial $R$ live. As said before, The degree of the remainder polynomial $R$ is strictly less than the degree of the divisor polynomial $G$. So this will be at maximum a polynomial of degree $n - 1$. Coefficients of the remainder polynomial are affected by the subtraction, especially starting from the coefficient of degree $n-1$ until the coefficient of degree $0$. It's worth noting that each of these coefficients only gets affected by a single subtraction during the polynomial division. For example, the coefficient of degree 2 of the dividend polynomial won't be subtracted anymore after the first round of division. In the limit case, the coefficient will be result of subtracting $Q - 1$ by $0$ resulting in $-(Q-1)$. Therefore we can conclude that the coefficients of the remainder will always be in the range $(-Q, Q)$.