Homometry and Direct-Sum Decompositions of Lattice-Convex Sets

Gennadiy Averkov, Barbara LangfeldDiscret. Comput. Geom 2016 · OpenReview

TL;DR

This paper investigates "homometric" sets, which are distinct sets that produce the same "covariogram" (a measure of how much a set overlaps with its translated copies). The authors focus on "lattice-convex" sets and provide a framework for constructing and classifying pairs of these sets that are homometric but not trivially so. They achieve this by establishing conditions for lattice-convexity within direct-sum decompositions and explicitly characterizing these pairs in 2D, while also constructing examples for higher dimensions.

What Problem Does This Paper Address?

The core problem this paper addresses is understanding the structure of "homometric" sets, particularly within the context of "lattice-convex" sets. Homometric sets are sets that share the same covariogram, a function that counts the number of points in the intersection of a set $K$ and its translation $K+u$ for all vectors $u$. If two homometric sets are not identical up to translation and point reflection, they are called "nontrivially homometric."

The challenge lies in characterizing these nontrivially homometric sets, especially when they possess a specific type of convexity related to lattices, known as "lattice-convexity." This means the set is the intersection of a lattice (a discrete set of points forming a regular grid) and a convex shape. While some examples of such sets were known, particularly in 2D, a systematic understanding and construction for arbitrary dimensions were lacking. The paper aims to fill this gap by providing necessary and sufficient conditions for lattice-convexity in direct-sum decompositions of sets, which are a common way to generate homometric pairs.

Methods

The paper employs a combination of geometric and algebraic techniques. A key method is the analysis of direct-sum decompositions of sets, specifically of the form $S \oplus T$ and $S \oplus (-T)$. The authors leverage the property that if the sum $X+Y$ is "direct" (meaning each element in the sum has a unique representation as an element from $X$ and an element from $Y$), then $S \oplus T$ and $S \oplus (-T)$ are homometric.

A central contribution is the development of a necessary and sufficient condition for the M-convexity of $S \oplus T$, where $M$ is a lattice. This condition is formulated in terms of the lattice width of the "tile" $T$ with respect to the lattice $L$ (where $M = L \oplus T$). Specifically, it relates to the set $W(T, L)$, which comprises directions where $T$ is "thin" relative to $L$.

For explicit constructions and classifications, the authors utilize concepts from convex geometry, lattice theory, and computational algebra. They employ tools like support functions, Minkowski sums, and dual lattices. For the 2D case, a detailed classification is achieved by analyzing specific geometric configurations of lattices and tiles, often involving computer enumeration using the Magma algebra system.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and classifications of abstract sets rather than empirical data analysis.

Key Insights and Ideas

  • Direct sums as a generator of homometry: The paper highlights that direct-sum decompositions of the form $S \oplus T$ and $S \oplus (-T)$ provide a fundamental mechanism for generating homometric sets. This offers a structured way to explore the problem.
  • The role of $W(T, L)$: The set $W(T, L)$, representing directions where a tile $T$ is "thin" relative to a lattice $L$, is crucial. Its properties directly influence the lattice-convexity of direct sums and, consequently, the existence of nontrivially homometric pairs.
  • Finiteness of "shapes" for higher dimensions: For $d \ge 3$, the paper shows that the possible "shapes" of $W(T, L)$ are essentially finite, suggesting that nontrivially homometric lattice-convex sets, under the studied structural assumptions, are not infinitely varied in their fundamental geometric properties.
  • Explicit classification in 2D: The paper provides a complete characterization of nontrivially homometric lattice-convex pairs in dimension two, under the assumption of direct-sum decomposition. This demonstrates that known examples in 2D cover all such cases within this structural framework.
  • Bridging theory and computation: The work effectively combines theoretical results with computational methods (Magma) to verify findings and perform explicit searches, particularly for the 2D classification.

