A “from scratch” proof of a theorem of Rockafellar and Fulkerson

The theorem of this paper is of the same general class as Farkas' Lemma, Stiemke's Theorem, and the Kuhn—Fourier Theorem in the theory of linear inequalities. LetV be a vector subspace ofR ⁿ , and let intervalsI ¹,, I ⁿ of real numbers be prescribed. A necessary and sufficient condition is given for existence of a vector (x ¹ ,, x ⁿ ) inV such thatx ⁱ I ⁱ (i = 1, ,n); this condition involves the elementary vectors (nonzero vectors with minimal support) ofV . The proof of the theorem uses only elementary linear algebra.The author at present holds a Senior Scientist Award of the Alexander von Humboldt Stiftung.     

Über Mosers regularisiertes Variationsproblem für minimale Blätterungen desn-dimensionalen Torus

We consider regular and Cantor-like minimal foliations of the (n+1)-dimensional TorusT ⁿ⁺¹ whose leaves minimize a given variational integral. Each leaf of such a generalized foliation lies in the universal coveringR ⁿ⁺¹ within a finite distance to the affine leaves (z, x+) of fixed R ⁿ . We show that the conjugation-functionU (x,), mapping the affine leaves (x, x+) into the leaves(x,U (x,x+)) of the generalized foliation, is itself a minimal solution of an extended degenerate variational problem onT ⁿ +1. If R ⁿ /Q ⁿ the functionU is characterized in a unique way as (discontinuous) limit of the minimal solutions of the corresponding regularized problem.     

New lower semicontinuity results for polyconvex integrals

Summary We study integral functionals of the formF(u, )= f(u)dx, defined foru C¹(;R ^k), R ⁿ . The functionf is assumed to be polyconvex and to satisfy the inequalityf(A) c₀¦(A)¦ for a suitable constant c₀ > 0, where (A) is then-vector whose components are the determinants of all minors of thek×n matrixA. We prove thatF is lower semicontinuous onC ¹(;R ^k) with respect to the strong topology ofL ¹(;R ^k). Then we consider the relaxed functional , defined as the greatest lower semicontinuous functional onL ¹(;R ^k ) which is less than or equal toF on C¹(;R ^k). For everyu BV(;R ^k) we prove that (u,) f(u)dx+c₀¦D^su¦(), whereDu=u dx+D^su is the Lebesgue decomposition of the Radon measureDu. Moreover, under suitable growth conditions onf, we show that (u,)= f(u)dx for everyu W^1,p(;R ^k), withp min{n,k}. We prove also that the functional (u, ) can not be represented by an inte- gral for an arbitrary functionu BV_loc(R ⁿ;R ^k). In fact, two examples show that, in general, the set function (u, ) is not subadditive whenu BV_loc(R ⁿ;R ^k), even ifu W _loc ^1,p (R ⁿ;R ^k) for everyp < min{n,k}. Finally, we examine in detail the properties of the functionsu BV(;R ^k) such that (u, )= f(u)dx, particularly in the model casef(A)=¦(A)¦.     

Some geometric applications of the beta distribution

Let be the angle between a line and a random k-space in Euclidean n-space R ⁿ. Then the random variable cos² has the beta distribution. This result is applied to show (1) in R ⁿthere are exponentially many (in n) lines going through the origin so that any two of them are nearly perpendicular, (2) any N-point set of diameter d in R ⁿlies between two parallel hyperplanes distance 2d{(log N)/(n-1)}^1/2 apart and (3) an improved version of a lemma of Johnson and Lindenstrauss (1984, Contemp. Math., 26, 189–206). A simple estimate of the area of a spherical cap, and an area-formula for a neighborhood of a great circle on a sphere are also given.     

Inversion of the Weyl integral transform and the radon transform on Rn using generalized wavelets

We invert the Weyl integral transform by means of a generalized continuous wavelet transform on the half line associated with the Bessel operatorL , >–1/2. Next, we use the connection between radial classical wavelets onR ⁿ and generalized wavelets associated with the Bessel operatorL( _n–2)/2 to derive new inversion formulas for the Radon transform onR ⁿ ,n2.     

Completeness and non-speciality of linear series on space curves and deficiency of the corresponding linear series on normalization

Summary Let be a curve ofP ^r (r3) of degree d, C its normalization and , I() a saturated, homogeneous ideal of k[X₀, ...,X _r]. In this paper we show that, if N 0 is an integer such that, for nN, the linear series cut out on by the hypersurfaces of degree n is complete and non-special, then the deficiency of the linear series cut out on C by the hypersurfaces ofA _n,forn>N, is independent ofn and can be explicitly calculated;this is the case, for instance, whenN=d–r+1, and when N=n_i –r–1 (under suitable conditions) if is a component of the complete intersection of r–1 hypersurfaces of degrees n_i.Under financial support from the N.S.E.R.C. of Canada, the italian M.P.I. and the N.A.T.O. Fellowships Scheme Programme.The author wishes to thank R.Lazarsfeld for advice and the Curves Seminar group at Queen's, in particular A. V.Geramita and E.Davis, for fruitful and stimulating discussions on this subject.     

