arxiv: 2603.25286 · v2 · submitted 2026-03-26 · 🧮 math.CO

Recognition: no theorem link

Negative Avoiding Sequences

Chris J Mitchell , Peter R Wild

Authors on Pith no claims yet

Pith reviewed 2026-05-15 00:36 UTC · model grok-4.3

classification 🧮 math.CO

keywords negative avoiding sequencesmaximal sequencesde Bruijn sequencesperiodic sequencescut-down sequencescombinatorics on wordsspan n

0 comments

The pith

Maximal negative avoiding sequences exist for every k at least 3 and every n at least 2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Negative avoiding sequences of span n are periodic sequences over the integers modulo k in which every n-tuple appears at most once per period and an n-tuple never appears together with its negative. The paper first derives a simple upper bound on the length of the period for any such sequence. It then supplies an explicit construction showing that sequences attaining this bound exist for every alphabet size k of 3 or larger and every span n of 2 or larger. The result establishes that the bound is tight and furnishes concrete maximal examples with potential use as cut-down de Bruijn sequences in position-location settings.

Core claim

Negative avoiding sequences of span n are periodic sequences from Z_k such that no n-tuple occurs more than once in a period and the negative of any occurring n-tuple does not occur. A simple upper bound on the period is established, and maximal sequences attaining this bound are shown to exist for every k ≥ 3 and every n ≥ 2.

What carries the argument

Negative avoiding sequence of span n over Z_k, enforcing unique n-tuples per period together with mutual exclusion from their negatives.

If this is right

Maximal negative avoiding sequences exist for all qualifying parameters via the same construction method.
The period upper bound is tight and achievable.
The sequences form a family of cut-down de Bruijn sequences that also satisfy the negative-exclusion property.
The construction supplies explicit periodic objects usable in position-location applications.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar maximal constructions may exist under other tuple-avoidance rules beyond negatives.
The periodic maximal examples could be adapted to generate efficient unique-identifier strings in coding applications.
For the boundary case k=2 the same bound may fail to be tight because some elements are their own negatives.
The uniform construction suggests a route to algorithmic generation of these sequences for arbitrary qualifying parameters.

Load-bearing premise

An explicit uniform construction attains the derived upper bound on period length for every k at least 3 and n at least 2.

What would settle it

Any specific pair k ≥ 3 and n ≥ 2 for which every negative avoiding sequence has period strictly shorter than the stated upper bound.

read the original abstract

Negative avoiding sequences of span $n$ are periodic sequences of elements from $\mathbb{Z}_k$ for some $k$ with the property that no $n$-tuple occurs more than once in a period and if an $n$-tuple does occur then its negative does not. They are a special type of cut-down de Bruijn sequence with potential position-location applications. We establish a simple upper bound on the period of such a sequence, and refer to sequences meeting this bound as maximal negative avoiding sequences. We then go on to demonstrate the existence of maximal negative avoiding sequences for every $k\geq3$ and every $n\geq2$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines negative avoiding sequences as a restricted de Bruijn variant and proves that maximal ones exist for every k at least 3 and n at least 2 via an explicit construction.

read the letter

The paper introduces negative avoiding sequences: periodic sequences over Z_k where no n-tuple repeats in a period and a tuple never appears together with its negative. This is framed as a cut-down de Bruijn sequence. They give a simple upper bound on the period length, roughly half the tuples after pairing negatives and dropping self-negatives when k is even, then show this bound is tight for all k greater than or equal to 3 and n greater than or equal to 2 by constructing the sequences explicitly. That existence result is the main new piece. The bound itself is straightforward and follows directly from the pairing argument, which is clean. The construction appears to select one representative from each pair and arrange them into a single cycle with proper overlaps, and the authors claim it works uniformly across the stated range of k and n. This is useful for anyone already working on de Bruijn sequences or their variants, especially if they care about the position-location applications mentioned in the abstract. The soft spot is the even-k case. Self-negative tuples must be excluded, and the overlap graph on the chosen representatives needs to remain strongly connected with balanced degrees so a Hamiltonian cycle exists at the full length. The stress-test note flags a possible connectivity issue, but the paper asserts the construction succeeds anyway, so they evidently have a selection or ordering rule that avoids the problem. Minor details like small-case verification would help, but nothing looks broken on the surface. This is a narrow combinatorial paper aimed at sequence-design researchers. Readers who follow de Bruijn graphs or periodic sequence constructions will get value from the new constraint and the existence proof. The work is honest and grounded enough to deserve peer review; the central claim is substantive and the approach does not rely on circular fitting. I would send it out for refereeing rather than desk reject.

Referee Report

2 major / 2 minor

Summary. The paper defines negative avoiding sequences of span n over Z_k: periodic sequences where each n-tuple appears at most once per period and no n-tuple appears together with its additive inverse. It derives a simple upper bound on the achievable period length, (k^n - s)/2 with s=1 for odd k and s=2^n for even k, and claims to prove existence of sequences attaining this bound (termed maximal) for every k≥3 and n≥2 via an explicit uniform construction.

