On the cycling operation in braid groups

The cycling operation is a special kind of conjugation that can be applied to elements in Artin’s braid groups, in order to reduce their length. It is a key ingredient of the usual solutions to the conjugacy problem in braid groups. In their seminal paper on braid-cryptography, Ko, Lee et al. proposed the cycling problem as a hard problem in braid groups that could be interesting for cryptography. In this paper we give a polynomial solution to that problem, mainly by showing that cycling is surjective, and using a result by Maffre which shows that pre-images under cycling can be computed fast. This result also holds in every Artin-Tits group of spherical type, endowed with the Artin Garside structure.On the other hand, the conjugacy search problem in braid groups is usually solved by computing some finite sets called (left) ultra summit sets (left-USSs), using left normal forms of braids. But one can equally use right normal forms and compute right-USSs. Hard instances of the conjugacy search problem correspond to elements having big (left and right) USSs. One may think that even if some element has a big left-USS, it could possibly have a small right-USS. We show that this is not the case in the important particular case of rigid braids. More precisely, we show that the left-USS and the right-USS of a given rigid braid determine isomorphic graphs, with the arrows reversed, the isomorphism being defined using iterated cycling. We conjecture that the same is true for every element, not necessarily rigid, in braid groups and Artin-Tits groups of spherical type.     

Theoretical and numerical considerations about Padé approximants for the matrix logarithm

We show that for a vast class of matrix Lie groups, which includes the orthogonal and the symplectic, diagonal Padé approximants of log((1+x)/(1−x)) are structure preserving. The conditioning of these approximants is analyzed. We also present a new algorithm for the Briggs–Padé method, based on a strategy for reducing the number of square roots in the inverse scaling and squaring procedure.     

A Signature Scheme Based on the Intractability of Computing Roots

We present RDSA, a variant of the DSA signature scheme, whose security is based on the intractability of extracting roots in a finite abelian group. We prove that RDSA is secure against an adaptively chosen message attack in the random oracle model if and only if computing roots in the underlying group is intractable. We report on a very efficient implementation of RDSA in the class group of imaginary quadratic orders. We also show how to construct class groups of algebraic number fields of degree < 2 in which RDSA can be implemented.     

Rn上的非初等变换群及其极限集

该文对高维非初等Mò'bius变换群进行了研究,得到了一些重要性质,给出了几个关于离散准则和代数收敛性的定理.     

Divisibility in certain automorphism groups

We study solvability of equations of the form x ⁿ = g in the groups of order automorphisms of archimedean-complete totally ordered groups of rank 2. We determine exactly which automorphisms of the unique abelian such group have square roots, and we describe all automorphisms of the general ones.     

~n上的非初等变换群及其极限集

该文对高维非初等Mobius变换群进行了研究,得到了一些重要性质,给出了几个关于离散准则和代数收敛性的定理.     

Counting the number of distinct real roots of certain polynomials by Bezoutian and the Galois groups over the rational number field

In this article, we count the number of distinct real roots of certain polynomials in terms of Bezoutian form. As an application, we construct certain irreducible polynomials over the rational number field which have given number of real roots and by the result of Oz Ben-Shimol [On Galois groups of prime degree polynomials with complex roots, Algebra Disc. Math. 2 (2009), pp. 99–107], we obtain an algorithm to construct irreducible polynomials of prime degree p whose Galois groups are isomorphic to S _p or A _p .     

Centraliser Dimension of Partially Commutative Groups

In a previous paper (Centraliser Dimension and Universal Classes of Groups), we investigated the centraliser dimension of groups. In the current paper we study properties of centraliser dimension for the class of free partially commutative groups and, as a corollary, we obtain an efficient algorithm for computation of centraliser dimension in these groups.Ilya V. Kazachkov, Vladimir N. Remeslennikov: Supported by RFFI grant N05-01-00057-a     

Coxeter Groups, 2-Completion, Perimeter Reduction and Subgroup Separability

We show that all groups in a very large class of Coxeter groups are locally quasiconvex and have a uniform membership problem solvable in quadratic time. If a group in the class satisfies a further hypothesis it is subgroup separable and relevant homomorphisms are also calculable in quadratic time. The algorithm also decides if a finitely generated subgroup has finite index.     

