A proof of the q,t-Catalan positivity conjecture

We present here a proof that a certain rational function C_n(q,t) which has come to be known as the “q,t-Catalan” is in fact a polynomial with positive integer coefficients. This has been an open problem since 1994. The precise form of the conjecture is given in Garsia and Haiman (J. Algebraic Combin. 5(3) (1996) 191), where it is further conjectured that C_n(q,t) is the Hilbert series of the diagonal harmonic alternants in the variables (x₁,x₂,…,x_n;y₁,y₂,…,y_n). Since C_n(q,t) evaluates to the Catalan number at t=q=1, it has also been an open problem to find a pair of statistics a(π),b(π) on Dyck paths π in the n×n square yielding C_n(q,t)=∑_πt^a(π)q^b(π). Our proof is based on a recursion for C_n(q,t) suggested by a pair of statistics a(π),b(π) recently proposed by Haglund. Thus, one of the byproducts of our developments is a proof of the validity of Haglund's conjecture. It should also be noted that our arguments rely and expand on the plethystic machinery developed in Bergeron et al. (Methods and Applications of Analysis, Vol. VII(3), 1999, p. 363).     

q-Catalan numbers

q-analogs of the Catalan numbers C_n = (1/(n + 1))(_n²ⁿ) are studied from the view-point of Lagrange inversion. The first, due to Carlitz, corresponds to the Andrews-Gessel-Garsia q-Lagrange inversion theory, satisfies a nice recurrence relation and counts inversions of Catalan words. The second, tracing back to Mac Mahon, arise from Krattenthaler's and Gessel and Stanton's q-Lagrange inversion formula, have a nice explicit formula and enumerate the major index. Finally a joint generalization is given which includes also the Polya-Gessel q-Catalan numbers.     

Fluctuations of the empirical quantiles of independent Brownian motions

We consider iid Brownian motions, B_j(t), where B_j(0) has a rapidly decreasing, smooth density function f. The empirical quantiles, or pointwise order statistics, are denoted by B_j:n(t), and we consider a sequence Q_n(t)=B_j(n):n(t), where j(n)/n→α∈(0,1). This sequence converges in probability to q(t), the α-quantile of the law of B_j(t). We first show convergence in law in C[0,∞) of F_n=n^1/2(Q_n−q). We then investigate properties of the limit process F, including its local covariance structure, and Hölder-continuity and variations of its sample paths. In particular, we find that F has the same local properties as fBm with Hurst parameter H=1/4.     

Twisted inner products and contraction inequalities on spaces of contravariant and covariant tensors

Given positive integers n and p, and a complex finite dimensional vector space V, we let S_n,p(V) denote the set of all functions from V×V×?×V-(n+p copies) to C that are linear and symmetric in the first n positions, and conjugate linear symmetric in the last p positions. Letting κ=min{n,p} we introduce twisted inner products, [·,·]_s,t,1?s,t?κ, on S_n,p(V), and prove the monotonicity condition [F,F]_s,t?[F,F]_u,v is satisfied when s?u?κ,t?v?κ, and F∈S_n,p(V). Using the monotonicity condition, and the Cauchy-Schwartz inequality, we obtain as corollaries many known inequalities involving norms of symmetric multilinear functions, which in turn imply known inequalities involving permanents of positive semidefinite Hermitian matrices. New tensor and permanental inequalities are also presented. Applications to partial differential equations are indicated.     

A p, q-Analogue of the Generalized Derangement Numbers

In this paper, we study the numbers D _n,k which are defined as the number of permutations σ of the symmetric group S _n such that σ has no cycles of length j for j ≤ k. In the case k = 1, D _n,1 is simply the number of derangements of an n-element set. As such, we shall call the numbers D _n,k generalized derangement numbers. Garsia and Remmel [4] defined some natural q-analogues of D _n,1, denoted by D _n,1(q), which give rise to natural q-analogues of the two classical recursions of the number of derangements. The method of Garsia and Remmel can be easily extended to give natural p, q-analogues D _n,1(p, q) which satisfy natural p, q-analogues of the two classical recursions for the number of derangements. In [4], Garsia and Remmel also suggested an approach to define q-analogues of the numbers D _n,k . In this paper, we show that their ideas can be extended to give a p, q-analogue of the generalized derangements numbers. Again there are two classical recursions for eneralized derangement numbers. However, the p, q-analogues of the two classical recursions are not as straightforward when k ≥ 2. Partially supported by NSF grant DMS 0400507.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