Nonexistence of certain symmetric spherical codes

A spherical 1-codeW is any finite subset of the unit sphere inn dimensionsS ^n–1, for whichd(u, v)1 for everyu, v fromW, uv. A spherical 1-code is symmetric ifuW implies –uW. The best upper bounds in the size of symmetric spherical codes onS ^n–1 were obtained in [1]. Here we obtain the same bounds by a similar method and improve these bounds forn=5, 10, 14 and 22.     

SOME ENDPOINT ESTIMATES FOR COMMUTATORS OF θ-TYPE CALDERON-ZYGMUND OPERATORS

In this note, the authors prove that the commutator generated by θ-type Calderón-Zygmund operator T and a Lipschitz function is bounded from L ^p (R ⁿ ) into (R ⁿ ) and also maps from (R ⁿ ) into BMO (R ⁿ ). Supported by NSFC(10571014), NSFC(10571156), the Doctor Foundation of Jxnu (2443), the Natural Science Foundation of Jiangxi province(2008GZS0051).     

Pyramids in the complex projective plane

We study the critical points of the diameter functional on the n-fold Cartesian product of the complex projective plane C P ² with the Fubini-Study metric. Such critical points arise in the calculation of a metric invariant called the filling radius, and are akin to the critical points of the distance function. We study a special family of such critical points, P _kC P ¹C P ², k=1,2... We show that P _k is a local minimum of by verifying the positivity of the Hessian of (a smooth approximation to) at P _k. For this purpose, we use Shirokov's law of cosines and the holonomy of the normal bundle of C P ¹C P ². We also exhibit a critical point of , given by a subset which is not contained in any totally geodesic submanifold of C P ².     

Developments on MTP2 properties of absolute value multinormal variables with nonzero means

LetX=(X ₁,...,X _n ) have a multivariate normal distribution with mean and covariance matrix. In the case=0, Karlin and Rinott^[6] obtained a necessary and sufficient condition on for |X|=(|X ₁|,...|X _n|) to be MTP₂. In this paper we consider the case0, and give some conditions under which |X| is MTP₂. A necessary and sufficient condition is given for |X| to be TP₂ whenn=2 and0. Some results about the TP₂ stochastic ordering are also given. The results are applied to obtain positive dependence and associated inequalities for multinormal and related distributions.This research is supported by the National Natural Science Foundation of China, the Doctoral Program Foundation of Institute of High Education and a grant of the Chinese Academy of Sciences.     

Polytopes which are orthogonal projections of regular simplexes

We consider the polytopes which are certain orthogonal projections of k-dimensional regular simplexes in k-dimensional Euclidean space R ^k . We call such polytopes -polytopes. Every sufficiently symmetric polytope, such as a regular polytope, a quasi-regular polyhedron, etc., belongs to this class. We denote by P _m,n all n-dimensional -polytopes with m vertices. We show that there is a one-to-one correspondence between the elements of P _m,n and those of P _m,m–n–1 and that this correspondence preserves the symmetry of -polytopes. Using this duality, we determine some of the P _m,n 's. We also show that a -polytope is an orthogonal projection of a cross polytope if and only if it has central symmetry.     

Laguerre Polynomials, Restriction Principle, and Holomorphic Representations of SL(2,R)

The restriction principle is used to implement a realization of the holomorphic representations of SL(2,R) on L ² (R ⁺,t dt) by way of the standard upper half plane realization. The resulting unitary equivalence establishes a correspondence between functions that transform according to the character e^–i(2n++1); under rotations and the Laguerre polynomials. The standard recursion relations amongst Laguerre polynomials are derived from the action of the Lie algebra.     

Perturbation of orthonormal bases inL 2-spaces

The paper improves and generalizes a classical result from Paley and Wiener in their book on Fourier transforms. Paley and Wiener gave conditions on functionsh _n that imply that the sequence (1+h _n (x))e ^inx is a Riesz basis forL ²[–,]. These conditions involve theL ²-norm of the second derivativesh _n . The new results replace the differential operatoryy by more general differential operators inL ²-spaces, in particular, by the Hermite differential operator inL ²(R), ande ^inx by arbitrary orthonormal bases.     

Polynomials with two values

This paper investigates the minimal degree of polynomialsfR[x] that take exactly two values on a given range of integers {0,...n}. We show that thegap, defined asn-deg(f), isO(n ⁵⁴⁸). The maximal gap forn128 is 3. As an application, we obtain a bound on the Fourier degree of symmetric Boolean functions.     

