Circular proofs for the Gödel-Löb provability logic

Sequent calculus for the provability logic GL is considered, in which provability is based on the notion of a circular proof. Unlike ordinary derivations, circular proofs are represented by graphs allowed to contain cycles, rather than by finite trees. Using this notion, we obtain a syntactic proof of the Lyndon interpolation property for GL.     

Two Proofs on Max-Min-Max Principle of Jerk Control in Time-Optimal Rectilinear Motion

This paper provides two proofs to the well-known principle of max-min-max jerk control in time-optimal jerk-controlled rectilinear motion, whose proof seems to be missing in the literature. One proof is constructive in that it computes and finds out the solution; the other is a disproof in that it shows all other control schemes lead to longer motion time. The ideas employed in the proofs may be used to solve the same kind of problems in a more general setting.     

Spectral theory of a class of canonical differential systems

The general spectral theory of canonical systems is used to study a generalized Krein system. Direct and inverse problems for this system are considered. In particular, some proofs are supplied for Krein's results published by him without proof. Academy of Radio and Communication, Department of Mathematics, Odessa, Ukraine. Translated from Funktsional'nyi Analiz i Ego Prilozheniya, Vol. 34, No. 2, pp. 50–62, April–June, 2000. Translated by L. A. Sakhnovich     

Bieberbach’s conjecture, the de Branges and Weinstein functions and the Askey-Gasper inequality

The Bieberbach conjecture about the coefficients of univalent functions of the unit disk was formulated by Ludwig Bieberbach in 1916 [4]. The conjecture states that the coefficients of univalent functions are majorized by those of the Koebe function which maps the unit disk onto a radially slit plane. The Bieberbach conjecture was quite a difficult problem, and it was surprisingly proved by Louis de Branges in 1984 [5] when some experts were rather trying to disprove it. It turned out that an inequality of Askey and Gasper [2] about certain hypergeometric functions played a crucial role in de Branges’ proof. In this article I describe the historical development of the conjecture and the main ideas that led to the proof. The proof of Lenard Weinstein (1991) [72] follows, and it is shown how the two proofs are interrelated. Both proofs depend on polynomial systems that are directly related with the Koebe function. At this point algorithms of computer algebra come into the play, and computer demonstrations are given that show how important parts of the proofs can be automated. This article is dedicated to Dick Askey on occasion of his seventieth birthday. 2000 Mathematics Subject Classification Primary—30C50, 30C35, 30C45, 30C80, 33C20, 33C45, 33F10, 68W30     

Approximately Local Derivations

Certain linear operators from a Banach algebra A into a BanachA-bimodule X, which are called approximately local derivations,are studied. It is shown that when A is a C^*-algebra, a Banachalgebra generated by idempotents, a semisimple annihilator Banachalgebra, or the group algebra of a SIN or a totally disconnectedgroup, bounded approximately local derivations from A into Xare derivations. This, in particular, extends a result of B.E. Johnson that ‘local derivations on C^*-algebras arederivations’ and provides an alternative proof of it.     

Some remarks on lengths of propositional proofs

We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m ^d+1) symbols. We show that renaming Frege proof systems are p-equivalent to extended Frege systems. Some open problems in propositional proof length and in logical flow graphs are discussed. Supported in part by NSF grant DMS-9205181     

Lower bounds on static Lovász-Schrijver calculus proofs for Tseitin tautologies

An exponential lower bound on the size of static Lovász-Schrijver proofs of Tseitin tautologies is established. Several techniques, such as translating a static LS₊ proof into a Positivstellensatz proof, extracting a “good” expander out of a given graph by removing edges and vertices, and proving a linear lower bound on the degree of Positivstellensatz proofs for Tseitin tautologies, are used. Bibliography: 22 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 340, 2006, pp. 10–32.     

Randomized proofs in arithmetic

