Using your Head is Permitted

Various autopilot software (subways, cars, planes...) use error detecting systems, to avoid being fooled by accidental data corruption.

For example, an integer X can be coded with two fields (x, r), with r = kx mod A for some integers k and A. X is valid if (kx - r) mod A = 0.

Suppose x is altered by an error (but not r) and becomes (x + e): this error won't be detected if k(x + e) - r mod A = ke mod A = 0, which amounts to e mod A = 0 if we wisely take k co-prime with A. So the general assumption is that such systems have probability 1/A of not detecting a random error.

Serge is wondering what this means regarding the distribution of e, the "random errors", over the naturals, if such assumptions were to hold regarding all possible choices of A>1. Let p(A) be the probability that e is not detected in modulo A, given that it is polled from a specific distribution, D, over the naturals. What distributions will satisfy p(A)=1/A exactly? Can an adversary design a distribution that will always satisfy p(A)≪1/A? Can an adversary design a distribution that will always satisfy p(A)≫1/A?

To make these questions more concrete, let f(x) and g(x) be two monotone strictly decreasing functions over the naturals such that for all x, 0<f(x)<1 and 0<g(x)<1, and when x tends to infinity f and g both tend to zero.

Answer all of the following questions with proof.

1. For which f(x) can you design a distribution for e such that for all A>1, p(A)≤f(A)?
2. For which g(x) can you design a distribution for e such that for all A>1, p(A)≥g(A)?
3. Can you design a distribution for e such that for all A, p(A)=1/A?

List of solvers: