Search

In this paper, we prove inequalities for the mean square deviation δ N,n of the N step transition matrix from the equiprobable matrix for certain random affine walk in the residue ring modulo n with dependent linear and drift components. It is proved that the relation lim/n→∞ δN, n = 0 is true if and only if N/n2 → ∞ as n → ∞. Under this condition, δ2N, n ∼ εn exp{- π2 N/l2n}, as n → ∞, where εn = 2 if n is even and εn = 1 if n is odd, ln = n/2 if n is 0 even and ln = n if n is odd. This research was supported by the program of the President of Russian Federation for support of leading scientific schools, grant 2358.2003.9. [ABSTRACT FROM AUTHOR]

The paper is concerned with sets of Bernoulli distributions which are closed under substitutions of independent random variables into Boolean functions from a given set (an algebra of Bernoulli distributions). A description of all finite algebras of Bernoulli distributions is given. [ABSTRACT FROM AUTHOR]

In the paper, Malcev rings are defined. The class of Malcev rings strictly contains rings of Malcev–Neumann series, formal skew Laurent series rings, and formal pseudo-differential operator rings. In the paper, ring-theoretic properties of Malcev rings are studied. It turns out that rings of Malcev–Neumann series, formal skew Laurent series rings, and formal pseudo-differential operator rings have similar ring-theoretic properties related to the existence of the filtration with respect to the lowest degree of the series. [ABSTRACT FROM AUTHOR]

The Cayley graph generated by a set A is the graph ΓA(V) on a set of positive integers V such that a pair(u,v) ∈ V×V is an edge of the graph if and only if |u-v| ∈ A or u+v ∈ A. We denote by G2(n,m) the class of graphs G = (V, E) such that G is a union of chains and cycles and |V| = n, |E| = m. In this paper, we present an upper bound for the number of independent sets in Cayley graphs ΓA(V) such that A = {⌈n/2⌉ - t, ⌈n/2⌉ - ƒ}, V &subE; [⌊n/2⌋ + 1, ⌊n/2⌋+t] ∪ [n - t + 1, n], where n, t, ƒ ∈ N and ƒ < t < n/4. We also describe the graph with the maximum number of independent sets in the family g2(n, m). This research was supported by the Russian Foundation for Basic Researches, grant 04–01–00359. [ABSTRACT FROM AUTHOR]

The paper gives lower bounds for the minimum number m of weighings that are necessary for identification of up to t non-standard objects out of the total number of n objects being tested. For the problem with fixed deviation of weights of non-standard objects we construct a perfect algorithms with parameters n = 11, m = 5, t = 2 corresponding to the parameters of the ternary Virtakallio-Golay code. The nonexistence of a perfect weighing code with such parameters is proved. [ABSTRACT FROM AUTHOR]

In this paper, we continue our studies concerning consistent sequences of tests in discrete probabilistic statistical schemes. We introduce the concept of a ''prohibition'' in a discrete probabilistic scheme and give a series of examples where ''prohibitions'' arise. In statistical problems, tests exist whose critical sets are completely determined by means of ''prohibitions.'' We find necessary and sufficient conditions for existence of consistent sequences of tests in discrete schemes where all critical sets are defined by means of ''prohibitions.'' [ABSTRACT FROM AUTHOR]

A Boolean function g is said to be an annihilator of a Boolean function f if fg = 0. In some problems concerning finite automata, it is required to find non-zero annihilators of low algebraic degree for a function f. In this paper we suggest Algorithm M2 which, given the Zhegalkin polynomial for a function f, yields a basis of the space of its annihilators of degree not exceeding d. Algorithm M2 is an enhancement of a previously known algorithm and allows in a series of cases to decrease calculations. The total complexity of Algorithm M2 is the same as for the previous algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider algorithms to pack rectangles into a strip. As the main result we present an algorithm that packs rectangles online and for which the ratio of expected wasted area to expected occupied area tends to zero as the number of rectangles increases. The research was supported by the Russian Foundation for Basic Research, grants 05–01–00798 and 04–01–00359. [ABSTRACT FROM AUTHOR]

In this paper, we present some results on algebraic complexity theory, which is a relatively new region of complexity theory. We consider the complexity of multiplication (bilinear complexity) in group algebras. In the 6-dimensional group algebra C(S3)over the field of complex numbers with permutations of the third order as the basis, we find a bilinear algorithm for multiplication with multiplicative complexity equal to 9 (instead of trivial 36) and prove that this bound is unimprovable. We prove a series of assertions on the structure of the group algebra C(S3), in particular, we show that the algebra C(S3) is decomposed into a direct product of the algebra of 2 × 2 matrices and two one-dimensional algebras. This research was supported by the Russian Foundation for Basic Research, grant 03–01–00783. [ABSTRACT FROM AUTHOR]

In this paper, we present the list of minimal sets of systems of parastrophs for all 109 classes of isomorphic loops and 22 classes of isotopic quasigroups of order 6. [ABSTRACT FROM AUTHOR]

In this paper, we consider mappings of Cartesian powers Sn of an arbitrary partially ordered set S into itself which possess the main properties of closures. For each partially ordered set, we describe the asymptotic behaviour of the logarithm of the number of such mappings as n→ ∞. This research was supported by the Russian Foundation for Basic Research, grant 03–01–00783. [ABSTRACT FROM AUTHOR]

The distribution of jobs in a system with m identical parallel processors which minimises the load of the maximally loaded processor is an NP-hard problem. Many approximate algorithms are developed for this problem, but for the version of the problem where the jobs arrive ad must be treated on-line there is no algorithm possessing the guaranteed estimate which is less than 1 + 1 / ... for m ≥ 4 and tends to 1.837 as m → ∞. In this paper, we consider the version of the problem where jobs arrive one by one and must be treated on-line under the additional condition that the total duration of the jobs is known. For this version of the problem we suggest an algorithm with the guaranteed estimate equal to 5/3. [ABSTRACT FROM AUTHOR]

Presents a study which focused on Boolean lattices of multiply ω-foliated formations. Lemmas; Theorems.

The paper is devoted to the complexity of representation of q-valued functions by polarized polynomials and by matrix Kronecker forms of certain type. The complexity of a function is the minimal possible number of nonzero coefficients of a polynomial or a Kronecker form representing the function. It is known that for polynomial representation and representation by Kronecker forms of a certain type the maximal values of complexity in the class of all q-valued n-ary functions coincide. We establish the lower bound of these maximal values for five-valued functions. [ABSTRACT FROM AUTHOR]

In this paper, we consider a generalisation of quadratic residue codes to the cases of higher power residues. Such a generalisation enhances the information transmission rate with the use of such codes as compared with the quadratic-residue codes, at a sacrifice in the lower bound for the code distance, though. We consider the construction of generating polynomials for such codes, which allows to write explicitly their generating matrix. [ABSTRACT FROM AUTHOR]

In this paper, we prove inequalities for the mean square deviation δ N,n of the N step transition matrix from the equiprobable matrix for certain random affine walk in the residue ring modulo n with dependent linear and drift components. It is proved that the relation lim/n→∞ δN, n = 0 is true if and only if N/n2 → ∞ as n → ∞. Under this condition, δ2N, n ∼ εn exp{- π2 N/l2n}, as n → ∞, where εn = 2 if n is even and εn = 1 if n is odd, ln = n/2 if n is 0 even and ln = n if n is odd. This research was supported by the program of the President of Russian Federation for support of leading scientific schools, grant 2358.2003.9. [ABSTRACT FROM AUTHOR]

Presents a proof on the general expressibility problem of the G ö del-L ö b provability logic. Relation of expressibility between logic operations; Connection between modalities of provability and G ö delised provability; Information on diagonalizable algebras; Reduction of deducibility of words in an arbitrary system of post productions to expressibility of formulas in the provability logic.

