Probabilistic verification of proofs in calculuses

We define a special kind of a probabilistically checkable proof system, namely, probabilistically checkable proof calculuses (PCP calculuses). A proof in such a calculus can be verified with sufficient confidence by examining only one random path in the proof tree, without reading the whole proof. The verification procedure just checks all applications of inference rules along the path; its running time is assumed to be polynomial in the theorem length. It is shown that the deductive power of PCP calculuses is characterized as follows: (i) the decision problem for theorems is in PSPACE for all PCP calculuses; and (ii) the mentioned problem is PSPACE-hard for some of the calculuses. Bibliography: 14 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 241, 1997, pp. 97–116 This research was supported in part by the Russian Foundation for Basic Research. Translated by E. Ya. Dintsin.     

Some topological minimax theorems

Two topological variants of the minimax theorem are proved with no restrictions on one of the spaces except for those related to the function under consideration. The conditions concerning the behavior of the function deal only with the interval between the maximin and minimax. As corollaries, we obtain the well-known theorems of Sion and Hoang-Tui on quasiconvex-quasiconcave semicontinuous functions. The scheme of arguments goes back to the Hahn-Banach theorem and the separating hyperplane theorem. It is shown how this scheme can be explicitly realized in the proof of the Hahn-Banach theorem. Translated fromMaternaticheskie Zametki, Vol. 67, No. 1, pp. 141–149, January, 2000.     

On a theorem of yulmukhametov

A new version and a modified proof of Yulmukhametov’s theorem on the decomposition of measures are given. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 859–862, June, 2000.     

On estimates for integral solutions of linear inequalities

Recently, Bombieri and Vaaler obtained an interesting adelic formulation of the first and the second theorems of Minkowski in the Geometry of Numbers and derived an effective formulation of the well-known “Siegel’s lemma” on the size of integral solutions of linear equations. In a similar context involving linearinequalities, this paper is concerned with an analogue of a theorem of Khintchine on integral solutions for inequalities arising from systems of linear forms and also with an analogue of a Kronecker-type theorem with regard to euclidean frames of integral vectors. The proof of the former theorem invokes Bombieri-Vaaler’s adelic formulation of Minkowski’s theorem.     

Normality and boundary behaviour of arbitrary and meromorphic functions along simple curves and applications

In this paper, we establish some theorems giving necessary and sufficient conditions for an arbitrary function defined in the unit disc of the complex plane to have boundary values along classes of an equivalence relation over simple curves. Our results generalize the well-known theorems on asymptotic and angular boundary behaviours of meromorphic functions (Lindelölf-, Lehto–Virtanen- and Seidel–Walsh-type theorems). The obtained results are applied to the study of boundary behaviour of meromorphic functions along curves using P-sequences, as well as in the proof of the uniqueness theorem similar to ?aginjan’s one. The constructed examples of functions show that the results cannot be improved.     

A constructive proof of Tucker's combinatorial lemma

Tucker's combinatorial lemma is concerned with certain labellings of the vertices of a triangulation of the n-ball. It can be used as a basis for the proof of antipodal-point theorems in the same way that Sperner's lemma yields Brouwer's theorem. Here we give a constructive proof, which thereby yields algorithms for antipodal-point problems. Our method is based on an algorithm of Reiser.     

Hahn–Banach extension theorems for multifunctions revisited

Several generalizations of the Hahn–Banach extension theorem to K-convex multifunctions were stated recently in the literature. In this note we provide an easy direct proof for the multifunction version of the Hahn–Banach–Kantorovich theorem and show that in a quite general situation it can be obtained from existing results. Then we derive the Yang extension theorem using a similar proof as well as a stronger version of it using a classical separation theorem. Moreover, we give counterexamples to several extension theorems stated in the literature. Dedicated to Jean-Paul Penot with the occasion of his retirement.     

Some comments on multidimensional local limit theorems

A proof is given of a theorem on monotonic approximation of continuous functions in R_k, 1 k, with compact carriers. The obtained theorem is employed to prove multidimensional local limit theorems.Translated from Matematicheskie Zametki, Vol. 14, No. 4, pp. 559–563, October, 1973.     

MacMahon's partition identity and the coin exchange problem

One of MacMahon's partition theorems says that the number of partitions of n into parts divisible by 2 or 3 equals the number of partitions of n into parts with multiplicity larger than 1. Recently, Holroyd has obtained a generalization. In this short note, we provide a bijective proof of his theorem.     

Hausdorff dimension and the dynamics of diffeomorphisms

A proof of the Hilbert-Smith conjecture for a free Lipschitz action is given. The proof is elementary in the sense that it does not rely on Yang’s theorem about the cohomology dimension of the orbit space of thep-acid action. The result turns out to be true for the class of spaces of finite Hausdorff volume, which is considerably wider than Riemannian manifolds. As a corollary to the Lipschitz version of the Hilbert-Smith conjecture, the theorem asserting that the diffeomorphism group of a finite-dimensional manifold has no small subgroups is obtained. Translated fromMatermaticheskie Zametki, Vol. 65, No. 3, pp. 457–463, March, 1999.     

Connected extensions of metric spaces and fixed points of Banach contractions

Two theorems announced by the author are proved. The first theorem concerns the existence of connected metrizable extensions of metric spaces. The second theorem is a slightly paradoxical assertion about the validity of the fixed-point principle. Bibliography: 4 titles. Translated fromProblemy Matematicheskogo Analiza, No. 17, 1997, pp. 227–237.     

