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.     

Maximal arcs in Desarguesian planes of odd order do not exist

Forq an odd prime power, and 1<n<q, the Desarguesian planePG(2,q) does not contain an(nq–q+n,n)-arc.Supported by Italian M.U.R.S.T. (Research Group onStrutture geometriche, combinatoria, loro applicazioni) and G.N.S.A.G.A. of C.N.R.     

The order dimension of two levels of the Boolean lattice

LetB _n(s, t) denote the partially ordered set consisting of alls-subsets andt-subsets of ann-element underlying set where these sets are ordered by inclusion. Answering a question of Trotter we prove that dim(B _n(k, n–k))=n–2 for 3k<(1/7)n ^1/3. The proof uses extremal hypergraph theory.     

The graph induced by affine <Emphasis Type="Italic">M</Emphasis>-flats over finite fields II

Let AG(n, F _q) be the n-dimensional affine space over F _q, where F _q is a finite field with q elements. Denote by Γ ^(m) the graph induced by m-flats of AG(n, F _q). For any two adjacent vertices E and F of is studied. In particular, sizes of maximal cliques in Γ ^(m) are determined and it is shown that Γ ^(m) is not edge-regular when m<n−1. Supported by the National Natural Science Foundation of China (19571024) and Hunan Provincial Department of Education (02C512).     

Blocking Sets Of External Lines To A Conic In PG(2,q), q ODD

We determine all point-sets of minimum size in PG(2,q), q odd that meet every external line to a conic in PG(2,q). The proof uses a result on the linear system of polynomials vanishing at every internal point to the conic and a corollary to the classification theorem of all subgroups of PGL(2,q). * Research supported by the Italian Ministry MURST, Strutture geometriche, combinatoria e loro applicazioni and by the Hungarian-Italian Intergovernemental project “Algebraic and Geometric Structures”.     

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.     

Simple quasidoubles of projective planes

We show that the number of (simple) designsS ₂(2,q + 1,q ² +q + 1), whereq is a power of a prime, grows at least asO(q!).Dedicated to Professor Otto Haupt with best wishes on his 100th birthday     

Orthogonal packings inPG(5, 2)

Aspread inPG(n, q) is a set of lines which partitions the point set. A packing inPG(n, q) (n odd) is a partition of the lines into spreads. Two packings ofPG(n, q) are calledorthogonal if and only if any two spreads, one from each packing, have at most one line in common. Recently, R. D. Baker has shown the existence of a pair of orthogonal packings inPG(5, 2). In this paper we enumerate all packings inPG(5, 2) having both an automorphism of order 31 and the Frobenius automorphism. We find all pairs of orthogonal packings of the above type and display a set of six mutually orthogonal packings. Previously the largest set of orthogonal packings known inPG(5, 2) was two.     

The choice number of random bipartite graphs

