The Nyman-Beurling criterion, equivalent to the Riemann hypothesis (RH), is an approximation problem in the space of square integrable functions on $(0,\infty)$, involving dilations of the fractional part function by factors $θ_k\in(0,1)$, $k\ge1$. Randomizing the $θ_k$ generates new structures and criteria. One of them is a sufficient condition for RH 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 generalizes conditions (i) and (ii) that involve a $σ_0\in(1/2,1)$, and imply $ζ(σ+it)\neq 0$ in the strip $1/2<σ\leσ_0<1$. We then identify 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 this context, the difficulty for proving RH is then reallocated in (ii), which heavily relies on the corresponding Gram matrices, for which two remarkable structures are obtained. We show that a particular tuning of the approximating sequence leads to a striking simplification of the second Gram matrix, then reading as a block Hankel form.