# Morgenstern's Theorem

Morgenstern proves a $\Omega(n\log n)$ lower bound for Fourier transform in the bounded coefficient model.

Let $x=[x_1,x_2,\ldots,x_n]'$ be given vector and $F$ be Fourier transform matrix.

It is not known if $F(x)$ needs $n\log n$ operations in the unbounded coefficient model when $x_i$'s are treated generically as variables.

Supposing each $x_i$ is an integer bounded by $2^b$, can one show computing $F(x)$ still needs $n\log n$ arithmetic operations in the unbounded coefficient model?

Added: The reason I posted was a few fold. Some questions in the bounded integer $x_i$ model are:

1) We cannot use bit level manipulation on variables $x_i$. However we can do bit level operations on integers $x_i$. Are bit level operations considered valid arithmetic operations when counting the $\Omega(n\log n)$ arithmetic operation?

2) Does one multiplication operation on a word that scales as $O(n)$ bits still count as $1$ arithmetic operation?

3) Is division a valid arithmetic operation?

• I don't see the point of 1: allowing bit level manipulations increases the power of the model, so it can only make lower bounds more difficult to prove. AFAIK, in the straight line program model bit level manipulations are not allowed. Moreover, I think the model Morgenstern uses is in fact a linear circuit, i.e. the value at each gate is a linear function of the input. Jun 22, 2013 at 4:52

Of course if you show a lower bound of $\Omega(n \log n)$ for your question, it would imply the same lower bound for the unrestricted model, which is not known.
On the other hand, you are asking whether it is possible to compute the Fourier transform where each $x_i$ is known within $b$ bits of precision using $\ll n \log n$ arithmetic operations. If true, by the fact that the Fourier transform is a unitary operation (and thus, perfectly conditioned), we would be able to compute Fourier transform of any vector within $b$ bits of precision much faster than FFT, which is certainly not known either.
• Thankyou. The reason I posted was a few fold: 1) We cannot use bit level manipulation on variables $xi$. However we can do bit level operations on integers $xi$. Are bit level operations a valid arithmetic operation when counting the $\Omega(nlogn)$ arithmetic operation? 2) Does one multiplication operation on a word that scales as $O(n)$ bits still count as $1$ arithmetic operation? 3) Is division a valid operation? Jun 21, 2013 at 18:57
• If you normalize everything by a factor of $2^b$, your model becomes equivalent with one where every $x_i$ is in $[0,1]$ and truncated to $b$ bits of precision. Division by a scalar is of course allowed in the straight line program model. Addition and scalar multiplication are considered to have cost $1$. Jun 21, 2013 at 20:36