We consider M ≥ 2 independent polynomial samples with N outcomes. For the case when M and N are fixed but sizes of samples tend to infinity we find limit distributions of a new statistic σ2: chi-square distribution with (M−1)(N−1) degrees of freedom if samples are statistically homogeneous, non-central chisquare distribution with the same number of degrees of freedom if samples are «convergent» to homogeneous ones, and normal distribution if samples are statistically nonhomogeneous. [ABSTRACT FROM AUTHOR]

We study a class of generalised linear discrete time systems whose coefficients are square constant matrices. The main objective of this research is to provide a link between the solutions of a class of singular linear discrete time systems and their proper (and transposed) dual systems. First, we study the prime system and by using the invariants of its matrix pencil we give necessary and sufficient conditions for existence and uniqueness of solutions, and obtain formulas for the solutions. Next, we prove that by using the same matrix pencil we can study the existence and uniqueness of solutions of the proper and transposed dual system. Moreover their solutions, when they exist, can be explicitly represented without resorting to further processes of computations for each one separately. Finally, we provide a numerical example to justify the theory. [ABSTRACT FROM AUTHOR]

A new estimate of the number of zeros ϱn = βn + iγn of the Riemann zeta-function with ordinates γn belonging to a given interval and for which the distance to the next zero is sufficiently large in comparison with the mean value 2 π(ln( γn/(2 π)))-1 is obtained. [ABSTRACT FROM AUTHOR]

Let c ≥ 2 and p ≥ c be two integers. We say that a proper colouring of the graph G is ( c, p)-nondegenerate, if for any vertex of G of degree at least p there are at least c vertices of different colours adjacent to it. In this research we prove the following result which generalises the Brooks theorem. Let D ≥ 3 and G be a graph without cliques on D + 1 vertices and a degree of any vertex in this graph be no greater than D. Then for any integer c ≥ 2 there is a proper ( c, p)-nondegenerate vertex D-colouring of G, where p = ( c3 + 8 c2 + 19 c + 6)( c – 1). [ABSTRACT FROM AUTHOR]

We consider a table with columns each of which contains each symbol of an alphabet A precisely once; the remaining elements of a column are equal to zero. It is required to transform the table preserving the sets of elements in each row and each column to the form with consecutively placed elements of alphabet A in each row. We give conditions for solvability of this problem. [ABSTRACT FROM AUTHOR]

It is shown that the diameter of the the ridge-graph, that is, the graph of the polytope C*( d, n) dual to the given polytope, where d is the dimension and n is the number of facets of the polytope, is equal to n – d – max{0, ⌈( n – 2 d)/(⌊ d/2⌋) + 1)⌉}. [ABSTRACT FROM AUTHOR]

We consider the groupoid of all possible matrices over an arbitrary Boolean algebra with partial operation of matrix product. On this groupoid, we define the equivalence classes analogous to the Green classes H, C, R, D, J for semigroups. We introduce the notion of the minor rank of a Boolean matrix. We show that the column, row, factorisation and minor ranks are invariants for the J -class of this groupoid, and the minor ranks do not exceed the column, row, factorisation and permanent ranks. The key result of this work explains the role of the Boolean determinant. We show that in some J -class there exists a square n × n matrix with nonzero determinant if and only if the column, row, factorisation and minor ranks of any matrix of this class are equal to each other and equal to n. All n × n matrices of this J -class have equal determinants, while the determinants of the square matrices of greater size are equal to zero. [ABSTRACT FROM AUTHOR]

We consider the relations between the level of affinity and other cryptographic parameters of Boolean functions such as nonlinearity, the order of correlation, and algebraic immunity. It is proved that the problem of finding the level of affinity for certain class of functions is an NP-hard problem. [ABSTRACT FROM AUTHOR]