On tricyclic graphs of a given diameter with minimal energy

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. Let G(n,d) be the class of tricyclic graphs G on n vertices with diameter d and containing no vertex disjoint odd cycles C_p,C_q of lengths p and q with p+q≡2(mod4). In this paper, we characterize the graphs with minimal energy in G(n,d).     

On the variation of Tate-Shafarevich groups of elliptic curves over hyperelliptic curves

Let E be an elliptic curve over F=F_q(t) having conductor (p)·∞, where (p) is a prime ideal in F_q[t]. Let d∈F_q[t] be an irreducible polynomial of odd degree, and let . Assume (p) remains prime in K. We prove the analogue of the formula of Gross for the special value L(E⊗_FK,1). As a consequence, we obtain a formula for the order of the Tate-Shafarevich group Ш(E/K) when L(E⊗_FK,1)≠0.     

The Eulerian generating function of q-derangements

Let F_q denote the finite field with q elements. For nonnegative integers n,k, let d_q(n,k) denote the number of n×nF_q-matrices having k as the sum of the dimensions of the eigenspaces (of the eigenvalues lying in F_q). Let d_q(n)=d_q(n,0), i.e., d_q(n) denotes the number of n×nF_q-matrices having no eigenvalues in F_q. The Eulerian generating function of d_q(n) has been well studied in the last 20 years [Kung, The cycle structure of a linear transformation over a finite field, Linear Algebra Appl. 36 (1981) 141-155, Neumann and Praeger, Derangements and eigenvalue-free elements in finite classical groups, J. London Math. Soc. (2) 58 (1998) 564-586 and Stong, Some asymptotic results on finite vector spaces, Adv. Appl. Math. 9(2) (1988) 167-199]. The main tools have been the rational canonical form, nilpotent matrices, and a q-series identity of Euler. In this paper we take an elementary approach to this problem, based on Möbius inversion, and find the following bivariate generating function:

     

Compactified Jacobians and q,t-Catalan numbers, II

We continue the study of the rational-slope generalized q,t-Catalan numbers c _m,n (q,t). We describe generalizations of the bijective constructions of J. Haglund and N. Loehr and use them to prove a weak symmetry property c _m,n (q,1)=c _m,n (1,q) for m=kn±1. We give a bijective proof of the full symmetry c _m,n (q,t)=c _m,n (t,q) for min(m,n)≤3. As a corollary of these combinatorial constructions, we give a simple formula for the Poincaré polynomials of compactified Jacobians of plane curve singularities x ^kn±1=y ⁿ . We also give a geometric interpretation of a relation between rational-slope Catalan numbers and the theory of (m,n)-cores discovered by J. Anderson.     

