The class of groups which have a subgroup of index 2 is not elementary

F. Oger proved that if A is a finite group, then the class of groups which are abelian-by-A can be axiomatized by a single first order sentence. It is established here that, in Oger's result, the word abelian cannot be replaced by group. Received: 15 March 1996 / Published online: 18 July 2001     

Axiomatization of abelian-by-G groups for a finite group G

We show that, for each finite group G, there exists an axiomatization of the class of abelian-by-G groups with a single sentence. In the proof, we use the definability of the subgroups M ⁿ in an abelian-by-finite group M, and the Auslander-Reiten sequences for modules over an Artin algebra. Received: 15 March 1996 / Published online: 18 July 2001     

Explaining the Gentzen–Takeuti reduction steps: a second-order system

Using the concept of notations for infinitary derivations we give an explanation of Takeuti's reduction steps on finite derivations (used in his consistency proof for Π¹ ₁-CA) in terms of the more perspicious infinitary approach from [BS88]. Received: 27 April 1999 / Published online: 21 March 2001     

On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. (In the limit as k→∞ these become the corresponding distributions for permutations on N letters.) We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating unction gives the distribution of the smallest eigenvalue in the k×k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N→∞ limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k×k hermitian matrices of trace zero. Received: 9 September 1999 / Revised version: 24 May 2000 / Published online: 24 January 2001     

Basic Propositional Calculus II. Interpolation

Let ℒ and ? be propositional languages over Basic Propositional Calculus, and ℳ = ℒ∩?. Weprove two different but interrelated interpolation theorems. First, suppose that Π is a sequent theory over ℒ, and Σ∪ {C⇒C′} is a set of sequents over ?, such that Π,Σ⊢C⇒C′. Then there is a sequent theory Φ over ℳ such that Π⊢Φ and Φ, Σ⊢C⇒C′. Second, let A be a formula over ℒ, and C ₁, C ₂ be formulas over ?, such that A∧C ₁⊢C ₂. Then there exists a formula B over ℳ such that A⊢B and B∧C ₁⊢C ₂. Received: 7 January 1998 / Published online: 18 May 2001     

The Typical Growth of the kth Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of . Received February 6, 2001; in revised form February 25, 2002 Published online August 5, 2002     

The Karp complexity of unstable classes

A class K of structures is controlled if, for all cardinals λ, the relation of L _∞,λ-equivalence partitions K into a set of equivalence classes (as opposed to a proper class). We prove that the class of doubly transitive linear orders is controlled, while any pseudo-elementary class with the ω-independence property is not controlled. Received: 23 September 1998 / Revised version: 6 July 1999 / Published online: 21 December 2000     

Near coherence and filter games

We investigate a two-player game involving pairs of filters on ω. Our results generalize a result of Shelah ([7] Chapter VI) dealing with applications of game theory in the study of ultrafilters. Received: 28 September 1998 / Published online: 25 January 2001     

Natural deduction with general elimination rules

The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates. Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001     

On a class of stochastic partial differential equations related to turbulent transport

Summary. We consider the Cauchy problem for the mass density ρ of particles which diffuse in an incompressible fluid. The dynamical behaviour of ρ is modeled by a linear, uniformly parabolic differential equation containing a stochastic vector field. This vector field is interpreted as the velocity field of the fluid in a state of turbulence. Combining a contraction method with techniques from white noise analysis we prove an existence and uniqueness result for the solution ρ∈C ^1,2([0,T]×ℝ ^d ,(S)^*), which is a generalized random field. For a subclass of Cauchy problems we show that ρ actually is a classical random field, i.e. ρ(t,x) is an L ²-random variable for all time and space parameters (t,x)∈[0,T]×ℝ ^d . Received: 27 March 1995 / In revised form: 15 May 1997     

Inégalités de concentration pour les processus empiriques de classes de parties

