This paper mathematically characterizes the tiny feasible regions within the vast 6D rotation–translation space in a full molecular replacement (MR) search. The capability to a priori isolate such regions is potentially important for enhancing robustness and efficiency in computational phasing in macromolecular crystallography (MX). The previous four papers in this series have concentrated on the properties of the full configuration space of rigid bodies that move relative to each other with crystallographic symmetry constraints. In particular, it was shown that the configuration space of interest in this problem is the rightcoset space Γ\ G , where Γ is the space group of the chiral macromolecular crystal and G is the group of rigidbody motions, and that fundamental domains F Γ\ G can be realized in many ways that have interesting algebraic and geometric properties. The cost function in MR methods can be viewed as a function on these fundamental domains. This, the fifth and final paper in this series, articulates the constraints that bodies packed with crystallographic symmetry must obey. It is shown that these constraints define a thin feasible set inside a motion space and that they fall into two categories: (i) the bodies must not interpenetrate, thereby excludingmore »
Mathematical aspects of molecular replacement. IV. Measuretheoretic decompositions of motion spaces
In molecularreplacement (MR) searches, spaces of motions are explored for determining the appropriate placement of rigidbody models of macromolecules in crystallographic asymmetric units. The properties of the space of nonredundant motions in an MR search, called a `motion space', are the subject of this series of papers. This paper, the fourth in the series, builds on the others by showing that when the space group of a macromolecular crystal can be decomposed into a product of two space subgroups that share only the lattice translation group, the decomposition of the group provides different decompositions of the corresponding motion spaces. Then an MR search can be implemented by trading off between regions of the translation and rotation subspaces. The results of this paper constrain the allowable shapes and sizes of these subspaces. Special choices result when the space group is decomposed into a product of a normal Bieberbach subgroup and a symmorphic subgroup (which is a common occurrence in the space groups encountered in protein crystallography). Examples of Sohncke space groups are used to illustrate the general theory in the threedimensional case (which is the relevant case for MR), but the general theory in this paper applies to any dimension.
 Award ID(s):
 1640970
 Publication Date:
 NSFPAR ID:
 10060063
 Journal Name:
 Acta Crystallographica Section A Foundations and Advances
 Volume:
 73
 Issue:
 5
 Page Range or eLocationID:
 387 to 402
 ISSN:
 20532733
 Sponsoring Org:
 National Science Foundation
More Like this


We consider two manifestations of nonpositive curvature: acylindrical actions (on hyperbolic spaces) and quasigeodesic stability. We study these properties for the class of hierarchically hyperbolic groups, which is a general framework for simultaneously studying many important families of groups, including mapping class groups, rightangled Coxeter groups, most 3 3 –manifold groups, rightangled Artin groups, and many others. A group that admits an acylindrical action on a hyperbolic space may admit many such actions on different hyperbolic spaces. It is natural to try to develop an understanding of all such actions and to search for a “best” one. The set of all cobounded acylindrical actions on hyperbolic spaces admits a natural poset structure, and in this paper we prove that all hierarchically hyperbolic groups admit a unique action which is the largest in this poset. The action we construct is also universal in the sense that every element which acts loxodromically in some acylindrical action on a hyperbolic space does so in this one. Special cases of this result are themselves new and interesting. For instance, this is the first proof that rightangled Coxeter groups admit universal acylindrical actions. The notion of quasigeodesic stability of subgroups provides a natural analogue ofmore »

We consider two manifestations of nonpositive curvature: acylindrical actions (on hyperbolic spaces) and quasigeodesic stability. We study these properties for the class of hierarchically hyperbolic groups, which is a general framework for simultaneously studying many important families of groups, including mapping class groups, rightangled Coxeter groups, most 3–manifold groups, rightangled Artin groups, and many others. A group that admits an acylindrical action on a hyperbolic space may admit many such actions on different hyperbolic spaces. It is natural to try to develop an understanding of all such actions and to search for a “best” one. The set of all cobounded acylindrical actions on hyperbolic spaces admits a natural poset structure, and in this paper we prove that all hierarchically hyperbolic groups admit a unique action which is the largest in this poset. The action we construct is also universal in the sense that every element which acts loxodromically in some acylindrical action on a hyperbolic space does so in this one. Special cases of this result are themselves new and interesting. For instance, this is the first proof that rightangled Coxeter groups admit universal acylindrical actions. The notion of quasigeodesic stability of subgroups provides a natural analogue of quasi convexitymore »

At the heart of both lossy compression and clustering is a tradeoff between the fidelity and size of the learned representation. Our goal is to map out and study the Pareto frontier that quantifies this tradeoff. We focus on the optimization of the Deterministic Information Bottleneck (DIB) objective over the space of hard clusterings. To this end, we introduce the primal DIB problem, which we show results in a much richer frontier than its previously studied Lagrangian relaxation when optimized over discrete search spaces. We present an algorithm for mapping out the Pareto frontier of the primal DIB tradeoff that is also applicable to other twoobjective clustering problems. We study general properties of the Pareto frontier, and we give both analytic and numerical evidence for logarithmic sparsity of the frontier in general. We provide evidence that our algorithm has polynomial scaling despite the superexponential search space, and additionally, we propose a modification to the algorithm that can be used where sampling noise is expected to be significant. Finally, we use our algorithm to map the DIB frontier of three different tasks: compressing the English alphabet, extracting informative color classes from natural images, and compressing a group theoryinspired dataset, revealing interestingmore »

We investigate the approximability of the following optimization problem. The input is an n× n matrix A=(Aij) with real entries and an originsymmetric convex body K⊂ ℝn that is given by a membership oracle. The task is to compute (or approximate) the maximum of the quadratic form ∑i=1n∑j=1n Aij xixj=⟨ x,Ax⟩ as x ranges over K. This is a rich and expressive family of optimization problems; for different choices of matrices A and convex bodies K it includes a diverse range of optimization problems like maxcut, Grothendieck/noncommutative Grothendieck inequalities, small set expansion and more. While the literature studied these special cases using casespecific reasoning, here we develop a general methodology for treatment of the approximability and inapproximability aspects of these questions. The underlying geometry of K plays a critical role; we show under commonly used complexity assumptions that polytime constantapproximability necessitates that K has type2 constant that grows slowly with n. However, we show that even when the type2 constant is bounded, this problem sometimes exhibits strong hardness of approximation. Thus, even within the realm of type2 bodies, the approximability landscape is nuanced and subtle. However, the link that we establish between optimization and geometry of Banach spaces allows usmore »