Packing spheres in high dimensions with moderate computational effort.

We generate nonlattice packings of spheres in up to 22 dimensions using the geometrical constraint satisfaction algorithm RRR. Our aggregated data suggest that it is easy to double the density of Ball's lower bound and, more tentatively, that the exponential decay rate of the density can be improved relative to Minkowski's longstanding 1/2.

Learning grammar with a divide-and-concur neural network.

We implement a divide-and-concur iterative projection approach to context-free grammar inference. Unlike most state-of-the-art models of natural language processing, our method requires a relatively small number of discrete parameters, making the inferred grammar directly interpretable-one can read off from a solution how to construct grammatically valid sentences. Another advantage of our approach is the ability to infer meaningful grammatical rules from just a few sentences, compared to the hundreds of gigabytes of training data many other models employ. We demonstrate several ways of applying our approach: classifying words and inferring a grammar from scratch, taking an existing grammar and refining its categories and rules, and taking an existing grammar and expanding its lexicon as it encounters new words in new data.

Reconstructing cellular automata rules from observations at nonconsecutive times.

Recent experiments have shown that a deep neural network can be trained to predict the action of t steps of Conway's Game of Life automaton given millions of examples of this action on random initial states. However, training was never completely successful for t>1, and even when successful, a reconstruction of the elementary rule (t=1) from t>1 data is not within the scope of what the neural network can deliver. We describe an alternative network-like method, based on constraint projections, where this is possible. From a single data item this method perfectly reconstructs not just the automaton rule but also the states in the time steps it did not see. For a unique reconstruction, the size of the initial state need only be large enough that it and the t-1 states it evolves into contain all possible automaton input patterns. We demonstrate the method on 1D binary cellular automata that take inputs from n adjacent cells. The unknown rules in our experiments are not restricted to simple rules derived from a few linear functions on the inputs (as in Game of Life), but include all 2^{2^{n}} possible rules on n inputs. Our results extend to n=6, for which exhaustive rule-search is not feasible. By relaxing translational symmetry in space and also time, our method is attractive as a platform for the learning of binary data, since the discreteness of the variables does not pose the same challenge it does for gradient-based methods.

Charge-order-enhanced capacitance in semiconductor moiré superlattices.

Van der Waals moiré materials have emerged as a highly controllable platform to study electronic correlation phenomena1-17. Robust correlated insulating states have recently been discovered at both integer and fractional filling factors of semiconductor moiré systems10-17. In this study we explored the thermodynamic properties of these states by measuring the gate capacitance of MoSe2/WS2 moiré superlattices. We observed a series of incompressible states for filling factors 0-8 and anomalously large capacitance in the intervening compressible regions. The anomalously large capacitance, which was nearly 60% above the device's geometrical capacitance, was most pronounced at small filling factors, below the melting temperature of the charge-ordered states, and for small sample-gate separation. It is a manifestation of the device-geometry-dependent Coulomb interaction between electrons and phase mixing of the charge-ordered states. Based on these results, we were able to extract the thermodynamic gap of the correlated insulating states and the device's electronic entropy and specific heat capacity. Our findings establish capacitance as a powerful probe of the correlated states in semiconductor moiré systems and demonstrate control of these states via sample-gate coupling.

Correlated insulating states at fractional fillings of moiré superlattices.

Quantum particles on a lattice with competing long-range interactions are ubiquitous in physics; transition metal oxides1,2, layered molecular crystals3 and trapped-ion arrays4 are a few examples. In the strongly interacting regime, these systems often show a rich variety of quantum many-body ground states that challenge theory2. The emergence of transition metal dichalcogenide moiré superlattices provides a highly controllable platform in which to study long-range electronic correlations5-12. Here we report an observation of nearly two dozen correlated insulating states at fractional fillings of tungsten diselenide/tungsten disulfide moiré superlattices. This finding is enabled by a new optical sensing technique that is based on the sensitivity to the dielectric environment of the exciton excited states in a single-layer semiconductor of tungsten diselenide. The cascade of insulating states shows an energy ordering that is nearly symmetric about a filling factor of half a particle per superlattice site. We propose a series of charge-ordered states at commensurate filling fractions that range from generalized Wigner crystals7 to charge density waves. Our study lays the groundwork for using moiré superlattices to simulate a wealth of quantum many-body problems that are described by the two-dimensional extended Hubbard model3,13,14 or spin models with long-range charge-charge and exchange interactions15,16.

Solving protein structure from sparse serial microcrystal diffraction data at a storage-ring synchrotron source.

In recent years, the success of serial femtosecond crystallography and the paucity of beamtime at X-ray free-electron lasers have motivated the development of serial microcrystallography experiments at storage-ring synchrotron sources. However, especially at storage-ring sources, if a crystal is too small it will have suffered significant radiation damage before diffracting a sufficient number of X-rays into Bragg peaks for peak-indexing software to determine the crystal orientation. As a consequence, the data frames of small crystals often cannot be indexed and are discarded. Introduced here is a method based on the expand-maximize-compress (EMC) algorithm to solve protein structures, specifically from data frames for which indexing methods fail because too few X-rays are diffracted into Bragg peaks. The method is demonstrated on a real serial microcrystallography data set whose signals are too weak to be indexed by conventional methods. In spite of the daunting background scatter from the sample-delivery medium, it was still possible to solve the protein structure at 2.1 Šresolution. The ability of the EMC algorithm to analyze weak data frames will help to reduce sample consumption. It will also allow serial microcrystallography to be performed with crystals that are otherwise too small to be feasibly analyzed at storage-ring sources.

Electron ptychography of 2D materials to deep sub-ångström resolution.

Aberration-corrected optics have made electron microscopy at atomic resolution a widespread and often essential tool for characterizing nanoscale structures. Image resolution has traditionally been improved by increasing the numerical aperture of the lens (α) and the beam energy, with the state-of-the-art at 300 kiloelectronvolts just entering the deep sub-ångström (that is, less than 0.5 ångström) regime. Two-dimensional (2D) materials are imaged at lower beam energies to avoid displacement damage from large momenta transfers, limiting spatial resolution to about 1 ångström. Here, by combining an electron microscope pixel-array detector with the dynamic range necessary to record the complete distribution of transmitted electrons and full-field ptychography to recover phase information from the full phase space, we increase the spatial resolution well beyond the traditional numerical-aperture-limited resolution. At a beam energy of 80 kiloelectronvolts, our ptychographic reconstruction improves the image contrast of single-atom defects in MoS2 substantially, reaching an information limit close to 5α, which corresponds to an Abbe diffraction-limited resolution of 0.39 ångström, at the electron dose and imaging conditions for which conventional imaging methods reach only 0.98 ångström.

Erratum: Reconstructing three-dimensional protein crystal intensities from sparse unoriented two-axis X-ray diffraction patterns. Corrigendum.

[This corrects the article DOI: 10.1107/S1600576717006537.].

Formation pathways of mesoporous silica nanoparticles with dodecagonal tiling.

Considerable progress in the fabrication of quasicrystals demonstrates that they can be realized in a broad range of materials. However, the development of chemistries enabling direct experimental observation of early quasicrystal growth pathways remains challenging. Here, we report the synthesis of four surfactant-directed mesoporous silica nanoparticle structures, including dodecagonal quasicrystalline nanoparticles, as a function of micelle pore expander concentration or stirring rate. We demonstrate that the early formation stages of dodecagonal quasicrystalline mesoporous silica nanoparticles can be preserved, where precise control of mesoporous silica nanoparticle size down to <30 nm facilitates comparison between mesoporous silica nanoparticles and simulated single-particle growth trajectories beginning with a single tiling unit. Our results reveal details of the building block size distributions during early growth and how they promote quasicrystal formation. This work identifies simple synthetic parameters, such as stirring rate, that may be exploited to design other quasicrystal-forming self-assembly chemistries and processes.Probing the growth pathways of quasicrystalline materials, where tiling units arrange with local but no long-range order, remains challenging. Here, the authors demonstrate that dodecagonal tiling of mesoporous silica nanoparticles occurs via irreversible packing of micelles with non-uniform size distribution.

Reconstructing three-dimensional protein crystal intensities from sparse unoriented two-axis X-ray diffraction patterns.

Recently, there has been a growing interest in adapting serial microcrystallography (SMX) experiments to existing storage ring (SR) sources. For very small crystals, however, radiation damage occurs before sufficient numbers of photons are diffracted to determine the orientation of the crystal. The challenge is to merge data from a large number of such 'sparse' frames in order to measure the full reciprocal space intensity. To simulate sparse frames, a dataset was collected from a large lysozyme crystal illuminated by a dim X-ray source. The crystal was continuously rotated about two orthogonal axes to sample a subset of the rotation space. With the EMC algorithm [expand-maximize-compress; Loh & Elser (2009). Phys. Rev. E, 80, 026705], it is shown that the diffracted intensity of the crystal can still be reconstructed even without knowledge of the orientation of the crystal in any sparse frame. Moreover, parallel computation implementations were designed to considerably improve the time and memory scaling of the algorithm. The results show that EMC-based SMX experiments should be feasible at SR sources.

Dragonfly: an implementation of the expand-maximize-compress algorithm for single-particle imaging.

