8
$\begingroup$

This question is related to the following general question:

Given a variety of (non-associative) algebras $\mathcal V$, a finite field $\mathbb{F}_q$, with $q$ elements, and a positive integer $n$, how many $n$-dimensional $\mathbb F_q$-algebras in $\mathcal V$ are there?

It is well known that if $A$ is an $n$-dimensional algebra over a field $F$, with basis $\{e_1, \dots, e_n\}$ then its algebra structure is uniquely determined by the $n^3$-tuple $(\alpha_{ij}^{(k)})\in F^{n^3}$, defined by $e_i e_j=\sum_{k=1}^n \alpha_{ij}^{(k)} e_k$.

So the general question above can be reformulated as:

How many of these $n^3$-tuples of elements of $\mathbb F_q$ define algebras in $\mathcal V$?

Or in another language: given an arbitrary $n$-dimensional algebra, what is the probability that it lies in $\mathcal V$?

Let us denote such number by $N_{q,n}(\mathcal V)$.

Some examples are simple to compute. For example, if $q$ is odd, one can easily show that if $\mathcal V$ is the variety of anticommutative algebras (i.e., the class of all algebras satisfying the identity $xy+yx=0$), then $N_{q,n}(\mathcal V)=q^{n^2(n-1)/2}$ and if $\mathcal C$ is the variety of commutative algebras, then $N_{q,n}(\mathcal C)=q^{n^2(n+1)/2}$.

But other examples seem to be much more difficult, for example for the varieties of Lie and associative algebras.

So my main questions (for now) are the following:

  1. How many Lie algebras of dimension $n$ over a field with $q$ elements are there?
  2. How many associative algebras of dimension $n$ over a field with $q$ elements are there?

I'd like to stress that I am not interested in isomorphism classes, but in the number of such algebras only (that is to say this is a problem of combinatorics and not of algebra).

Finally, I would like to remark that I have considered the possibility to write a computer program to compute some cases (example for $q=3$ and $n \leq 6$), so I could have a guess of the general answer, but in a first look I realized that this is would take too much time.

EDIT:

The answer I am expecting is an explicit formula for $N_{q,n}(\mathcal V)$ when $\mathcal V$ is the variety of associative or Lie algebras.

$\endgroup$
  • 2
    $\begingroup$ There's almost certainly no chance of an exact answer here... so you might want to be more specific about what kind of answer you'd like $\endgroup$ – Sam Hopkins Sep 8 '20 at 0:14
  • $\begingroup$ An algebra is determined by its $n^3$-tuple, but not every $n^3$-tuple determines an algebra, right? Unless I'm off on that, maybe the first question is how many $n$-dimensional algebras there are, full stop. And then, of course, among the ones that are algebras, there will be isomorphisms. Do you want to distinguish isomorphic algebras? $\endgroup$ – LSpice Sep 8 '20 at 1:15
  • $\begingroup$ Oops, it gradually sunk in that you mean "algebra" in the "universal algebra" sense, so that you genuinely meant all of the $n^3$ tuples to define an algebra. (At first I didn't register the word 'Lie' as an option indicating you didn't just want associative algebras ….) But then there's still the issue of whether to distinguish isomorphic algebras. $\endgroup$ – LSpice Sep 8 '20 at 2:29
  • 1
    $\begingroup$ Yes, I mean algebra over a field - i.e., just a vector space with a bilinear map. $\endgroup$ – Thiago Sep 8 '20 at 11:55
  • 1
    $\begingroup$ As regards your edit (you want an explicit formula, not just estimates): it's clearly out of reach at the moment. $\endgroup$ – YCor Sep 8 '20 at 12:57
15
$\begingroup$

Bjorn Poonen addresses this question for commutative (associative, unital) algebras in The moduli space of commutative algebras of finite rank; asymptotically we have

$$q^{\frac{2}{27} n^3 + O(n^{8/3})}$$

such algebras (Theorem 10.9). Bjorn also gives a more precise lower bound on the dimension of the corresponding affine scheme in Theorem 9.2 which is a collection of three polynomials with leading term $\frac{2}{27} n^3$ depending on the value of $n \bmod 3$. The $\frac{2}{27}$ may seem familiar from a corresponding count of the number of finite $p$-groups and it happens for very similar reasons as he discusses in Section 10:

