( q,t)-analogues and $GL_{n}({\ma thbb{F}}_{ q})$

We start with a (q,t)-generalization of a binomial coefficient. It can be viewed as a polynomial in t that depends upon an integer q, with combinatorial interpretations when q is a positive integer, and algebraic interpretations when q is the order of a finite field. These (q,t)-binomial coefficients and their interpretations generalize further in two directions, one relating to column-strict tableaux and Macdonald’s “7 ^th variation” of Schur functions, the other relating to permutation statistics and Hilbert series from the invariant theory of GL_n(\mathbbF_q)GL_{n}({\mathbb{F}}_{q}) .     

The homogeneous q-difference operator

We introduce a q-differential operator D_xy on functions in two variables which turns out to be suitable for dealing with the homogeneous form of the q-binomial theorem as studied by Andrews, Goldman, and Rota, Roman, Ihrig, and Ismail, et al. The homogeneous versions of the q-binomial theorem and the Cauchy identity are often useful for their specializations of the two parameters. Using this operator, we derive an equivalent form of the Goldman–Rota binomial identity and show that it is a homogeneous generalization of the q-Vandermonde identity. Moreover, the inverse identity of Goldman and Rota also follows from our unified identity. We also obtain the q-Leibniz formula for this operator. In the last section, we introduce the homogeneous Rogers–Szegö polynomials and derive their generating function by using the homogeneous q-shift operator.     

On the Computation of Square Roots in Finite Fields

In this paper, two improvements for computing square roots in finite fields are presented. Firstly, we give a simple extension of a method by O. Atkin, which requires two exponentiations in FM _q , when q9 mod 16. Our second method gives a major improvement to the Cipolla–Lehmer algorithm, which is both easier to implement and also much faster. While our method is independent of the power of 2 in q–1, its expected running time is equivalent to 1.33 as many multiplications as exponentiation via square and multiply. Several numerical examples are given that show the speed-up of the proposed methods, compared to the routines employed by Mathematica, Maple, respectively Magma.     

Surjections,Differences, and Binomial Lattices

The elementary problem of counting surjections from an n-set to a k-set is generalized to that of enumerating solutions of a₁ ∨ ? ∨ a_n = y, with each a_i an atom of the k-interval [x, y] in a binomial lattice L. When L is modular, the number of such solutions is representable as a q-difference and satisfies a simple recurrence.     

A congruence involving products of q-binomial coefficients

In this paper we establish a q-analogue of a congruence of Sun concerning the products of binomial coefficients modulo the square of a prime.     

A Poisson * Negative Binomial Convolution Law for Random Polynomials over Finite Fields

Let F _q[X] denote a polynomial ring over a finite field F _q with q elements. Let 𝒫_n be the set of monic polynomials over F _q of degree n. Assuming that each of the qⁿ possible monic polynomials in 𝒫_n is equally likely, we give a complete characterization of the limiting behavior of P(Ω_n=m) as n→∞ by a uniform asymptotic formula valid for m≥1 and n−m→∞, where Ω_n represents the number (multiplicities counted) of irreducible factors in the factorization of a random polynomial in 𝒫_n. The distribution of Ω_n is essentially the convolution of a Poisson distribution with mean log n and a negative binomial distribution with parameters q and q⁻¹. Such a convolution law exhibits three modes of asymptotic behaviors: when m is small, it behaves like a Poisson distribution; when m becomes large, its behavior is dominated by a negative binomial distribution, the transitional behavior being essentially a parabolic cylinder function (or some linear combinations of the standard normal law and its iterated integrals). As applications of this uniform asymptotic formula, we derive most known results concerning P(Ω_n=m) and present many new ones like the unimodality of the distribution. The methods used are widely applicable to other problems on multiset constructions. An extension to Rényi's problem, concerning the distribution of the difference of the (total) number of irreducibles and the number of distinct irreducibles, is also presented. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 17–47, 1998     

