A Parity Theorem for Reverse-Complement-Invariant Minimum Decycling Sets in q-ary de Bruijn Graphs

Introduction

Minimum decycling sets in directed de Bruijn graphs are classical combinatorial objects and underlie several finite-window sequence-sampling constructions. Their ordinary minimum is governed by rotation cycles and unavoidable sets [5, 1]. More recent work made the move structure of minimum decycling sets explicit [3]. Reverse-complement symmetry imposes a different constraint: whenever a word is chosen, its reverse complement must also be chosen. This is the natural strand symmetry for DNA and was posed directly in the k-nonical setting [4].

In Section 5.1 of [4], the authors identify the lack of known algorithms for symmetric MDSs; § 6 also notes the unknown symmetric minimum size. We answer the following existence part of that problem: for which word lengths can literal reverse-complement symmetry attain the ordinary minimum? The answer below classifies every fixed-point-free complemented alphabet. It does not determine the exact odd-order constrained minimum or solve the additional path-length optimization in that work.

In particular, Theorem 1.1 applies to binary words and to DNA words under $A \leftrightarrow T$ and $C \leftrightarrow G$. The case $k = 1$ is deliberately outside the theorem: every loop must be deleted, so the unique ordinary minimum is the whole alphabet and is invariant even though $k$ is odd.

The two directions use different mechanisms. At odd order, a primitive pure-rotation cycle has two reverse-complement-fixed lower endpoints. One deletion from that cycle cannot destroy both endpoint-to-endpoint directions, and reverse complement supplies the opposing residual path. Counting this obstruction over disjoint alphabet pairs gives at least $q$ additional deletions. At even order, we assign distinct nonzero real weights $s(a)$ satisfying $s(\overline{a}) = -s(a)$. A weighted cyclotomic version of the classical selector then has an exact reverse-complement defect equal to the gradient of an open half-plane indicator. Legal full-alphabet source firings remove that defect monotonically.

The proof yields two complementary constructions. The first is a finite descent and exposes the move-theoretic mechanism; every allowed monotone scheduler uses an explicitly determined number of firings. The second cuts the same self-dual residual poset at a spectral midpoint and gives a direct word-membership rule. When the weight table is integer-valued, exact real-algebraic sign determination makes the latter a polynomial-bit algorithm. Neither statement supplies a bound on the longest residual path or a biological performance guarantee.

Relation to prior terminology. The phrase “symmetric decycling set” has also been used for the ordinary Mykkeltveit construction based on opposite geometric half-planes [6]. We use the unambiguous phrase reverse-complement-invariant throughout.

Evidence discipline. The all-order proof occupies Sections 3–8. Section 9 records an independent exact implementation of the binary specialization only as a sign, convention, and mutation check. No finite census is a premise of Theorem 1.1.

Organization. Section 2 fixes the graph, rotation, and gradient conventions. Section 3 proves the odd obstruction. Sections 4–6 construct and symmetrize the weighted seed. Section 7 gives the direct spectral selector, and Section 8 assembles the parity theorem and its DNA corollary. The appendices collect convention maps, technical details, and the finite binary assurance table.

Claim boundary. The mathematical theorem is alphabet-general under a fixed-point-free complement. We do not claim an exact odd-order symmetry premium, an optimal firing path, a quantitative window guarantee, biological performance, or blanket novelty or priority over unexamined sources.

Normalization and prior work

Words, graphs, and reverse complement

Let $\mathcal{A}$ be a finite nonempty alphabet of cardinality $q$, equipped with a fixed-point-free involution $a \mapsto\bar{a}$. Thus $q$ is even. The binary specialization has $\bar{0}=1$, and the DNA specialization has $\bar{\mathrm{A}}=\mathrm{T}$, $\bar{\mathrm{C}}=\mathrm{G}$. For $w=w_0\cdots w_{k-1}$ define

