Uniformity over primes of tamely ramified splittings

We fix a prime p and let f(X) vary over all monic integer polynomials of fixed degree n. Given any possible shape of a tamely ramified splitting of p in an extension of degree n, we prove that there exists a rational function φ(X)∈ℚ(X) such that the density of the monic integer polynomials f(X) for which the splitting of p has the given shape in ℚ[X]/f(X) is φ(p) (here reducible polynomials can be neglected). As a corollary, we prove that, for p≥n, the density of irreducible monic polynomials of degree n in ℤ _p [X] is the value at p of a rational function φ _n (X)∈ℚ(X). All rational functions involved are effectively computable. Received: 15 September 1998 / Revised version: 21 October 1999     

Some results on distance two labelling of outerplanar graphs

Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.     

Some Elements of Finite Order in K2Q

Let K2 be the Milnor functor and let Фn （x）∈ Q[X] be the n-th cyclotomic polynomial. Let Gn（Q） denote a subset consisting of elements of the form {a, Фn（a）}, where a ∈ Q^＊ and {, } denotes the Steinberg symbol in K2Q. J. Browkin proved that Gn（Q） is a subgroup of K2Q if n = 1,2, 3, 4 or 6 and conjectured that Gn（Q） is not a group for any other values of n. This conjecture was confirmed for n =2^T 3S or n = p^r, where p ≥ 5 is a prime number such that h（Q（ζp）） is not divisible by p. In this paper we confirm the conjecture for some n, where n is not of the above forms, more precisely, for n = 15, 21,33, 35, 60 or 105.     

The cup product of Hilbert schemes for K3 surfaces

To any graded Frobenius algebra A we associate a sequence of graded Frobenius algebras A ^[n] so that there is canonical isomorphism of rings (H ^*(X;ℚ)[2]) ^[n] ≅H ^*(X ^[n] ;ℚ)[2n] for the Hilbert scheme X ^[n] of generalised n-tuples of any smooth projective surface X with numerically trivial canonical bundle. Oblatum 25-I-2001 & 18-IX-2002?Published online: 24 February 2003     

Cyclotomic and simplicial matroids

We show that two naturally occurring matroids representable over ℚ are equal: thecyclotomic matroid μ_n represented by then ^th roots of unity 1, ζ, ζ², …, ζ^n-1 inside the cyclotomic extension ℚ(ζ), and a direct sum of copies of a certain simplicial matroid, considered originally by Bolker in the context of transportation polytopes. A result of Adin leads to an upper bound for the number of ℚ-bases for ℚ(ζ) among then ^th roots of unity, which is tight if and only ifn has at most two odd prime factors. In addition, we study the Tutte polynomial of μ_n in the case thatn has two prime factors. First author supported by NSF Postdoctoral Fellowship. Second author supported by NSF grant DMS-0245379.     

Large Distinct Part Sizes in a Random Integer Partition

Let Y _s,n denote the number of part sizes ≧ s in a random and uniform partition of the positive integer n that are counted without multiplicity. For s = λ(6n)^1/2/π + o(n ^1/4), 0 ≦ λ < ∞, as n → ∞, we establish the weak convergence of Y _s,n to a Gaussian distribution in the form of a central limit theorem. The mean and the standard deviation are also asymptotically determined. This revised version was published online in June 2006 with corrections to the Cover Date.     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05     

Finding rational points on bielliptic genus 2 curves

We discuss a technique for trying to find all rational points on curves of the form Y ²=f ₃ X ⁶+f ₂ X ⁴+f ₁ X ²+f ₀, where the sextic has nonzero discriminant. This is a bielliptic curve of genus 2. When the rank of the Jacobian is 0 or 1, Chabauty's Theorem may be applied. However, we shall concentrate on the situation when the rank is at least 2. In this case, we shall derive an associated family of elliptic curves, defined over a number field ℚα. If each of these elliptic curves has rank less than the degree of ℚα : ℚ, then we shall describe a Chabauty-like technique which may be applied to try to find all the points (x,y) defined over ℚα) on the elliptic curves, for which x∈ℚ. This in turn allows us to find all ℚ-rational points on the original genus 2 curve. We apply this to give a solution to a problem of Diophantus (where the sextic in X is irreducible over ℚ), which simplifies the recent solution of Wetherell. We also present two examples where the sextic in X is reducible over ℚ. Received: 27 November 1998 / Revised version: 4 June 1999     

Generating Uniform Random Vectors in Z p k : The General Case

We consider the rate of convergence of the Markov chain X _n+1=A X _n +B _n (mod p), where A is an integer matrix with nonzero eigenvalues, and {B _n } _n is a sequence of independent and identically distributed integer vectors, with support not parallel to a proper subspace of Q ^k invariant under A. If for all eigenvalues λ _i of A, then n=O((ln p)²) steps are sufficient and n=O(ln p) steps are necessary to have X _n sampling from a nearly uniform distribution. Conversely, if A has the eigenvalues λ _i that are roots of positive integer numbers, |λ ₁|=1 and |λ _i |>1 for all , then O(p ²) steps are necessary and sufficient.      

Uniform boundedness of level structures on abelian varieties over complex function fields

