On the size of -fold sum and product sets of integers

In this paper, we show that for all 1$"> there is a positive integer such that if is an arbitrary finite set of integers, 2$">, then either N^{b}$"> or N^{b}$">. Here (resp. ) denotes the -fold sum (resp. product) of . This fact is deduced from the following harmonic analysis result obtained in the paper. For all 2$"> and 0$">, there is a 0$"> such that if satisfies , then the -constant of (in the sense of W. Rudin) is at most .

     

Independence of of monodromy groups

Let be a smooth curve over a finite field of characteristic , let be a number field, and let be an -compatible system of lisse sheaves on the curve . For each place of not lying over , the -component of the system is a lisse -sheaf on , whose associated arithmetic monodromy group is an algebraic group over the local field . We use Serre's theory of Frobenius tori and Lafforgue's proof of Deligne's conjecture to show that when the -compatible system is semisimple and pure of some integer weight, the isomorphism type of the identity component of these monodromy groups is ``independent of '. More precisely, after replacing by a finite extension, there exists a connected split reductive algebraic group over the number field such that for every place of not lying over , the identity component of the arithmetic monodromy group of is isomorphic to the group with coefficients extended to the local field .

     

An uncountable family of nonorbit equivalent actions of

For each , we construct an uncountable family of free ergodic measure preserving actions of the free group on the standard probability space such that any two are nonorbit equivalent (in fact, not even stably orbit equivalent). These actions are all ``rigid' (in the sense of Popa), with the IIfactors mutually nonisomorphic (even nonstably isomorphic) and in the class

     

The threshold for random -SAT is

Let be a random -CNF formula formed by selecting uniformly and independently out of all possible -clauses on variables. It is well known that if , then is unsatisfiable with probability that tends to 1 as . We prove that if , where , then is satisfiable with probability that tends to 1 as .

Our technique, in fact, yields an explicit lower bound for the random -SAT threshold for every . For our bounds improve all previously known such bounds.

     

Topology of symplectomorphism groups of rational ruled surfaces

Let be either or the one point blow-up of . In both cases carries a family of symplectic forms , where -1$"> determines the cohomology class . This paper calculates the rational (co)homology of the group of symplectomorphisms of as well as the rational homotopy type of its classifying space . It turns out that each group contains a finite collection , of finite dimensional Lie subgroups that generate its homotopy. We show that these subgroups ``asymptotically commute", i.e. all the higher Whitehead products that they generate vanish as . However, for each fixed there is essentially one nonvanishing product that gives rise to a ``jumping generator" in and to a single relation in the rational cohomology ring . An analog of this generator was also seen by Kronheimer in his study of families of symplectic forms on -manifolds using Seiberg-Witten theory. Our methods involve a close study of the space of -compatible almost complex structures on .

     

Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients

Let be a quiver without oriented cycles. For a dimension vector let be the set of representations of with dimension vector . The group acts on . In this paper we show that the ring of semi-invariants is spanned by special semi-invariants associated to representations of . From this we show that the set of weights appearing in is saturated. In the case of triple flag quiver this reduces to the results of Knutson and Tao on the saturation of the set of triples of partitions for which the Littlewood-Richardson coefficient is nonzero.

     

The essentially tame local Langlands correspondence, I

Let be a non-Archimedean local field (of characteristic or ) with finite residue field of characteristic . An irreducible smooth representation of the Weil group of is called essentially tame if its restriction to wild inertia is a sum of characters. The set of isomorphism classes of irreducible, essentially tame representations of dimension is denoted . The Langlands correspondence induces a bijection of with a certain set of irreducible supercuspidal representations of . We consider the set of isomorphism classes of certain pairs , called ``admissible', consisting of a tamely ramified field extension of degree and a quasicharacter of . There is an obvious bijection of with . Using the classification of supercuspidal representations and tame lifting, we construct directly a canonical bijection of with , generalizing and simplifying a construction of Howe (1977). Together, these maps give a canonical bijection of with . We show that one obtains the Langlands correspondence by composing the map with a permutation of of the form , where is a tamely ramified character of depending on . This answers a question of Moy (1986). We calculate the character in the case where is totally ramified of odd degree.

     

Zeta function of representations of compact -adic analytic groups

Let be an FAb compact -adic analytic group and suppose that 2$"> or and is uniform. We prove that there are natural numbers and functions rational in such that

     

On a correspondence between cuspidal representations of