The directed vertex de Bruijn graph $B(q,k)$ has vertex set $\mathcal{A}^k$ and an arc $u\to v$ exactly when $u_1\cdots u_{k-1}=v_0\cdots v_{k-2}$. Loops are retained. Reverse complement is a directed anti-automorphism:

A set $M\subseteq\mathcal{A}^k$ is a decycling set when $B(q,k)\setminus M$ is a directed acyclic graph (DAG), and is an ordinary minimum decycling set when its cardinality is minimum among all decycling sets. We abbreviate the latter to MDS. Reverse-complement invariance means $\operatorname{RC}(M)=M$ as a literal set of labelled words.

The line-graph identity $B(q,k)=L(B(q,k-1))$ lets us regard each length-$k$ word as the labelled lower-state arc

Deleting $M$ as vertices of $B(q,k)$ is equivalent to deleting those labelled arcs from $B(q,k-1)$; acyclicity is equivalent in the two representations.

Pure cycling registers and the ordinary minimum

Let $R(w_0\cdots w_{k-1})=w_1\cdots w_{k-1}w_0$. A pure cycling register (PCR) is an orbit under $R$, using distinct rotations only. Its cardinality is the minimal period of its words. PCRs partition $\mathcal{A}^k$, and each is a directed cycle. Their number is

Every decycling set meets every PCR. The matching construction for arbitrary finite alphabets is the unavoidable-set theorem of Champarnaud–Hansel–Perrin [1]; the original binary construction is due to Mykkeltveit [5]. Hence the ordinary minimum cardinality is $N_q(k)$, and an MDS selects exactly one distinct word from each PCR. The converse is false: one-per-PCR is only a local cardinality condition and can leave cycles using several PCRs. Every homopolymer $a^k$ is a singleton PCR loop and is a mandatory selection.

Full-alphabet source firings

For $u\in\mathcal{A}^{k-1}$ write

A forward firing, or full-alphabet $F$-move, is valid at $u$ for a selected set $M$ when $L(u)\subseteq M$, and then

These are literal sets. The two companion sets overlap only at a homopolymer loop, which is removed and reinserted. A valid $F$-move preserves ordinary-MDS status; this is the standard move of [3 Section 4.1]. Indeed, before the move the residual lower graph has no arc entering $u$, whereas afterward it has no arc leaving $u$. Any newly created directed cycle would have to enter $u$ along a restored arc and then leave through a deleted one, which is impossible. The result is therefore decycling. If a newly inserted outgoing companion other than the common loop had already belonged to $M$, the result would be a smaller decycling set, contradicting ordinary minimality; hence cardinality is preserved.

For an integer function $f$ on lower states, fix the gradient convention

The indicator update of a valid firing is $\nabla\mathbf{1}_u$, including at a homopolymer loop where both sides vanish.

Scope of the imported results

We import the ordinary cardinality theorem and the standard $F$-move terminology. We prove move preservation above, as well as the odd obstruction, the weighted arbitrary-zero-tie acyclicity theorem, equivariant zero ties, the exact coboundary, the terminating descent, and the direct midpoint selector. The k-nonical paper supplies a dated formulation of the reverse-complement-constrained problem [4]; it does not supply the parity theorem or the construction below. Our graph-theoretic result does not replace that paper’s optimization, implementation, or window-guarantee analysis.

The odd-order obstruction

The proof does not determine the exact odd excess; no formula inferred from small odd orders is used below.

The weighted cyclotomic seed and zero-sector ties

Assume for this section that $k \ge4$ is even. Choose an injective map

Such a map exists by assigning distinct positive magnitudes to the complement pairs. For DNA one may use $s(A)=-2$, $s(C)=-1$, $s(G)=1$, $s(T)=2$. The existence, descent, and direct-selector arguments use only real arithmetic, signs, and injectivity. Integrality will be imposed separately in Corollary 7.4, where a finite exact encoding and a bit complexity bound are required. Put $\zeta=e^{2\pi i/k}$ and, for $w=w_0\cdots w_{k-1}$, define

