<p>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.</p>

<p>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 <em>any</em> vector within $b$ bits of precision much faster than FFT, which is certainly not known either.</p>

CC BY-SA 3.0
2013-06-21T18:57:15.667Z
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?
Turbo
CC BY-SA 3.0
2013-06-21T20:36:15.750Z
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$.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-06-22T06:44:28.623Z
So multiplication operation on a word that scales as O(n) bits still count as 1 arithmetic operation. Thankyou.

One last question can we include floor and ceil to be one arithmetic operation?
Turbo
CC BY-SA 3.0
2013-06-21T18:45:13.270Z
2013-06-21T18:45:13.270Z
Mahdi Cheraghchi
<p>Morgenstern proves a $\Omega(n\log n)$ lower bound for Fourier transform in the bounded coefficient model.</p>

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

<p>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.</p>

<p>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?</p>

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

<p>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?</p>

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

<p>3) Is division a valid arithmetic operation?</p>

CC BY-SA 3.0
2013-06-22T04:52:37.657Z
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.
Sasho Nikolov
<algebraic-complexity>
Morgenstern's Theorem
Turbo
# Morgenstern's Theorem

(Asked by: username_0 on 2013-06-21)

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?

**Tags:** algebraic-complexity

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-06-21. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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$.  
> **username_0**: So multiplication operation on a word that scales as O(n) bits still count as 1 arithmetic operation. Thankyou.  One last question can we include floor and ceil to be one arithmetic operation?  

---

