Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Thanks for the correction. –  Manta Jan 14 '13 at 15:50
add comment

1 Answer 1

up vote 7 down vote accepted

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$.

share|improve this answer
    
Thank you: I think your proof works. However, I would like to also have a reference. –  Manta Jan 14 '13 at 17:18
3  
A version of this argument (in the context of finite abelian groups, though as noted above the abelian property is unnecessary) appears in (the hint for) Exercise 2.4.1 of my book with Van Vu. It's one of these "folklore" constructions for which it may be difficult to pin down a precise reference (it may be noted in some of Ruzsa's papers, perhaps...). –  Terry Tao Jan 14 '13 at 21:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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