The bias of three pseudo-random shuffles

Three schemes for shuffling a deck ofn cards are studied, each involving a random choice from [n] ⁿ . The shuffles favor some permutations over others sincen! does not dividen ⁿ . The probabilities that the shuffles lead to some simple permutations, for instance cycles left and right and the identity, are calculated. Some inequalities are obtained which lead to information about the least and most likely permutations. Numbers of combinatorial interest occur, notably the Catalan numbers and the Bell numbers.     

The conditioning of the stiffness matrix for certain elements approximating the incompressibility condition in fluid dynamics

Summary In order to solve the Stokes equations numerically, Crouzeix and Raviart introduced elements satisfying a discrete divergence condition. For the two dimensional case and uniform triangulations it is shown, that using the standard basis functions, the conditioning of the stiffness matrix is of orderN ², whereN is the dimension of the corresponding finite element space. Hierarchical bases are introduced which give a condition number of orderN log(N)³.     

On the rate of convergence to normality for generalized linear rank statistics

Summary A generalized linear rank statistic is introduced to include, as special cases, both signed as well as unsigned linear rank statistics. For this statistic, the rate of convergence to asymptotic normality is investigated. It is shown that this rate is of orderO(N ^−1/2 logN) if the score generating function ϕ is twice differentiable, and it is of orderO(N ^−1/2) if the second derivative of ϕ satisfies Lipschitz's condition of order ≧1/2. The results obtained extend as well as generalize most of the earlier results obtained in this direction.     

Translation planes of large dimension admitting nonsolvable groups

In this article, the question is considered whether there exist finite translation planes with arbitrarily small kernels admitting nonsolvable collineation groups. For any integerN, it is shown that there exist translation planes of dimension >N and orderq ³ admittingGL(2,q) as a collineation group.     

A group theoretic characterization of finite derivable nets

In this article, it is shown that a finite net of orderq ² and degreeq + 1 is a derivable net if and only if the net admits a collineation group isomorphic toPSL(4,q)_N (whereN is a line of the associated 3-dimensional projective space upon which the abstract group acts).     

On thep-ranks of net graphs

Let be ak-net of ordern with line-point incidence matrixN and letA be the adjacency matrix of its collinearity graph. In this paper we study thep-ranks (that is, the rank over ) of the matrixA+kl withp a prime dividingn. SinceA+kI=N ^T N thesep-ranks are closely related to thep-ranks ofN. Using results of Moorhouse on thep-ranks ofN, we can determiner _p (A+kI) if is a 3-net (latin square) or a desarguesian net of prime order. On the other hand we show how results for thep-ranks ofA+kI can be used to get results for thep-ranks ofN, especially in connection with the Moorhouse conjecture. Finally we generalize the result of Moorhouse on thep-rank ofN for desarguesian nets of orderp a bit to special subnets of the desarguesian affine plane of orderp ^e .The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities.     

Smoothing noisy data with spline functions

Summary A procedure for calculating the trace of the influence matrix associated with a polynomial smoothing spline of degree2m–1 fitted ton distinct, not necessarily equally spaced or uniformly weighted, data points is presented. The procedure requires orderm ² n operations and therefore permits efficient orderm ² n calculation of statistics associated with a polynomial smoothing spline, including the generalized cross validation. The method is a significant improvement over an existing method which requires ordern ³ operations.     

On translation planes of orderq 3 that admit a collineation group of orderq 3

Let II be a translation plane of orderq ³, with kernel GF(q) forq a prime power, that admits a collineation groupG of orderq ³ in the linear translation complement. Moreover, assume thatG fixes a point at infinity, acts transitively on the remaining points at infinity andG/E is an abelian group of orderq ², whereE is the elation group ofG.In this article, we determined all such translation planes. They are (i) elusive planes of type I or II or (ii) desirable planes.Furthermore, we completely determined the translation planes of orderp ³, forp a prime, admitting a collineation groupG of orderp ³ in the translation complement such thatG fixes a point at infinity and acts transitively on the remaining points at infinity. They are (i) semifield planes of orderp ³ or (ii) the Sherk plane of order 27.     

An algorithm for finding optimal integration lattices of composite order

In this paper we describe a search algorithm that can be used to determine good lattices of orderN whenN=N _L N _R has two nontrivial integer factors. This algorithm is based on relationships between an integer latticeA _R of orderN _R and its various sublattices all of orderN. Using this we have determined all four dimensional good lattices of order 599 or less. Our list has 23 entries.This work was supported by the Applied Mathematical Sciences Subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the Norwegian Council for Humanities and Science.     

An efficient method for calculating smoothing splines using orthogonal transformations

Summary A procedure for calculating the mean squared residual and the trace of the influence matrix associated with a polynomial smoothing spline of degree 2m–1 using an orthogonal factorization is presented. The procedure substantially overcomes the problem of ill-conditioning encountered by a recently developed method which employs a Cholesky factorization, but still requires only orderm ² n operations and ordermn storage.     

Permutability of minimal subgroups and<Emphasis Type="Italic">p</Emphasis>-nilpotency of finite groups

In this paper it is proved that ifp is a prime dividing the order of a groupG with (|G|,p − 1) = 1 andP a Sylowp-subgroup ofG, thenG isp-nilpotent if every subgroup ofP ∩G ^N of orderp is permutable inN _G (P) and whenp = 2 either every cyclic subgroup ofP ∩G ^N of order 4 is permutable inN _G (P) orP is quaternion-free. Some applications of this result are given. The research of the first author is supported by a grant of Shanxi University and a research grant of Shanxi Province, PR China. The research of the second author is partially supported by a UGC(HK) grant #2160126 (1999/2000).     