A randomized proof system for arithmetic is introduced. A proof of an arithmetical formula is defined as its derivation from the axioms of arithmetic by the standard rules of inference of arithmetic and also one more rule which we call the random substitution rule. Such proofs can be regarded as a special kind of interactive proof and, more exactly, as a special kind of the Arthur-Merlin proofs. The main result of the paper shows that a proof in arithmetic with the random substitution rule can be considerably shorter than an arithmetical proof of the same formula. Namely, there exists a set of formulas such that (i) these formulas are provable in arithmetic but, unless PSPACE=NP, do not have polynomially long proofs; (ii) these proofs have polynomially long proofs in arithmetic with random substitution (whatever random numbers appear) and the probability of error of these proofs is exponentially small. Bibliography: 10 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 49–71. Translated by E. Ya. Dantsin.     

On quantitative versions of theorems due to F.E. Browder and R. Wittmann

This paper is another case study in the program of logically analyzing proofs to extract new (typically effective) information (‘proof mining’). We extract explicit uniform rates of metastability (in the sense of T. Tao) from two ineffective proofs of a classical theorem of F.E. Browder on the convergence of approximants to fixed points of nonexpansive mappings as well as from a proof of a theorem of R. Wittmann which can be viewed as a nonlinear extension of the mean ergodic theorem. The first rate is extracted from Browder's original proof that is based on an application of weak sequential compactness (in addition to a projection argument). Wittmann's proof follows a similar line of reasoning and we adapt our analysis of Browder's proof to get a quantitative version of Wittmann's theorem as well. In both cases one also obtains totally elementary proofs (even for the strengthened quantitative forms) of these theorems that neither use weak compactness nor the existence of projections anymore. In this way, the present article also discusses general features of extracting effective information from proofs based on weak compactness. We then extract another rate of metastability (of similar nature) from an alternative proof of Browder's theorem essentially due to Halpern that already avoids any use of weak compactness. The paper is concluded by general remarks concerning the logical analysis of proofs based on weak compactness as well as a quantitative form of the so-called demiclosedness principle. In a subsequent paper these results will be utilized in a quantitative analysis of Baillon's nonlinear ergodic theorem.     

A numerical verification method of bifurcating solutions for 3-dimensional Rayleigh–Bénard problems

This paper is the three dimensional extension of the two dimensional work in Nakao et al. (Reliable Comput 9(5):359–372, 2003) and Watanabe et al. (J Math Fluid Mech 6:1–20, 2004) on a computer assisted proof of the existence of nontrivial steady state solutions for Rayleigh–Bénard convection based on the fixed point theorem using a Newton like operator. The differences are emerging of complicated types of bifurcation, direct attack on the problem without stream functions, and increased complexity of numerical computation. The last one makes it hard to proceed the verification of solutions corresponding to the points on bifurcation diagram for three dimensional case. Actually, this work should be the first result for the three dimensional Navier–Stokes problems which seems to be very difficult to solve by theoretical approaches.     

Program derivation with verified transformations — a case study

A program development methodology based on verified program transformations is described and illustrated through derivations of a high level bisimulation algorithm and an improved minimum-state DFA algorithm. Certain doubts that were raised about the correctness of an initial paper-and-pencil derivation of the DFA minimization algorithm were laid to rest by machine-checked formal proofs of the most difficult derivational steps. Although the protracted labor involved in designing and checking these proofs was almost overwhelming, the expense was somewhat offset by a successful reuse of major portions of these proofs. In particular, the DFA minimization algorithm is obtained by specializing and then extending the last step in the derivation of the high level bisimulation algorithm. Our experience suggests that a major focus of future research should be aimed towards improving the technology of machine checkable proofs — their construction, presentation, and reuse. This paper demonstrates the importance of such a technology to the verification of programs and program transformations. We believe that the utility of transformational systems to program development will ultimately rest on a practical program correctness technology. © 1996 John Wiley & Sons, Inc.     

The standard proof,the elegant proof,and the proof without words of tasks in geometry,and their dynamic investigation

Solution of problems in mathematics, and in particular in the field of Euclidean geometry is in many senses a form of artisanship that can be developed so that in certain cases brief and unexpected solutions may be obtained, which would bring out aesthetically pleasing mathematical traits. We present four geometric tasks for which different proofs are given under the headings: standard proof, elegant proof, and the proof without words. The solutions were obtained through a combination of mathematical tools and by dynamic investigation of the geometrical properties.     

Structure of Chevalley groups: The proof from the book