The approach towards both those results is to adapt the proof (begun in [Hig60] and completed in [Sim65]) that the number of $p$-groups of order $p^n$ is $p^{ \frac{2}{27} n^3 + O(n^{8/3})}$. As suggested to us by Hendrik Lenstra, there is an analogy between the powers of the maximal ideal of a local finite-rank $k$-algebra and the descending $p$-central series of a $p$-group. Although there seems to be no direct connection between finite-rank $k$-algebras and finite $p$-groups, the combinatorial structure in the two enumeration proofs are nearly identical.

He also cites An estimate of the number of parameters defining an $e$-dimensional algebra by Yuri Neretin (which is in Russian, sadly for me) as addressing the Lie and associative cases; I'm not sure if the estimates immediately carry through to a finite field but if they do the answer is the same for Lie algebras and for associative algebras it is

$$q^{ \frac{4}{27} n^3 + O(n^{8/3}) }.$$

Presumably the analogous structure for Lie algebras making the answer similar is the descending central series for a nilpotent Lie algebra. For the associative case maybe it's something like powers of the Jacobson radical?

Note also that because $\frac{8}{3} > 2$ the error term in the exponent absorbs multiplicative factors as large as $q^{O(n^2)}$ so these asymptotics hold regardless of whether or not we quotient by the action of $GL_n(\mathbb{F}_q)$ (which is equivalent to asking for the isomorphism classification), which you might see as unsatisfactorily lenient but I think these are state of the art.


Edit: The lower bound for Lie algebras is easy enough to give here; it's very similar to the argument for finite $p$-groups and for commutative algebras but, I think, simpler. We consider only 2-step nilpotent Lie algebras $L$ of some dimension $n$, which arise as a central extension

$$0 \to [L, L] \to L \to A \to 0$$

of an abelian Lie algebra $A$ (the abelianization) by another abelian Lie algebra $[L, L]$ (the commutator; I am not using fraktur here to save typing). Explicitly, the Lie bracket $[-, -]$ factors through $A$ and lands in $[L, L]$, and so the only constraint on it is that it's a surjective alternating map $\wedge^2(A) \to [L, L]$; given any such map we can construct a Lie bracket which trivially satisfies the Jacobi identity because all triple commutators vanish by 2-step nilpotence. This is a mild generalization of the construction of the Heisenberg algebra where $\dim [L, L] = 1$.

So, fixing the vector space $L$, we put a 2-step nilpotent Lie algebra structure on $L$ by first choosing a subspace $[L, L]$ we want to be the commutator and then choosing a surjection $\wedge^2(L/[L, L]) \to [L, L]$. In general the space of surjections from a f.d. vector space $V$ to a f.d. vector space $W$ admits a free action by $GL(W)$ and the quotient by this action is the Grassmannian of codimension $\dim W$ subspaces of $V$. So, setting $b = \dim [L, L]$, the space of choices we have available is the triple of choices of

  • a $b$-dimensional subspace $[L, L]$ of $L$,
  • a $b$-codimensional subspace of $\wedge^2(L/[L, L])$, and
  • an isomorphism between the first choice and the quotient by the second choice.

Write $a = n - b = \dim L/[L, L] = \dim A$, so that $a + b = n$. Over $\mathbb{F}_q$ there are exactly

$${n \choose b}_q { {a \choose 2} \choose b}_q |GL_b(\mathbb{F}_q)|$$

ways to make the above choices. Now our job is to find $a, b$ which maximizes this, or at least which makes it quite big since we're aiming for a lower bound. The leading term in $q$ is $q$ to the power of

$$ab + \left( {a \choose 2} - b \right) b + b^2 = \frac{a(a+1)b}{2}.$$

Subject to the constraint that $a + b = n$ this is maximized when $a \approx \frac{2n}{3}, b \approx \frac{n}{3}$, and we could be more careful depending on the value of $n \bmod 3$ if desired. Let's instead restrict to the case that $3 \mid n$ so that we can divide by $3$ exactly, and also take the liberty of dividing by $(q - 1)^b$ so that what remains is a polynomial in $q$ with nonnegative coefficients and so the leading term is a true lower bound. We get that there are at least