For $u=u_0\cdots u_{k-2}$ define

The selector

On each PCR with nonzero embedding select one word by the rule

1. select the point on the negative real axis, if it occurs;

2. otherwise select the unique $w$ satisfying $\operatorname{Im}P_s(w)<0<\operatorname{Im}P_s(Rw)$.

On a PCR where $P_s$ vanishes identically, select an arbitrary representative for now. Call the resulting set $M_0$ and write $m_0=1_{M_0}$.

A residual path cannot pass from $\operatorname{Im} P_s \le0$ to $\operatorname{Im} P_s > 0$: the strict crossing and departure from the negative ray are selected. Hence a residual cycle lies wholly in the open upper or closed lower half-plane.

Write $\theta= 2\pi/k$ and $P_s(w) = \rho e^{i\phi} \ne0$. Along an edge whose endpoints remain in the open upper region,

Along a residual edge in the closed lower region the same expression is strictly negative: the negative-ray starting point was selected and the remaining angular interval is $\pi+\theta\le\phi\le2\pi$. Thus a residual cycle could only consist of edges beginning at $P_s = 0$.

If consecutive labels $w$ and $y$ both have zero embedding, then $P_s(y) = s(a) - s(w_0) = 0$. Injectivity of $s$ gives $a = w_0$, so the edge is a pure rotation. Such a cycle is exactly a zero-embedding PCR, from which one word was selected. This final contradiction proves acyclicity. Since $M_0$ meets every PCR exactly once, it has cardinality $N_q(k)$.

Equivariant zero ties

Reverse complement permutes the zero PCRs. On a paired orbit $\{C,\operatorname{RC}(C)\}$, choose $w \in C$ and $\operatorname{RC}(w)$ in its mate. On a stable PCR, choose one of its two reverse-complement-fixed rotations; the alphabet-general fixed-rotation lemma is proved in Appendix § 13. From now on $M_0$ denotes a seed with these equivariant zero ties. The zero-sector part of $m_0$ is then literally reverse-complement invariant.

The half-plane coboundary

The open upper half-plane and the negative-real-axis convention are load-bearing. (4) is a literal edgewise identity, not an averaged symmetry statement.

Legal defect descent and even existence

Reverse complement carries an ordinary MDS to an ordinary MDS because it reverses directed cycles bijectively.

Proof. Assume otherwise. At every positive state $u$, failure of the source condition supplies an incoming residual arc $v \to u$. It may be chosen nonloop: a residual loop would already contradict that $A$ is decycling. Since this arc is not in $A$,

so $f(v)\ge f(u)>0$. Iterating the predecessor choice within the finite positive support eventually produces a directed residual cycle, a contradiction.