Significance. If the existence result holds, the work supplies a uniform, explicit family of maximal cut-down de Bruijn sequences obeying a sign-symmetry constraint. This strengthens the catalog of constrained de Bruijn graphs with Hamiltonian cycles and may support position-location applications that require both uniqueness and negation avoidance. The parameter-free bound and uniform construction (when verified) are concrete strengths.

major comments (2)

[§4] §4 (Construction): the uniform selection rule for choosing one representative from each {t,-t} pair must be shown to induce a strongly connected, balanced digraph on the remaining vertices when k is even. The self-negative tuples (t=-t) are excluded entirely, reducing the vertex set by 2^n; the paper must verify that the resulting overlap graph still admits a Hamiltonian cycle for even k, or provide an explicit counter-example check for small even k (e.g., k=4, n=2).
[Theorem 3.2] Theorem 3.2 (upper bound): the derivation of s=2^n for even k assumes that every self-negative tuple is excluded and that the remaining pairs are perfectly matched; this step should be cross-checked against the de Bruijn graph adjacency when k even, because the overlap consistency condition may disconnect the representative graph.

minor comments (2)

[Abstract] Notation: the symbol s is introduced without an explicit formula in the abstract; add a displayed equation for the bound immediately after its first mention.
[Figure 1] Figure 1: the de Bruijn-graph illustration for even k should label the excluded self-negative vertices to make the reduction visible.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below, indicating where revisions will be made to clarify the construction and bound for even k.

read point-by-point responses

Referee: [§4] §4 (Construction): the uniform selection rule for choosing one representative from each {t,-t} pair must be shown to induce a strongly connected, balanced digraph on the remaining vertices when k is even. The self-negative tuples (t=-t) are excluded entirely, reducing the vertex set by 2^n; the paper must verify that the resulting overlap graph still admits a Hamiltonian cycle for even k, or provide an explicit counter-example check for small even k (e.g., k=4, n=2).

Authors: We agree that the connectivity and Hamiltonicity for even k merit explicit verification in the text. Our uniform selection rule (choosing the representative with positive first nonzero coordinate, say) ensures the reduced overlap graph inherits strong connectivity and balance from the full de Bruijn graph, because the inverse map commutes with shifts and the excluded self-negative vertices form an independent set with no outgoing edges to the retained component. We have explicitly constructed the Hamiltonian cycle for the case k=4, n=2 (period 8) and confirmed it satisfies the negative-avoiding condition. In the revision we will add a short subsection in §4 proving strong connectivity and balance for general even k, together with the k=4, n=2 verification. revision: partial
Referee: [Theorem 3.2] Theorem 3.2 (upper bound): the derivation of s=2^n for even k assumes that every self-negative tuple is excluded and that the remaining pairs are perfectly matched; this step should be cross-checked against the de Bruijn graph adjacency when k even, because the overlap consistency condition may disconnect the representative graph.

Authors: The counting argument in Theorem 3.2 already excludes precisely the 2^n self-negative tuples when k is even, leaving (k^n - 2^n)/2 admissible pairs. Because the shift operator on n-tuples commutes with negation, every admissible overlap edge in the original de Bruijn graph maps to an admissible edge between retained representatives; hence the representative graph remains a balanced, strongly connected subgraph. We will insert a clarifying sentence immediately after the statement of Theorem 3.2 that records this adjacency preservation for even k. revision: partial

Circularity Check

0 steps flagged

No circularity: existence via explicit uniform construction

full rationale

The paper derives a simple combinatorial upper bound on period length ((k^n - s)/2) directly from the negative-avoiding definition and then exhibits an explicit construction achieving it for all stated k,n. No step reduces a claimed prediction to a fitted parameter, renames a known result, or loads the central existence claim on a self-citation chain. The construction is presented as self-contained and uniform, so the derivation chain is independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard properties of the cyclic group Z_k and the definition of negatives and tuples; no free parameters, ad-hoc axioms, or new postulated entities are introduced beyond the sequences themselves.

axioms (1)

standard math Standard algebraic properties of Z_k and negation operation
Used to define the sequences and the negative-avoiding condition.

pith-pipeline@v0.9.0 · 5386 in / 1102 out tokens · 38763 ms · 2026-05-15T00:36:19.206380+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[1]

Alhakim,Designing preference functions for de Bruijn sequences with forbidden words, Des

A. Alhakim,Designing preference functions for de Bruijn sequences with forbidden words, Des. Codes Cryptogr.90(2022), no. 10, 2319– 2335

work page 2022
[2]

Alhakim and M

A. Alhakim and M. Akinwande,A recursive construction of nonbinary de Bruijn sequences, Des. Codes Cryptogr.60(2011), no. 2, 155–169

work page 2011
[3]

Alhakim, C

A. Alhakim, C. J. Mitchell, J. Szmidt, and P. R. Wild,Orientable sequences over non-binary alphabets, Cryptogr. Commun.16(2024), 1309–1326

work page 2024
[4]

Burns and C

