I want to specify, what it means to give an algebra as input to an algorithm and didn't find very much literature about it. So first I want to ask if you can recommend a book or paper that deals with the topic of complexity analysis of algebras over fields and clearly define the decision problem.

After some digging I found something and want to share it here and furthermore ask if the definitions make sense and are in compliance with literature (if there is any):

Definition: Let $\mathbb F$ be a field and $A$ be a finitely generated commutative $\mathbb F$-algebra with additive basis $b_1,\ldots, b_n\in\mathbb F$. We now want to capture the multiplicative structure of the algebra and therefore write every product of base elements as a linear combination of all base elements: $$ \forall 1\leq i, j, k\leq n: \exists a_{ijk}: b_ib_j=\sum_{k=1}^n a_{ijk}b_k. $$ The $a_{ijk}$ are called structure coefficients. We directly have that: $$ A \cong \left.\mathbb{F}[b_1, \ldots, b_n] \middle/ \left<b_i b_j-\sum_{k=1}^n a_{ijk}b_k\right>_{1\leq i,j\leq n}\right..$$ Now one can define the following decision problem: $$ \{(A,B)\mid A, B \text{ commutative $\mathbb F$-algebras with basis $b_1, \ldots b_n$ and } A\cong B\}. $$ To specify an isomorphism $\phi:A\rightarrow B$ it is sufficient to write every $\phi(b_i)$ as linear combination of the elements of a basis of $B$.

Does anything in this definition seem strange to you or do you think that one can work with it?

Motivation: My motivation behind this is to give a very clear definition of the decision problem first to connect it to other problems, i.e. the problem of deciding polynomial equivalence: Given two polynomials $f,g\in\mathbb F[x_1, \ldots, x_n]$, we say that $f$ is equivalent to $g$ if there exists an invertible linear transformation $\tau$ on the variables such that $f(\tau(x_1), \ldots, \tau(x_n))=g(x_1, \ldots, x_n)$. In other words, two polynomials are equivalent if you can replace every variable by a linear combination of all variables to obtain the other polynomial.

I'm not sure if this helps as a motivation but the connection of this problems is established by constructing finitely generated commutative $\mathbb F$-algebras from the two polynomials that are isomorphic if and only if the polynomials are equivalent. For this I wanted to make sure that the decision problem is defined very clearly.

  • $\begingroup$ Does anyone know references besides the one mhum links to? $\endgroup$
    – born
    Jul 9, 2012 at 8:24

2 Answers 2


This seems to be consistent with the presentation in Equivalence of $\mathbb{F}$-algebras and cubic forms, Agrawal & Saxena (2006).


Computability over mathematical structure is a long and well established area of research. For example, see:

or google for:

  • computability algebra
  • computable model theory

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.