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 .

     

Random polynomials with prescribed Newton polytope

The Newton polytope of a polynomial is well known to have a strong impact on its behavior. The Bernstein-Kouchnirenko Theorem asserts that even the number of simultaneous zeros in of a system of polynomials depends on their Newton polytopes. In this article, we show that Newton polytopes also have a strong impact on the distribution of zeros and pointwise norms of polynomials, the basic theme being that Newton polytopes determine allowed and forbidden regions in for these distributions.

Our results are statistical and asymptotic in the degree of the polynomials. We equip the space of polynomials of degree in complex variables with its usual SU-invariant Gaussian probability measure and then consider the conditional measure induced on the subspace of polynomials with fixed Newton polytope . We then determine the asymptotics of the conditional expectation of simultaneous zeros of polynomials with Newton polytope as . When , the unit simplex, it is clear that the expected zero distributions are uniform relative to the Fubini-Study form. For a convex polytope , we show that there is an allowed region on which is asymptotically uniform as the scaling factor . However, the zeros have an exotic distribution in the complementary forbidden region and when (the case of the Bernstein-Kouchnirenko Theorem), the expected percentage of simultaneous zeros in the forbidden region approaches 0 as .

     

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 .

     

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.

     

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.

     

On intervals in subgroup lattices of finite groups

We investigate the question of which finite lattices are isomorphic to the lattice of all overgroups of a subgroup in a finite group . We show that the structure of is highly restricted if is disconnected. We define the notion of a ``signalizer lattice" in and show for suitable disconnected lattices , if is minimal subject to being isomorphic to or its dual, then either is almost simple or admits a signalizer lattice isomorphic to or its dual. We use this theory to answer a question in functional analysis raised by Watatani.

     

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 .

     

Hilbert's Tenth Problem and Mazur's Conjecture for large subrings of

We give the first examples of infinite sets of primes such that Hilbert's Tenth Problem over has a negative answer. In fact, we can take to be a density 1 set of primes. We show also that for some such there is a punctured elliptic curve over such that the topological closure of in has infinitely many connected components.

     

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.

     

Pythagoras numbers of fields

A field of characteristic is said to have finite Pythagoras number if there exists an integer such that each nonzero sum of squares in can be written as a sum of squares, in which case the Pythagoras number of is defined to be the least such integer. As a consequence of Pfister's results on the level of fields, of a nonformally real field is always of the form or , and all integers of such type can be realized as Pythagoras numbers of nonformally real fields. Prestel showed that values of the form , , and can always be realized as Pythagoras numbers of formally real fields. We will show that in fact to every integer there exists a formally real field with . As a refinement, we will show that if and are integers such that , then there exists a uniquely ordered field with and (resp. ), where (resp. ) denotes the supremum of the dimensions of anisotropic forms over which are torsion in the Witt ring of (resp. which are indefinite with respect to each ordering on ).

     

Generalized group characters and complex oriented cohomology theories

Let be the classifying space of a finite group . Given a multiplicative cohomology theory , the assignment

is a functor from groups to rings, endowed with induction (transfer) maps. In this paper we investigate these functors for complex oriented cohomology theories , using the theory of complex representations of finite groups as a model for what one would like to know.

An analogue of Artin's Theorem is proved for all complex oriented : the abelian subgroups of serve as a detecting family for , modulo torsion dividing the order of .

When is a complete local ring, with residue field of characteristic and associated formal group of height , we construct a character ring of class functions that computes . The domain of the characters is , the set of -tuples of elements in each of which has order a power of . A formula for induction is also found. The ideas we use are related to the Lubin-Tate theory of formal groups. The construction applies to many cohomology theories of current interest: completed versions of elliptic cohomology, -theory, etc.

The th Morava K-theory Euler characteristic for is computed to be the number of -orbits in . For various groups , including all symmetric groups, we prove that is concentrated in even degrees.

Our results about extend to theorems about , where is a finite -CW complex.

     

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.     

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 .

     

Quasisymmetric groups

One of the first problems in the theory of quasisymmetric and convergence groups was to investigate whether every quasisymmetric group that acts on the sphere , , is a quasisymmetric conjugate of a Möbius group that acts on . This was shown to be true for by Sullivan and Tukia, and it was shown to be wrong for by Tukia. It also follows from the work of Martin and of Freedman and Skora. In this paper we settle the case of by showing that any -quasisymmetric group is -quasisymmetrically conjugated to a Möbius group. The constant is a function .

     

