Multiplicative factorizations of integral representations by quadratic forms

Multiplicative dependence of integral representations of integers by positive definite quadratic forms in an odd number of variables on square factors of the represented numbers is studied. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 212, 1994, pp. 15–55. Translated by A. S. Goloubeva.     

Minimal numerations of positively computable families

It is proved that among computable numerations that are limit-equivalent to some positive numeration of a computable family of recursively enumerable sets, either there exists one least numeration, or there are countably many nonequivalent, minimal numerations. In particular, semilattices of computable numerations for computable families of finite sets and of weakly effectively discrete families of recursively enumerable sets either have a least element or possess countably many minimal elements.Translated fromAlgebra i Logika, Vol. 33, No. 3, pp. 233–254, May–June, 1994.     

On superpositions of continuous functions defined on the baire space

For continuous functions specified on the Baire space, conditions for the representability of a function of several variables as a superposition of functions of a smaller number of variables are considered. With the use of linear functions of the form (1+α)t, a boundary value of the modulus of continuity separating the positive from the negative solution of the problem is found. For the case in which the problem has a negative solution, a constructive method for obtaining (n+1)-variable continuous functions with modulus of continuity ϕ(t) that are not representable as superposition ofn-variable continuous functions with the same modulus of continuity ϕ(t) is suggested. Translated fromMatermaticheskie Zametki, Vol. 66, No. 5, pp. 696–705, November, 1999.     

Limit theorems for Markov random walks with a fixed number of certain transitions

The limit behavior of Markov chains with discrete time and a finite number of states (MCDT) depending on the number n of its steps has been almost completely investigated [1–4]. In [5], MCDT with forbidden transitions were investigated, and in [6], the sum of a random number of functionals of random variables related by a homogeneous Markov chain (HMC) was considered. In the present paper, we continue the investigation of the limit behavior of the MCDT with random stopping time which is determined by a Markov walk plan II with a fixed number of certain transitions [7, 8]. Here we apply a method similar to that of [6], which allows us to obtain, together with some generalizations of the results of [6], a number of new assertions. Translated fromStatisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 119–130, Perm, 1990.     

Uniqueness theorems for rational,algebraic, and algebroid functions

A number of pointsA, for which one must define the sets of simpleA-points to determine a rational function, a polynomial, and an algebraic or algebroid function uniquely, is obtained.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 3, pp. 212–226, March, 1994.     

On the Real Zeros of Positive Semidefinite Biquadratic Forms

For a positive semidefinite biquadratic forms F in (3, 3) variables, we prove that, if F has a finite number but at least 7 real zeros 𝒵(F), then it is not a sum of squares. We show also that if F has at least 11 zeros, then it has infinitely many real zeros and it is a sum of squares. It can be seen as the counterpart for biquadratic forms as the results of Choi, Lam, and Reznick for positive semidefinite ternary sextics.

We introduce and compute some of the numbers BB _{n, m} which are set to be equal to sup |𝒵(F)| where F ranges over all the positive semidefinite biquadratic forms F in (n, m) variables such that |𝒵(F)| < ∞.

We also recall some old constructions of positive semidefinite biquadratic forms which are not sums of squares and we give some new families of examples.     

On the equivalency of piecewise-constant control with a known number of switchings and arbitrary amplitude bounded control in a terminal problem for a linear nonstationary system

It is shown that any amplitude-bounded control of a linear terminal nonstationary system with two control coordinates can be replaced by a piecewise-constant (relaying) control with a known number of switchings, and moreover, the procedure of determining the moments of switching is reduced to a known finite number of problems of nonlinear programming in a space of two variables, which are given in the paper.Translated from Dinamicheskie Sistemy, No. 7, pp. 78–84, 1988.     

The number of cells of a dynamical system

In a dynamical system with a finite number of elementary stationary points, in which just these points serve as the limiting sets of its trajectories, a component of the connection of the set of trajectory points with the common positive and common negative limiting set is called a cell. An example is constructed which shows that a dynamical system can have any finite number of cells even though the number of stationary points is fixed.Translated from Matematicheskie Zametki, Vol. 3, No. 6, pp. 707–714, June, 1968.     

