Consequences of Pure Point Diffraction Spectra for Multiset Substitution Systems

   Abstract. There is a growing body of results in the theory of discrete point sets and tiling systems giving conditions under which such systems are pure point diffractive. Here we look at the opposite direction: what can we infer about a discrete point set or tiling, defined through a primitive substitution system, given that it is pure point diffractive? Our basic objects are Delone multisets and tilings, which are self-replicating under a primitive substitution system of affine mappings with a common expansive map Q . Our first result gives a partial answer to a question of Lagarias and Wang: we characterize repetitive substitution Delone multisets that can be represented by substitution tilings using a concept of ``legal cluster.' This allows us to move freely between both types of objects. Our main result is that for lattice substitution multiset systems (in arbitrary dimensions), being a regular model set is not only sufficient for having pure point spectrum—a known fact—but is also necessary. This completes a circle of equivalences relating pure point dynamical and diffraction spectra, modular coincidence, and model sets for lattice substitution systems begun by the first two authors of this paper.     

Consequences of Pure Point Diffraction Spectra for Multiset Substitution Systems

Abstract. There is a growing body of results in the theory of discrete point sets and tiling systems giving conditions under which such systems are pure point diffractive. Here we look at the opposite direction: what can we infer about a discrete point set or tiling, defined through a primitive substitution system, given that it is pure point diffractive? Our basic objects are Delone multisets and tilings, which are self-replicating under a primitive substitution system of affine mappings with a common expansive map Q . Our first result gives a partial answer to a question of Lagarias and Wang: we characterize repetitive substitution Delone multisets that can be represented by substitution tilings using a concept of ``legal cluster.' This allows us to move freely between both types of objects. Our main result is that for lattice substitution multiset systems (in arbitrary dimensions), being a regular model set is not only sufficient for having pure point spectrum—a known fact—but is also necessary. This completes a circle of equivalences relating pure point dynamical and diffraction spectra, modular coincidence, and model sets for lattice substitution systems begun by the first two authors of this paper.     

On the Helly Number for Hyperplane Transversals to Unit Balls

We prove two results about the Hadwiger problem of finding the Helly number for line transversals of disjoint unit disks in the plane, and about its higher-dimensional generalization to hyperplane transversals of unit balls in d -dimensional Euclidean space. These consist of (a) a proof of the fact that the Helly number remains 5 even for arbitrarily large sets of disjoint unit disks—thus correcting a 40-year-old error; and (b) a lower bound of d+3 on the Helly number for hyperplane transversals to suitably separated families of unit balls in R ^d . Received January 25, 1999, and in revised form July 7, 1999.     

Some common fixed point theorems for selfmappings satisfying two contractive conditions of integral type in a uniform space

In this paper, we establish some common fixed point theorems for selfmappings of a uniform space by employing both the concepts of an A—distance and an E—distance introduced by Aamri and El Moutawakil [1] and two contractive conditions of integral type. Our results are generalizations and extensions of the classical Banach’s fixed point theorem of [2, 3, 19], some results of Aamri and El Moutawakil [1], Theorem 2.1 of Branciari [5] as well as a result of Jungck [7].      

Entering and leaving j-facets

Let S be a set of n points in d -space, no i+1 points on a common (i-1) -flat for 1 ≤ i ≤ d . An oriented (d-1) -simplex spanned by d points in S is called a j-facet of S if there are exactly j points from S on the positive side of its affine hull. We show: (*) {\em For j ≤ n/2 - 2 , the total number of (≤ j) -facets (i.e. the number of i -facets with 0 ≤ i ≤ j ) in 3-space is maximized in convex position (where these numbers are known).} A large part of this presentation is a preparatory review of some basic properties of the collection of j -facets—some with their proofs—and of relations to well-established concepts and results from the theory of convex polytopes (h -vector, Dehn—Sommerville relations, Upper Bound Theorem, Generalized Lower Bound Theorem). The relations are established via a duality closely related to the Gale transform—similar to previous works by Lee, by Clarkson, and by Mulmuley. A central definition is as follows. Given a directed line ℓ and a j -facet F of S , we say that {\it ℓ enters F } if ℓ intersects the relative interior of F in a single point, and if ℓ is directed from the positive to the negative side of F . One of the results reviewed is a tight upper bound of j+d-1 \choose d-1 on the maximum number of j -facets entered by a directed line. Based on these considerations, we also introduce a vector for a point relative to a point set, which—intuitively speaking—expresses ``how interior' the point is relative to the point set. This concept allows us to show that statement (*) above is equivalent to the Generalized Lower Bound Theorem for d -polytopes with at most d+4 vertices. Received May 21, 1999, and in revised form July 6, 2000. Online publication January 17, 2001.     

The Pfaff/Cauchy derivative identities and Hurwitz type extensions

