A new graphic characterization of non singular quadrics of PG(r,q)

LetK be ak-set of class [0, 1,m,n]₁ of anr-dimensional projective Galois space PG(r, q) of orderq. We prove that: Ifr = 2s (s 2),k = _2s–1 and if through each point ofK there are exactlyq ^2(s–1) tangent lines and at most _2s–3 n-secant lines, thenK is a non singular quadric of PG(2s,q). Ifr = 2s–1 (s2),k=_2(s–1) +q ^s–1 and if at each point ofK there are exactlyq ^2s–3 –q ^s–2 tangents and at most _2(s–2)+q ^s–2 n-secant lines, thenK is a hyperbolic quadric of PG(2s–1,q).     

Triangulating point sets in space

A setP ofn points inR ^d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn/(d + 1) points. A splitter can be found inO(d ⁴ +nd ²) time. Using this result, we give anO(nd ⁴ log_1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR ³ we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR ³ for which the number of simplices produced may vary between (n – 1)² + 1 and 2n – 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.Research supported by the Natural Science and Engineering Research Council grant A3013 and the F.C.A.R. grant EQ1678.     

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.     

Separating convex sets in the plane

Given a setA inR ² and a collectionS of plane sets, we say that a lineL separatesA fromS ifA is contained in one of the closed half-planes defined byL, while every set inS is contained in the complementary closed half-plane.We prove that, for any collectionF ofn disjoint disks inR ², there is a lineL that separates a disk inF from a subcollection ofF with at least (n–7)/4 disks. We produce configurationsH _n andG _n , withn and 2n disks, respectively, such that no pair of disks inH _n can be simultaneously separated from any set with more than one disk ofH _n , and no disk inG _n can be separated from any subset ofG _n with more thann disks.We also present a setJ _m with 3m line segments inR ², such that no segment inJ _m can be separated from a subset ofJ _m with more thanm+1 elements. This disproves a conjecture by N. Alonet al. Finally we show that ifF is a set ofn disjoint line segments in the plane such that they can be extended to be disjoint semilines, then there is a lineL that separates one of the segments from at least n/3+1 elements ofF.     

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

A sharp form of Poincaré type inequalities on balls and spheres

Summary Letu be a real valued function on ann-dimensional Riemannian manifoldM ⁿ. We consider an inequality between theL ^q-norm ofu minus its mean value overM ⁿ and theL ^p-norm of the gradient ofu.The best constant in such inequality is exhibited in the following cases: i)M ⁿ is an open ball inIR ⁿ andp=1, 0<qn/(n–1); ii)M ⁿ is a sphere inIR ⁿ +1 and eitherp=1, 0<qn/(n–1) orp>n,q=.

---

Sunto Siau una funzione a valori reali dafinita su una varietà riemannianan-dimensionaleM ⁿ. Si considera una disuguaglianza tra la normaL ^q diu meno il suo valor medio suM ⁿ e la normaL ^p del gradiente diu.Si determina la costante ottimale in tale disuguaglianza nei seguenti casi: i)M ⁿ è un disco aperto inIR ⁿ ep=1, 0<qn/(n–1); ii)M ⁿ è una sfera inIR ⁿ +1 ep=1, 0<qn/(n–1) oppurep>n,q=.

     

On the number of solutions to the linear comple-mentarity problem

Given ann × n matrixA and ann-dimensional vectorq letN(A, q) be the cardinality of the set of solutions to the linear complementarity problem defined byA andq. It is shown that ifA is nondegenerate thenN(A, q) + N(A, –q) 2 ⁿ , which in turn impliesN(A, q) 2 ⁿ – 1 ifA is also aQ-matrix.It is then demonstrated that min _q0 N(A, q) 2 ^n–1 – 1, which concludes that the complementary cones cannot spanR ⁿ more than 2 ^n–1 – 1 times around. For anyn, an example of ann × n nondegenerateQ-matrix spanning allR ⁿ , but a subset of empty interior, 2^[n/3] times around is given.     

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.     

On the number of nowhere zero points in linear mappings

LetA be a nonsingularn byn matrix over the finite fieldGF _q ,k=n/2,q=p ^a ,a1, wherep is prime. LetP(A,q) denote the number of vectorsx in (GF _q ) ⁿ such that bothx andAx have no zero component. We prove that forn2, and ,P(A,q)[(q–1)(q–3)] ^k (q–2) ^n–2k and describe all matricesA for which the equality holds. We also prove that the result conjectured in [1], namely thatP(A,q)1, is true for allqn+23 orqn+14.     

Abschätzungen der unvollständigen Beta-Funktion in mehreren reellen Variablen und Parametern

The integral ofu ₁ ^p–1 ...u _n ^pn–1 (1–u₁–...–u_n)^q, extended over then-simplex {(u ₁,...,u _n) ₊ ⁿ :u ₁/x ₁+...+u _n/x _n<1}, is estimated from below under the condition thatp ₁+...+p_n+qc=p₁/x₁+...+p_n/x_n=const.     

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

A strong law for weighted sums of i.i.d. random variables

