# A group-theoretic perspective on Frankl's union closed problem

Here is a group theoretic phrasing of a special case of the union closed conjecture:

Question: Given a finite group $G$, is there an element of prime power order which is contained in at most half the subgroups of $G$?

Motivation: Frankl's union closed sets conjecture has an equivalent phrasing in terms of lattices. It says that in every finite lattice there is a join irreducible element which is less than or equal to at most half the elements in the lattice.

Finite lattices are always isomorphic to intervals of subgroups $[H,G]$ for groups $H,G$ (i.e. the lattice of subgroups $H\subseteq K \subseteq G$, with the subgroup relation). It is not known whether it suffices to take $H$ and $G$ to be finite. I wonder if anything about Frankl's conjecture is known for the case when $H$ is the trivial group. And that is precisely what is asked above. Notice that the elements of prime power order are in correspondence with the join irreducibles of the lattice of subgroups of $G$.

Is the answer to the question above known? Is this known for special classes of groups?

• Is there any group $H_0$ such that the answer in the case $H=H_0$ is known? – Noah Schweber Jan 9 '14 at 4:12
• @Noah, not that I know of. – Gjergji Zaimi Jan 9 '14 at 7:19
• Is it conceivable that the following reduction might hold: Let $N$ be a normal subgroup of a group $G$. If $N$ contains an element $g$ of prime power order that is contained in at most half the subgroups of $N$, then $g$ is contained in at most half the subgroups of $G$? – Nick Gill Jan 10 '14 at 12:03
• Were such a reduction possible, then one might be able to proceed by proving the statement for quasisimple groups (generalizing @Alireza's comment below), then proving it for central products of isomorphic quasisimples, and then the result would be true for groups with non-nilpotent generalized Fitting subgroup of $G$. In other words you'd be left with the situation $F^*(G)=F(G)$... – Nick Gill Jan 10 '14 at 12:05
• ... at which point the direction that @Russ suggests might work - you'd need to prove the statement for nilpotent groups. Having typed all that, I start to doubt that the reduction is really possible... – Nick Gill Jan 10 '14 at 12:07

In a somewhat different direction from Alireza: the conjecture is true for a large family of groups, including all abelian groups and many supersolvable groups.

Let me start with the abelian case. Pick an element $g$ of highest possible prime-power order in an abelian group $G$. Then $\langle g \rangle$ has a complement: that is, there is a subgroup $K$ such that $K \langle g \rangle = G$ and $K \cap \langle g \rangle = 0$. In particular, $K \cong G / \langle g \rangle$ by the Isomorphism Theorems, and for any subgroup $X$ with $\langle g \rangle \subseteq X$ there is a corresponding subgroup $X \cap K$ which does not contain $\langle g \rangle$.

In fact, the same argument applies to any $G$ and prime-power order element $g$ if 1) $g$ generates a normal subgroup, and 2) we can find a complement $K$ to $\langle g \rangle$ in G. In this situation, $[\langle g \rangle, G] \cong [1,K]$.

(Edit: deleted discussion of supersolvable groups, which is irrelevant in light of update below.)

UPDATE: The conjecture is true for all finite solvable groups.

Proof: Let $G$ be a solvable group. Then $G$ has a normal subgroup $N$ of prime index, and some element of prime-power order $g \notin N$. Since $N$ is maximal in $G$, we have $\langle g,N \rangle = G$, and since $N$ is normal we have $\langle g,N \rangle = \langle g \rangle N$. Then by Dedekind's identity, we get that $\langle g \rangle (H \cap N) = H \cap G = H$ for any $H$ containing $\langle g \rangle$.

The last tells us that the map from the interval $[\langle g \rangle,G] \rightarrow [1,N]$ given by $H \mapsto H \cap N$ is an injection. Since $N$ doesn't contain $g$, we get the conjectured statement. $\square$

Indeed, the above works whenever $G$ has a maximal normal subgroup of prime index. (E.g., for symmetric groups.)

(Thanks to John Shareshian for several useful comments and discussion.)

UPDATE 2: By combining my argument for solvable groups with Alireza's argument for (certain) finite simple groups, we can prove the conjecture for all groups having a quotient satisfying a certain condition. This very likely holds for all finite groups, but as I'll explain, a little bit of work remains on the group theory side.

Theorem 1: If $G$ is a finite group with a normal subgroup $N$ such that $G/N$ is generated by (at most) two elements of prime power order, then $G$ satisfies the Frankl condition.

