On some properties of Hall elements in the free nonassociative algebra

We study certains aspects of a particular Hall set constructed with respect to the alpabetical order. In our main result we show how this Hall set leads to the construction of a family of generators of the kernel of “from right to left Lie bracketing” mapping. This construction is based on certain remarkable properties of these generators.      

Hochschild cohomology of algebras of semidihedral type. II. Local algebras

In terms of generators and relations, the Hochschild cohomology algebra is described for a family of local algebras of semidihedral type over the ground field that has characteristic not equal to 2. In relevant calculations, the free bimodule resolution that was constructed in another author’s paper is used. Bibliography: 22 titles.     

Hochschild cohomology for self-injective algebras of tree class <Emphasis Type="Italic">D</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>. III

In terms of generators and relations, the Hochschild cohomology algebra is described for a family of representation-finite self-injective algebras of tree class D ₄. In calculations, the minimal projective bimodule resolution that was constructed in another authors’ paper is used. Bibliography: 10 titles.     

On a problem of integral geometry related to the Dirichlet problem for an ultrahyperbolic equation

We study the nontrivial solvability of the homogeneous problem of integral geometry on the family of spheres formed by sections of the (n − 1)-dimensional unit sphere by hyperplanes perpendicular to the generators of a given cone. By using a relationship between this problem and the Dirichlet problem for an ultrahyperbolic equation in a ball and a criterion for the failure of uniqueness of the solution of the latter problem in terms of zeros of classical Jacobi polynomials, we obtain a criterion for the uniqueness of the solution of the former problem.     

The word and Riemannian metrics on lattices of semisimple groups

Let G be a semisimple Lie group of rank ⩾2 and Γ an irreducible lattice. Γ has two natural metrics: a metric inherited from a Riemannian metric on the ambient Lie group and a word metric defined with respect to some finite set of generators. Confirming a conjecture of D. Kazhdan (cf. Gromov [Gr2]) we show that these metrics are Lipschitz equivalent. It is shown that a cyclic subgroup of Γ is virtually unipotent if and only if it has exponential growth with respect to the generators of Γ.     

Expansion Of Product Replacement Graphs

We establish a connection between the expansion coefficient of the product replacement graph Γ_k(G) and the minimal expansion coefficient of a Cayley graph of G with k generators. In particular, we show that the product replacement graphs Γ_k(PSL(2,p)) form an expander family, under assumption that all Cayley graphs of PSL(2,p), with at most k generators are expanders. This gives a new explanation of the outstanding performance of the product replacement algorithm and supports the speculation that all product replacement graphs are expanders [42,52].     

Monodromy of certain Painlevé–VI transcendents and reflection groups

We study the global analytic properties of the solutions of a particular family of Painlevé VI equations with the parameters β=γ=0, δ= and 2α=(2μ-1)² with arbitrary μ, 2μ≠∈ℤ. We introduce a class of solutions having critical behaviour of algebraic type, and completely compute the structure of the analytic continuation of these solutions in terms of an auxiliary reflection group in the three dimensional space. The analytic continuation is given in terms of an action of the braid group on the triples of generators of the reflection group. We show that the finite orbits of this action correspond to the algebraic solutions of our Painlevé VI equation and use this result to classify all of them. We prove that the algebraic solutions of our Painlevé VI equation are in one-to-one correspondence with the regular polyhedra or star-polyhedra in the three dimensional space. Oblatum 19-III-1999 & 25-XI-1999?Published online: 21 February 2000     

The Picard–Lefschetz formula for p-adic cohomology

In this paper, we discuss a p-adic analogue of the Picard–Lefschetz formula. For a family with ordinary double points over a complete discrete valuation ring of mixed characteristic (0,p), we construct vanishing cycle modules which measure the difference between the rigid cohomology groups of the special fiber and the de Rham cohomology groups of the generic fiber. Furthermore, the monodromy operators on the de Rham cohomology groups of the generic fiber are described by the canonical generators of the vanishing cycle modules in the same way as in the case of the ℓ-adic (or classical) Picard–Lefschetz formula. For the construction and the proof, we use the logarithmic de Rham–Witt complexes and those weight filtrations investigated by Mokrane (Duke Math. J. 72(2):301–337, 1993).      

