On the pseudorandomness of binary and quaternary sequences linked by the Gray mapping (Q532107)

The Gray mapping provides a correspondence between quaternary sequences on the symbols \(\{1, -1, i, -i\}\) and pairs of binary sequences on the symbols \(\{1, -1\}\). If the quaternary sequence is \(G_N=(g_1, \ldots,g_N)\), the associated binary sequences are given by \(e_n={1\over2}((1-i)g_n+(1+i)\overline{g_n})\) and \(f_n={1\over2}((1+i)g_n+(1-i)\overline{g_n})\). Conversely, \(g_n={1\over2}((1+i)e_n+(1-i)f_n)\). Standard measures of pseudo-randomness for a binary sequence \(E_N=(e_1,\ldots,e_N)\) are the well distribution \[ W(E_N)=\max_{M,u,v} \left| \sum_{j=0}^{M-1} e_{u+jv}\right| \] and the correlation of order \(k\) \[ C_k(E_N)=\max_{M,D}\left| \sum_{n=1}^M e_{n+d_1}e_{n+d_2}\cdots e_{n+d_k}\right| \] where \(D=(d_1,\dots,d_k)\) and \(0\leq d_1<d_2<\ldots<d_k\leq N-M\). There are analogous definitions for quaternary sequences. The authors show how these measures are related. Thus, with explicit constants in the inequalities, \[ W(G_N)\ll \max W(E_N), W(F_N), W(E_NF_N) \ll W(G_N) \] and \[ C_k(G_N)\ll \max C_k(H_1,\ldots,H_k) \ll C_k(G_N) \] where \(C_k(H_1, \ldots, H_k)\) is the cross-correlation of the \(k\) binary sequences in the arguments and the maximum is taken over all \((H_1, \ldots, H_l)\) in \(\{E_N, F_N, E_NF_N\}^k\). Thus a pseudo-random quaternary sequence corresponds to a pair of uncorrelated pseudo-random binary sequences. Some examples are given with \(e_n=\left({g_1(n)\over p}\right)\) and \(f_n=\left({g_2(n)\over p}\right)\) where \(g_1, g_2\) are polynomials over \(\mathbb F_p\), but the appearance of the cross-correlation limit the scope of the application.