Automorphisms of groups of orderp 5

We study automorphisms of groups of orderp ⁵ (p is an odd prime number). Groups without any automorphism of order 2 and groups with group automorphisms of orderp ⁶ are found.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 4, pp. 562–565, April, 1995.     

On additive Schwarz preconditioners for sparse grid discretizations

Summary Based on the framework of subspace splitting and the additive Schwarz scheme, we give bounds for the condition number of multilevel preconditioners for sparse grid discretizations of elliptic model problems. For a BXP-like preconditioner we derive an estimate of the optimal orderO(1) and for a HB-like variant we obtain an estimate of the orderO(k ² ·2 ^k/2 ), wherek denotes the number of levels employed. Furthermore, we confirm these results by numerically computed condition numbers.     

L 2 estimates for the finite element method for the Dirichlet problem with singular data

Summary In this paper we consider the approximation by the finite element method of second order elliptic problems on convex domains and homogeneous Dirichlet condition on the boundary. In these problems the data are Borel measures. Using a quasiuniform mesh of finite elements and polynomials of degree 1, we prove that in two dimensions the convergence is of orderh inL ² and in three dimensions of orderh ^1/2.     

Accurate computation of higher Sturm-Liouville eigenvalues

Summary The computation of eigenvalues of regular Sturm-Liouville problems is considered. It is shown that a simple step-dependent linear multistep method can be used to reduce the error of the orderk ⁴ h ² of the centered finite difference estimate of thek-th eigenvalue with uniform step lengthh, to an error of orderkh ². By an appropriate minimization of the local error term of the method one can obtain even more accurate results. A comparison of the simple correction techniques of Paine, de Hoog and Anderssen and of Andrew and Paine is given. Numerical examples demonstrate the usefulness of this correction even for low values ofk.Research Director of the National Fund for Scientific Research (N.F.W.O. Belgium)     

On (p a,p, p a,p a−1 )-relative difference sets

Abelian relative difference sets of parameters (m, n, k, )=(p ^a , p, p ^a , p ^a–1 )are studied in this paper. In particular, we show that for an abelian groupG of orderp ^2c+1 and a subgroupN ofG of orderp, a (p ^2c , p, p ^2c , p ^2c–1 )-relative difference set exists inG relative toN if and only if exp (G)p ^c+1 .Furthermore, we have some structural results on (p ^2c p, p ^2c , p ^2c–1 )-relative difference sets in abelian groups of exponentp ^c+1 . We also show that for an abelian groupG of order 2^2c+2 and a subgroupN ofG of order 2, a (2^2c+1, 2, 2^2c+1, 2^2c )-relative difference set exists inG relative toN if and only if exp(G)2 ^c+2 andN is contained in a cyclic subgroup ofG of order 4. New constructions of (p ^2c+1 , p, p ^2c+1 , p ^2c )-relative difference sets, wherep is an odd prime, are given. However, we cannot find the necessary and sufficient condition for this case.     

Torsion sur des familles de courbes de genre g

We construct here, forl=2g ² +2g+1 or2g ² +3g+1, a family with one parameter of hyperelliptic curves of genusg overQ such that its jacobian has a point of orderl rational overQ(t). Wheng=2 the method allows to construct, forl=17, 19 or 21 a family with one parameter of hyperelliptic curves of genus 2 overQ such that its jacobian has a point of orderl rational overQ(t).      

Greedy maximum-clique decompositions

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. We have recently shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. A greedy max-clique decomposition is a particular kind cf greedy clique decomposition where maximum cliques are removed, instead of just maximal ones. In this paper, we show that any greedy max-clique decompositionC of a graph of ordern has, wheren(C) is the number of vertices inC.     

Multilevel preconditioning on the refined interface and optimal boundary solvers for the Laplace equation

In this paper we propose and analyze some strategies to construct asymptotically optimal algorithms for solving boundary reductions of the Laplace equation in the interior and exterior of a polygon. The interior Dirichlet or Neumann problems are, in fact, equivalent to a direct treatment of the Dirichlet-Neumann mapping or its inverse, i.e., the Poincaré-Steklov (PS) operator. To construct a fast algorithm for the treatment of the discrete PS operator in the case of polygons composed of rectangles and regular right triangles, we apply the Bramble-Pasciak-Xu (BPX) multilevel preconditioner to the equivalent interface problem in theH ^1/2-setting. Furthermore, a fast matrix-vector multiplication algorithm is based on the frequency cutting techniques applied to the local Schur complements associated with the rectangular substructures specifying the nonmatching decomposition of a given polygon. The proposed compression scheme to compute the action of the discrete interior PS operator is shown to have a complexity of the orderO(N log ^q N),q [2, 3], with memory needsO(N log² N), whereN is the number of degrees of freedom on the polygonal boundary under consideration. In the case of exterior problems we propose a modification of the standard direct BEM whose implementation is reduced to the wavelet approximation applied to either single layer or hypersingular harmonic potentials and, in addition, to the matrix-vector multiplication for the discrete interior PS operator.     

Base tensorielle des matrices de Hankel (ou de Toeplitz) Applications

Summary The set of all Hankel (or Toeplitz) matrices of dimensionn, is shown to possess tensorial bases: bases made ofn rank one matrices. Four families of such tensorial bases are possible. From this result, we deduce that the following computations can be performed with a number of multiplications of ordern instead of ordern ²: evaluation of the 2n+1 coefficients of the polynomial product of two polynomials of degreen, evaluation of the inverse of a lower triangular toeplitz matrix, evaluation of the quotient and of the remainder in the division of a polynomial of degree 2n by a polynomial of degreen.