Frucht theorem for inverse semigroups

In the paper, the problem of representing a finite inverse semigroup by partial transformations of a graph is treated. The notions of weighted graph and its weighted partial isomorphisms are introduced. The main result is that any finite inverse semigroup is isomorphic to the semigroup of weighted partial isomorphisms of a weighted graph. This assertion is a natural generalization of the Frucht theorem for groups. Translated fromMatematicheskie Zametki, Vol. 61, No. 2, pp. 246–251, February, 1997. This research was partially supported by the International Science Foundation under grant No. GSU 041049. Translated by A. I. Shtern     

Extremum problems for functions with small support

In this paper we consider an extremum problem for even periodic functions having small intervals as their supports and subject to restrictions on the sum of the absolute values of their Fourier coefficients. Translated fromMatematicheskie Zametki, Vol. 60, No. 3, pp. 323–332, September, 1996. We wish to express our gratitude to S. B. Stechkin for his interest in our work. This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00378, and the work of the first and second authors also by the International Science Foundation under grant No. MC5300.     

An Adjacency Criterion for the Prime Graph of a Finite Simple Group

For every finite non-Abelian simple group, we give an exhaustive arithmetic criterion for adjacency of vertices in a prime graph of the group. For the prime graph of every finite simple group, this criterion is used to determine an independent set with a maximal number of vertices and an independent set with a maximal number of vertices containing 2, and to define orders on these sets; the information obtained is collected in tables. We consider several applications of these results to various problems in finite group theory, in particular, to the recognition-by-spectra problem for finite groups. Supported by RFBR grant No. 05-01-00797; by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1; by the RF Ministry of Education Developmental Program for Scientific Potential of the Higher School of Learning, project No. 8294; by FP “Universities of Russia,” grant No. UR.04.01.202; and by Presidium SB RAS grant No. 86-197. __________ Translated from Algebra i Logika, Vol. 44, No. 6, pp. 682–725, November–December, 2005.     

On stability of the P n mod /P n element for incompressible flow problems

It is well known that finite element spaces used for approximating the velocity and the pressure in an incompressible flow problem have to be stable in the sense of the inf-sup condition of Babuška and Brezzi if a stabilization of the incompressibility constraint is not applied. In this paper we consider a recently introduced class of triangular nonconforming finite elements of nth order accuracy in the energy norm called P _n ^mod elements. For n ≤ 3 we show that the stability condition holds if the velocity space is constructed using the P _n ^mod elements and the pressure space consists of continuous piecewise polynomial functions of degree n. This research has been supported by the Grant Agency of the Czech Republic under the grant No. 201/05/0005 and by the grant MSM 0021620839.     

The number of periodic solutions of polynomial differential equations

We estimate the number of periodic solutions for special classes ofnth-order ordinary differential equations with variable coefficients. Translated fromMatematicheskie Zametki, Vol. 64, No. 5, pp. 720–727, November, 1998. The author thanks Yu. S. Il'yashenko for setting the problems, permanent advice, and overall support. The author is also thankful to D. A. Panov for numerous discussions. This research was supported by the CRDF Foundation under grant MR1-220, by the INTAS Foundation under grant No. 93-05-07, and by the Russian Foundation for Basic Research under grant No. 95-01-01258.     

Logarithmic asymptotics of solutions of the large deviation problem for the boltzmann equation with small transfer of momentum

For the Boltzmann equation with small transfer of momentum, we derive a system of nonlinear integral-differential equations describing the logarithmic asymptotics of the solution to the Cauchy problem in the domain at the distanceO(1) from the support of the initial condition.Translated fromMatematicheskie Zametki, Vol. 64, No. 1, pp. 73–94, July, 1998.This research was partially supported by INTAS-RFBR under grant No. 95-91 in the case of the first author, and by INTAS under grant No. 96-0698 in the case of the second author.     

Inverse spectral problem for the operators with non‐local potential

The main object under consideration in the paper is the second derivative operator on a finite interval with zero boundary conditions perturbed by a self‐adjoint integral operator with the degenerate kernel (non‐local potential). The inverse problem, i.e., the reconstruction of the perturbation from the spectral data, is solved by means of the step‐by‐step procedure based on the n‐interlacing property of the spectrum.     

Two-letter group codes that preserve aperiodicity of inverse finite automata

We construct group codes over two letters (i.e., bases of subgroups of a two-generated free group) with special properties. Such group codes can be used for reducing algorithmic problems over large alphabets to algorithmic problems over a two-letter alphabet. Our group codes preserve aperiodicity of inverse finite automata. As an application we show that the following problems are PSpace-complete for two-letter alphabets (this was previously known for large enough finite alphabets): The intersection-emptiness problem for inverse finite automata, the aperiodicity problem for inverse finite automata, and the closure-under-radical problem for finitely generated subgroups of a free group. The membership problem for 3-generated inverse monoids is PSpace-complete. Both authors were supported in part by NSF grant DMS-9970471. The first author was also supported in part by NSF grant CCR-0310793. The second author acknowledges the support of the Excellency Center, “Group Theoretic Methods for the Study of Algebraic Varieties” of the Israeli Science Foundation.     

Solvability of the conjugacy problem for finite subgroups in automorphism groups of free groups

We prove that there exists an algorithm which solves a conjugacy problem for finite subgroups in automorphism and outer automorphism groups of a free group of finite rank. Of independent interest is the construction of an algorithm of decomposing an arbitrary free-by-finite group into a fundamental group of a finite graph of finite groups, with the number of steps evaluated explicitly. In passing, we solve the conjugacy problem for finite subgroups in almost free groups. As a consequence, an algorithm is obtained computing generating sets for a group of fixed points in an arbitrary finite automorphism group of a free group of finite rank.Translated fromAlgebra i Logika, Vol. 34, No. 5, pp. 558–606, September-October, 1995.Supported by the RFFR grant No. 93-011-1508 and by the ISF (International Science Foundation) grant RPC000.     

Recognition of simple groups U 3(Q) by element orders

An exhaustive solution is given to the recognition-by-spectrum problem for finite, simple, three-dimensional unitary groups. For every such group, the number of non-isomorphic, finite, isospectral groups is determined. In particular, a new counterexample to Problem 13.63 in the Kourovka Notebook is furnished. Supported by RFBR grant No. 05-01-00797, and by SB RAS Young Researchers Support grant No. 29 and Integration Project No. 2006.1.2. __________ Translated from Algebra i Logika, Vol. 45, No. 2, pp. 185–202, March–April, 2006.     

Generalized polynomial approximation providing the best reference

We pose the extremum problem of finding a polynomial approximation for a function of several variables so that this approximation by a fragment of the function provides the best reference. We obtain an upper bound for the modulus of informativity of polynomials and rational functions.Translated fromMatematickeskie Zametki, Vol. 60, No. 5, pp. 658–669, November, 1996.The author wishes to thank Yu. N. Subbotin for valuable discussions.This research was supported by the Russian Foundation for Basic Research under grant No. 93-011-196.     

Integral characteristics in the inverse problem of magnetotelluric sounding

This article examines some aspects of the one-dimensional inverse problem of magnetotelluric sounding. A uniqueness theorem is proved in the presence ofS-surfaces. A numerical algorithm based on transformation formulas is proposed. This research was partially supported by Russian Foundation for Basic Research (grant No. 96-01-00410) and by the State Scientific-Technical Program “Future Information Technologies” (grant No. 0201.06.010). Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 53–66, 1998.     

Scattering in a Forked-Shaped Waveguide

We consider wave scattering in a forked-shaped waveguide which consists of two finite and one half-infinite intervals having one common vertex. We describe the spectrum of the direct scattering problem and introduce an analogue of the Jost function. In case of the potential which is identically equal to zero on the half-infinite interval, the problem is reduced to a problem of the Regge type. For this case, using Hermite-Biehler classes, we give sharp results on the asymptotic behavior of resonances, that is, the corresponding eigenvalues of the Regge-type problem. For the inverse problem, we obtain sufficient conditions for a function to be the S-function of the scattering problem on the forked-shaped graph with zero potential on the half-infinite edge, and present an algorithm that allows to recover potentials on the finite edges from the corresponding Jost function. It is shown that the solution of the inverse problem is not unique. Some related general results in the spectral theory of operator pencils are also given. This work was supported by the grant UM1-2567-OD-03 from the Civil Research and Development Foundation (CRDF). YL was partially supported by the NSF grants 0338743, 0354339 and 0754705, by the Research Board and Research Council of the University of Missouri, and by the EU Marie Curie “Transfer of Knowledge” program.     

A singularly perturbed boundary value problem for a second-order equation in the case of variation of stability

A boundary value problem for a second-order nonlinear singularly perturbed differential equation is considered for the case in which there is variation of stability caused by the intersection of roots of the degenerate equation. By the method of differential inequalities, we prove the existence of a solution such that the limit solution is nonsmooth. Translated fromMatematicheskie Zametki, Vol. 63, No. 3, pp. 354–362, March, 1998. This research was partially supported by the Russian Foundation for Basic Research under grant No. 96-01-00694.     

The Word Problem for Polynilpotent Groups with a Single Primitive Defining Relation

It is shown that polynilpotent groups with a single primitive defining relation have a decidable word problem. Supported by RFBR grant No. 05-01-00292. __________ Translated from Algebra i Logika, Vol. 45, No. 1, pp. 28–43, January–February, 2006.     

Regular sets in residual classes

Sets regular modulo a fixed odd prime power are explicitly constructed under the condition that their cardinalities do not exceed an arbitrarily small positive power of the modulus.Translated fromMatematicheskie Zametki, Vol. 64, No. 2, pp. 224–228, August, 1998.This research was supported by the Russian Foundation for Basic Research under grant No. 97-01-00721 and by the Professor B. Novak grant (Karlov University, Prague).     

On continuous extension of locally homeomorphic simplicial maps of ℝ2 into itself byσ-processes

It is shown that the Klein bottle with two points removed can be embedded in the compactification of ℝ² by a finite tree. Translated fromMatematicheskie Zametki, Vol. 59, No. 6, pp. 821–831, June, 1996. I wish to express sincere gratitude to A. G. Vitushkin for posing the problem and guidance. This research was supported by the Russian Foundation for Basic Research under grant No. 93-01-00225 and by the Ministry of Scientific and Technological Research in the Mathematical Sciences of Italy.     

Modified realizability and predicate logic

Semantics of predicate formulas based on the notion of modified realizability for arithmetic formulas and interpretations of the language of arithmetic in all finite types are considered. For a number of natural constructive interpretations, the corresponding predicate logic of modified realizability is proved to be nonarithmetical. Translated fromMatematicheskie Zametki, Vol. 61, No. 2, pp. 259–269, February, 1997. This research was supported by the Russian Foundation for Basic Research under grant No. 95-01-00416 and by the International Science Foundation under grant No. NFQ000. Translated by V. N. Dubrovsky     

Use of the Lagrange method in nonlinear analysis

The problem of the spectrum of a nonlinear system and its relation to ellipsoid transform widths are studied.Translated fromMatematicheskie Zametki, Vol. 59, No. 3, pp. 334–342, March, 1996.This research was partially supported by the Russian Foundation for Basic Research under grant No. 93-01-00237 and by the International Science Foundation under grant No. MP1000.     

Solutions of the heat equation in domains with singularities

We study the asymptotics of solutions to the Dirichlet problem for the heat equation in time-dependent domains with singular points.Translated fromMatematicheskie Zametki, Vol. 64, No. 2, pp. 163–179, August, 1998.This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00504 and by INTAS under grant No. 93-351.