A test for expandability

A model of countable similarity type and cardinality is expandable if every consistent extension of its complete theory with is satisfiable in and it is compactly expandable if every such extension which additionally is finitely satisfiable in is satisfiable in . In the countable case and in the case of a model of cardinality of a superstable theory without the finite cover property the notions of saturation, expandability and compactness for expandability agree. The question of the existence of compactly expandable models which are not expandable is open. Here we present a test which serves to prove that a compactly expandable model of cardinality of a superstable theory is expandable. It is stated in terms of the existence of a certain elementary submodel whose corresponding theory of pairs of models satisfies a weak elimination of Ramsey quantifiers. Received May 20, 1996     

An elementary proof of strong normalization for intersection types

We provide a new and elementary proof of strong normalization for the lambda calculus of intersection types. It uses no strong method, like for instance Tait-Girard reducibility predicates, but just simple induction on type complexity and derivation length and thus it is obviously formalizable within first order arithmetic. To obtain this result, we introduce a new system for intersection types whose rules are directly inspired by the reduction relation. Finally, we show that not only the set of strongly normalizing terms of pure lambda calculus can be characterized in this system, but also that a straightforward modification of its rules allows to characterize the set of weakly normalizing terms. Received: 15 June 1998 / Revised version: 15 November 1999 / Published online: 15 June 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     

All finitely axiomatizable subframe logics containing the provability logic CSM_{0} are decidable

