Mixing
The (generalized) autocorrelation of the Legendre sequence
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Let $S=s_1,s_2,dots,s_w$ with $s_jin0,1,dots,p-1$ for odd prime $p$. I'd like to calculate the $(w+1)$-body autocorrelation function
beginequation
C(S)=sum_j=0^p-1b_jb_j+s_1b_j+s_2dots b_j+s_w,
endequation
where $b_j=left(fracjpright)$ is the Legendre symbol. A solution for all $w$ would be ideal, but any insight on any of the cases $w>1$ would be helpful.
I'll explain the $w=1$ case (see also Zierler), in which we can evaluate $C(S)$ by a combination of the Wiener-Kninchin theorem and quadratic Gauss sums. Maybe this will give some insight to larger $w$. For the sake of generality, let $b_s$ be any periodic sequence of real numbers with period $p$. Let
beginequation
hat b_t = sum_s=0^p-1b_se^i2pi st/p
endequation
be its Fourier transform. Also, suppose $T=t_1,t_2,dots,t_w$ with $t_jin0,1,dots,p-1$ and define (the $*$ represents complex conjugation or, equivalently, the inverse Fourier transform)
beginequation
F(T)=hat b_t_1+t_2+dots+t_what b^*_t_1hat b^*_t_2dotshat b^*_t_w.
endequation
Then it is easy to show the Fourier transform of $F$ is $C$,
beginalign
hat F(S):=sum_t_1=0^p-1sum_t_2=0^p-1dotssum_t_w=0^p-1F(T)e^i2pi (t_1s_1+t_2s_2+dots t_ws_w)/p=p^wC(S).
endalign
The $w=1$ case of this statement, when $F(t)=|hat b_t|^2$, is the content of the Wiener-Kninchin theorem. Specializing to $b_s=left(fracspright)$ now, Gauss' theorem says
beginequation
hat b_t=bigg{beginarrayllleft(fractpright)sqrtp,&pequiv 1(textmod 4)\ileft(fractpright)sqrtp,&pequiv 3(textmod 4)endarray.
endequation
So $F(t)=|hat b_t|^2=p(1-delta_t0)$ and $C(s)=frac1phat F(s)=pdelta_s0-1$ for the Legendre sequence case.
The difficulty of using this reasoning for $w>1$ on the Legendre sequence is that calculating $hat F(T)$ requires evaluating the Fourier transform
beginequation
sum_t_1=0^p-1sum_t_2=0^p-1dotssum_t_w=0^p-1left(fract_1+t_2+dots+t_wpright)left(fract_1pright)left(fract_2pright)dotsleft(fract_wpright)e^i2pi (t_1s_1+t_2s_2+dots t_ws_w)/p,
endequation
and I don't know how to do so. Doing this would be sufficient to solve my problem.
Thanks folks. Cheers.
algebraic-number-theory signal-processing
asked Jul 31 at 0:01
anthony mann
12
add a comment |Â
up vote
0
down vote
favorite
Let $S=s_1,s_2,dots,s_w$ with $s_jin0,1,dots,p-1$ for odd prime $p$. I'd like to calculate the $(w+1)$-body autocorrelation function
beginequation
C(S)=sum_j=0^p-1b_jb_j+s_1b_j+s_2dots b_j+s_w,
endequation
where $b_j=left(fracjpright)$ is the Legendre symbol. A solution for all $w$ would be ideal, but any insight on any of the cases $w>1$ would be helpful.
I'll explain the $w=1$ case (see also Zierler), in which we can evaluate $C(S)$ by a combination of the Wiener-Kninchin theorem and quadratic Gauss sums. Maybe this will give some insight to larger $w$. For the sake of generality, let $b_s$ be any periodic sequence of real numbers with period $p$. Let
beginequation
hat b_t = sum_s=0^p-1b_se^i2pi st/p
endequation
be its Fourier transform. Also, suppose $T=t_1,t_2,dots,t_w$ with $t_jin0,1,dots,p-1$ and define (the $*$ represents complex conjugation or, equivalently, the inverse Fourier transform)
beginequation
F(T)=hat b_t_1+t_2+dots+t_what b^*_t_1hat b^*_t_2dotshat b^*_t_w.
endequation
Then it is easy to show the Fourier transform of $F$ is $C$,
beginalign
hat F(S):=sum_t_1=0^p-1sum_t_2=0^p-1dotssum_t_w=0^p-1F(T)e^i2pi (t_1s_1+t_2s_2+dots t_ws_w)/p=p^wC(S).
endalign
The $w=1$ case of this statement, when $F(t)=|hat b_t|^2$, is the content of the Wiener-Kninchin theorem. Specializing to $b_s=left(fracspright)$ now, Gauss' theorem says
beginequation
hat b_t=bigg{beginarrayllleft(fractpright)sqrtp,&pequiv 1(textmod 4)\ileft(fractpright)sqrtp,&pequiv 3(textmod 4)endarray.
endequation
So $F(t)=|hat b_t|^2=p(1-delta_t0)$ and $C(s)=frac1phat F(s)=pdelta_s0-1$ for the Legendre sequence case.
The difficulty of using this reasoning for $w>1$ on the Legendre sequence is that calculating $hat F(T)$ requires evaluating the Fourier transform
beginequation
sum_t_1=0^p-1sum_t_2=0^p-1dotssum_t_w=0^p-1left(fract_1+t_2+dots+t_wpright)left(fract_1pright)left(fract_2pright)dotsleft(fract_wpright)e^i2pi (t_1s_1+t_2s_2+dots t_ws_w)/p,
endequation
and I don't know how to do so. Doing this would be sufficient to solve my problem.
Thanks folks. Cheers.
algebraic-number-theory signal-processing
asked Jul 31 at 0:01
anthony mann
12
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let $S=s_1,s_2,dots,s_w$ with $s_jin0,1,dots,p-1$ for odd prime $p$. I'd like to calculate the $(w+1)$-body autocorrelation function
beginequation
C(S)=sum_j=0^p-1b_jb_j+s_1b_j+s_2dots b_j+s_w,
endequation
where $b_j=left(fracjpright)$ is the Legendre symbol. A solution for all $w$ would be ideal, but any insight on any of the cases $w>1$ would be helpful.
I'll explain the $w=1$ case (see also Zierler), in which we can evaluate $C(S)$ by a combination of the Wiener-Kninchin theorem and quadratic Gauss sums. Maybe this will give some insight to larger $w$. For the sake of generality, let $b_s$ be any periodic sequence of real numbers with period $p$. Let
beginequation
hat b_t = sum_s=0^p-1b_se^i2pi st/p
endequation
be its Fourier transform. Also, suppose $T=t_1,t_2,dots,t_w$ with $t_jin0,1,dots,p-1$ and define (the $*$ represents complex conjugation or, equivalently, the inverse Fourier transform)
beginequation
F(T)=hat b_t_1+t_2+dots+t_what b^*_t_1hat b^*_t_2dotshat b^*_t_w.
endequation
Then it is easy to show the Fourier transform of $F$ is $C$,
beginalign
hat F(S):=sum_t_1=0^p-1sum_t_2=0^p-1dotssum_t_w=0^p-1F(T)e^i2pi (t_1s_1+t_2s_2+dots t_ws_w)/p=p^wC(S).
endalign
The $w=1$ case of this statement, when $F(t)=|hat b_t|^2$, is the content of the Wiener-Kninchin theorem. Specializing to $b_s=left(fracspright)$ now, Gauss' theorem says
beginequation
hat b_t=bigg{beginarrayllleft(fractpright)sqrtp,&pequiv 1(textmod 4)\ileft(fractpright)sqrtp,&pequiv 3(textmod 4)endarray.
endequation
So $F(t)=|hat b_t|^2=p(1-delta_t0)$ and $C(s)=frac1phat F(s)=pdelta_s0-1$ for the Legendre sequence case.
The difficulty of using this reasoning for $w>1$ on the Legendre sequence is that calculating $hat F(T)$ requires evaluating the Fourier transform
beginequation
sum_t_1=0^p-1sum_t_2=0^p-1dotssum_t_w=0^p-1left(fract_1+t_2+dots+t_wpright)left(fract_1pright)left(fract_2pright)dotsleft(fract_wpright)e^i2pi (t_1s_1+t_2s_2+dots t_ws_w)/p,
endequation
and I don't know how to do so. Doing this would be sufficient to solve my problem.
Thanks folks. Cheers.
algebraic-number-theory signal-processing
asked Jul 31 at 0:01
anthony mann
12
Let $S=s_1,s_2,dots,s_w$ with $s_jin0,1,dots,p-1$ for odd prime $p$. I'd like to calculate the $(w+1)$-body autocorrelation function
beginequation
C(S)=sum_j=0^p-1b_jb_j+s_1b_j+s_2dots b_j+s_w,
endequation
where $b_j=left(fracjpright)$ is the Legendre symbol. A solution for all $w$ would be ideal, but any insight on any of the cases $w>1$ would be helpful.
I'll explain the $w=1$ case (see also Zierler), in which we can evaluate $C(S)$ by a combination of the Wiener-Kninchin theorem and quadratic Gauss sums. Maybe this will give some insight to larger $w$. For the sake of generality, let $b_s$ be any periodic sequence of real numbers with period $p$. Let
beginequation
hat b_t = sum_s=0^p-1b_se^i2pi st/p
endequation
be its Fourier transform. Also, suppose $T=t_1,t_2,dots,t_w$ with $t_jin0,1,dots,p-1$ and define (the $*$ represents complex conjugation or, equivalently, the inverse Fourier transform)
beginequation
F(T)=hat b_t_1+t_2+dots+t_what b^*_t_1hat b^*_t_2dotshat b^*_t_w.
endequation
Then it is easy to show the Fourier transform of $F$ is $C$,
beginalign
hat F(S):=sum_t_1=0^p-1sum_t_2=0^p-1dotssum_t_w=0^p-1F(T)e^i2pi (t_1s_1+t_2s_2+dots t_ws_w)/p=p^wC(S).
endalign
The $w=1$ case of this statement, when $F(t)=|hat b_t|^2$, is the content of the Wiener-Kninchin theorem. Specializing to $b_s=left(fracspright)$ now, Gauss' theorem says
beginequation
hat b_t=bigg{beginarrayllleft(fractpright)sqrtp,&pequiv 1(textmod 4)\ileft(fractpright)sqrtp,&pequiv 3(textmod 4)endarray.
endequation
So $F(t)=|hat b_t|^2=p(1-delta_t0)$ and $C(s)=frac1phat F(s)=pdelta_s0-1$ for the Legendre sequence case.
The difficulty of using this reasoning for $w>1$ on the Legendre sequence is that calculating $hat F(T)$ requires evaluating the Fourier transform
beginequation
sum_t_1=0^p-1sum_t_2=0^p-1dotssum_t_w=0^p-1left(fract_1+t_2+dots+t_wpright)left(fract_1pright)left(fract_2pright)dotsleft(fract_wpright)e^i2pi (t_1s_1+t_2s_2+dots t_ws_w)/p,
endequation
and I don't know how to do so. Doing this would be sufficient to solve my problem.
Thanks folks. Cheers.
algebraic-number-theory signal-processing
asked Jul 31 at 0:01
anthony mann
12
asked Jul 31 at 0:01
anthony mann
12
asked Jul 31 at 0:01
anthony mann
12
asked Jul 31 at 0:01
anthony mann
12
12
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867524%2fthe-generalized-autocorrelation-of-the-legendre-sequence%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password