Proof that no O(n) multiplication algorithm exists For the multiplication of two $n$ digit numbers, the best known algorithm has complexity $O(n \log n)$. Has it been proven that this is the best possible, or that an algorithm $O(n)$ is not possible?
There is a conditional $\Omega(n\log n)$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.