Lower bounds for algebraic algorithms for nilpotent and solvable lie algebras

We obtain the lower bounds for the tensor rank for the class of nilpotent and solvable Lie algebras (in terms of dimensions of certain quotient algebras). These estimates, in turn, give lower bounds for the complexity of algebraic algorithms for this class of algebras. We adduce examples of attainable estimates for nilpotent Lie algebras of various dimensions.     

The algebraic classification of nilpotent Tortkara algebras

Abstract

We classify all complex 6-dimensional nilpotent Tortkara algebras.

Communicated by Alberto Facchini     

Lower bounds for algebraic decision trees

A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where an $\text{Ω(n}{}^2\text{)}$ bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indicated. Some open problems are discussed.     

Lower complexity bounds for interpolation algorithms

We introduce and discuss a new computational model for the Hermite-Lagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known Hermite-Lagrange interpolation problems and algorithms. Like in traditional Hermite-Lagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski’s Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants).In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques.We finish this paper highlighting the close connection of our complexity results in Hermite-Lagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM).     

Lower complexity bounds for positive contactomorphisms

Let S*Q be the spherization of a closed connected manifold of dimension at least two. Consider a contactomorphism φ that can be reached by a contact isotopy that is everywhere positively transverse to the contact structure. In other words, φ is the time-1-map of a time-dependent Reeb flow. We show that the volume growth of φ is bounded from below by the topological complexity of the loop space of Q. Denote by ΩQ₀(q) the component of the based loop space that contains the constant loop.     

Lower bounds for commutative radical Banach algebras

One says a commutative radical Banach algebra A has a lower bound if there is a lower growth condition on $\text{∥x}{}^{\mathrm{n}}\text{∥}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ for all nonzero elements x in A. If A is a separable algebra we give necessary and sufficient conditions for A to possess a lower bound.     

The algebraic and geometric classification of nilpotent terminal algebras

We give algebraic and geometric classifications of 4-dimensional complex nilpotent terminal algebras. Specifically, we find that, up to isomorphism, there are 41 one-parameter families of 4-dimensional nilpotent terminal (non-Leibniz) algebras, 18 two-parameter families of 4-dimensional nilpotent terminal (non-Leibniz) algebras, 2 three-parameter families of 4-dimensional nilpotent terminal (non-Leibniz) algebras, complemented by 21 additional isomorphism classes (see Theorem 13). The corresponding geometric variety has dimension 17 and decomposes into 3 irreducible components determined by the Zariski closures of a one-parameter family of algebras, a two-parameter family of algebras and a three-parameter family of algebras (see Theorem 15). In particular, there are no rigid 4-dimensional complex nilpotent terminal algebras.     

The structure of algebraic jordan algebras without nonzero nilpotent elements

An algebraic, linear Jordan algebra without nonzero nil-potent elements is proved to be a subdirect sum of prime Jordan algebras each of which has finite capacity or contains simple subalgebras of arbitrary capacity. If in addition the base field has nonzero character-istic or the algebra satisfies a polynomial identity, then each of the summands is determined to be simple of finite capacity. Further, it is proved that algebraic, PI Jordan algebras without nonzero nilpotent elements are locally finite in the sense that any finitely generated subalgebra has finite capacity.     

On the action of derivations on nilpotent ideals of associative algebras

Let I be a nilpotent ideal of an associative algebra A over a field F and let D be a derivation of A. We prove that the ideal I + D(I) is nilpotent if char F = 0 or the nilpotency index I is less than char F = p in the case of the positive characteristic of the field F. In particular, the sum N(A) of all nilpotent ideals of the algebra A is a characteristic ideal if char F = 0 or N(A) is a nilpotent ideal of index < p = char F.     

Lower bounds for increasing complexity of derivations after cut elimination

We denote by C _k ^* the formula. In this paper for all k there is constructed a derivation of C _k ^* with cut, the number of sequents in which depends linearly on k. On the other hand, it is impossible to give an upper bound which is a Kalmar elementary function of k for the number of sequents in any derivation of the formula C _k ^* without cuts, or for the number of disjunctions in a refutation by the method of resolutions of systems of disjunctions corresponding to the negation of the formula C _k ^* . In particular, one can construct a derivation with cut of the formula C ₆ ^* , in which there is contained no more than 253 sequents, but in seeking a derivation of C ₆ ^* by the method of resolutions it is necessary to construct more than 10¹⁹²⁰⁰ disjunctions. With the help of Skolemization and taking out of quantifiers with respect to the formula C _k ^* there is constructed a formula v₀B _k ⁺ (v₀), which satisfies the following conditions: 1) one can construct a derivation with cuts of the formula v₀B _k ⁺ (v₀) in the constructive predicate calculus, the number of sequents in which depends linearly on k; 2) it is impossible to give an upper bound which is a Kalmar elementary function of k of the length of a term t such that the formula B _k ⁺ (t) is derivable.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 137–161, 1979.     

The algebraic and geometric classification of associative algebras of dimension five

The scheme Alg₅ of associative, unitary algebra structures on k⁵, k an algebraically closed field with char (k)2 is investigated. We establish the list of GL₅-orbits on Alg₅ under the action of structural transport. The numberalg₅ of irreducible components of Alg₅ is 10; a list of generic structures is included. We exhibit upper and lower bounds for the asymptotic behaviour of the numberalg_n.     

Lower bounds on monotone complexity of the logical permanent

Mathematical Notes -     

Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity

Lightweight cipher designs try to minimize the implementation complexity of the cipher while maintaining some specified security level. Using only a small number of AND gates lowers the implementation costs, and enables easier protections against side-channel attacks. In our paper we study the connection between the number of AND gates (multiplicative complexity) and the complexity of algebraic attacks. We model the encryption with multiple right-hand sides (MRHS) equations. The resulting equation system is transformed into a syndrome decoding problem. The complexity of the decoding problem depends on the number of AND gates, and on the relative number of known output bits with respect to the number of unknown key bits. This allows us to apply results from coding theory, and to explicitly connect the complexity of the algebraic cryptanalysis to the multiplicative complexity of the cipher. This means that we can provide asymptotic upper bounds on the complexity of algebraic attacks on selected families of ciphers based on the hardness of the decoding problem.     

Fuzzy nilpotent algebras

We define the concept of fuzzy nilpotent algebra, prove that the homomorphic inverse image of a fuzzy nilpotent algebra is also nilpotent and study the intersection and union of fuzzy nilpotent algebras.     

Mal'cev nilpotent algebras

We show that the Mal'cev semigroup identity x_n = y_n holds in the circle semigroup of an associative algebra over an infinite field precisely when the algebra is Lie nilpotent of class at most n. The Mal'cev semigroup law x_n = y_n holds in a group if and only if the group is nilpotent of class at most n.