Orthogonal Polynomials on the Ball and the Simplex for Weight Functions with Reflection Symmetries

Generalized classical orthogonal polynomials on the unit ball B ^d and the standard simplex T ^d are orthogonal with respect to weight functions that are reflection-invariant on B ^d and, after a composition, on T ^d , respectively. They are also eigenfunctions of a second-order differential—difference operator that is closely related to Dunkl's h -Laplacian for the reflection groups. Under a proper limit, the generalized classical orthogonal polynomials on B ^d converge to the generalized Hermite polynomials on R ^d , and those on T ^d converge to the generalized Laguerre polynomials on R ^d ₊ . The latter two are related to the Calogero—Sutherland models associated to the Weyl groups of type A and type B . February 14, 2000. Date revised: July 26, 2000. Date accepted: August 4, 2000.     

A Construction of Difference Sets in High Exponent 2-Groups Using Representation Theory

Nontrivial difference sets in groups of order a power of 2 are part of the family of difference sets called Menon difference sets (or Hadamard), and they have parameters (2^2d+2, 2^2d+1±2 ^d , 2^2d ±2 ^d ). In the abelian case, the group has a difference set if and only if the exponent of the group is less than or equal to 2 ^d+2. In [14], the authors construct a difference set in a nonabelian group of order 64 and exponent 32. This paper generalizes that result to show that there is a difference set in a nonabelian group of order 2^2d+2 with exponent 2 ^d+3. We use representation theory to prove that the group has a difference set, and this shows that representation theory can be used to verify a construction similar to the use of character theory in the abelian case.     

Weyl quantization of Lebesgue spaces

We study boundedness and compactness properties for the Weyl quantization with symbols in L^q (?^2d ) acting on L^p (?^d ). This is shown to be equivalent, in suitable Banach space setting, to that of the Wigner transform. We give a short proof by interpolation of Lieb's sufficient conditions for the boundedness of the Wigner transform, proving furthermore that these conditions are also necessary. This yields a complete characterization of boundedness for Weyl operators in L^p setting; compactness follows by approximation. We extend these results defining two scales of spaces, namely L_*^q (?^2d ) and L_?^q (R^2d ), respectively smaller and larger than the L^q (?^2d ),and showing that the Weyl correspondence is bounded on L_*^q (R^2d ) (and yields compact operators), whereas it is not on L_?^q (R^2d ). We conclude with a remark on weak‐type L^p boundedness (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Upper bounds for configurations and polytopes inR d

We give a new upper bound onn ^d(d+1)n on the number of realizable order types of simple configurations ofn points inR ^d , and ofn2d ² n on the number of realizable combinatorial types of simple configurations. It follows as a corollary of the first result that there are no more thann ^d(d+1)n combinatorially distinct labeled simplicial polytopes inR ^d withn vertices, which improves the best previous upper bound ofn ^{cn d/2}.Supported in part by NSF Grant DMS-8501492 and PSC-CUNY Grant 665258.Supported in part by NSF Grant DMS-8501947.     

Cubical d-Polytopes with Few Vertices for d>4

A cubical polytope is a convex polytope all of whose facets are combinatorial cubes. A d-polytope P is called almost simple if, in the graph of P, each vertex of P is d-valent or (d+1)-valent. We show that, for d>4, all but one cubicald -polytopes with up to 2 ^d+1 vertices are almost simple. This provides a complete enumeration of all the cubical d-polytopes with up to 2 ^d+1 vertices, for d>4.     

Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n ^d ) sidedness queries are required to determine whether a set ofn points in ℝ ^d is affinely degenerate, i.e., whether it containsd+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n ^d ) “collapsible” simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n ^d ) lower bound on the number of sidedness queries required to determine the order type of a set ofn points in ℝ ^d . Using similar techniques, we also show that Ω(n ^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set ofn points in ℝ ^d . An earlier version of this paper was presented at the 34th Annual IEEE Symposium on Foundations of Computer Science [8]. This research has been supported by NSF Presidential Young Investigator Grant CCR-9058440.     

Multiple Phase Transitions in Long‐Range First‐Passage Percolation on Square Lattices

We consider a model of long‐range first‐passage percolation on the d‐dimensional square lattice ?d in which any two distinct vertices x,y ? ?^d are connected by an edge having exponentially distributed passage time with mean ‖ x – y ‖^α+o(1), where α > 0 is a fixed parameter and ‖·‖ is the l¹–norm on ?^d. We analyze the asymptotic growth rate of the set ß_t, which consists of all x ? ?^d such that the first‐passage time between the origin 0 and x is at most t as t → ∞. We show that depending on the values of α there are four growth regimes: (i) instantaneous growth for α < ^d, (ii) stretched exponential growth for α ? d,2d), (iii) superlinear growth for α ? (2d,2d + 1), and finally (iv) linear growth for α > 2d + 1 like the nearest‐neighbor first‐passage percolation model corresponding to α=∞. © 2015 Wiley Periodicals, Inc.     

