I am wondering whether I can get the upper bound in closed form of


$$\sum\_{n=1}^N(\alpha \exp(j2\pi n/N)) \text{ where } \alpha = +1\text{ or }-1 \text{ and } j^2=-1.$$


If alpha is just positive one, this would be just a single value,


but I'm trying to get the upper bound when alpha is $+1$ or $-1$, randomly,


while the total amount of $+1$ and $-1$ is different at most $1.$ ($N/2$ or $N/2+1$)


I have looked for exponential sums materials, but can't see things like this.




---


edit : $\alpha $ is generated by LFSR, so it holds pseudo randomness property.  

 or equivalently, it is a maximal length sequences.



Upper bound of signed exponential sums
Let the maximum length sequence $$s\_n=(-1)^{Tr(\beta \alpha^n)}$$have period $2^m-1,$ and be nontrivial with $\beta\neq0.$ Your sum is
$$\Gamma(m,N)=\sum\_{n=1}^N s\_n \exp(2 \pi i n/N).$$


If $\beta=0,$ you have the standard unmodulated linear exponential sum with the bound 
$$\min\left\{N,\frac{1}{|\sin \pi/N|}\right\}.
$$


If $N\leq m,$ all possible $N-$tuples in $\{\pm 1\}^N$ are taken on by 
$$(s\_n,\ldots,s\_{n+N-1})$$ so a better bound is not possible.


**Edit:** In the intermediate range $m<N\leq 2^m-1,$ a bound along the lines suggested by @FelipeVoloch is indeed possible.


From Theorem 8.78 in the book Lidl and Niederreiter, *Finite Fields (Encyclopedia of Mathematics and its Applications*, we have
$$
|\Gamma(m,N)|\leq \sqrt{2^m},
$$
which is nontrivial if $N>\sqrt{2^m}$.