Equilibrium states with incomplete supports and periodic trajectories

The relationship between analytic properties of the Artin-Mazur-Ruelle zeta function and the structure of the state of equilibrium states for a topological Markov chain is studied for a class of functions constant on a system of cylinder sets. The convergence of discrete invariant measures to equilibrium states is studied. Special attention is paid to the case in which the uniqueness condition is violated. Dynamic Ruelle-Smale zeta functions are considered, as well as the distribution laws for the number of periodic trajectories of special flows corresponding to topological Markov chains and to positive functions of this class.Translated fromMatematicheskie Zametki, Vol. 59, No. 2, pp. 230–253, February, 1996.The author is grateful to B. M. Gurevich for discussing the paper.This work was partially supported by the International Science Foundation under grant No. M8X000.     

Finite problems and the logic of the weak law of excluded middle

A new characteristic of propositional formulas as operations on finite problems, the cardinality of a sufficient solution set, is defined. It is proved that if a formula is deducible in the logic of the weak law of excluded middle, then the cardinality of a sufficient solution set is bounded by a constant depending only on the number of variables; otherwise, the accessible cardinality of a sufficient solution set is close to (greater than the nth root of) its trivial upper bound. This statement is an analog of the authors result about the algorithmic complexity of sets obtained as values of propositional formulas, which was published previously. Also, we introduce the notion of Kolmogorov complexity of finite problems and obtain similar results.Translated from Matematicheskie Zametki, vol. 77, no. 2, 2005, pp. 291–302.Original Russian Text Copyright © 2005 by A. V. Chernov.This revised version was published online in April 2005 with a corrected issue number.     

A relationship between the maximum modulus and Taylor coefficients of entire functions of several complex variables

We present results on the relationship between the growth of the maximum modulus and the decay of Taylor coefficients of entire functions of several variables. The results are obtained by two different methods, the first of which had been proposed earlier by Oskolkov for the one-dimensional case, and the second is based on the use of the Legendre-Jung-Fenchel conjugates of the weight functions. Attention is mainly paid to the characterization of the growth of entire functions with respect to the conjunction of variables; however, some results are obtained for the case in which there is different growth with respect to different variables. Translated fromMatematicheskie Zametki, Vol. 62, No. 2, pp. 238–258, August, 1997. Translated by N. K. Kulman     

The effect of structural branching on the efficiency of clause learning SAT solving: An experimental study

The techniques for making decisions (branching) play a central role in complete methods for solving structured instances of propositional satisfiability (SAT). Experimental case studies in specific problem domains have shown that in some cases SAT solvers can determine satisfiability faster if branching in the solver is restricted to a subset of the variables at hand. The underlying idea in these approaches is to prune the search space substantially by restricting branching to strong backdoor sets of variables which guarantee completeness of the search. In this paper we present an extensive experimental evaluation of the effects of structure-based branching restrictions on the efficiency of solving structural SAT instances. Previous work is extended in a number of ways. We study state-of-the-art solver techniques, including clause learning and related heuristics. We provide a thorough analysis of the effect of branching restrictions on the inner workings of the solver, going deeper than merely measuring the solution time. Extending previous studies which have focused on input-restricted branching, we also consider relaxed branching restrictions that are based on underlying structural properties of the variables.     

On plane trees with a prescribed number of valency set realizations

We describe valency sets of plane bicolored trees with a prescribed number of realizations by plane trees. Three special types of plane trees are defined: chains, trees of diameter 4, and special trees of diameter 6. We prove that there is a finite number of valency sets that have R realizations as plane trees and do not belong to these special types. The number of edges of such trees is less than or equal to 12R  + 2. The complete lists of valency sets of plane bicolored trees with 1, 2, or 3 realizations are presented. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 6, pp. 9–17, 2007.     

Towards the global solution of the maximal correlation problem