We obtain estimates of complexity and depth of Boolean inverter circuits in normal and polynomial bases of finite fields. In particular, we show that it is possible to construct a Boolean inverter circuit in the normal basis of the field GF(2n) whose complexity is at most (λ(n - 1) + (1 + o(1))λ(n)/λ(λ(n)))M(n) and the depth is at most (λ(n - 1) + 2)D(n), where M(n), D(n) are the complexity and the depth, respectively, of the circuits for multiplication in this basis and λ(n) = ⌊log2 n⌋. [ABSTRACT FROM AUTHOR]

We study properties of two schemes of public distribution of a key suggested by V. M. Sidelnikov which are based on a noncommutative operation. As a noncommutative operation we consider the operations belonging to the family suggested by M. A. Cherepnev, namely, the operations in the rings of integers of cyclotomic fields based on the power residue symbol. [ABSTRACT FROM AUTHOR]

The algebraic method is widely used in analysis of filter generators of pseudo-random sequences. It is based on obtaining low-degree Boolean equations in bits of the initial states of the generator. The problem to obtain such equations reduces to finding low-degree annihilators for the filtering Boolean function. The presence of nonzero low-degree annihilators decreases the complexity of determining the initial state of the generator by means of its output. In this research we deal with the problem to find all low-degree annihilators for a Boolean function defined as a polynomial in several variables. We propose two new algorithms which solve this problem. Their complexities are bounded above by polynomials of the number of variables of the function and of the number of monomials in the polynomial which defines the function. We also consider the application of these algorithms to realising the algebraic method by three known scenarios which yield low-degree equations. [ABSTRACT FROM AUTHOR]

We introduce a class of cell circuits, T-circuits, and describe a connection between the lower bound for the area and the depth of the circuits of this class: the less the depth the greater the area of a circuit. We give examples of T-circuits with logarithmic depth in the problem of calculation of n prefix sums and also of sums and differences of two n-digit numbers. It is shown that the area of these circuits is O(n log n) and has the optimal order. [ABSTRACT FROM AUTHOR]

A functional graph is a digraph describing the action of a function on a set. The endomorphisms of such graphs are of interest in group theory: the centraliser of an element of the semigroup of all mappings of a set into itself coincides with the set of all endomorphisms of a digraph corresponding to this element. In this study, the functional graphs with a countable set of vertices are considered. We introduce the notion of lineals and calculate the cardinality of the set of endomorphisms of functional graphs which are not lineals. [ABSTRACT FROM AUTHOR]

Let on the set Sn,N of all different permutations of degree n with N cycles the uniform distribution be given. We obtain estimates of the rate of convergence of the distribution of the number of cycles of given length in a random permutation of Sn,N to the limit distributions as n, N → ∞ in such a way that either n/N ∞ 1 or n/N → ∞. [ABSTRACT FROM AUTHOR]

We consider a problem to pack rectangles into several semi-infinite strips of certain widths. We suggest two simply realised online algorithms, that is, algorithms which pack rectangles just at the moments of their arrivals. It is shown that the accuracy of the former algorithm cannot be approximated by any absolute constant. The latter algorithm guarantees a constant multiplicative accuracy, and the obtained estimate of the multiplicative accuracy is unimprovable. The research was supported by the Russian Foundation for Basic Research, grant 05–01–00798. [ABSTRACT FROM AUTHOR]

We describe the classes of all modules and all rings such that any system of linear equations over them is solvable if and only if it is concordant with linear relations. The research was supported by the program of the President of Russian Federation for support of leading scientific schools, grant 2358.2003.9. [ABSTRACT FROM AUTHOR]

Let Sn be the symmetric group of all permutations of degree n, A be some subset of the set of natural numbers N, and Tn = Tn(A) be the set of all permutations of Sn with cycle lengths belonging to A. The permutations of Tn are called A-permutations. We consider a wide class of the sets A with the asymptotic density σ > 0. In this article, the limit distributions are obtained for μm(n)/n as n → ∞ and m ∈ N is fixed. Here μm(n) is the length of the mth maximal cycle in a random permutation uniformly distributed on Tn. It is shown here that these limit distributions coincide with the limit distributions of the corresponding functionals of the random permutations in the Ewens model with parameter σ. This research was supported by the Russian Foundation for Basic Research, grant 05–01–00583, and by the Program of the President of the Russian Federation for support of leading scientific schools, grant 1758.2003.1. [ABSTRACT FROM AUTHOR]

