7
$\begingroup$

Let $W$ be a cyclic word of length $n$ in a 2-letter alphabet $\{0,1\}$. It is clear that it has at most $n^2$ different subwords (because the number of subwords of length $i$ is at most $n$ for each $i$) and that the actual number of subwords is less than $n^2$ (because the number of subwords of length $1$ is not $n$, but $2$). What is the maximal possible number of subwords as a function of $n$ and what are words where this upper bound is achieved.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

If you take a de Bruijn sequence of length $2^k$, then you have every length $k$ sequence precisely once. This implies that the number of subwords is maximal, since each subword of length $\geq k$ is determined uniquely by its prefix, and each subword of length $ < k$ occurs (with equal frequency). So this achieves the upper bound when $n=2^k$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ A similar analysis applies for general n. If m is the smallest integer such that every subword of n of length m is unique, then the number of unique subwords total is at least n(n-m+1). Thus m will always be at least floor(log n). But it should be possible to find a length n fragment of a Debruijn word which will achieve minimal m, as well as attain the largest number of distinct subwords of smaller length. Gerhard "Ask Me About System Design" Paseman, 2012.09.15 $\endgroup$
    – Gerhard Paseman
    Commented Sep 15, 2012 at 17:20
  • 1
    $\begingroup$ You can go the other way too. If you have a prescribed multiplicity for each word, you can form a corresponding directed (Eulerian) multigraph in an obvious generalization of the de Bruijn construction. Then you can use the matrix-tree and BEST theorems to enumerate the sequences with these multiplicities. If you google "generalized de Bruijn" and restrict to site:mathoverflow.net you'll find one or two posts of mine on this topic. $\endgroup$
    – Steve Huntsman
    Commented Sep 15, 2012 at 20:41
  • 1
    $\begingroup$ Here is a nice paper on subword complexity that gives the same answer: csd.uwo.ca/faculty/ilie/IJFCS04.pdf . $\endgroup$
    – user6976
    Commented Sep 16, 2012 at 12:14

You must log in to answer this question.