In this paper we investigate those extensions of the bimodal provability logic (alias or which are subframe logics, i.e. whose general frames are closed under a certain type of substructures. Most bimodal provability logics are in this class. The main result states that all finitely axiomatizable subframe logics containing are decidable. We note that, as a rule, interesting systems in this class do not have the finite model property and are not even complete with respect to Kripke semantics. Received July 15, 1997     

Normal deduction in the intuitionistic linear logic

We describe a natural deduction system NDIL for the second order intuitionistic linear logic which admits normalization and has a subformula property. NDIL is an extension of the system for !-free multiplicative linear logic constructed by the author and elaborated by A. Babaev. Main new feature here is the treatment of the modality !. It uses a device inspired by D. Prawitz' treatment of S4 combined with a construction introduced by the author to avoid cut-like constructions used in -elimination and global restrictions employed by Prawitz. Normal form for natural deduction is obtained by Prawitz translation of cut-free sequent derivations. Received: March 29, 1996     

A computably enumerable vector space with the strong antibasis property

Downey and Remmel have completely characterized the degrees of c.e. bases for c.e. vector spaces (and c.e. fields) in terms of weak truth table degrees. In this paper we obtain a structural result concerning the interaction between the c.e. Turing degrees and the c.e. weak truth table degrees, which by Downey and Remmel's classification, establishes the existence of c.e. vector spaces (and fields) with the strong antibasis property (a question which they raised). Namely, we construct c.e. sets such that the c.e. W-degrees below that of A are disjoint from the nonzero c.e. T-degrees below that of A and comparable to that of B. Received: 2 December 1998     

The high temperature case for the random K-sat problem

We give a completely rigorous proof that the replica-symmetric solution holds at high enough temperature for the random K-sat problem. The most notable feature of this problem is that the order parameter of the system is a function and not a number. Received: 21 April 1998 / Revised version: 24 April 2000 / Published online: 21 December 2000     

A generalized strong law of large numbers

Strong laws of large numbers have been stated in the literature for measurable functions taking on values on different spaces. In this paper, a strong law of large numbers which generalizes some previous ones (like those for real-valued random variables and compact random sets) is established. This law is an example of a strong law of large numbers for Borel measurable nonseparably valued elements of a metric space. Received: 24 February 1998 / Revised version: 3 January 1999     

A non-uniform Berry–Esseen bound via Stein's method

This paper is part of our efforts to develop Stein's method beyond uniform bounds in normal approximation. Our main result is a proof for a non-uniform Berry–Esseen bound for independent and not necessarily identically distributed random variables without assuming the existence of third moments. It is proved by combining truncation with Stein's method and by taking the concentration inequality approach, improved and adapted for non-uniform bounds. To illustrate the technique, we give a proof for a uniform Berry–Esseen bound without assuming the existence of third moments. Received: 2 March 2000 / Revised version: 20 July 2000 / Published online: 26 April 2001     

On the equations of the edge cone of a graph¶and some applications

Let G be a graph such that none of its components is bipartite. We describe the facets of the cone generated by the columns of the incidence matrix of G. Let k[G] be the subring generated by the monomials of degree two defining the edges of G, where k is a field. Some estimates for the a-invariant of k[G] are shown when G is the cone of a normal connected non bipartite graph or G is the join of two normal connected non bipartite graphs. Received: 24 July 1997 / Revised version: 3 March 1998     

Un théorème central limite presque sûr à moments généralisés pour les rotations irrationnelles

In a recent work, we indicated another formulation of the Almost Sure Central Limit Theorem (A.S.C.L.T.), with series in place of averages, by showing that the property of the A.S.C.L.T. directly follows from the theory of orthogonal sums. For, we used the notion of quasi-orthogonal systems introduced earlier by R. Bellmann, and later developed by Kac–Salem–Zygmund. The main object of this paper is to prove a similar result for irrational rotations of the torus. We prove the existence of a generalized moment version of the A.S.C.L.T., with a speed of convergence. In our strategy, we use again the notion of quasi-orthogonal system, and purpose a Gaussian randomization technic, new at least in this context. The proof avoid notably the use of Volny's result on the existence of good Gaussian approximations in aperiodic dynamical systems, and should also permit to be able to treat problems of comparable nature, in particular in non-ergodic cases. Received: 2 February 1999     

Adelic version of Margulis arithmeticity theorem

We generalize Margulis's S-arithmeticity theorem to the case when S can be taken as an infinite set of primes. Let R be the set of all primes including infinite one and set . Let S be any subset of R. For each , let be a connected semisimple adjoint -group and be a compact open subgroup for each finite prime . Let denote the restricted topological product of 's, with respect to 's. Note that if S is finite, . We show that if , any irreducible lattice in is a rational lattice. We also present a criterion on the collections and for to admit an irreducible lattice. In addition, we describe discrete subgroups of generated by lattices in a pair of opposite horospherical subgroups. Received: 30 November 2000 / Revised version: 2 April 2001 / Published online: 24 September 2001     

On the Connection Between the Projection and the Extension of a Parallelotope

This paper presents a result concerning the connection between the parallel projection P _v,H of a parallelotope P along the direction v (into a transversal hyperplane H) and the extension P + S(v), meaning the Minkowski sum of P and the segment S(v) = {λv | −1 ≤ λ ≤ 1}. A sublattice L _v of the lattice of translations of P associated to the direction v is defined. It is proved that the extension P + S(v) is a parallelotope if and only if the parallel projection P _v,H is a parallelotope with respect to the lattice of translations L _v,H , which is the projection of the lattice L _v along the direction v into the hyperplane H.     

Some coinductive graphs

Summary LetT be a universal theory of graphs such that Mod(T) is closed under disjoint unions. Let _T be a disjoint union _i such that each _i is a finite model ofT and every finite isomorphism type in Mod(T) is represented in{ _i i<3}. We investigate under what conditions onT, Th( _T ) is a coinductive theory, where a theory is called coinductive if it can be axiomatizated by -sentences. We also characterize coinductive graphs which have quantifier-free rank 1.     

The associated primes of local cohomology modules over rings of small dimension

Let R be a commutative Noetherian local ring of dimension d, I an ideal of R, and M a finitely generated R-module. We prove that the set of associated primes of the local cohomology module H ⁱ _I (M) is finite for all i≥ 0 in the following cases: (1) d≤ 3; (2) d= 4 and $R$ is regular on the punctured spectrum; (3) d= 5, R is an unramified regular local ring, and M is torsion-free. In addition, if $d>0$ then H ^{d − 1} _I (M) has finite support for arbitrary R, I, and M. Received: 31 October 2000 / Revised version: 8 January 2001     

On the first cohomology of arithmetic groups

We study the restriction to smaller subgroups, of cohomology classes on arithmetic groups (possibly after moving the class by Hecke correspondences), especially in the context of first cohomology of arithmetic groups. We obtain vanishing results for the first cohomology of cocompact arithmetic lattices in SU(n,1) which arise from hermitian forms over division algebras D of degree p ², p an odd prime, equipped with an involution of the second kind. We show that it is not possible for a ‘naive’ restriction of cohomology to be injective in general. We also establish that the restriction map is injective at the level of first cohomology for non co-compact lattices, extending a result of Raghunathan and Venkataramana for co-compact lattices. Received: 14 September 2000 / Accepted: 6 June 2001     

Phase transition of the principal Dirichlet eigenvalue in a scaled Poissonian potential

We consider d-dimensional Brownian motion in a scaled Poissonian potential and the principal Dirichlet eigenvalue (ground state energy) of the corresponding Schr?dinger operator. The scaling is chosen to be of critical order, i.e. it is determined by the typical size of large holes in the Poissonian cloud. We prove existence of a phase transition in dimensions d≥ 4: There exists a critical scaling constant for the potential. Below this constant the scaled infinite volume limit of the corresponding principal Dirichlet eigenvalue is linear in the scale. On the other hand, for large values of the scaling constant this limit is strictly smaller than the linear bound. For d > 4 we prove that this phase transition does not take place on that scale. Further we show that the analogous picture holds true for the partition sum of the underlying motion process. Received: 10 December 1999 / Revised version: 14 July 2000/?Published online: 15 February 2001     

Completeness of two systems of illative combinatory logic for first-order propositional and predicate calculus

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. The paper considers 4 systems of illative combinatory logic that are sound for first-order propositional and predicate calculus. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators, or in a more direct way, in which derivations are not translated. Both translations are closely related in a canonical way. In a preceding paper, Barendregt, Bunder and Dekkers, 1993, we proved completeness of the two direct translations. In the present paper we prove completeness of the two indirect translations by showing that the corresponding illative systems are conservative over the two systems for the direct translations. In another version, DBB (1997), we shall give a more direct completeness proof. These papers fulfill the program of Church and Curry to base logic on a consistent system of -terms or combinators. Hitherto this program had failed because systems of ICL were either too weak (to provide a sound interpretation) or too strong (sometimes even inconsistent). Received: February 15, 1996