Generating a group by randomly sampling generators - MathOverflow

Generating a group by randomly sampling generators

2012-05-23T19:51:15Z

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.

Answer by Will Sawin for Generating a group by randomly sampling generators

2012-05-24T00:32:05Z

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.

Answer by Steve Flammia for Generating a group by randomly sampling generators

2012-05-26T05:57:07Z

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.