半监督度量学习内蕴最速下降算法的收敛性分析

主要研究对称正定矩阵群上的内蕴最速下降算法的收敛性问题.首先针对一个可转化为对称正定矩阵群上无约束优化问题的半监督度量学习模型,提出对称正定矩阵群上一种自适应变步长的内蕴最速下降算法.然后利用李群上的光滑函数在任意一点处带积分余项的泰勒展开式,证明所提算法在对称正定矩阵群上是线性收敛的.最后通过在分类问题中的数值实验说明算法的有效性.     

Sturm and Sylvester algorithms revisited via tridiagonal determinantal representations

First, we show that Sturm algorithm and Sylvester algorithm, which compute the number of real roots of a given univariate polynomial, lead to two dual tridiagonal determinantal representations of the polynomial. Next, we show that the number of real roots of a polynomial given by a tridiagonal determinantal representation is greater than the signature of this representation.     

A class of periodic groups

We deal with periodic groups saturated with dihedral groups. In particular, it is proved that periodic groups of bounded period, and also periodic Shunkov groups, saturated with dihedral groups, are locally finite.Supported by RFBR grant No. 03-01-00356 and by the Krasnoyarsk Science Foundation, project 11F0202C.Translated from Algebra i Logika, Vol. 44, No. 1, pp. 114–125, January–February, 2005.     

On Normal Subgroups of Coxeter Groups Generated by Standard Parabolic Subgroups

We discuss one construction of nonstandard subgroups in the category of Coxeter groups. Two formulae for the growth series of such a subgroups are given. As an application we construct a flag simple convex polytope, whose f-polynomial has non-real roots. Partially supported by a KBN grant 2 P03A 017 25     

On roots and squares – estimation,intuition and creativity

The paper presents findings of a small scale study of a few items related to problem solving with squares and roots, for different teacher groups (pre-service and in-service mathematics teachers: elementary and junior high school). The research participants were asked to explain what would be the units digit of a natural number to be squared in order to obtain a certain units digit as a result. They were also asked to formulate a rule – an algorithm for calculating the square of a 2-digit number which is a multiple of 5. Based on this knowledge and estimation capability, they were required to find, without using calculators, the square roots of given natural numbers. The findings show that most of the participants had only partial intuition regarding the units’ digit of a number which is squared when the units’ digit of the square is known. At the same time, the participants manifested some evidence of creativity and flow of ideas in identifying the rule for calculating the square of a natural number whose units digit is 5. However, when asked to identify, by means of estimation and based on knowledge from previous items, the square roots of three natural numbers, only few of them managed to find the three roots by estimation.     

The equation x 2 y 2 = g in partially commutative groups

A partially commutative group is a group defined by generators and relations so that all defining relations are of the form: the commutator of two generators is equal to the identity element. We consider an algorithm for checking whether a given group element is a product of two squares. This generalizes a result of Wicks for free groups.     

Linear optimization over permutation groups

For a permutation group given by a set of generators, the problem of finding “special” group members is NP-hard in many cases, e.g., this is true for the problem of finding a permutation with a minimum number of fixed points or a permutation with a minimal Hamming distance from a given permutation. Many of these problems can be modeled as linear optimization problems over permutation groups. We develop a polyhedral approach to this general problem and derive an exact and practically fast algorithm based on the branch & cut-technique.     

积分型总极值方法的最优性条件

郑权提出了求总极值问题的积分—水平集的概念性算法,同时给出了最优性条件.本文构造函数F(x),讨论了该函数的性质,证明求解原问题等价于求解方程F(c)=0的根.在文中给出了相应的总极值存在的最优性条件.     

Groups Saturated by a Finite Set of Groups

We study the periodic groups that are saturated by a finite set of finite (nonabelian simple) groups, obtaining some information about the elements of the saturating set.     

Bounded Rank Subgroups of Coxeter Groups, Artin Groups and One-Relator Groups with Torsion

We obtain a number of results regarding the freeness of subgroupsof Coxeter groups, Artin groups and one-relator groups withtorsion. In the case of Coxeter groups, we also obtain resultson quasiconvexity and subgroup separability. 2000 MathematicsSubject Classification 20F65, 20F55, 20F36, 20F06.