Average-case complexity and decision problems in group theory

We investigate the average-case complexity of decision problems for finitely generated groups, in particular, the word and membership problems. Using our recent results on “generic-case complexity”, we show that if a finitely generated group G has word problem solvable in subexponential time and has a subgroup of finite index which possesses a non-elementary word-hyperbolic quotient group, then the average-case complexity of the word problem of G is linear time, uniformly with respect to the collection of all length-invariant measures on G. This results applies to many of the groups usually studied in geometric group theory: for example, all braid groups B_n, all groups of hyperbolic knots, many Coxeter groups and all Artin groups of extra-large type.     

Automorphisms of Hyperbolic Groups and Graphs of Groups

Using the canonical JSJ splitting, we describe the outer automorphism group Out(G) of a one-ended word hyperbolic group G. In particular, we discuss to what extent Out(G) is virtually a direct product of mapping class groups and a free abelian group, and we determine for which groups Out(G) is infinite. We also show that there are only finitely many conjugacy classes of torsion elements in Out(G), for G any torsion-free hyperbolic group. More generally, let Γ be a finite graph of groups decomposition of an arbitrary group G such that edge groups G_e are rigid (i.e. Out(G_e) is finite). We describe the group of automorphisms of G preserving Γ, by comparing it to direct products of suitably defined mapping class groups of vertex groups.     

Some results on embeddings of algebras, after de Bruijn and McKenzie

In 1957, N.G. de Bruijn showed that the symmetric group Sym(Ω) on an infinite set Ω contains a free subgroup on 2^card(Ω) generators, and proved a more general statement, a sample consequence of which is that for any group A of cardinality card(Ω), the group Sym(Ω) contains a coproduct of 2^card(Ω) copies of A, not only in the variety of all groups, but in any variety of groups to which A belongs. His key lemma is here generalized to an arbitrary variety of algebras V, and formulated as a statement about functors Set V. From this one easily obtains analogs of the results stated above with “group” and Sym(Ω) replaced by “monoid” and the monoid Self(Ω) of endomaps of Ω, by “associative K-algebra” and the K-algebra End_K (V) of endomorphisms of a K-vector-space V with basis Ω, and by “lattice” and the lattice Equiv(Ω) of equivalence relations on Ω. It is also shown, extending another result from de Bruijn's 1957 paper, that each of Sym(Ω), Self(Ω) and End_K(V) contains a coproduct of 2^card(Ω) copies of itself.That paper also gave an example of a group of cardinality 2^card(Ω) that was not embeddable in Sym(Ω), and R. McKenzie subsequently established a large class of such examples. Those results are shown here to be instances of a general property of the lattice of solution sets in Sym(Ω) of sets of equations with constants in Sym(Ω). Again, similar results - this time of varying strengths - are obtained for Self(Ω), End_K(V), and Equiv(Ω), and also for the monoid Rel(Ω) of binary relations on Ω.Many open questions and areas for further investigation are noted.     

On generalizations of Fermat curves over finite fields and their automorphisms

Let 𝒳 be an irreducible algebraic curve defined over a finite field 𝔽_q of characteristic p>2. Assume that the 𝔽_q-automorphism group of 𝒳 admits a subgroup isomorphic to the direct product of two cyclic groups C_m and C_n of orders m and n prime to p, such that both quotient curves 𝒳∕C_n and 𝒳∕C_m are rational. In this paper, we provide a complete classification of such curves as well as a characterization of their full automorphism groups.     

Equations in polyadic groups

Systems of equations and their solution sets are studied in polyadic groups. We prove that a polyadic group (G,f)?=?der_𝜃,b(G,?) is equational noetherian, if and only if the ordinary group (G,?) is equational noetherian. The structure of coordinate polyadic group of algebraic sets in equational noetherian polyadic groups is also determined.     

The Field Descent Method

We obtain a broadly applicable decomposition of group ring elements into a “subfield part” and a “kernel part”. Applications include the verification of Lander’s conjecture for all difference sets whose order is a power of a prime >3 and for all McFarland, Spence and Chen/Davis/Jedwab difference sets. We obtain a new general exponent bound for difference sets. We show that there is no circulant Hadamard matrix of order v with 4<v<548, 964, 900 and no Barker sequence of length l with 13 < l ≤ 10²².     

