Choice functions and well-orderings over the infinite binary tree

We give a new proof showing that it is not possible to define in monadic second-order logic (MSO) a choice function on the infinite binary tree. This result was first obtained by Gurevich and Shelah using set theoretical arguments. Our proof is much simpler and only uses basic tools from automata theory. We show how the result can be used to prove the inherent ambiguity of languages of infinite trees. In a second part we strengthen the result of the non-existence of an MSO-definable well-founded order on the infinite binary tree by showing that every infinite binary tree with a well-founded order has an undecidable MSO-theory.     

On reid’s 3-simplicial matroid theorem

In this paper we prove the following result of Ralph Reid (which was never published nor completely proved). Theorem. Let M be a matroid coordinatizable (representable) over a prime field F. Then there is a 3-simplicial matroid M′ over F which is a series extension of M. The proof we give is different from the original proof of Reid which uses techniques of algebraic topology. Our proof is constructive and uses elementary matrix operations.     

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.     

The small octagon with longest perimeter

The convex octagon with unit diameter and maximum perimeter is determined. This answers an open question dating from 1922. The proof uses geometric reasoning and an interval arithmetic based global optimization algorithm to solve a series of non-linear and non-convex programs involving trigonometric functions.     

Global exact controllability of 1d Schrödinger equations with a polarizability term

We consider a quantum particle in a 1d interval submitted to a potential. The evolution of this particle is controlled using an external electric field. Taking into account the so-called polarizability term in the model (quadratic with respect to the control), we prove global exact controllability in a suitable space for arbitrary potential and arbitrary dipole moment. This term is relevant both from the mathematical and physical points of view. The proof uses tools from the bilinear setting and a perturbation argument.     

Poisson过程分解问题的一个注记

在研究Poisson过程分解问题时,现有文献的证明往往令人费解,本文主要运用极限理论,给出了一个简明易懂的证明.     

Effective estimates on indefinite ternary forms

We give an effective proof of a theorem of Dani and Margulis regarding values of indefinite ternary quadratic forms at primitive integer vectors. The proof uses an effective density-type result for orbits of the groups SO(2, 1) on SL(3, ?)/SL(3, ?).     

The Kissing Problem in Three Dimensions

The kissing number k(3) is the maximal number of equal size nonoverlapping spheres in three dimensions that can touch another sphere of the same size. This number was the subject of a famous discussion between Isaac Newton and David Gregory in 1694. The first proof that k(3) = 12 was given by Schutte and van der Waerden only in 1953. In this paper we present a new solution of the Newton--Gregory problem that uses our extension of the Delsarte method. This proof relies on basic calculus and simple spherical geometry.     

Minimax Results and Finite-Dimensional Separation

In this paper, we review and unify some classes of generalized convex functions introduced by different authors to prove minimax results in infinite-dimensional spaces and show the relations between these classes. We list also for the most general class already introduced by Jeyakumar (Ref. 1) an elementary proof of a minimax result. The proof of this result uses only a finite-dimensional separa- tion theorem; although this minimax result was already presented by Neumann (Ref. 2) and independently by Jeyakumar (Ref. 1), we believe that the present proof is shorter and more transparent.     

Time asymptotics for solutions of the Burgers equation with a periodic force

We consider the Burgers equation with a periodic force which presents a simplified model for turbulence. We are interested in the asymptotic behaviour of solutions for . This problem has been studied by Sinai who uses a probabilistic and very technical approach. Using methods from spectral theory we get similar results. This functional analytic approach gives an easier proof. For certain initial data (periodic or some random perturbations of those) we show time-convergence towards a deterministic periodic limit solution related to the ground state of a certain Schr?dinger operator. Received June 10, 1998     

A simple proof of Bernstein-Lunts equivalence

We give a new proof of the Bernstein-Lunts equivalence of ordinary and equivariant derived categories of Harish-Chandra modules. This proof requires no boundedness assumptions. It uses K-projective resolutions of equivariant complexes, which are shown to exist and constructed explicitly when the group under consideration is reductive. The general case can be obtained from the reductive case by techniques of [MP].     

Higher spin generalisation of Fueter's theorem

In this paper, we generalize Fueter's theorem to the higher spin setting. To do so, we consider an alternative proof for the celebrated theorem that uses the Fischer decomposition. This decomposition is then extended to spaces of polynomials that depend on wedge variables, after which we can finish the proof of our higher spin Fueter theorem.     

Families Of K3 surfaces and Lyapunov exponents

Consider a family of K3 surfaces over a hyperbolic curve (i.e., Riemann surface). Their second cohomology groups form a local system, and we show that its top Lyapunov exponent is a rational number. One proof uses the Kuga–Satake construction, which reduces the question to Hodge structures of weight 1. A second proof uses integration by parts. The case of maximal Lyapunov exponent corresponds to modular families coming from the Kummer construction.     

AgentGeom: a multiagent system for pedagogical support in geometric proof problems

This paper aims, first, to describe the fundamental characteristics and workings of the AgentGeom artificial tutorial system, which is designed to help students develop knowledge and skills related to problem solving, mathematical proof in geometry, and the use of mathematical language. Following this, we indicate the manner in which a secondary school student can appropriate these abilities through interactions with the system. Our system uses strategic messages of the agent tutor in an argumentative process that collaborates with a student in the construction of a proof.     

Stability properties of a nonstandard finite difference scheme for a hantavirus epidemic model

This paper studies the stability properties of a nonstandard finite difference (NSFD) scheme used to simulate the dynamics of a mouse population model in hantavirus epidemics. It is shown that this difference scheme and the underlying system of differential equations have the same dynamics. The proof uses the fact that the total population obeys the logistic equation, as well as techniques from calculus, graphical analysis, and dynamical systems.     

The Topological Representation of Oriented Matroids

We present a new proof of the Topological Representation Theorem for oriented matroids in the general rank case. Our proof is based on an earlier rank 3 version. It uses hyperline sequences and the generalized Schonflies theorem. As an application, we show that one can read off oriented matroids from arrangements of embedded spheres of codimension one, even if wild spheres are involved.     

Dynkin's isomorphism theorem and the Ray-Knight theorems

Summary In the case of diffusions, we show that the isomorphism theorem of Dynkin and the Ray-Knight theorems can be derived from each other. Our proof uses additivity properties of squared Bessel processes and an absolute continuity relation between squared Bessel processes of dimensions one and three.Research supported in part by Air Force Office of Scientific Research (USAFOSR 89-0261)This work was carried out while visiting the Technion     

LR(k) grammars and deterministic languages

A clear proof of the statement that every deterministic language has an LR(l) grammar is given. It uses a definition ofLR(k) grammars found in Lewis and Stearns and the Ginsburg’s simulation of apda by a contex-free grammar. This work is part of a Master’s thesis conducted under the supervision of Professor Eliahu Shamir.     

The theorem of Kronheimer-Mrowka

A proof of the conjecture of Thom (algebraic curves in the complex projective plane minimize genus within their homology class) due to Kronheimer-Mrowka is presented. The proof uses the mod-2 Seiberg-Witten invariants.