Criteria for -ampleness

In the noncommutative geometry of Artin, Van den Bergh, and others, the twisted homogeneous coordinate ring is one of the basic constructions. Such a ring is defined by a -ample divisor, where is an automorphism of a projective scheme . Many open questions regarding -ample divisors have remained.

We derive a relatively simple necessary and sufficient condition for a divisor on to be -ample. As a consequence, we show right and left -ampleness are equivalent and any associated noncommutative homogeneous coordinate ring must be noetherian and have finite, integral GK-dimension. We also characterize which automorphisms yield a -ample divisor.

     

Quantum groups, the loop Grassmannian, and the Springer resolution

We establish equivalences of the following three triangulated categories:

Here, is the derived category of the principal block of finite-dimensional representations of the quantized enveloping algebra (at an odd root of unity) of a complex semisimple Lie algebra ; the category is defined in terms of coherent sheaves on the cotangent bundle on the (finite-dimensional) flag manifold for ( semisimple group with Lie algebra ), and the category is the derived category of perverse sheaves on the Grassmannian associated with the loop group , where is the Langlands dual group, smooth along the Schubert stratification.

The equivalence between and is an ``enhancement' of the known expression (due to Ginzburg and Kumar) for quantum group cohomology in terms of nilpotent variety. The equivalence between and can be viewed as a ``categorification' of the isomorphism between two completely different geometric realizations of the (fundamental polynomial representation of the) affine Hecke algebra that has played a key role in the proof of the Deligne-Langlands-Lusztig conjecture. One realization is in terms of locally constant functions on the flag manifold of a -adic reductive group, while the other is in terms of equivariant -theory of a complex (Steinberg) variety for the dual group.

The composite of the two equivalences above yields an equivalence between abelian categories of quantum group representations and perverse sheaves. A similar equivalence at an even root of unity can be deduced, following the Lusztig program, from earlier deep results of Kazhdan-Lusztig and Kashiwara-Tanisaki. Our approach is independent of these results and is totally different (it does not rely on the representation theory of Kac-Moody algebras). It also gives way to proving Humphreys' conjectures on tilting -modules, as will be explained in a separate paper.     

On the singularity probability of random Bernoulli matrices

Let be a large integer and let be a random matrix whose entries are i.i.d. Bernoulli random variables (each entry is with probability ). We show that the probability that is singular is at most , improving an earlier estimate of Kahn, Komlós and Szemerédi, as well as earlier work by the authors. The key new ingredient is the applications of Freiman-type inverse theorems and other tools from additive combinatorics.

     

The enumerative geometry of surfaces and modular forms

Let be a surface, and let be a holomorphic curve in representing a primitive homology class. We count the number of curves of geometric genus with nodes passing through generic points in in the linear system for any and satisfying .

When , this coincides with the enumerative problem studied by Yau and Zaslow who obtained a conjectural generating function for the numbers. Recently, Göttsche has generalized their conjecture to arbitrary in terms of quasi-modular forms. We prove these formulas using Gromov-Witten invariants for families, a degeneration argument, and an obstruction bundle computation. Our methods also apply to blown up at 9 points where we show that the ordinary Gromov-Witten invariants of genus constrained to points are also given in terms of quasi-modular forms.     

Hilbert schemes, polygraphs and the Macdonald positivity conjecture

We study the isospectral Hilbert scheme , defined as the reduced fiber product of with the Hilbert scheme of points in the plane , over the symmetric power . By a theorem of Fogarty, is smooth. We prove that is normal, Cohen-Macaulay and Gorenstein, and hence flat over . We derive two important consequences.

(1) We prove the strong form of the conjecture of Garsia and the author, giving a representation-theoretic interpretation of the Kostka-Macdonald coefficients . This establishes the Macdonald positivity conjecture, namely that .

(2) We show that the Hilbert scheme is isomorphic to the -Hilbert scheme of Nakamura, in such a way that is identified with the universal family over . From this point of view, describes the fiber of a character sheaf at a torus-fixed point of corresponding to .

The proofs rely on a study of certain subspace arrangements , called polygraphs, whose coordinate rings carry geometric information about . The key result is that is a free module over the polynomial ring in one set of coordinates on . This is proven by an intricate inductive argument based on elementary commutative algebra.