Analysis and synthesis of Ultra-uniform Pseudorandom Number Generators

The Wichmann–Hill algorithm is a high-performance generatorof uniformly distributed pseudorandom numbers, designed foruse on, and portability between, 8-bit of 16-bit machines. Twoanalyses (one number-theoretic, the other probability-theoretic)are presented in order to explain its superb performance. Itis shown that the original Wichmann–Hill configurationcan be regarded as a single linear congruential generator withunrealizably large multiplier and modulus decomposed into threerealizable subgenerators. This provides an obvious insight intothe source of the generator's high quality, but more importantlypermits, for the first time, the application of the extremelystringent Coveyou-MacPherson spectral test—which is passedwith flying colours. The techniques used for analysis have also been applied to designand test a large family of three-component generalized Wichmann–Hill-typegenerators with substantially the same very high performanceas the original. Over one hundred such generators have beenfound. There is no difficulty in extending the design to configurationssuitable for 32-bit machines, with some improvement in the quality.Increasing the number of subgenerators produces a more dramaticenhancement: this is illustrated by means of an example employingfour components.     

Rank 2 Nichols Algebras with Finite Arithmetic Root System

The concept of arithmetic root systems is introduced. It is shown that there is a one-to-one correspondence between arithmetic root systems and Nichols algebras of diagonal type having a finite set of (restricted) Poincaré–Birkhoff–Witt generators. This has strong consequences for both objects. As an application all rank 2 Nichols algebras of diagonal type having a finite set of (restricted) Poincaré–Birkhoff–Witt generators are determined. Supported by the European Community under a Marie Curie Intra-European Fellowship.     

Centers of Mal’tsev and alternative algebras

Let ϕ be an associative commutative ring with unity containing 1/6. Let A and B be a free Mal’tsev and a free alternative ϕ-algebras on a set of k≥6 free generators, respectively. We construct nonzero homogeneous elements of degree 7 belonging to an annihilatorAnnA of A, and nonzero homogeneous elements of degree 7 belonging to the center Z(B) of B. It is shown that a nilpotent Mal’tsev algebra of index 8 on a set of 6 generators has no faithful representation. Supported by RFFR grant No. 96-01-01511, and by the Program “Universities of Russia: Fundamental Research.” Translated fromAlgebra i Logika, Vol. 38, No. 5, pp. 613–635, September–October, 1999.     

One way functions and pseudorandom generators

Pseudorandom generators transform in polynomial time a short random “seed” into a long “pseudorandom” string. This string cannot be random in the classical sense of [6], but testing that requires an unrealistic amount of time (say, exhaustive search for the seed). Such pseudorandom generators were first discovered in [2] assuming that the function (a ^x modb) is one-way, i.e., easy to compute, but hard to invert on a noticeable fraction of instances. In [12] this assumption was generalized to the existence of any one-way permutation. The permutation requirement is sufficient but still very strong. It is unlikely to be proven necessary, unless something crucial, like P=NP, is discovered. Below, among other observations, a weaker assumption about one-way functions is proposed, which is not only sufficient, but also necessary for the existence of pseudorandom generators. Supported by NSF grant #DCR-8304498, DCR-8607492.     

Functional equations for transfer-matrix operators in open Hecke chain models

We consider integrable open chain models formulated in terms of the generators of affine Hecke algebras. We use the fusion procedure to construct the hierarchy of commutative elements, which are analogues of the commutative transfer matrices. These elements satisfy a set of functional relations generalizing functional relations for a family of transfer matrices in solvable spin chain models of the U_q(gl(n|m)) type. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 150, No. 2, pp. 219–236, February, 2007.     

Design of Practical and Provably Good Random Number Generators

We present a construction for a family of pseudo-random generators that are very fast in practice, yet possess provable statistical and cryptographic unpredictability properties. Such generators are useful for simulations, randomized algorithms, and cryptography.Our starting point is a slow but high quality generator whose use can be mostly confined to a preprocessing step. We give a method of stretching its outputs that yields a faster generator. The fast generator offers smooth memory–time–security trade-offs and also has many desired properties that are provable. The slow generator can be based on strong one-way permutations or block ciphers. Our implementation based on the block cipher DES is faster than popular generators.     

An Infinite Presentation of the Torelli Group