A general framework of compactly supported splines and wavelets

Let {V_k} be a nested sequence of closed subspaces that constitute a multiresolution analysis of L²( ). We characterize the family Φ = {φ} where each φ generates this multiresolution analysis such that the two-scale relation of φ is governed by a finite sequence. In particular, we identify the ε Φ that has minimum support. We also characterize the collection Ψ of functions η such that each η generates the orthogonal complementary subspaces W_k of V_k, . In particular, the minimally supported ψ ε Ψ is determined. Hence, the “B-spline” and “B-wavelet” pair (, ψ) provides the most economical and computational efficient “spline” representations and “wavelet” decompositions of L² functions from the “spline” spaces V_k and “wavelet” spaces W_k, k . A very general duality principle, which yields the dual bases of both {(·−j):j and {η(·−j):j } for any η ε Ψ by essentially interchanging the pair of two-scale sequences with the pair of decomposition sequences, is also established. For many filtering applications, it is very important to select a multiresolution for which both and ψ have linear phases. Hence, “non-symmetric” and ψ, such as the compactly supported orthogonal ones introduced by Daubechies, are sometimes undesirable for these applications. Conditions on linear-phase φ and ψ are established in this paper. In particular, even-order polynomial B-splines and B-wavelets φ_m and ψ_m have linear phases, but the odd-order B-wavelet only has generalized linear phases.     

Fundamental Groups of Closed Manifolds with Positive Curvature and Torus Actions

We determine the fundamental group of a closed n-manifold of positive sectional curvature on which a torus T^k (k large) acts effectively and isometrically. Our results are: (A) If k>(n − 3)/4 and n ≥ 17, then the fundamental group π₁(M) is isomorphic to the fundamental group of a spherical 3-space form. (B) If k ≥ (n/6)+1 and n≠ 11, 15, 23, then any abelian subgroup of π₁(M) is cyclic. Moreover, if the T^k-fixed point set is empty, then π₁(M) is isomorphic to the fundamental group of a spherical 3-space form.Mathematics Subject Classification (2000). 53-XX*Supported partially by NSF Grant DMS 0203164 and by a reach found from Beijing normal university.**Supported partially by NSFC 10371008.     

On Recognition by Spectrum of Finite Simple Linear Groups over Fields of Characteristic 2

A finite group G is said to be recognizable by spectrum, i.e., by the set of element orders, if every finite group H having the same spectrum as G is isomorphic to G. We prove that the simple linear groups L _n (2^k) are recognizable by spectrum for n = 2^m ≥ 32.Original Russian Text Copyright © 2005 Vasil’ev A. V. and Grechkoseeva M. A.The authors were supported by the Russian Foundation for Basic Research (Grant 05-01-00797), the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant NSh-2069.2003.1), the Program “ Development of the Scientific Potential of Higher School” of the Ministry for Education of the Russian Federation (Grant 8294), the Program “Universities of Russia” (Grant UR.04.01.202), and a grant of the Presidium of the Siberian Branch of the Russian Academy of Sciences (No. 86-197).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 749–758, July–August, 2005.     

Polynomial identity rings as rings of functions

We generalize the usual relationship between irreducible Zariski closed subsets of the affine space, their defining ideals, coordinate rings, and function fields, to a non-commutative setting, where “varieties” carry a PGL_n-action, regular and rational “functions” on them are matrix-valued, “coordinate rings” are prime polynomial identity algebras, and “function fields” are central simple algebras of degree n. In particular, a prime polynomial identity algebra of degree n is finitely generated if and only if it arises as the “coordinate ring” of a “variety” in this setting. For n=1 our definitions and results reduce to those of classical affine algebraic geometry.     

Noncommutative algebras related with Schubert calculus on Coxeter groups

