# Generating a group by randomly sampling generators

Let $G$ be a finite abelian group, $n$ a positive integer and let $G^n$ denote the direct product of $n$ copies of $G$. We say an element of $G^n$ is full if it acts as a nonidentity element of $G$ in each of the factors of $G^n$.

Now consider the following random process. Sample a full group element $(g_1,g_2,\ldots,g_n)$ uniformly at random from $G^n$. Now generate a subgroup $H$ of $G^n$ consisting of all elements of the form $\bigl(g_1^{a_1},\ldots,g_n^{a_n}\bigr)$ for integers $a_i$. If we do this $k$ times (sampling with or without replacement, more on this below), then we can let $H_j$ denote the subgroup generated on the $j$th iteration. Now we take the union of these subgroups and define $$N_k = \left| \bigcup_{j=1}^k H_j \right| \ ,$$ where $|\cdot|$ denotes the cardinality of the set. Finally, let $\mu_k = \mathbb{E}(N_k)$.

When $G$ is also a simple group, this is easy to calculate. So let's specialize to the simplest nontrivial case, $G = \mathbb{Z}/2 \times \mathbb{Z}/2$. (The other simplest case is $\mathbb{Z}/4$, but I'm not as interested in that one.) Then my question is,

How does $\mu_k$ grow as a function of $k$?

I am principally interested in lower bounds on $\mu_k$ in the case where the sampling is done uniformly without replacement on the set of full elements of $G^n$. Clearly sampling with replacement gives a lower bound, and it's much easier to work with. If you can say something about the variance of $N_k$ too, that would be outstanding.

-
When G is cyclic of prime order, it is easy to calculate. What is the calculation for G cyclic of order pq, where p and q are primes (you may restrict to those p and q which guarantee that a group of order pq is cyclic)? Gerhard "Ask Me About System Design" Paseman, 2012.05.23 – Gerhard Paseman May 23 '12 at 21:20
You know, I am even willing to see only the calculation for G=Z_4. Gerhard "Willing To Compromise On Groups" Paseman, 2012.05.23 – Gerhard Paseman May 23 '12 at 21:24
@Gerhard, yes, you're right. I meant simple, sorry. Fixed. – Steve Flammia May 23 '12 at 21:44

Stupid lower bound: Sampling without replacement, it is obvious that $N_k\geq k$.

Why this bound may be close to optimal: If $g$ is a full element of $G^n$, then $g$ is only contained in the subgroup $H$ "generated" by $h$ if $g=h$. This gives an upper bound:

$(4^n-\mu_k)\leq (3/4)^n (4^n-k)$

We can get more accurate, but much more painful bounds as follows: Let $f: G^n \to \mathbb N$ for a given $g\in G^n$ be the number of $h\in G^n$ that generate $g$. The sum over $G^n$ of $f^a$ is equal to $(3+4^a)^n$.

The probability that $g$ is in $\cup_{j=1}^k H_j$ is a function of $f(g)$ and $k$. If we lower bound this function by a polynomial of $f(g)$, for instance $(k/4^n)+(f(g)-1)(1-k/4^n)/(4^n-1)$, and sum over $G^n$, we can get a not completely terrible lower bound formula:

$k+ (7^n-4^n)(4^n-k)/(16^n-4^n)$

which we can simplify tremendously by approximating.

-
I lost you after the first line... $N_k \le |G|^n = 4^n$ for all k, so the bound your wrote can't always hold. – Steve Flammia May 24 '12 at 0:51
This is sampling without replacement, so there is no point in considering $k$ above $|G|^n$. – Will Sawin May 24 '12 at 1:34
Yes, of course. (I read "with" instead of "without".) In fact, $k \le 3^n$, the number of full elements in $G^n$. Then $N_{3^n} = 4^n \gg 3^n$. In that case, it seems the bound is rather loose, no? Plus one regardless! – Steve Flammia May 24 '12 at 3:50
Ah, sorry. I didn't read "full". Then we can strengthen the bound. In fact I argue it is $k\cdot 4^n/3^n$. The number of full elements is exactly $k$, and the probability that a non-full element is in the set is at least the probability that a full element is in the set. My other bound seems a bit too cumbersome, and I'm not going to try to update it. – Will Sawin May 24 '12 at 4:23
Actually, I think there is a simpler derivation of the other bound. There is a best linear lower bound for this problem, since $\mu_k$ is clearly a convex (concave?) function for $k$. It's the kind where if you interpolate linearly between $k=1$ and $k=3^n$, that's a lower bound for $\mu_k$. $\mu_1=2^k$, $\mu_{3^k}=4^k$. – Will Sawin May 24 '12 at 4:28

Let's get a lower bound by considering sampling with replacement, for which we can even get the exact answer. If we sample $k$ full elements, what is the probability that they agree at exactly $l$ locations? For $G = \mathbb{Z}/2 \times \mathbb{Z}/2$, the answer is $$p(k,l) = {n \choose l} \left(\left(\frac{1}{3}\right)^{k-1}\right)^l \left(1-\left(\frac{1}{3}\right)^{k-1}\right)^{n-l}.$$ When two full elements agree in exactly $l$ places, they jointly generate $2\times2^n - 2^l$ elements of $G^n$. Continuing this logic, an inclusion-exclusion principle lets us count the expected number of elements after $k$ steps, namely, $$\mu_k = \sum_{j=1}^k {n \choose j} (-1)^{j-1} \sum_{l=0}^n p(j,l) 2^l .$$ This formula isn't very nice because when $k$ is large we have to sum over as many as $3^n$ terms. Fortunately, we can use the binomial theorem twice to get rid of the sum on $j$. We first expand the binomial term in $p(j,l)$, then collapse the sum on $j$. The result is $$\mu_k = 4^n - \sum_{l=0}^n \sum_{m=0}^{n-l} {n \choose l} {n-l \choose m} (-3)^m 6^l \bigl(1-3^{-(l+m)}\bigr)^k .$$ This is much easier to evaluate than the previous formula.

While this bound is really good for small $k$, it is not good for very large $k$. Since $\mu_k$ is concave in $k$ (see the comments in Will Sawin's answer), the convex hull of two lower bounds is again a lower bound. So we can add in the fact that the point $(3^n,4^n)$ is the answer for sampling without replacement and find the line which connects this point back to the previous bound in an optimal way. This is hard to do analytically, but can be done for specific values of $n$. This gives a very good lower bound.

-