A partially ordered set and q-Krawtchouk polynomials

A family of q-Krawtchouk polynomials are the eigenvalues of the association schemes of bilinear, alternating, symmetric, and hermitian forms over a finite field. Another derivation is given for the analytic expression of the polynomials, which uses a lowering operator on a partially ordered set. It does not rely upon the associated additive characters. It is similar to a technique which has been applied to other partially ordered sets.     

广义Reed-Solomon 码的深洞

深洞在广义Reed-Solomon 码的译码中发挥重要的作用. 最近, Wu 和Hong 通过循环码对于标准Reed-Solomon 码发现了一类新的深洞. 本文给出一个简洁的方法, 对于一般广义Reed-Solomon 码给出新的一类深洞. 特别地, 对于标准Reed-Solomon 码, 我们得到了Wu 和Hong 给出的深洞. 对于广义Reed-Solomon 码GRS_k(F_q,D), Li 和Wan 研究和刻画了k+1 次多项式定义的深洞, 并且指出这个问题归结为在有限域中的子集和问题. 在偶特征的情形下, 利用他们的方法, 我们对于一些特殊的Reed-Solomon 码得到了更多一类新的深洞. 此外, 我们研究扩展Reed-Solomon 码(即赋值集合为D=F_q) k+2 次多项式定义的深洞, 并且证明没有k+2次多项式定义的深洞.     

Coboundaries, Flows, and Tutte Polynomials of Matrices

Using matroid duality and the critical problem, we show that certain evaluations of the Tutte polynomial of a matroid represented as a matrix over a finite field GF(q) can be interpreted as weighted sums over pairs f , g of functions defined from the ground set to GF(q) whose difference f – g is the restriction of a linear functional on the column space of the matrix. Similar interpretations are given for the characteristic polynomial evaluated at q. These interpretations extend and elaborate interpretations for Tutte and chromatic polynomials of graphs due to Goodall and Matiyasevich. Received July 14, 2006     

Bounding the piercing number

It is shown that for everyk and everyp≥q≥d+1 there is ac=c(k,p,q,d)<∞ such that the following holds. For every familyℋ whose members are unions of at mostk compact convex sets inR ^d in which any set ofp members of the family contains a subset of cardinalityq with a nonempty intersection there is a set of at mostc points inR ^d that intersects each member ofℋ. It is also shown that for everyp≥q≥d+1 there is aC=C(p,q,d)<∞ such that, for every family of compact, convex sets inR ^d so that among andp of them someq have a common hyperplane transversal, there is a set of at mostC hyperplanes that together meet all the members of . This research was supported in part by a United States-Israel BSF Grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Laplacian Operators and Radon Transforms on Grassmann Graphs

Let Ω be a vector space over a finite field with q elements. Let G denote the general linear group of automorphisms of Ω and let us consider the left regular representation associated with the natural action of G on the set X of linear subspaces of Ω. In this paper we study a natural basis B of the algebra End_G(L ₂(X)) of intertwining maps on L ₂(X). By using a Laplacian operator on Grassmann graphs, we identify the kernels in B as solutions of a basic hypergeometric difference equation. This provides two expressions for these kernels. One in terms of the q-Hahn polynomials and the other by means of a Rodrigues type formula. Finally, we obtain a useful product formula for the mappings in B. We give two different proofs. One uses the theory of classical hypergeometric polynomials and the other is supported by a characterization of spherical functions in finite symmetric spaces. Both proofs require the use of certain associated Radon transforms.     

Polynomial Factorisation and an Application to Regular Directed Graphs

The main theme is the distribution of polynomials of given degree which split into a product of linear factors over a finite field. The work was motivated by the following problem on regular directed graphs. Extending a notion of Chung, Katz has defined a regular directed graph based on thek-algebrak[X]/(f), wherekis the finite field of orderqandfa monic polynomial of degreenoverk. It is shown that the diameter of this graph is at mostn+2 wheneverq≥B(n)=[n(n+2)!]². This improves on the work of Katz who gave a similar result for square-free polynomialsfwithout specifyingB(n).     