A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log₂(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship.     

Book Ramsey numbers. I

A book B_p is a graph consisting of p triangles sharing a common edge. In this paper we prove that if p ≤ q/6 ?o(q) and q is large, then the Ramsey number r (B_p,B_q) is given by r (B_p,B_q) = 2q+3, and the constant 1/6 is essentially best possible. Our proof is based on Szemerédi's uniformity lemma and a stability result for books. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

<Emphasis Type="Italic">q</Emphasis>-Fibonacci Polynomials and the Rogers-Ramanujan Identities

We derive some formulas for the Carlitz q-Fibonacci polynomials F_n(t) which reduce to the finite version of the Rogers-Ramanujan identities obtained by I. Schur for t = 1. Our starting point is a representation of the q-Fibonacci polynomials as the weight of certain lattice paths in contained in a strip along the x-axis. We give an elementary combinatorial proof by using only the principle of inclusion-exclusion and some standard facts from q-analysis.     

AN EIGENSPACE CHARACTERIZATION OF LORENTZ-IMPROVING MEASURES ON COMPACT GROUPS

Abstract

A measure μ on a compact group is called Lorentz-improving if for some 1 > p > ∞ and 1 → q ₁ > q ₂ ∞ μ *L (p, q ₂) ? L(p, q ₁). Let T _μ denote the operator on L ² defined by T _μ(f) = μ * f. Lorentz-improving measures are characterized in terms of the eigenspaces of T _μ, if T _μ is a normal operator, and in terms of the eigenspaces of |T _μ| otherwise. This result generalizes our recent characterization of Lorentz-improving measures on compact abelian groups and is modelled after Hare's characterization of L ^p -improving measures on compact groups.     

Conjectured statistics for the q,t-Catalan numbers

We introduce the distribution function F_n(q,t) of a pair of statistics on Catalan words and conjecture F_n(q,t) equals Garsia and Haiman's q,t-Catalan sequence C_n(q,t), which they defined as a sum of rational functions. We show that F_n,s(q,t), defined as the sum of these statistics restricted to Catalan words ending in s ones, satisfies a recurrence relation. As a corollary we are able to verify that F_n(q,t)=C_n(q,t) when t=1/q. We also show the partial symmetry relation F_n(q,1)=F_n(1,q). By modifying a proof of Haiman of a q-Lagrange inversion formula based on results of Garsia and Gessel, we obtain a q-analogue of the general Lagrange inversion formula which involves Catalan words grouped according to the number of ones at the end of the word.     

Counting points in hypercubes and convolution measure algebras

It is shown that ifA andB are non-empty subsets of {0, 1} ⁿ (for somenεN) then |A+B|≧(|A||B|)^α where α=(1/2) log₂ 3 here and in what follows. In particular if |A|=2 ^n-1 then |A+A|≧3 ^n-1 which anwers a question of Brown and Moran. It is also shown that if |A| = 2 ^n-1 then |A+A|=3 ^n-1 if and only if the points ofA lie on a hyperplane inn-dimensions. Necessary and sufficient conditions are also given for |A +B|=(|A||B|)^α. The above results imply the following improvement of a result of Talagrand [7]: ifX andY are compact subsets ofK (the Cantor set) withm(X),m(Y)>0 then λ(X+Y)≧2(m(X)m(Y))^α wherem is the usual measure onK and λ is Lebesgue measure. This also answers a question of Moran (in more precise terms) showing thatm is not concentrated on any proper Raikov system.     

Recursive constructions for skew resolutions in affine geometries

A resolutionR inAG(n, q) is defined to be a partition of the lines into classesR ₁,R ₂, ...,R _t (t=(q ⁿ –1)/(q–1)) such that each point of the geometry is incident with precisely one line of each classR _l , 1it. Of course, the equivalence relation of parallelism defines a resolution in any affine geometry. A resolutionR is said to be a skew resolution provided noR _i , 1it, contains two parallel lines. Skew resolutions are useful for producing packings of lines in projective spaces and doubly resolvable block designs. Skew resolutions are known to exist inAG(n, q),n=2^t–1,i2,q a prime power. The entire spectrum is unknown. In this paper, we give two recursive constructions for skew resolutions. These constructions produce skew resolutions inAG(n, q) for infinietly many new values ofn.     

On simple modules of Hecke algebras of type Dn

This is a continuation of our previous work. We classify all the simple ℋ_q(D _n )-modules via an automorphismh defined on the set { λ | D^λ ≠ 0}. Whenf _n(q) ≠ 0, this yields a classification of all the simple ℋ ^q (D _n)- modules for arbitrary n. In general ( i. e., q arbitrary), if λ⁽¹⁾ = λ⁽²⁾,wegivea necessary and sufficient condition ( in terms of some polynomials ) to ensure that the irreducible ℋ_q,1(B _n )- module D^λ remains irreducible on restriction to ℋ_q(D _n ).     

Pesenti-Szpiro inequality for optimal elliptic curves

We study Pesenti-Szpiro inequality in the case of elliptic curves over F_q(t) which occur as subvarieties of Jacobian varieties of Drinfeld modular curves. In general, we obtain an upper-bound on the degrees of minimal discriminants of such elliptic curves in terms of the degrees of their conductors and q. In the special case when the level is prime, we bound the degrees of discriminants only in terms of the degrees of conductors. As a preliminary step in the proof of this latter result we generalize a construction (due to Gekeler and Reversat) of 1-dimensional optimal quotients of Drinfeld Jacobians.     

On a problem of Erdős concerning property B

A family ℱ of sets has propertyB if there exists a setS such thatS∩F≠0 andS⊄F for everyF∈ℱ. ℱ has propertyB(s) if there exists a setS such that 0<|F∩S|<s for everyF∈ℱ. Denote bym(n) (respectivelym(n, s)) the size of a smallest family ofn-element sets not having propertyB (respectivelyB(s)). P. Erdős has asked whetherm(n, s)≧m (s) for alln≧s. We show that, in general, this inequality does not hold.     

Identities involving Farey fractions

The rational numbers a/q in [0, 1] can be counted by increasing height H(a/q) = max(a, q), or ordered as real numbers. Franel’s identity shows that the Riemann hypothesis is equivalent to a strong bound for a measure of the independence of these two orderings. We give a proof using Dedekind sums that allows weights w(q). Taking w(q) = χ(q) we find an extension to Dirichlet L-functions.     

The Cardinality of Sets of <Emphasis Type="Italic">k</Emphasis>-Independent Vectors over Finite Fields

A set of vectors is k-independent if all its subsets with no more than k elements are linearly independent. We obtain a result concerning the maximal possible cardinality Ind _q (n, k) of a k-independent set of vectors in the n-dimensional vector space F _q ⁿ over the finite field F _q of order q. Namely, we give a necessary and sufficient condition for Ind _q (n, k) = n + 1. We conclude with some pertinent remarks re applications of our results to codes, graphs and hypercubes. Supported, in part by grants EP/C000285, NSF-DMS-0439734 and NSF-DMS-0555839. S. B. Damelin thanks the Institute for Mathematics and Applications for their hospitality.