q-Discrete Painlevé equations for recurrence coefficients of modified q-Freud orthogonal polynomials

We present an asymmetric q-Painlevé equation. We will derive this using q-orthogonal polynomials with respect to generalized Freud weights: their recurrence coefficients will obey this q-Painlevé equation (up to a simple transformation). We will show a stable method of computing a special solution, which gives the recurrence coefficients. We establish a connection with α-q-P_V.     

On PSL(2,q) as a totally irregular collineation group

Non-abelian simple totally irregular collineation groups containing an involutorial perspectivity have been classified by the authors in a recent paper. They are PSL(2,q), PSL(3,q), PSU(3,q), Sz(q), the alternating group on 7 letters, and the second Janko sporadic simple group. In this article, we study PSL(2,q),q congruent to 1 modulo 4, as a collineation group containing an involutory homology.C. Y. Ho was partially supported by a NSA grant.     

The graph constructions of Hajós and Ore

A well-known theorem of Hajós shows that any graph with chromatic number at least q contains a subgraph constructible from the complete graph K_q by repeated application of two simple operations. Ore proved that the theorem still holds if the two operations are replaced by a single operation combining both of Hajós's operations. This note answers a question of Jensen and Toft by showing that for each q the classes of graphs constructible by these two methods are the same. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 211–215, 1997     

Interpolation and Combinatorial Functions

Using some basic results about polynomial interpolation, divided differences, and Newton polynomial sequences we develop a theory of generalized binomial coefficients that permits the unified study of the usual binomial coefficients, the Stirling numbers of the second kind, the q-Gaussian coefficients, and other combinatorial functions. We obtain a large number of combinatorial identities as special cases of general formulas. For example, Leibniz's rule for divided differences becomes a Chu-Vandermonde convolution formula for each particular family of generalized binomial coefficients.     

On a family of q-binomial distributions

We introduce a family of q-analogues of the binomial distribution, which generalises the Stieltjes-Wigert-, Rogers-Szegö-, and Kemp-distribution. Basic properties of this family are provided and several convergence results involving the classical binomial, Poisson, discrete normal distribution, and a family of q-analogues of the Poisson distribution are established. These results generalize convergence properties of Kemp’s-distribution, and some of them are q-analogues of classical convergence properties.     

Constructing Highly Incident Configurations

A geometric (q,k)-configuration is a collection of points and straight lines in the Euclidean plane in which each point lies on q lines and each line passes through k points. We say a (q,k)-configuration is highly incident when one (or both) of q or k is strictly greater than 4. In this paper, two simple lemmas are used to construct infinite classes of (2q,2k)-configurations for any q,k≥2; the resulting configurations have non-trivial dihedral symmetry. In particular, this construction produces the only known infinite class of symmetric 6-configurations.     

Factored matrices can generate combinatorial identities

By identifying the terms in the LU decomposition of various matrices, one produces combinatorial identities. Examples are given with formulas involving binomial coefficients and other numbers arising from simple recurrence formulas, number-theoretic functions, q-series, and orthogonal polynomials.     

On the Residues of Binomial Coefficients and Their Products Modulo Prime Powers

In this paper, we show several arithmetic properties on the residues of binomial coefficients and their products modulo prime powers, e.g., for any distinct odd primes p and q. Meanwhile, we discuss the connections with the prime recognitions. Received November 5, 1998, Accepted December 7, 2000.     

On solving sparse band systems with three algorithms of the ABS family

