The range of a projection of small norm inl 1 n

It is proved that there exists a positive function Φ(∈) defined for sufficiently small ∈ 〉 0 and satisfying lim_t→0 Φ(∈) =0 such that for any integersn 〉>0, ifQ is a projection ofl ₁ ⁿ onto ak-dimensional subspaceE with ‖|Q‖|≦1+∈ then there is an integerh〉=k(1−Φ(∈)) and anh-dimensional subspaceF ofE withd(F,l ₁ ^h ) 〈= 1+Φ (∈) whered(X, Y) denotes the Banach-Mazur distance between the Banach spacesX andY. Moreover, there is a projectionP ofl ₁ ⁿ ontoF with ‖|P‖| ≦1+Φ(∈). Author was partially supported by the N.S.F. Grant MCS 79-03042.     

Mixing properties of Markov operators and ergodic transformations,and ergodicity of cartesian products

LetT be a Markov operator onL ₁(X, Σ,m) withT*=P. We connect properties ofP with properties of all productsP ×Q, forQ in a certain class: (a) (Weak mixing theorem)P is ergodic and has no unimodular eigenvalues ≠ 1 ⇔ for everyQ ergodic with finite invariant measureP ×Q is ergodic ⇔ for everyu ∈L ₁ with∝ udm=0 and everyf ∈L _∞ we haveN ⁻¹Σ _n ^≠1/N |<u, P ⁿf>|→0. (b) For everyu ∈L ₁ with∝ udm=0 we have ‖T ⁿu‖₁ → 0 ⇔ for every ergodicQ, P ×Q is ergodic. (c)P has a finite invariant measure equivalent tom ⇔ for every conservativeQ, P ×Q is conservative. The recent notion of mild mixing is also treated. Dedicated to the memory of Shlomo Horowitz An erratum to this article is available at .     

Independence results for uncountable superstable theories

We prove that the following statement is independent of ZFC+┐CH: IFT is a superstable theory of power <2^ℵ ₀,M≰N are models ofT withQ(M)=Q(N), then there isN′≱N withQ(N)=Q(N′). This generalizes Lachlan’s (1972) result.     

Characterization of algebraic curves by Chebyshev quadrature

Complex potential theory is used to show that Chebyshev-type quadrature works particularly well on algebraic Jordan curves Γ in ℝ ^d , supplied with normalized arc length or a similar probability measure μ. Evaluating the integral ∫_Γ fdμ by the arithmetic mean of the value off on any cycle ofN equally spaced nodes on Γ (relative to μ), the quadrature error will, be bounded byAe ^−bN sup_Γ|f| for allN and all polynomialsf(x) of degree ≤cN. It is plausible that small shifts of the nodes would give quadrature error zero for such polynomials. There are related results for algebraic Jordan arcs and certain algebraic surfaces. The situation is completely different for nonalgebraic curves and surfaces, where corresponding quadrature remainders are at least of order 1/N.     

On a combinatorial problem in group theory

We say that a groupG ∈DS if for some integerm, all subsetsX ofG of sizem satisfy |X ²|<|X|², whereX ²={xy|x,y ∈X}. It is shown, using a previous result of Peter Neumann, thatG ∈DS if and only if either the subgroup ofG generated by the squares of elements ofG is finite, orG contains a normal abelian subgroup of finite index, on which each element ofG acts by conjugation either as the identity automorphism or as the inverting automorphism. Dedicated to John G. Thompson, the Wolf Prize Laureate in Mathematics for 1992 The first author wishes to thank the Department of Mathematics in the University of Napoli for their hospitality during the preparation of this paper.     

Automata accepting primitive words

LeA be an automaton whose set of inputs equalsX (|X|≧2) and whose cardinality of the set of states equalsn (n≧2), and letQ be the set of all primitive words overX. ByT(A) we denote the language accepted byA. In this paper, we give the following results:

Existence d’un generateur suivant une sous-suite de densite superieure nulle

Ergodic theory: for every dynamical system (X,A,T, μ), totally ergodic and of finite entropy, there exist a sequenceS of integers, of upper density zero, and a partitionQ ofX, such that V _i∈S T ⁻ⁱ Q is the whole σ-algebraA. Furthermore, there is a “universal” sequenceS ⁰ for which this property is true if we restrict ourselves to the class of strongly mixing systems.      

On completely reducible solvable subgroups of GL(n, Δ)

