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.     

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).     

On the number of lines in planar spaces

SupposeS is a planar space withv>4 points and letq be the positive real number such thatv=q ³+q²+q+1. Assuming a weak non-degeneracy condition, we shall show thatS has at least (q²+1)(q²+q+1) lines with equality iffq is a prime power andS=PG(3,q).     

Bivariate spline interpolation with optimal approximation order

Let Δ be a triangulation of some polygonal domain Ω ⊂ R² and let S_q^r(Δ) denote the space of all bivariate polynomial splines of smoothness r and degree q with respect to Δ. We develop the first Hermite-type interpolation scheme for S _q ^r (Δ), q ≥ 3r + 2, whose approximation error is bounded above by Kh ^q +1, where h is the maximal diameter of the triangles in Δ, and the constant K only depends on the smallest angle of the triangulation and is independent of near-degenerate edges and near-singular vertices. Moreover, the fundamental functions of our scheme are minimally supported and form a locally linearly independent basis for a superspline subspace of S _q ^r (Δ). This shows that the optimal approximation order can be achieved by using minimally supported splines. Our method of proof is completely different from the quasi-interpolation techniques for the study of the approximation power of bivariate splines developed in [7] and [18].     

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.     

On a Class of Symmetric Balanced Generalized Weighing Matrices

Let q be a prime power and m a positive integer. A construction method is given to multiply the parametrs of an -circulant BGW(v=1+q+q ₂+·+q ^m , q ^m , q ^m –q ^m–1) over the cyclic group C _n of order n with (q–1)/n being an even integer, by the parameters of a symmetric BGW(1+q ^m+1, q ^m+1, q ^m+1–q ^m ) with zero diagonal over a cyclic group C _vn to generate a symmetric BGW(1+q+·+q ^2m+1,q ^2m+1,q ^2m+1–q ^2m) with zero diagonal, over the cyclic group C _n . Applications include two new infinite classes of strongly regular graphs with parametersSRG(36(1+25+·+25^2m+1),15(25)^2m+1,6(25)^2m+1,6(25)^2m+1), and SRG(36(1+49+·+49^2m+1),21(49)^2m+1,12(49)^2m+1,12(49)^2m+1).     

Oscillation criteria for fourth‐order differential equations with middle term

Oscillation criteria for self‐adjoint fourth‐order differential equations were established for various conditions on the coefficients r(x) > 0, q(x) and p(x). However, most of these results deal with the case when lim_{x → ∞}∫^x₁q(s) ds < +∞. In this note we give a new oscillation criterion in the case when this condition is not fulfilled, in particular when q(x)↗ + ∞ (even with exponential growth).     

Lower bounds for the cardinality of minimal blocking sets in projective spaces

In this paper new lower bounds for the cardinality of minimal m-blocking sets are determined. Let r₂(q) be the number such that q+r₂(q)+1 is the cardinality of the smallest non-trivial line-blocking set in a plane of order q. If B is a minimal m-blocking set in PG(n,q) that contains at most q^m+q^m−1+…+q+1+r₂(q)·(∑_i=2m−n′^m−1qⁱ) points for an integer n′ satisfying mn′2m, then the dimension of B is at most n′. If the dimension of B is n′, then the following holds. The cardinality of B equals q^m+q^m−1+…+q+1+r₂(q)(∑_i=2m−n′^m−1qⁱ). For n′=m the set B is an m-dimensional subspace and for n′=m+1 the set B is a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. This result is due to Heim (Mitt. Math. Semin. Giessen 226 (1996), 4–82). For n′>m+1 and q not a prime the number q is a square and for q16 the set B is a Baer cone. If q is odd and |B|<q^m+q^m−1+…+q+1+r₂(q)(q^m−1+q^m−2), it follows from this result that the subspace generated by B has dimension at most m+1. Furthermore we prove that in this case, if , then B is an m-dimensional subspace or a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. For q=p^3h, p7 and q not a square we show this assertion for |B|q^m+q^m−1+…+q+1+q^2/3·(q^m−1+…+1).     

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.     

