6
$\begingroup$

The commutativity degree $d(G)$ of a finite group $G$ is defined as the ratio $$\frac{|\{(x,y)\in G^2 | xy=yx\}|}{|G|^2}.$$It is well known that $d(G)\leq5/8$ for any finite non-abelian group $G$. If $P(G)$ is the monoid of subsets of $G$ with respect to the usual product of group subsets, then the commutativity degree $d(P(G))$ of $P(G)$ can be defined similarly: $$d(P(G))=\frac{|\{(A,B)\in P(G)^2 | AB=BA\}|}{|P(G)|^2}.$$Which are the connections between $d(G)$ and $d(P(G))$? Is there a constant $c\in (0,1)$ such that $d(P(G))\leq c$ for any finite non-abelian group $G$?

Additional Question: Let $P_k(G)$ be the subset of $P(G)$ consisting of all $k$-subsets of $G$ and $$d(P_k(G))=\frac{|\{(A,B)\in P_k(G)^2 | AB=BA\}|}{|P_k(G)|^2}.$$Clearly, $d(P_1(G))=d(G)$ and, for every $k\in\{1,2,3\}$, $G$ is abelian iff $d(P_k(G))=1$. A similar question can be asked for $d(P_k(G))$, $k=2,3$: is there a constant $c_k\in (0,1)$ such that $d(P_k(G))\leq c_k$ for any finite non-abelian group $G$?

$\endgroup$
3
  • $\begingroup$ @Derek Holt: I would say that your argument shows just that any two subsets $A$ and $B$ of cardinality $>|G|/2$ each commute, since $AB=BA=G$... $\endgroup$ Commented Mar 16, 2016 at 12:08
  • $\begingroup$ Yes that's right - I have deleted my comment. $\endgroup$
    – Derek Holt
    Commented Mar 16, 2016 at 12:40
  • 2
    $\begingroup$ That raises the question for what fraction of the pairs $(A,B)$ of subsets of $G$ is $AB=BA=G$. Could this approach $1$ for large $G$? If so, there would be no such constant $c$. $\endgroup$
    – Derek Holt
    Commented Mar 16, 2016 at 13:55

1 Answer 1

5
$\begingroup$

@Derek Holt is completely right: as $|G|\to \infty$, the fraction of subsets $(A,B)$ with $AB=G$ tends to $1$, so there is no such $c$.

Indeed, assume that $|G|=n$. Let us choose the subsets $A$ and $B$ uniformly and independently. Fix any $g\in G$; there are $n$ pairs $(a,b)$ with $ab=g$, each pair belongs to $A\times B$ with probability $1/4$, and these events are independent for distinct pairs. Thus the probability that $g\notin AB$ is $(3/4)^n$, so the probability that $AB\neq G$ is at most $n(3/4)^n$ which tends to $0$ as $n\to\infty$.

To conclude: if $n$ is large, almost all pairs $(A,B)\in P(G)\times P(G)$ satisfy $AB=BA=G$.

$\endgroup$
3
  • $\begingroup$ Right - that's easier than I expected! $\endgroup$
    – Derek Holt
    Commented Mar 16, 2016 at 16:21
  • $\begingroup$ @GeoffRobinson: I do not fix the cardinalities of $A$ abd $B$; I simply put every element to $A$ with probability $1/2$, the same for $B$ (all $2n$ choices are independent). $\endgroup$ Commented Mar 17, 2016 at 12:25
  • $\begingroup$ @IlyaBogdanov :OK, thanks, I see what is going on now. $\endgroup$ Commented Mar 19, 2016 at 22:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .