Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 10 down vote accepted

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

share|improve this answer
1  
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 –  Gerhard Paseman Sep 15 '12 at 17:20
    
@Ian: Thank you! –  Mark Sapir Sep 15 '12 at 17:49
1  
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. –  Steve Huntsman Sep 15 '12 at 20:41
    
@Steve: Thank you for the comment. –  Mark Sapir Sep 16 '12 at 5:07
1  
Here is a nice paper on subword complexity that gives the same answer: csd.uwo.ca/faculty/ilie/IJFCS04.pdf . –  Mark Sapir Sep 16 '12 at 12:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.