×

Polynomial identities for ternary intermolecular recombination. (English) Zbl 1256.17001

The operation of binary intermolecular recombination [L. Landweber and L. Kari, “The evolution of cellular computing: nature’s solution to a computational problem”, Biosystems 52, 3–13 (1999)], originating in the theory of DNA computing, permits a natural generalization to \(n\)-ary operations. The present paper versus with the case \(n = 3\). The author uses computer algebra to determine the polynomial identities of degree \(\leq 9\) satisfied by ternary intermolecular recombination. Let \(X\) be a finite set, consider the set \[ X^* = \{x_1 x_2 \ldots x_k \mid x_1, x_2, \ldots, x_k \in X \, (k \geq 1) \} \] with the binary operation of concatenation, \[ (x_1 x_2 \ldots x_k)(x_{k + 1}x_{k + 2} \ldots x_{k + \ell}) \mapsto x_1 x_2 \ldots x_{k + \ell}, \] L. Landweber and L. Kari (loc. cit.) that is, the free semigroup on \(X\). Given a positive integer \(n\), denote by \(R(X, n)\) the \(\mathbb{Q}\)-vector space with basis \((X^*)^n\), the set of all \(n\)-tuples of elements of \(X^*\). The \(n\)-ary intermolecular recombination is the multilinear nonassociative operation, denoted \(\{a_1, a_2, \ldots, a_n\}\), and defined on basis elements \(a_i = (a_{i1}, a_{i2}, \ldots, a_{in}) \in (X^*)^n\) as follows: \[ \{a_1, a_2, \ldots, a_n\} = \sum_{\sigma \in S_n} (a_{\sigma(1), 1}, a_{\sigma(2), 2}, \ldots, a_{\sigma(n), n}), \] where \(S_n\) is the symmetric group on \(\{1, 2, \ldots, n\}\).
The paper is organized as follows: in Section 2, the author recalls the main results of M. R. Bremner, [“Jordan algebras arising from intermolecular recombination”, SIGSAM Bull. 39, No. 4, 106–117 (2005; Zbl 1226.17026)] on polynomial identities for binary intermolecular recombination. He also shows how these results can be improved by using the Hermite normal form with lattice basis reduction. Section 3 contains the main results of the paper: a complete and minimal set of polynomial identities of degree \(\leq 9\) for ternary intermolecular recombination is provided. He concludes the paper by posting, in Section 4, three interesting conjectures on polynomial identities for the general case of \(n\)-ary intermolecular recombination. As the author points out these conjectures has been proved by S. R. Sverchkov, [“The structure and representation of \(n\)-ary algebras of DNA recombination”, Cent. Eur. J. Math. 9, No. 6, 1193–1216 (2011; Zbl 1252.17016)]. He received Sverchkov’s preprint shortly before the final version of the present paper was sent to the editors.

MSC:

17A40 Ternary compositions
17A42 Other \(n\)-ary compositions \((n \ge 3)\)
17C05 Identities and free Jordan structures
68W30 Symbolic computation and algebraic computation
92D20 Protein sequences, DNA sequences
PDFBibTeX XMLCite
Full Text: DOI arXiv