Average minimum distances of periodic point sets – foundational invariants for mapping periodic crystals

Daniel E. Widdowson, Marco M. Mosca, Angeles Pulido, Andrew I. Cooper, Vitaliy KurlinMatch 2021 · DOI

TL;DR

This paper introduces a new set of continuous "Average Minimum Distances" (AMD) that act as robust invariants for classifying periodic point sets, like atomic structures in crystals. These AMDs are computationally efficient and can continuously map the vast space of all possible crystal structures, akin to Mendeleev's periodic table for elements.

What Problem Does This Paper Address?

Crystalline materials are fundamental to many scientific and engineering fields. At their core, these materials can be represented as periodic point sets, where atoms are points arranged in a repeating pattern. A key challenge is to classify these structures based on their fundamental geometric equivalence – isometry, meaning they are identical up to rigid motion (translation, rotation, reflection).

Traditional methods for comparing crystal structures relied on discontinuous measures like symmetry groups or manually chosen thresholds for atomic distances. These methods are brittle; even slight perturbations, like thermal vibrations, can drastically change the classification, making it difficult to study continuous transitions between crystal phases or to find truly similar structures in large databases. The paper aims to bridge this gap by developing a set of continuous and efficient invariants that can robustly classify these periodic point sets.

Methods

The paper introduces "Average Minimum Distances" (AMD) as a sequence of continuous isometry invariants. For a given periodic point set and a chosen number of neighbors k, AMD$_k$ is calculated by averaging the distances from each point in a representative unit cell to its k-th nearest neighbor in the entire infinite structure.

The authors provide theoretical proofs for the isometry invariance of AMD$_k$ and demonstrate its continuity under small perturbations. A key contribution is a near-linear time algorithm for computing AMD$_k$, making it practical for large datasets. They also analyze the asymptotic behavior of AMD$_k$ as k increases, showing it converges to a "point packing coefficient" that characterizes the density of the structure.

Datasets

The primary dataset used for evaluation is the Cambridge Structural Database (CSD), the world's largest collection of known crystal structures, containing over 1.1 million entries. The authors applied their AMD algorithm to a significant portion of this database (228,994 molecular organic real crystal structures) to demonstrate its effectiveness.

Key Insights and Ideas

  • Continuous Classification: The core idea is that geometric properties of crystals should be continuously measurable, not based on discrete thresholds. AMDs provide this continuity, allowing for smooth transitions and comparisons.
  • Isometry Invariants: AMDs are proven to be invariant under isometries, meaning that if two crystal structures are geometrically identical (just rotated or translated), their AMD values will be the same. This is crucial for robust classification.
  • Computational Efficiency: The development of a near-linear time algorithm for AMD computation is a significant practical breakthrough, enabling the analysis of massive crystallographic datasets.
  • "Mendeleev's Table" for Crystals: The continuous nature and computational efficiency of AMDs open the door to parameterizing the vast space of all possible periodic crystals, creating a high-dimensional "map" analogous to the periodic table of elements.
  • Detecting Hidden Duplicates: The AMD algorithm successfully identified hundreds of pairs of crystals in the CSD that were considered duplicates based on their atomic positions (low RMSD) but had been missed by traditional methods.

Key Results

  • The proposed AMD algorithm successfully identified all different crystals in the Cambridge Structural Database within a few hours on a modest desktop.
  • AMD invariants were used to predict the lattice energy of molecular crystals with high accuracy.
  • The algorithm identified 405 pairs of crystals in the CSD with identical AMD(100) values but low RMSD, suggesting they were duplicates missed by previous methods.
  • Five pairs of crystals were found to have identical AMD invariants but differed only by the chemical type of a single atom, highlighting the sensitivity of AMDs to subtle structural changes.
  • The near-linear time complexity of the AMD algorithm (O((5v)ⁿVnkm log²(km))) makes it highly scalable.

Limitations and Future Work

  • Potential Incompleteness: While AMDs are powerful, the authors acknowledge that they do not know of any non-isometric periodic sets that have equal AMD$_k$ for all k > 1. Theorem 16 hints at completeness for generic finite sets, but this remains an open question for periodic sets.
  • Parameter Choice: The choice of k (number of neighbors) in AMD$_k$ influences the level of detail captured. While the asymptotic behavior is well-understood, selecting an optimal k for specific applications might require further investigation.
  • Future Work: The authors suggest extending their work to explore the continuous parameterization of crystal spaces, further investigating the completeness of AMDs, and applying these methods to other areas of materials science and data analysis. The development of a continuous map from lattices to reduced bases is also highlighted as an important theoretical direction.

Summary updated

Abstract

The fundamental model of any solid crystalline material (crystal) at the atomic scale is a periodic point set. The strongest natural equivalence of crystals is rigid motion or isometry that preserves all inter-atomic distances. Past comparisons of periodic structures often used manual thresholds, symmetry groups and reduced cells, which are discontinuous under perturbations or thermal vibrations of atoms. This work defines the infinite sequence of continuous isometry invariants (Average Minimum Distances) to progressively capture distances between neighbors. The asymptotic behaviour of the new invariants is theoretically proved in all dimensions for a wide class of sets including non-periodic. The proposed near linear time algorithm identified all different crystals in the world's largest Cambridge Structural Database within a few hours on a modest desktop. The ultra fast speed and proved continuity provide rigorous foundations to continuously parameterise the space of all periodic crystals as a high-dimensional extension of Mendeleev's table of elements.
BibTeX
@inproceedings{widdowson2021average,
  author = {Daniel E. Widdowson and Marco M. Mosca and Angeles Pulido and Andrew I. Cooper and Vitaliy Kurlin},
  title = {{Average minimum distances of periodic point sets – foundational invariants for mapping periodic crystals}},
  booktitle = {Match},
  year = {2021},
  doi = {10.46793/match.87-3.529w},
}
Figure