The maximal correlation problem (MCP) aiming at optimizing correlation between sets of variables plays a very important role in many areas of statistical applications. Currently, algorithms for the general MCP stop at solutions of the multivariate eigenvalue problem for a related matrix A, which serves as a necessary condition for the global solutions of the MCP. However, the reliability of the statistical prediction in applications relies greatly on the global maximizer of the MCP, and would be significantly impacted if the solution found is a local maximizer. Towards the global solution of the MCP, we have obtained four results in the present paper. First, the sufficient and necessary condition for global optimality of the MCP when A is a positive matrix is extended to the nonnegative case. Secondly, the uniqueness of the multivariate eigenvalues in the global maxima of the MCP is proved either when there are only two sets of variables involved, or when A is nonnegative. The uniqueness of the global maximizer of the MCP for the nonnegative irreducible case is also proved. These theoretical achievements lead to our third result that if A is a nonnegative irreducible matrix, both the Horst-Jacobi algorithm and the Gauss-Seidel algorithm converge globally to the global maximizer of the MCP. Lastly, some new estimates of the multivariate eigenvalues related to the global maxima are obtained.     

A generalization of the symmetric classical polynomials: Hermite and Gegenbauer polynomials

In this paper, we give new families of polynomials orthogonal with respect to a d-dimensional vector of linear functionals, d being a positive integer number, and generalizing the standard symmetric classical polynomials: Hermite and Gegenbauer. We state the inversion formula which is used to express the corresponding moments by means of integral representations involving the Meijer G-function. Moreover, we determine some characteristic properties for these polynomials: generating functions, explicit representations and component sets.     

Approximation Schemes for Functional Optimization Problems

Approximation schemes for functional optimization problems with admissible solutions dependent on a large number d of variables are investigated. Suboptimal solutions are considered, expressed as linear combinations of n-tuples from a basis set of simple computational units with adjustable parameters. Different choices of basis sets are compared, which allow one to obtain suboptimal solutions using a number n of basis functions that does not grow “fast” with the number d of variables in the admissible decision functions for a fixed desired accuracy. In these cases, one mitigates the “curse of dimensionality,” which often makes unfeasible traditional linear approximation techniques for functional optimization problems, when admissible solutions depend on a large number d of variables. Marcello Sanguineti was partially supported by a PRIN grant from the Italian Ministry for University and Research (project “Models and Algorithms for Robust Network Optimization”).     

Application of Eichler's reduction formula to the representation of numbers by certain quaternary quadratic forms

It is shown how Eichler's formula can be used to obtain exact formulas for the number of representations of positive integers by certain positive-definite quadratic forms of principal type in four variables, in terms of traces of Frobenius endomorphisms of appropriate elliptic curves over fields of finite characteristic; as examples, some new exact formulas are derived.Translated from Matematicheskie Zametki, Vol. 9, No. 1, pp. 71–76, January, 1971.     

Ideals of porous sets in the real line and in metrizable topological spaces

Porous sets and spherically porous sets of a metric space are studied. In particular, porous, superporous, and equiporous sets of a metric space (X, π) are characterized from the topological point of view. Metrizable spaces that are spherically porous in themselves with respect to some metric generating the topology are characterized. Some relations between the ideals of the classes of porous sets in the real line are established. Bibliography: 13 titles. Translated fromProblemy Matematicheskogo Analiza, No. 20, 2000, pp. 221–242.     

Records in the Fα-scheme. II. Limit laws

Limit theorems for the number of records in a sequence of independent nonidentically distributed random variables are obtained. A generalization of the so-called F^α-scheme is given. Bibliography: 4 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 216, 1994, pp. 42–51. Translated by A. Sudakov.     

Structure of coordinate groups for algebraic sets in partially commutative nilpotent groups

The results obtained deal in algebraic geometry over partially commutative class two nilpotent ℚ-groups, where ℚ is a field of rationals. It is proved that two arbitrary non-Abelian partially commutative class two nilpotent ℚ-groups are geometrically equivalent. A necessary and sufficient condition of being universally geometrically equivalent is specified for two partially commutative class two nilpotent ℚ-groups. Algebraic sets for systems of equations in one variable, as well as for some special systems in several variables, are described. Dedicated to V. N. Remeslennikov on the occasion of his 70th birthday Translated from Algebra i Logika, Vol. 48, No. 2, pp. 378–399, May–June, 2009.