11
$\begingroup$

Let $A(n,p)$ be the order of the largest subset of $M_n(Z_p)$ such that no two distinct matrices in this subset commute. Is it true that $\lim_{p \to \infty} \dfrac{A(n,p)}{p^{n^2}} =1$? Can anyone find better asymptotics?

Also, what happens if we fix $p$ and allow $n$ to grow?

(Inspired by 1990 Putnam B3)

Improve this question
$\endgroup$
6
  • $\begingroup$ Given that one can only select at most one regular semisimple element from each maximal torus, it seems to me that one can't exceed $O(p^{n^2-1})$ elements (and probably less than that if one works more carefully.) $\endgroup$
    – Terry Tao
    Sep 19, 2012 at 19:48
  • $\begingroup$ I think that should be $O(p^{n^2-n})$, not $n^2-1$. $\endgroup$
    – David E Speyer
    Sep 19, 2012 at 20:31
  • $\begingroup$ I don't think it can get lower than $O(p^{n^2−n})$. In fact, a lower bound is $A(n,p)\geq p^{\frac{n^2+n-2}{2}}(p^{n-2}-1)\cdots(p^2-1)(p-1)$ $\endgroup$
    – Gjergji Zaimi
    Sep 19, 2012 at 20:51
  • $\begingroup$ Is that by picking one diagonal matrix for each essentially different way to diagonalize? $\endgroup$
    – Douglas Zare
    Sep 19, 2012 at 21:59
  • $\begingroup$ @Gjergji, can you show me how you got that lower bound? Thanks! $\endgroup$
    – jwellens
    Sep 20, 2012 at 0:00

1 Answer 1

Reset to default
1
$\begingroup$

According to Abelian coverings of finite general linear groups and an application to their non-commuting graph by A. Azad, M. A. Iranmanesh, C. E. Praeger, P. Spiga for the general linear group, one has that the ratio of the largest pairwise non-commuting set of invertible matrices in $GL(n,q)$ to the order of $GL(n,q)$ is something like $q^{-n}$. One would guess that the answer should be the same since in some sense the unit group dominates the whole monoid.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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