We investigate the joint distribution of sums of elements in disjoint parts of a random permutation of a certain class. We find the generating function of the distribution of such sums and the limit distributions of the corresponding standardised random variables as the number of elements of the permutation tends to infinity. [ABSTRACT FROM AUTHOR]

We obtain upper and lower bounds for the probability that a given sequence X of finite length of symbols of a finite alphabet occurs inside a random equiprobable sequence Y of symbols of the same alphabet as a subsequence whose terms are separated in Y by at most one symbol. We give sequences X at which the bounds are attained. This research was supported by the Russian Foundation for Basic Research, grants 02–01–00266 and 05.01.00035, and by the Program of the President of the Russian Federation for support of leading scientific schools, grant 1758.2003.1. [ABSTRACT FROM AUTHOR]

We consider a method of steganalysis based on the use of a hidden Markov field model in the case of the LSB-modification of the initial discrete Markov field. We describe iterative filtering algorithms which yield estimates of some parameters of a hidden Markov field with prescribed accuracy. [ABSTRACT FROM AUTHOR]

On the base of equation calculus, we define the operator of equational closure. We give examples of equationally complete systems and equationally closed classes. We find the cardinality of the set of equationally precomplete classes and give criteria of equational completeness. We present all equationally closed classes of Boolean functions. This research was supported by the Russian Foundation for Basic Research, grant 03-01-00783. [ABSTRACT FROM AUTHOR]

In order to test homogeneity of r independent polynomial schemes with the same number of outcomes N under non-classical conditions where the numbers of trials nd, d = 1,...,r, in each of the schemes and the number of outcomes N tend to infinity, we suggest a statistic I (λ, r) which is a multidimensional analogue of the statistic I(λ) introduced by T. Read and N. Cressie. We obtain conditions of asymptotic normality of the distributions of the statistics I(λ) and I(λ,r) for an arbitrary tixed integer λ, λ ≠ 0, --1, as N → ∞, ndN-1 ∞, d = 1,...,r. The expressions for the centring and normalising parameters are given in the explicit form for the hypothesis H0 under which the distributions in these r schemes coincide, and for some class of alternatives close to H0. [ABSTRACT FROM AUTHOR]

We suggest an algorithm to solve a two-dimensional interval search problem which is characterised by the memory consumed of order k, the average search time (without the lime needed to output the answer) of order √k. where k is the database size. This research was supported by the Russian Foundation for Basic Research, grant 01-01-00748. [ABSTRACT FROM AUTHOR]

We introduce the notion of a homomorphic relation of algebras with a scheme of operators. Homomorphisms and π-homomorphisms are special cases of this notion. Some new relations of algebras with a scheme of operators are studied. [ABSTRACT FROM AUTHOR]

We consider the equation (x1 + … + xn)m = ax1 … xn where a is a nonzero element of the finite field Fq, n ≥ 2, and m is a positive integer. Explicit formulas for the number of solutions of this equation in Fnq under the condition d ∈ {1, 2, 3, 6}, where d = gcd(m – n, q – 1), are found. Moreover, we obtain formulas for the number of solutions for arbitrary d > 2 if there exists positive integer l such that d | (pl + 1), where p is the characteristic of Fq . [ABSTRACT FROM AUTHOR]

We study the question on average and typical values of sums of pairwise Hamming distances for subsets of vertices of the n-dimensional unit cube. We suggest an approach to the problem of evaluation of average and typical values of arbitrary functionals defined on subsets of a finite set as the sum of values assigned to ordered pairs of elements of this set; general formulas for this case are obtained. We find average and typical values of sums of pairwise distances in the case of all subsets of vertices of the n-dimensional unit cube and of sums of pairwise distances for subsets of vertices of fixed cardinality. This research was supported by the Russian Foundation for Basic Research, grant 01–01–00266. [ABSTRACT FROM AUTHOR]