Let X = Ω/Γ be a smooth quotient of a bounded symmetric domain Ω by an arithmetic subgroup . We prove the following generalization of Nadel's result: for any non-negative integer g, there exists a finite étale cover X_g = Ω/Γ(g) of X determined by a subgroup depending only on g, such that for any compact Riemann surface R of genus g and any non-constant holomorphic map f : R → X_g^* from R into the Satake-Baily-Borel compactification X_g^* of X_g, the image f(R) lies in the boundary ∂X_g: = X^*_g\X_g. Nadel proved it for g = 0 or 1. Moreover, for any positive integer n and any non-negative integer g≥0, we show that there exists a positive number a(n,g) depending only on n and g with the following property: a principally polarized non-isotrivial n-dimensional abelian variety over a complex function field of genus g does not have a level-N structure for N≥a(n,g). This was proved by Nadel for g = 0 or 1, and by Noguchi for arbitrary g under the additional hypothesis that the abelian variety has non-empty singular fibers.     

New series of odd non-congruent numbers

We determine all square-free odd positive integers n such that the 2-Selmer groups S _n and Ŝ _n of the elliptic curve E _n : y ² = x(x − n)(x − 2n) and its dual curve ê _n : y ² = x ³ + 6nx ² + n ² x have the smallest size: S _n = {1}, Ŝ _n = {1, 2, n, 2n}. It is well known that for such integer n, the rank of group E _n (ℚ) of the rational points on E _n is zero so that n is a non-congruent number. In this way we obtain many new series of elliptic curves E _n with rank zero and such series of integers n are non-congruent numbers. Dedicated to Professor Sheng GONG on the occasion of his 75th birthday     

Many partition relations below density

We force 2 ^λ to be large, and for many pairs in the interval (λ, 2 ^λ ) a strong version of the polarized partition relations holds. We apply this to problems in general topology. For example, consistently, every 2 ^λ is the successor of a singular and for every Hausdorff regular space X, hd(X) ≤ s(X)⁺³, hL(X) ≤ s(X)⁺³ and better when s(X) is regular, via a halfgraph partition relations. For the case s(X) = ℵ ₀ we get hd(X), hL(X) ≤ N ₂.     

Moderate Deviations for Random Sums of Heavy-Tailed Random Variables

Let {Xn;n≥ 1} be a sequence of independent non-negative random variables with common distribution function F having extended regularly varying tail and finite mean μ = E（X1） and let {N（t）; t ≥0} be a random process taking non-negative integer values with finite mean λ（t） = E（N（t）） and independent of {Xn; n ≥1}. In this paper, asymptotic expressions of P（（X1 ＋… ＋XN（t）） -λ（t）μ 〉 x） uniformly for x ∈[γb（t）, ∞） are obtained, where γ〉 0 and b（t） can be taken to be a positive function with limt→∞ b（t）/λ（t） = 0.     

The Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite

Let X be a normed space that satisfies the Johnson–Lindenstrauss lemma (J–L lemma, in short) in the sense that for any integer n and any x ₁,…,x _n ∈X, there exists a linear mapping L:X→F, where F⊆X is a linear subspace of dimension O(log n), such that ‖x _i −x _j ‖≤‖L(x _i )−L(x _j )‖≤O(1)⋅‖x _i −x _j ‖ for all i,j∈{1,…,n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion 2^2O(log*n)2^{2^{O(\log^{*}n)}} . On the other hand, we show that there exists a normed space Y which satisfies the J–L lemma, but for every n, there exists an n-dimensional subspace E _n ⊆Y whose Euclidean distortion is at least 2^Ω(α(n)), where α is the inverse Ackermann function.     

Explicit Classification for Torsion Subgroups of Rational Points of Elliptic Curves

We study the classification of elliptic curves E over the rationals ℚ according to the torsion sugroups E _tors(ℚ). More precisely, we classify those elliptic curves with E _tors(ℚ) being cyclic with even orders. We also give explicit formulas for generators of E _tors(ℚ). These results, together with the recent results of K. Ono for the non-cyclic E _tors(ℚ), completely solve the problem of the explicit classification and parameterization when E has a rational point of order 2. Received July 29, 1999, Revised March 9, 2001, Accepted July 20, 2001     

Hausdorff operator of special kind on <Emphasis Type="Italic">p</Emphasis>-adic field and <Emphasis Type="Italic">BMO</Emphasis>-type spaces

For Hausdorff operator with generating function having support in the unit ball of p-adic field ℚ _p we give sufficient and necessary conditions of its boundedness in BMO-type spaces: BLO(ℚ _p ⁿ ), Q _r ^α,q (ℚ _p ⁿ ) and BMO _r ^α,q (ℚ _p ⁿ ). Some embedding relations between these spaces and Besov spaces are established.     

On K 1,k -factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

On graded quotient modules of mapping class groups of surfaces

Let Γ _{g, n} be the mapping class group of a compact Riemann surface of genusg withn points preserved (2−2g−n<0,g≥1,n≥0). The Torelli subgroup of Γ _{g, n} has a natural weight filtration {Γ_{g, n}(m)} _m≥1. Each graded quotient gr ^m Γ _{g, n} ⊗ ℚ (m≥1) is a finite dimensional vector space over ℚ on which the group Sp(2g, ℚ)×S _n naturally acts. In this paper, we have determined the Sp(2g, ℚ)×S _n module structure of gr ^m Γ _{g, n} ⊗ ℚ for 1≤m≤3. This includes a verification of an expectation by S. Morita. Also, for generalm, we have identified a certain Sp(2g, ℚ)-irreducible component of gr ^m Γ _{g, n} ⊗ ℚ by constructing explicitly elements in these modules.