A three shuffle case of the compositional parking function conjecture

We prove here that the polynomial 〈∇_Cp1,_eahbhc〉$〈\mathrm{\nabla }{\mathbf{C}}_{p}1,e_a{h}_b{h}_c〉$q,t$q,t$-enumerates, by the statistics dinv and area  , the parking functions whose supporting Dyck path touches the main diagonal according to the composition p?a+b+c$p?a+b+c$ and has a reading word which is a shuffle of one decreasing word and two increasing words of respective sizes a, b, c  . Here _Cp1${\mathbf{C}}_{p}1$ is a rescaled Hall–Littlewood polynomial and ∇ is the Macdonald eigen-operator introduced by Bergeron and Garsia. This is our latest progress in a continued effort to settle the decade old shuffle conjecture   of Haglund et al. This result includes as special cases all previous results connected with the shuffle conjecture such as the q,t$q,t$-Catalan, Schröder and two shuffle results of Haglund as well as their compositional refinements recently obtained by the authors. It also confirms the possibility that the approach adopted by the authors has the potential to yield a resolution of the shuffle parking function conjecture as well as its compositional refinement more recently proposed by Haglund, Morse and Zabrocki.     

The Green polynomials via vertex operators

An iterative formula for the Green polynomial is given using the vertex operator realization of the Hall-Littlewood function. Based on this, (1) a general combinatorial formula of the Green polynomial is given; (2) several compact formulas are given for Green's polynomials associated with upper partitions of length ≤3 and the diagonal lengths ≤3; (3) a Murnaghan-Nakayama type formula for the Green polynomial is obtained; and (4) an iterative formula is derived for the bitrace of the finite general linear group G and the Iwahori-Hecke algebra of type A on the permutation module of G by its Borel subgroup.     

The correlation functions of vertex operators and Macdonald polynomials

The n-point correlation functions introduced by Bloch and Okounkov have already found several geometric connections and algebraic generalizations. In this note we formulate a q,t-deformation of this n-point function. The key operator used in our formulation arises from the theory of Macdonald polynomials and affords a vertex operator interpretation. We obtain closed formulas for the n-point functions when n = 1,2 in terms of the basic hypergeometric functions. We further generalize the q,t-deformed n-point function to more general vertex operators.     

Newton functions generating symmetric fields and irreducibility of Schur polynomials

We prove (Theorem 1.1) that if e₀>>e_r>0 are coprime integers, then the Newton functions , i=0,…,r, generate over the field of symmetric rational functions in X₁,…,X_r. This generalizes a previous result of us for r=2. This extension requires new methods, including: (i) a study of irreducibility and Galois-theoretic properties of Schur polynomials (Theorem 3.1), and (ii) the study of the dimension of the varieties obtained by intersecting Fermat hypersurfaces (Theorem 4.1). We shall also observe how these results have implications to the study of zeros of linear recurrences over function fields; in particular, we give (Theorem 4.2) a complete classification of the zeros of recurrences of order four with constant coefficients over a function field of dimension 1.     

Recursions associated to trapezoid,symmetric and rotation symmetric functions over Galois fields

Rotation symmetric Boolean functions are invariant under circular translation of indices. These functions have very rich cryptographic properties and have been used in different cryptosystems. Recently, Thomas Cusick proved that exponential sums of rotation symmetric Boolean functions satisfy homogeneous linear recurrences with integer coefficients. In this work, a generalization of this result is proved over any Galois field. That is, exponential sums over Galois fields of some rotation symmetric polynomials satisfy linear recurrences with integer coefficients. In the particular case of ${\mathbb{F}}_2$, an elementary method is used to obtain explicit recurrences for exponential sums of some of these functions. The concept of trapezoid Boolean function is also introduced and it is showed that the linear recurrences that exponential sums of trapezoid Boolean functions satisfy are the same as the ones satisfied by exponential sums of the corresponding rotations symmetric Boolean functions. Finally, it is proved that exponential sums of trapezoid and symmetric polynomials also satisfy linear recurrences with integer coefficients over any Galois field ${\mathbb{F}}_q$. Moreover, the Discrete Fourier Transform matrix and some Complex Hadamard matrices appear as examples in some of our explicit formulas of these recurrences.     

q-Analogs of some congruences involving Catalan numbers

We present some variations on the Greene–Krammer?s identity which involve q-Catalan numbers. Our method reveals an intriguing analogy between these new identities and some congruences modulo a prime.     

A note on approximation properties of q-Durrmeyer operators

In this paper, the approximation properties of q-Durrmeyer operators D_n,q(f;x) for f∈C[0,1] are discussed. The exact class of continuous functions satisfying approximation process lim_n→∞D_n,q(f;x)=f(x) is determined. The results of the paper provide an elaboration of the previously-known ones on operators D_n,q.     