Let Δ be a finite field and denote by GL(n, Δ) the group ofn×n nonsingular matrices defined over Δ. LetR⊆GL(n, Δ) be a solvable, completely reducible subgroup of maximal order. For |Δ|≧2, |Δ|≠3 we give bounds for |R| which improve previous ones. Moreover for |Δ|=3 or |Δ|>13 we determine the structure ofR, in particular we show thatR is unique, up to conjugacy. This work is part of a Ph.D. thesis done at the Hebrew University under the supervision of Professor A. Mann.     

Regular modules and quasi-lengths over a 3-Kronecker quiver: using Fibonacci numbers

Let Q be a 3-Kronecker quiver (i.e., two vertices and three arrows having the same starting and ending vertices). The dimension vectors of the indecomposable regular representations X such that |X| = |τ ⁱ X| will be studied using the Fibonacci numbers, where |X| denotes the length of X and τ denotes the Auslander–Reiten translation. The quasi-lengths of the indecomposable regular representations with dimension vectors (m, m) and (2m, m) will also be discussed.     

On the bounded version of Hilbert's tenth problem

 The paper establishes lower bounds on the provability of 𝒟=NP and the MRDP theorem in weak fragments of arithmetic. The theory I ⁵ E ₁ is shown to be unable to prove 𝒟=NP. This non-provability result is used to show that I ⁵ E ₁ cannot prove the MRDP theorem. On the other hand it is shown that I ¹ E ₁ proves 𝒟 contains all predicates of the form (∀i≤|b|)P(i,x)^Q(i,x) where ^ is =, <, or ≤, and I ⁰ E ₁ proves 𝒟 contains all predicates of the form (∀i≤b)P(i,x)=Q(i,x). Here P and Q are polynomials. A conjecture is made that 𝒟 contains NLOGTIME. However, it is shown that this conjecture would not be sufficient to imply 𝒟=N P. Weak reductions to equality are then considered as a way of showing 𝒟=NP. It is shown that the bit-wise less than predicate, ≤₂, and equality are both co-NLOGTIME complete under FDLOGTIME reductions. This is used to show that if the FDLOGTIME functions are definable in 𝒟 then 𝒟=N P. Received: 13 July 2001 / Revised version: 9 April 2002 / Published online: 19 December 2002 Key words or phrases: Bounded Arithmetic – Bounded Diophantine Complexity     

Systems of quadratic Diophantine inequalities and the value distribution of quadratic forms

Let Q ₁,…,Q _r be quadratic forms with real coefficients. We prove that the set {(Q₁(x),?,Q_r(x)) | x ? \Bbb Z^s}\{(Q_1(x),\ldots ,Q_r(x))\,\vert\, x\in{\Bbb Z}^s\} is dense in \Bbb R^r{\Bbb R}^r , provided that the system Q ₁(x) = 0,…,Q _r (x) = 0 has a nonsingular real solution and all forms in the real pencil generated by Q ₁,…,Q _r are irrational and have rank larger than 8r. Moreover, we give a quantitative version of the above assertion. As an application we study higher correlation functions of the value distribution of a positive definite irrational quadratic form.     

Universality Limits for Exponential Weights

We establish universality in the bulk for fixed exponential weights on the whole real line. Our methods involve first-order asymptotics for orthogonal polynomials and localization techniques. In particular, we allow exponential weights such as | x | ^2β g ²(x)exp (−2Q(x)), where β>−1/2, Q is convex and Q ^′′ satisfies some regularity conditions, while g is positive, and has a uniformly continuous and slowly growing or decaying logarithm.      

Resolutions of generic points lying on a smooth quadric

For a 0-dimensional schemeX on a smooth quadricQ we define a special type of resolution of its ideal sheaf as a locally freeO _Q. These resolutions allow to find, for schemes which are generic inQ, the minimal free resolution ofX as a subscheme of ℙ³. For almost all such schemes the graded Betti numbers in ℙ³ depend only on the Hilbert function ofX in ℙ³. Work done with financial support of M.U.R.S.T., while the authors were members of C.N.R.     

Functions with slowly-growing area and harmonic majorants

Letf be a function holomorphic inU={|z|<1}, and letA(R,f) be the area off(U)∩{|w|<R}, not counting multiplicities. IfA(R,f)=O(R ^γ) asR→∞ for a γ, 0≦γ<2, then the subharmonic function exp |f| ^p has a harmonic majorant inU for eachp, 0<p<2−γ. If 0≦γ<1 further, thene ^f is of Hardy classH ^p for eachp, 0<p<∞.     

The subalgebra systems of direct powers

