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.

Improve this question
$\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$
    – Gerry Myerson
    Commented 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
    Commented 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$
    – Gerry Myerson
    Commented 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$
    – Joe Silverman
    Commented 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$
    – Felipe Voloch
    Commented May 9, 2019 at 22:08

1 Answer 1

Reset to default
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}$.

Improve this answer
$\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
    Commented 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
    Commented May 10, 2019 at 3:29
  • $\begingroup$ Thank you so much. $\endgroup$
    – bogner
    Commented May 10, 2019 at 3:43
  • $\begingroup$ @bogner can you accept the answer if it is satisfactory $\endgroup$
    – kodlu
    Commented May 10, 2019 at 4:44
  • $\begingroup$ Begging is unbecoming, kodlu, especially so soon. $\endgroup$
    – Gerry Myerson
    Commented May 10, 2019 at 6:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .