Search

The paper is devoted to circuits implementing parity functions. A review of results establishing exact values of the complexity of parity functions is given. The structure of optimal circuits implementing parity functions is described for some bases. For one infinite basis, an upper bound for the complexity of parity functions is given.

The paper presents a technique for the automatic calculation of Belyi functions for trees with weighted edges. Bibliography: 20 titles.

The main purpose of this paper is to give a complete description of isometry groups on the 4-dimensional simply connected nilpotent Lie groups. We distinguish between two geometrically distinct cases of degenerate and nondegenerate center of the group. Since Walker metrics appear as the underlying structure of neutral signature metrics on the nilpotent Lie groups with degenerate center, we find necessary and sufficient condition for them to locally admit the nilpotent group of isometries.

The classical Hurwitz theorem claims that there are exactly four normed algebras with division: the real numbers (ℝ), complex numbers (ℂ), quaternions (ℍ), and octonions (𝕆). The length of ℝ as an algebra over itself is zero; the length of ℂ as an ℝ-algebra equals one. The purpose of the present paper is to prove that the lengths of the ℝ-algebras of quaternions and octonions equal two and three, respectively.

In this paper, the functorial property of the inverse image for transitive Lie algebroids is proved and also there is proved the functorial property for all objects that are necessary for building transitive Lie algebroids due to K. Mackenzie—bundles L of finite-dimensional Lie algebras, covariant connections of derivations ▽, associated differential 2-dimensional forms Ω with values in the bundle L, couplings, and the Mackenzie obstructions. On the base of the functorial properties, a final object for the structure of transitive Lie prealgebroid and for the universal cohomology class inducing the Mackenzie obstruction can be constructed.

A homomorphic encryption allows specific types of computations on ciphertext and generates an encrypted result that matches the result of operations performed on the plaintext. Some classic cryptosystems, e.g., RSA and ElGamal, allow homomorphic computation of only one operation. In 2009, C. Gentry suggested a model of a fully homomorphic algebraic system, i.e., a cryptosystem that supports both addition and multiplication operations. This cryptosystem is based on lattices. Later M. Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan suggested a fully homomorphic system based on integers. In a 2010 paper of A. V. Gribov, P. A. Zolotykh, and A. V. Mikhalev, a cryptosystem based on a quasigroup ring was constructed, developing an approach of S. K. Rososhek, and a homomorphic property of this system was investigated. An example of a quasigroup for which this system is homomorphic is given. Also a homomorphic property of the ElGamal cryptosystem based on a medial quasigroup is shown.

The paper is devoted to the popularization of one of the topics at the border between analysis and number theory that is related to polynomial with integer coefficients.

The paper presents an explicit formula for the Hilbert pairing between the Milnor K-group of a higher-dimensional local field and a polynomial formal module. This formula generalizes similar results for the one-dimensional case and the higher-dimensional case of multiplicative group. The case where the field and its first residue field have different characteristics, is considered. Bibliography: 13 titles.

In this paper, we prove the paragraded version of the Wedderburn–Artin theorem. Following the methods known from the abstract case, we first prove the density theorem and observe the matrix rings whose entries are from a paragraded ring. However, in order to arrive at the desired structure theorem, we introduce the notion of a Jacobson radical of a paragraded ring and prove some properties which are analogous to the abstract case. In the process, we study the faithful and irreducible paragraded modules over noncommutative paragraded rings and prove the paragraded version of the well-known Schur lemma.

Let S + and S + ′ be the Schwartz spaces of rapidly decreasing functions and tempered distributions on ℝ+ , respectively. Let P(S + ′ ) be the space of continuous polynomials over S + ′ and let P ′ (S + ′ ) be its strong dual. These spaces have representations in the form of Fock type spaces $$ \varGamma \left({S}_{+}\right):=\underset{n\in {\mathbb{Z}}_{+}}{\oplus}\left({\oplus}_{s,\mathrm{p}}^n{S}_{+}\right)\kern2em \mathrm{and}\kern2em \varGamma \left({S}_{+}^{\prime}\right):=\underset{n\in {\mathbb{Z}}_{+}}{\times}\left({\oplus}_{s,\mathrm{p}}^n{S}_{+}^{\prime}\right), $$ respectively. In the present paper, the Gâteaux differentiability of elements of the spaces P(S + ′ ), P ′ (S + ′ ), Γ(S +), and Γ(S + ′ ) is investigated. The relationship between the Gâteaux derivative, the operators of creation and annihilation in the Fock type spaces, and the differentiations on Γ(S +) and Γ(S + ′ ) is established.

Let K be a multidimensional local field with characteristic different from the characteristic of its residue field, c be a unit of K, and Fc(X, Y) = X +Y +cXY be a polynomial formal group, which defines the formal module Fc( $$ \mathfrak{M} $$ ) over the maximal ideal of the ring of integers in K. Assume that K contains the group of roots of the isogeny [p m]c(X), which we denote by μ Fc, m . Let be the multiplicative group of Cartier curves and c be the formal analog of the module Fc( $$ \mathfrak{M} $$ ). In the present paper, the formal symbol { ·, · }c : K n ( )× c → μ Fc, m is constructed and its basic properties are checked. This is the first step in the construction of an explicit formula for the Hilbert symbol.

The paper presents a full description of idempotent elements of the semigroup of binary relations BX(D), which are defined by semilattices of the class Σ3(X, 8). For the case where X is a finite set and Z7 = O, we derive formulas for calculating the number of idempotent elements of the respective semigroup.

In this paper, we introduce a novel polynomial-time algorithm to compute graph invariants based on the idea of a modified random walk on graphs. Though not proved to be a full graph invariant yet, our method gives the right answer for the graph instances other well-known methods could not compute (such as special Furer gadgets and point-line incidence graphs of finite projective planes of higher degrees).

The minimality theorem states, in particular, that on cohomology H(A) of a dg algebra there exists sequence of operations mi : H(A)⊗i → H(A), i = 2, 3, . . . , which form a minimal A ∞ -algebra (H(A), {m i }). This structure defines on the bar construction BH(A) a correct differential dm so that the bar constructions (BH(A), d m ) and BA have isomorphic homology modules. It is known that if A is equipped additionally with a structure of homotopy Gerstenhaber algebra, then on BA there is a multiplication which turns it into a dg bialgebra. In this paper, we construct algebraic operations Ep,q : H(A) ⊗p ⊗H(A) ⊗q → H(A), p, q = 0, 1, 2, . . ., which turn (H(A), {m i }, {E p,q }) into a B ∞ -algebra. These operations determine on BH(A) correct multiplication, so that (BH(A), d m ) and BA have isomorphic homology algebras.

Connections between certain types of categories (logoses and toposes) and intuitionistic predicate logic was established in 1960–1970 by Lowvere. The possibility of extending this connection to some types of modal logics by using the internal structure of categories of particular type (logos) was also established. Category-theoretical constructs were hence used as one of the possible semantic interpretations of intuitionistic logic. This interpretation has also included intuionistic modal logics using different semantical tools such as adjoint pair of functors. In this paper, we discuss one of the possible extension of intuitionistic logic.

In this paper we give a full description of regular elements of the semigroup that are defined by semilattices of the class, when Z7 ∩ Z6 ≠ ∅. Formulas are derived by means of which the number of regular elements of the semigroup is calculated when it is a finite set.

The classes of right and left γ-generating matrices were introduced by D. Z. Arov in the 1980s. These matrices play an important role in the description of solutions of the indeterminate Nehari problem. In the present paper, the classes of the so-called generalized right and left γ-generating matrices, being resolvent matrices of the Nehari–Takagi problem, are introduced. For matrices of these classes, some factorization theorems are proved, and the connection between the class of generalized γ-generating matrices and the class of generalized j pq -inner matrix valued functions is found. Subclasses of singular, regular, and strongly regular generalized -generating matrices are introduced and studied.

The paper is devoted to the development of the theory of lower Q-homeomorphisms relative to a p-modulus in ℝ n , n ≥ 2. For these classes of mappings, a number of theorems on the local behavior are established, and, in particular, an analog of the famous Gehring theorem on a local Lipschitz property is proved, various theorems on estimates of distortion of the Euclidean distance are given, an estimate of the ball image measure is established, and, as a consequence, an analog of the Ikoma–Schwartz lemma is proved.

It this paper, we examine the sums of double sine series with coefficients that are multiply monotonic with respect to subsequences. We obtain sufficient conditions under which these sums belong to the classes Lp, 0 < p < ∞.

Let A and B be square nonsingular n-by-n matrices with entries being rational or rational Gaussian numbers. The paper describes a method for verifying whether these matrices are congruent. The method uses a finite number of arithmetic (and, in the complex case, also conjugation) operations.

The paper continues the investigation of the lengths of quasi-commuting matrix pairs; specifically, it considers the problem of realizability of different positive integers as values of the length function for quasi-commuting matrix pairs.

The paper provides a short overview of a series of articles devoted to C*-algebras generated by a self-mapping on a countable set. Such an algebra can be seen as a representation of the universal C*-algebra generated by a family of partial isometries satisfying a set of conditions. These conditions are determined by the initial mapping.

The paper generalizes results by E. Janvresse, T. de la Rue, and Y. Velenik and results by the second author on the fluctuations in the ergodic sums for the Pascal adic transformation in the case of an arbitrary ergodic invariant measure and arbitrary cylinder function.

In this paper, we give new upper bounds for the chromatic numbers for integer lattices and some rational spaces and other lattices. In particular, we have proved that for any concrete integer number d, the chromatic number of ℤn with critical distance \( \sqrt{2d} \) has a polynomial growth in n with exponent less than or equal to d (sometimes this estimate is sharp). The same statement is true not only in the Euclidean norm, but also in any lp norm. Moreover, we have given concrete estimates for some small dimensions as well as upper bounds for the chromatic number of ℚpn, where by ℚp we mean the ring of all rational numbers having denominators not divisible by some prime numbers.

Many invariants of knots rely upon smoothing the knot at its crossings. To compute them, it is necessary to know how to count the number of connected components the knot diagram is broken into after the smoothing. In this paper, it is shown how to use a modification of a theorem of Zulli together with a modification of the spectral theory of graphs to approach such problems systematically. We give an application to counting subdiagrams of pretzel knots which have one component after oriented and unoriented smoothings.

The aim of the paper is to study a service system model introduced by I. Kaj and M. Taqqu. A limit theorem for the process of integral workload on the service system is proved. This theorem generalizes the corresponding result of I. Kaj and M. Taqqu, because the weak convergence in the Skorokhod space is established.

The paper presents estimates of small deviation probabilities of the sum $$ {\displaystyle \sum_{j\ge 1}{\leftthreetimes}_j{X}_j} $$ , where {⋋j} are positive numbers and {Xj} are i.i.d. positive random variables satisfying weak restrictions at zero and infinity. Bibliography: 16 titles.

In this paper, we study mod-retractable modules, CSL-modules, fully Kasch modules, and their interrelations. Right fully Kasch rings are described. It is proved that for a module M of finite length, the following conditions are equivalent. (1) In the category σ(M), every module is retractable. (2) In the category σ(M), every module is coretractable. (3) M is a CSL-module. (4) Ext 1 (S 1 , S 2) = 0 for any two simple nonisomorphic modules S 1 , S 2 ∈ σ(M). (5) M is a fully Kasch module.

This paper is devoted to the structure that describes the construction of finite distributive lattices. From the viewpoint of application, we consider algorithms of construction and enumeration of distributive lattices and partially ordered sets for finite distributive lattices: A formula for finding the maximum anti-chain with respect to nonintersection is given, it is shown that elements of the lattice can be split into pairs according to comparison, the point of the maximum number of elements in the lattices is considered, and the structure of lattice congruence is described.

Let L be the Laplace matrix of a weighted digraph. The aim of the paper is to establish a simple way for computing any coefficient of the characteristic polynomial of L as a constant sign sum over the incoming spanning forests. The idea is to express L as the product of generalized (weighted) incidence matrices. It turns out that the minors of them can be studied in terms of the tree-like structure of the digraph. This makes it possible to compute the minors of L.

In this paper, we consider the multiplicative groupoid of matrices with elements in a lattice with 0 and 1. Examples of such groupoids are the semigroup of binary relations and semigroups of minimax (fuzzy) relations. It is shown that every automorphism of a groupoid is the composition of an inner automorphism and the automorphism defined by an automorphism of the lattice. Despite the fact that, in general, the groupoid is not associative, it satisfies the UA-property: Every multiplicative automorphism is an additive automorphism. Earlier, the realization of the UA-property has been considered mainly for associative rings and semirings. We describe the invertible matrices that define inner automorphisms.

In the present paper, a necessary and sufficient condition for an element of the semigroup BX (D) defined by semilattices of the class Σ1(X, 5) to be regular is given. Moreover, formulas for calculation of regular elements are derived.

In 2007, A. L. Smirnov formulated an interesting conjecture on the generalized rings introduced and studied by N. V. Durov. In this paper, the conjecture is proved.

Here and in what follows, we write "a b" instead of "a ≤ Cb for some uniform constant C" for brevity; we also write ab when a b and b a .T he symbol∂j, j =1 , 2, denotes the differentiation with respect to jth variable. To be more precise, we study estimates of the scalar product of two functions in some Hilbert space (in this paper, some Sobolev space of fractional order) in terms of the product of L1- norms of some differential polynomials applied to these functions. For the author, the interest in inequalities of such type originated from the work on nonisomorphism problems for Banach spaces of smooth functions and embedding theorems used there, see the short report (5) and preprint (6). We are going to use some formalism to make our statements shorter. Let k and l be natural numbers, let α and β be real nonnegative numbers, and let σ and τ be complex nonzero numbers. The symbol BE(k, l, α, β, σ, τ) means the statement that the inequality �

The paper is devoted to the general problem of obtaining interpolation theorems for operators that are bounded on cones in normed spaces and to some specific results pertaining to the particular problem of interpolation of operators that are bounded on cones in weighted spaces of numerical sequences. This setting is a natural generalization of the classical problem of interpolation of the boundedness property for a linear operator that is bounded between two Banach couples. We introduce the general concept of a Banach triple of cones possessing the interpolation property with respect to a given Banach triple. We provide sufficient conditions under which a triple of cones (Q0,Q1,Q) in weighted spaces of numerical sequences possesses the interpolation property with respect to a given Banach triple of weighted spaces of numerical sequences (F0, F1, F). Appropriate interpolation theorems generalize the classical result about interpolation of linear operators in weighted spaces and are of interest for the theory of bases in Frechet spaces. Bibliography: 10 titles.

In this paper, we consider the functions on algebraic curves whose divisors have the form nA−nC. Combinatorial-topological and algebraic descriptions are introduced for exploring such functions. All Belyi functions with such divisors are described. The case of curves of genus 1 is considered in more detail. The number of Belyi functions with divisor nA − nC is explicitly calculated. For general functions of this type on a curve of genus 1, we consider the space of the parameters and a method of its calculation that uses the Pade approximation.

For every real number γ ≥ 1 we denote by K↓(γ) the least possible value of the constant term of an even nonnegative trigonometric polynomial with monotone coefficients such that all its coefficients, save for the constant term, are not lesser than 1 and the sum of these coefficients equals γ. In this paper, the asymptotic estimate of K↓(γ) is found and some extremal problems on the minimum of the constant term of an even nonnegative trigonometric polynomial are studied.

The paper is concerned with some characteristics of approximation by piecewise polynomial functions with nonfixed knots in various integral metrics Lp(a,b), 0

This paper proposes an inversion algorithm for pairings. This technique can be used for breaking the Diffie–Hellman protocol on elliptic curves and for solving the discrete logarithm problem on some curves that satisfy GOST P.34.10-2012.

In this paper, we prove the decidability of the ultimate periodicity problem (the HD0L periodicity problem).

Reed–Muller codes are one of the most well-studied families of codes; however, there are still open problems regarding their structure. Recently, a new ring-theoretic approach has emerged that provides a rather intuitive construction of these codes. This approach is centered around the notion of basic Reed–Muller codes. We recall that Reed–Muller codes over a prime field are radical powers of a corresponding group algebra. In this paper, we prove that basic Reed–Muller codes in the case of a nonprime field of arbitrary characteristic are distinct from radical powers. This implies the same result for regular codes. Also we show how to describe the inclusion graph of basic Reed–Muller codes and radical powers via simple arithmetic equations.

Let R be a partially ordered commutative ring without zero divisors, Gn(R) be the subsemigroup of GLn(R) consisting of matrices with nonnegative elements, and GEn+(R) be its subsemigroup generated by elementary transformation matrices, diagonal matrices, and permutation matrices. In this paper, we describe in which cases endomorphisms of GE2+(R) can be extended to endomorphisms of GE2+(R[x]).

Let \( \mathbb{F} \) be a linearly ordered field. Consider Gn(\( \mathbb{F} \)), which is the subsemigroup of GLn(\( \mathbb{F} \)) consisting of all matrices with nonnegative coefficients. In 1940, A. I. Maltsev introduced the concept of the group of fractions for a semigroup. In the given paper, we prove that the group of fractions of G3(\( \mathbb{F} \)) coincides with GL3(\( \mathbb{F} \)).

This paper deals with extremal problems concerning colorings of partial Steiner systems. We establish a new sufficient condition for r-colorability of a hypergraph from some class of such systems in terms of maximum vertex degree. Moreover, as a corollary we obtain a new lower bound for the threshold probability for r-colorability of a random hypergraph in a binomial model.

In this paper we study a problem of preserving probabilistic and statistical properties of random walks under sample space mapping, in particular, under mapping of random walk sample space into space of sufficient statistics of that random walk. We consider problems of closedness and completeness of random walks plans, formulate necessary condition of mapped plans completeness, consider problems of constructing unbiased estimate for function of unknown parameter, and find unbiased estimate for probability density of getting into reachable area.

The paper deals with the Markov property for the occupation time process for a homogeneous Markov chain with continuous time and countable state space. The well-known result that the Markov property is valid for a random walk on a tree is generalized to the case of a random walk on an arbitrary graph. Bibliography: 7 titles.

Let the vertices of a circle graph be divided into several groups. This paper contains lower bounds on the size of an independent set that can be contained in one group of this subdivision. Bibliography: 7 titles.

In this paper, we investigate the inverse problem to the minimal branching geodesic searching problem in a normed space. Let us consider a normed space. Then the form of the minimal branching geodesic is determined. We must find all possible normed spaces with the same form of the minimal branching geodesics as the one in the considered normed space. The case of Euclidean norms is analyzed in detail.

In this paper, we consider so-called double covering polytopes. In 1995, Matsui showed that the problem of checking nonadjacency on these polytopes is NP-complete. We show that double covering polytopes are faces of the following polytopes: knapsack polytopes, set covering polytopes, cubic subgraph polytopes, 3-SAT polytopes, partial order polytopes, traveling salesman polytopes, and some others.

In this paper we describe all indecomposable two-term partial tilting complexes over a Brauer tree algebra with multiplicity 1 using a criterion for a minimal projective presentation of a module to be a partial tilting complex. As an application we describe all two-term tilting complexes over Brauer star algebra and compute their endomorphism rings., 16 pages