Robinson forcing is not absolute

Robinson (or infinite model theoretic) forcing is studied in the context of set theory. The major result is that infinite forcing, genericity, and related notions are not absolute relative to ZFC. This answers a question of G. Sacks and provides a non-trivial example of a non-absolute notion of model theory. This non-absoluteness phenomenon is shown to be intrinsic to the concept of infinite forcing in the sense that any ZFC-definable set theory, relative to which forcing is absolute, has the flavor of asserting self-inconsistency. More precisely: IfT is a ZFC-definable set theory such that the existence of a standard model ofT is consistent withT, then forcing is not absolute relative toT. For example, if it is consistent that ZFC+ “there is a measureable cardinal” has a standard model then forcing is not absolute relative to ZFC+ “there is a measureable cardinal.” Some consequences: 1) The resultants for infinite forcing may not be chosen “effectively” in general. This answers a question of A. Robinson. 2) If ZFC is consistent then it is consistent that the class of constructible division rings is disjoint from the class of generic division rings. 3) If ZFC is consistent then the generics may not be axiomatized by a single sentence ofL _w/w. In Memoriam: Abraham Robinson     

Edge quantisation of elliptic operators

The ellipticity of operators on a manifold with edge is defined as the bijectivity of the components of a principal symbolic hierarchy , where the second component takes values in operators on the infinite model cone of the local wedges. In the general understanding of edge problems there are two basic aspects: Quantisation of edge-degenerate operators in weighted Sobolev spaces, and verifying the ellipticity of the principal edge symbol which includes the (in general not explicitly known) number of additional conditions of trace and potential type on the edge. We focus here on these questions and give explicit answers for a wide class of elliptic operators that are connected with the ellipticity of edge boundary value problems and reductions to the boundary. In particular, we study the edge quantisation and ellipticity for Dirichlet–Neumann operators with respect to interfaces of some codimension on a boundary. We show analogues of the Agranovich–Dynin formula for edge boundary value problems. Nicoleta Dines and Bert-Wolfgang Schulze were supported by Chinese-German Cooperation Program “Partial Differential Equations”, NNSF of China and DFG of Germany. Xiaochun Liu was supported by NNSF of China through Grant No. 10501034, and Chinese-German Cooperation Program “Partial Differential Equations”, NNSF of China and DFG of Germany.     

Some properties of autostable models

Established are (1) a nonuniform criterion for the stability of models in terms of enumeration reducibility of constructivizations; (2) a criterion for the autostability of certain particular classes of models close to algebraic number fields; (3) a uniform autostability of each 1-constructive model that is autostable. Supported by RFFR grant No. 096-01-01525 and by ISF grant NQ 6000. Translated fromAlgebra i Logika, Vol. 35, No. 6, pp. 685–698, November–December, 1996.     

autostability of prime models under strong constructivizations

We furnish an example of an Ehrenfeucht theory whose prime model is autostable under strong constructivizations and there exists a prime model in a finite expansion by constants that is nonautostable under strong constructivizations of the theory constructed.     

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.     

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.     

Autostability of hyperarithmetical models

Let be a Δ ₁ ¹ -constructivizable model. If its Scott rank is strictly less than ω ₁ ^CK , then it is proved autostable. But if , then there exists an ordinal α<ω ₁ ^CK for which is not autostable in any degree O^(γ+1) for all γ>α. We also consider some problems concerning Δ ₁ ¹ -autostability of Δ ₁ ¹ -constructivizable Boolean algebras. Supported through the FP “Integration” and the RP “Universities of Russia. Fundamental Research.” Translated fromAlgebra i Logika, Vol. 39, No. 2, pp. 198–205, March–April, 2000.     

Large nilpotent subgroups of finite simple groups

Orders and the structure of large nilpotent subgroups in all finite simple groups are determined. In particular, it is proved that if G is a finite simple non-Abelian group, and N is some of its nilpotent subgroups, then |N|²<|G|. Supported through FP “Integration” project No. 274, by RFFR grant No. 99-01-00550, by International Soros Education Program for Exact Sciences (ISEP) grant No. S99-56, and by a SO RAN grant for Young Scientists, Presidium Decree No. 83 of 03/10/2000. Translated fromAlgebra i Logika, Vol. 39, No. 5, pp. 526–546, September—October, 2000.     

