3-regularity in generalized quadrangles of order (s,s 2)

If (x, y, z) is a 3-regular triad of a generalized quadrangle S=(P, B, I) of order (s, s ²), s even, then {x, y, z} {x, y, z} is contained in a subquadrangle of order s. As an application it is proved that a generalized quadrangle of order (4, 16) with at least one 3-regular triad is isomorphic to the classical generalized quadrangle Q(5, 4) of order (4, 16).     

Orthogonal Groups 𝒪(n) over GF(2) as Automorphisms

Let (V, Q) be a quadratic vector space over a fixed field. Orthogonal group 𝒪(V, Q) is defined as automorphisms on (V, Q). If Q = I, it is 𝒪(V, I) = 𝒪(n). There is a nice result that 𝒪(n) ? Aut(𝔬(n)) over ? or ?, where 𝔬(n) is the Lie algebra of n × n alternating matrices over the field. How about another field The answer is “Yes” if it is GF(2). We show it explicitly with the combinatorial basis ?. This is a verification of Steinberg's main result in 1961, that is, Aut(𝔬(n)) is simple over the square field, with a nonsimple exception Aut(𝔬(5)) ? 𝒪(5) ? 𝔖₆.     

A remark on uniform spaces with invariant nonstandard hulls

Let (X , Γ) be a uniform space with its uniformity generated by a set of pseudo‐metrics Γ. Let the symbol ? denote the usual infinitesimal relation on *X , and define a new infinitesimal relation ≈ on *X by writing x ≈ y whenever *? (x, p ) ? *? (y, p ) for each ? ∈ Γ and each p ∈ X . We call (X , Γ) an S‐space if the relations ? and ≈ coincide on fin(*X ). S ‐spaces are interesting because their nonstandard hulls have representations within Nelson's internal set theory (IST, [5]). This was shown in [1], where it was also observed that the class of uniform spaces that have invariant nonstandard hulls is contained in the class of S ‐spaces. The question of whether there are S ‐spaces that do not have invariant nonstandard hulls was left open in [1]. In this note we show that when the uniformity of an S ‐space is given by a single pseudometric, the space has invariant nonstandard hulls. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Remarks onB(H) ⊗B(H)

We review the existing proofs that the min and max norms are different onB(H) ⊗B(H) and give a shortcut avoiding the consideration of non-separable families of operator spaces.     

Gauge Orbit Types for Theories with Gauge Group O(n), SO(n) or Sp(n)

We determine the orbit types of the action of the group of local gauge transformations on the space of connections in a principal bundle with structure group O(n), SO(n) or Sp(n) over a closed, simply connected manifold of dimension 4. On the way we derive a classification of Howe subgroups of SO(n) up to conjugacy.     

Adaptive sampling for geometric problems over data streams

Geometric coordinates are an integral part of many data streams. Examples include sensor locations in environmental monitoring, vehicle locations in traffic monitoring or battlefield simulations, scientific measurements of earth or atmospheric phenomena, etc. This paper focuses on the problem of summarizing such geometric data streams using limited storage so that many natural geometric queries can be answered faithfully. Some examples of such queries are: report the smallest convex region in which a chemical leak has been sensed, or track the diameter of the dataset, or track the extent of the dataset in any given direction. One can also pose queries over multiple streams: for instance, track the minimum distance between the convex hulls of two data streams, report when datasets A and B are no longer linearly separable, or report when points of data stream A become completely surrounded by points of data stream B, etc. These queries are easily extended to more than two streams.

In this paper, we propose an adaptive sampling scheme that gives provably optimal error bounds for extremal problems of this nature. All our results follow from a single technique for computing the approximate convex hull of a point stream in a single pass. Our main result is this: given a stream of two-dimensional points and an integer r, we can maintain an adaptive sample of at most 2r+1 points such that the distance between the true convex hull and the convex hull of the sample points is O(D/r²), where D is the diameter of the sample set. The amortized time for processing each point in the stream is O(logr). Using the sample convex hull, all the queries mentioned above can be answered approximately in either O(logr) or O(r) time.     

Flexible polyhedra in Minkowski 3-space

 We prove that (non-immersed) flexible polyhedra do exist in the Minkowski 3-space and each of them preserves the (generalized) volume and the (total) mean curvature during a flex. To prove the latter result, we introduce the notion of the angle between two arbitrary non-null nonzero vectors in the Minkowski plane. Received: 16 August 2001 Published online: 19 May 2003 Mathematics Subject Classification (2000): 52C25, 51B20, 52B70, 52B11, 51M25     