Proof: A routine argument shows that we can pick $g,h \in G$ of prime power order such that $g$ and $h$ project in the quotient to generators of $G/N$. (If $G/N$ is cyclic, assume $g=h$.) Let $K = \langle g, h \rangle$, and notice that $KN = \langle N, g, h\rangle = G$.
Then wlog there are at least as many subgroups containing $h$ as containing $g$ (else switch $h$ and $g$). This gives an injection $\varphi_1$ from the set of subgroups containing $g$ but not $h$ to the set of subgroups containing $h$ but not $g$.
Moreover, if $H$ is a subgroup containing both $h$ and $g$, then $H \supseteq K$. It then follows from the Dedekind identity that $K (H \cap N) = H \cap KN = H$, hence the map $\varphi_2$ sending $H \mapsto H \cap N$ is an injection from $[K,G] \rightarrow [1,N]$.
Since the intervals $[\langle h \rangle, G]$ and $[1,N]$ are disjoint, combining the two maps gives an injection from $[\langle g \rangle, G]$ to its complement, and we see the Frankl condition to hold. $\square$

Remark 1: The solvable case (above) is the case when $G/N$ is cyclic -- here, $K = \langle g,h \rangle = K$. The case where $N=1$ solved by Alireza has $K = G$, in which case we map $G$ to $1$ and all other subgroups containing $g$ to a subgroup containing $h$.

Remark 2: The proof has a particularly pleasing explanation if we can take $g$ and $h$ to be conjugate. In this case, the intervals $[\langle g \rangle, G]$ and $[\langle h \rangle, G]$ are isomorphic lattices, with the isomorphism given by conjugation of subgroups. As we shall see below, this stronger conjugacy condition often does seem to occur.

Now, if $N$ is a maximal normal subgroup, then $G/N$ is simple, so to verify the conjecture for all groups it suffices to verify that every finite simple group is generated by two elements of prime-power order. I managed to put together the following from results in the literature:

Theorem 2: All but possibly finite many of the finite simple groups are generated by two elements of prime power order. The two elements may be taken to be conjugate. Any exceptions are classical groups.

The conjugacy part will come from the following lemma:

Lemma: If a finite simple group $G$ is generated by $x$ and $g$, where $x$ has order 2, then $G = \langle g, g^x \rangle$.

Proof (of Lemma): Suppose not, and let $H = \langle g, g^x \rangle$. Then $H$ is easily seen to permute with $\langle x \rangle$, hence $H$ has index 2, contradicting simplicity of $G$. $\square$

We say a group is $(2,q)$-generated if it is generated by an element of order 2, together with an element of order $q$. To prove Theorem 2, it suffices to show that (modulo possible exceptions) every finite simple group is (2,$q$)-generated for some prime-power $q$. We go through the list of groups from the Classification Theorem.

1. Many finite simple groups are known to be (2,3)-generated, and this condition has been well-studied. ((2,3)-generated groups can be represented as quotients of $PSL_2(\mathbb{Z})$, explaining the high level of interest in this condition.)

A. Liebeck and Shalev in "Classical groups, probabilistic methods, and the (2,3)-generation problem" showed that, excluding the groups $PSp_4(q)$, all but finitely many of the classical groups are (2,3)-generated.

B. Di Martino and Cazzola in "$(2,3)$-generation of $PSp(4,q),\ q=p^n,\ p\neq 2,3$" showed that $PSp_4(q)$ is (2,3)-generated, except in characteristic 2 or 3.