For any finite Coxeter system (W,S) we construct a certain noncommutative algebra, the so-called bracket algebra, together with a family of commuting elements, the so-called Dunkl elements. The Dunkl elements conjecturally generate an algebra which is canonically isomorphic to the coinvariant algebra of the Coxeter group W. We prove this conjecture for classical Coxeter groups and I₂(m). We define a “quantization” and a multiparameter deformation of our construction and show that for Lie groups of classical type and G₂, the algebra generated by Dunkl’s elements in the quantized bracket algebra is canonically isomorphic to the small quantum cohomology ring of the corresponding flag variety, as described by B. Kim. For crystallographic Coxeter systems we define the so-called quantum Bruhat representation of the corresponding bracket algebra. We study in more detail the structure of the relations in B_n-, D_n- and G₂-bracket algebras, and as an application, discover a Pieri-type formula in the B_n-bracket algebra. As a corollary, we obtain a Pieri-type formula for multiplication of an arbitrary B_n-Schubert class by some special ones. Our Pieri-type formula is a generalization of Pieri’s formulas obtained by A. Lascoux and M.-P. Schützenberger for flag varieties of type A. We also introduce a super-version of the bracket algebra together with a family of pairwise anticommutative elements, the so-called flat connections with constant coefficients, which describes “a noncommutative differential geometry on a finite Coxeter group” in the sense of S. Majid.     

Reflection sieve obstructions in finite groups of type dn

In [4] we constructed certain homology representations of a finite group G of type A_n, B_n or C_n, and showed that these representations can be used to sift out the reflection compound characters of G. In the present note, we show that for a group G of type D_n, each reflection compound character π^(k), 2 k n − 2, determines a unique “obstruction” character θ^(k), which occurs with positive multiplicity in every homology representation containing π^(k).     

Reflection Theorems and the Tame Kernel of a Number Field

Let L be a number field containing the pth primitive root of unity ζ _p . We investigate the p-rank of the ideal class groups of some subfields of L by using reflection theorems and establish relations between the p-rank of the ideal class groups and that of groups of units of some subfields of L.

Let F be a number field and 𝒪 _F the ring of integers in F. We also study the p-rank of tame kernels of F and establish relations between the p-rank of K ₂𝒪 _F and that of some direct summands of the ideal class group of F(ζ _p ).     

Numerical Schottky Uniformizations

A real algebraic curve of algebraic genus g ≥ 2 is a pair (S, τ), where S is a closed Riemann surface of genus g and τ is a reflection on S (anticonformal involution with fixed points). In this note, we discuss a numerical (Burnside) program which permits to obtain a Riemann period matrix of the surface S in terms of an uniformizing real Schottky group. If we denote by Aut₊(S, τ) the group of conformal automorphisms of S commuting with the real structure τ, then it is a well known fact that |Aut₊(S,τ)| ≥ 12(g−1). We say that (S,τ) is maximally symmetric if |Aut₊(S,τ)|=12(g−1). We work explicitly such a numerical program in the case of maximally symmetric real curves of genus two. We construct a real Schottky uniformization for each such real curve and we use the numerical program to obtain a real algebraic curve, a Riemann period matrix and the accessory parameters in terms of the corresponding Schottky uniformization. In particular, we are able to give for Bolza’s curve a Schottky uniformization (at least numerically), providing an example for which the inverse uniformization theorem is numerically solved.Partially supported by Projects Fondecyt 1030252 1030373 and UTFSM 12.03.21     

Effacement des dérivations et spectres premiers des algèbres quantiques

Given any (commutative) field k and any iterated Ore extension R=k[X₁][X₂;σ₂,δ₂][X_N;σ_N,δ_N] satisfying some suitable assumptions, we construct the so-called “Derivative-Elimination Algorithm.” It consists of a sequence of changes of variables inside the division ring F=Fract(R), starting with the indeterminates (X₁,…,X_N) and terminating with new variables (T₁,…,T_N). These new variables generate some quantum-affine space such that . This algorithm induces a natural embedding which satisfies the following property:

Full-size image

. We study both the derivative-elimination algorithm and natural embedding and use them to produce, for the general case, a (common) proof of the “quantum Gelfand–Kirillov” property for the prime homomorphic images of the following quantum algebras: , (wW), R_q[G] (where G denotes any complex, semi-simple, connected, simply connected Lie group with associated Lie algebra and Weyl group W), quantum matrices algebras, quantum Weyl algebras and quantum Euclidean (respectively symplectic) spaces. Another application will be given in [G. Cauchon, J. Algebra, to appear]: In the general case, the prime spectrum of any quantum matrices algebra satisfies the normal separation property.     