In this paper, we construct an infinite presentation of the Torelli subgroup of the mapping class group of a surface whose generators consist of the set of all “separating twists”, all “bounding pair maps”, and all “commutators of simply intersecting pairs” and whose relations all come from a short list of topological configurations of these generators on the surface. Aside from a few obvious ones, all of these relations come from a set of embeddings of groups derived from surface groups into the Torelli group. In the process of analyzing these embeddings, we derive a novel presentation for the fundamental group of a closed surface whose generating set is the set of all simple closed curves.     

Multi-Box Splines

We construct local generators, comprising r functions, for refinable spaces of bivariate C^n-1 spline functions of degree n on meshes comprising all lines through points of the integer lattice in the directions of n + r + 1 pairwise linearly independent vectors with integer components. The generators are characterised by their Fourier transforms. Their shifts are shown to form a Riesz basis if and only if at most r lines in the mesh intersect other than in the integer lattice, which can occur for n ≤ 2r - 1. The symmetry of these generators is studied and examples are given.     

Generators of some Ramanujan formulas

In this paper we prove some Ramanujan type formulas for 1/π but without using the theory of modular forms. Instead we use the WZ—method created by H. Wilf and D. Zeilberger and find some hypergeometric functions in two variables which are second components of WZ—pairs than can be certified using Zeilberger's EKHAD package. These certificates have an additional property which allows us to get generalized Ramanujan's type series which are routinely proven by computer. We call these second hypergeometric components of the WZ—pairs generators. Finding generators seems a hard task but using a kind of experimental research (explained below), we have succeeded in finding some of them. Unfortunately we have not found yet generators for the most impressive Ramanujan's formulas. We also prove some interesting binomial sums for the constant 1/π². Finally we rewrite many of the obtained series using pochhammer symbols and study the rate of convergence. 2000 Mathematics Subject Classification Primary—33C20     

Approximation Orders of FSI Spaces in L 2 (R d )

A second look at the authors' [BDR1], [BDR2] characterization of the approximation order of a Finitely generated Shift-Invariant subspace S(Φ) of L ₂ (R ^d ) results in a more explicit formulation entirely in terms of the (Fourier transform of the) generators of the subspace. Further, when the generators satisfy a certain technical condition, then, under the mild assumption that the set of 1-periodizations of the generators is linearly independent, such a space is shown to provide approximation order k if and only if contains a ψ (necessarily unique) satisfying . The technical condition is satisfied, e.g., when the generators are at infinity for some ρ>k+d . In the case of compactly supported generators, this recovers an earlier result of Jia [J1], [J2]. March 19. 1996. Date revised: September 6, 1996.     

Local semilattices on two generators

The set of idempotents of a pseudo-inverse semigroup (see Nambooripad [11]) is referred to as alocal semilattice in this paper (it was called a “partially associative pseudo-semilattice” by Nambooripad). Local semilattices form a variety and so free local semilattices exist. The free local semilattice F₂ on two generators was described and studied by Meakin and Pastijn in [7]. In this paper we describe all local semilattices on two generators as images of F₂. To Professor L.M. Gluskin, on his 60th birthday This research was supported by NSF Grant No. MCS 8002901     

A Method of Systematic Search for Optimal Multipliers in Congruential Random Number Generators

This paper presents a method of systematic search for optimal multipliers for congruential random number generators. The word-size of computers is a limiting factor for development of random numbers. The generators for computers up to 32 bit word-size are already investigated in detail by several authors. Some partial works are also carried out for moduli of 2⁴⁸ and higher sizes. Rapid advances in computer technology introduced recently 64 bit architecture in computers. There are considerable efforts to provide appropriate parameters for 64 and 128 bit moduli. Although combined generators are equivalent to huge modulus linear congruential generators, for computational efficiency, it is still advisable to choose the maximum moduli for the component generators. Due to enormous computational price of present algorithms, there is a great need for guidelines and rules for systematic search techniques. Here we propose a search method which provides ‘fertile’ areas of multipliers of perfect quality for spectral test in two dimensions. The method may be generalized to higher dimensions. Since figures of merit are extremely variable in dimensions higher than two, it is possible to find similar intervals if the modulus is very large. This revised version was published online in July 2006 with corrections to the Cover Date.