**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).



What is the probability that a random subset of a finite group is generic?
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$.