The octahedron theorem in Minkowski three-space a metric vector space proof of Miquel's theorem in the Laguerre plane

As is well known [1, p.480], the cycles and spears of the real Laguerre plane can be represented by the points and null planes of three-dimensional Minkowski space. Miquel's theorem in the Laguerre plane can then be expressed as an intrinsically interesting Minkowski space theorem the octahedron theorem. We outline the correspondence between the two theorems, and then give a metric vector space proof of the octahedron theorem, thereby providing an alternate proof of Miquel's theorem. We then discuss the generalization of both theorems to more general spaces.     

Classical and approximate sampling theorems; studies in the and the uniform norm

The approximate sampling theorem with its associated aliasing error is due to J.L. Brown (1957). This theorem includes the classical Whittaker–Kotel’nikov–Shannon theorem as a special case. The converse is established in the present paper, that is, the classical sampling theorem for , 1p<∞, w>0, implies the approximate sampling theorem. Consequently, both sampling theorems are fully equivalent in the uniform norm.Turning now to -space, it is shown that the classical sampling theorem for , 1<p<∞ (here p=1 must be excluded), implies the -approximate sampling theorem with convergence in the -norm, provided that f is locally Riemann integrable and belongs to a certain class Λ^p. Basic in the proof is an intricate result on the representation of the integral as the limit of an infinite Riemann sum of |f|^p for a general family of partitions of ; it is related to results of O. Shisha et al. (1973–1978) on simply integrable functions and functions of bounded coarse variation on . These theorems give the missing link between two groups of major equivalent theorems; this will lead to the solution of a conjecture raised a dozen years ago.     

Limit theorems with refinements for random processes

One considers the problem of the derivation of limit theorems with refinements in functional spaces. One proves theorems on the expansions of the mathematical expectations of bounded continuous linear functionals of the trajectories of a Gaussian random process. From these theorems one derives a limit theorem with correction terms for the mathematical expectation of a functional of the trajectories of the time-discretized Wiener process, when the step of the discretization tends to zero. One discusses questions regarding generalizations, methods of proof, and the relation of these kind of limit theorems with other problems of the theory of probability, as well as possible applications of these theorems.Translated from Veroyatnostnye Raspredeleniya i Matematicheskaya Statistika, pp. 94–114, 1986.     

Alternatives to the Halpern-Läuchli theorem

In this paper, it is shown that the fact that the BPI holds in the Cohen's symmetric model can be used as an equal substitute for the Halpern-Läuchli theorem. Also, some alternatives to the Halpern-Läuchli theorem in the form of absoluteness theorems for a certain class of statements are consequences¹ of such consistency results. The article also contains a new proof of the Halpern-Läuchli theorem.     

On the law of the iterated logarithm for sums of independent random variables with finite variances

The objective of the paper is to find simple but rather general conditions giving the opportunity to extend the Kolmogorov theorem on the law of the iterated logarithm to the case of unbounded summands with finite variances. The results obtained in the paper include both the Kolmogorov and the Hartman-Wintner theorems. Bibliography: 11 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 244, 1997, pp. 257–270. Translated by L. Rozovsky.     

Non-zero solutions of equations with strong nonlinearities

Existence theorems are proved for non-zero solutions of a multi-point Valle-Poussin boundary problem for differential equations with strong non-linearities. The proof is based on the construction of special cones in a Banach space, and on the application of a modification of a theorem on fixed points of operators which expand a cone.Translated from Matematicheskie Zametki, Vol. 5, No. 2, pp. 253–260, February, 1969.     

Uniqueness theorem for locally antipodal Delaunay sets

We prove theorems on locally antipodal Delaunay sets. The main result is the proof of a uniqueness theorem for locally antipodal Delaunay sets with a given 2R-cluster. This theorem implies, in particular, a new proof of a theorem stating that a locally antipodal Delaunay set all of whose 2R-clusters are equivalent is a regular system, i.e., a Delaunay set on which a crystallographic group acts transitively.     

Representation theorems for recursively enumerable sets and a conjecture related to poonen’s large subring of $\bf \mathbb{Q} $

It is remarked that unsolvability results can often be extended to yield novel “representation” theorems for the set of all recursively enumerable sets. In particular, it is shown that an analysis of the proof of the unsolvability of Hilbert’s 10th problem over Poonen’s large subring of \mathbbQ \mathbb{Q} can provide such a theorem. Moreover, applying that theorem to the case of a simple set leads to a conjecture whose truth would imply the unsolvability of Hilbert’s 10th problem over \mathbbQ \mathbb{Q} .     

Limit theorems on locally compact Abelian groups

We prove limit theorems for row sums of a rowwise independent infinitesimal array of random variables with values in a locally compact Abelian group. First we give a proof of Gaiser's theorem [4, Satz 1.3.6], since it does not have an easy access and it is not complete. This theorem gives sufficient conditions for convergence of the row sums, but the limit measure cannot have a nondegenerate idempotent factor. Then we prove necessary and sufficient conditions for convergence of the row sums, where the limit measure can be also a nondegenerate Haar measure on a compact subgroup. Finally, we investigate special cases: the torus group, the group of p ‐adic integers and the p ‐adic solenoid. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)