Two Remarks on Blocking Sets and Nuclei in Planes of Prime Order

In this paper we characterize a sporadic non-Rédei Type blocking set of PG(2,7) having minimum cardinality, and derive an upper bound for the number of nuclei of sets in PG(2,q) having less than q+1 points. Our methods involve polynomials over finite fields, and work mainly for planes of prime order.     

A short proof of an interesting helly-type theorem

We give a short proof of the theorem that any family of subsets ofR ^d , with the property that the intersection of any nonempty finite subfamily can be represented as the disjoint union of at mostk closed convex sets, has Helly number at mostk(d+1). Some of this work was done at the University of California, Berkeley, where the author was supported by a U.C. Presidents Dissertation Year Fellowship and an AT&T Graduate Research Program for Women Grant.     

On explicit factors of cyclotomic polynomials over finite fields

We study the explicit factorization of 2 ⁿ r-th cyclotomic polynomials over finite field \mathbbF_q{\mathbb{F}_q} where q, r are odd with (r, q) = 1. We show that all irreducible factors of 2 ⁿ r-th cyclotomic polynomials can be obtained easily from irreducible factors of cyclotomic polynomials of small orders. In particular, we obtain the explicit factorization of 2 ⁿ 5-th cyclotomic polynomials over finite fields and construct several classes of irreducible polynomials of degree 2 ^n–2 with fewer than 5 terms.     

Newton stratification for polynomials: The open stratum

In this paper we consider the Newton polygons of L-functions coming from additive exponential sums associated to a polynomial over a finite field Fq. These polygons define a stratification of the space of polynomials of fixed degree. We determine the open stratum: we give the generic Newton polygon for polynomials of degree d?2 when the characteristic p?3d, and the Hasse polynomial over Fp, i.e. the equation defining the hypersurface complementary to the open stratum.     

Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams

We consider the problem of finding the number of matrices over a finite field with a certain rank and with support that avoids a subset of the entries. These matrices are a q-analogue of permutations with restricted positions (i.e., rook placements). For general sets of entries, these numbers of matrices are not polynomials in q (Stembridge in Ann. Comb. 2(4):365, 1998); however, when the set of entries is a Young diagram, the numbers, up to a power of q?1, are polynomials with nonnegative coefficients (Haglund in Adv. Appl. Math. 20(4):450, 1998). In this paper, we give a number of conditions under which these numbers are polynomials in q, or even polynomials with nonnegative integer coefficients. We extend Haglund’s result to complements of skew Young diagrams, and we apply this result to the case where the set of entries is the Rothe diagram of a permutation. In particular, we give a necessary and sufficient condition on the permutation for its Rothe diagram to be the complement of a skew Young diagram up to rearrangement of rows and columns. We end by giving conjectures connecting invertible matrices whose support avoids a Rothe diagram and Poincaré polynomials of the strong Bruhat order.     

Counting Solutions to Equations in Many Variables over Finite Fields

We present a polynomial-time algorithm for computing the zeta function of a smooth projective hypersurface of degree d over a finite field of characteristic p, under the assumption that p is a suitably small odd prime and does not divide d. This improves significantly upon an earlier algorithm of the author and Wan which is only polynomial-time when the dimension is fixed.     

Degree distribution of the greatest common divisor of polynomials over 𝔽q

We study the degree distribution of the greatest common divisor of two or more random polynomials over a finite field ??_q. We provide estimates for several parameters like number of distinct common irreducible factors, number of irreducible factors counting repetitions, and total degree of the gcd of two or more polynomials. We show that the limiting distribution of a random variable counting the total degree of the gcd is geometric and that the distributions of random variables counting the number of common factors (with and without repetitions) are very close to Poisson distributions when q is large. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Automorphisms and Isomorphisms of Symmetric and Affine Designs

Given a finite group G, for all sufficiently large d and for each q > 3 there are symmetric designs and affine designs having the same parameters as PG(d, q) and AG(d, q), respectively, and having full automorphism group isomorphic to G.     

