  The Fourier Transform is one of the most important linear transformations
used in science and engineering. Cooley and Tukey's Fast Fourier Transform
(FFT) from 1964 is a method for computing this transformation in time $O(n\log
n)$. From a lower bound perspective, relatively little is known. Ailon shows in
2013 an $\Omega(n\log n)$ bound for computing the normalized Fourier Transform
assuming only unitary operations on two coordinates are allowed at each step,
and no extra memory is allowed. In 2014, Ailon then improved the result to show
that, in a $\kappa$-well conditioned computation, Fourier computation can be
sped up by no more than $O(\kappa)$. The main conjecture is that Ailon's result
can be exponentially improved, in the sense that $\kappa$-well condition cannot
admit $\omega(\log \kappa)$ speedup.
  The main result here is that `algebraic' $\kappa$-well condition admits no
more than $O(\sqrt \kappa)$ speedup. The definition of algebraic condition
number is obtained by formally viewing multiplication by constants, as
performed by the algorithm, as multiplication by indeterminates, giving rise to
computation over polynomials. The algebraic condition number is related to the
degree of these polynomials. Using the maximum modulus theorem from complex
analysis, we show that algebraic condition number upper bounds standard
condition number, and equals it in certain cases. Algebraic condition number is
an interesting measure of numerical computation stability in its own right.
Moreover, we believe that the approach of algebraic condition number has a good
chance of establishing an algebraic version of the main conjecture.
