I have a polynomial of known degree $n$ with initial numerical coefficients $a$ set to $0$ or $1$

such as: $p= a_nx^n +a_{n-1}x^{n-1}+...+ ax +a_0$

I have to perform a series of computations by adding, subtracting or multiplying to this polynomial other polynomials with the same properties. It is also possible to square these.

Given that the computation to perform is fixed, I would like to know which is the maximum infinity norm of the polynomial reached throughout all the computation, without making any assumption about the initial values $a$ of $p$.

What I want really know is if it's possible to compute such a value without brute-forcing the coefficients' values. My guess is that it isn't possible since the problem may be similar to SAT, but I would like to get a formal proof.

For example: we have $n=2,\ p=a_2x^2 +a_1x + a_0$ and we want to add the polynomial $x+1$. The result of the computation will be $\ a_2x^2 +(a_1+1)x + (a_0+1)$. After this, we compute a square. The result is the following: $a_2^2x^4 + 2a_2(a_1+1)x^3+((a_1+1)^2+2a_2(a_0+1))x^2 + 2(a_1+1)(a_0+1)x + (a_0+1)^2 $. Now we can subtract $a_0x^2 + a_2$ and we get $a_2^2x^4 + 2a_2(a_1+1)x^3+((a_1+1)^2+2a_2(a_0+1)-a_0)x^2 + 2(a_1+1)(a_0+1)x + (a_0+1)^2-a_2 $.

It is possible to observe that computing the maximum infinity norm at the end of the computation is not trivial as at the beginning: $a$ coefficients start to entwine making the problem hard. At the last step the only solution seems to try all the combinations of $a$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.