The method of Iterated Defect-Correction and its application to two-point boundary value problems

Summary In Part II of this paper we present a rigorous analysis of the Iterated Defect-Correction — applied to two-point boundary value problems — which was introduced in Part I of this paper [1]. A complete proof of Theorem 5. 1 of [1] is given.     

Position dependent and stochastic thinning of point processes

A short probabilistic proof of Kallenberg's theorem [2] on thinning of point processes is given. It is extended to the case where the probability of deletion of a point depends on the position of the point and is itself random. The proof also leads easily to a statement about the rate of convergence in Renyi's theorem on thinning a renewal process.     

The inner structure of the dilogarithm in algebraic fields

A certain combination of dilogarithms of powers of an algebraic base is constructed and shown to have significant properties when the powers are divisors of the highest power (index) in the relation. The combination is called a ladder and under some circumstances is zero when all the coefficients involved are rational. When this happens it is found empirically that the base satisfies an equation of cyclotomic form whose structure is obtainable by inspection from the ladder. A proof of this equation is given for the case where the ladder is obtainable by a finite number of steps from Abel's functional equation. A number of conjectures are made and used to discover many new relations, all of which are confirmed numerically, but which do not appear to be capable of analytic proof with presently available methods. The paper concludes with some conjectures on the cyclotomic equations which occur in this context.     

Covering radius and dual distance

Recently a number of bounds have been obtained for the covering radius of a code with given length and cardinality. In this paper we show that—perhaps surprisingly—the covering radius of a code depends heavily on its dual distance. We consider an arbitrary finite Abelian group alphabet though in the applications the alphabet is very often the field F ₂.     

Hausdorff's moment problem and expansions in Legendre polynomials

A new proof is given for Hausdorff's condition on a set of moments which determines when the function generating these moments is in L². The proof uses Legendre polynomials and their discrete extensions found by Tchebychef. Then an extension is given to a weighted L² space using Jacobi polynomials and their discrete extensions.     

The boundary characteristic and the volume of lattice polyhedra

The boundary characteristic — introduced by Ding and Reay — is a functional defined for a given planar tiling which associates with a given lattice figure, some integer. It appeared to be a very useful parameter to determine the area of lattice figures in the planar tilings with congruent regular polygons. The purpose of this paper is to extend the notion of the boundary characteristic to lattice polyhedra inR³. Studying some of its properties we show, in particular, that it can be applied to determine the volume of lattice polyhedra.     

Signature classes of transportation polytopes

Signature algorithms solve certain classes of transportation problems in a number of steps bounded by the diameter of the dual polyhedron. The class of problems to which signature algorithms may be applied—the signature classes of the title—are characterized, and the monotonic Hirsch conjecture is shown to hold for them. In addition, certain more precise results are given for different cases. Finally, it is explained why a supposed proof of the Hirsch conjecture for all transportation polytopes is incomplete and apparently irremedial.Dedicated with affection to Philip Wolfe on the occasion of his 65th birthday.     

On the width—length inequality

This paper was written at the Rensselaer Polytechnic Institute in 1963. A lecture based on it was given at the Rand Corporation in 1965 and this version is in the form in which Ray Fulkerson received it at Rand.The paper is the underpinning for results on resistor network inequalities (Reference [4]) which has not been published. A specific example, however, appears inProceedings of the IEEE 51 (1963) 1047–1048. There is also a parallel theory of the abstract assignment problem; every W—L matrix being an assignment matrix.More is known about minimal non-W—L matrices. U. Peled has found several additional classes of matrices which are also classically known in other contexts. A consequence of a recent matrix theorem is apparently that the degenerate projective planes are the only minimal matrices requiring unequal weights.Due to unfortunate circumstances this article was originally published (Mathematical Programming 16(2)(1979) 245–259) without the proof corrections. Thecorrect version is printed herewith. Please use this version when referring to the paper.The preparation of this paper was supported by the National Science Foundation under grant GP-14. Editor's Note: This paper, although written in 1963, was sought for inclusion inMathematical Programming Study 8—Polyhedral Combinatorics, which was dedicated to the memory of D.R. Fulkerson. Unfortunately, an editorial mishap prevented its inclusion. Nevertheless, the historical importance of the paper, the fact that it has been widely referenced and influenced Fulkerson's and others' work in the area has convinced the Editor that it should be published and hence made readily available. Alfred Lehman has given his assent to this despite his reluctance to publish a paper which is not current.     

Invariant random boolean fields

In the set of finite binary sequences a Markov process is defined with discrete time in which each symbol of the binary sequence at time t+1 depends on the two neighboring symbols at time t. A proof is given of the existence and uniqueness of an invariant distribution, and its derivation is also given in a number of cases.Translated from Matematicheskie Zametki, Vol. 6. No. 5, pp. 555–566, November, 1969.     

Transformations of Feynman integrals under nonlinear transformations of the phase space

