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

  • $\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$ – Ilya Bogdanov Mar 16 '16 at 12:08
  • $\begingroup$ Yes that's right - I have deleted my comment. $\endgroup$ – Derek Holt Mar 16 '16 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 Mar 16 '16 at 13:55

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

| cite | improve this answer | |
  • $\begingroup$ Right - that's easier than I expected! $\endgroup$ – Derek Holt Mar 16 '16 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$ – Ilya Bogdanov Mar 17 '16 at 12:25
  • $\begingroup$ @IlyaBogdanov :OK, thanks, I see what is going on now. $\endgroup$ – Geoff Robinson Mar 19 '16 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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