Convergence in distribution and Skorokhod Convergence for the general theory of processes

Summary This paper proves some Skorokhod Convergence Theorems for processes with filtration. Roughly, these are theorems which say that if a family of processes with filtration (X ⁿ , ⁿ ),n, converges in distribution in a suitable sense, then there exists a family of equivalent processes (Y ⁿ , ⁿ ),n, which converges almost surely. The notion of equivalence used is that of adapted distribution, which guarantees that each (X ⁿ , ⁿ ) has the same stochastic properties as (X ⁿ , ⁿ ), with respect to its filtration, such as the martingale property or the Markov property. The appropriate notion of convergence in distribution is convergence in adapted distribution, which is developed in the paper. Fortunately, any tight sequence of processes has a subsequence which converges in adapted distribution. For discrete time processes, (Y ⁿ , ⁿ ),n, and their limit (Y, ) may be taken as all having the same fixed filtration ⁿ =. In the continuous time case, theY ⁿ , ⁿ may require different filtrations ⁿ , which converge to. To handle this, convergence of filtrations is defined and its theory developed.During part of the time this work was in progress, it was supported by an NSERC operating grant, and the author was an NSERC University Research Fellow. The author wishes to thank the Steklov Mathematical Institute of the Soviet Academy of Sciences for its hospitality while the principle research in this paper was being begun, A.N. Shiryaev and P.C. Greenwood, who made the author's visit there possible, and Ján Miná for his hospitality while that research was being finished. We thank the referee who suggested the results in Sect. 12     

Simultaneous reduction of a lattice basis and its reciprocal basis

Given a latticeL we are looking for a basisB=[b ₁, ...b _n ] ofL with the property that bothB and the associated basisB ^*=[b ₁ ^* , ...,b _n ^* ] of the reciprocal latticeL ^* consist of short vectors. For any such basisB with reciprocal basisB ^* let . Håstad and Lagarias [7] show that each latticeL of full rank has a basisB withS(B)exp(c ₁·n ^1/3) for a constantc ₁ independent ofn. We improve this upper bound toS(B)exp(c ₂·(lnn)²) withc ₂ independent ofn.We will also introduce some new kinds of lattice basis reduction and an algorithm to compute one of them. The new algorithm proceeds by reducing the quantity . In combination with an exhaustive search procedure, one obtains an algorithm to compute the shortest vector and a Korkine-Zolotarev reduced basis of a lattice that is efficient in practice for dimension up to 30.     

Dehn twists and pseudo-Anosov diffeomorphisms

Summary We show that it is possible to obtain many pseudo-Anosov diffeomorphisms from Dehn twists. In particular, we generalize a theorem of Long and Morton to obtain that iff is a pseudo-Anosov diffeomorphism of an oriented surface andT is the Dehn twist around the simple closed curve , then the isotopy class ofT ⁿ f contains a pseudo-Anosov diffeomorphism except for at most 7 consecutive values ofn.     

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

Ein beliebig startender SIMPLEX-Algorithmus

Zusammenfassung Die betrachtete Aufgabe der linearen Programmierung lautet: man maximiereC _T x unter den Bedingungenx0,A xd, wobeix,c R ⁿ ,d R ^m ,A=(m×n)-Matrix. Fallsd0, muß man nach herkömmlichen Verfahren zuerst einen zulässigen Ausgangspunkt finden, um den eigentlichen SIMPLEX-Algorithmus starten zu können. Die beschriebene Methode wendet den eigentlichen SIMPLEX-Algorithmus sofort solange auf jeweils noch verletzte Restriktionend _i <0 an, bis entweder alle eingehalten sind, und optimiert schließlich die gegebene Zielfunktion, oder gibt an, daß eine zulässige Lösung der Aufgabe nicht existiert.

---

Consider the linear programming problem: maximizec ^T x s.t.x0,A xd, wherex,cR _n ,d R _m ,A=(m×n)-matrix. Ifd0, the ordinary SIMPLEX-algorithm can only be started after some feasible solution has been found. The above procedure instead takes advantage of the SIMPLEX-algorithm from the very beginning by using violated constraints as objective functions until either all of them hold (which allows subsequent optimization of the original objective function) or it can be stated that there exists no feasible solution at all.

     

Constraint decomposition algorithms in global optimization

Many global optimization problems can be formulated in the form min{c(x, y): x X, y Y, (x, y) Z, y G} where X, Y are polytopes in ^p , ⁿ , respectively, Z is a closed convex set in ^p+n, while G is the complement of an open convex set in ⁿ . The function c: ^p+n is assumed to be linear. Using the fact that the nonconvex constraints depend only upon they-variables, we modify and combine basic global optimization techniques such that some new decomposition methods result which involve global optimization procedures only in ⁿ . Computational experiments show that the resulting algorithms work well for problems with smalln.