Let be an irreducible, automorphic, self-dual, cuspidal representation of , where is the adele ring of a number field . Assume that has a pole at and that . Given a nontrivial character of , we construct a nontrivial space of genuine and globally -generic cusp forms on -the metaplectic cover of . is invariant under right translations, and it contains all irreducible, automorphic, cuspidal (genuine) and -generic representations of , which lift (``functorially, with respect to ") to . We also present a local counterpart. Let be an irreducible, self-dual, supercuspidal representation of , where is a -adic field. Assume that has a pole at . Given a nontrivial character of , we construct an irreducible, supercuspidal (genuine) -generic representation of , such that has a pole at , and we prove that is the unique representation of satisfying these properties.

     

Global existence for energy critical waves in -d domains

We prove that the defocusing quintic wave equation, with Dirichlet boundary conditions, is globally well posed on for any smooth (compact) domain . The main ingredient in the proof is an spectral projector estimate, obtained recently by Smith and Sogge, combined with a precise study of the boundary value problem.

     

A solution to the L space problem

In this paper I will construct a non-separable hereditarily Lindelöf space (L space) without any additional axiomatic assumptions. The constructed space is a subspace of where is the unit circle. It is shown to have a number of properties which may be of additional interest. For instance it is shown that the closure in of any uncountable subset of contains a canonical copy of .

I will also show that there is a function such that if are uncountable and , then there are in and respectively with . Previously it was unknown whether such a function existed even if was replaced by . Finally, I will prove that there is no basis for the uncountable regular Hausdorff spaces of cardinality .

The results all stem from the analysis of oscillations of coherent sequences of finite-to-one functions. I expect that the methods presented will have other applications as well.

     

Presentations of finite simple groups: A quantitative approach

There is a constant such that all nonabelian finite simple groups of rank over , with the possible exception of the Ree groups , have presentations with at most generators and relations and total length at most . As a corollary, we deduce a conjecture of Holt: there is a constant such that for every finite simple group , every prime and every irreducible -module .

     

Représentations -adiques et normes universelles I. Le cas cristallin

Let be a crystalline -adic representation of the absolute Galois group of an finite unramified extension of , and let be a lattice of stable by . We prove the following result: Let be the maximal sub-representation of with Hodge-Tate weights strictly positive and . Then, the projective limit of is equal up to torsion to the projective limit of . So its rank over the Iwasawa algebra is .

     

On the number of zero-patterns of a sequence of polynomials

Let be a sequence of polynomials of degree in variables over a field . The zero-pattern of at is the set of those ( ) for which . Let denote the number of zero-patterns of as ranges over . We prove that for and

for . For , these bounds are optimal within a factor of . The bound () improves the bound proved by J. Heintz (1983) using the dimension theory of affine varieties. Over the field of real numbers, bounds stronger than Heintz's but slightly weaker than () follow from results of J. Milnor (1964), H.E.  Warren (1968), and others; their proofs use techniques from real algebraic geometry. In contrast, our half-page proof is a simple application of the elementary ``linear algebra bound'.

Heintz applied his bound to estimate the complexity of his quantifier elimination algorithm for algebraically closed fields. We give several additional applications. The first two establish the existence of certain combinatorial objects. Our first application, motivated by the ``branching program' model in the theory of computing, asserts that over any field , most graphs with vertices have projective dimension (the implied constant is absolute). This result was previously known over the reals (Pudlák-Rödl). The second application concerns a lower bound in the span program model for computing Boolean functions. The third application, motivated by a paper by N. Alon, gives nearly tight Ramsey bounds for matrices whose entries are defined by zero-patterns of a sequence of polynomials. We conclude the paper with a number of open problems.

     

Orbit equivalence for Cantor minimal -systems

We show that every minimal, free action of the group on the Cantor set is orbit equivalent to an AF-relation. As a consequence, this extends the classification of minimal systems on the Cantor set up to orbit equivalence to include AF-relations, -actions and -actions.

     

Conformal restriction: The chordal case

We characterize and describe all random subsets of a given simply connected planar domain (the upper half-plane , say) which satisfy the ``conformal restriction' property, i.e., connects two fixed boundary points ( and , say) and the law of conditioned to remain in a simply connected open subset of is identical to that of , where is a conformal map from onto with and . The construction of this family relies on the stochastic Loewner evolution processes with parameter and on their distortion under conformal maps. We show in particular that SLE is the only random simple curve satisfying conformal restriction and we relate it to the outer boundaries of planar Brownian motion and SLE.     

boundedness of discrete singular Radon transforms

We prove that if is a Calderón-Zygmund kernel and is a polynomial of degree with real coefficients, then the discrete singular Radon transform operator

extends to a bounded operator on , . This gives a positive answer to an earlier conjecture of E. M. Stein and S. Wainger.

     

Simple homogeneous models

Geometrical stability theory is a powerful set of model-theoretic tools that can lead to structural results on models of a simple first-order theory. Typical results offer a characterization of the groups definable in a model of the theory. The work is carried out in a universal domain of the theory (a saturated model) in which the Stone space topology on ultrafilters of definable relations is compact. Here we operate in the more general setting of homogeneous models, which typically have noncompact Stone topologies. A structure equipped with a class of finitary relations is strongly -homogeneous if orbits under automorphisms of have finite character in the following sense: Given an ordinal and sequences , from , if and have the same orbit, for all and , then for some automorphism of . In this paper strongly -homogeneous models in which the elements of induce a symmetric and transitive notion of independence with bounded character are studied. This notion of independence, defined using a combinatorial condition called ``dividing', agrees with forking independence when is saturated. A concept central to the development of stability theory for saturated structures, namely parallelism, is also shown to be well-behaved in this setting. These results broaden the scope of the methods of geometrical stability theory.

     

Weakly null sequences in

We construct a weakly null normalized sequence in so that for each , the Haar basis is -equivalent to a block basis of every subsequence of . In particular, the sequence has no unconditionally basic subsequence. This answers a question raised by Bernard Maurey and H. P. Rosenthal in 1977. A similar example is given in an appropriate class of rearrangement invariant function spaces.