Fonctions de corrélation des fonctions pseudo-aléatoires. (Correlation functions of pseudo-random functions)
type: Item
instance of: scholarly article
title: Fonctions de corrélation des fonctions pseudo-aléatoires. (Correlation functions of pseudo-random functions)
zbMATH Open document ID: 0714.60042
author: D. Kharzeev
published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques
publication date: 1989-01-01T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/77362
review text: 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…
Mathematics Subject Classification ID: 60G99
Mathematics Subject Classification ID: 60E99
Mathematics Subject Classification ID: 60G10
zbMATH DE Number: 4176133
zbMATH Keywords: pseudo-random functions
zbMATH Keywords: characteristic function
zbMATH Keywords: Fourier transform
reviewed by: Ion Cuculescu
MaRDI profile type: Publication
Recommended article: Q3221618
Recommended article: Q3723392
Recommended article: Correlation functions for random involutions
Recommended article: Q3471273
Recommended article: Pseudorandom correlation functions from variable-density LPN, revisited
Recommended article: Q4255260
Recommended article: Random half-order differential correlation functions
Recommended article: Notes on certain \((0,2)\) correlation functions
Recommended article: Sur la corrélation des fonctions de Piltz. (On the correlation of Piltz' divisor functions)
Recommended article: Q3761394
description: scientific article; zbMATH DE number 4176133