Proof. The physical firing gives $\mathbf{1}_{A'}-\mathbf{1}_{A}=\nabla\mathbf{1}_{u}$. Reverse complement reverses lower arcs, hence sends this gradient to $-\nabla\mathbf{1}_{\mathrm{RC}(u)}$. Subtracting the update from its image gives

The lower length $k-1$ is odd, so a reverse-complement-fixed lower word would have a central letter fixed by complement; therefore $u\ne\mathrm{RC}(u)$. Symmetry of $f$ makes both decremented coordinates positive. Nonnegativity, symmetry, and minimum zero are preserved, and the total decreases by two.

Proof. Theorem 5.1 initializes the symmetric nonnegative potential $f=\chi$. Its minimum is zero: every homopolymer lower word $a^{k-1}$ has

While the current MDS is not invariant, Lemmas 6.1–6.2 supply another legal move and decrease $\sum f$ by two. The process terminates.

At an invariant terminal, $\nabla f=0$. The lower de Bruijn graph is strongly connected—append the letters of any target word—so $f$ is constant. Its preserved minimum is zero, hence $f=0$. Conversely the potential cannot vanish before the indicator defect does. Starting from the 0–1 potential $\chi$ therefore gives exactly (5) moves.

The theorem asserts neither uniqueness of the terminal, confluence, nor shortest distance among unrestricted firing paths. A “paired update” is one physical firing whose defect potential changes at two lower states, not two simultaneous firings.

A direct spectral construction

The descent proves existence but need not be simulated. This section selects a particular self-dual ideal of positive lower states and thereby gives a direct terminal formula.

Fix any total order on $\mathcal{A}$ and use its lexicographic extension to lower words. Write $\vartheta(u)=\operatorname{RC}(u)$ and define

The final coefficient of $P_s(ua)-W_s(ua)$ is $s(a)(\zeta^k-1)=0$, so

for every appended letter $a$.

Define $a_\star:\mathcal{A}^{k-1}\to\{0,1\}$ by

Proof. Reindexing as in Lemma 4.1 gives

Thus $\lambda_s(\vartheta u)=\lambda_s(u)$ and $r_s(\vartheta u)=-r_s(u)$. Since $k-1$ is odd and the complement has no fixed letter, $\vartheta$ has no fixed lower word. Formula (7) therefore chooses exactly one member of every $\vartheta$-pair in $U$, proving (8).

Now let $w:u\to v$ be an edge with $u,v\in U$. Both consecutive imaginary coordinates are positive, so $w$ is not selected by the seed. From (6) and rotation covariance,

Writing $P_s(w)=\rho e^{i\phi}$ and $\alpha=2\pi/k$, the two positive imaginary coordinates imply $\alpha<\phi<\pi$. Hence

If $v\in A_\star$, then $r_s(v)\leq0$, so every predecessor $u$ has $r_s(u)<0$ and lies in $A_\star$. This is the ideal property. Strictness also shows that no residual edge joins two zero-level states, so the lexicographic tie in (7) cannot spoil ideality.

Proof. Fire the states of $A_\star$ in any predecessor-first order. Consider an incoming edge $x \to u$ when $u$ is to be fired. If it was selected by $M_0$, nothing is required. Otherwise it is an edge of the residual seed graph. If $x \notin U$, the defect identity (4) and Booleanity would force that edge to be selected by $M_0$, a contradiction. Thus $x \in U$; ideality puts $x$ in $A_\star$, and it was fired earlier, selecting its outgoing edge to $u$. No state of $U$ is a homopolymer, since the complete sine sum is zero there. Thus all incoming companions of $u$ are selected and the full-alphabet firing is legal.

The cumulative indicator update is exactly (10); in particular it is 0–1 valued and remains an ordinary MDS. For $w:u \to v$, equation (8) gives

Combining this with (4) yields $m_\star(\operatorname{RC} w) = m_\star(w)$.

The construction is direct in a precise sense: membership of a queried word uses the seed rule and the two endpoint values in (7), not a materialized list of firings or of $q^{k-1}$ lower states. For a deterministic seed, order PCRs by their lexicographically least word. In each paired zero-PCR orbit, select the least word of the smaller PCR and its reverse complement in the mate; on a stable zero PCR select the least of the two fixed rotations.

Proof. Weighted covariance uses only real linearity, antisymmetry, and complex conjugation. The zero-sector argument additionally uses injectivity to deduce equality of letters from equality of weights. The coboundary uses only signs, while its nonnegative integral potential is the indicator $\chi$, not the alphabet weight map. Finally, the direct construction uses the real order of $\lambda_s$ and $r_s$. Thus every preceding step remains valid for the stated real weights.

Proof. Appendix B reduces every required real and imaginary sign to the sign of an integer polynomial at $2\cos(2\pi/k)$, supplies an explicit algebraic separation bound, and invokes standard polynomial-bit real algebraic arithmetic. In the zero-PCR branch, at most $k$ distinct rotations and their reverse complements are inspected. All remaining operations are linear scans or lexicographic comparisons of words of length at most $k$.

The $q$-ary parity theorem

The only even order not covered by the cyclotomic argument is $k=2$.

Proof. Choose one representative $a_i$ from each complement pair and impose the complement-reversing order

Delete the word $xy$ exactly when $y \le x$. Every residual lower arc is strictly increasing, so the residual graph is acyclic. The deletion rule is invariant because $y \le x$ if and only if $\bar{x} \le\bar{y}$. It deletes all $q$ loops and one orientation of every unordered pair, hence

Proof of Theorem 1.1. For even $k \ge4$, choose any injective antisymmetric nonzero real weight map. Theorem 6.3 gives an invariant ordinary MDS, and Theorem 7.2 gives a deterministic direct choice of one. The case $k = 2$ is Lemma 8.1. Theorem 3.1 excludes ordinary minimum cardinality at every odd $k \ge3$.

Exact finite assurance and reproducibility

The proof above is deductive and alphabet-general. The public executable capsule is deliberately restricted to the binary specialization: it reconstructs $k=2,4,6,8,10,12$ using exact cyclotomic coordinates, verifies one-per-PCR selection, residual acyclicity, the edgewise coboundary, every legal firing, and the final literal symmetry. Keeping this scope explicit avoids presenting a finite sample as evidence for an all-order or alphabet-general quantifier.

Two implementations are used. The producer represents exact coordinates in the appropriate quadratic or cyclotomic integer rings and uses Kahn’s algorithm for the residual DAG. The independent validator uses frozen exact coordinate tables and a recursive DFS DAG oracle; it does not import the producer. Both reconstruct the complete scientific payload rather than comparing only summary counts.

The panel reports six rows and 612 legal source firings. Seven scientific mutations alter rotation, gradient, half-plane, ray, zero-tie, paired-update, or firing conventions; seven independent envelope mutations alter retained scientific fields. Every mutation must be rejected. Appendix § 14 gives the finite table, and the repository documentation gives the exact replay commands and stable payload identity.

This executable layer neither implements the direct $q$-ary membership algorithm of Corollary 7.4 nor tests genomic data. Those absences are intentional: the repository accompanies a mathematical article, not a sequence-analysis software release.

Boundaries and outlook

The parity theorem settles whether literal reverse-complement symmetry can be achieved at the ordinary necklace bound for every finite alphabet with a fixed-point-free complement. Several nearby questions remain distinct.

1. The exact premium $\Delta_q(k)$ at odd orders is not determined. The proof gives the uniform lower bound $q$ by counting disjoint obstructions, one for each complementary alphabet pair. This is a lower bound, not an equality claim or a packing–covering theorem.

2. The descent does not identify a unique terminal or a shortest path. The direct selector chooses one terminal after fixing weights and a total alphabet order, but different choices may produce different MDSs.

3. Minimum cardinality implies that the residual graph is acyclic, but it does not bound its longest directed path. Quantitative window guarantees require a separate analysis.

4. The fixed-point-free hypothesis is structural. If a complement has fixed letters, lower reverse-complement fixed points and odd-order PCR arguments change. The exceptional order $k = 1$ also behaves differently.

5. Corollary 7.4 is a word-membership theorem, not a claim that explicitly listing an exponentially large MDS takes polynomial total time.

6. No biological conservation, density, runtime, memory, clinical, or application-performance conclusion follows from the graph theorem alone.

The self-dual ideal description may nevertheless be useful independently of the present proof: it converts a global symmetry condition into an exact local membership rule while retaining the ordinary optimum. Understanding which choices of weights and midpoint ties also optimize residual-path statistics is a natural next mathematical problem.

Use of generative AI

Generative-AI assistants contributed substantively to the mathematical development, including candidate proof arguments, symbolic identities, construction and verification code, adversarial checks, and manuscript drafting. The author selected the problem, directed the research process, and is responsible for the article’s claims and final text. The two exact implementations are distinct, but the AI-assisted review process does not constitute independent specialist peer review. No end-to-end formal proof-assistant certification is claimed.

Convention dictionary

The theorem starts at $k = 2$. At $k = 1$ every vertex is a loop, the unique ordinary minimum is $A$, and the parity conclusion would be false.

Stable PCRs and exact algebraic signs

Stable rotation cycles

Proof. Choose $w \in C$ and $s$ (mod $d$) with $\operatorname{RC}(w) = R^s w$. In cyclic position notation,

The positional involution $r \mapsto s - 1 - r$ cannot have a fixed point. If $d$ were odd, 2 would be invertible modulo $d$ and $2r \equiv s - 1 \pmod d$ would have a solution, a contradiction. Thus $d$ is even. For even $d$, that congruence is solvable exactly when $s$ is odd, so $s$ is even. A rotation $R^i w$ is reverse-complement fixed precisely when

or $2i \equiv s \pmod d$. Since $d$ and $s$ are even, this congruence has exactly $\gcd(2,d) = 2$ solutions modulo $d.

Proof. The central letter of a fixed odd-length word would equal its complement.

These facts permit equivariant representatives on stable zero PCRs, but do not by themselves imply global acyclicity; Theorem 4.3 is still essential.

Polynomial-bit exact sign determination

We justify Corollary 7.4. In this subsection only, specialize the real weight map used by the existence proof to an integer-valued map. Put

For $k \ge4$, $c$ is an algebraic integer of degree $d$. If $\Psi_k$ is its monic minimal polynomial, it is recovered from the reciprocal cyclotomic identity

Classical minimal-polynomial formulas provide the same representation [7]. Among the real conjugates of $c$, the chosen value is the largest one; this property gives a canonical exact isolating interval for the root of $\Psi_k$ at which all subsequent signs are evaluated. Define integer polynomials

At $x=c$,

Since $\sin(2\pi/k)>0$, every sign or zero used in the seed and midpoint rules reduces to an integer polynomial at $c$:

Reducing a polynomial modulo $\Psi_k$ decides exact zero: the value vanishes at $c$ precisely when the remainder is the zero polynomial. For a nonzero remainder $g$, each conjugate $c_i$ of $c$ lies in $[-2,2]$. The elementary bounds $|C_j(c_i)|\le2$ and $|S_j(c_i)|\le j$ imply the common safe estimate

Because $g(c)$ is a nonzero algebraic integer, its field norm is a nonzero rational integer. Therefore

Certified interval evaluation below half this gap determines the sign. The coefficients of $\Phi_k$, $\Psi_k$, the recurrences, and their remainders have bit length polynomial in $k$ and $\log(B+1)$. Standard Sturm–Habicht real-root isolation and sign evaluation operate in polynomial bit complexity [2]. Equation (13) requires only $O(k(\log B+\log k))$ refinement bits. Scanning at most $k$ rotations handles a deterministic zero-PCR tie. This proves the claimed polynomial preprocessing, query, and workspace bounds without a real-RAM or floating-point assumption.

Finite validation boundaries

The executable binary panel has four epistemic roles: it verifies the left-rotation and gradient conventions; exercises negative-ray, strict-crossing, and zero-sector cases; replays every legal firing and terminal invariant; and rejects convention mutations. It neither interpolates in $k$ nor tests the alphabet-general theorem.

$k$	PCRs	zero PCRs	stable zero	paired zero	$|\operatorname{supp}\chi|$	firings
2	3	0	0	0	0	0
4	6	3	1	1	2	1
6	14	5	1	2	10	5
8	36	6	2	2	52	26
10	108	9	1	4	220	110
12	352	19	5	7	940	470

The total is 612 legal firings. Runtime and envelope metadata are excluded from the stable scientific payload. The paper proof, not this table or its hash, is authority for every all-order statement.