Binary sequences with ideal and small arithmetic correlations

Arithmetic cross/auto-correlation, which is the with-carry analog of classical correlation, is an important figure of merit for pseudorandom sequences. It is desirable that the absolute values of the arithmetic correlations of nontrivial shifts are as small as possible. Sequences have ideal arithmetic correlations if their arithmetic correlations of nontrivial shifts are equal to zero. The work covers two new contributions on the arithmetic cross/auto-correlations of two binary sequences with connection integer \(\varvec{q}\varvec{=}\varvec{p}_{\varvec{1}}^{\varvec{k}_{\varvec{1}}}\varvec{p}_{\varvec{2}}^{\varvec{k}_{\varvec{2}}}\varvec{\cdots } \varvec{p}_{\varvec{t}}^{\varvec{k}_{\varvec{t}}}\) $\mathit{q}\mathbf{=}{\mathit{p}}_{\mathbf{1}}^{{\mathit{k}}_{\mathbf{1}}}{\mathit{p}}_{\mathbf{2}}^{{\mathit{k}}_{\mathbf{2}}}\mathbf{\cdots }{\mathit{p}}_{\mathit{t}}^{{\mathit{k}}_{\mathit{t}}}$ for pairwise distinct odd primes \(\varvec{p}_{\varvec{1}}\varvec{<}\varvec{p}_{\varvec{2}}\varvec{<}\varvec{\ldots }\varvec{ <}\varvec{p}_{\varvec{t}}\) ${\mathit{p}}_{\mathbf{1}}\mathbf{<}{\mathit{p}}_{\mathbf{2}}\mathbf{<}\mathbf{\dots }\mathbf{<}{\mathit{p}}_{\mathit{t}}$ . One is to prove that the absolute arithmetic correlation of two sequences is of order of magnitude at most \(\varvec{q\ln (q)/p}_{\varvec{1}}^{\varvec{1/2}}\) ${\mathit{q}\mathbf{ln}\mathbf{(}\mathit{q}\mathbf{)}\mathbf{/}\mathit{p}}_{\mathbf{1}}^{\mathbf{1}\mathbf{/}\mathbf{2}}$ , by using certain standard exponential sums. This leads to an optimal bound if \(\varvec{q}\) $\mathit{q}$ is an odd prime. The other is to prove that, if there is a common fixed integer \(\varvec{\delta \ge 1}\) $\mathit{\delta }\mathbf{\ge }\mathbf{1}$ satisfying \(\varvec{2}^{\varvec{\delta }}\varvec{|}\varvec{\textrm{ord}}_{\varvec{p}_{\varvec{i}}}\varvec{(2)}\) ${\mathbf{2}}^{\mathit{\delta }}\mathbf{|}{\text{ord}}_{{\mathit{p}}_{\mathit{i}}}\mathbf{(}\mathbf{2}\mathbf{)}$ but \(\varvec{2}^{\varvec{\delta +1}}\varvec{\not \mid \textrm{ord}}_{\varvec{p}_{\varvec{i}}}\varvec{(2)}\) ${\mathbf{2}}^{\mathit{\delta }\mathbf{+}\mathbf{1}}{\mathbf{\nmid }\text{ord}}_{{\mathit{p}}_{\mathit{i}}}\mathbf{(}\mathbf{2}\mathbf{)}$ for all \(\varvec{1\le i\le t}\) $\mathbf{1}\mathbf{\le }\mathit{i}\mathbf{\le }\mathit{t}$ , where \(\varvec{\textrm{ord}}_{\varvec{p}_{\varvec{i}}}\varvec{(2)}\) ${\text{ord}}_{{\mathit{p}}_{\mathit{i}}}\mathbf{(}\mathbf{2}\mathbf{)}$ is the (multiplicative) order of \(\varvec{2}\) $\mathbf{2}$ modulo \(\varvec{p}_{\varvec{i}}\) ${\mathit{p}}_{\mathit{i}}$ , then the sequences have ideal arithmetic correlations. Numerical analysis also supports our results.