The Feynman measure is defined as a linear continuous functional on a test-function space (introduced in the paper). The functional is given by means of its Fourier transform. Not only a positive-definite correlation operator but also one without fixed sign is considered (the latter case corresponds to the so-called symplectic, or Hamiltonian, Feynman measure). The Feynman integral is the value of the Feynman measure on a function (in the test-function space). The effect on the Feynman measure of nonlinear transformations of the phase space in the form of shifts along vector fields or along integral curves of vector fields is described. Analogs of the well-known Cameron—Martin, Girsanov—Maruyama, and Ramer formulas in the theory of Gaussian measures are obtained. The results of the paper can be regarded as formulas for a change of variable in Feynman integrals.Moscow State University. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 100, No. 1, pp. 3–13, July, 1994.     

Newton's solution to the equiangular spiral problem and a new solution using only the equiangular property

This paper is a study of Proposition IX of Book I of Newton's Principia, the problem of determining the centripetal force for an equiangular spiral. In Newton's main proof of this proposition there is an error concerning his reason for the figure SPRQT being “given in kind,” and a very interesting technique of varying things in the neighborhood of a limit. This main proof utilized Newton's formula for the limit of SP²QT²/QR given in Corollary I to Proposition VI of the Principia. Newton also gave an alternate proof which utilized his formula for SY²PV given in Corollary III to Proposition VI. The “given” of Proposition IX was “a spiral PQS, cutting all the radii SP, SQ, &c., in a given angle.” Both the main proof and the alternate proof implicitly depend on the property of the equiangular spiral that the radius of curvature at any point is proportional to the pole distance SP. We here offer a new proof of Newton's proposition which does not depend on this implicit assumption.     

A short proof of Kneser's conjecture

In the paper a short proof is given for Kneser's conjecture. The proof is based on Borsuk's theorem and on a theorem of Gale.     

On a generalization of the Kalman-Yakubovic lemma

In this paper we generalize the Kalman-Yakubovic lemma to infinite dimensions—or, more precisely, to semigroups of operators over a Hilbert space. The proof differs substantially from the finite-dimensional version and is based on the Paley-Wiener-Helson-Lowdenslager factorization theorem.     

Posted price profit maximization for multicast by approximating fixed points

We describe an iterative fixed point approach for the following stochastic optimization problem: given a multicast tree and probability distributions of user utilities, find an optimal posted price mechanism—i.e., compute prices to offer the users in order to maximize the expected profit of the service provider. We show that any optimum pricing is a fixed point of an efficiently computable function. We can then apply the non-linear Jacobi and Gauss–Seidel methods of coordinate descent. We provide proof of convergence to the optimum prices for special cases of utility distributions and tree edge costs.     

The gap between monotone and non-monotone circuit complexity is exponential

A. A. Razborov has shown that there exists a polynomial time computable monotone Boolean function whose monotone circuit complexity is at leastn ^{c losn} . We observe that this lower bound can be improved to exp(cn ^1/6–o(1)). The proof is immediate by combining the Alon—Boppana version of another argument of Razborov with results of Grötschel—Lovász—Schrijver on the Lovász — capacity, of a graph.     

Comments on “a numerical approach to the infinite horizon problem of deterministic control theory”

In the paper cited above a proof about an estimate of the rate of convergence for a special discretization scheme for the Hamilton—Jacobi equation is given. The proof is essentially based on the identification between functions andv _h ^k . Here we give a simple example which shows that this identification is incorrect.     

Linear Systems of Cubics Singular at General Points of Projective Space

We present an elementary proof that given a general collection of d points in Pⁿ the linear system of cubics singular on each point has the expected codimension except when n=4 and d=7. In that case the cubic is unique. This, together with previous work of the author, gives a proof of the Alexander–Hirschowitz interpolation theorem.     

On the finiteness theorem of Siegel and Mahler concerning diophantine equations

In this paper we present a new proof, involving so-called nonstandard arguments, of Siegel's classical theorem on diophantine equations: Any irreducible algebraic equation f(x,y) = 0 of genus g > 0 admits only finitely many integral solutions. We also include Mahler's generalization of this theorem, namely the following: Instead of solutions in integers, we are considering solutions in rationals, but with the provision that their denominators should be divisible only by such primes which belong to a given finite set. Then again, the above equation admits only finitely many such solutions. From general nonstandard theory, we need the definition and the existence of enlargements of an algebraic number field. The idea of proof is to compare the natural arithmetic in such an enlargement, with the functional arithmetic in the function field defined by the above equation.     

Schubert graphs,symmetric groups and flags of Boolean lattices

We introduce the concept of Schubert graphs, as Schubert spaces — in the meaning of A. Bichara and C. Somma [2] — whose lines have exactly two points. They turn out to be isomorphic to particular Cayley graphs of symmetric groups; this leads also to a new proof of a well-known characterization of symmetric groups. In connection with [2], we prove that a Schubert graph is isomorphic to the graph representing the flags of a Boolean lattice. Finally, we discuss the independence of the axioms.To Professor Adriano Barlotti on the occasion of his seventieth birthday     

Contact Dehn surgery, symplectic fillings, and Property P for knots

These are notes of a talk given at the Mathematische Arbeitstagung 2005 in Bonn. Following ideas of Özbağcı–Stipsicz, a proof based on contact Dehn surgery is given of Eliashberg's concave filling theorem for contact 3-manifolds. The role of the theorem in the Kronheimer–Mrowka proof of Property P for nontrivial knots is sketched.