3
$\begingroup$

$\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)$?
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Derek Holt Dec 8 '15 at 22:53
  • $\begingroup$ 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. $\endgroup$ – argentpepper Dec 9 '15 at 16:46
  • $\begingroup$ 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$. $\endgroup$ – Derek Holt Dec 9 '15 at 17:10
  • $\begingroup$ Sorry about that, I have updated the question to be more clear. Hopefully it makes more sense now. $\endgroup$ – argentpepper Dec 9 '15 at 20:36
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you expand on why each independent subset must have size at most $\log_2 n$? $\endgroup$ – argentpepper Dec 10 '15 at 19:28
  • 1
    $\begingroup$ 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$. $\endgroup$ – Derek Holt Dec 10 '15 at 19:49

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.