Convergence results for maximum likelihood type estimators in multivariable ARMA models II

The consistency proof for the (Gaussian quasi) maximum likelihood estimator in multivariable ARMA models as given in Dunsmuir and Hannan (1976, Adv, in Appl. Probab. 8, 339–364) rests on a certain property of the underlying parameter space, called B6 in their paper. It is not known whether the usual parameter spaces like the manifold M(n) or the parameter spaces corresponding to echelon forms satisfy condition B6, since the argument given by Dunsmuir and Hannan to establish this fact is inconclusive. In Pötscher (1987, J. Multivariate Anal. 21 29–52) it was shown how consistency can be proved without relying on B6 if the data generating process is Gaussian. In this note we show that the Gaussianity assumption can be replaced by ergodicity thus restoring Dunsmuir and Hannan's consistency proof to its full generality and extending it to parameter spaces which do not satisfy condition B6.     

Constrained Minkowski Sums: A Geometric Framework for Solving Interval Problems in Computational Biology Efficiently

In this paper, we introduce the notion of a constrained Minkowski sum: for two (finite) point-sets P,Q⊆ℝ² and a set of k inequalities Ax≥b, it is defined as the point-set (P ⊕ Q) _Ax≥b ={x=p+q∣p∈P,q∈Q,Ax≥b}. We show that typical interval problems from computational biology can be solved by computing a set containing the vertices of the convex hull of an appropriately constrained Minkowski sum. We provide an algorithm for computing such a set with running time O(Nlog N), where N=|P|+|Q| if k is fixed. For the special case where P and Q consist of points with integer x ₁-coordinates whose absolute values are bounded by O(N), we even achieve a linear running time O(N). We thereby obtain a linear running time for many interval problems from the literature and improve upon the best known running times for some of them. The main advantage of the presented approach is that it provides a general framework within which a broad variety of interval problems can be modeled and solved. T. Bernholt gratefully acknowledges the Deutsche Forschungsgemeinschaft for the financial support (SFB 475, “Reduction of complexity in multivariate data structures”).     

On (k,n)-blocking sets which can be obtained as a union of conics

A family of conics in PG(2,q) is called saturated if any line LPG(2,q) is incident with at least one conic of the family. Then, if <(q+1)/2, the support of is a (k,n)-blocking set. It is shown that in this way one can get blocking sets whose character n is small compared to q; it is also shown that cannot be taken independent of q, but must necessarily increase as q does.     

Numerical solutions to coupled-constraint (or generalised Nash) equilibrium problems

This paper is about games where the agents face constraints in the combined strategy space (unlike in standard games where the action sets are defined separately for each player) and about computational methods for solutions to such games. The motivation examples for such games include electricity generation problems with transmission capacity constraints, environmental management to control pollution and internet switching to comply to buffers of bounded capacity. In each such problem a regulator may aim at compliance to standards or quotas through taxes or charges. The relevant solution concept for these games has been known under several names like generalised Nash equilibrium, coupled constraint equilibrium and more. Existing numerical methods converging to such an equilibrium will be explained. Application examples of use of NIRA, which is a suite of Matlab routines that implement one of the methods, will be provided.      

On Backward p(x)-Parabolic Equations for Image Enhancement

In this study, we investigate the backward p(x)-parabolic equation as a new methodology to enhance images. We propose a novel iterative regularization procedure for the backward p(x)-parabolic equation based on the nonlinear Landweber method for inverse problems. The proposed scheme can also be extended to the family of iterative regularization methods involving the nonlinear Landweber method. We also investigate the connection between the variable exponent p(x) in the proposed energy functional and the diffusivity function in the corresponding Euler-Lagrange equation. It is well known that the forward problems converges to a constant solution destroying the image. The purpose of the approach of the backward problems is twofold. First, solving the backward problem by a sequence of forward problems, we obtain a smooth image which is denoised. Second, by choosing the initial data properly, we try to reduce the blurriness of the image. The numerical results for denoising appear to give improvement over standard methods as shown by preliminary results.     

On Some Geometric Representations of GL N (𝔬)

We study a family of complex representations of the group GL _n (𝔬), where 𝔬 is the ring of integers of a non-archimedean local field F. These representations occur in the restriction of the Grassmann representation of GL _n (F) to its maximal compact subgroup GL _n (𝔬). We compute explicitly the transition matrix between a geometric basis of the Hecke algebra associated with the representation and an algebraic basis that consists of its minimal idempotents. The transition matrix involves combinatorial invariants of lattices of submodules of finite 𝔬-modules. The idempotents are p-adic analogs of the multivariable Jacobi polynomials.     

