Convexity of Nonlinear Image of a Small Ball with Applications to Optimization

Let f: XY be a nonlinear differentiable map, X,Y are Hilbert spaces, B(a,r) is a ball in X with a center a and radius r. Suppose f (x) is Lipschitz in B(a,r) with Lipschitz constant L and f (a) is a surjection: f (a)X=Y; this implies the existence of >0 such that f (a)^* yy, yY. Then, if r,/(2L), the image F=f(B(a,)) of the ball B(a,) is convex. This result has numerous applications in optimization and control. First, duality theory holds for nonconvex mathematical programming problems with extra constraint x–a. Special effective algorithms for such optimization problems can be constructed as well. Second, the reachability set for small power control is convex. This leads to various results in optimal control.     

Weak solutions of the Stokes problem in weighted Sobolev spaces

For n2 we consider the Stokes problem in ⁿ, -u + p=f, -divu=g, in weighted Soboiev spaces H ₆ ^m,r , where the weights are proportional to (1+|x|). We prove the existence of weak solutions for any K, whereK is a discrete set of critical values. Furthermore, we characterize the solutions of the homogeneous problem.This research was supported by the DFG research group Equations of Hydrodynamics, Universities of Bayreuth and Paderborn.     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

Large Deviations of Local Times of Lévy Processes

For X(t) a real-valued symmetric Lévy process, its characteristic function is E(e ^iX(t))=exp(–t()). Assume that is regularly varying at infinity with index 1<2. Let L ^x _t denote the local time of X(t) and L* _t =sup _xR L ^x _t . Estimates are obtained for P(L ⁰ _t y) and P(L* _t y) as y and t fixed.     

Existence and construction of Δ1-splines of class Ck on a three-directional mesh

Let ^* be the equilateral triangulation of the plane and let ₁ ^* be the equilateral triangle formed by four triangles of ^*. We study the space of piecewise polynomial functions in C ^k (R ²) with support ₁ ^*, having a sufficiently high degree n and which are invariant with respect to the group of symmetries of ₁ ^*. Such splines are called ₁ ^*-splines. We first compute the dimension of this space in function of n and k. Then, for any fixed k0, we prove the existence of ₁ ^*-splines of class C ^k and minimal degree, but these splines are not unique. Finally, we describe an algorithm computing the Bernstein–Bézier coefficients of these splines.     

Some inequalities about the covering radius of Reed-Muller codes

