Introduction
Karatsuba gave the optimal way for multiplying two polynomials of degree 1. He reduced the number of multiplications from 4 to 3.
Let the imput for f be the degree of a polynomial and the output the number of multiplications needed to multiply two such polynomials.
Thus
$$f(1)=3$$
And by iterating
$$f(2n−1)=<3n$$ That is karatsuba's result.
I recently discovered $f(2)$ is at most $6$. ( see answer at Optimal multiplying method )
I learned much about $f$ however ...
Questions
Let $g$ be the best algoritm to multiply 3 polynomials of degree $a,b,c$ and $f(u,V)$ the best algoritm to multiply 2 polynomials of degree $u,V$.
Conjecture 1
$f(u,V)$ is given by the same formula's for the $f( \max (u,V) ) $ but then by filling in the 0 coefficients the result is reduced and the number of multiplications is then optimal ( optimal reduced ).
Is the following pessimistic conjecture true ?
Conjecture 2
$$ g(a,b,c) = f(a,f(b,c)) = f(b,f(a,c)) = f(c,f(a,b))$$
Conjecture 3
If degree $a $ = $ b + c$ is then conjecture 2 true ?
Conjecture 4
$$g(a,b,c) = \min f(a,f(b,c)) , f(b,f(a,c)) , f(c,f(a,b))$$
Conjecture 5
Combining conjecture 3 and 4.
--- edit---
Conjecture 1 is completely false !! To my surprise !!
Seems conjecture 1 was too optimistic. Is conjecture 2 too pessimistic ??
--- edit 2 ---
Added conjectures 3,4,5.