Randomized rounding: A technique for provably good algorithms and algorithmic proofs

We study the relation between a class of 0–1 integer linear programs and their rational relaxations. We give a randomized algorithm for transforming an optimal solution of a relaxed problem into a provably good solution for the 0–1 problem. Our technique can be a of extended to provide bounds on the disparity between the rational and 0–1 optima for a given problem instance. This work was supported by Semiconductor Research Corporation grant SRC 82-11-008 and an IBM Doctoral Fellowship.     

Cutting-plane proofs in polynomial space

Following Chvátal, cutting planes may be viewed as a proof system for establishing that a given system of linear inequalities has no integral solution. We show that such proofs may be carried out in polynomial workspace.Research supported by Sonderforschungsbereich 303 (DFG), Institut für Operations Research, Universität Bonn, FR Germany and by NSF grant ECS-8611841.     

Counting proofs in propositional logic

We give a procedure for counting the number of different proofs of a formula in various sorts of propositional logic. This number is either an integer (that may be 0 if the formula is not provable) or infinite. Research described in this paper is supported by Polish Ministry of Science and Higher Education grant NN206 356236.     

Nonrealizability proofs in computational geometry

This paper deals with a class of computational problems in real algebraic geometry. We introduce the concept of final polynomials as a systematic approach to prove nonrealizability for oriented matroids and combinatorial geometries.Hilbert's Nullstellensatz and its real analogue imply that an abstract geometric object is either realizable or it admits a final polynomial. This duality has first been applied by Bokowski in the study of convex polytopes [7] and [11], but in these papers the resulting final polynomials were given without their derivations.It is the objective of the present paper to fill that gap and to describe an algorithm for constructing final polynomials for a large class of nonrealizable chirotopes. We resolve a problem posed in [10] by proving that not every realizable simplicial chirotope admits a solvability sequence. This result shows that there is no easy combinatorial method for proving nonrealizability and thus justifies our final polynomial approach.     

Cycling in proofs and feasibility

There is a common perception by which small numbers are considered more concrete and large numbers more abstract. A mathematical formalization of this idea was introduced by Parikh (1971) through an inconsistent theory of feasible numbers in which addition and multiplication are as usual but for which some very large number is defined to be not feasible. Parikh shows that sufficiently short proofs in this theory can only prove true statements of arithmetic. We pursue these topics in light of logical flow graphs of proofs (Buss, 1991) and show that Parikh's lower bound for concrete consistency reflects the presence of cycles in the logical graphs of short proofs of feasibility of large numbers. We discuss two concrete constructions which show the bound to be optimal and bring out the dynamical aspect of formal proofs. For this paper the concept of feasible numbers has two roles, as an idea with its own life and as a vehicle for exploring general principles on the dynamics and geometry of proofs. Cycles can be seen as a measure of how complicated a proof can be. We prove that short proofs must have cycles.

     

The arithmetic of cuts in models of arithmetic

We present a number of results on the structure of initial segments of models of Peano arithmetic with the arithmetic operations of addition, subtraction, multiplication, division, exponentiation and logarithm. Each of the binary operations introduced is defined in two dual ways, often with quite different results, and we attempt to systematise the issues and show how various calculations may be carried out. To understand the behaviour of addition and subtraction we introduce a notion of derivative on cuts, analogous to differentiation in the calculus. Multiplication, division and other operations are described by higher order versions of derivative. The work here is presented as important preliminary work related to a nonstandard measure theory of non‐definable bounded subsets of a model of Peano arithmetic.     

Topological function-theoretic proofs in spectral theory

In this paper, the spectral theorem and related characterizations of the spectrum and the spectral projections for bounded self adjoint and normal operators on a Hilbert space, are proved in purely topological —function theoretic terms. The basis for such a development, is the Gelfand—Naimark theorem for commutativeC ^*-algebras and the fact that the structure space of the (abelian) von Neumann algebra generated by the operator is a Stonean space.     

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.     

Semigroup identities and proofs

Tamura proved that for any semigroup word U(x, y), if every group satisfying an identity of the form yx ~ xU(x, y)y is abelian, then so is every semigroup that satisfies that identity. Because a group has an identity element and the cancellation property, it is easier to show that a group is abelian than that a semigroup is. If we know that it is, then there must be a sequence of substitutions using xU(x, y)y ~ yx that transforms xy to yx. We examine such sequences and propose finding them as a challenge to proof by computer. Also, every model of y ~ xU(x, y)x is a group. This raises a similar challenge, which we explore in the special case y ~ x ^m y ^p x ⁿ . In addition, we determine the free model with two generators of some of these identities. In particular, we find that the free model for y ~ x ² yx ² has order 32 and is the product of D ₄ (the symmetries of a square), C ₂, and C ₄, and point out relations between such identities and Burnside’s Problem concerning models of x ⁿ ~ y ⁿ . We also examine several identities not related to groups.     

Uniform proofs of q-Series-product identities

In this paper we give a simple proof of the Jacobi triple product identity by using basic properties of cube roots of unity. Then we give a new proof of the quintuple product identity, the septuple product identity and Winquist’s identity by using the Jacobi triple product identity and basic properties of cube and fifth roots of unity. Furthermore, we derive some new product identities by this uniform method. Later, we give some generalizations of those identities. Lastly, we derive some modular equations.     

Experimental mathematics and proofs in the classroom

Experimental mathematics is a serious branch of mathematics that starts gaining attention both in mathematics education and research. We given examples of using experimental techniques (not only) on the classroom. At first sight it seems that introducing experiments will weaken the formal rules and the abstractness of mathematics that are considered a valuable contribution to education as a whole. By putting proof and experiment side by side we show how this can be avoided. We also highlight consequences of experimentation for educational computer software.     

Informal prerequisites for informal proofs

Reasoning and proof play an important role in the mathematics classroom. However, prerequisites for the learning of mathematical reasoning and proof, such as logical competence or the understanding of concepts and proofs, are rarely taught explicitly. In an empirical survey with 106 students in grade 8 we investigated students' declarative and methodological knowledge related to some of these prerequisites. The results show that there are certain deficits which make it difficult for students to learn reasoning and proof.     

More proofs of menger's theorem

Four ways of proving Menger's Theorem by induction are described. Two of them involve showing that the theorem holds for a finite undirected graph G if it holds for the graphs obtained from G by deleting and contracting the same edge. The other two prove the directed version of Menger's Theorem to be true for a finite digraph D if it is true for a digraph obtained by deleting an edge from D.