patternMinor
An $\mathbb F$-algebra as input to an algorithm
Viewed 0 times
inputalgorithmalgebramathbb
Problem
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_{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 va
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_{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 va
Solution
This seems to be consistent with the presentation in Equivalence of $\mathbb{F}$-algebras and cubic forms, Agrawal & Saxena (2006).
Context
StackExchange Computer Science Q#2642, answer score: 5
Revisions (0)
No revisions yet.