Greedy F-colorings of graphs

Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N₀ is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v₁)=1 and (2) for each i with 1?i<n, c(v_i+1) is the smallest positive integer p such that F(v_j,v_i+1,|c(v_j)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and .     

On orthogonal systems of matrix algebras

In this work it is shown that certain interesting types of orthogonal system of subalgebras (whose existence cannot be ruled out by the trivial necessary conditions) cannot exist. In particular, it is proved that there is no orthogonal decomposition of M_n(C)⊗M_n(C)≡M_n²(C) into a number of maximal abelian subalgebras and factors isomorphic to M_n(C) in which the number of factors would be 1 or 3.In addition, some new tools are introduced, too: for example, a quantity c(A,B), which measures “how close” the subalgebras A,B⊂M_n(C) are to being orthogonal. It is shown that in the main cases of interest, c(A^′,B^′) - where A^′ and B^′ are the commutants of A and B, respectively - can be determined by c(A,B) and the dimensions of A and B. The corresponding formula is used to find some further obstructions regarding orthogonal systems.     

A Remarkable q,t-Catalan Sequence and q-Lagrange Inversion

We introduce a rational function C _n(q, t) and conjecture that it always evaluates to a polynomial in q, t with non-negative integer coefficients summing to the familiar Catalan number . We give supporting evidence by computing the specializations and C _n (q) = C _n(q,1) = C _n(1,q). We show that, in fact, D _n(q) q-counts Dyck words by the major index and C _n(q) q-counts Dyck paths by area. We also show that C _n(q, t) is the coefficient of the elementary symmetric function e _nin a symmetric polynomial DH_n(x; q, t) which is the conjectured Frobenius characteristic of the module of diagonal harmonic polynomials. On the validity of certain conjectures this yields that C _n(q, t) is the Hilbert series of the diagonal harmonic alternants. It develops that the specialization DH_n(x; q, 1) yields a novel and combinatorial way of expressing the solution of the q-Lagrange inversion problem studied by Andrews [2], Garsia [5] and Gessel [11]. Our proofs involve manipulations with the Macdonald basis {P (x; q, t)} which are best dealt with in -ring notation. In particular we derive here the -ring version of several symmetric function identities.Work carried out under NSF grant support.     

Construction of determinantal representation of trigonometric polynomials

For a pair of n×n Hermitian matrices H and K, a real ternary homogeneous polynomial defined by F(t,x,y)=det(tI_n+xH+yK) is hyperbolic with respect to (1,0,0). The Fiedler conjecture (or Lax conjecture) is recently affirmed, namely, for any real ternary hyperbolic polynomial F(t,x,y), there exist real symmetric matrices S₁ and S₂ such that F(t,x,y)=det(tI_n+xS₁+yS₂). In this paper, we give a constructive proof of the existence of symmetric matrices for the ternary forms associated with trigonometric polynomials.     

Homoclinic solutions for a class of the second order Hamiltonian systems

We study the existence of homoclinic orbits for the second order Hamiltonian system , where q∈Rⁿ and V∈C¹(R×Rⁿ,R), V(t,q)=-K(t,q)+W(t,q) is T-periodic in t. A map K satisfies the “pinching” condition b₁|q|²?K(t,q)?b₂|q|², W is superlinear at the infinity and f is sufficiently small in L²(R,Rⁿ). A homoclinic orbit is obtained as a limit of 2kT-periodic solutions of a certain sequence of the second order differential equations.     

Counting subsets of the random partition and the ‘Brownian Bridge’ process

Let Ω_m be the set of partitions, ω, of a finite m-element set; induce a uniform probability distribution on Ω_m, and define X_ms(ω) as the number of s-element subsets in ω. We alow the existence of an integer-valued function n=n^(m)(t), t?[0, 1], and centering constants b_ms, 0?s? m, such that

$\text{Z}{}^{\mathrm{(m)}}\text{(t)=}\text{∑}\text{s=0}\text{n(m)(t)}\text{(X}{}_{\mathrm{ms}}\text{?b}{}_{\mathrm{ms}}\text{)}\text{√}\text{∑}\text{s=0}\text{m}\text{b}{}_{\mathrm{ms}}$

converges to the ‘Brownian Bridge’ process in terms of its finite-dimensional distributions.     

Newton Polygons of L Functions Associated with Exponential Sums of Polynomials of Degree Four over Finite Fields

Let F_q be the finite field of q elements with characteristic p and F_q^m its extension of degree m. Fix a nontrivial additive character Ψ of F_p. If f(x₁,…, x_n)∈F_q[x₁,…, x_n] is a polynomial, then one forms the exponential sum S_m(f)=∑_{(x1,…,xn)∈(Fq^m)ⁿ}Ψ(Tr_Fq^m/Fp(f(x₁,…,x_n))). The corresponding L functions are defined by L(f, t)=exp(∑^∞_m=0S_m(f)t^m/m). In this paper, we apply Dwork's method to determine the Newton polygon for the L function L(f(x), t) associated with one variable polynomial f(x) when deg f(x)=4. As an application, we also give an affirmative answer to Wan's conjecture for the case deg f(x)=4.     

An application of L-functions of imaginary quadratic fields

Let F₁(x, y),…, F_2h+1(x, y) be the representatives of equivalent classes of positive definite binary quadratic forms of discriminant ?q (q is a prime such that q ≡ 3 mod 4) with integer coefficients, then the number of integer solutions of F_i(x, y) = n (i = 1,…, 2h + 1) can be calculated for each natural number n using L-functions of imaginary quadratic field $\text{Q}$((?q)^1/2).     

Surfaces and Curves Corresponding to the Solutions Generated from Periodic“Seed”of NLS Equation

The solutions q [n] generated from a periodic "seed" q = cei(as+bt) of the nonlinear Schrdinger(NLS) by n-fold Darboux transformation is represented by determinant.Furthermore,the s-periodic solution and t-periodic solution are given explicitly by using q [1].The curves and surfaces(F1,F2,F3) associated with q [n] are given by means of Sym formula.Meanwhile,we show periodic and asymptotic properties of these curves.     

A semi-recursion for the number of involutions in special orthogonal groups over finite fields

Let I(n) be the number of involutions in a special orthogonal group SO(n,Fq) defined over a finite field with q elements, where q is the power of an odd prime. Then the numbers I(n) form a semi-recursion, in that for m>1 we haveI(2m+3)=(q2m+2+1)I(2m+1)+q2m(q2m−1)I(2m−2). We give a purely combinatorial proof of this result, and we apply it to give a universal bound for the character degree sum for finite classical groups defined over Fq.