-
Meeting #970
Andrey Mironov (Sobolev Institute of Mathematics)
"Rational functions on algebraic curves and commuting difference operators"
Abstract. In the report I will tell you how, using a certain set of rational functions on an algebraic curve, you can construct commuting difference operators. It will also be described how to obtain ordinary commuting differential operators using passage to the limit from commuting difference operators.
-
Meeting #969
Alexander Prolubnikov (Omsk State University)
"An approach to finding connected components of graphs using perturbations of adjacency matrices."
Abstract. We consider the problem of finding connected components of a graph. The natural approach to the problem is the breadth-first search (BFS) that is implemented in the software libraries which are using the benefits of modern computer architectures. We present the approach that uses perturbations of adjacency matrix of a graph to implement the connectivity test. To perform the test, we compare solutions of the two systems of linear algebraic equations (SLAE) which we associate with the unperturbed adjacency matrix and with the perturbed one. Such approach allows to use computationally effective implementations of numerical methods for solving SLAE to solve connectivity problems on graphs. Iterations of iterative methods for solving SLAE may be considered as implementations of graph traversals which, in general, are not equivalent to the traversal that is implemented by BFS. We present the algorithm to find connected components of a graph that uses such a traversal. For every instance of the problem, the computational complexity of the algorithm is not greater than the one of BFS, and it is lower than that in most instances.
-
Meeting #968
Alexey Nikitin (Deeplay, Omsk)
"Computations in universal classes with applications for graph and order models."
Abstract. In the talk I will present results concerning algebraic geometry over partially ordered sets:
1. Complexity of algorithms for solving systems of equations over partial orders;
2. Noethericity by equations for partial orders;
3. Decidability of theories over partial orders;
4. Construction of radicals and coordinate partial orders for systems of equations over partial orders and strict partially ordered sets. -
Meeting #967
Vitaly Roman'kov (Sobolev Institute of Mathematics)
"On the embedding of free nilpotent groups in partially commutative nilpotent groups."
Abstract. An algorithm is presented that allows one to calculate the maximum rank of a free nilpotent group of class k into a given partially commutative nilpotent group of class k.
-
Meeting #966
Marina Rasskazova (Omsk State Technical University)
"Binary Lie algebras and its application to the theory of Binary Lie superalgebras."
Abstract. The tropical structures min-plus and max-plus are well-known and have many interesting applications.
By definition an algebra \(B\) is binary-Lie algebra iff any two elements \(a,b\in B\) generate a Lie subalgebra. A \({\bf Z}_2-\)graded algebra \(B=B_0\oplus B_1\) is a binary-Lie superalgebra iff \(B\times \Gamma=B_0\otimes \Gamma_0\oplus B_1\otimes \Gamma_1\) is a binary Lie algebra, where \(\Gamma=\Gamma_0\oplus \Gamma_1\) is a Grassman algebra with natural gradation. We apply the theory of binary-Lie algebras for proving the following result.
Theorem. Let \(B=B_0\oplus B_1\) be a simple binary-Lie superalgebra finite dimensional over the field \({\bf C}\) of complex numbers. Then \(B_0\) is a solvable algebra or \(B\) is a Lie superalgebra.
This theorem reduced the problem (open yet!) of classification of a simple binary-Lie superalgebra finite dimensional over the field \({\bf C}\) to the case where subalgebra \(B_0\) is solvable.
This talk is based on the joint paper with A.Grishkov and I.Shestakov. -
Meeting #965
Matvei Kotov (Sobolev Institute of Mathematics)
"Tropical approach in cryptography."
Abstract. The tropical structures min-plus and max-plus are well-known and have many interesting applications.
In two papers “Tropical Cryptography” (2014) and “Tropical Cryptography II: extensions by homomorphisms” (2019), V. Shpilrain and D. Grigoriev suggested using tropical algebras as platforms for several cryptographic schemes in order to avoid linear algebra attacks. Another reason for their popularity is efficiency because multiplication is replaced by addition. Also, in “An application of different dioids in public key cryptography” (2014), M. Durcheva offered other cryptographic protocols based on tropical algebras and similar algebras. In recent years, other authors also developed some schemes in this area.
Many of these protocols were analyzed and attacks were developed by M. Kotov and A. Ushakov (2018), A. Muanalifah, and S. Sergeev (2020), D. Rudy and C. Monico (2020), S. Isaac and D. Kahrobaei (2021), K. Ahmed, S. Pal, and R. Mohan (2022).
Recently, we analyzed one of Durcheva’s protocols and implemented a successful attack (joint work with Ivan Buchinskiy and Alexander Treier).
In this talk, I will review the current status of tropical cryptography (protocols, methods to analyze them, and attacks) and discuss our new attack. -
Meeting #964
Alexander Rybalov (Sobolev Institute of Mathematics)
"Generic complexity of the word problem in some semigroups."
Abstract. Generic algorithms decide problems for almost all inputs and ignore remaining rare inputs. I.Kapovich, A.Myasnikov, P.Schupp and V.Shpilrain in 2003 suggested a generic algorithm, which decides the word problem in a wide class of finitely generated groups, including classical groups with undecidable word problem. D. Won in 2008 proposed a generic algorithm for finitely defined semigroups with so called balanced presentation. In particular, classical Markov-Post, Tseitin and Makanin semigroups with undecidable word problems, all have balanced representation. In 2019 M. Volkov at the Sverdlovsk semigroup seminar asked me about generic decidability of the word problem in every semigroup with one relation. For the classical decidability this is a well known and still open Adjan problem. In this talk I will present a generic algorithm for the word problem in a wide class of finitely generated semigroups, including balanced semigroups and semigroups with one relation.
-
Meeting #963
Alexander Kornev (Universidade Federal do ABC)
"Embedding of Malcev and alternative algebras."
Abstract. We continue studying associative f-representations, which was begun in A. I. Kornev, I.P. Shestakov, On associative representations of non-associative algebras, J. Algebra Appl.,17, No. 3, 1850051 (2018). We are interested in finding identities that an algebra satisfies if it has a faithful f-representation. We introduce the notions of g-associative and g-Lie algebras and we prove that any alternative (Malcev) algebra can be embedded into some g-associative (g-Lie) algebra. We show that any Malcev algebra can be embedded as a commutator subalgebra in some g-associative for two different polynomials g.
-
Meeting #962 (in Russian)
Artem Shevlyakov (Sobolev Institute of Mathematics)
"Varieties of equationally Noetherian semigroups and Plotkin`s problem."
Abstract. B.Plotkin posed a problem: find all varieties V of groups, where each G \in V is equationally Noetherian (i.e. any infinite system of equations is equivalent over G to a finite subsystem). In our talk we solve this problem for
a) semigroups
b) equations with constants
It will be obtained the description of such varieties by algebraic (structures of semigroups) and logical (set of identities) approaches. -
Meeting #961 (in Russian)
Irina Zubareva (Sobolev Institute of Mathematics)
"Abnormal extremals of abnormal sub-Finsler quasimetrics on four-dimensional Lie groups with three-dimensional generating distributions."
Abstract. All three-dimensional generating subspaces q of all four-dimensional real Lie algebras are found. Exact formulas for abnormal extremals are found for an arbitrary left-invariant sub-Finsler quasimetric d on any four-dimensional connected Lie group G with Lie algebra g defined by the seminorm F on q. On the basis of the structure constants of the Lie algebra g and the seminorm dual to F on g*, a criterion is established for the (non)strict abnormality of these extremals.
-
Meeting #960 (in Russian)
Alexei Miasnikov (Stevens Institute of Technology) (Sobolev Institute of Mathematics)
"General algebraic schemes, non-standard groups, and first-order classification."
Abstract. In this talk I will discuss a new notion of an algebraic group scheme and the related class of “new” algebraic groups (which, of course, contains the classical ones). This leads to some interesting results on the first-order classification problems and sheds new light on first-order rigidity and quasi-finite axiomatization. In another direction I will touch on non-standard models of groups (aka non-standard analysis), especially on non-standard models of the finitely generated ones with decidable or recursively enumerable word problems.
-
Meeting #959 (in Russian)
V.A. Roman'kov (Sobolev Institute of Mathematics)
"Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group."
Abstract. The submonoid membership problem for a finitely generated group $G$ is the decision problem, where for a given finitely generated submonoid $M$ of $G$ and a group element $g$ it is asked whether $g \in M$. We prove that for a sufficiently large direct power $\mathbb{H}^n$ of the Heisenberg group $\mathbb{H}$, there exists a finitely generated submonoid $M$ whose membership problem is algorithmically unsolvable. Thus, an answer is given to the question of M. Lohrey and B. Steinberg about the existence of a finitely generated nilpotent group with an unsolvable submonoid membership problem. It also answers the question of T. Colcombet, J. Ouaknine and P. Semukhin about the existence of such a group in the class of direct powers of the Heisenberg group (these authors proved that the submonoid membership problem for $\mathbb{H}$ itself is solvable). This result implies the existence of a similar submonoid in any free nilpotent group $N_{k,c}$ of sufficiently large rank $k$ of the class $c\geq 2$. The proofs are based on the undecidability of Hilbert's 10th problem and interpretation of Diophantine equations in nilpotent groups.
-
Meeting #958 (in Russian)
O.I. Krivorotko (Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk)
"Agent-based modeling of COVID-19: identifiability, regularization and software package."
Abstract. The paper presents the construction and analysis of an agent model of the spread of COVID-19 in the regions of the Russian Federation and other countries (Great Britain, Kazakhstan, New York State). The population of agents is divided into 4 layers of contact: households, educational institutions, workplaces and public places, and also combined into age groups with a step of 10 years. Each agent can be in one of 9 epidemiological states, the transition probabilities between which are controlled by parameters specific to each region.
Due to the novelty and complexity of the COVID-19 disease, as well as the social and economic processes that affect the nature of the spread, the parameters of the model are usually unknown, which leads to the need to solve inverse problems. The analysis of the identifiability of the model for the studied regions was carried out, on the basis of which the regularization of the solution of the inverse problem was carried out. The main algorithms for solving inverse problems of epidemiology are adapted: stochastic optimization, nature-like algorithms (genetic, differential evolution, particle swarm), methods of assimilation, big data analysis and machine learning. A software package has been created for the analysis and calculation of scenarios for the development of the epidemiological situation, taking into account economic, social and environmental processes.
Dear participants, we are glad to start a new semester of the seminar.
We are going to do some rebranding and change the title from Omsk Algebraic Webinar
to Omsk Algebraic Seminar. Therefore, we continue the numeration of the meetings from
the latest meeting of the Omsk Algebraic Seminar which was held typically offline.
The other things remain the same. -
Meeting #232
A.V. Eremeev (Sobolev Institute of Mathematics)
A.S Yurkov (Omsk scientific center SB RAS)"On a symmetry group for some problems of quadratic programming"
Abstract. Solution and analysis of mathematical programming problems may be simplified when these problems are symmetric under appropriate linear transformations. In particular, a knowledge of the symmetries may help decrease the problem dimension, reduce the size of the search space by means of linear cuts. While the previous studies of symmetries in the mathematical programming usually dealt with permutations of coordinates of the solutions space, the present paper considers a larger group of invertible linear transformations. We study a special case of the quadratic programming problem, where the objective function and constraints are given by quadratic forms. We formulate conditions, which allow us to transform the original problem to a new system of coordinates, such that the symmetries may be sought only among orthogonal transformations. In particular, these conditions are satisfied if the sum of all matrices of quadratic forms, involved in the constraints, is a positive definite matrix. We describe the structure and some useful properties of the group of symmetries of the problem. Besides that, the methods of detection of such symmetries are outlined for different special cases as well as for the general case.
-
Meeting #231
Alexander Zubkov
(Sobolev Institute of Mathematics & Al Ain University, UAE)"Orbits of actions of group superschemes"
Abstract. It is long known that any rational action of (not necessarily affine) algebraic group on a scheme of finite type has closed orbits. For example, if this group is reductive and affine, and the scheme on which the group acts is affine as well, then the closed orbits parametrize the points of the corresponding categorical quotient. In my talk I discuss the generalization of this fundamental result for algebraic group superschemes, rationally acting on superschemes of finite type.
-
Meeting #230
Alexei Miasnikov
(Stevens Institute of Technology, USA)"Logical, universal, and classical algebraic geometry and algebraic groups"
Abstract. In this talk I will discuss two types of algebraic geometries: the universal one (see the book by Daniyarova, Miasnikov and Remeslennikov) and the logical one (proposed by B.Plotkin) – the roles they currently play in modern algebra and what kind of perspectives they provide. In particular, I will touch on a new notion of an “algebraic group” and how it appears in group theory.
-
Meeting #229
Alexander Grishkov
(San Paulo University, Brazil)"Anderson modules and abelian extension of fields"
Abstract. The well known Kronecker-Weber theorem affirms that every finite abelian extension of the field \(Q\) of rational numbers belongs to some cyclotomic extension \(Q(t|t^n=1)\). In his 12th problem D.Hilbert asked how to generalize this theorem for other global fields.
In this talk, we give the exposition of atual state of this problem together with the connection with Carlitz-Drinfeld-Anderson modules.
Recall that Anderson module \(M\) is a (left)module over non-commutative ring \(R=C_p[T,\tau]\), \(T\tau=\tau T\), \(\tau a=a^p \tau\), where \(C_p\) is a some field of characteristic \(p>0\), such that \(M\) is free finite generated over subrings \(C_p[T]\) and \(C_p\{\tau\}\). -
Meeting #228
Denis Serbin
(Stevens Institute of Technology, NJ, USA)"Which properties of groups can be defined by their pregroup structures?"
Abstract. In this talk we discuss which properties of pregroups translate into the corresponding properties of their universal groups. First, we are going to give a survey of known results on the subject and then report some new results from the ongoing research on pregroup structures encoding hyperbolicity.
-
Meeting #227
Alexey Miasnikov
(Stevens Institute of Technology, NJ, USA)"Rich algebraic structures and weak second order logic"
Abstract. "What can be described by first-order formulas in a given algebraic structure \(A\)?" - an old and interest question. Of course, much depends on the structure \(A\). For example, in a free group, only cyclic subgroups (and the group itself) are definable in the first order logic, but in a free monoid of finite rank we can define any finitely generated submonoid. An algebraic structure \(A\) is called rich if the first order logic in \(A\) is equivalent to weak second order logic.
Surprising but there are many interesting groups, rings, and semigroups that are rich. I will talk about some of them, and then I will describe various algebraic, geometric and algorithmic properties that we able to describe by formulas in these systems.
Weak second order logic can be presented in algebraic systems in different ways: through HF-logic, or list superstructures over \(A\), or recursively enumerable (arithmetic) infinite disjunctions and conjunctions, or via finite binary predicates, etc. I will describe some particular form of this logic that is especially convenient for use in algebra, and show how to effectively translate such weak second-order formulas into equivalent first-order formulas in the case of a rich structure \(A\). -
Meeting #226
Artem Shevlyakov
(Sobolev Institute of Mathematics, Omsk, Russia)"Direct powers of algebraic structures in algebraic geometry"
Abstract. In this talk I begin with elementary properties of equations over direct powers of algebraic structures. We discuss the Noetherian property for direct powers of groups, semigroups, graphs etc. In the conclusion I present a general result asserting that a direct power PA of any finite algebraic structure A is weakly equationally Noetherian (i.e. any system of equations with constants over PA is equivalent to some finite system).
-
Meeting #225
Arkady Tsurkov
(Federal University of Rio Grande do Norte (UFRN) Natal, Brazil)"Automorphic equivalence in the classical varieties of linear algebras"
Abstract. We consider some variety of universal algebras \(\Theta\) and the category \(\Theta^0\). Objects of this category are finitely generated free algebras of the variety \(\Theta\), morphisms of this category are homomorphisms of these algebras.
After this we consider algebras \(H_1, H_2 \in \Theta\). The automorphisms of the category \(\Theta^0\) are very important in the study of the question when these algebras have same algebraic geometry.
In this talk we will consider as \(\Theta\) the classical varieties of linear algebras:- Variety of all linear algebras,
- Variety of all commutative algebras,
- Variety of all power associative algebras,
- Variety of all alternative algebras,
- Variety of all associative algebras,
- Variety of all Jordan algebras,
- Arbitrary subvariety of the variety of all anticommutative algebras over the arbitrary field k of characteristic \(0\).
The structure of the group of the all automorphisms of the category \(\Theta^0\) will be studied in all these cases. Also examples of algebras which are not geometric equivalent (the families of closed congruences are not coincides) but have the same algebraic geometry (exist a monotone bijection between these families) will be given in all these cases.
-
Meeting #224
Stepan Kuznetsov
(Steklov Mathematical Institute, Moscow)"Structures with non-standard Kleene stars"
Abstract. Kleene iteration, or Kleene star, is one of the most intriguing algebraic operations appearing in theoretical computer science. Usually, the Kleene star is interpreted as the limit of \(n\)-th powers of an element. This is how it behaves in algebras of formal languages and in relational algebras. In the talk, we shall show some examples of structures with non-standard Kleene iteration, and apply them to proving some results for corresponding logical theories.
-
Meeting #223
Andrey Mironov
(Sobolev Institute of Mathematics, Novosibirsk)"Birkhoff conjecture and angular billiards"
Abstract. We discuss Birkhoff conjecture on integrable billiards inside convex smooth curves on the plane.
-
Meeting #222
Alexander Mikhailov
(University of Leeds, UK)"Quantisation of free associative dynamical systems. Quantisation ideals"
Abstract.
-
Meeting #221
Alexander Zubkov
(Sobolev Institute of Mathematics)"Central elements of the distribution algebra of a general linear supergroup and supersymmetric elements"
Abstract. We discuss the notion of supersymmetric element, recently introduced in the joint work with F.Marko. We also show how it relates to the description of the center of the distribution algebra of a general linear supergroup as well as to the description of blocks of the category of supermodules over a general linear supergroup.
-
Meeting #220
Ruan Barbosa Fernandes
(Federal University of Rio Grande Do Norte, Brazil)"Automorphisms of the category of finitely generated free groups of the certain subvariety of the variety of all groups"
Abstract. In universal algebraic geometry the category \(Θ^0\) of finitely generated free algebras of some fixed variety Θ of algebras and the quotient group \(A/I\) are very important. Here \(A\) is the group of automorphisms of the category \(Θ^0\) and \(I\) is the group of inner automorphisms of this category.
In the varieties of all groups, of all abelian groups (B. Plotkin, G. Zhitomirski, "On automorphisms of categories of free algebras of some varieties", Journal of Algebra. 306:2 (2006), DOI: 10.1016/j.jalgebra.2006.07.028), of all nilpotent groups of the class no more than \(n\) (\(n ≥ 2\)) (A. Tsurkov, "Automorphisms of the category of the free nilpotent groups of the fixed class of nilpotency", International Journal of Algebra and Computation, 17(5/6) (2007), DOI: 10.1142/S021819670700413X.1273—1281) the group \(A/I\) is trivial. B. Plotkin posed the following question: "Is there a subvariety of the variety of all groups, such that the group \(A/I\) in this subvariety is not trivial?" A. Tsurkov hypothesized that for some varieties of periodic groups the group \(A/I\) is not trivial. In this talk we give an example of one particular subvariety of this kind. -
Meeting #219
Alexander Rybalov
(Sobolev Institute of Mathematics)"Generic complexity of two problems about semigroups"
Abstract. First problem is the word problem for some finitely defined semigroups. In 2008 Won suggested a simple generic algorithm for the word problem in finitely defined semigroups. It works for classical semigroups with undecidable word problem: Tseitin semigroup, Makanin semigroup. But it does not work for semigroups with one relation. The problem of existence of algorithms for word problem in these semigroups is still open, despite the efforts of Adjan and his students. In this talk I present a polynomial generic algorithm for some finitely defined semigroups, which works for Tseitin semigroups and semigroups with one relation.
Second problem is the isomorphism problem for finite semigroups, represented by multiplication tables. Kornienko, Zinchenko and Tyshkevich in 1982 proved that the famous graph isomorphism problem can be reduced in polynomial time to the isomorphism problem for finite semigroups. Thus it is still unknown, does it decidable in polynomial time. In this talk I will present a polynomial generic algorithm for the isomorphism problem for finite semigroups. -
Meeting #218
Motiejus Valiunas
(University of Wrocław, Poland)"Residually finite and equationally Noetherian groups"
Abstract. We say a group G is residually finite (\(RF\)) if any non-trivial element of \(G\) is non-trivial in some finite quotient, and equationally Noetherian (\(EN\)) if every system of equations in \(G\) is equivalent to a finite subsystem. These two properties, although a priori unrelated, turn out to exhibit similar behaviour, especially among finitely generated groups. For instance, all finitely generated linear groups and rigid soluble groups are both \(RF\) and \(EN\), certain wreath products and non-Hopfian groups are neither, and both of these properties are stable under taking subgroups, direct and free products, and finite extensions. Until recently, we did not seem to know any explicit examples of finitely generated groups that are \(RF\) but not \(EN\), or vice versa.
In this talk, I will compare and contrast the classes of finitely generated \(RF\) and \(EN\) groups. On the one hand, I will illustrate the similarities between these two classes by discussing their shared properties and introducing several "natural" common subclasses. On the other hand, I will give easy examples of finitely generated groups that are \(RF\) but not \(EN\), and vice versa. -
Meeting #217
Alexei Miasnikov
(Stevens Institute of Technology, USA)"Description of the coordinate groups of irreducible algebraic sets over free \(2\)-nilpotent groups"
Abstract. The talk is based on a joint work with M. Amaglobeli (Tbilisi State university) and V. Remeslennikov (Sobolev Institute of Mathematics).
We give a pure algebraic description of the coordinate groups of irreducible algebraic sets over non-abelian free \(2\)-nilpotent group \(N\). As a corollary we describe finitely generated groups \(H\) which are universally equivalent to the group \(N\) (with constants from \(N\) in the language). Besides, we give a pure algebraic criterion when a group \(H\), containing \(N\) as a subgroup, and \(N\)-separated by \(N\), is in fact \(N\)-discriminated by \(N\). -
Meeting #216
Josenildo Simões da Silva
(Federal University of Rio Grande Do Norte, Brazil)"Geometrical Equivalence and Action Type Geometrical Equivalence of Group Representations"
Abstract. The universal algebraic geometry of group representations was considered in: B. Plotkin, A. Tsurkov, “Action type geometrical equivalence of group representations”, Algebra and discrete mathematics, 4: (2005), 48-79. The concepts of geometrical equivalence and action type geometrical equivalence of group representations were defined. It was proved that if two representations are geometrically equivalent then they are action type geometrically equivalent. Also it was remarked that if two representations \((V_1,G_1)\) and \((V_2,G_2)\) are action type geometrically equivalent and groups G₁ and G₂ are geometrically equivalent, the representations \((V_1,G_1)\) and \((V_2,G_2)\) are not necessarily geometrically equivalent. However some specific counterexample was not presented. In this talk we fill the gap and construct the example of two representations \((V_1,G_1)\) and \((V_2,G_2)\) which are action type geometrically equivalent and groups \(G_1\) and \(G_2\) are geometrically equivalent, but the representations \((V_1,G_1)\) and \((V_2,G_2)\) are not geometrically equivalent.
-
Meeting #215
Artem Shevlyakov
"Plotkin`s problem for semigroups"
Abstract. B.Plotkin posed the following problem: when a wreath product of two groups is \(q_{\omega}\)-compact or equationally Noetherian? We solve this problem for wreath products of semigroups \(A\) wr \(B\) where \(B\) is infinite cyclic and \(A\) contains zero.
-
Meeting #214
Elena Aladova
(Federal University of Rio Grande Do Norte, Brazil)"Automorphisms of the category of free algebras"
Abstract. There are many various reasons why it is interesting to study automorphisms of some arbitrary algebraic structure. Our considerations are tightly connected with some problems in Universal Algebraic Geometry. The main goal of this talk is give a brief introduction to Universal Algebraic Geometry and to describe the method of verbal operations for a description of automorphisms of the category free finitely generated algebras in a given variety of algebras.