Fast inversion of vandermonde-like matrices involving orthogonal polynomials

Let {q} _j ^=0n–1 be a family of polynomials that satisfy a three-term recurrence relation and let {t _k } _k ⁼¹ⁿ be a set of distinct nodes. Define the Vandermonde-like matrixW _n =[w _jk ] _k,j ⁼¹ⁿ ,w _jk =q _j–1(t _k ). We describe a fast algorithm for computing the elements of the inverse ofW _n inO(n ²) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n ³) arithmetic operations.Dedicated to Gene H. Golub on his 60th birthdayResearch supported by NSF grant DMS-9002884.     

New higher order methods for solving nonlinear equations with multiple roots

For a nonlinear equation f(x)=0 having a multiple root we consider Steffensen’s transformation, T. Using the transformation, say, F_q(x)=T^qf(x) for integer q≥2, repeatedly, we develop higher order iterative methods which require neither derivatives of f(x) nor the multiplicity of the root. It is proved that the convergence order of the proposed iterative method is 1+2^q−2 for any equation having a multiple root of multiplicity m≥2. The efficiency of the new method is shown by the results for some numerical examples.     

Error bounds for least squares approximation by polynomials

Let f ε Cⁿ⁺¹[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials q_k associated with a distribution dα on [−1, 1]. It is shown that if q_n+1/q_n max(q_n+1(1)/q_n(1), −q_n+1(−1)/q_n(−1)), then f − H[f] f^{n + 1} · q_n+1/q_{n + 1}^{(n + 1)}, where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)^α (1 + t)^β dt, α, β > −1, the condition on q_n+1/q_n is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2.     

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.     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

A theorem,like f⊘lner’s theorem on amenability,concerning residual properties of free groups

Let PL(F _q) denote the projective line over a Galois field F _q. Consider PSL (2, Z ) as a free product of two cyclic groups <x> and <y> of orders 2 and 3. We have shown that any homomorphism from PSL(2,Z) into PGL(2,q) can be extended to a homomorphism from PGL(2Z) into PGL(2q) except in the case where the order of the image of xyis 6 but the images of xand ydo not commute in PGL(2q). It has been shown also that every element in PGL(2,q), not of order 1,2 , or 6, is the image of xyunder some non-degenerate homomorphism. We have parametrized the conjugacy classes of non-degenerate homomorphisms α with the non-trivial elements of F _q. Due to this parametrization we have developed a useful mechanism by which one can construct.

a unique coset diagram (attributed to G. Higman) for each conjugacy class, depicting the action of PGL(2Z) on PL( F _q).     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

Theq-gamma function forx<0

F. H. Jackson defined aq analogue of the gamma function which extends theq-factorial (n!) _q =1(1+q)(1+q+q ²)...(1+q+q ²+...+q ^n–1) to positivex. Askey studied this function and obtained analogues of most of the classical facts about the gamma function, for 0<q<1. He proved an analogue of the Bohr-Mollerup theorem, which states that a logarithmically convex function satisfyingf(1)=1 andf(x+1)=[(q ^x –1)/(q–1)]f(x) is in fact theq-gamma function He also studied the behavior of _q asq changes and showed that asq1^–, theq-gamma function becomes the ordinary gamma function forx>0.I proved many of these results forq>1. The current paper contains a study of the behavior of _q (x) forx<0 and allq>0. In addition to some basic properties of _q , we will study the behavior of the sequence {x _n (q)} of critical points asn orq changes.     

Blocking Sets and Derivable Partial Spreads

We prove that a GF(q)-linear Rédei blocking set of size q ^t + q ^t–1 + ··· + q + 1 of PG(2,q ^t) defines a derivable partial spread of PG(2t – 1, q). Using such a relationship, we are able to prove that there are at least two inequivalent Rédei minimal blocking sets of size q ^t + q ^t–1 + ··· + q + 1 in PG(2,q ^t), if t 4.     

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.