On the length of simplex paths: The assignment case

This paper reports on an experimental study of the distribution of the length of simplex paths for the Optimal Assignment Problem. We study the distribution of the pivot counts for a version of the simplex method that with essentially equal probabilities introduces any variable with negative reduced cost into the basis. In this situation the distribution of the pivot counts turns out to be normally distributed and independent of the actual cost coefficients, provided these are sufficiently spread out. Further, the mean and standard deviation grow only moderately with the size of the problem, namely asd ^1.8, andd ^1.5 respectively for ad×d problem, implying in particular that the pivot counts concentrate around the mean with growingd. The usual simplex method on the other hand gives a growth ofd ^1.6. Hence a large part of the favourable polynomial growth experienced on practical problems may be attributed to the fact that the simplex paths are rather short on the average, at least for assignment problems.     

Estimates of n ‐widths of Besov classes on two‐point homogeneous manifolds

Estimates of Kolmogorov and linear n ‐widths of Besov classes on compact globally symmetric spaces of rank 1 (i.e., on S^d, P^d (?), P^d (?), P^d (?), P¹⁶(Cay)) are established. It is shown that these estimates have sharp orders in different important cases. A new characterisation of Besov spaces is also given (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the cumulants of affine equivariant estimators in elliptical families

Given a statistical model for data which take values in R^d and have elliptically distributed errors, and affine equivariant estimators and of a mean vector in R^dRⁿ and a d × d scatter matrix, expressions are given for the covarances of the estimators in terms of their expectations and some unknown constants that depend on the model and the estimator. Higher order cumulants are also developed. These results place considerable constraints on the possible cumulants of and , as wel as those of estimators of higher order behavior such as multivariate skewness and kurtosis. These expressions are obtained using tensor methods.     

The Semigroup of Ultrafilters Near 0

+ of ultrafiliters on (0,1) that converge to 0 is a semigroup under the restriction of the usual operation + on BetaR _d, the Stone-Cech compactification of the discrete semigroup (R _d,+). It is also a subsemigroup of Beta((0,1) _d,·). The interaction of these operations has recently yielded some strong results in Ramsey Theory. Since (0 ⁺,·) is an ideal of Beta((0,1) _d,·), much is known about the structure of (0 ⁺,·). On the other hand, (0 ⁺,+) is far from being an ideal of ( BetaR _d,+) so little about its algebraic structure follows from known results. We characterize here the smallest ideal of (0 ⁺,+), its closure, and those sets "central" in (0 ⁺,+), that is, those sets which are members of minimal idempotents in (0 ⁺, +). We derive new combinatorial applications of those sets that are central in (0 ⁺,+).     

Stresses and Liftings of Cell-Complexes

This paper introduces a general notion of stress on cell-complexes and reports on connections between stresses and liftings (generalization of C ₁ ⁰ -splines) of d -dimensional cell-complexes in R ^d . New sufficient conditions for the existence of a sharp lifting for a ``flat" piecewise-linear realization of a manifold are given. Our approach also gives some new results on the equivalence between spherical complexes and convex and star polytopes. As an application, two algorithms are given that determine whether a piecewise-linear realization of a d -manifold in R ^d admits a lifting to R ^d+1 which satisfies given constraints. We also demonstrate connections between stresses and Voronoi—Dirichlet diagrams and show that any weighted Voronoi—Dirichlet diagram without non-compact cells can be represented as a weighted Delaunay decomposition and vice versa. Received April 24, 1997, and in revised form July 31, 1998.     

Polynomial Interpolation on the Unit Sphere and on the Unit Ball

The problem of interpolation on the unit sphere S ^d by spherical polynomials of degree at most n is shown to be related to the interpolation on the unit ball B ^d by polynomials of degree n. As a consequence several explicit sets of points on S ^d are given for which the interpolation by spherical polynomials has a unique solution. We also discuss interpolation on the unit disc of R ² for which points are located on the circles and each circle has an even number of points. The problem is shown to be related to interpolation on the triangle in a natural way.     

Construction of spherical t-designs

Spherical t-designs are Chebyshev-type averaging sets on the d-dimensional unit sphere S ^d–1, that are exact for polynomials of degree at most t. The concept of such designs was introduced by Delsarte, Goethals and Seidel in 1977. The existence of spherical t-designs for every t and d was proved by Seymour and Zaslavsky in 1984. Although some sporadic examples are known, no general construction has been given. In this paper we give an explicit construction of spherical t-designs on S ^d–1 containing N points, for every t,d and N,NN ₀, where N ₀ = C(d)t ^{O(d 3}).     

Cubical 4-Polytopes with Few Vertices

A cubical polytope is a convex polytope all of whose facets are conbinatorial cubes. A d-polytope Pis called almost simple if, in the graph of P, each vertex of Pis d-valent of (d+ 1)-valent. It is known that, for d> 4, all but one cubical d-polytopes with up to 2^d+1vertices are almost simple, which provides a complete enumeration of all the cubical d-polytopes with up to 2^d+1vertices. We show that this result is also true for d=4.     

Enumeration of three-dimensional convex polygons

A self-avoiding polygon (SAP) on a graph is an elementary cycle. Counting SAPs on the hypercubic lattice ℤ ^d withd≥2, is a well-known unsolved problem, which is studied both for its combinatorial and probabilistic interest and its connections with statistical mechanics. Of course, polygons on ℤ ^d are defined up to a translation, and the relevant statistic is their perimeter. A SAP on ℤ ^d is said to beconvex if its perimeter is “minimal”, that is, is exactly twice the sum of the side lengths of the smallest hyper-rectangle containing it. In 1984, Delest and Viennot enumerated convex SAPs on the square lattice [6], but no result was available in a higher dimension. We present an elementar approach to enumerate convex SAPs in any dimension. We first obtain a new proof of Delest and Viennot's result, which explains combinatorially the form of the generating function. We then compute the generating function for convex SAPs on the cubic lattice. In a dimension larger than 3, the details of the calculations become very cumbersome. However, our method suggests that the generating function for convex SAPs on ℤ ^d is always a quotient ofdifferentiably finite power series.     

Weighted Approximation of Functions on the Unit Sphere

The direct and inverse theorems are established for the best approximation in the weighted L^p space on the unit sphere of R^d+1, in which the weight functions are invariant under finite reflection groups. The theorems are stated using a modulus of smoothness of higher order, which is proved to be equivalent to a K-functional defined using the power of the spherical h-Laplacian. Furthermore, similar results are also established for weighted approximation on the unit ball and on the simplex of R^d.     

A class of ((p n−p m)(p n−1), p n−p m)-arcs in PG(2, p n)

A (k, d)-arc in PG(2, q) is a set of k points such that some d, but no d+1, of them are collinear. An outstanding problem is to find the maximum value of k for which a (k, d)-arc exists. A construction is given for a class of (k, p ⁿ–p ^m)-arcs in PG(2, p ⁿ). These arcs constitute a lower bound on the maximum possible value of k, and a subset of them is shown to be optimal.     

Tame roots of wild quivers

We study the tame behaviour of the representations of wild quivers Q via tame roots. A positive root d of Q is called a tame root if d is sincere and for any positive sub-root d^′ of d we have q(d^′)0, where q(d^′) is the Tits form of Q. We prove that a sincere root is a tame root if and only if for any decomposition of d into a sum of positive sub-roots d=d¹++d^s, there is at most one dⁱ with q(dⁱ)=0 and q(d^j)=1. This is the essential property of a tame root and it is an alternative way to define tame roots. Then we give the canonical decomposition of a tame root. At the end we prove our main result that for any wild graph, there are only finitely many tame roots.     

A New Family of Cyclic Difference Sets with Singer Parameters in Characteristic Three

We construct a new family of cyclic difference sets with parameters ((3 ^d – 1)/2, (3 ^{d – 1} – 1)/2, (3 ^{d – 2} – 1)/2) for each odd d. The difference sets are constructed with certain maps that form Jacobi sums. These new difference sets are similar to Maschietti's hyperoval difference sets, of the Segre type, in characteristic two. We conclude by calculating the 3-ranks of the new difference sets.