The Nyman-Beurling criterion, equivalent to the Riemann hypothesis, is an approximation problem in the space of square integrable functions on $(0,\infty)$, involving dilations of the fractional part function by factors $\theta_k\in(0,1)$, $k\ge1$. Randomizing the $\theta_k$ generates new structures and criteria. One of them is a sufficient condition that splits into (i) showing that the indicator function can be approximated by convolution with the fractional part, (ii) a control on the coefficients of the approximation. This self-contained paper aims at identifying functions for which (i) holds unconditionally, by means of polynomial approximations. This yields in passing a short probabilistic proof of a known consequence of Wiener's Tauberian theorem. In order to tackle (ii) in the future, we give some expressions of the scalar products. New and remarkable structures arise for the Gram matrix, in particular moment matrices for a suitable weight that may be the squared $\Xi$-function for instance.