Deciding Orthogonality in Construction-A Lattices

Karthekeyan Chandrasekaran, Venkata Gandikota, Elena GrigorescuarXiv 2015 · arXiv

TL;DR

This paper provides the first efficient, polynomial-time algorithms to solve the "orthogonality decision problem"—determining whether a lattice has an orthogonal basis—for the well-known family of Construction-A lattices derived from binary and ternary error-correcting codes. By proving that these lattices must structurally decompose into direct products of low-dimensional components, the authors turn a notoriously hard open problem into one that can be solved in $O(n^6)$ time for binary and $O(n^8)$ time for ternary settings.

What Problem Does This Paper Address?

Lattices—discrete grids of points in multi-dimensional space—form the backbone of modern integer programming and post-quantum cryptography. A central, computationally hard problem in these fields is the Closest Vector Problem (CVP): given an arbitrary point in space, find the closest lattice point.

If a lattice possesses an orthogonal basis (meaning all the basis vectors are perpendicular to one another), CVP becomes trivial to solve; you simply round the coordinates of the target point to the nearest integer. However, if you are handed an arbitrary, messy basis for a lattice, how do you know if an orthogonal basis even exists?

This is the orthogonality decision problem. For general lattices, its computational complexity is a mystery: it is neither known to be NP-complete nor known to be solvable in polynomial time (P). This paper tackles this challenge for a specific, widely studied family called Construction-A lattices, which bridge coding theory and lattice theory by combining error-correcting codes with integer grids ($C + q\mathbb{Z}^n$).

Methods

The authors bridge lattice theory and combinatorics by leveraging the properties of weighing matrices—orthogonal matrices containing only $\{0, 1, -1\}$ entries.

Their approach relies on proving a structural decomposition theorem. They demonstrate that if a Construction-A lattice derived from a binary ($q=2$) or ternary ($q=3$) code is orthogonal, it must break down into a direct product of smaller, independent, low-dimensional orthogonal lattices. Crucially, they prove these irreducible components have a strictly bounded, constant dimension:

  • For binary codes, the components are at most 2-dimensional.
  • For ternary codes, the components are at most 4-dimensional.

Using this structural insight, the authors design recursive polynomial-time algorithms. The algorithms systematically check whether the underlying error-correcting code can be peeled apart step-by-step into these small, predefined component codes. If the decomposition succeeds, the algorithm outputs the orthogonal basis; if it fails at any stage, it guarantees that no such basis exists.

Datasets

Not applicable. This is a purely theoretical paper focused on mathematical proofs and algorithmic complexity analysis. No empirical datasets or benchmarks were used.

Key Insights and Ideas

  • The Direct Product Necessity: A straightforward way to build a large orthogonal lattice is to take the direct product of smaller ones. The authors' key "aha moment" was proving that for binary and ternary Construction-A lattices, this is actually the only way an orthogonal basis can manifest.
  • Code-Lattice Equivalence: The paper elegantly demonstrates that the geometric property of lattice orthogonality is completely mirrored by the structural decomposition of the underlying algebraic code.
  • Dimension Bounding via Weighing Matrices: By mapping the basis vectors to weighing matrices of weight 2 and 3, the authors could definitively bound the search space. This prevents the recursive algorithm from getting stuck exploring arbitrarily large dimensional blocks.

Key Results

  • Binary Construction-A Lattices ($q=2$): The paper proves these are orthogonal if and only if they decompose into 1D grids ($\mathbb{Z}$ or $2\mathbb{Z}$) or a specific 2D orthogonal lattice. The decision and basis-finding algorithm runs efficiently in $O(n^6)$ time.
  • Ternary Construction-A Lattices ($q=3$): These are orthogonal if and only if they decompose into 1D grids ($\mathbb{Z}$ or $3\mathbb{Z}$) or a specific 4D lattice block. The corresponding algorithm runs in $O(n^8)$ time.

Limitations and Future Work

The primary limitation is that the current techniques are strictly bound to $q=2$ and $q=3$. Extending these results to larger finite fields ($q > 3$) hits a major roadblock in combinatorial mathematics: a complete characterization of weighing matrices of weight $q$ is a famous open problem.

Furthermore, even for $q=4$ (where some weighing matrix properties are known), the components in the direct product decomposition do not necessarily have a constant dimension. This means the recursive search strategy introduced here would face an exponential blow-up in runtime, requiring entirely new algorithmic strategies to resolve.

Summary updated

Abstract

Lattices are discrete mathematical objects with widespread applications to integer programs as well as modern cryptography. A fundamental problem in both domains is the Closest Vector Problem (popularly known as CVP). It is well-known that CVP can be easily solved in lattices that have an orthogonal basis \emph{if} the orthogonal basis is specified. This motivates the orthogonality decision problem: verify whether a given lattice has an orthogonal basis. Surprisingly, the orthogonality decision problem is not known to be either NP-complete or in P. In this paper, we focus on the orthogonality decision problem for a well-known family of lattices, namely Construction-A lattices. These are lattices of the form $C+q\mathbb{Z}^n$, where $C$ is an error-correcting $q$-ary code, and are studied in communication settings. We provide a complete characterization of lattices obtained from binary and ternary codes using Construction-A that have an orthogonal basis. We use this characterization to give an efficient algorithm to solve the orthogonality decision problem. Our algorithm also finds an orthogonal basis if one exists for this family of lattices. We believe that these results could provide a better understanding of the complexity of the orthogonality decision problem for general lattices.
BibTeX
@misc{chandrasekaran2015deciding,
  author = {Karthekeyan Chandrasekaran and Venkata Gandikota and Elena Grigorescu},
  title = {{Deciding Orthogonality in Construction-A Lattices}},
  year = {2015},
  eprint = {1512.02734},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1512.02734},
}
Figure