  Under the assumption that some part of the observed highest energy cosmic
rays consists of protons originating from cosmological distances, we derive
bounds on the associated flux of neutrinos generated by inelastic processes
with the cosmic microwave background photons. We exploit two methods. First, a
power-like injection spectrum is assumed. Then, a model-independent technique,
based on the inversion of the observed proton flux, is presented. The inferred
lower bound is quite robust. As expected, the upper bound depends on the
unknown composition of the highest energy cosmic rays. Our results represent
benchmarks for all ultrahigh energy neutrino telescopes.