More than 200 years ago, Pfaff found two generalizations of Leibniz’s rule for the nth derivative of a product of two functions. Thirty years later Cauchy found two similar identities, one equivalent to one of Pfaff’s and the other new. We give simple proofs of these little-known identities and some further history. We also give applications to Abel-Rothe type binomial identities, Lagrange’s series, and Laguerre and Jacobi polynomials. Most importantly, we give extensions that are related to the Pfaff/Cauchy theorems as Hurwitz’s generalized binomial theorems are to the Abel-Rothe identities. We apply these extensions to Laguerre and Jacobi polynomials as well. Dedicated to Dick Askey on the occasion of his 70th birthday. 2000 Mathematics Subject Classification Primary—05A19; Secondary—33C45     

Construction theorems for polytopes

Certain construction theorems are represented, which facilitate an inductive combinatorial construction of polytopes. That is, applying the constructions to ad-polytope withn vertices, given combinatorially, one gets many combinatoriald-polytopes—and polytopes only—withn+1 vertices. The constructions are strong enough to yield from the 4-simplex all the 1330 4-polytopes with up to 8 vertices.     

The Fermat–Torricelli Problem, Part I: A Discrete Gradient-Method Approach

We give a discrete geometric (differential-free) proof of the theorem underlying the solution of the well known Fermat–Torricelli problem, referring to the unique point having minimal distance sum to a given finite set of non-collinear points in d-dimensional space. Further on, we extend this problem to the case that one of the given points is replaced by an affine flat, and we give also a partial result for the case where all given points are replaced by affine flats (of various dimensions), with illustrative applications of these theorems.     

Optimality conditions and duality for a class of nondifferentiable multi-objective fractional programming problems

A class of multi-objective fractional programming problems (MFP) are considered where the involved functions are locally Lipschitz. In order to deduce our main results, we give the definition of the generalized (F,θ,ρ,d)-convex class about the Clarke’s generalized gradient. Under the above generalized convexity assumption, necessary and sufficient conditions for optimality are given. Finally, a dual problem corresponding to (MFP) is formulated, appropriate dual theorems are proved.      

Carathéodory, Helly and the Others in the Max-Plus World

Carathéodory’s, Helly’s and Radon’s theorems are three basic results in discrete geometry. Their max-plus or tropical analogues have been proved by various authors. We show that more advanced results in discrete geometry also have max-plus analogues, namely, the colorful Carathéodory theorem and the Tverberg theorem. A conjecture connected to the Tverberg theorem—Sierksma’s conjecture—although still open for the usual convexity, is shown to be true in the max-plus setting.     

Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem

The analysis of incomplete data is a long-standing challenge in practical statistics. When, as is typical, data objects are represented by points in ℝ ^d , incomplete data objects correspond to affine subspaces (lines or Δ-flats). With this motivation we study the problem of finding the minimum intersection radius r(ℒ) of a set of lines or Δ-flats ℒ: the least r such that there is a ball of radius r intersecting every flat in ℒ. Known algorithms for finding the minimum enclosing ball for a point set (or clustering by several balls) do not easily extend to higher-dimensional flats, primarily because “distances” between flats do not satisfy the triangle inequality. In this paper we show how to restore geometry (i.e., a substitute for the triangle inequality) to the problem, through a new analog of Helly’s theorem. This “intrinsic-dimension” Helly theorem states: for any family ℒ of Δ-dimensional convex sets in a Hilbert space, there exist Δ+2 sets ℒ′⊆ℒ such that r(ℒ)≤2r(ℒ′). Based upon this we present an algorithm that computes a (1+ε)-core set ℒ′⊆ℒ, |ℒ′|=O(Δ ⁴/ε), such that the ball centered at a point c with radius (1+ε)r(ℒ′) intersects every element of ℒ. The running time of the algorithm is O(n ^Δ+1 dpoly (Δ/ε)). For the case of lines or line segments (Δ=1), the (expected) running time of the algorithm can be improved to O(ndpoly (1/ε)). We note that the size of the core set depends only on the dimension of the input objects and is independent of the input size n and the dimension d of the ambient space. An extended abstract appeared in ACM–SIAM Symposium on Discrete Algorithms, 2006. Work was done when J. Gao was with Center for the Mathematics of Information, California Institute of Technology. Work was done when M. Langberg was a postdoctoral scholar at the California Institute of Technology. Research supported in part by NSF grant CCF-0346991. Research of L.J. Schulman supported in part by an NSF ITR and the Okawa Foundation.     

Points surrounding the origin

Suppose d > 2, n > d+1, and we have a set P of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any p ∈ P, the convex hull of Q∪{p} does not contain the origin in its interior. We also show that for non-empty, finite point sets A ₁, ..., A _d+1 in ℝ ^d , if the origin is contained in the convex hull of A _i ∪ A _j for all 1≤i<j≤d+1, then there is a simplex S containing the origin such that |S∩A _i |=1 for every 1≤i≤d+1. This is a generalization of Bárány’s colored Carathéodory theorem, and in a dual version, it gives a spherical version of Lovász’ colored Helly theorem. Dedicated to Imre Bárány, Gábor Fejes Tóth, László Lovász, and Endre Makai on the occasion of their sixtieth birthdays. Supported by the Norwegian research council project number: 166618, and BK 21 Project, KAIST. Part of the research was conducted while visiting the Courant Institute of Mathematical Sciences. Supported by NSF Grant CCF-05-14079, and by grants from NSA, PSC-CUNY, the Hungarian Research Foundation OTKA, and BSF.     