Let R(r, m) be the rth order Reed-Muller code of length 2 ^m , and let (r, m) be its covering radius. We prove that if 2 k m - r - 1, then (r + k, m + k) (r, m + 2(k - 1). We also prove that if m - r 4, 2 k m - r - 1, and R(r, m) has a coset with minimal weight (r, m) which does not contain any vector of weight (r, m) + 2, then (r + k, m + k) (r, m) + 2k(. These inequalities improve repeated use of the known result (r + 1, m + 1) (r, m).This work was supported by a grant from the Research Council of Wright State University.     

Eulerian numbers with fractional order parameters

Summary The aim of this paper is to generalize the well-known Eulerian numbers, defined by the recursion relationE(n, k) = (k + 1)E(n – 1, k) + (n – k)E(n – 1, k – 1), to the case thatn is replaced by . It is shown that these Eulerian functionsE(, k), which can also be defined in terms of a generating function, can be represented as a certain sum, as a determinant, or as a fractional Weyl integral. TheE(, k) satisfy recursion formulae, they are monotone ink and, as functions of , are arbitrarily often differentiable. Further, connections with the fractional Stirling numbers of second kind, theS(, k), > 0, introduced by the authors (1989), are discussed. Finally, a certain counterpart of the famous Worpitzky formula is given; it is essentially an approximation ofx in terms of a sum involving theE(, k) and a hypergeometric function.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

An infinite dimensional analogue of the Albeverio-Röckner's theorem on Fukushima's conjecture

LetX be the solution of the SDE:dX _t = (X _t)dB _t +b(X _t)dt, with andb C _b (R) such that >0 for some constant , andB a real Brownian motion. Let be the law ofX onE=C([0, 1],R) andk E* – {0}, whereE* is the topological dual space ofE. Consider the classical form: _k (u, v)=u / kv / kd, whereu andv are smooth functions onE. We prove that, if _k is closable for anyk in a dense subset ofE* and if the smooth functions are contained in the domain of the generator of the closure of _k , must be a constant function.     

Sharp Large Deviation Estimates for the Stochastic Heat Equation

We consider the family {X , 0} of solution to the heat equation on [0,T]×[0,1] perturbed by a small space-time white noise, that is _t X = X +b({X })+({X }) . Then, for a large class of Borelian subsets of the continuous functions on [0,T]×[0,1], we get an asymptotic expansion of P({X }A) as 0. This kind of expansion has been handled for several stochastic systems, ranging from Wiener integrals to diffusion processes.     

Efficiency of Proximal Bundle Methods

We give efficiency estimates for proximal bundle methods for finding f_*min_Xf, where f and X are convex. We show that, for any accuracy <0, these methods find a point x^kX such that f(x^k)–f^* after at most k=O(1/³) objective and subgradient evaluations.     

Contraction of Exterior Powers in Characteristic 2 and the Spin Module

Let K be a field of characteristic 2 and letV be a vector space of dimension 2m over K. Let f be a non-degenerate alternating bilinear form defined on V × V. The symplectic group Sp(2m, K) acts on the exterior powers ^k V for 0 k. 2m There is a contraction map defined on the exterior algebra , which commutes with the Sp(2m, K) action and satisfies ² = 0 and ( ^k V) ^k–1 V We prove that ( ^k V)= ker ^k–1 V except when k=m+2. In the exceptional case, ( ^m+2 V) has codimension 2^m in ker ^m V and we show that the quotient module ker ^m V/ ^m+2 V is a spin module for Sp(2m,K). When K is algebraically closed, we show that this spin module occurs with multiplicity 1 in ^m V and multiplicity 0 in all other components of V.     

Subsets with Restricted Movement

Let G be a finite permutation group on a set with no fixed points in and let m and k be integers with 0 < m < k. For a finite subset of the movement of is defined as move() = max_gG| ^g \ |. Suppose further that G is not a 2-group and that p is the least odd prime dividing |G| and move() m for all k-element subsets of . Then either || k + m or k (7m – 5) / 2, || (9m – 3)/2. Moreover when || > k + m, then move() m for every subset of .     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

The Parameters of Bipartite Q-polynomial Distance-Regular Graphs

Let denote a bipartite distance-regular graph with diameter D 3 and valency k 3. Suppose ₀, ₁, ..., _D is a Q-polynomial ordering of the eigenvalues of . This sequence is known to satisfy the recurrence _{i – 1} – _i + _{i + 1} = 0 (0 > i > D), for some real scalar . Let q denote a complex scalar such that q + q ^–1 = . Bannai and Ito have conjectured that q is real if the diameter D is sufficiently large.We settle this conjecture in the bipartite case by showing that q is real if the diameter D 4. Moreover, if D = 3, then q is not real if and only if ₁ is the second largest eigenvalue and the pair (, k) is one of the following: (1, 3), (1, 4), (1, 5), (1, 6), (2, 4), or (2, 5). We observe that each of these pairs has a unique realization by a known bipartite distance-regular graph of diameter 3.     

Der Beweis eines Satzes von G. Choodnovsky

1. If is a weakly compact cardinal then ( ⁺)( ). 2. If is measurable andU a normal ultrafilter then ( ⁺)(U ).

---

---

Diese Arbeit ist ein Teil der Dissertation des Autors. Teilweise gefördert von der DFG.     

Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen

Ohne Zusammenfassung Zusatz bei der Korrektur: Ein vollständiger und korrekter Beweis für die Entscheidbarkeit der eingangs angeführten Aanderaaschen Klasse ((0, ), (, , ...)) erscheint demnächst im JSL (S.O. Aanderaa/H.R.Lewis: Prefix classes of Krom formulas). Ebendort wird auch die Reduktionstypeneigenschaft für ((0, ), (0, 0, )) und ((0, )), (0, 0, )) nachgewiesen, während ((0, ), (, )) sich als entscheidbar herausgestellt hat (s. E. Börger: Eine entscheidbare Klasse von Kromformeln. ZMLG 19 (1973), 117–120.) Der Kromsche Reduktionstyp konnte mittlerweile einerseits zu ((0, ), (0, 4)) verschärft werden (s. D. Rödding, E. Börger: The undecidability of (0, 4)-formulae with binary disjunctions, vorgetragen auf dem Logic Coll. Bristol 1973, ein abstract erscheint im JSL), andererseits kündigt H.R.Lewis die Reduktionstypeneigenschaft für ((0, ), (0, 1)) an (s. H.R.Lewis: Krom formulas with one dyadic predicate letter. Notices AMS 20, 5 (1973) A-500, abstr. no. 73T-E78.)Dieser Aufsatz geht aus der Dissertation [2] hervor, die dem Fachbereich Mathematik der Mathematisch-Naturwissenschaftlichen Fakultät der Universität Münster im Sommersemester 1971 vorgelegt worden ist. Die Ergebnisse stammen aus dem Wintersemester 1970/71. Eine Ankündigung der hauptsächlichen Resultate ist in den Notices of the American Mathematical Society 19, 2 (1972) A-333 unter der abstract no. * 72T-E24 erschienen.     

Singular perturbations in foliations

Summary We define a constraint system , [0,₀), which is a kind of family of vector fields on a manifold. This is a generalized version of the family of the equations , [0,₀),x ^m ,y ⁿ . Finally, we prove a singular perturbation theorem for the system , [0,₀).Dedicated to Professor Kenichi Shiraiwa on his 60th birthday     

On convergence and summability of Fourier series

. , , –1<<0. .

---

---

The present work was written on the basis of two earlier works received byAnalysis Mathematica on January 16, 1979, and July 20, 1979.     

Sur les équations fonctionnelles auxq-différences

Summary In this paper, we study the convergence of formal power series solutions of functional equations of the formP _k(x)(^[k](x))=(x), where ^[k] (x) denotes thek-th iterate of the function.We obtain results similar to the results of Malgrange and Ramis for formal solutions of differential equations: if(0) = 0, and(0) =q is a nonzero complex number with absolute value less than one then, if(x)=a(n)x ⁿ is a divergent solution, there exists a positive real numbers such that the power seriesa(n)q ^sn(n+1)2 x ⁿ has a finite and nonzero radius of convergence.