Multiplicative perturbations in semigroup theory with the (Z)-condition

In [4] the (Z)-condition was introduced by G. W. Desch and W. Schappacher. This condition on a Banach spaceZ and a generatorA inX ensures thatA(I+B) and(I+B)A generateC ₀-semigroups, ifB has its range inZ. In this paper we will consider how certain properties of the semigroup generated byA are inherited by the semigroups generated byA(I+B) and(I+B)A. We shall furthermore investigate a related condition, that simplifies certain sufficiency assumptions given previously.     

Representations of the exceptional lie superalgebraE(3, 6) I: Degeneracy conditions

Recently one of the authors obtained a classification of simple infinite dimensional Lie superalgebras of vector fields which extends the well known classification of E. Cartan in the Lie algebra case. The list consists of many series defined by simple equations, and of several exceptional superalgebras, among themE(3, 6).In the article we study irreducible representations of the exceptional Lie superalgebraE(3, 6). This superalgebra hass(3)×s(2)×g(1) as the zero degree component of the consistent -grading which leads us to believe that its representation theory has potential for physical applications.Supported in part by NSF grant DMS-9970007.     

Compressing spatio-temporal trajectories

A trajectory is a sequence of locations, each associated with a timestamp, describing the movement of a point. Trajectory data is becoming increasingly available and the size of recorded trajectories is getting larger. In this paper we study the problem of compressing planar trajectories such that the most common spatio-temporal queries can still be answered approximately after the compression has taken place. In the process, we develop an implementation of the Douglas–Peucker path-simplification algorithm which works efficiently even in the case where the polygonal path given as input is allowed to self-intersect. For a polygonal path of size n, the processing time is O(nlog^kn) for k=2 or k=3 depending on the type of simplification.     

Classification of lattice-regular lattice convex polytopes

We completely describe lattice convex polytopes in ℝ ⁿ (for any dimension n) that are regular with respect to the group of affine transformations preserving the lattice. Supported in part by the RFBR (Grant Nos. SS-1972.2003.1 and 05-01-01012a) and the NWO-RFBR (Grant No. 047.011.2004.026/RFBR No. 05-02-89000-NWO_a).     

A k-mean-directions Algorithm for Fast Clustering of Data on the Sphere

A k-means-type algorithm is proposed for efficiently clustering data constrained to lie on the surface of a p-dimensional unit sphere, or data that are mean-zero-unit-variance standardized observations such as those that occur when using Euclidean distance to cluster time series gene expression data using a correlation metric. We also provide methodology to initialize the algorithm and to estimate the number of clusters in the dataset. Results from a detailed series of experiments show excellent performance, even with very large datasets. The methodology is applied to the analysis of the mitotic cell division cycle of budding yeast dataset of Cho et al. [Molecular Cell (1998), 2, 65–73]. The entire dataset has not been analyzed previously, so our analysis provides an understanding for the complete set of genes acting in concert and differentially. We also use our methodology on the submitted abstracts of oral presentations made at the 2008 Joint Statistical Meetings (JSM) to identify similar topics. Our identified groups are both interpretable and distinct and the methodology provides a possible automated tool for efficient parallel scheduling of presentations at professional meetings.

The supplemental materials described in the article are available in the online supplements.     

Minimizing synchronization in IDR (s)

IDR (s) is a family of fast algorithms for iteratively solving large nonsymmetric linear systems. With cluster computing and in particular with Grid computing, the inner product is a bottleneck operation. In this paper, three techniques are investigated for alleviating this bottleneck. First, a recently proposed IDR (s) algorithm that is highly efficient and stable is reformulated in such a way that it has a single global synchronization point per iteration step. Second, the so‐called test matrix is chosen so that the work, communication, and storage involving this matrix is minimized in multi‐cluster environments. Finally, a methodology is presented for a‐priori estimation of the optimal value of s using only problem and machine‐based parameters. Numerical experiments applied to a 3D convection–diffusion problem are performed on the DAS‐3 Grid computer, demonstrating the effectiveness of our approach. Copyright © 2011 John Wiley & Sons, Ltd.     

Continued fraction expansions of matrix eigenvectors

We examine various properties of the continued fraction expansions of matrix eigenvector slopes of matrices from the SL(2, ℤ) group. We calculate the average period length, maximum period length, average period sum, maximum period sum, and the distributions of 1s, 2s, and 3s in the periods versus the radius of the ball within which the matrices are located. We also prove that the periods of continued fraction expansions from the real irrational roots of x ²+px+q=0 are always palindromes.