A generalization of Kawanaka’s identity for Hall-Littlewood polynomials and applications

An infinite summation formula of Hall-Littlewood polynomials due to Kawanaka is generalized to a finite summation formula, which implies, in particular, twelve more multiple q-identities of Rogers-Ramanujan type than those previously found by Stembridge and the last two authors.     

Green polynomials at roots of unity and Springer modules for the symmetric groups

We consider the Green polynomials at roots of unity. We obtain a recursive formula for the Green polynomials at roots of unity whose orders do not exceed some positive integer. The formula is described in a combinatorial manner. The coefficients of the recursive formula are realized by the cardinality of a set of permutations. The formula gives an interpretation of a combinatorial property on a family of graded modules for the symmetric group in terms of representation theory.     

A Formula for <Emphasis Type="Italic">N</Emphasis>-Row Macdonald Polynomials

We derive a formula for the n-row Macdonald polynomials with the coefficients presented both combinatorically and in terms of very-well-poised hypergeometric series.     

Generalized characters of the symmetric group

Normalized irreducible characters of the symmetric group S(n) can be understood as zonal spherical functions of the Gelfand pair (S(n)×S(n),diagS(n)). They form an orthogonal basis in the space of the functions on the group S(n) invariant with respect to conjugations by S(n). In this paper we consider a different Gelfand pair connected with the symmetric group, that is an “unbalanced” Gelfand pair (S(n)×S(n−1),diagS(n−1)). Zonal spherical functions of this Gelfand pair form an orthogonal basis in a larger space of functions on S(n), namely in the space of functions invariant with respect to conjugations by S(n−1). We refer to these zonal spherical functions as normalized generalized characters of S(n). The main discovery of the present paper is that these generalized characters can be computed on the same level as the irreducible characters of the symmetric group. The paper gives a Murnaghan-Nakayama type rule, a Frobenius type formula, and an analogue of the determinantal formula for the generalized characters of S(n).     

Minimizing symmetric submodular functions

We describe a purely combinatorial algorithm which, given a submodular set functionf on a finite setV, finds a nontrivial subsetA ofV minimizingf[A] + f[V A]. This algorithm, an extension of the Nagamochi—Ibaraki minimum cut algorithm as simplified by Stoer and Wagner [M. Stoer, F. Wagner, A simple min cut algorithm, Proceedings of the European Symposium on Algorithms ESA '94, LNCS 855, Springer, Berlin, 1994, pp. 141–147] and by Frank [A. Frank, On the edge-connectivity algorithm of Nagamochi and Ibaraki, Laboratoire Artémis, IMAG, Université J. Fourier, Grenbole, 1994], minimizes any symmetric submodular function using O(|V|³) calls to a function value oracle. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper was presented at the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) in January 1995. This research was supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada.     

Content evaluation and class symmetric functions

In this article we study the evaluation of symmetric functions on the alphabet of contents of a partition. Applying this notion of content evaluation to the computation of central characters of the symmetric group, we are led to the definition of a new basis of the algebra Λ of symmetric functions over that we call the basis of class symmetric functions.By definition this basis provides an algebra isomorphism between Λ and the Farahat-Higman algebra FH governing for all n the products of conjugacy classes in the center of the group algebra of the symmetric group . We thus obtain a calculus of all connexion coefficients of inside Λ. As expected, taking the homogeneous components of maximal degree in class symmetric functions, we recover the symmetric functions introduced by Macdonald to describe top connexion coefficients.We also discuss the relation of class symmetric functions to the asymptotic of central characters and of the enumeration of standard skew young tableaux. Finally we sketch the extension of these results to Hecke algebras.     

Some properties of q-biorthogonal polynomials

Almost four decades ago, Konhauser introduced and studied a pair of biorthogonal polynomials

     

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:

     

q-Taylor and interpolation series for Jackson q-difference operators

We prove q-Taylor series for Jackson q-difference operators. Absolute and uniform convergence to the original function are proved for analytic functions. We derive interpolation results for entire functions of q-exponential growth which is less than lnq⁻¹, 0<q<1, from its values at the nodes , a is a non-zero complex number with absolute and uniform convergence criteria.     

A curious q-analogue of Hermite polynomials

Two well-known q-Hermite polynomials are the continuous and discrete q-Hermite polynomials. In this paper we consider a new family of q-Hermite polynomials and prove several curious properties about these polynomials. One striking property is the connection with q-Fibonacci and q-Lucas polynomials. The latter relation yields a generalization of the Touchard-Riordan formula.