Single-particle imaging (SPI) with X-ray free-electron lasers has the potential to change fundamentally how biomacromolecules are imaged. The structure would be derived from millions of diffraction patterns, each from a different copy of the macromolecule before it is torn apart by radiation damage. The challenges posed by the resultant data stream are staggering: millions of incomplete, noisy and un-oriented patterns have to be computationally assembled into a three-dimensional intensity map and then phase reconstructed. In this paper, the Dragonfly software package is described, based on a parallel implementation of the expand-maximize-compress reconstruction algorithm that is well suited for this task. Auxiliary modules to simulate SPI data streams are also included to assess the feasibility of proposed SPI experiments at the Linac Coherent Light Source, Stanford, California, USA.

Coherent diffraction of single Rice Dwarf virus particles using hard X-rays at the Linac Coherent Light Source.

Single particle diffractive imaging data from Rice Dwarf Virus (RDV) were recorded using the Coherent X-ray Imaging (CXI) instrument at the Linac Coherent Light Source (LCLS). RDV was chosen as it is a well-characterized model system, useful for proof-of-principle experiments, system optimization and algorithm development. RDV, an icosahedral virus of about 70 nm in diameter, was aerosolized and injected into the approximately 0.1 µm diameter focused hard X-ray beam at the CXI instrument of LCLS. Diffraction patterns from RDV with signal to 5.9 Ångström were recorded. The diffraction data are available through the Coherent X-ray Imaging Data Bank (CXIDB) as a resource for algorithm development, the contents of which are described here.

Protein crystal structure from non-oriented, single-axis sparse X-ray data.

X-ray free-electron lasers (XFELs) have inspired the development of serial femtosecond crystallography (SFX) as a method to solve the structure of proteins. SFX datasets are collected from a sequence of protein microcrystals injected across ultrashort X-ray pulses. The idea behind SFX is that diffraction from the intense, ultrashort X-ray pulses leaves the crystal before the crystal is obliterated by the effects of the X-ray pulse. The success of SFX at XFELs has catalyzed interest in analogous experiments at synchrotron-radiation (SR) sources, where data are collected from many small crystals and the ultrashort pulses are replaced by exposure times that are kept short enough to avoid significant crystal damage. The diffraction signal from each short exposure is so 'sparse' in recorded photons that the process of recording the crystal intensity is itself a reconstruction problem. Using the EMC algorithm, a successful reconstruction is demonstrated here in a sparsity regime where there are no Bragg peaks that conventionally would serve to determine the orientation of the crystal in each exposure. In this proof-of-principle experiment, a hen egg-white lysozyme (HEWL) crystal rotating about a single axis was illuminated by an X-ray beam from an X-ray generator to simulate the diffraction patterns of microcrystals from synchrotron radiation. Millions of these sparse frames, typically containing only ∼200 photons per frame, were recorded using a fast-framing detector. It is shown that reconstruction of three-dimensional diffraction intensity is possible using the EMC algorithm, even with these extremely sparse frames and without knowledge of the rotation angle. Further, the reconstructed intensity can be phased and refined to solve the protein structure using traditional crystallographic software. This suggests that synchrotron-based serial crystallography of micrometre-sized crystals can be practical with the aid of the EMC algorithm even in cases where the data are sparse.

Determination of crystallographic intensities from sparse data.

X-ray serial microcrystallography involves the collection and merging of frames of diffraction data from randomly oriented protein microcrystals. The number of diffracted X-rays in each frame is limited by radiation damage, and this number decreases with crystal size. The data in the frame are said to be sparse if too few X-rays are collected to determine the orientation of the microcrystal. It is commonly assumed that sparse crystal diffraction frames cannot be merged, thereby setting a lower limit to the size of microcrystals that may be merged with a given source fluence. The EMC algorithm [Loh & Elser (2009 ▶), Phys. Rev. E, 80, 026705] has previously been applied to reconstruct structures from sparse noncrystalline data of objects with unknown orientations [Philipp et al. (2012 ▶), Opt. Express, 20, 13129-13137; Ayyer et al. (2014 ▶), Opt. Express, 22, 2403-2413]. Here, it is shown that sparse data which cannot be oriented on a per-frame basis can be used effectively as crystallographic data. As a proof-of-principle, reconstruction of the three-dimensional diffraction intensity using sparse data frames from a 1.35 kDa molecule crystal is demonstrated. The results suggest that serial microcrystallography is, in principle, not limited by the fluence of the X-ray source, and collection of complete data sets should be feasible at, for instance, storage-ring X-ray sources.

Phonon contribution to the entropy of hard-sphere crystals.

Comparing the entropies of hard spheres in the limit of close packing, for different stacking sequences of the hexagonal layers, has been a challenge because the differences are so small. Here we present a method based on a "sticky-sphere" model by which the system interpolates between hard spheres in one limit and a harmonic crystal in the other. For the fcc and hcp stackings we have calculated the entropy difference in the harmonic (sticky) limit, as well as the differences in the free energy change upon removing the stickiness in the model. The former, or phonon entropy, accounts for most of the entropy difference. Our value for the net entropy difference, Δs = 0.001164(8)k(B) per sphere, is in excellent agreement with the best previous estimate by Mau and Huse [Phys. Rev. E 59, 4396 (1999)].

Real-Space x-ray tomographic reconstruction of randomly oriented objects with sparse data frames.

Schemes for X-ray imaging single protein molecules using new x-ray sources, like x-ray free electron lasers (XFELs), require processing many frames of data that are obtained by taking temporally short snapshots of identical molecules, each with a random and unknown orientation. Due to the small size of the molecules and short exposure times, average signal levels of much less than 1 photon/pixel/frame are expected, much too low to be processed using standard methods. One approach to process the data is to use statistical methods developed in the EMC algorithm (Loh & Elser, Phys. Rev. E, 2009) which processes the data set as a whole. In this paper we apply this method to a real-space tomographic reconstruction using sparse frames of data (below 10(-2) photons/pixel/frame) obtained by performing x-ray transmission measurements of a low-contrast, randomly-oriented object. This extends the work by Philipp et al. (Optics Express, 2012) to three dimensions and is one step closer to the single molecule reconstruction problem.

Breaking the Crowther limit: combining depth-sectioning and tilt tomography for high-resolution, wide-field 3D reconstructions.

To date, high-resolution (<1 nm) imaging of extended objects in three-dimensions (3D) has not been possible. A restriction known as the Crowther criterion forces a tradeoff between object size and resolution for 3D reconstructions by tomography. Further, the sub-Angstrom resolution of aberration-corrected electron microscopes is accompanied by a greatly diminished depth of field, causing regions of larger specimens (>6 nm) to appear blurred or missing. Here we demonstrate a three-dimensional imaging method that overcomes both these limits by combining through-focal depth sectioning and traditional tilt-series tomography to reconstruct extended objects, with high-resolution, in all three dimensions. The large convergence angle in aberration corrected instruments now becomes a benefit and not a hindrance to higher quality reconstructions. A through-focal reconstruction over a 390 nm 3D carbon support containing over 100 dealloyed and nanoporous PtCu catalyst particles revealed with sub-nanometer detail the extensive and connected interior pore structure that is created by the dealloying instability.

Direct phasing of nanocrystal diffraction.

Recent experiments at free-electron laser X-ray sources have been able to resolve the intensity distributions about Bragg peaks in nanocrystals of large biomolecules. Information derived from small shifts in the peak positions augment the Bragg samples of the particle intensity with samples of its gradients. Working on the assumption that the nanocrystal is entirely generated by lattice translations of a particle, an algorithm is developed that reconstructs the particle from intensities and intensity gradients. Unlike traditional direct phasing methods that require very high resolution data in order to exploit sparsity of the electron density, this method imposes no constraints on the contrast other than positivity and works well at low resolution. Successful reconstructions are demonstrated with simulated P1 lysozyme nanocrystal data down to a signal-to-noise ratio of 2 in the intensity gradients.

Hierarchical porous polymer scaffolds from block copolymers.

Hierarchical porous polymer materials are of increasing importance because of their potential application in catalysis, separation technology, or bioengineering. Examples for their synthesis exist, but there is a need for a facile yet versatile conceptual approach to such hierarchical scaffolds and quantitative characterization of their nonperiodic pore systems. Here, we introduce a synthesis method combining well-established concepts of macroscale spinodal decomposition and nanoscale block copolymer self-assembly with porosity formation on both length scales via rinsing with protic solvents. We used scanning electron microscopy, small-angle x-ray scattering, transmission electron tomography, and nanoscale x-ray computed tomography for quantitative pore-structure characterization. The method was demonstrated for AB- and ABC-type block copolymers, and resulting materials were used as scaffolds for calcite crystal growth.

Solving structure with sparse, randomly-oriented x-ray data.

Single-particle imaging experiments of biomolecules at x-ray free-electron lasers (XFELs) require processing hundreds of thousands of images that contain very few x-rays. Each low-fluence image of the diffraction pattern is produced by a single, randomly oriented particle, such as a protein. We demonstrate the feasibility of recovering structural information at these extremes using low-fluence images of a randomly oriented 2D x-ray mask. Successful reconstruction is obtained with images averaging only 2.5 photons per frame, where it seems doubtful there could be information about the state of rotation, let alone the image contrast. This is accomplished with an expectation maximization algorithm that processes the low-fluence data in aggregate, and without any prior knowledge of the object or its orientation. The versatility of the method promises, more generally, to redefine what measurement scenarios can provide useful signal.