Theorem 4.1 in Regev's paper talks about a theorem due to Pomerance as follows:

Theorem 4.1: Suppose G is a finite abelian group with minimal number of generators $r$. Then, when choosing elements from $G$ independently and uniformly, the expected number of elements needed to generate G is less than r + σ, where σ = 2.118456563....

Then, Corollary 4.2 is derived from it, which states that $r+4$ uniform and random sample from $G$ is sufficient to generate $G$ with a probability of at least $1/2$. Or the sample is 'likely' to contain the basis for the lattice (group). As per the paper, the proof is as follows:

Proof: Otherwise, with probability at least 1/2, r+ 5 elements are needed to generate G. Since this random variable is never smaller than r by assumption, and its expectation is at least r + 5/2 > r + σ, in contradiction.

I need some help understanding the above-highlighted line.


1 Answer 1


This is just Markov's inequality that states that for a positive random variable $X$ and $a > 0$ then $$ P( X \geq a ) \leq \frac{E(X)}{a}. $$ see the wikipedia: https://en.wikipedia.org/wiki/Markov%27s_inequality.

Now, $a = 5$ and $X$ is the number of elements needed to generate the group minus $r$. Thus,

$$ \frac{5}{2} \leq E(X). $$

If $Y$ is the random variables corresponding to the number of samples needed to generate the group, then $X = Y-r$ and so

$$ \frac{5}{2} + r \leq E(Y). $$

  • $\begingroup$ a small clarification. Based on the last line of your answer, I see a lower bound on E(X) of 'r/2 +5/2'. We need to show a lower bound of 'r+5/2' (the highlighted line in the question). Perhaps I am missing something. Could you make it a bit more precise for me? Thanks!! $\endgroup$ Apr 4 at 17:23
  • 1
    $\begingroup$ Good, point we need to use that $X \geq r$. Let me edit. $\endgroup$ Apr 4 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.