C. Malle, and Lübeck and Malle in a series of papers culminating in "(2,3)-generation of exceptional groups" show that all exceptional groups of Lie type are (2,3)-generated, except for the Suzuki groups and $G(2)' \cong PSU_2(9)$.
(Nick Gill also referenced this paper in his comment to Alireza's answer.)

D. Woldar in "On Hurwitz generation and genus actions of sporadic groups" showed the sporadic groups to be (2,3)-generated, except for $M_{11}$, $M_{22}$, $M_{23}$, and $McL$

E. GA Miller proved in 1901 that the alternating groups $A_n$ are (2,3)-generated for $n \neq 6,7,8$.

2. $A_6, A_7, A_8$ are easily verified to all be (2,5)-generated.

3. Liebeck and Shalev in Proposition 6.4 of the same paper referenced above show that all but finitely many of the groups $PSp_4(2^n)$ and $PSp_4(3^n)$ are (2,5)-generated.

4. Suzuki, in his original paper on the topic, showed that the Suzuki groups are (2,4)-generated.

5. For the remaining sporadics, $M_{11}$ and $M_{22}$ are (2,4)-generated, while $M_{23}$ and $McL$ are (2,5)-generated. (The best place I found to read about this is in a series of papers on symmetric genus of groups. These papers are by various authors, frequently including Conder and Woldar.)

Theorem 2 follows from the list above, together with the Classification of Finite Simple Groups.

There is very likely a nicer approach to some of the simple group stuff than what I do above -- I'm far from an expert. (Maybe one of the real experts around here can remove the possible exceptions from the statement!!)

I found the slides linked here of Maxim Vsemirnov on (2,3)-generated groups very helpful for understanding the exceptions to (2,3)-generation.
In particular, he has a list of groups that are not (2,3)-generated on page 15 (which he conjectures to be complete). I've verified with GAP that all are (2,$q$)-generated for some prime $q$, except for the PSp's and $\Omega_8^+(2), P\Omega_8^+(3)$.

Corollary: The conjecture holds for any $G$ with a maximal normal subgroup $N$ such that $G/N$ is not one of the exceptional (small) classical groups in Theorem 2.

• Russ, thank you for this great answer. I will need some time to digest your latest update, but it would be wonderful if the answer turned up to be positive for all groups :-) – Gjergji Zaimi Jan 21 '14 at 7:28

If $G$ is a non-trivial finite group which can be generated by two non-trivial elements of prime power orders, then the answer to the question is affirmative. Let $\mathcal{G}$ be the set of all subgroups of $G$ and let $G=\langle x,y\rangle$, where $x$ and $y$ are non-trivial elements of $G$ of prime power oders. Assume $A=\lbrace H\in \mathcal{G} \;|\; x\in H, y\not\in H \rbrace$, $B=\lbrace H\in \mathcal{G} \;|\; x\not\in H, y\in H \rbrace$, $C=\lbrace H\in \mathcal{G} \;|\; x\not\in H, y\not\in H \rbrace$ and $E=\lbrace H\in \mathcal{G} \;|\; x\in H, y\in H \rbrace$. So $E=\{G\}$ and $|C|\geq 1$ as $\{1\}\in C$. It follows that either $|A|\leq |\mathcal{G}|/2$ or $|B|\leq |\mathcal{G}|/2$.

I think (if I am not wrong) that every (if not "most" of!) finite simple groups can be generated by two elements of prime power orders. So the question has affirmative answer for finite simple groups and $2$-generated groups of prime power orders.

UPDATE (17/January/2014): Inspired by Russ, one can show that the question has affirmative answer for finite groups having a maximal subgroup(not necessarily normal) of prime index. Let $M$ be a maximal subgroup of $G$ of prime index $p$. If there exists an element $g\in G\setminus M$ of $p$-power order, then $G=M\langle g\rangle$. The latter holds since $$|M\langle g\rangle|=\frac{|M||g|}{|M\cap \langle g\rangle|}.$$ Now the map $H\mapsto H\cap M$ is injective for all subgroups $H$ containing $g$. So we may assume that all $p$-power order elements are in $M$ which implies that $M$ contains all Sylow $p$-subgroups of $G$, a contradiction. This slightly improves the result of Russ, as we do not assume $M$ is normal in the group.

• To understand the situation mentioned in the final paragraph, refer to Lubeck & Malle, (2,3)-generation of exceptional groups, in which Corollary 1.3 states: Let $G$ be a non-abelian finite simple group not equal to $Sp_4(2^n)$, $Sp_4(3^n)$ or ${^2B_2}(2^{2n+1})$, then, up to a finite number of exceptions, $G$ is generated by an element of order 2 and an element of order $3$... – Nick Gill Jan 10 '14 at 11:59
• ... If you want to know what the list of exceptions is, then you should refer to the references given near the statement of Corollary 1.3. So I'm guessing that @Alireza's statement is true (all FSGs are generated by two elements of prime power order) - one just needs to prove it for the three infinite families just mentioned, plus the finite list. – Nick Gill Jan 10 '14 at 12:01
• ... One can probably deal with the three infinite families directly, or using ideas in On triangle generation of finite groups of Lie type by Claude Marion. – Nick Gill Jan 10 '14 at 12:18