$$q^{ \frac{2}{27} n^3 + \frac{n^2}{9} - \frac{n}{3}}$$

2-step nilpotent Lie brackets on $\mathbb{F}_q^n$ when $3 \mid n$.

To get a lower bound on the number of isomorphism classes we quotient badly by the action of $GL_n(\mathbb{F}_q)$. At this point we can actually restore the factor of $(q - 1)^b$ we lost above (although it doesn't matter too much either way); it's not hard to show that $\frac{|GL_n(\mathbb{F}_q)|}{|GL_b(\mathbb{F}_q)|} \le q^{n^2 - b^2}$, so we can then divide by $|GL_b(\mathbb{F}_q)|$ and then by $q^{n^2 - b^2}$ to get a lower bound, whereupon what remains is a polynomial in $q$ with non-negative coefficients which can be bounded from below by its leading term again. We get that there are at least

$$q^{ \frac{2}{27} n^3 - \frac{8n^2}{9}}$$

isomorphism classes of 2-step nilpotent Lie algebras of dimension $3 \mid n$ over $\mathbb{F}_q$. It is maybe surprising that it's possible to prove a matching upper bound, at least up to leading order in the exponent; I don't know what that argument looks like in detail.

For small values of $n$ it would be feasible to not only maximize but sum over all $a + b = n$ above and so compute the exact number of 2-step nilpotent Lie brackets. The truly brave who wanted to compute the exact number of isomorphism classes could hope to apply Burnside's lemma...

The lower bound for finite groups is very similar, using 2-step nilpotent $p$-groups arising as the central extension of a f.d. $\mathbb{F}_p$-vector space by another one, etc.

$\endgroup$
  • 1
    $\begingroup$ In the Lie case, one chooses for $m<n$ the $(n-m)$-Grassmanian in $\Lambda^2(K^n)$. This gives as many 2-step $n$-dim nilpotent Lie algebras. It seems to be maximal around $m=2n/3$ (whence the mod 3 discussion), in which case this Grassmannian has dimension $(2/27)n^3+O(n^2)$. This also gives the lower bounds for $p$-groups (at least for odd $p$), yielding $p^{(2/27)n^3+O(n^2)}$ such groups (2-nilpotent of exponent $p$). The estimate in $S^2(K^n)$ instead of $\Lambda^2(K^n)$ seems roughly the same, yielding as many commutative associative nilpotent algebras (or local, if one requires a unit). $\endgroup$ – YCor Sep 8 '20 at 8:23
  • $\begingroup$ I'm more surprised by Neretin's lower bound $4/27$: it should come either from non-nilpotent Lie algebras, or nilpotent of unbounded nilpotency length (as otherwise it would provide for large $p$, as many $p$-groups of order $p^n$) $\endgroup$ – YCor Sep 8 '20 at 8:25
  • $\begingroup$ The $\frac{4}{27}$ confuses me also but I am very unfamiliar with the structure theory of finite-dimensional algebras. I guess such an algebra $A$ over $\mathbb{F}_q$ looks like a finite product $A/J(A)$ of matrix rings $M_n(\mathbb{F}_{q^i})$ extended by the Jacobson radical $J(A)$ which should in particular be nilpotent... I guess after two square-zero extensions $A/J^3(A) \to A/J^2(A) \to A/J(A)$ complicated stuff is happening? $\endgroup$ – Qiaochu Yuan Sep 8 '20 at 8:33
  • 1
    $\begingroup$ By the way, the existence of a component of dimension $\ge 2n^3/27$ in the variety of Lie algebra laws in dimension $n$ was observed in: M. Vergne, Réductibilité de la variété des algèbres de Lie nilpotentes. (French) C. R. Acad. Sci. Paris Sér. A-B 263 (1966), A4–A6. $\endgroup$ – YCor Sep 8 '20 at 9:57
  • $\begingroup$ @Qiaochu Yuan Thank you for your answer and for the references. I'll try to read it carefully later. $\endgroup$ – Thiago Sep 8 '20 at 23:53

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.