# What is the maximum cardinality of an independent set in a finite group?

$\DeclareMathOperator{\rank}{rank}$ This is sort of the dual question for How do I find the minimum size of a generating set of a group?.

A subset S of a finite group G is an independent set if for each x in S, the element x is not in 〈S ∖ {x}〉. For example,

• the additive group $\mathbb{Z}_2^n$ has an independent set of size n, namely the set $\{e_1, \dotsc, e_n\}$ where $e_i$ is the sequence of length n with a 1 in the ith position and zeros elsewhere,
• the symmetric group $S_n$ has an independent set of size n - 1, namely the set of adjacent transpositions.

Let $\rank_u(G)$ denote the upper rank of G, defined by $$\rank_u(G) = \max \{ |S| \, | \, S \subseteq G \text{ and } S \text{ is independent} \}$$

My question is what are the upper and lower bounds for the upper rank function? More formally,

1. What is the smallest function u(n) such that for each finite group G of order n, each independent set has cardinality at most u(n)?
2. What is the largest function $\ell(n)$ such that for each finite group G of order n, there is an independent set of cardinality at least $\ell(n)$?
• The best general upper bound is still $\log_2 n$. But there are infinitely many groups ${\rm PSL}(2,p)$ in which the maximal size is $3$. See math.stackexchange.com/questions/1004210 – Derek Holt Dec 8 '15 at 22:53
• If I understand your comment correctly, this is not quite what I'm asking. First, there exists an independent set of size at most $\log_2 n$, which I think follows from the proof that a finite group has a generating set of size $\log_2 n$, but that doesn't provide an upper bound. Second, I think you are describing the size of a maximal independent generating set, which is more restrictive than I require. I just need an independent set, not a generating one. – argentpepper Dec 9 '15 at 16:46
• It is not clear to me what you are asking. The question "What is the maximum cardinality of any independent set in an arbitrary finite group?" doesn't make much sense. What I am saying is that it is not possible for an independent set in a group $G$ with $|G|=n$ to have size larger than $\log_2 n$. – Derek Holt Dec 9 '15 at 17:10
• Sorry about that, I have updated the question to be more clear. Hopefully it makes more sense now. – argentpepper Dec 9 '15 at 20:36

## 1 Answer

These functions $u(n)$ and $l(n)$ will depend heavily on the prime factorization of $n$ and I doubt whether it would be possible to come up with simple formula for them that works for all $n$, or even a reasonably efficient algorithm to compute them (although that might be an interesting problem to investigate).

What we can say is that $u(n) \le \log_2 n$ for all $n$, with equality when $n$ is a power of $2$

When $n$ is a product of $k$ distinct primes (which could be the first $k$ primes) than $l(n)=k$. Groups of order $n$ are solvable, and we can find a collection of $k$ Sylow subgroups, one for each prime, and choose one element from each. So, using results from Number Theory, there are arbitrarily large integers $n$ with $l(n) > \log n/\log \log n$.

On the other hand $u(n)=1$ when $n$ is prime, and $l(n) = 1$ when $n$ is a prime power.

• Can you expand on why each independent subset must have size at most $\log_2 n$? – argentpepper Dec 10 '15 at 19:28
• Suppose the independent subset is $\{g_1,g_2,\ldots,g_k\}$ and let $G_i =\langle g_1,g_2,\ldots,g_i \rangle$ for $0 \le i \le k$. Then $g_i \not\in G_{i-1}$, so $|G_i| \ge 2|G_{i-1}|$ and hence $|G| = |G_k| \ge 2^k$. – Derek Holt Dec 10 '15 at 19:49