Stability and bifurcation for periodic perturbations of the equilibrium of an oscillator with infinite or infinitesimal oscillation frequency

We consider small perturbations periodic in time of an oscillator whose restoring force has a leading term with exponent 3 or 1/3. The first case corresponds to oscillations with infinitesimal frequency and the second case to oscillations with infinite frequency. The smallness of the perturbation is determined both by the smallness of the considered neighborhood of the equilibrium point and by a small nonnegative parameter ε. For ε=0, the stability of the equilibrium point is studied. For ε>0, we find conditions for an invariant two-dimensional torus to branch off with “soft” or “rigid” loss of stability with loss index 1/2. Translated fromMatematicheskie Zametki, Vol. 65, No. 3, pp. 323–335, March, 1999.     

Direct problem of calculating the magnetic dipole field in a quasilayered medium

A method is developed for calculating the electromagnetic field of a magnetic dipole in a quasilayered two-dimensional medium. The quasi-three-dimensional problem is reduced to a two-dimensional problem for the Fourier-transformed electromagnetic field. An equivalent system of integral equations on the layer boundaries is obtained. This research was partially supported by the State Scientific-Technical Program “Future Information Technologies” (grant No. 0201.06.010) and the Interuniversity Scientific Program “Russian Universities: Basic Research.” Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 94–110, 1998.     

Inverse problem of magnetotelluric sounding in a medium with faults

This article considers a method for solving the direct and the inverse problems in the presence ofH-polarization for the fundamental three-layer model of deep magnetotelluric sounding with vertical tectonic faults and horizontal high-conductivityS-layers in a poorly conducting crystalline matrix. The conductivities may vanish on parts of the vertical cracks or the horizontalS-layers, i.e., in this modelS-layers and vertical faults may degenerate into an insulator. This research was partially supported by the Russian Foundation for Basic Research (grant No. 96-95-64340) 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.     

Discrete-Time Dichotomous Well-Posed Linear Systems and Generalized Schur–Nevanlinna–Pick Interpolation

We introduce a class of matrix-valued functions W called “L²- regular”. In case W is J-inner, this class coincides with the class of “strongly regular J-inner” matrix functions in the sense of Arov–Dym. We show that the class of L²-regular matrix functions is exactly the class of transfer functions for a discrete-time dichotomous (possibly infinite-dimensional) input-state-output linear system having some additional stability properties. When applied to J-inner matrix functions, we obtain a state-space realization formula for the resolvent matrix associated with a generalized Schur–Nevanlinna–Pick interpolation problem. Communicated by Daniel Alpay Submitted: August 20, 2006; Accepted: September 13, 2006     

Numerical analysis of geoelectric fields in a medium with faults

An efficient method of electromagnetic field calculation is applied to the model of a multilayer nonhomogeneous medium with an arbitrary number of vertical faults. The model simulates a medium that includes the asthenosphere, the crustal layer, and the surface sedimentary layer, all joined by conducting faults. The numerical results are calculated and the effect of faults is assessed. This research was partially supported by the Russian Foundation for Basic Research (grant No. 96-05-64340) and by the Interuniversity Scientific Program “Russian Universities: Basic Research.” Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 85–93, 1998.     

Complexity of Boolean algebras and their Scott rank

We deal with problems associated with Scott ranks of Boolean algebras. The Scott rank can be treated as some measure of complexity of an algebraic system. Our aim is to propound and justify the procedure which, given any countable Boolean algebra, will allow us to construct a Boolean algebra of a small Scott rank that has the same natural algebraic complexity as has the initial algebra. In particular, we show that the Scott rank does not always serve as a good measure of complexity for the class of Boolean algebras. We also study into the question as to whether or not a Boolean algebra of a big Scott rank can be decomposed into direct summands with intermediate ranks. Examples are furnished in which Boolean algebras have an arbitrarily big Scott rank such that direct summands in them either have a same rank or a fixed small one, and summands of intermediate ranks are altogether missing. This series of examples indicates, in particular, that there may be no nontrivial mutual evaluations for the Scott and Frechet ranks on a class of countable Boolean algebras. Supported by RFFR grant No. 99-01-00485, by a grant for Young Scientists from SO RAN, 1997, and by the Federal Research Program (FRP) “Integration”. Translated fromAlgebra i Logika, Vol. 38, No. 6, pp. 643–666, November–December, 1999.     

