# An $\mathbb F$-algebra as input to an algorithm

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.

• Does anyone know references besides the one mhum links to? – born Jul 9 '12 at 8:24

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