A simple characterization of the subalgebra systems of direct powers of finitary universal algebras on a fixed infinite setA is given. For |I|≥|A| such subalgebra system of anI-power is precisely an algebraic closure systemS onA ^I closed under mutations ofI (which encompass both the precomposition by permutations ofI and allowing the values at specified elements ofI to become unrestricted) and such that each function in the intersection ofS is constant. For |I|<|A| the subalgebra systems ofI-powers are obtained as the restrictions toI of such closure systems on someA ^J withJ⊇I and |J|=|A|. Presented by J. D. Monk.     

Concerning the Sierpinski-Schinzel system of Diophantine equations

It is proved that the equation (x ²−1)(y ²−1)=(z ²−1)², |x|≠|y|, |z|≠1, is not solvable in integersx,y,z under the conditionx−y=kz, wherek is a positive integer different from 2. Translated fromMatematicheskie Zametki, Vol. 66, No. 2, pp. 181–187, August, 1999.     

Additive Latin transversals and group rings

LetA={a ₁, …,a _k} and {b ₁, …,b _k} be two subsets of an abelian groupG, k≤|G|. Snevily conjectured that, when |G| is odd, there is a numbering of the elements ofB such thata _i+b _i,1≤i≤k are pairwise distinct. By using a polynomial method, Alon affirmed this conjecture for |G| prime, even whenA is a sequence ofk<|G| elements. With a new application of the polynomial method, Dasgupta, Károlyi, Serra and Szegedy extended Alon’s result to the groupsZ _p ^r andZ _p ^rin the casek<p and verified Snevily’s conjecture for every cyclic group. In this paper, by employing group rings as a tool, we prove that Alon’s result is true for any finite abelianp-group withk<√2p, and verify Snevily’s conjecture for every abelian group of odd order in the casek<√p, wherep is the smallest prime divisor of |G|. This work has been supported partly by NSFC grant number 19971058 and 10271080.     

Growth and Hölder conditions for the sample paths of Feller processes

Let (A,D(A)) be the infinitesimal generator of a Feller semigroup such that C _c ^∞(ℝ ⁿ )⊂D(A) and A|C _c ^∞(ℝ ⁿ ) is a pseudo-differential operator with symbol −p(x,ξ) satisfying |p(•,ξ)|_∞≤c(1+|ξ|²) and |Imp(x,ξ)|≤c ₀Rep(x,ξ). We show that the associated Feller process {X _t } _{t ≥0} on ℝ ⁿ is a semimartingale, even a homogeneous diffusion with jumps (in the sense of [21]), and characterize the limiting behaviour of its trajectories as t→0 and ∞. To this end, we introduce various indices, e.g., β_∞ ^x :={λ>0:lim _{|ξ|→∞ | x − y |≤2/|ξ|}|p(y,ξ)|/|ξ|^λ=0} or δ_∞ ^x :={λ>0:liminf _{|ξ|→∞ | x − y |≤2/|ξ| |ε|≤1}|p(y,|ξ|ε)|/|ξ|^λ=0}, and obtain a.s. (ℙ ^x ) that lim _{t →0} t ^−1/λ _{s ≤ t} |X _s −x|=0 or ∞ according to λ>β_∞ ^x or λ<δ_∞ ^x . Similar statements hold for the limit inferior and superior, and also for t→∞. Our results extend the constant-coefficient (i.e., Lévy) case considered by W. Pruitt [27]. Received: 21 July 1997 / Revised version: 26 January 1998     

Asymptotic behaviour of trajectories of unipotent flows on homogeneous spaces

We show that ifG is a semisimple algebraic group defined overQ and Γ is an arithmetic lattice inG:=G _R with respect to theQ-structure, then there exists a compact subsetC ofG/Γ such that, for any unipotent one-parameter subgroup {u _t} ofG and anyg∈G, the time spent inC by the {u _t}-trajectory ofgΓ, during the time interval [0,T], is asymptotic toT, unless {g ⁻¹u_tg} is contained in aQ-parabolic subgroup ofG. Some quantitative versions of this are also proved. The results strengthen similar assertions forSL(n,Z),n≥2, proved earlier in [5] and also enable verification of a technical condition introduced in [7] for lattices inSL(3,R), which was used in our proof of Raghunathan’s conjecture for a class of unipotent flows, in [8].     

Two cardinal compactness

We prove that ifλ≧μ ^ℵo=μ≧|T | and if every finite subtheory ofT has a (λ, μ)-model (i.e. a model with a domain of powerλ, in which a distinguished predicate is interpreted as a set ofμ elements) thenT has such a model. There are generalizations forμ-like models (or, equivalently, to languages with generalized quantifiers).