On the tensor product of a finite and an infinite dimensional representation

There are two main results in the paper. The first gives the infinitesimal character that can occur in the tensor product V V_λ of an irreducible finite dimensional representation V_λ and an irreducible infinite dimensional representation V of a semisimple Lie algebra . The statement is that the infinitesimal characters are x_{v + μi}, I = 1, 2,…, k, where μ_i are the weights of V_λand v is the “pseudo” highest weight of V.The second result proves that if V is a Harish-Chandra module (one which comes from a group representation), then V V_λ has a finite composition series. But then the irreducible components in the composition series have the infinitesimal characters given in the first results.     

Graded Quantum Groups and Quasitriangular Hopf Group-Coalgebras

ABSTRACT

Starting from a Hopf algebra endowed with an action of a group π by Hopf automorphisms, we construct (by a “twisted” double method) a quasitriangular Hopf π-coalgebra. This method allows us to obtain non-trivial examples of quasitriangular Hopf π-coalgebras for any finite group π and for infinite groups π such as GL _n (𝕂). In particular, we define the graded quantum groups, which are Hopf π-coalgebras for π = ?[[h]] ^l and generalize the Drinfeld-Jimbo quantum enveloping algebras.     

On the algebra structure of some bismash products

We study several families of semisimple Hopf algebras, arising as bismash products, which are constructed from finite groups with a certain specified factorization. First we associate a bismash product H_q of dimension q(q−1)(q+1) to each of the finite groups PGL₂(q) and show that these H_q do not have the structure (as algebras) of group algebras (except when q=2,3). As a corollary, all Hopf algebras constructed from them by a comultiplication twist also have this property and are thus non-trivial. We also show that bismash products constructed from Frobenius groups do have the structure (as algebras) of group algebras.     

Uniformly generated submodules of permutation modules: Over fields of characteristic 0

This paper is motivated by a link between algebraic proof complexity and the representation theory of the finite symmetric groups. Our perspective leads to a new avenue of investigation in the representation theory of S_n. Most of our technical results concern the structure of “uniformly” generated submodules of permutation modules. For example, we consider sequences of submodules of the permutation modules M^(n−k,1k) and prove that if the sequence W_n is given in a uniform (in n) way – which we make precise – the dimension p(n) of W_n (as a vector space) is a single polynomial with rational coefficients, for all but finitely many “singular” values of n. Furthermore, we show that dim(W_n)<p(n) for each singular value of n≥4k. The results have a non-traditional flavor arising from the study of the irreducible structure of the submodules W_n beyond isomorphism types. We sketch the link between our structure theorems and proof complexity questions, which are motivated by the famous NP vs. co-NP problem in complexity theory. In particular, we focus on the complexity of showing membership in polynomial ideals, in various proof systems, for example, based on Hilbert's Nullstellensatz.     

The net Bayes premium with dependence between the risk profiles

In Bayesian analysis it is usual to assume that the risk profiles Θ₁ and Θ₂ associated with the random variables “number of claims” and “amount of a single claim”, respectively, are independent. A few studies have addressed a model of this nature assuming some degree of dependence between the two random variables (and most of these studies include copulas). In this paper, we focus on the collective and Bayes net premiums for the aggregate amount of claims under a compound model assuming some degree of dependence between the random variables Θ₁ and Θ₂. The degree of dependence is modelled using the Sarmanov–Lee family of distributions [Sarmanov, O.V., 1966. Generalized normal correlation and two-dimensional Frechet classes. Doklady (Soviet Mathematics) 168, 596–599 and Ting-Lee, M.L., 1996. Properties and applications of the Sarmanov family of bivariate distributions. Communications Statistics: Theory and Methods 25 (6) 1207–1222], which allows us to study the impact of this assumption on the collective and Bayes net premiums. The results obtained show that a low degree of correlation produces Bayes premiums that are highly sensitive.