Different geometric proofs of the main structure theorems for Chevalley groups over commutative rings are described and compared. Known geometric proofs, published by I. Z. Golubchik, N. A. Vavilov, A. V. Stepanov, and E. B. Plotkin, such as A₂ and A₃ proofs for classical groups, A₅ and D₅ proofs for E₆, A₇ and D₆ proofs for E₇, and a D₈ proof for E₈ are given in outline. After that, A₂ proofs for exceptional groups of types F₄, E₆, and E₇, based on the multiple commutation, are discussed in more detail. This new proof, the proof from the Book, provides better bounds than any previously known proof. Moreover, it does not use results for fields, the factorization with respect to the radical, or any specific information concerning the structure constants and the equations defining exceptional Chevalley groups. Bibliography: 71 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 330, 2006, pp. 36–76.     

Preservice Teacher Beliefs About Proofs

This article describes a study of backgrounds, beliefs, and attitudes of teachers about proofs. Thirty preservice elementary teachers enrolled in a mathematics content course and 21 secondary mathematics teachers in an abstract algebra course were surveyed. The study explored four issues: preservice teachers' experiences/exposure to proof, their beliefs about what constitutes a proof and the role of proof in mathematics, and their beliefs about when proof should be introduced in grades K-12. Results of the survey are described as a means for discussing the backgrounds and beliefs future teachers hold with regard to teaching proofs in their own classrooms. Finally, a short collection of sample explorations and questions, which could be used to encourage the thinking and writing of proofs in grades K-12, is provided. One of these questions was posed to 215 secondary students; examples of their reasoning and a discussion of the various techniques employed by the students are included.     

Gentzen’s consistency proof without heightlines

This paper gives a Gentzen-style proof of the consistency of Heyting arithmetic in an intuitionistic sequent calculus with explicit rules of weakening, contraction and cut. The reductions of the proof, which transform derivations of a contradiction into less complex derivations, are based on a method for direct cut-elimination without the use of multicut. This method treats contractions by tracing up from contracted cut formulas to the places in the derivation where each occurrence was first introduced. Thereby, Gentzen’s heightline argument, which introduces additional cuts on contracted compound cut formulas, is avoided. To show termination of the reduction procedure an ordinal assignment based on techniques of Howard for Gödel’s T is used.     

Multiple intersections of diagonals of regular polygons,and related topics

Our main concern is to investigate geometrically all sets of three concurrent chords of regular polygons or, equivalently, all adventitious quadrangles (that is, all quadrangles such that the angle between every pair of the six sides is an integral multiple of /n radians). Most of our results are stated without proof. The proofs are elementary, often consisting of straightforward verification; to include them would make the paper much longer and less readable.     

Quintic and septic Eisenstein series

Using results that were well-known to Ramanujan, we give proofs of some results for Eisenstein series in the lost notebook. Our proofs have the additional advantage that it is not necessary to know the results in advance; that is, the proofs are derivations as opposed to verifications.      

An elementary proof of an equivalence theorem relevant in the theory of optimization

The authors give an elementary proof of an equivalence theorem of analysis which is often used in optimization theory. The theorem asserts that certain conditions are equivalent to weak convergence inL ₁. One is the Dunford-Pettis condition concerning absolute integrability. Two others are expressed in terms of Nagumo functions, and can be thought of as growth properties. The original proofs of the various parts of the theorem are scattered in different and specialized mathematical publications. The authors feel it useful to present here a straightforward proof of the various parts in terms of standard Lebesgue integration theory.     

Unsolvable algorithmic problems for semigroups,groups, and rings

A survey of the subject outlined in the heading (with many proof s sketched) is given. A special focus is on the original proofs of the unsolvability theorems of Markov, Post, and Novikov for word problems in semigroups and groups. A method of Shirshov is described, which has led to proof of the main unsolvability theorems for Lie algebras.Translated from Itogi Nauki I Tekhniki, Seriya Algebra, Topologiya, Geometriya, Vol. 25, pp. 3–66, 1987.The Russian names in this survey are given according to standard transliteration. Some Russian authors, however, are also known in the Western literature in a different spelling. The corresponding equivalents are given below, in alphabetical order:     

On the rosenthal inequality for mixing fields

A proof of the Rosenthal inequality for α-mixing random fields is given. The statements and proofs are modifications of the corresponding results obtained by Doukhan and Utev.