We consider a sequence of independent trials, under the hypothesis H0 each of them is a realisation of a certain polynomial scheme. We introduce a family of multivariate χ2-statistics where the outcomes are equipped with weights depending on the ordinal of the trial. Earlier results on families of multivariate χ2-statistic are extended to this family. This research was supported by grant 1758.2003.1 of President of Russian Federation for support of leading scientific schools. [ABSTRACT FROM AUTHOR]

For sums of independent identically distributed non-negative random variables we give a series of limit theorems which may be of use in probabilistic combinations in the framework of the generalised allocation schem. This research was supported by the grant 1758.2003.1 of State support of leading scientific schools of Russian Federatin. [ABSTRACT FROM AUTHOR]

We give conditions for emergence of a giant cycle in a random permutation with a given number of cycles and obtain limit distributions of the maximum cycle lengths in all domains of variation of the parameters. [ABSTRACT FROM AUTHOR]

We give a complete description of the limit behaviour of the number of cycles of length r in a random permutation of degree n with N cycles in all domains of variations of the parameters n, N, r, thus essentially extending the know results concerning the limit behaviour of the number of such cycles. This research was supported by the grant 1758.2003.1 of support of leading scientific schools of Russian Federation. [ABSTRACT FROM AUTHOR]

We obtain explicit formulas for the coefficients of asymptotic expansions in the domain of large deviations for the distributions of the number of cycles v[subn] in a random permutation of degree n, that is, for the probability P(v[subn] = N) under the condition that n, N → ∞ in such a way that 1 < α[sub0] ≤ α = n/N ≤ α[sub1] < ∞, where α[sub0], α[sub1] are constants. The formulas express the coefficients in terms of cumulants of the random variable which has the distribution of the logarithmic series with specialy chosen parameter. For the cumulants of the third and fourth orders we give the corresponding values. We discuss the accuracy of the obtained approximation. If n, N → ∞ so that 0 < γ[sub0] ≤ γ = N/ In n ≤ γ[sub1] ≤ ∞ where γ[sub0], γ[sub1] are constants, we give asymptotic estimates of the probabilities, P(v[subn] = N), P(v[subn] ≤ N), P(v[subn] ≥ N) with the remainder terms of order O((In n)[sup-2]) uniform in γ ∈ [γ[sub0], γ[sub1]]. The corresponding estimate for the probability P(v[subn] = N) refines the previously known results for the case N = β In n + o (In n), where β is a positive constant. [ABSTRACT FROM AUTHOR]

We define the operator of Boolean reducibility on the set of all infinite binary sequences. This operator is a variant of the operator of finite-automaton transformability when automata with several inputs and one state are considered. Each set Q of Boolean functions containing a selector function and closed with respect to the operation of superposition of a special form defines the Q-reducibility and Q-degrees, that is, the sets of Q-equivalent sequences. We study properties of the partially ordered set LQ of all Q-degrees, namely, the existence of maximal, minimal and the greatest elements, infinite chains and antichains, and upper bounds. The research was supported by the Russian Foundation for Basic Research, grant 03-01-00783.. [ABSTRACT FROM AUTHOR]

In each finite simple sporadic group, excepting the Baby Monster group B, the Monster group M, the McLaughlin group McL and Mathieu groups M[sub11], M[sub22], M[sub23], three generating involutions, two of which commute, are found. If G is one of the groups M[sub12], M[sub24], HS, J[sub1], J[sub2], J[sub3], then we give pairs of numbers p, q, p ≤ q, such that p = |ik|, q = |jk| for some involutions i, j, k with condition |ij| = 2 generating the group G. The triples of involutions mentioned above are found with the use of the system of computer algebra GAP. Recall that any two involutions of the triple of involutions generating either McL, ore M[sub11], or M[sub22], or M[sub23] do not commute. This research was supported by the Russian Foundation for Basic Research, grant 02-01-00078. [ABSTRACT FROM AUTHOR]