Subalgebras of the Stanley—Reisner Ring

In [2], Billera proved that the R -algebra of continuous piecewise polynomial functions (C ⁰ splines) on a d -dimensional simplicial complex Δ embedded in R ^d is a quotient of the Stanley—Reisner ring A _Δ of Δ. We derive a criterion to determine which elements of the Stanley—Reisner ring correspond to splines of higher-order smoothness. In [5], Lau and Stiller point out that the dimension of C ^r _k (Δ) is upper semicontinuous in the Zariski topology. Using the criterion, we give an algorithm for obtaining the defining equations of the set of vertex locations where the dimension jumps. Received June 2, 1997, and in revised form December 22, 1997, and March 24, 1998.     

Roof duality,complementation and persistency in quadratic 0–1 optimization

The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenx _i=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.     

Negotiation,preferences over agreements,and the core

We analyze conditions under which negotiated agreements are efficient from the point of view of every possible coalition of negotiators. The negotiators have lexicographic preferences over agreements they reach. Their utility is the first criterion. The coalition reaching an agreement is the second criterion. In the analyzed non-cooperative discrete time bargaining game Γ the players bargain about the choice from the sets of utility vectors feasible for coalitions in a given NTU game (N, V). If Γ has a Markov perfect equilibrium, then the set of equilibrium utility vectors in Markov perfect equilibria in it equals the core of (N, V). I thank an anonymous referee, an anonymous Associate Editor, and the Editor for their comments that helped me to improve the paper. The research reported in this paper was supported by the Grant VEGA 1/1223/04 of the Ministry of Education of the Slovak Republic.     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,f _n) wheref _i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton).     

A short proof of an interesting helly-type theorem

We give a short proof of the theorem that any family of subsets ofR ^d , with the property that the intersection of any nonempty finite subfamily can be represented as the disjoint union of at mostk closed convex sets, has Helly number at mostk(d+1). Some of this work was done at the University of California, Berkeley, where the author was supported by a U.C. Presidents Dissertation Year Fellowship and an AT&T Graduate Research Program for Women Grant.     

Dimension Gaps between Representability and Collapsibility

A simplicial complex K\mathsf{K} is called d -representable if it is the nerve of a collection of convex sets in ℝ ^d ; K\mathsf{K} is d -collapsible if it can be reduced to an empty complex by repeatedly removing a face of dimension at most d−1 that is contained in a unique maximal face; and K\mathsf{K} is d -Leray if every induced subcomplex of K\mathsf{K} has vanishing homology of dimension d and larger. It is known that d-representable implies d-collapsible implies d-Leray, and no two of these notions coincide for d≥2. The famous Helly theorem and other important results in discrete geometry can be regarded as results about d-representable complexes, and in many of these results, “d-representable” in the assumption can be replaced by “d-collapsible” or even “d-Leray.”     

Common Best Proximity Points: Global Optimal Solutions

Let S:A→B and T:A→B be given non-self mappings, where A and B are non-empty subsets of a metric space. As S and T are non-self mappings, the equations Sx=x and Tx=x do not necessarily have a common solution, called a common fixed point of the mappings S and T. Therefore, in such cases of non-existence of a common solution, it is attempted to find an element x that is closest to both Sx and Tx in some sense. Indeed, common best proximity point theorems explore the existence of such optimal solutions, known as common best proximity points, to the equations Sx=x and Tx=x when there is no common solution. It is remarked that the functions x→d(x,Sx) and x→d(x,Tx) gauge the error involved for an approximate solution of the equations Sx=x and Tx=x. In view of the fact that, for any element x in A, the distance between x and Sx, and the distance between x and Tx are at least the distance between the sets A and B, a common best proximity point theorem achieves global minimum of both functions x→d(x,Sx) and x→d(x,Tx) by stipulating a common approximate solution of the equations Sx=x and Tx=x to fulfill the condition that d(x,Sx)=d(x,Tx)=d(A,B). The purpose of this article is to elicit common best proximity point theorems for pairs of contractive non-self mappings and for pairs of contraction non-self mappings, yielding common optimal approximate solutions of certain fixed point equations. Besides establishing the existence of common best proximity points, iterative algorithms are also furnished to determine such optimal approximate solutions.     

Polynomial-time computation of the degree of a dominant morphism in zero characteristic. IV

Consider a projective algebraic variety W that is an irreducible component of the set of all common zeros of a family of homogeneous polynomials of degrees less than d in n + 1 variables in zero characteristic. Consider a dominant rational morphism from W to W′ given by homogeneous polynomials of degree d′. We suggest algorithms for constructing objects in general position related to this morphism. These algorithms are deterministic and polynomial in (dd′) ⁿ and the size of the input. This work concludes a series of four papers. Bibliography: 13 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 360, 2008, pp. 260–294.