Key Results

  • Theorem 2.1: Provides a necessary and sufficient condition for the M-convexity of $S \oplus T$ based on the lattice-convexity of $S$ and the properties of $W(T, L)$.
  • Corollary 2.2: Offers a sufficient condition for constructing nontrivially homometric M-convex pairs $S \oplus T$ and $S \oplus (-T)$ when $W(T, L)$ contains specific linearly independent vectors.
  • Theorem 2.3: Establishes that for a fixed lattice $L$ and a finite $d$-dimensional tile $T$, the set $W(T, L)$ has a finite number of possible "shapes" under certain conditions, limiting the complexity of homometric pairs.
  • Theorem 2.4: Provides a complete classification of nontrivially homometric lattice-convex pairs of the form $S \oplus T$ and $S \oplus (-T)$ in dimension two, showing that known examples are exhaustive within this structural class.
  • Construction of examples for $d \ge 3$: The paper presents methods to construct nontrivially homometric pairs of lattice-convex sets for dimensions $d \ge 3$, addressing a gap in prior research.

Limitations and Future Work

  • Structural assumptions: The study of nontrivially homometric pairs is largely confined to those that can be represented as direct sums $S \oplus T$ and $S \oplus (-T)$, where $T$ is a lattice-convex tile and $S$ is a subset of a sublattice $L$ such that $M = L \oplus T$. The paper acknowledges that this is a strong structural assumption and does not cover all possible lattice-convex sets.
  • Explicit enumeration for $d \ge 3$: While examples are constructed for $d \ge 3$, a complete classification analogous to the 2D case is not provided, likely due to the increased complexity.
  • Problem 2.5 (Geometrically inconstructible pairs): The paper poses the question of whether geometrically inconstructible homometric pairs of lattice-convex sets exist, suggesting this as an open area.
  • Problem 2.6 (Improving Theorem 2.1): The authors ask if Theorem 2.1 can be refined for a more precise description of sets $S \subseteq L$ that ensure $S \oplus T$ is M-convex, and if the theorem can be extended to sets $S$ of any dimension.
  • Problem 2.7 (Enumeration of $W(T, L)$ for $d=2,3$): An explicit enumeration of all possible sets $W(T, L)$ for fixed dimensions $d=2$ and $d=3$ is posed as a future research direction.

Summary updated

Abstract

Two sets in \({\mathbb {R}}^d\) are called homometric if they have the same covariogram, where the covariogram of a finite subset K of \({\mathbb {R}}^d\) is the function associating to each \(u \in {\mathbb {R}}^d\) the cardinality of \(K \cap (K+u)\). Understanding the structure of homometric sets is important for a number of areas of mathematics and applications. If two sets are homometric but do not coincide up to translations and point reflections, we call them nontrivially homometric. We study nontrivially homometric pairs of lattice-convex sets, where a set K is called lattice-convex with respect to a lattice \({\mathbb {M}}\subseteq {\mathbb {R}}^d\) if K is the intersection of \({\mathbb {M}}\) and a convex subset of \({\mathbb {R}}^d\). This line of research was initiated in 2005 by Daurat, Gérard and Nivat and, independently, by Gardner, Gronchi and Zong. All pairs of nontrivially homometric lattice-convex sets that have been known so far can essentially be written as direct sums \(S \oplus T\) and \(S \oplus (-T)\), where T is lattice-convex, the underlying lattice \({\mathbb {M}}\) is the direct sum of T and some sublattice \({\mathbb {L}}\), and S is a subset of \({\mathbb {L}}\). We study pairs of nontrivially homometric lattice-convex sets assuming this particular form and establish a necessary and a sufficient condition for the lattice-convexity of \(S \oplus T\). This allows us to explicitly describe all nontrivially homometric pairs in dimension two, under the above assumption, and to construct examples of nontrivially homometric pairs of lattice-convex sets for each \(d \ge 3\).
BibTeX
@inproceedings{averkov2016homometry,
  author = {Gennadiy Averkov and Barbara Langfeld},
  title = {{Homometry and Direct-Sum Decompositions of Lattice-Convex Sets}},
  booktitle = {Discret. Comput. Geom},
  year = {2016},
  url = {https://openreview.net/forum?id=e4b6BZ2CuM},
}

Loading related content...

Figure