In this paper, we examine three algorithms in the ABS family and consider their storage requirements on sparse band systems. It is shown that, when using the implicit Cholesky algorithm on a band matrix with band width 2q+1, onlyq additional vectors are required. Indeed, for any matrix with upper band widthq, onlyq additional vectors are needed. More generally, ifa _kj 0,j>k, then thejth row ofH _i is effectively nonzero ifj>i>k. The arithmetic operations involved in solving a band matrix by this method are dominated by (1/2)n ² q. Special results are obtained forq-band tridiagonal matrices and cyclic band matrices.The implicit Cholesky algorithm may require pivoting if the matrixA does not possess positive-definite principal minors, so two further algorithms were considered that do not require this property. When using the implicit QR algorithm, a matrix with band widthq needs at most 2q additional vectors. Similar results forq-band tridiagonal matrices and cyclic band matrices are obtained.For the symmetric Huang algorithm, a matrix with band widthq requiresq–1 additional vectors. The storage required forq-band tridiagonal matrices and cyclic band matrices are again analyzed.This work was undertaken during the visit of Dr. J. Abaffy to Hatfield Polytechnic, sponsored by SERC Grant No. GR/E-07760.     

Verifying Huppert’s Conjecture for PSp<Subscript>4</Subscript>(<Emphasis Type="Italic">q</Emphasis>) when <Emphasis Type="Italic">q</Emphasis> > 7

Let G denote a finite group and cd (G) the set of irreducible character degrees of G. Bertram Huppert conjectured that if H is a finite nonabelian simple group such that cd (G) = cd (H), then G ≅ H × A, where A is an abelian group. Huppert verified the conjecture for PSp₄(q) when q = 3, 4, 5, or 7. In this paper, we extend Huppert’s results and verify the conjecture for PSp₄(q) for all q. This demonstrates progress toward the goal of verifying the conjecture for all nonabelian simple groups of Lie type of rank two.     

Efficiency of numerical integration algorithms related to divisor theory in cyclotomic fields

For function classes with dominant mixed derivative and bounded mixed difference in the metric ofL ^q (1<q≤2), quadrature formulas are constructed so that the following properties are achieved simultaneously: the grid is simple, the algorithm is efficient and close to the optimal algorithm for constructing the grid, and the order of the error on the power scale cannot be further improved. The caseq=2 was studied earlier. Translated fromMatematicheskie Zametki, Vol. 61, No. 2, pp. 297–301, February, 1997. Translated by N. K. Kulman     

A reduction theorem for the McKay conjecture

The McKay conjecture asserts that for every finite group G and every prime p, the number of irreducible characters of G having p’-degree is equal to the number of such characters of the normalizer of a Sylow p-subgroup of G. Although this has been confirmed for large numbers of groups, including, for example, all solvable groups and all symmetric groups, no general proof has yet been found. In this paper, we reduce the McKay conjecture to a question about simple groups. We give a list of conditions that we hope all simple groups will satisfy, and we show that the McKay conjecture will hold for a finite group G if every simple group involved in G satisfies these conditions. Also, we establish that our conditions are satisfied for the simple groups PSL₂(q) for all prime powers q≥4, and for the Suzuki groups Sz(q) and Ree groups R(q), where q=2 ^e or q=3 ^e respectively, and e>1 is odd. Since our conditions are also satisfied by the sporadic simple group J ₁, it follows that the McKay conjecture holds (for all primes p) for every finite group having an abelian Sylow 2-subgroup.     

A reconstruction method for a two-dimensional inverse eigenvalue problem

In this paper we describe a method for constructing approximate solutions of a two-dimensional inverse eigenvalue problem. Here we consider the problem of recovering a functionq(x, y) from the eigenvalues of — +q(x, y) on a rectangle with Dirichlet boundary conditions. The potentialq(x, y) is assumed to be symmetric with respect to the midlines of the rectangle. Our method is a generalization of an algorithm Hald presented for the construction of symmetric potentials in the one-dimensional inverse Sturm-Liouville problem. Using a projection method, the inverse spectral problem is reduced to an inverse eigenvalue problem for a matrix. We show that if the given eigenvalues are small perturbations of simple eigenvalues ofq=0, then the matrix problem has a solution. This solution is used to construct a functionq which has the same lowest eigenvalues as the unknownq, and several numerical examples are given to illustrate the methods.