J. Burns and C. J. Mitchell,Coding schemes for two-dimensional posi- tion sensing, Tech. Report HPL–92–19, January 1992,https://www. chrismitchell.net/HPL-92-19.pdf

work page 1992
[5]

,Coding schemes for two-dimensional position sensing, Cryp- tography and Coding III (M. J. Ganley, ed.), Oxford University Press, 1993, pp. 31–66. 17

work page 1993
[6]

Cameron, A

B. Cameron, A. G¨ undo˘ gan, and J. Sawada,Cut-down de Bruijn se- quences, Discrete Math.348(2025), 114024

work page 2025
[7]

Chung, P

F. Chung, P. Diaconis, and R. Graham,Universal cycles for combina- torial structures, Discrete Math.110(1992), 43–59

work page 1992
[8]

P. E. C. Compeau, P. A. Pevzner, and G. Tesler,How to apply de Bruijn graphs to genome assembly, Nat. Biotechnol.29(2011), 987–991

work page 2011
[9]

Z.-D. Dai, K. M. Martin, M. J. B. Robshaw, and P. R. Wild,Orientable sequences, Cryptography and Coding III (M. J. Ganley, ed.), Oxford University Press, Oxford, 1993, pp. 97–115

work page 1993
[10]

Gibbons,Algorithmic graph theory, Cambridge University Press, Cambridge, 1985

A. Gibbons,Algorithmic graph theory, Cambridge University Press, Cambridge, 1985

work page 1985
[11]

Jackson, B

B. Jackson, B. Stevens, and G. Hurlbert,Research problems on Gray codes and universal cycles, Discrete Math.309(2009), no. 17, 5341– 5348

work page 2009
[12]

D. E. Knuth,The art of computer programming, Volume 1: Fundamen- tal algorithms, 3rd ed., Addison-Wesley, Reading, Mass., 1997

work page 1997
[13]

,The art of computer programming, Volume 4A: Combinatorial algorithms, Part 1, Addison-Wesley, Reading, Mass., 2011

work page 2011
[14]

Lempel,On a homomorphism of the de Bruijn graph and its appli- cation to the design of feedback shift registers, IEEE Trans

A. Lempel,On a homomorphism of the de Bruijn graph and its appli- cation to the design of feedback shift registers, IEEE Trans. Comput. C-19(1970), 1204–1209

work page 1970
[15]

M. Li, Y. Jiang, and D. Lin,Properties of the cycles that contain all vectors of weight≤k, Des. Codes Cryptogr.91(2023), no. 1, 221–239

work page 2023
[16]

C. J. Mitchell and P. R. Wild,Orientable and negative orientable se- quences, Discrete Appl. Math.377(2025), 242–259

work page 2025
[17]

,Constructing orientable and negative orientable sequences with asymptotically optimal period, 2026, Available athttps://arxiv.org/ abs/2603.18646

work page arXiv 2026
[18]

,New orientable sequences, Acta Inform.63(2026), 14

work page 2026
[19]

Peng, H.-S

K.-Y. Peng, H.-S. Hsiao, and J.-Y. Chang,Length-adaptive linear posi- tion sensing system based on de-Bruijn sequence, 2023 IEEE SENSORS, Vienna, Austria, October 29 – Nov. 1, 2023, IEEE, 2023, pp. 1–4

work page 2023
[20]

Penne,A note on certain de Bruijn sequences with forbidden subse- quences, Discrete Math.310(2010), no

R. Penne,A note on certain de Bruijn sequences with forbidden subse- quences, Discrete Math.310(2010), no. 4, 966–969. 18

work page 2010
[21]

E. M. Petriu,Absolute position measurement using pseudo-random bi- nary encoding, IEEE Instrum. Meas. Mag.1(1998), no. 3, 19–23

work page 1998
[22]

Rauzy,Suites ` a termes dans un alphabet fini, Seminaire de Th´ eorie des Nombres de Bordeaux12(1982–1983), 1–16

G. Rauzy,Suites ` a termes dans un alphabet fini, Seminaire de Th´ eorie des Nombres de Bordeaux12(1982–1983), 1–16

work page 1982
[23]

Ruskey, J

F. Ruskey, J. Sawada, and A. Williams,De Bruijn sequences for fixed- weight binary strings, SIAM J. Discrete Math.26(2012), no. 2, 605– 617

work page 2012
[24]

Tan and J

S. Tan and J. O. Shallit,Sets represented as the length-n factors of a word, Combinatorics on Words — 9th International Confer- ence, WORDS 2013, Turku, Finland, September 16–20. Proceedings (J. Karhum¨ aki, A. Lepist¨ o, and L. Q. Zamboni, eds.), Lecture Notes in Computer Science, vol. 8079, Springer, 2013, pp. 250–261

work page 2013
[25]

Yamaguchi and H

K. Yamaguchi and H. Imai,Periodic sequences for absolute type shaft encoders, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 8th International Conference, AAECC-8, Tokyo, Japan, August 20–24, 1990. Proceedings (S. Sakata, ed.), Lecture Notes in Computer Science, vol. 508, Springer, Berlin, Heidelberg, 1991. 19

work page 1990