Irreducible linear subgroups generated by pairs of matrices with large irreducible submodules

We call an element of a finite general linear group GL(d, q) fat if it leaves invariant and acts irreducibly on a subspace of dimension greater than d/2. Fatness of an element can be decided efficiently in practice by testing whether its characteristic polynomial has an irreducible factor of degree greater than d/2. We show that for groups G with SL(d, q) ≤ G ≤ GL(d, q) most pairs of fat elements from G generate irreducible subgroups, namely we prove that the proportion of pairs of fat elements generating a reducible subgroup, in the set of all pairs in G × G, is less than q ^−d+1. We also prove that the conditional probability to obtain a pair (g ₁, g ₂) in G × G which generates a reducible subgroup, given that g ₁, g ₂ are fat elements, is less than 2q ^−d+1. Further, we show that any reducible subgroup generated by a pair of fat elements acts irreducibly on a subspace of dimension greater than d/2, and in the induced action the generating pair corresponds to a pair of fat elements.     

Quantum B-splines

Quantum splines are piecewise polynomials whose quantum derivatives (i.e. certain discrete derivatives or equivalently certain divided differences) agree up to some order at the joins. Just like classical splines, quantum splines admit a canonical basis with compact support: the quantum B-splines. These quantum B-splines are the q-analogues of classical B-splines. Here quantum B-spline bases and quantum B-spline curves are investigated, using a new variant of the blossom: the q (quantum)-blossom. The q-blossom of a degree d polynomial is the unique symmetric, multiaffine function in d variables that reduces to the polynomial along the q-diagonal. By applying the q-blossom, algorithms and identities for quantum B-spline bases and quantum B-spline curves are developed, including quantum variants of the de Boor algorithms for recursive evaluation and quantum differentiation, knot insertion procedures for converting from quantum B-spline to piecewise quantum Bézier form, and a quantum variant of Marsden’s identity.     

On the Number of Solutions of Polynomial Systems

We consider systems of homogenous polynomial equations of degreedin a projective space ^mover a finite field _q. We attempt to determine the maximum possible number of solutions of such systems. The complete answer for the caser= 2,d<q− 1 is given, as well as new conjectures about the general case. We also prove a bound on the number of points of an algebraic set of given codimension and degree. We also discuss an application of our results to coding theory, namely to the problem of computing generalized Hamming weights forq-ary projective Reed–Muller codes.     

A generalization of the symmetric classical polynomials: Hermite and Gegenbauer polynomials

In this paper, we give new families of polynomials orthogonal with respect to a d-dimensional vector of linear functionals, d being a positive integer number, and generalizing the standard symmetric classical polynomials: Hermite and Gegenbauer. We state the inversion formula which is used to express the corresponding moments by means of integral representations involving the Meijer G-function. Moreover, we determine some characteristic properties for these polynomials: generating functions, explicit representations and component sets.     

Fast construction of irreducible polynomials over finite fields

We present a randomized algorithm that on inputting a finite field K with q elements and a positive integer d outputs a degree d irreducible polynomial in K[x]. The running time is d ^1+?(d)×(log q)^5+?(q) elementary operations. The function ? in this expression is a real positive function belonging to the class o(1), especially, the complexity is quasi-linear in the degree d. Once given such an irreducible polynomial of degree d, we can compute random irreducible polynomials of degree d at the expense of d ^1+?(d) × (log q)^1+?(q) elementary operations only.     

An analogue of the big <Emphasis Type="Italic">q</Emphasis>-Jacobi polynomials in the algebra of symmetric functions

It is well known how to construct a system of symmetric orthogonal polynomials in an arbitrary finite number of variables from an arbitrary system of orthogonal polynomials on the real line. In the special case of the big q-Jacobi polynomials, the number of variables can be made infinite. As a result, in the algebra of symmetric functions, there arises an inhomogeneous basis whose elements are orthogonal with respect to some probability measure. This measure is defined on a certain space of infinite point configurations and hence determines a random point process.