1
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ Draw a line through the origin, take $\alpha$ to be plus one for all exponentials on one side of the line, minus one for all exponentials on the other side. $\endgroup$ May 9, 2019 at 12:15
  • $\begingroup$ Right, that would be the upper bound, but I forgot to mention that alpha follows pseudo random properties. My apologize... $\endgroup$
    – bogner
    May 9, 2019 at 12:21
  • $\begingroup$ You'll have to tell us what you mean by "pseudorandom properties" then. If I flip a coin 100 times, and it comes up heads the first 50 and tails the last 50, is that pseudorandom? Why? Why not? It's just as likely as any other outcome. $\endgroup$ May 9, 2019 at 12:24
  • 1
    $\begingroup$ The best upper bound for the magnitude is the one that Gerry indicated. The expected value of the squared magnitude is $N$, since it's a random walk consisting of $N$ unit steps. The variance is fairly large, so you'll "often" be larger or smaller by a significant amount. In any case, you might look up "random walks". (What is the $j$ in your formula? You'll get better answers if you formulate your problem more clearly.) $\endgroup$ May 9, 2019 at 12:45
  • 1
    $\begingroup$ If your $\alpha$'s come from a LFSR, then your sum is something like $\sum (-1)^{Tr (\beta \gamma^n)} e^{2\pi i n/N}$ where Tr is the trace on a finite field extension of $\mathbb{F}_2$. I've seen similar sums in papers by I. Shparlinski (that doesn't narrow it down very much :-) ). Maybe you can ask him. $\endgroup$ May 9, 2019 at 22:08

1 Answer 1

1
$\begingroup$

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}$.

$\endgroup$
5
  • $\begingroup$ It is a quite tight bounds, great! Actually, my final goal is to get the bounds when $s_n$ is a cross-correlation of a ML-sequences and a reciprocal version of it, which is a reversed ML-sequences. In this case, $s_n$ is not a ML-sequences, but there are some papers derived the bounds of cross-correlation of those two, it's just not a exponential sums. 'Cross-Correlations of Reverse Maximal-length Shift Register Sequences', J. A. Dowlingl and R. McHiece, but would it be possible to get a bounds of it? $\endgroup$
    – bogner
    May 10, 2019 at 2:53
  • $\begingroup$ @bogner, tour suggested problem is interesting. I might have a look if I get a chance. $\endgroup$
    – kodlu
    May 10, 2019 at 3:29
  • $\begingroup$ Thank you so much. $\endgroup$
    – bogner
    May 10, 2019 at 3:43
  • $\begingroup$ @bogner can you accept the answer if it is satisfactory $\endgroup$
    – kodlu
    May 10, 2019 at 4:44
  • $\begingroup$ Begging is unbecoming, kodlu, especially so soon. $\endgroup$ May 10, 2019 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.