Solving elliptical equations with high-contrast coefficients in an unbounded region

An approximation model is proposed for an elliptical equation with complex rapidly varying coefficients. An efficient numerical method is developed and implemented. A problem of geoelectricity requiring solution of an equation in this setting is investigated. This research was partially supported by the Russian Foundation for Basic Research (grant No. 96-05-64340) and by the Interuniversity Scientific Program “Russian Universities: Basic Research.” Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 37–45, 1998.     

On numerical optimization theory of infinite kernel learning

In Machine Learning algorithms, one of the crucial issues is the representation of the data. As the given data source become heterogeneous and the data are large-scale, multiple kernel methods help to classify “nonlinear data”. Nevertheless, the finite combinations of kernels are limited up to a finite choice. In order to overcome this discrepancy, a novel method of  “infinite”  kernel combinations is proposed with the help of infinite and semi-infinite programming regarding all elements in kernel space. Looking at all infinitesimally fine convex combinations of the kernels from the infinite kernel set, the margin is maximized subject to an infinite number of constraints with a compact index set and an additional (Riemann–Stieltjes) integral constraint due to the combinations. After a parametrization in the space of probability measures, it becomes semi-infinite. We adapt well-known numerical methods to our infinite kernel learning model and analyze the existence of solutions and convergence for the given algorithms. We implement our new algorithm called “infinite” kernel learning (IKL) on heterogenous data sets by using exchange method and conceptual reduction method, which are well known numerical techniques from solve semi-infinite programming. The results show that our IKL approach improves the classifaction accuracy efficiently on heterogeneous data compared to classical one-kernel approaches.     

Large hyperbolic lattices

For a fundamental group of a compact orientable manifold, a condition is specified that is sufficient to guarantee the presence of a “virtual” epimorphism onto a free non-Abelian group. A consequence is deriving a strong Tits alternative. An arbitrary noncompact finitely generated discrete subgroup in PO(3, 1) either is large or is virtually Abelian. An application is provided to the problem of uniform exponential growth for lattices in a 3-dimensional hyperbolic space and of growth of Betti numbers for lattices in a hyperbolic n-dimensional space, where n is an odd number. Supported by RFBR (project No. 08-01-00067), by DFG grant Gr 627-11, and by Forschergruppe “Spektrale Analysis, asymptotical Verteilungen und stochastische Dynamiken,” Billfold University. (G. A. Noskov) Translated from Algebra i Logika, Vol. 48, No. 2, pp. 174–189, March–April, 2009.     

On the extreme inequalities of infinite group problems

Infinite group relaxations of integer programs (IP) were introduced by Gomory and Johnson (Math Program 3:23–85, 1972) to generate cutting planes for general IPs. These valid inequalities correspond to real-valued functions defined over an appropriate infinite group. Among all the valid inequalities of the infinite group relaxation, extreme inequalities are most important since they are the strongest cutting planes that can be obtained within the group-theoretic framework. However, very few properties of extreme inequalities of infinite group relaxations are known. In particular, it is not known if all extreme inequalities are continuous and what their relations are to extreme inequalities of finite group problems. In this paper, we describe new properties of extreme functions of infinite group problems. In particular, we study the behavior of the pointwise limit of a converging sequence of extreme functions as well as the relations between extreme functions of finite and infinite group problems. Using these results, we prove for the first time that a large class of discontinuous functions is extreme for infinite group problems. This class of extreme functions is the generalization of the functions given by Letchford and Lodi (Oper Res Lett 30(2):74–82, 2002), Dash and Günlük (Proceedings 10th conference on integer programming and combinatorial optimization. Springer, Heidelberg, pp 33–45 (2004), Math Program 106:29–53, 2006) and Richard et al. (Math Program 2008, to appear). We also present several other new classes of discontinuous extreme functions. Surprisingly, we prove that the functions defining extreme inequalities for infinite group relaxations of mixed integer programs are continuous. S.S. Dey and J.-P.P. Richard was supported by NSF Grant DMI-03-48611.