6
$\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.

$\endgroup$
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$.

| cite | improve this answer | |
$\endgroup$
  • 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 Sep 15 '12 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 Sep 15 '12 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 Sep 16 '12 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy