When designing sequences for digital communications or DNA nanotechnology, researchers frequently encounter a striking mathematical phenomenon: problems that are elegantly solvable for odd lengths or parameters become notoriously difficult when those parameters are even.
This "even-length gap" stems from a fundamental shift in symmetry. In an odd-length system, structural elements cannot easily map directly onto their own exact inverses. In an even-length system, however, elements can become their own exact self-inverses—such as a DNA strand being its own reverse complement, or a binary sequence perfectly balancing against its own reflection. This self-symmetry disrupts the clean mathematical frameworks that govern optimal sequence construction, leaving open questions at the boundary of graph theory and abstract algebra.
Graph Topology and the Problem of Even $q$
The impact of this parity shift is clearly visible in the design of long, non-self-hybridizing DNA sequences for nano-architectures. To prevent a sequence from accidentally folding or binding to itself, researchers ensure that no sub-segment of length $q$ (a $q$-gram) is the reverse complement of another sub-segment in the sequence.
To find the longest possible sequence satisfying this constraint, Marianna D'Addario et al. utilized a specialized graph structure called a De Bruijn Quotient Graph (DBQG) in their paper, Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs. In this graph, edges represent $q$-grams, and vertices represent the overlaps between them, collapsing Watson-Crick complementary pairs into single entities.
Odd q: [ A T G ] --> No central nucleotide can pair with itself.
Graph remains perfectly balanced (Eulerian).
Even q: [ A T G C ] --> Self-complementary! Must be deleted.
Graph balance is destroyed (Non-Eulerian).
When the window size $q$ is odd, the problem is trivial. A DNA sequence of odd length can never be its own reverse complement because the central nucleotide would have to pair with itself (e.g., 'A' pairing with 'A'), which is biologically impossible. Because these self-complementary states cannot exist, the underlying DBQG maintains a perfectly balanced degree distribution. The authors demonstrate that for odd $q$, the graph is naturally Eulerian, meaning a single continuous path can traverse every single edge exactly once. This guarantees an optimal, maximum-length sequence via a simple linear-time algorithm.
When $q$ is even, this elegant topology shatters. Even-length sequences like ATGC can be their own reverse complements. Because these self-complementary sequences cause self-hybridization, they must be strictly forbidden, meaning their corresponding edges must be pruned from the graph.
The authors show that this pruning process transforms the challenge into an "Eulerization by deletion" task. Removing these specific edges destroys the Eulerian property of the graph. Finding the minimum number of additional edge deletions required to restore a valid Eulerian path—and thus find the longest possible $q$-unique sequence—remains an open and highly complex optimization problem.
Algebraic Rigidity and Exotic Sequences
A parallel challenge appears in coding theory when constructing Golay complementary sequences and array pairs, which are used to optimize signal transmission in digital communications. Here, the goal is to find pairs of sequences whose auto-correlation vectors perfectly cancel each other out, eliminating signal noise.
For decades, researchers have relied on standard recursive algebraic constructions—specifically using Generalized Boolean functions—to generate these pairs. However, as Zhi Gu et al. point out in New Construction of Optimal Type-II Binary Z-Complementary Pairs, existing optimal constructions for even-length sequences are highly constrained, only working for very specific base lengths and their multiples. Whether optimal pairs exist universally across all even lengths, or if there are fundamental mathematical barriers preventing them, remains unknown.
To resolve this, researchers have attempted to map the entire boundary of the sequence space to see if "exotic" or non-standard sequence configurations can exist outside of known algebraic formulas.
Multi-Dimensional Space One-Dimensional Space
┌───────────────────────────┐ ┌───────────────────────────┐
│ Power-of-two arrays │ Collapse 1D │ Even-length sequences │
│ Strictly "Standard" │ ─────────────> │ Do exotic non-standard │
│ (Proven by Xue et al.) │ │ structures exist? (Open) │
└───────────────────────────┘ └───────────────────────────┘
In The q-ary Golay arrays of size 2˟ 2˟ ... ˟ 2 are standard, Erzhong Xue et al. successfully proved that all $q$-ary Golay complementary array pairs of power-of-two dimensions are "standard," meaning they are strictly confined to these known algebraic boundaries. The authors extended this structural characterization in Boolean functions of binary Type-II and Type-III/II complementary array pairs, proving that the algebraic normal forms of these multi-dimensional arrays must follow rigid, predictable mathematical expressions.
Yet, despite completely characterizing the multi-dimensional space, a stubborn theoretical gap remains when collapsing these structures down to a single dimension. The authors note that a formal proof for the non-existence of non-standard, one-dimensional binary Golay sequences of even (power-of-two) lengths remains an unsolved challenge.
Because even lengths allow for complex internal symmetries, numerical searches have ruled out exotic sequences at small lengths, but the mathematical bridge required to definitively rule them out at all even lengths does not yet exist.
Bridging the Parity Divide
Whether analyzing the structural breakdown of a De Bruijn graph or mapping the algebraic boundaries of Generalized Boolean functions, the core challenge remains identical: even parameters introduce a degree of freedom for self-inverse configurations that disrupts standard mathematical order.
In graph-based sequence design, this forces researchers to move from elegant Eulerian tours to destructive "Eulerization by deletion" problems. In algebraic coding theory, it manifests as an inability to definitively rule out exotic, non-standard sequence pairs. Resolving the even-length gap requires finding new mathematical frameworks that can either absorb or exploit these self-inverse symmetries, transforming them from structural disruptions into predictable design patterns.
Key Foundational Work
Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs (2012) — contributed 11 concept elements to this direction.
New Construction of Optimal Type-II Binary Z-Complementary Pairs (2020) — contributed 1 concept elements to this direction.