Enumeration of Complex Golay Pairs via Programmatic SAT

Curtis Bright, Ilias S. Kotsireas, Albert Heinle, Vijay Ganesh

This paper, presented at ISSAC ’18, describes a powerful hybrid computational approach to solve a long-standing problem in combinatorics: the complete enumeration of complex Golay pairs. By combining the "brute force" search capabilities of SAT solvers with the mathematical "intelligence" of Computer Algebra Systems (CAS), the authors verified the existence (or lack thereof) of these sequences up to length 25.

TL;DR

The authors used a "SAT+CAS" hybrid approach to perform the first complete enumeration of complex Golay pairs up to length 25. Their work independently verifies that these pairs do not exist for lengths 23 and 25, resolving a mathematical conjecture using roughly 24 hours of computation on a 25-core cluster.

What Problem Does This Paper Address?

Golay pairs are pairs of sequences consisting of symbols (like $\pm 1$) where the sum of their "out-of-sync" correlations is always zero. Essentially, they are sequences with perfect mathematical properties for minimizing interference. Because of this, they are used extensively in radar pulse compression, Wi-Fi networks, and medical ultrasounds.

While standard Golay pairs use a binary alphabet, complex Golay pairs use a four-phase alphabet: $\{1, -1, i, -i\}$. The challenge is that as the length of the sequence ($n$) increases, the search space grows exponentially ($4^{2n}$). For a long time, mathematicians conjectured that complex Golay pairs of length 23 did not exist, but proving this required an exhaustive search that was computationally daunting.

Methods

The authors employ a two-stage SAT+CAS paradigm, which bridges the gap between symbolic computation and logic-based search.

  1. Stage 1: CAS-based Filtering: Instead of searching for pairs $(A, B)$ simultaneously, they first find all possible candidates for the first sequence $A$. They use a Computer Algebra System (Maple) and the FFTW library to apply heavy mathematical filters. For example, they use the "sum-of-squares" decomposition and the "Hall polynomial" property to discard sequences that could never mathematically be part of a Golay pair. This reduces the search space by over 99.99%.
  2. Stage 2: Programmatic SAT Solving: For each candidate $A$ that survives Stage 1, they use a SAT solver (MapleSAT) to find a matching sequence $B$. Crucially, they use a programmatic SAT solver. Unlike a standard solver that only understands Boolean logic, a programmatic solver can call external C++ code during its search. This code checks the specific autocorrelation properties of the sequences and provides "conflict clauses" back to the solver, allowing it to prune the search tree much faster than a general-purpose solver could.

Datasets

As a pure mathematics and search-based paper, it does not use traditional training datasets. Instead, it uses:

  • Fiedler’s 2013 Table: Used as a benchmark for verification. The authors' results perfectly matched Fiedler's counts for total pairs and sequences.
  • New Enumerations: The paper provides the first explicit publication of complex Golay pairs and their counts (up to equivalence) for lengths 20 through 25. These are now publicly available online.

Key Insights and Ideas

  • The Power of Hybridization: The "aha moment" is that SAT solvers are excellent at searching, but "dumb" at math, while CAS are "smart" at math but poor at exhaustive searching. Combining them allows the CAS to define the boundaries and the SAT solver to efficiently navigate the interior.
  • FFT for Filtering: The authors realized that the Discrete Fourier Transform (DFT) is the fastest way to evaluate the filtering conditions (specifically the Hall polynomial bounds). Using the FFTW library significantly sped up the preprocessing stage.
  • Symmetry Breaking: By applying "equivalence operations" (like reversing or scaling a sequence), the authors could normalize the search. This ensured they didn't waste time finding the same pair multiple times in different orientations.

Key Results

  • Verification: Confirmed that complex Golay pairs do not exist for lengths $n=23$ and $n=25$, but do exist for $n=24$.
  • Performance: The entire enumeration up to length 25 took about one day on a cluster with 25 cores. For comparison, length 25 alone required about 700 CPU hours across the various stages.
  • New Data: They provided the first counts of "inequivalent" complex Golay pairs for higher lengths (e.g., 1,056 inequivalent pairs at length 24).

Limitations and Future Work

  • Scaling: While efficient, the method is still subject to exponential growth. The authors estimate that moving from length 25 to length 26 would take an additional week of computation.
  • Algebraic Structure: The authors note they haven't yet fully exploited certain algebraic properties, such as the irreducibility of the Hall polynomial over finite fields, which could provide even stronger filters in the future.
  • Symbolic Optimization: There is potential to symbolically determine the best points to evaluate the filtering conditions, rather than testing a large number of roots of unity, which could further reduce the preprocessing time.

Summary updated

Abstract

We provide a complete enumeration of all complex Golay pairs of length up to 25, verifying that complex Golay pairs do not exist in lengths 23 and 25 but do exist in length 24. This independently verifies work done by F. Fiedler in 2013 that confirms the 2002 conjecture of Craigen, Holzmann, and Kharaghani that complex Golay pairs of length 23 don't exist. Our enumeration method relies on the recently proposed SAT+CAS paradigm of combining computer algebra systems with SAT solvers to take advantage of the advances made in the fields of symbolic computation and satisfiability checking. The enumeration proceeds in two stages: First, we use a fine-tuned computer program and functionality from computer algebra systems to construct a list containing all sequences which could appear as the first sequence in a complex Golay pair (up to equivalence). Second, we use a programmatic SAT solver to construct all sequences (if any) that pair off with the sequences constructed in the first stage to form a complex Golay pair.
BibTeX
@inproceedings{bright2018enumeration,
  author = {Curtis Bright and Ilias S. Kotsireas and Albert Heinle and Vijay Ganesh},
  title = {{Enumeration of Complex Golay Pairs via Programmatic SAT}},
  booktitle = {ISSAC},
  year = {2018},
  url = {https://openreview.net/forum?id=Uorxhpz8g2js},
}
Figure