A strong law is proved for weighted sumsS _n=a _in X _i whereX _i are i.i.d. and {a _in} is an array of constants. When sup(n ^–1|a _in | ^q )^1/q <, 1<q andX _i are mean zero, we showE|X| ^p <,p ^l+q ^–1=1 impliesS _n /n 0. Whenq= this reduces to a result of Choi and Sung who showed that when the {a _in} are uniformly bounded,EX=0 andE|X|< impliesS _n /n 0. The result is also true whenq=1 under the additional assumption that lim sup |a _in |n ^–1 logn=0. Extensions to more general normalizing sequences are also given. In particular we show that when the {a _in} are uniformly bounded,E|X|^1/< impliesS _n /n 0 for >1, but this is not true in general for 1/2<<1, even when theX _i are symmetric. In that case the additional assumption that (x ^1/ log^1/–1 x)P(|X|x)0 asx provides necessary and sufficient conditions for this to hold for all (fixed) uniformly bounded arrays {a _in}.     

Return probabilities for random walk on a half-line

A random walk with reflecting zone on the nonnegative integers is a Markov chain whose transition probabilitiesq(x, y) are those of a random walk (i.e.,q(x, y)=p(y–x)) outside a finite set {0, 1, 2,...,K}, and such that the distributionq(x,·) stochastically dominatesp(·–x) for everyx{0, 1, 2,..., K}. Under mild hypotheses, it is proved that when xp _x>0, the transition probabilities satisfyq ⁿ(x, y)C_xyR^–nn^–3/2 asn, and when xp _x=0,q ⁿ(x, y)C_xyn^–1/2.Supported by National Science Foundation Grant DMS-9307855.     

On The Sum of Digits Function for Number Systems with Negative Bases

Let q 2 be an integer. Then –q gives rise to a number system in , i.e., each number n has a unique representation of the form n = c ₀ + c ₁ (–q) + ... + c _h (–q) ^h , with c _i {0,..., q – 1}(0 i h). The aim of this paper is to investigate the sum of digits function _–q (n) of these number systems. In particular, we derive an asymptotic expansion for

On a relation between a cyclic relative difference set associated with the quadratic extensions of a finite field and the Szekeres difference sets

Letq 3 (mod 4) be a prime power and put . We consider a cyclic relative difference set with parametersq ²–1,q, 1,q–1 associated with the quadratic extension GF(q²)/GF((q). The even part and the odd part of the cyclic relative difference set taken modulon are supplementary difference sets. Moreover it turns out that their complementary subsets are identical with the Szekeres difference sets. This result clarifies the true nature of the Szekeres difference sets. We prove these results by using the theory of the relative Gauss sums.     

A Graham-Sloane Type Construction for s-Surjective Matrices

We give a construction of (n–s)-surjective matrices with n columns over using Abelian groups and additive s-bases. In particular we show that the minimum number of rows ms _q(n,n–s) in such a matrix is at most s ^s q ^n–s for all q, n and s.     

Some Asymptotic Formulae for q-Shifted Factorials

The q-shifted factorial defined by (a : q^k) _n = (1 – a) (1 – aq^k)(1 – aq^2k)... (1 – aq^{(n – 1)k}) appears in the terms of basic hypergeometric series. Complete asymptotic expansions as q 1 of some q-shifted factorials are given in terms of polylogarithms and Bernoulli polynomials.     

Linear independence in finite spaces

The maximum number m ₂(n, q) of points in PG(n, q), n2, such that no three are collinear is known precisely for (n, q)=(n,2), (2,q), (3,q), (4, 3), (5,3). In this paper an improved upper bound of order q ^n–1 –1/2q ^n–2 is obtained for q even when n4 and q>2. A necessary preliminary is an improved upper bound for m₂(3, q), the maximum size of a k-cap not contained in an ovoid. It is shown that and that m₂(3, 4)=14.     

Controllability of the wave equation with moving point control

This paper deals with approximate and exact controllability of the wave equation in finite time with interior point control acting along a curve specified in advance in the system's spatial domain. The structure of the control input is dual to the structure of the observations which describe the measurements of velocity and gradient of the solution of the dual system, obtained from the moving point sensor. A relevant formalization of such a control problem is discussed, based on transposition. For any given timeinterval [0,T] the existence of the curves providing approximate controllability inH _D ^–[n/2]–1 ()×H _D ^–[n/2]–1 () (wheren stands for the space dimension) is established with controls fromL ²(0,T; R ⁿ +1). The same curves ensure exact controllability inL ²() × H^–1() if controls are allowed to be selected in [L (0,T; R ⁿ+1)]. Required curves can be constructed to be continuous on [0,T).This work was supported in part by NSF Grant ECS 89-13773 and NASA Grant NAG-1-1081.     

Mixed Partitions of Projective Geometries

Starting from a linear collineation of PG(2n–1,q) suitably constructed from a Singer cycle of GL(n,q), we prove the existence of a partition of PG(2n–1,q) consisting of two (n–1)-subspaces and caps, all having size (qⁿ–1)/(q–1) or (qⁿ–1)/(q+1) according as n is odd or even respectively. Similar partitions of quadrics or hermitian varieties into two maximal totally isotropic subspaces and caps of equal size are also obtained. We finally consider the possibility of partitioning the Segre variety of PG(8,q) into caps of size q²+q+1 which are Veronese surfaces.