What is the probability that a random subset of a finite group is generic?

Question

Definition 1: Given a group $G$, a subset $X \subseteq G$, and a natural number $k$, we say that $X$ is (left) $k$-generic in $G$ if there are $k$ many left translates of $X$ that cover $G$. That is, if there exist $a_1, \dots, a_k \in G$ such that $G = \bigcup_i a_i \cdot X$ (where $a_i \cdot X = \{ a_i \cdot x: x \in X \}$).

Definition 2: Let $n$ be a natural number and $G$ be a group with $n$ elements. On the family of subsets of $G$ we put the probability that gives to each subset probability $1/2^n$; equivalently, for every $g \in G$ we toss a coin to decide whether or not $g$ is in a given set.

Let $P_k(G)$ be the probability that a random subset of a group $G$ is $k$-generic in $G$.

Problem: I want to show that, for a fixed $k$, $P_k(G) \to 0$ as the cardinality of $G$ goes to infinity, independently of the choice of the group $G$ (actually, I need only the case $G = \mathbb Z / n \mathbb Z$).

I expect that the above is a known fact: I would appreciate a reference for it (my background is in logic).

Answer 1

I think your conjecture is right. I hadn't heard of this fact before, so can't provide a reference. Here is my attempt at a proof.

The idea is that I want to reverse things: Fix a set $A=\{a_i\}$ with $|A|=k$ and show that the probability that a set $X$ is $A$-generic (i.e. $AX=G$) is exponentially small in $n$ (uniformly in $A$). On the other hand, there are only polynomially many ($\approx n^k$) $A$'s, so the probability that $X$ is $k$-generic is bounded above by $n^k\times$(exponentially small in $n$).

Let's do this in detail. Let $B=AA^{-1}$ (i.e. $\{a{a'}^{-1}\colon a,a'\in A\}$), so that $|B|\le k^2$. Now I claim that you can pick in $G$ elements $g_1,\ldots,g_m$, where $m=n/k^2$ such that $g_j\not\in\bigcup_{i < j}Bg_i$ (at the $j$th stage, there are at least $|G|-|B|(j-1)$ choices). The $A^{-1}g_i$ are now disjoint: if $A^{-1}g_i\cap A^{-1}g_j\ne\emptyset$ for $i < j$, then $g_j\in Bg_i$.

Now we compute for a random subset $X$: what is the probability that $AX\supset\{g_1,\ldots,g_m\}$? Note that $AX$ contains $g_i$ if $X$ contains an element of $A^{-1}g_i$. The probability of this is $1-2^{-k}$. Since the sets $A^{-1}g_i$ are disjoint, the probability that $AX$ contains each of the $g_i$ is $(1-2^{-k})^m=(1-2^{-k})^{n/k^2}$. Hence the probability that $X$ is $k$-generic is at most $n^k(1-2^{-k})^{n/k^2}$, which tends to 0 as $n\to\infty$ for fixed $k$.