We propose new concentration inequalities for maxima of set-indexed empirical processes. Our approach is based either on entropy inequalities or on martingale methods. The improvements we get concern the rate function which is exactly the large deviations rate function of a binomial law in most of the cases. Received: 11 January 2000 / Revised version: 12 May 2000 / Published online: 14 December 2000     

On the modality of parabolic subgroups of linear algebraic groups

For a linear algebraic group G over an algebraically closed field k and a parabolic subgroup P of G the modality of P is defined to be the maximal number of parameters upon which a family of G-orbits on Lie P _u depends and it is denoted by mod P, where P _u is the unipotent radical of P. The principal aim of this note is a generalization of two basic “monotonicity” results from [19] to positive characteristic: (1) If Θ is a semisimple automorphism of G and P is Θ-stable, then mod P ^\Θ≤ mod P. (2) If G is reductive, char k is a good prime for G, and H is a closed reductive subgroup of G normalized by a maximal torus T⊂P of G, then mod (P∩H)≤ mod P. Received: 22 April 1998 / Revised version: 3 July 1998     

An explicit upper bound for Weil-Petersson volumes of the moduli spaces of punctured Riemann surfaces

An explicit upper bound for the Weil-Petersson volumes of punctured Riemann surfaces is obtained using Penner's combinatorial integration scheme from [4]. It is shown that for a fixed number of punctures n and for genus g increasing, while this limit is exactly equal to two for n=1. Received: 17 May 2000 / Revised version: 9 August 2000 / Published online: 23 July 2001     

On the filter of computably enumerable supersets of an r-maximal set

We study the filter ℒ^*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ^*(A) is still Σ⁰ ₃-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ^*(A). Received: 6 November 1999 / Revised version: 10 March 2000 /?Published online: 18 May 2001     

Zeno's walk: A random walk with refinements

Summary. A self-modifying random walk on is derived from an ordinary random walk on the integers by interpolating a new vertex into each edge as it is crossed. This process converges almost surely to a random variable which is totally singular with respect to Lebesgue measure, and which is supported on a subset of having Hausdorff dimension less than , which we calculate by a theorem of Billingsley. By generating function techniques we then calculate the exponential rate of convergence of the process to its limit point, which may be taken as a bound for the convergence of the measure in the Wasserstein metric. We describe how the process may viewed as a random walk on the space of monotone piecewise linear functions, where moves are taken by successive compositions with a randomly chosen such function. Received: 20 November 1995 / In revised form: 14 May 1996     

Ordinal diagrams for recursively Mahlo universes

In this paper we introduce a recursive notation system of ordinals. An element of the notation system is called an ordinal diagram following G. Takeuti [25]. The system is designed for proof theoretic study of theories of recursively Mahlo universes. We show that for each in KPM proves that the initial segment of determined by is a well ordering. Proof theoretic study for such theories will be reported in [9]. Received: 13 January, 1998     

On the false pole problem

We prove that if a convex body has an interior false pole with respect to some hyperplane, then the body is an ellipsoid. This research was partially carried out during the postdoctoral visit of this author at University College London, and it was supported by CONACYT, México.     

On the Constants in the Meyer Inequality

 We study the growth of the constants in the Meyer inequality as p → 1 and p → ∞. Both constants grow, within constant factors, like (p − 1)⁻¹ and like p respectively. Received August 10, 2001; in revised form February 5, 2002     

On the Range of the Chébli–Trimèche Transform

We first characterise the L²-Schwartz functions whose image under the Chébli–Trimèche transform are compactly supported smooth functions. We then generalise a theorem by H. H. Bang, characterising the smooth L^p-functions whose (distributional) transform have compact support.The author is supported by a research grant from the Australian Research Council.     

On the smallest maximal increment of partial sums of i.i.d. random variables

Summary. We study the almost sure limiting behavior of the smallest maximal increment of partial sums of independent identically distributed random variables for a variety of increment sizes , where is a sequence of integers satisfying , and going to infinity at various rates. Our aim is to obtain universal results on such behavior under little or no assumptions on the underlying distribution function. Received: 30 August 1995 / In revised form: 27 September 1996