title: Class 2 Moufang loops, small Frattini Moufang loops, and code loops

abstract: Let $L$ be a Moufang loop which is centrally nilpotent of class 2. We first show that the nuclearly-derived subloop (normal associator subloop) $L^*$ of $L$ has exponent dividing 6. It follows that $L_p$ (the subloop of $L$ of elements of $p$-power order) is associative for $p>3$. Next, a loop $L$ is said to be a {\it small Frattini Moufang loop}, or SFML, if $L$ has a central subgroup $Z$ of order $p$ such that $C\isom L/Z$ is an elementary abelian $p$-group. $C$ is thus given the structure of what we call a {\it coded vector space}, or CVS. (In the associative/group case, CVS's are either orthogonal spaces, for $p=2$, or symplectic spaces with attached linear forms, for $p>2$.) Our principal result is that every CVS may be obtained from an SFML in this way, and two SFML's are isomorphic in a manner preserving the central subgroup $Z$ if and only if their CVS's are isomorphic up to scalar multiple. Consequently, we obtain the fact that every SFM 2-loop is a code loop, in the sense of Griess, and we also obtain a relatively explicit characterization of isotopy in SFM 3-loops. (This characterization of isotopy is easily extended to Moufang loops of class 2 and exponent 3.) Finally, we sketch a method for constructing any finite Moufang loop which is centrally nilpotent of class 2.


title: Proper and Unit Trapezoid Orders and Graphs

abstract: We show that the class of trapezoid orders in which no trapezoid strictly contains any other trapezoid strictly contains the class of trapezoid orders in which every trapezoid can be drawn with unit area. This is different from the case of interval orders, where the class of proper interval orders is exactly the same as the class of unit interval orders.


title: Asymptotic rigidity of scaling ratios for critical circle mappings

abstract: In this paper we establish $C^2$ a-priori bounds for the scaling ratios of critical circle mappings in a form that gives also a compactness property for the renormalization operator.


title: Symmetry breaking perturbations and strange attractors

abstract: The asymmetrically forced, damped Duffing oscillator is introduced as a prototype model for analyzing the homoclinic tangle of symmetric dissipative systems with \textit{symmetry breaking} disturbances. Even a slight fixed asymmetry in the perturbation may cause a substantial change in the asymptotic behavior of the system, e.g. transitions from two sided to one sided strange attractors as the other parameters are varied. Moreover, slight asymmetries may cause substantial asymmetries in the relative size of the basins of attraction of the unforced nearly symmetric attracting regions. These changes seems to be associated with homoclinic bifurcations. Numerical evidence indicates that \textit{strange attractors} appear near curves corresponding to specific secondary homoclinic bifurcations. These curves are found using analytical perturbational tools.


title: Preud's equations for orthogonal polynomials as discrete Painlev\'e equations

abstract: We consider orthogonal polynomials p_n with respect to an exponential weight function w(x) = exp(-P(x)). The related equations for the recurrence coefficients have been explored by many people, starting essentially with Laguerre [49], in order to study special continued fractions, recurrence relations, and various asymptotic expansions (G. Freud's contribution [28, 56]). Most striking example is n = 2tw_n + w_n(w_n+1 + w_n + w_n-1) for the recurrence coefficients p_n+1 = xp_n - w_np_n-1 of the orthogonal polynomials related to the weight w(x) = exp(-4(tx^3 + x^4)) (notation of [26, pp. 34-36]). This example appears in practically all the references below. The connection with discrete Painlev\'e equations is described here.


title: Archimedean superrigidity of solvable S-arithmetic groups

abstract: Let $\Ga$ be a connected, solvable linear algebraic group over a number field~$K$, let $S$ be a finite set of places of~$K$ that contains all the infinite places, and let $\theints$ be the ring of $S$-integers of~$K$. We define a certain closed subgroup~$\GOS$ of $\Ga_S = \prod_{v \in S} \Ga_{K_v}$ that contains $\Ga_{\theints}$, and prove that $\Ga_{\theints}$ is a superrigid lattice in~$\GOS$, by which we mean that finite-dimensional representations $\alpha\colon \Ga_{\theints} \to \GL_n(\real)$ more-or-less extend to representations of~$\GOS$. The subgroup~$\GOS$ may be a proper subgroup of~$\Ga_S$ for only two reasons. First, it is well known that $\Ga_{\theints}$ is not a lattice in~$\Ga_S$ if $\Ga$ has nontrivial $K$-characters, so one passes to a certain subgroup $\GS$. Second, $\Ga_{\theints}$ may fail to be Zariski dense in $\GS$ in an appropriate sense; in this sense, the subgroup $\GOS$ is the Zariski closure of~$\Ga_{\theints}$ in~$\GS$. Furthermore, we note that a superrigidity theorem for many non-solvable $S$-arithmetic groups can be proved by combining our main theorem with the Margulis Superrigidity Theorem.


title: Cohomology at infinity and the well-rounded retract for general Linear Groups

abstract: Let $\bold G$ be a reductive algebraic group defined over $\Q$, and let $\Gamma$ be an arithmetic subgroup of $\bold G(\Q)$. Let $X$ be the symmetric space for $\bold G(\R)$, and assume $X$ is contractible. Then the cohomology (mod torsion) of the space $X/\Gamma$ is the same as the cohomology of $\Gamma$. In turn, $X/\Gamma$ will have the same cohomology as $W/\Gamma$, if $W$ is a ``spine'' in $X$. This means that $W$ (if it exists) is a deformation retract of $X$ by a $\Gamma$-equivariant deformation retraction, that $W/\Gamma$ is compact, and that $\dim W$ equals the virtual cohomological dimension (vcd) of $\Gamma$. Then $W$ can be given the structure of a cell complex on which $\Gamma$ acts cellularly, and the cohomology of $W/\Gamma$ can be found combinatorially.


title: There may be no nowhere dense ultrafilter

abstract: We show the consistency of ZFC +''there is no NWD-ultrafilter on omega'', which means: for every non principle ultrafilter D on the set of natural numbers, there is a function f from the set of natural numbers to the reals, such that for some nowhere dense set A of reals, the set {n: f(n) in A} is not in D. This answers a question of van Douwen, which was put in more general context by Baumgartner


title: Product preserving functors of infinite dimensional manifolds

abstract: The theory of product preserving functors and Weil functors is partly extended to infinite dimensional manifolds, using the theory of $C^\infty$-algebras.


title: The Jacobi flow

abstract: The geodesic flow on the tangent bundle is the flow of a certain vector field which is called the spray $S:TM\to TTM$. The flow lines of the vector field $\ka_{TM}\o TS:TTM\to TTTM$ project to the Jacobi fields on $TM$. This could be called the Jacobi flow.


title: Type 4 is not computable

abstract: We extend a recent result of McKenzie, and show that it is an undecidable problem to determine if 4 appears in the typeset of a finitely generated, locally finite variety.


title: Fourier coefficients of half-integral weight modular forms modulo ell

abstract: For each prime $\ell$, let $|\cdot|_\ell$ be an extension to $\bar \Q$ of the usual $\ell$-adic absolute value on $\Q$. Suppose $g(z) = \sum_{n=0}^\infty c(n)q^n \in M_{k+\half}(N)$ is an eigenform whose Fourier coefficients are algebraic integers. Under a mild condition, for all but finitely many primes $\ell$ there are infinitely many square-free integers $m$ for which $|c(m)|_\ell = 1$. Consequently we obtain indivisibility results for ``algebraic parts'' of central critical values of modular $L$-functions and class numbers of imaginary quadratic fields. These results partially answer a conjecture of Kolyvagin regarding Tate-Shafarevich groups of modular elliptic curves. Similar results were obtained earlier by Jochnowitz by a completely different method. Our method uses standard facts about Galois representations attached to modular forms, and pleasantly uncovers surprising Kronecker-style congruences for $L$-function values. For example if $\Delta(z)$ is Ramanujan's cusp form and $g(z)=\sum_{n=1}^{\infty}c(n)q^n$ is the cusp form for which $$L(\Delta_D,6)=\fracwithdelims(){\pi}{D}^6\frac{\sqrt{D}}{5!}\frac{< \Delta(z),\Delta(z)>} {< g(z),g(z)>}\cdot c(D)^2,$$ for fundamental discriminants $D>0,$ then for $N\geq 1$ $$\sum_{k=-\infty}^\infty c(N-k^2) \equiv \half \sum_{d|N}(\chi_{-1}(d)+\chi_{-1}(N/d))d^6 \pmod {61}. \tag{0}$$


title: The local Langlands conjecture for GL(n) over a p-adic field, n < p

abstract: Let F be a p-adic field and n a positive integer. The local Langlands conjecture asserts the existence of a bijection between irreducible admissible representations of GL(n,F) and n-dimensional admissible representations of the Weil-Deligne group of F. This bijection is required to satisfy certain natural compatibilities, of which the most important is compatibility with local functional equations (preservation of L and epsilon factors of pairs). It is enough to construct a bijection with these properties between supercuspidal representations of GL(n,F) and n-dimensional irreducible representations of the Weil group of F. In a previous paper, the author constructed a canonical bijection on the etale cohomology of the rigid-analytic coverings of the p-adic upper half space constructed by Drinfeld. (That the map in the previous paper is a bijection was actually proved by Henniart.) However, the compatibility of epsilon factors of pairs was not shown. The present article uses a technique of non-Galois automorphic induction to show that the bijection previously constructed is compatible with epsilon factors of pairs of representations of GL(n,F) and GL(m,F) when n and m are prime to p (the tame case). This implies the local Langlands conjecture in degree < p. It is also shown how the local Langlands conjecture in general would follow from a generalization of Carayol's theorem on the bad reduction of Shimura curves to certain Shimura varieties of higher dimension.


title: Domains with Non-Compact Automorphism Group: A Survey

abstract: We survey results arising from the study of domains in C^n with non-compact automorphism group. Beginning with a well-known characterization of the unit ball, we develop ideas toward a consideration of weakly pseudoconvex (and even non-pseudoconvex) domains with particular emphasis on characterizations of (i) smoothly bounded domains with non-compact automorphism group and (ii) the Levi geometry of boundary orbit accumulation points. Particular attention will be paid to results derived in the past ten years.


title: The Julia-Wolff-Caratheodory theorem in polydisks

abstract: The classical Julia-Wolff-Caratheodory theorem gives a condition ensuring the existence of the non-tangential limit of both a bounded holomorphic function and its derivative at a given boundary point of the unit disk in the complex plane. This theorem has been generalized by Rudin to holomorphic maps between unit balls in C^n, and by the author to holomorphic maps between strongly (pseudo)convex domains. Here we describe Julia-Wolff-Caratheodory theorems for holomorphic maps defined in a polydisk and with image either in the unit disk, or in another polydisk, or in a strongly convex domain. One of main tool for the proof is a general version of Lindelof's principle valid for not necessarily bounded holomorphic functions.


title: Polynomial Diffeomorphisms of C^2: VI. Connectivity of J

abstract: Given a polynomial diffeomorphism f: C^2 -> C^2 there is a set $J_f\subset{\bf C}^2$ which we call the Julia set of f. The set $J_f\subset C^2$ plays the role of the Julia set $J\subset{\bf C}$ for a polynomial map of C. In the study of polynomial maps of C a great deal of attention has been paid to the connectivity of the Julia set. The focus of this paper is to investigate the J-connected/J-disconnected dichotomy in the case of polynomial diffeomorphisms of C^2. The Jacobian determinant of f is constant. We make the standing assumption that $|det\ Df|\le 1$ (this can always be achieved by replacing f by $f^{-1}$ if necessary). The set $J^-$ is the set of points with bounded backward orbits. The set $U^+$ is the set of points with unbounded forward orbits. Let p be a periodic saddle point and let $W^u(p)$ be its unstable manifold. The set $W^u(p)$ will be a Riemann surface conformally equivalent to C. Theorem 1. The following are equivalent: 1. For some periodic saddle point p, some component of $W^u(p)\cap U^+$ is simply connected. 2. The set $J^-\cap U^+$ has a lamination by simply connected leaves so that for any periodic saddle point p each component of $W^u(p)\cap U^+$ is a leaf of this lamination. 3. For any periodic saddle point p, each component of $W^u(p)\cap U^+$ is simply connected. If f satisfies one of these conditions we say that f is unstably connected. Theorem 2. The set J is connected if and only if f is unstably connected. These results imply that we can determine the connectivity of J by considering the forward orbits of points in a single unstable manifold. These results open the door to computer exploration of the topology of two dimensional Julia sets and the connectivity locus in the parameter space.


title: Global regularity of the dbar-Neumann problem: a survey of the L^2-Sobolev theory

abstract: This is a survey article written for the proceedings of the special year in several complex variables, 1995-1996, at the Mathematical Sciences Research Institute in Berkeley.


title: Plurisubharmonic functions and subellipticity of the dbar-Neumann problem on nonsmooth domains

abstract: We show subellipticity of the d-bar Neumann problem on domains with Lipschitz boundary in the presence of plurisubharmonic functions with Hessians of algebraic growth. In particular, a subelliptic estimate holds near a point where the boundary is piecewise smooth of finite type.


title: Fractional Isoperimetric Inequalities and subgroup distortion

abstract: It is shown that there exist infinitely many non-integers $r>2$ such that the Dehn function of some finitely presented group is $\simeq n^r$. For each positive rational number $s$ we construct pairs of finitely presented groups $H\subset G$ such that the distortion of $H$ in $G$ is $\simeq n^s$. And for each $s\ge 1$ we also construct finitely presented groups whose isodiametric function is $\simeq n^s$.


title: The sequential topology on complete Boolean algebras

abstract: We investigate the sequential topology $\tau_s$ on a complete Boolean algebra $B$ determined by algebraically convergent sequences in $B$. We show the role of weak distributivity of $B$ in separation axioms for the sequential topology. The main result is that a necessary and sufficient condition for $B$ to carry a strictly positive Maharam submeasure is that $B$ is ccc and that the space $(B,\tau_s)$ is Hausdorff. We also characterize sequential cardinals.


title: More on forcing iteration

abstract: The preservation theorems for semi-properness, hemi-properness, and pseudo-completeness hold for countable support iterations as well as revised countable support iterations, notwithstanding the fact that the "factor lemma" fails for the countable support versions. Example: The countable support iteration of Namba forcing over a ground model of CH does not add reals. Example: A countable support iteration built from Namba forcing and Cohen forcing, over a ground model of CH, does not collapse omega_1


title: Extensions of $c_0$

abstract: If $X$ is a closed subspace of a Banach space $L$ which embeds into a Banach lattice not containing $\ell_\infty^n$'s uniformly and $L/X$ contains $\ell_\infty^n$'s uniformly, then $X$ cannot have local unconditional structure in the sense of Gordon-Lewis (GL-{\sl l.u.st.}).


title: The Pelczynski property for tight subspaces

abstract: We show that if X is a tight subspace of C(K) then X has the Pelczynski property and X^* is weakly sequentially complete. We apply this result to the space U of uniformly convergent Taylor series on the unit circle and using a minimal amount of Fourier theory prove a theorem of Bourgain, namely that U has the Pelczynski property and U^* is weakly sequentially complete. Using separate methods, we prove U and U^* have the Dunford-Pettis property. Some results concerning pointwise bounded approximation are proved for tight uniform algebras. We use tightness and the Pelczynski property sto make a remark about inner functions on strictly pseudoconvex domains in C^n.


title: Ping-Pong on Negatively Curved Groups

abstract: We prove several generalisations of the ping-pong lemma for negatively curved groups.


title: On $k$-ordered Hamiltonian Graphs

abstract: A Hamiltonian graph $G$ of order $n$ is $k$-ordered, $2\leq k \leq n$, if for every sequence $v_1, v_2, \ldots ,v_k$ of $k$ distinct vertices of $G$, there exists a Hamiltonian cycle that encounters $v_1, v_2, \ldots , v_k$ in this order. In this paper, answering a question of Ng and Schultz, we give a sharp bound for the minimum degree guaranteeing that a graph is a $k$-ordered Hamiltonian graph under some mild restrictions. More precisely, we show that there are $\varepsilon, n_0> 0$ such that if $G$ is a graph of order $n\geq n_0$ with minimum degree at least $\lceil \frac{n}{2} \rceil + \lfloor \frac{k}{2} \rfloor - 1$ and $2\leq k \leq \eps n$, then $G$ is a $k$-ordered Hamiltonian graph. It is also shown that this bound is sharp for every $2\leq k \leq \lfloor \frac{n}{2} \rfloor$.


title: An Algorithmic Version of the Blow-up Lemma

abstract: Recently we have developed a new method in graph theory based on the Regularity Lemma. The method is applied to find certain spanning subgraphs in dense graphs. The other main general tool of the method, beside the Regularity Lemma, is the so-called Blow-up Lemma. This lemma helps to find bounded degree spanning subgraphs in $\varepsilon$-regular graphs. Our original proof of the lemma is not algorithmic, it applies probabilistic methods. In this paper we provide an algorithmic version of the Blow-up Lemma. The desired subgraph, for an $n$-vertex graph, can be found in time $O(nM(n))$, where $M(n)=O(n^{2.376})$ is the time needed to multiply two $n$ by $n$ matrices with 0,1 entries over the integers. We show that the algorithm can be parallelized and implemented in $NC^5$.


title: Contractible open 3-manifolds with free covering translation groups

abstract: This paper concerns the class of contractible open 3-manifolds which are ``locally finite strong end sums'' of eventually end-irreducible Whitehead manifolds. It is shown that whenever a 3-manifold in this class is a covering space of another 3-manifold the group of covering translations must be a free group. It follows that such a 3-manifold cannot cover a closed 3-manifold. For each countable free group a specific uncountable family of irreducible open 3-manifolds is constructed whose fundamental groups are isomorphic to the given group and whose universal covering spaces are in this class and are pairwise non-homeomorphic.


title: R^2-irreducible universal covering spaces of P^2-irreducible open 3-manifolds

abstract: An irreducible open 3-manifold $W$ is {\bf R}$^2$-irreducible if every proper plane in $W$ splits off a halfspace. In this paper it is shown that if such a $W$ is the universal cover of a connected, {\bf P}$^2$-irreducible open 3-manifold $M$ with finitely generated fundamental group, then either $W$ is homeomorphic to {\bf R}$^3$ or the group is a free product of infinite cyclic groups and infinite closed surface groups. Given any such finitely generated group uncountably many $M$ are constructed with that fundamental group such that their universal covers are {\bf R}$^2$-irreducible, are not homeomorphic to {\bf R}$^3$, and are pairwise non-homeomorphic. These results are related to the conjecture that closed, orientable, irreducible, aspherical 3-manifolds are covered by {\bf R}$^3$.


title: Maximal Nilpotent Quotients of 3-Manifold Groups

abstract: We show that if the lower central series of the fundamental group of a closed oriented $3$-manifold stabilizes then the maximal nilpotent quotient is a cyclic group, a quaternion $2$-group cross an odd order cyclic group, or a Heisenberg group. These groups are well known to be precisely the nilpotent fundamental groups of closed oriented $3$-manifolds.


title: Subspace Arrangements over Finite Fields: Cohomological and Enumerative Properties

abstract: The enumeration of points on (or off) the union of some linear or affine subspaces over a finite field is dealt with in combinatorics via the characteristic polynomial and in algebraic geometry via the zeta function. We discuss the basic relations between these two points of view. Counting points is also related to the $\ell$-adic cohomology of the arrangement (as a variety). We describe the eigenvalues of the Frobenius map acting on this cohomology, which corresponds to a finer decomposition of the zeta function. The $\ell$-adic cohomology groups and their decomposition into eigenspaces are shown to be fully determined by combinatorial data. Finally, it is shown that the zeta function is determined by the topology of the corresponding complex variety in some important cases.


title: The number of faces of a simple polytope

abstract: Consider the question: Given integers $k<d<n$, does there exist a simple $d$-polytope with $n$ faces of dimension $k$? We show that there exist numbers $G(d,k)$ and $N(d,k)$ such that for $n> N(d,k)$ the answer is yes if and only if $n\equiv 0\quad \pmod {G(d,k)}$. Furthermore, a formula for $G(d,k)$ is given, showing that e.g. $G(d,k)=1$ if $k\ge \left\lfloor\frac{d+1}{2}\right\rfloor$ or if both $d$ and $k$ are even, and also in some other cases (meaning that all numbers beyond $N(d,k)$ occur as the number of $k$-faces of some simple $d$-polytope). This question has previously been studied only for the case of vertices ($k=0$), where Lee \cite{Le} proved the existence of $N(d,0)$ (with $G(d,0)=1$ or $2$ depending on whether $d$ is even or odd), and Prabhu \cite{P2} showed that $N(d,0) \le cd\sqrt {d}$. We show here that asymptotically the true value of Prabhu's constant is $c=\sqrt2$ if $d$ is even, and $c=1$ if $d$ is odd.


title: Trapezoid Order Classification

abstract: We show the nonequivalence of combinations of several natural geometric restrictions on trapezoid representations of trapezoid orders. Each of the properties unit parallelogram, unit trapezoid and proper parallelogram, unit trapezoid and parallelogram, unit trapezoid, proper parallelogram, proper trapezoid and parallelogram, proper trapezoid, parallelogram, and trapezoid is shown to be distinct from each of the others. Additionally, interval orders are shown to be both unit trapezoid and proper parallelogram orders.


title: Graph-Based Logic and Sketches II: Finite-Product Categories and Equational Logic (Preliminary Report)

abstract: It is shown that the proof theory for sketches and forms provided in Part I of this paper (see http://www.cwru.edu/1/class/mans/math/pub/wells) is strong enough to produce all the theorems of the entailment system for multisorted equational logic provided in Goguen and Meseguer's article ``Completeness of many-sorted equational logic'' (Technical Report CSL-135, SRI International Computer Science Laboratory, 333 Ravenswood Ave., Menlo Park, CA 94025, USA, 1982).


title: Seiberg--Witten Monopoles on Seifert Fibered Spaces

abstract: In this paper, we investigate the Seiberg-Witten gauge theory for Seifert fibered spaces. The monopoles over these three-manifolds, for a particular choice of metric and perturbation, are completely described. Gradient flow lines between monopoles are identified with holomorphic data on an associated ruled surface, and a dimension formula for such flows is calculated.


title: A zero-one law for dynamical properties

abstract: For any countable group $\Gamma$ satisfying the ``weak Rohlin property'', and for any dynamical property, the set of $\Gamma$-actions with that property is either residual or meager. The class of groups with the weak Rohlin property includes each lattice $\integers^{\times{d}}$; indeed, all countable discrete amenable groups. For $\Gamma$ an arbitrary countable group, let $\actsp$ be the set of $\Gamma$-actions on the unit circle $Y$. We establish an Equivalence theorem by showing that a dynamical property is Baire/meager/residual in $\actsp$ if and only if it is Baire/meager/residual in the set of shift-invariant measures on the product space $Y^{\times\Gamma}$.


title: Ergodic properties of Erd\"os measure, the entropy of the goldenshift, and related problems

abstract: We define a two-sided analog of Erd\"os measure on the space of two-sided expansions with respect to the powers of the golden ratio, or, equivalently, the Erd\"os measure on the 2-torus. We construct the transformation (goldenshift) preserving both Erd\"os and Lebesgue measures on $\Bbb T^2$ which is the induced automorphism with respect to the ordinary shift (or the corresponding Fibonacci toral automorphism) and proves to be Bernoulli with respect to both measures in question. This provides a direct way to obtain formulas for the entropy dimension of the Erd\"os measure on the interval, its entropy in the sense of Garsia-Alexander-Zagier and some other results. Besides, we study central measures on the Fibonacci graph, the dynamics of expansions and related questions.


title: Algorithms for classical orthogonal polynomials

abstract: In this article explicit formulas for the recurrence equation p_{n+1}(x) = (A_n x + B_n) p_n(x) - C_n p_{n-1}(x) and the derivative rules sigma(x) p'_n(x) = alpha_n p_{n+1}(x) + beta_n p_n(x) + gamma_n p_{n-1}(x) and sigma(x) p'_n(x) = (alpha_n-tilde x + beta_n-tilde) p_n(x) + gamma_n-tilde p_{n-1}(x) respectively which are valid for the orthogonal polynomial solutions p_n(x) of the differential equation sigma(x) y''(x) + r(x) y'(x) + lambda_n y(x) = 0 of hypergeometric type are developed that depend only on the coefficients sigma(x) and tau(x) which themselves are polynomials w.r.t. x of degree not larger than 2 and 1, respectively. Partial solutions of this problem had beed previously published by Tricomi, and recently by Y\'a\~nez, Dehesa and Nikiforov.


title: On a problem of Koornwinder

abstract: In this note we solve a problem about the rational representablility of hupergeometric terms which represent hypergeometric sums. This problem was proposed by Koornwinder in [4].


title: Club does not imply the existence of a Suslin tree

abstract: We prove that club does not imply the existence of a Suslin tree, so answering a question of I. Juhasz.


title: Superdestructibility: a dual to Laver indestructibility

abstract: After small forcing, any < kappa-closed forcing will destroy the supercompactness, even the strong compactness, of kappa .


title: Generalized Hex and logical characterizations of polynomial space

abstract: We answer a question posed by Makowsky and Pnueli and show that the logic $(\pm\mbox{HEX})^\ast[\mbox{FO}_s]$, where HEX is the operator (i.e., uniform sequence of Lindstr\"om quantifiers) corresponding to the well-known {\bf PSPACE}-complete decision problem Generalized Hex, collapses to the fragment $\mbox{HEX}^1[\mbox{FO}_s]$ and, moreover, that this logic has a particular normal form which results in the problem HEX being complete for {\bf PSPACE} via quantifier-free projections with successor (HEX is the first ``natural'' problem to be shown to have this property). Our proof of this normal form result is remarkably similar to Immerman's original proof that transitive closure logic, $(\pm\mbox{TC})^\ast[\mbox{FO}_s]$, has such a normal form; which is surprising given that $(\pm\mbox{HEX})^\ast[\mbox{FO}_s]$ captures {\bf PSPACE} and $(\pm\mbox{TC})^\ast[\mbox{FO}_s]$ captures {\bf NL}. We also show that $(\pm\mbox{HEX})^\ast[\mbox{FO}]$ does not capture {\bf PSPACE} and that this logic does not have a corresponding normal form.


title: Small generators of number fields

abstract: This is a revised version of ANT-0045. If K is a number field of degree n with discriminant D, if K=Q(a) then H(a)>c(n)|D|^(1/(2n-2)) where H(a) is the height of the minimal polynomial of a. We ask if one can always find a generator a of K such that d(n)|D|^(1/(2n-2))>H(a) holds. The answer is yes for real quadratic fields.


title: Parametrization of local biholomorphisms of real analytic hypersurfaces

abstract: Let $M$ be a real analytic hypersurface in $\bC^N$ which is finitely nondegenerate, a notion that can be viewed as a generalization of Levi nondegenerate, at $p_0\in M$. We show that if $M'$ is another such hypersurface and $p'_0\in M'$, then the set of germs at $p_0$ of biholomorphisms $H$ with $H(M)\subset M'$ and $H(p_0)=p'_0$, equipped with its natural topology, can be naturally embedded as a real analytic submanifold in the complex jet group of $\bC^N$ of the appropriate order. We also show that this submanifold is defined by equations that can be explicitly computed from defining equations of $M$ and $M'$. Thus, $(M,p_0)$ and $(M',p'_0)$ are biholomorphically equivalent if and only if this (infinite) set of equations in the complex jet group has a solution. Another result obtained in this paper is that any invertible formal map $H$ that transforms $(M,p_0)$ to $(M',p'_0)$ is convergent. As a consequence, $(M,p_0)$ and $(M',p'_0)$ are biholomorphically equivalent if and only if they are formally equivalent.


title: A universal Polish G-space

abstract: If G is a Polish group, then there is a Polish G-space X which is universal among Polish G-spaces with respect to continuous G-embeddings.


title: Banach spaces determined by their uniform structures

abstract: Following results of Bourgain and Gorelik we show that the spaces $\ell_p$, $1<p<\infty$, as well as some related spaces have the following uniqueness property: If $X$ is a Banach space uniformly homeomorphic to one of these spaces then it is linearly isomorphic to the same space. We also prove that if a $C(K)$ space is uniformly homeomorphic to $c_0$, then it is isomorphic to $c_0$. We show also that there are Banach spaces which are uniformly homeomorphic to exactly $2$ isomorphically distinct spaces.


title: Metric entropy of homogeneous spaces and Finsler geometry of classical Lie groups

abstract: For a (compact) subset $K$ of a metric space and $\varepsilon > 0$, the {\em covering number} $N(K , \varepsilon )$ is defined as the smallest number of balls of radius $\varepsilon$ whose union covers $K$. Knowledge of the {\em metric entropy}, i.e., the asymptotic behaviour of covering numbers for (families of) metric spaces is important in many areas of mathematics (geometry, functional analysis, probability, coding theory, to name a few). In this paper we give asymptotically correct estimates for covering numbers for a large class of homogeneous spaces of unitary (or orthogonal) groups with respect to some natural metrics, most notably the one induced by the operator norm. This generalizes earlier author's results concerning covering numbers of Grassmann manifolds; the generalization is motivated by applications to noncommutative probability and operator algebras. In the process we give a characterization of geodesics in $U(n)$ (or $SO(m)$) for a class of non-Riemannian metric structures.


title: Confidence regions for means of multivariate normal distributions and a non-symmetric correlation inequality for gaussian measure

abstract: Let $\mu$ be a Gaussian measure (say, on ${\bf R}^n$) and let $K, L \subset {\bf R}^n$ be such that K is convex, $L$ is a "layer" (i.e. $L = \{x : a \leq < x,u > \leq b \}$ for some $a$, $b \in {\bf R}$ and $u \in {\bf R}^n$) and the centers of mass (with respect to $\mu$) of $K$ and $L$ coincide. Then $\mu(K \cap L) \geq \mu(K) \cdot \mu(L)$. This is motivated by the well-known "positive correlation conjecture" for symmetric sets and a related inequality of Sidak concerning confidence regions for means of multivariate normal distributions. The proof uses an apparently hitherto unknown estimate for the (standard) Gaussian cumulative distribution function: $\Phi (x) > 1 - \frac{(8/\pi)^{{1/2}}}{3x + (x^2 +8)^{{1/2}}} e^{-x^2/2}$ (valid for $x > -1$).


title: K-theory for algebras of operators on Banach spaces

abstract: It is proved that, for each pair (m,n) of non-negative integers, there is a Banach space X for which the group K_0(B(X)) is isomorphic to m copies of the integers and the group K_1(B(X)) is isomorphic to n copies of the integers. Along the way we compute the K-groups of all closed ideals of operators contained in the ideal of strictly singular operators, and we derive some results about the existence of splittings of certain short exact sequences.


title: Piles of Cubes, Monotone Path Polytopes and Hyperplane Arrangements

abstract: Monotone path polytopes arise as a special case of the construction of fiber polytopes, introduced by Billera and Sturmfels. A simple example is provided by the permutahedron, which is a monotone path polytope of the standard unit cube. The permutahedron is the zonotope polar to the braid arrangement. We show how the zonotopes polar to the cones of certain deformations of the braid arrangement can be realized as monotone path polytopes. The construction is an extension of that of the permutahedron and yields interesting connections between enumerative combinatorics of hyperplane arrangements and geometry of monotone path polytopes.


title: On a Refined Stark Conjecture for Function Fields

abstract: We prove that a refinement of Stark's Conjecture formulated by Rubin is true up to primes dividing the order of the Galois group, for finite, abelian extensions of function fields over finite fields. We also show that in the case of constant field extensions a statement stronger than Rubin's holds true.


title: Gras-Type Conjectures for Function Fields

abstract: Based on results obtained in a companion paper [MSRI preprint 1997-002], we construct groups of special $S$--units for function fields of characteristic $p>0$, and show that they satisfy Gras--type Conjectures. We use these results in order to give a new proof of Chinburg's $\Omega_3$--Conjecture on the Galois module structure of the group of $S$--units, for cyclic extensions of prime degree of function fields.


title: Polynomial Retracts and the Jacobian Conjecture

abstract: Let $ K[x, y]$ be the polynomial algebra in two variables over a field $K$ of characteristic $0$. A subalgebra $R$ of $K[x, y]$ is called a retract if there is an idempotent homomorphism (a {\it retraction}, or {\it projection}) $\varphi: K[x, y] \to K[x, y]$ such that $\varphi(K[x, y]) = R$. The presence of other, equivalent, definitions of retracts provides several different methods of studying them, and brings together ideas from combinatorial algebra, homological algebra, and algebraic geometry. In this paper, we characterize all the retracts of $ K[x, y]$ up to an automorphism, and give several applications of this characterization, in particular, to the well-known Jacobian conjecture. Notably, we prove that if a polynomial mapping $\varphi$ of $K[x,y]$ has invertible Jacobian matrix {\it and } fixes a non-constant polynomial, then $\varphi$ is an automorphism.


title: Floer homology of Brieskorn homology spheres: solution to Atiyah's problem

abstract: In this paper we answer the question posed by M.~Atiyah and give an explicit formula for Floer homology of Brieskorn homology spheres in terms of their branching sets over the 3--sphere. We further show how Floer homology is related to other invariants of knots and 3--manifolds, among which are the $\bar\mu$--invariant of W.~Neumann and L.~Siebenmann and the Jones polynomial. Essential progress is made in proving the homology cobordism invariance of our own $\nu$--invariant.


title: Geometry and topology of complex hyperbolic and CR-manifolds

abstract: We study geometry, topology and deformation spaces of noncompact complex hyperbolic manifolds (geometrically finite, with variable negative curvature), whose properties make them surprisingly different from real hyperbolic manifolds with constant negative curvature. This study uses an interaction between K\"ahler geometry of the complex hyperbolic space and the contact structure at its infinity (the one-point compactification of the Heisenberg group), in particular an established structural theorem for discrete group actions on nilpotent Lie groups.


title: Metric Entropy of Homogeneous Spaces


title: Retardation of Plateau-Rayleigh Instability: A Distinguishing Characteristic Among Perfectly Wetting Fluids

abstract: We consider a cylindrical film of fluid adhering to a rigid cylinder of fixed radius. The main result is to give the critical (maximum) length for which such a film of given thickness can be stable. The problem is considered both when the cylinder remains stationary and when the fluid and the cylinder are co-rotating at a fixed angular velocity.


title: Hausdorff dimension of boundaries of self-affine tiles in R^n

abstract: We present a new method to calculate the Hausdorff dimension of a certain class of fractals: boundaries of self-affine tiles. Among the interesting aspects are that even if the affine contraction underlying the iterated function system is not conjugated to a similarity we obtain an upper- and lower-bounds for its Hausdorff dimension. In fact, we obtain the exact value for the dimension if the moduli of the eigenvalues of the underlying affine contraction are all equal (this includes Jordan blocks). The tiles we discuss play an important role in the theory of wavelets. We calculate the dimension for a number of examples.


title: Rigidity properties of locally scaling fractals

abstract: Local scaling of a set means that in a neighborhood of a point the structure of the set can be mapped into a finer scale structure of the set. These scaling transformations are compact sets of locally affine (that is: with uniformly $\alpha$-H\"older continuous derivatives) contractions. In this setting, without any assumption on the spacing of these contractions such as the open set condition, we show that the measure of the set is an upper semi-continuous of the scaling transformation in the $C^0$-topology. With a restriction on the 'non-conformality' (see below) the Hausdorff dimension is lower semi-continous function in the $C^{1}$-topology. We include some examples to show that neither of these notions is continuous.


title: Pruning fronts and the formation of horseshoes

abstract: Let f:E -> E be a homeomorphism of the plane E. We define open sets P, called {\em pruning fronts} after the work of Cvitanovi\'c, for which it is possible to construct an isotopy H: E x [0,1] -> E with open support contained in the union of f^{n}(P), such that H(*,0)=f(*) and H(*,1)=f_P(*), where f_P is a homeomorphism under which every point of P is wandering. Applying this construction with f being Smale's horseshoe, it is possible to obtain an uncountable family of homeomorphisms, depending on infinitely many parameters, going from trivial to chaotic dynamic behaviour. This family is a 2-dimensional analog of a 1-dimensional universal family.


title: Prehomogeneous vector spaces and field extensions III

abstract: In this paper, we determine the rational orbit decomposition for two prehomogeneous vector spaces associated with the simple group of type G_2.


title: Random graphs in the monadic theory of order

abstract: We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line).


title: Closures in $\aleph_0$-categorical bilinear maps

abstract: Alternating bilinear maps with few relations allow to define a combinatorial closure similarly as in [2]. For the $\aleph_0$-categorical case we show that this closure is part of the algebraic closure.


title: Blow-analytic retraction onto the central fibre

abstract: Let X be a complex analytic space and let f:X -> C be a proper complex analytic function with nonsingular generic fibres. By adapting the blowanalytic methods of Kuo we construct a retraction of a neighbourhood of the central fibre f^{-1}(0) onto f^{-1}(0). Our retraction is defined by the flow of a real analytic vector field on an oriented real analytic blow-up of X. Then we describe in terms of this blow-up the associated specialization map and local Milnor fibrations. The method also works in real analytic category.


title: No directed fractal percolation in zero area

abstract: We show that fractal (or "Mandelbrot") percolation in two dimensions produces a set containing no directed paths, when the set produced has zero area. This improves a similar result by the first author in the case of constant retention probabilities to the case of retention probabilities approaching 1.


title: Markov chains in a field of traps

abstract: A general criterion is given for when a Markov chain trapped with probability p(x) in state x will be almost surely trapped. The quenched (state x is a trap forever with probability p(x)) and annealed (state x traps with probability p(x) on each visit) problems are shown to be equivalent.


title: Vertex-reinfoced random walk on Z visits finitely many states

abstract: Vertex-reinforced random walk is defined in Pemantle's (1988) thesis; it is a random walk that is biased to visit sites it has already visited a lot. We show that this reinforcement scheme, in contrast to the scheme of edge-reinforcement, causes random walk on a line to get trapped in a finite set.


title: Sets avoided by Brownian motion

abstract: Any fixed cylinder is hit almost surely by a 3-dimensional Brownian motion, but is there a random cylinder that is in the complement? We answer this for cylinders, and then replacing a cylinder with a more general set.


title: First passage percolation and a model for competing spatial growth

abstract: We generalize Richardson's model by starting with two sites of different colors and giving each new site the color of the site that spawned it. We show that co-existence is possible.


title: Paths with exponential intersection tails and oriented percolation

abstract: We show that oriented percolation occurs whenever a condition is satisfied called "exponential intersection tails". This condition says that a measure on paths exists for which the probability of two independent paths intersecting in more than k sites is exponentially small in k.


title: The probability that Brownian motion almost covers a line

abstract: Lower and upper estimates are given for the probability that the epsilon-enlargement of planar Brownian motion to time 1 (the epsilon sausage) contains a unit line segment. The estimates imply that Brownian motion to time 1 itself contains no line segment.


title: The Frobenius and monodromy operators for curves and abelian varieties

abstract: In this paper, we give explicit descriptions of Hyodo and Kato's Frobenius and Monodromy operators on the first $p$-adic de Rham cohomology groups of curves and Abelian varieties with semi-stable reduction over local fields of mixed characteristic. This paper was motivated by the first author's paper "A $p$-adic Shimura isomorphism and periods of modular forms," where conjectural definitions of these operators for curves with semi-stable reduction were given.


title: Positivity conditions for bihomogeneous polynomials

abstract: In this paper we continue our study of a complex variables version of Hilbert's seventeenth problem by generalizing some of the results from [CD]. Given a bihomogeneous polynomial $f$ of several complex variables that is positive away from the origin, we proved that there is an integer $d$ so that $||z||^{2d} f(z,{\overline z})$ is the squared norm of a holomorphic mapping. Thus, although $f$ may not itself be a squared norm, it must be the quotient of squared norms of holomorphic homogeneous polynomial mappings. The proof required some operator theory on the unit ball. In the present paper we prove that we can replace the squared Euclidean norm by squared norms arising from an orthonormal basis for the space of homogeneous polynomials on any bounded circled pseudoconvex domain of finite type. To do so we prove a compactness result for an integral operator on such domains related to the Bergman kernel function.


title: Solvable Baumslag-Solitar Groups Are Not Almost Convex

abstract: The arguments of Cannon, Floyd, Grayson and Thurston showing that solve geometry groups are not almost convex also show that solvable Baumslag-Solitar groups are not almost convex.


title: Regular geodesic normal forms in virtually abelian groups

abstract: Cannon has given an example of a virtually abelian group and a generating set where the full language of geodesics is not regular. We describe a virtually abelian group and a generating set so that no regular language of geodesics surjects to the group.


title: Countable support iterations and large continuum

abstract: We prove that any countable support iteration formed with posets with $\omega_2$-p.i.c.\ has $\omega_2$-c.c., assuming CH in the ground model and assuming also that $\omega_1$ is not collapsed. This improves earlier results of Shelah by removing the restriction on the length of the iteration. Thus, we solve the problem of obtaining a large continuum via such forcing iterations.


title: $\square_\kappa^{<\omega}$ holds in $L[{\vec E}]$

abstract: Square-kappa-finite, the finite family version of weak square, holds at all cardinals kappa in the Mitchell-Steel inner models.


title: The maximality of the core model

abstract: If T is an iteration tree on K and F is a countably certified extender that coheres with the final model of T, then F is on the extender sequence of the final model of T. Several applications of maximality are proved, including: o K computes successors of weakly compact cardinals correctly. o K^c is an iterate of K. o (with Mitchell) If alpha is a cardinal > aleph_1, then K-restriction-alpha is universal for mice of height alpha. Other results in this paper, when combined with work of Woodin, imply: o If square-kappa-finite fails and kappa is a singular, strong limit cardinal, then Inductive Determinacy holds. o If square-kappa-finite fails and kappa is a weakly compact cardinal, then L(R)-determinacy holds.


title: The covering lemma up to a Woodin cardinal

abstract: A cardinal kappa is countably closed if mu^omega < kappa whenever mu < kappa. Assume that there is no inner model with a Woodin cardinal and that every set has a sharp. Let K be the core model. Assume that kappa is a countably closed cardinal and that alpha is a successor cardinal of K with kappa < alpha < kappa^+. Then cf( alpha ) = kappa. In particular, K computes successors of countably closed singular cardinals correctly. (The hypothesis of countable closure is not required; see "Weak covering without countable closure", W. J. Mitchell and E. Schimmerling, Math. Res. Lett., Vol. 2, No. 5, Sept. 1995.)


title: The Jensen covering property

abstract: An optimal extension of the Jensen covering lemma, within the limits imposed by Prikry forcing, is proved. If L[E] is an "iterable" weasel with no measurable cardinals, then either L[E] has "indiscernibles", or every uncountable set of ordinals is contained in a set in L[E] of the same cardinality. (The terms "iterable" and "indiscernibles" are made precise in the paper.) Most importantly, there is no hypothesis explicitly limiting the large cardinals which are consistent in L[E].


title: Coloring ordinals by reals

abstract: We introduce several new set-theoretic axioms formulated in terms of coloring of ordinals by reals. We show that these axioms generalize the axioms considered by I.Juhasz, L.Soukup and Z.Szentmiklossy, and give a class of p.o.s including Cohen p.o.-sets which force the axioms. In appearance these axioms are somewhat similar to OCA but it appears that they are inconsistent with OCA.


title: Uniform embeddings, homeomorphisms and quotient maps between Banach spaces (A short survey)

abstract: This is a survey of the area mentioned in the title.


title: Second derivative test for isometric embeddings in $L_p$

abstract: An old problem of P. Levy is to characterize those Banach spaces which embed isometrically in $L_p.$ We show a new criterion in terms of the second derivative of the norm. As an application, we show that if $M$ is a twice differentiable Orlicz function with $M'(0)=M''(0)=0$ then the $n$-dimensional Orlicz space $\ell_M^n,\ n\ge 3,$ does not embed isometrically in $L_p$ with $0<p\le 2.$ These results generalize and clear up the recent solution to the 1938 Schoenberg's problem on positive definite functions.


title: Approximation of Lipschitz functions by $\Delta$-convex functions in Banach spaces

abstract: In this paper we give some results about the approximation of a Lipschitz function on a Banach space by means of $\Delta$-convex functions. In particular, we prove that the density of $\Delta$-convex functions in the set of Lipschitz functions for the topology of uniform convergence on bounded sets characterizes the superreflexivity of the Banach space. We also show that Lipschitz functions on superreflexive Banach spaces are uniform limits on the whole space of $\Delta$-convex functions.


title: M-ideals of compact operators into $\ell_p$

abstract: We show for $2\le p<\infty$ and subspaces $X$ of quotients of $L_{p}$ with a $1$-unconditional finite-dimensional Schauder decomposition that $K(X,\ell_{p})$ is an $M$-ideal in $L(X,\ell_{p})$.


title: One-complemented subspaces of real sequence spaces

abstract: Characterizations are given for 1-complemented hyperplanes of strictly monotone real Lorentz spaces and 1-complemented finite codimensional subspaces (which contain at least one basis element) of real Orlicz spaces equipped with either Luxemburg or Orlicz norm.


title: Hilbert transform associated with finite maximal subdiagonal algebras

abstract: Let $M$ be a von Neumann algebra with a faithful normal finite trace $t$, and $H^\infty$ be a finite, maximal, subdiagonal of $M$. Fundamental theorems on conjugate functions for weak* Dirichlet algebras are shown to be a bounded linear map from $L^p(M,t)$ into $L^p(M,t)$ for $1<p<\infty$, and to be a continuous linear map from $L^1(M,t)$ into $L^{1,\infty}(M,t)$. We also obtain that if a positive operator $a$ is such that $a\log^{+}a \in L^1(M,t)$, then its conjugate belongs to $L^1(M,t)$.


title: The near Radon-Nikodym property in Lebesgue-Bochner function spaces

abstract: Let $X$ be a Banach space $E$ a K\"othe function space that does not contain $c_0$. It is shown that the vector valued function space $E(X)$ has the Near Radon Nikodym property if and only if $X$ does.


title: Factorization of operators on $C^*$-algebras

abstract: Let $A$ be a $C^*$-algebra. It is shown that every absolutely summing operator from $A$ into $\ell_2$ factors through a Hilbert space operator that belongs to the 4-Schatten- von Neumann class. We also provide finite dimensinal examples that show that one can not improve the 4-Schatten-von Neumann class to $p$-Schatten von Neumann class for any $p<4$. As application, we prove that there exists a modulus of capacity $\epsilon \to N(\epsilon)$ so that if $A$ is a $C^*$-algebra and $T \in \Pi_1(A,\ell_2)$ with $\pi_1(T)\leq 1$, then for every $\epsilon >0$, the $\epsilon$-capacity of the image of the unit ball of $A$ under $T$ does not exceed $N(\epsilon)$. This aswers positively a question raised by Pe\l czynski.


title: Some Remarks on Real and Complex Output Feedback

abstract: We provide some new necessary and sufficient conditions which guarantee arbitrary pole placement of a particular linear system over the complex numbers. We exhibit a non-trivial real linear system which is not controllable by real static output feedback and discuss a conjecture from algebraic geometry concerning the existence of real linear systems for which all static feedback laws are real.


title: The Tutte dichromate and Whitney homology of matroids

abstract: We consider a specialization $Y_M(q,t)$ of the Tutte polynomial of a matroid $M$ which is inspired by analogy with the Potts model from statistical mechanics. The only information lost in this specialization is the number of loops of $M$. We show that the coefficients of $Y_M(1-p,t)$ are very simply related to the ranks of the Whitney homology groups of the opposite partial orders of the independent set complexes of the duals of the truncations of $M$. In particular, we obtain a new homological interpretation for the coefficients of the characteristic polynomial of a matroid.


title: Prehomogeneous vector spaces and ergodic theory III

abstract: Let H_1=SL(5), H_2=SL(3), H=H_1 \times H_2. It is known that (G,V) is a prehomogeneous vector space (see [22], [26], [25], for the definition of prehomogeneous vector spaces). A non-constant polynomial \delta(x) on V is called a relative invariant polynomial if there exists a character \chi such that \delta(gx)=\chi(g)\delta(x). Such \delta(x) exists for our case and is essentially unique. So we define V^{ss}={x in V such that \delta(x) is not equal to 0}. For x in V_R^{ss}, let H_{x R+}^0 be the connected component of 1 in classical topology of the stabilizer H_{x R}. We will prove that if x in V_R^ss is "sufficiently irrational", H_{x R+}^0 H_Z is dense in H_R.


title: Some New Applications of Toric Geometry

abstract: This paper reexamines univariate reduction from a toric geometric point of view. We begin by constructing a binomial variant of the $u$-resultant and then retailor the generalized characteristic polynomial to fully exploit sparsity in the monomial structure of any given polynomial system. We thus obtain a fast new algorithm for univariate reduction and a better understanding of the underlying projections. As a corollary, we show that a refinement of Hilbert's Tenth Problem is decidable within single-exponential time. We also show how certain multisymmetric functions of the roots of polynomial systems can be calculated with sparse resultants.


title: Toric Generalized Characteristic Polynomials

abstract: We illustrate an efficient new method for handling polynomial systems with degenerate solution sets. In particular, a corollary of our techniques is a new algorithm to find an isolated point in every excess component of the zero set (over an algebraically closed field) of any $n$ by $n$ system of polynomial equations. Since we use the sparse resultant, we thus obtain complexity bounds (for converting any input polynomial system into a multilinear factorization problem) which are close to cubic in the degree of the underlying variety -- significantly better than previous bounds which were pseudo-polynomial in the classical B\'ezout bound. By carefully taking into account the underlying toric geometry, we are also able to improve the reliability of certain sparse resultant based algorithms for polynomial system solving.


title: Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps

abstract: Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating function $H(x)$ of all 1342-avoiding permutations of length $n$ as well as an {\em exact} formula for their number $S_n(1342)$. While achieving this, we bijectively prove that the number of indecomposable 1342-avoiding permutations of length $n$ equals that of labeled plane trees of a certain type on $n$ vertices recently enumerated by Cori, Jacquard and Schaeffer, which is in turn known to be equal to the number of rooted bicubic maps enumerated by Tutte in 1963. Moreover, $H(x)$ turns out to be algebraic, proving the first nonmonotonic, longer-than-three instance of a conjecture of Zeilberger and Noonan. We also prove that $\sqrt[n]{S_n(1342)}$ converges to 8, so in particular, $lim_{n\rightarrow \infty}(S_n(1342)/S_n(1234))=0$.


title: A Simple Bijection for the Regions of the Shi Arrangement of Hyperplanes

abstract: The Shi arrangement ${\mathcal S}_n$ is the arrangement of affine hyperplanes in ${\mathbb R}^n$ of the form $x_i - x_j = 0$ or $1$, for $1 \leq i < j \leq n$. It dissects ${\mathbb R}^n$ into $(n+1)^{n-1}$ regions, as was first proved by Shi. We give a simple bijective proof of this result. Our bijection generalizes easily to any subarrangement of ${\mathcal S}_n$ containing the hyperplanes $x_i - x_j = 0$ and to the extended Shi arrangements.


title: Stably non-synchronizable maps of the plane

abstract: Pecora and Carroll presented a notion of synchronization where an (n-1)-dimensional nonautonomous system is constructed from a given $n$-dimensional dynamical system by imposing the evolution of one coordinate. They noticed that the resulting dynamics may be contracting even if the original dynamics are not. It is easy to construct flows or maps such that no coordinate has synchronizing properties, but this cannot be done in an open set of linear maps or flows in $\R^n$, $n\geq 2$. In this paper we give examples of real analytic homeomorphisms of $\R^2$ such that the non-synchronizability is stable in the sense that in a full $C^0$ neighborhood of the given map, no homeomorphism is synchronizable.


title: Automorphism groups with cyclic commutator subgroup and Hamilton cycles

abstract: It has been shown that there is a Hamilton cycle in every connected Cayley graph on each group G whose commutator subgroup is cyclic of prime-power order. This paper considers connected, vertex-transitive graphs X of order at least 3 where the automorphism group of X contains a transitive subgroup G whose commutator subgroup is cyclic of prime-power order. We show that of these graphs, only the Petersen graph is not hamiltonian.


title: On non-Hamiltonian circulant digraphs of outdegree three

abstract: We construct infinitely many connected, circulant digraphs of outdegree three that have no hamiltonian circuit. All of our examples have an even number of vertices, and our examples are of two types: either every vertex in the digraph is adjacent to two diametrically opposite vertices, or every vertex is adjacent to the vertex diametrically opposite to itself.


title: On the number of elementary submodels of an unsuperstable homogeneous structure

abstract: We show that if M is a stable unsuperstable homogeneous structure, then for most kappa < |M|, the number of elementary submodels of M of power kappa is 2^kappa .


title: Multiplicity of a zero of an analytic function on a trajectory of a vector field

abstract: Let P(x) be a germ at the origin of an analytic function in C^n, where x = (x_1,..., x_n), and let \xi = \xi_1(x) d/dx_1 + ... + \xi_n(x) d/dx_n be a germ at the origin of an analytic vector field. Suppose that \xi(0) != 0, and let \gamma be a trajectory of \xi through the origin. Suppose that P|_\gamma /\equiv 0, and let \mu(P|_\gamma) be the multiplicity of a zero of P|_\gamma at the origin. Let \xi P = \xi_1 dP/dx_1 + ... + \xi_n dP/dx_n be derivative of P in the direction of \xi, and let \xi^kP be the kth iteration of this derivative. We give a formula (Theorem 1) for \mu(P|_\gamma) in terms of the Euler characteristic of the Milnor fibers defined by a deformation of P, \xi P, ..., \xi^{n-1}P . For a polynomial P of degree p and a vector field \xi with polynomial coefficients of degree q, this allows one to compute \mu(P|_\gamma) in purely algebraic terms (Theorem 2), and to give an estimate (Theorem 3) for \mu(P|_\gamma) in terms of n, p, q, single exponential in n and polynomial in p and q. This estimate improves previous results which were doubly exponential in n.


title: Rigid analytic flatificators

abstract: Let K be an algebraically closed field endowed with a complete non-archimedean norm. Let f:Y -> X be a map of K-affinoid varieties. We prove that for each point x in X, either f is flat at x, or there exists, at least locally around x, a maximal locally closed analytic subvariety Z in X containing x, such that the base change f^{-1}(Z) -> Z is flat at x, and, moreover, g^{-1}(Z) has again this property in any point of the fibre of x after base change over an arbitrary map g:X' -> X of affinoid varieties. If we take the local blowing up \pi:X-tilde -> X with this centre Z, then the fibre with respect to the strict transform f-tilde of f under \pi, of any point of X-tilde lying above x, has grown strictly smaller. Among the corollaries to these results we quote, that flatness in rigid analytic geometry is local in the source; that flatness over a reduced quasi-compact rigid analytic variety can be tested by surjective families; that an inclusion of affinoid domains is flat in a point, if it is unramified in that point.


title: Groups acting on CAT(0) cube complexes

abstract: We show that groups satisfying Kazhdan's property (T) have no unbounded actions on finite dimensional CAT(0) cube complexes, and deduce that there is a locally CAT(-1) Riemannian manifold which is not homotopy equivalent to any finite dimensional, locally CAT(0) cube complex.


title: Real fields and repeated radical extensions

abstract: The main result of this paper is that if E is a field extension of finite odd degree over a real field Q, and if E is a repeated radical extension of Q, then every intermediate field is also a repeated radical extension of Q. This paper also contains a number of other results about repeated radical extensions.


title: Irreducible character degrees and normal subgroups

abstract: Let N be a normal subgroup of a finite group G and consider the set cd(G|N) of degrees of irreducible characters of G whose kernels do not contain N. A number of theorems are proved relating the set cd(G|N) to the structure of N. For example, if N is solvable, its derived length is bounded above by a function of |cd(G|N)|. Also, if |cd(G|N)| is at most 2, then N is solvable and its derived length is at most |cd(G|N)|. If G is solvable and |cd(G|N)| = 3, then the derived length of N is at most 3.


title: Buildings, group extensions and the cohomology of congruence subgroups

abstract: We use buildings and group extensions to compute lower bounds on the top Betti numbers for the cohomology of the level p congruence subgroups of SL(3,Z) and Sp(4,Z).


title: Maximal subgroups of direct products

abstract: We determine all maximal subgroups of the direct product $\sc G^n$ of $\sc n$ copies of a group~$\sc G$. If $\sc G$ is finite, we show that the number of maximal subgroups of~$\sc G^n$ is a quadratic function of~$\sc n$ if $\sc G$ is perfect, but grows exponentially otherwise. We~deduce a theorem of Wiegold about the growth behaviour of the number of generators of~$\sc G^n$.


title: Duality and Local Group Cohomology

abstract: Recently, Meierfrankenfeld has published three theorems on the cohomology of a finitary module. They cover the local determination of complete reducibility; the local splitting of group extensions; and the representation of locally split extensions in the double dual. In this note we derive all three by combining a certain duality between homology and cohomology with the continuity of homology.


title: Solovay-type characterizations for forcing-algebras

abstract: We give characterizations for the (in ZFC unprovable) sentences ``Every $\Sb{1}{2}$--set is measurable" and ``Every $\Db{1}{2}$--set is measurable" for various notions of measurability derived from well--known forcing partial orderings.


title: Changing the heights of automorphism towers

abstract: If $G$ is a centreless group, then $\tau(G)$ denotes the height of the automorphism tower of $G$. We prove that it is consistent that for every cardinal $\lambda$ and every ordinal $\alpha < \lambda$, there exists a centreless group $G$ such that (a) $\tau(G) = \alpha$; and (b) if $\beta$ is any ordinal such that $1 \leq \beta < \lambda$, then there exists a notion of forcing $P$, which preserves cofinalities and cardinalities, such that $\tau(G) = \beta$ in the corresponding generic extension $V^{P}$.


title: Absolutely continuous spectrum of perturbed Stark operators

abstract: We prove new results on the stability of the absolutely continuous spectrum for perturbed Stark operators with decaying or satisfying certain smoothness assumption perturbation. We show that the absolutely continuous spectrum of the Stark operator is stable if the perturbing potential decays at the rate $(1+x)^{-\frac{1}{3}-\epsilon}$ or if it is continuously differentiable with derivative from the H\"older space $C_{\alpha}(R),$ with any $\alpha>0.$


title: On two-generator satellite knots

abstract: Techniques are introduced which determine the geometric structure of non-simple two-generator $3$-manifolds from purely algebraic data. As an application, the satellite knots in the $3$-sphere with a two-generator presentation in which at least one generator is represented by a meridian for the knot are classified.


title: On invariants and homology of spaces of knots in arbitrary manifolds

abstract: Finite-order invariants of knots in arbitrary 3-manifolds (including non-orientable ones) are constructed and studied by methods of the topology of discriminant sets. Obstructions to the integrability of admissible weight systems to well-defined knot invariants are identified as 1-dimensional cohomology classes of generalized loop spaces of the manifold. Unlike the case of the 3-sphere, these obstructions can be non-trivial and provide invariants of the manifold itself. The corresponding algebraic machinery allows us to obtain on the level of the ``abstract nonsense'' some of results and problems of the theory, and to extract from other the essential topological part.


title: Sierksma's Dutch Cheese Problem

abstract: Consider partitions, of a cardinality $(q-1)(d+1)+1$ generic subset of euclidean $d$-space, into $q$ parts whose convex hulls have a nonempty intersection. We show that if these partitions are counted with appropriate signs $\pm 1$ then the answer is always $((q-1)!)^d$. Also some other related results are given.


title: A Combinatorial proof of a result of Hetyei and Reiner on Foata-Strehl type permutation trees

abstract: We give a combinatorial proof of the result of Hetyei and Reiner that there are exactly $n!/3$ permutations of length $n$ in the minmax tree representation of which the $i$th node is a leaf. We also prove the new result that the number of $n$-permutations in which this node has one child is $n!/3$ as well, implying that the same holds for those in which this node has two children.


title: Explicit irreducible representations of the Iwahori-Hecke algebra of type $F_4$

abstract: A general method for computing irreducible representations of Weyl groups and Iwahori-Hecke algebras was introduced earlier by the first author. The representations of the algebras of types $A_n$, $B_n$, $D_n$ and $G_2$ were computed and it is the purpose of this paper to extend these computations to $F_4$. The main goal here is to compute irreducible representations of the Iwahori-Hecke algebra of type $F_4$ by only using information in the character table of the Weyl group.


title: On a computer recognition of 3-manifolds

abstract: We describe theoretical backgrounds for a computer program that recognizes all closed orientable 3-manifolds up to complexity 8. The program can treat also not necessarily closed 3-manifolds of bigger complexities, but here some unrecognizable (by the program) 3-manifolds may occur.


title: A Suspension Lemma for Bounded Posets

abstract: Let $P$ and $Q$ be bounded posets. In this note, a lemma is introduced that provides a set of sufficient conditions for the proper part of $P$ being homotopy equivalent to the suspension of the proper part of~$Q$. An application of this lemma is a unified proof of the sphericity of the higher Bruhat orders under both inclusion order (a known proved earlier by Ziegler) and single step inclusion order (which was not previously known).


title: Ergodicity of hard spheres in a box

abstract: We prove that the system of two hard balls in a $\nu$-dimensional ($\nu\ge2$) rectangular box is ergodic and, therefore, actually it is a Bernoulli flow.


title: An analytic solar model physical principles and mathematical structure

abstract: The physical principles and the mathematical structure involved in deriving an analytical representation of the internal structure of the sun are discussed. For a two-parameter family of a non-linear matter density distribution, the run of mass, pressure, temperature, and luminosity throughout the sun are expressed in terms of Gauss' hypergeometric function. The system of differential equations governing hydrostatic equilibrium and energy conservation for the sun generates another field of application of special functions.


title: On the zeros of the Hahn-Exton q-Bessel function and associated q-Lommel polynomials

abstract: For the Bessel function \begin{equation} \label{bessel} J_{\nu}(z) = \sum\limits_{k=0}^{\infty} \frac{(-1)^k \left( \frac{z}{2} \right)^{\nu+2k}}{k! \Gamma(\nu+1+k)} \end{equation} there exist several $q$-analogues. The oldest $q$-analogues of the Bessel function were introduced by F. H. Jackson at the beginning of this century, see M. E. H. Ismail \cite{Is1} for the appropriate references. Another $q$-analogue of the Bessel function has been introduced by W. Hahn in a special case and by H. Exton in full generality, see R. F. Swarttouw \cite{Sw1} for a historic overview. Here we concentrate on properties of the Hahn-Exton $q$-Bessel function and in particular on its zeros and the associated $q$-Lommel polynomials.


title: A package on orthogonal polynomials and special functions

abstract: In many applications (hupergeometric-type) special functions like orthogonal polynomials are needed. For example in more than 50% of the published solutions for the (application-oriented) questions in the "Problems Section" of SIAM Review special functions occur. In this article the Mathematica package SpecialFunction which can be obtained from the URL http://www.zib.de/koepf is introduced [15]. Algorithms to convert between power series representations and their generating functions is the main topic of this package {[8]-[15]}, extending the previous package PowerSeries [12]. Moreover the package automatically finds differential and recurrence equations {[13]-[14]} for expressions and for sums (the latter using Zeilberger's algorithm {[23], [18], [13\}. As an application the fast computation of polynomial approximations of solutions of linear differential equations with polynomial coefficients is presented. This is the asymptotically fastest known algorithm for series computations, and it is much faster than Mathematica's builtin Series command if applicable. Many more applications are considered. Finally the package includes implementations supporting the efficient computation of classical continuous and discrete orthogonal polynomials.


title: Representations of orthogonal polynomials

abstract: Zeilberger's algorithm provides a method to compute recurrence and differential equations from given hypergeometric series representations, and an adaption of Almquist and Zeilberger computes recurrence and differential equations for hyperexponential integrals. Further versions of this algorithm allow the computation of recurrence and differential equations from Rodrigues type formulas and from generating functions. In particular, these algorithms can be used to compute the differential/difference and recurrence equations for the classical continuous and discrete orthogonal polynomials from their hypergeometric representations, and from their Rodrigues rperesentations and generating functions. In recent work, we used an explicit formula for the recurrence equation of families of classical continuous and discrete orthogonal polynomials, in terms of the coefficients of their differential/difference equations, to give an algorithm to identify the polynomial system from a given recurrence equation. In this article we extend these results by presenting a collection of algorithms with which any of the conversions between the differential/difference equation, the hupergeometric representation, and the recurrence equation is possible. The main technique is again to use texplicit formulas for structural identities of the given polynomial systems.


title: Cardinal invariants of ultrapoducts of Boolean algebras

abstract: We deal with some of problems posed by Monk and related to cardinal invariant of ultraproducts of Boolean algebras. We also introduce and investigate some new cardinal invariants.


title: Some independence results on reflection

abstract: We prove that there is a certain degree of independence between stationary reflection phenomena at different cofinalities; e.g. it is consistent that every stationary subset of S_1^3 reflects at a point of cofinality aleph_2 while every stationary subset of S^3_0 has a non-reflecting stationary subset


title: On the cardinality and weight spectra of compact spaces, II

abstract: Let B(kappa, lambda) be the subalgebra of P(kappa) generated by [kappa]^{<= lambda}. It is shown that if B is any homomorphic image of B(kappa, lambda) then either |B|< 2^lambda or |B|=|B|^lambda, moreover if X is the Stone space of B then either |X| <= 2^{2^lambda} or |X|=|B|=|B|^lambda. This implies the existence of 0-dimensional compact T_2 spaces whose cardinality and weight spectra omit lots of singular cardinals of ``small'' cofinality.


title: Torsion modules, lattices and p-points

abstract: Answering a long-standing question in the theory of torsion modules, we show that weakly productively bounded domains are necessarily productively bounded. Moreover, we prove a twin result for the ideal lattice L of a domain equating weak and strong global intersection conditions for families (X_i)_{i in I} of subsets of L with the property that bigcap_{i in I} A_i not= 0 whenever A_i in X_i. Finally, we show that, for domains with Krull dimension (and countably generated extensions thereof), these lattice-theoretic conditions are equivalent to productive boundedness.


title: Norms on possibilities II: more ccc ideals on 2^{omega}

abstract: We use the method of norms on possibilities to answer a question of Kunen and construct a ccc sigma --ideal on 2^omega with various closure properties and distinct from the ideal of null sets, the ideal of meager sets and their intersection.


title: Flattening and subanalytic sets in rigid analytic geometry

abstract: Let K be an algebraically closed field endowed with a complete non-archimedean norm with valuation ring R. Let f:Y -> X be a map of K-affinoid varieties. In this paper we study the analytic structure of the image f(Y) in X; such an image is a typical example of a subanalytic set. We show that the subanalytic sets are precisely the D-semianalytic sets, where D is the truncated division function first introduced by Denef and van den Dries. This result is most conveniently stated as a Quantifier Elimination result for the valuation ring R in an analytic expansion of the language of valued fields.


title: On the Lojasiewicz exponent of the gradient of a polynomial function

abstract: Let h = \sum h_{\alpha \beta} X^\alpha Y^\beta be a polynomial with complex coefficients. The Lojasiewicz exponent of the gradient of h at infinity is the upper bound of the set of all real \lambda such that |grad h(x, y)| >= c|(x,y)|^\lambda in a neighbourhood of infinity in C^2, for c > 0. We estimate this quantity in terms of the Newton diagram of h. The equality is obtained in the nondegenerate case.


title: Factorization of proper holomorphic mappings through Thullen Domains

abstract: In this article, we consider a bounded pseudoconvex domain in ${\bf C}^2$ satifying: (a) it admits a proper holomorphic mapping $f$ onto the unit ball $B^2$, and (b) it is simply connected and has a real analytic boundary. According to [Barletta-Bedford, Indiana U. Math. J, 39(1985), 315-338], the strong pseudconvexity of $B^2$ alone yields that such a domain is "weakly spherical" at the boundary points that are at the same time a smooth point of the branch locus $Z_{df} = \{\det(J_{\bf C} f) = 0\}$. (Notice that [Diederich-Fornaess, Math. Ann., 282 (1988), 681-700] implies that $f$ as well as $Z_{df}$ extends holomorphically across the boundaries.) Our main contribution in this paper is that we have discovered a stronger rigidity (both local and global) in case the target domain is the unit ball. The main results are: THEOREM ("Local Rigidity"): Let $(M,o)$ be a real analytic normalized weakly spherical pointed CR hypersurface in ${\bf C}^2$ of order $k_0 > 1$. Let $(\Sigma, o)$ be the pointed Siegel hypersurface given by the defining equation $Re w - |z|^2 = 0$. If there is a holomorphic mapping $F:(M,o) \to (\Sigma,o)$ for which $o$ is a regular branch point, then (1) $(M,o)$ is defined by the equation $Re w - |z|^{2k_0} = 0$, and (2) $F(z,w)$ is equivalent to $(z,w) \mapsto (z^{k_0},w)$ up to a composition with elements in $Aut (M,o)$ and $Aut (\Sigma,o)$. THEOREM ("Global Rigidity"): Let $D$ and $f:D \to B^2$ be as above, and let $f$ be generically $m$-to-1. Assume that its branch locus $Z_{df}$ admits an analytic component $V$ with the following properties: (1) $f$ is locally a $m$-to-1 branched covering with branch locus $V$ at every point of $V \cap \partial D$; (2) $V \cap \partial D$ is connected and contains no singular point of the variety $Z_{df}$. Then $D$ is biholomorphic to $E_m = \{|z|^{2m} + |w|^2 < 1\}$.


title: Amenability, Bilipschitz Maps, and the Von Neumann conjecture

abstract: We determine when a quasi-isometry between discrete spaces is at bounded distance from a bilipschitz map. From this we prove a geometric version of the Von Neumann conjecture on amenability. We also get some examples in geometric groups theory which show that the sign of the Euler characteristic is not a coarse invariant. Finally we get some general results on uniformly finite homology which we will apply to manifolds in a later paper.


title: A non-quasiconvexity embedding theorem for hyperbolic groups

abstract: We show that if $G$ is a non-elementary torsion-free word hyperbolic group then there exists another word hyperbolic group $G^*$, such that $G$ is a subgroup of $G^*$ but $G$ is not quasiconvex in $G^*$.


title: Parallel poly pushdown groups

abstract: We define a class of groups based on parallel computations by pushdown automata. This class generalizes automatic groups. It includes the fundamental groups of all 3-manifolds which obey Thurston' s geometrization conjecture. It also includes nilpotent groups of arbitrary class and polynomial degree isoperimetric inequality. It is closed under wreath product.


title: A hierarchy of maps between compacta

abstract: Let $CH$ be the class of compacta (i.e., compact Hausdorff spaces), with $BS$ the subclass of Boolean spaces. For each ordinal $alpha$ and pair $(K,L)$ of subclasses of $CH$, we define $Lev_{>=alpha}(K,L)$, the class of maps of level at least $alpha$ from spaces in $K$ to spaces in $L$, in such a way that, when $alpha < omega$, $Lev}_{>=alpha}(BS,BS)$ consists of the Stone duals of Boolean lattice embeddings that preserve all prenex first-order formulas of quantifier rank $alpha$. Maps of level $>=0$ are just the continuous surjections, and the maps of level $>=1$ are the co-existential maps. Co-elementary maps are of level $>=alpha$ for all ordinals $alpha$; of course in the Boolean context, the co-elementary maps coincide with the maps of level $>=omega$. The results of this paper include: (i) every map of level $>=omega$ is co-elementary; (ii) the limit maps of an $omega$-indexed inverse system of maps of level $>=alpha$ are also of level $>=alpha$; and (iii) if $K$ is a co-elementary class, $k < omega$ and $Lev_{>=k}(K,K) = Lev_{>=k+1}(K,K)$, then $Lev_{>=k}(K,K}) = Lev_{>=omega}(K,K)$. A space $X$ in $K$ is co-existentially closed in $K$ if $Lev_{>=0}(K,{X}) = Lev_{>=1}(K,{X})$. We showed in an earlier paper that every infinite member of a co-inductive co-elementary class (such as $CH$ itself, $BS$, or the class $CON$ of continua) is a continuous image of a space of the same weight that is co-existentially closed in that class. We show here that every compactum that is co-existentially closed in $CON$ (a "co-existentially closed continuum") is both indecomposable and of covering dimension one.


title: Ranks and pregeometries in finite diagrams

abstract: The study of classes of models of a finite diagram was initiated by S. Shelah in 1969. A diagram D is a set of types over the empty set, and the class of models of the diagram D consists of the models of T which omit all the types not in D. In this work, we introduce a natural dependence relation on the subsets of the models for the omega-stable case which share many of the formal properties of forking. This is achieved by considering a rank for this framework which is bounded when the diagram D is omega-stable. We can also obtain pregeometries with respect to this dependence relation. The dependence relation is the natural one induced by the rank, and the pregeometries exist on the set of realizations of types of minimal rank. Finally, these concepts are used to generalize many of the classical results for models of a totally transcendental first-order theory. In fact, strong analogies arise: models are determined by their pregeometries or their relationship with their pregeometries; however the proofs are different, as we do not have compactness. This is illustrated with positive results (categoricity) as well as negative results (construction of nonisomorphic models).


title: When a partial Borel order is linearizable

abstract: We prove the following classification theorem of the ``Glimm -- Effros'' type for Borel order relations: a Borel partial order on the reals either is Borel linearizable or includes a copy of a certain Borel partial order $\meo$ which is not Borel linearizable.


title: The ``maximal" tensor product of operator spaces

abstract: In analogy with the maximal tensor product of $C^*$-algebras, we define the ``maximal" tensor product $E_1\otimes_\mu E_2$ of two operator spaces $E_1$ and $E_2$ and we show that it can be identified completely isometrically with the sum of the two Haagerup tensor products: \ $E_1\otimes_h E_2 + E_2\otimes_h E_1$. Let $E$ be an $n$-dimensional operator space. As an application, we show that the equality $E^* \otimes_\mu E=E^* \otimes_{\rm min} E$ holds isometrically iff $E = R_n$ or $E=C_n$ (the row or column $n$-dimensional Hilbert spaces). Moreover, we show that if an operator space $E$ is such that, for any operator space $F$, we have $F\otimes_{\min} E=F\otimes_{\mu} E$ isomorphically, then $E$ is completely isomorphic to either a row or a column Hilbert space.


title: Non-commutative martingale inequalities

abstract: We prove the analogue of the classical Burkholder-Gundy inequalites for non-commutative martingales. As applications we give a characterization for an Ito-Clifford integral to be an $L^p$-martingale via its integrand, and then extend the Ito-Clifford integral theory in $L^2$, developed by Barnett, Streater and Wilde, to $L^p$ for all $1<p<\infty$. We include an appendix on the non-commutative analogue of the classical Fefferman duality between $H^1$ and $BMO$.


title: Optimal Young's inequality and its converse:a simple proof

abstract: We give a new proof of the sharp form of Young's inequality for convolutions, first proved by Beckner [Be] and Brascamp-Lieb [BL]. The latter also proved a sharp reverse inequality in the case of exponents less than $1$. Our proof is simpler and gives Young's inequality and its converse altogether.


title: A sharp estimate for the Hardy-Littlewood maximal function

abstract: The best constant in the usual Lp norm inequality for the centered Hardy-Littlewood maximal function on R1 is obtained for the class of all ``peak-shaped'' functions. A positive function on the line is called ``peak-shaped'' if it is positive and convex except at one point. The techniques we use include convexity and an adaptation of the standard Euler-Langrange variational method.


title: Time decay for the bounded mean oscillation of solutions of the Schr\"odinger and wave equations

abstract: Let $u(x,t)$ be the solution of the Schr\"odinger or wave equation with $L_2$ initial data. We provide counterexamples to plausible conjectures involving the decay in $t$ of the $\BMO$ norm of $u(t,\cdot)$. The proofs make use of random methods, in particular, Brownian motion. (Since this paper was written, the unsolved problem remaining in this paper has been solved by Keel and Tao.)


title: Random rearrangements and operators

abstract: Consider an n by n matrix x_ij, and consider the quantity || x_{i,pi(i)} ||_X where X is a symmetric sequence space as a random variable where the permutation pi is chosen randomly. This was considered by Kwapien and Schutt, and we extend their results to rearrangement invariant spaces. We also consider the property of D and D^* convexity for rearrangement invariant spaces.


title: Proximity to $\ell_1$ and Distortion in Asymptotic $\ell_1$ Spaces

abstract: For an asymptotic $\ell_1$ space $X$ with a basis $(x_i)$ certain asymptotic $\ell_1$ constants, $\delta_\alpha (X)$ are defined for $\alpha <\omega_1$. $\delta_\alpha (X)$ measures the equivalence between all normalized block bases $(y_i)_{i=1}^k$ of $(x_i)$ which are $S_\alpha$-admissible with respect to $(x_i)$ ($S_\alpha$ is the $\alpha^{th}$-Schreier class of sets) and the unit vector basis of $\ell_1^k$. This leads to the concept of the delta spectrum of $X$, $\Delta (X)$, which reflects the behavior of stabilized limits of $\delta_\alpha (X)$. The analogues of these constants under all renormings of $X$ are also defined and studied. We investigate $\Delta (X)$ both in general and for spaces of bounded distortion. We also prove several results on distorting the classical Tsirelson's space $T$ and its relatives.


title: Modified mixed Tsirelson spaces

abstract: We study the modified and boundedly modified mixed Tsirelson spaces $T_M[({\cal F}_{k_n},\theta_n)_{n=1}^{\infty }]$ and $T_{M(s)}[({\cal F}_{k_n},\theta_n)_{n=1}^{\infty }]$ respectively, defined by a subsequence $({\cal F}_{k_n})$ of the sequence of Schreier families $({\cal F}_n)$. These are reflexive asymptotic $\ell_1$ spaces with an unconditio- nal basis $(e_i)_i$ having the property that every sequence $\{ x_i\}_{i=1}^n$ of normalized disjointly supported vectors contained in $\langle e_i\rangle_{i=n}^{\infty }$ is equivalent to the basis of $\ell_1^n$. We show that if $\lim\theta_n^{1/n}=1$ then the space $T[({\cal F}_n,\theta_n) _{n=1}^{\infty }]$ and its modified variations are totally incomparable by proving that $c_0$ is finitely disjointly representable in every block subspace of $T[({\cal F}_n, \theta_n)_{n=1}^{\infty }]$. Next, we present an example of a boundedly modified mixed Tsirelson space $X_{M(1),u}$ which is arbitrarily distortable. Finally, we construct a variation of the space $X_{M(1),u}$ which is hereditarily indecomposable.


title: Linear maps on factors which preserve the extreme points of the unit ball

abstract: The aim of this paper is to characterize those linear maps from a von Neumann factor $\A$ into itself which preserve the extreme points of the unit ball of $\A$. For example, we show that if $\A$ is infinite, then every such linear preserver can be written as a fixed unitary operator times either a unital *-homomorphism or a unital *-antihomomorphism.


title: On Subdivision Posets of Cyclic Polytopes

abstract: There are two related poset structures, the higher Stasheff-Tamari orders, on the set of all triangulations of the cyclic $d$ polytope with $n$ vertices. In this paper it is shown that both of them have the homotopy type of a sphere of dimension $n-d-3$. Moreover, we resolve positively a new special case of the \emph{Generalized Baues Problem}: The Baues poset of all polytopal decompositions of a cyclic polytope of dimension $d \leq 3$ has the homotopy type of a sphere of dimension $n-d-2$.


title: A simple polynomial time algorithm to approximate the permanent within a simply exponential factor

abstract: We present a simple randomized polynomial time algorithm to approximate the mixed discriminant of $n$ positive semidefinite $n \times n$ matrices within a factor $2^{O(n)}$. Consequently, the algorithm allows us to approximate in randomized polynomial time the permanent of a given $n \times n$ non-negative matrix within a factor $2^{O(n)}$. When applied to approximating the permanent, the algorithm turns out to be a simple modification of the well-known Godsil-Gutman estimator.


title: Extension Properties of Meromorphic Mappings with Values in Non-Kahler Manifolds

abstract: We prove an analogue of E. Levi's Continuity Principle for meromorphic mappings with values in arbitrary compact complex manifolds in place of the Riemann sphere $\cc\pp^1$. The result is achieved by introducing a new extension method for meromorphic mappings. One of the corollaries reads as follows: If a compact complex surface $X$ is not "among the known ones" then for every domain $\Omega $ in a Stein surface every meromorphic mapping $f:\Omega \to X$ is in fact holomorphic and extends as a holomorphic mapping $\hat f:\hat D\to X$ of the envelope of holomorphy $\hat D$ of $D$ into $X$. In this last version also two examples of compact complex maniflds are described with meromoprhic mappings into these manifolds having thin but non-analytic singularity sets.


title: Continued Fractions and Unique Additive Partitions

abstract: A partition of the positive integers into sets $A$ and $B$ {\em avoids} a set $S\subset\N$ if no two distinct elements in the same part have a sum in $S$. If the partition is unique, $S$ is {\em uniquely avoidable.} For any irrational $\alpha>1$, Chow and Long constructed a partition which avoids the numerators of all convergents to $\alpha$, and conjectured that the set $S_\alpha$ which this partition avoided was uniquely avoidable. We prove that the set of numerators of convergents is uniquely avoidable if and only if the continued fraction for $\alpha$ has infinitely many partial quotients equal to 1. We also construct the set $S_\alpha$ and show that it is always uniquely avoidable.


title: Dehn surgery on arboresent knots and links -- a survey

abstract: This article is solicited by C.\ Adams for a special issue of {\it Chaos, Solitons and Fractals\/} devoted to knot theory and its applications. We present some recent results about Dehn surgeries on arborescent knots and links.


title: Non-integral toroidal surgery on hyperbolic knots in $S^3$

abstract: We show that on any hyperbolic knot in $S^3$ there is at most one non-integral Dehn surgery which yields a manifold containing an incompressible torus.


title: Combinatorial methods in Dehn surgery

abstract: This is an expository paper, in which we give a summary of some of the joint work of John Luecke and the author on Dehn surgery. We consider the situation where we have two Dehn fillings $M(\alpha)$ and $M(\beta)$ on a given 3-manifold $M$, each containing a surface that is either essential or a Heegaard surface. We show how a combinatorial analysis of the graphs of intersection of the two corresponding punctured surfaces in $M$ enables one to find faces of these graphs which give useful topological information about $M(\alpha)$ and $M(\beta)$, and hence, in certain cases, good upper bounds on the intersection number $\Delta(\alpha, \beta)$ of the two filling slopes.


title: Sutured manifold hierarchies, essential laminations, and Dehn surgery

abstract: We use sutured manifold theory, essential laminations and essential branched surfaces to establish the upper bounds of distances between certain types of nonsimple Dehn surgery slopes. This is the revised version of an earlier preprint {\it Dehn surgery and simple manifolds.}


title: Order complexes of noncomplemented lattices are nonevasive

abstract: We reprove and generalize in a combinatorial way the result of A. Bj\"orner [J.\ Comb.\ Th.\ A {\bf 30}, 1981, pp.~90--100, Theorem 3.3], that order complexes of noncomplemented lattices are contractible, namely by showing that these simplicial complexes are in fact nonevasive, in particular collapsible.


title: A Polynomial Time Algorithm for Vertex Enumeration and Optimization over Shaped Partition Polytopes

abstract: We consider the {\em Shaped Partition Problem} of partitioning $n$ given vectors in real $k$-space into $p$ parts so as to maximize an arbitrary objective function which is convex on the sum of vectors in each part, subject to arbitrary constraints on the number of elements in each part. In addressing this problem, we study the {\em Shaped Partition Polytope} defined as the convex hull of solutions. The Shaped Partition Problem captures ${\cal N}{\cal P}$-hard problems such as the Max-Cut problem and the Traveling Salesperson problem, and the Shaped Partition Polytope may have exponentially many vertices and facets, even when $k$ or $p$ are fixed. In contrast, we show that when both $k$ and $p$ are fixed, the number of vertices is polynomial in $n$, and all vertices can be enumerated and the optimization problem solved in strongly polynomial time. Explicitly, we show that any Shaped Partition Polytope has $O(n^{k{p\choose 2}})$ vertices which can be enumerated in $O(n^{k^2p^3})$ arithmetic operations, and that any Shaped Partition Problem is solvable in $O(n^{kp^2})$ arithmetic operations.


title: Diagrams of classifying spaces and $k$-fold Boolean algebras

abstract: In this paper we study the problem of determining the homology groups of a quotient of a topological space by an action of a group. The method is to represent the original topological space as a homotopy limit of a diagram, and then act with the group on that diagram. Once it is possible to understand what the action of the group on every space in the diagram is, and what it does to the morphisms, we can compute the homology groups of the homotopy limit of this quotient diagram. Our motivating example is the symmetric deleted join of a simplicial complex. It can be represented as a diagram of symmetric deleted products. In the case where the simplicial complex in question is a simplex, we perform the complete computation of the homology groups with $\mathbb Z_p$ coefficients. For the infinite simplex the spaces in the quotient diagram are classifying spaces of various direct products of symmetric groups and diagram morphisms are induced by group homomorphisms. Combining Nakaoka's description of the $\mathbb Z_p$-homology of the symmetric group with a spectral sequence, we reduce the computation to an essentially combinatorial problem, which we then solve using the braid stratification of a sphere. Finally, we give another description of the problem in terms of posets and complete the computation for the case of a finite simplex.


title: Littlewood-Richardson semigroups

abstract: This note is an extended abstract of my talk at the workshop on Representation Theory and Symmetric Functions, MSRI, April 14, 1997. We discuss the problem of finding an explicit description of the semigroup $LR_r$ of triples of partitions of length $\leq r$ such that the corresponding Littlewood-Richardson coefficient is non-zero. After discussing the history of the problem and previously known results, we suggest a new approach based on the ``polyhedral'' combinatorial expressions for the Littlewood-Richardson coefficients.


title: Hard ball systems are completely hyperbolic

abstract: We consider the system of N (\ge 2) elastically colliding hard balls with masses m_1,..., m_N, radius r, moving uniformly in the flat torus T_L^{\nu}= R^\nu/L \cdot Z^\nu, \nu \ge 2. It is proved here that the relevant Lyapunov exponents of the flow do not vanish for almost every (N+1)-tuple (m_1,...,m_N;L) of the outer geometric parameters.


title: Dynamical cocycles with values in the Artin braid group

abstract: By considering the way an n-tuple of points in the 2-disk are linked together under iteration of an orientation preserving diffeomorphism, we construct a dynamical cocycle with values in the Artin braid group. We study the asymptotic properties of this cocycle and derive a series of topological invariants for the diffeomorphism which enjoy rich properties.


title: On minimal parabolic functions and time-homogeneous parabolic h-transforms

abstract: Does a minimal harmonic function $h$ remain minimal when it is viewed as a parabolic function? The question is answered for a class of long thin semi-infinite tubes $D\subset \R^d$ of variable width and minimal harmonic functions $h$ corresponding to the boundary point of $D$ ``at infinity.'' Suppose $f(u)$ is the width of the tube $u$ units away from its endpoint and $f$ is a Lipschitz function. The answer to the question is affirmative if and only if $\int^\infty f^3(u)du = \infty$. If the test fails, there exist parabolic $h$-transforms of space-time Brownian motion in $D$ with infinite lifetime which are not time-homogenous.


title: Verdier stratifications and [wf]-stratification in o-minimal structures

abstract: We prove the existence of Verdier stratifications for sets definable in any o-minimal structure on (R, +, .). It is also shown that the Verdier condition (w) implies the Whitney condition (b) in o-minimal structures on (R, +, .). As a consequence the Whitney Stratification Theorem holds. The existence of (wf)-stratification of functions definable in polynomially bounded o-minimal structures is presented.


title: Groups in simple theories

abstract: Groups definable in simple theories retain the chain conditions and decomposition properties known from stable groups, up to commensurability. In the small case, if a generic type of G is not foreign to some type q, there is a q-internal quotient. In the supersimple case, the Berline-Lascar decomposition works. One-based simple groups are finite-by-abelian-by-finite.