Fonctions de corrélation des fonctions pseudo-aléatoires. (Correlation functions of pseudo-random functions) (Q751038)

For f: \([0,\infty)\to C\) and \(\tau\in R\), denote \[ \gamma_{f,f}(\tau)=\lim T^{-1}\int \chi_{[0,T]}(t)f(t+\tau)\overline{f(t)}dt \] for \(T\to \infty\); it is the characteristic function of a measure \(\Phi_ f\) on R when it exists for all \(\tau\). If \(\Phi_ f\) has a density \(\phi_ f\), then f is called pseudo-random. The author gives several examples of finding an f with a given \(\Phi_ f.\) Let h: [0,a]\(\to C\), r: [0,1]\(\to [0,a]\), \(\int r=1\), \(\int h=0\), \(\int | h|^ 2=1\) (Riemann), and let \(z_ n\), \((u_ n,u_{n+k})\) be, for every \(k>0\), ``uniformly distributed'' on [0,1], [0,1]\(\times [0,1]\), respectively; let \(t_{n+1}-t_ n=r(z_ n)\). Then \(f=h(u_ n)\) defines a pseudo-random f on \([t_ n,t_{n+1})\) with \(\gamma_{f,f}(\tau)=\int (r-\tau)\chi_{(r>\tau)}.\) It remains true for some unbounded r, particularly for \(r(z)=-\log z\) and \(z_ n=n\theta (mod 1)\), \(\theta\) being an algebraic irrational. On the other hand, if f is pseudo-random and \(K\in L^ 1\), then K*f is pseudo-random and \(\phi_{K*f}=| \hat K|^ 2\phi_ f\), \(\hat K\) being the Fourier transform. It generalizes, in a certain way, to the case of a distribution K. If \(\theta\) is a quadratic irrational, \(c>0\), \(f=\exp (2i\pi \theta n^ 2)\) on \([n,n+1)\) and \(g(t)=t^{-1}\sin 4\pi \theta ct,\) the author proves that g*f exists. This leads to an h with \(\phi_ h=\chi_{[-b,b]}.\) Finally, if \(| f_ n| \leq 1\), \(\sum | c_ n| <\infty\) and \(\gamma_{f_ n,f_ k}=0\) for all \(n\neq k\), then for \(f=\sum c_ nf_ n\) we have \(\gamma_{f,f}=\sum | c_ n|^ 2\gamma_{f_ n,f_ n}\) etc. If \(P(t)=\theta t^{\alpha}+...\), \(Q(t)=\lambda t^{\beta}+..\). are polynomials of degrees \(\alpha\),\(\beta\geq 2\) with irrationals \(\theta\), \(\lambda\), respectively, and \(f=\exp (2i\pi P(n))\), \(g=\exp (2i\pi Q(n))\) on \([n,n+1)\), then f,g are pseudo-random. Moreover, \(\gamma_{f,g}=0\) if \(\alpha\neq \beta\) or if \(\theta\), \(\lambda\) are arithmetically independent. The author's book ``Fonctions de corrélation, fonctions pseudo-aléatoires et applications'' (1984; Zbl 0557.76053)] is used.