3
$\begingroup$

This might be trivial, or difficult, I do not know. I could not find anything on the internet and feel stupid for not seeing anything more straightforward.

The question is whether for any alphabet $\Sigma$ and any length $n$

there is a string such that every word of length $n$ over the alphabet $\Sigma$ is contained exactly once in that string?

TL;DR: This is what I have, which is pretty much nothing.

Some time ago, I was dealing with LFSR and find out, that the output stream (or string) of $1$s and $0$s has a interesting property: Every word of a length n is contained in this string exactly once, well except all zeros. However there is a sequence $100..n-1 \text{ zeros}..01$, which can easily be extended by one more zero to get the a sequence of length $2^n+n-1$ where every word of length n is contained exactly once.

However, since these words are overlapping, it is not immediately obvious something like that should be possible. From the properties of LFSR, one can prove this is true for any length of any alphabet with $2^n$ characters. But LFSR is build over a certain model in theory of finite fields of characteristic $2$, so not much help for proving required results for other numbers.

The principle is that there is a polynomial over $\mathbb Z/\mathbb Z_2,$ such that $x$ is its primitive root. We then multiply the register with it and take the remainder after division with this polynomial, and only write down the highest bit in the register. But for any setting of the register, there is a unique output sequence of length $n$, and every state of the register is repeated only after the maximal period, therefore no output sequences of length $n$ can appear with less than $2^n$ distance. And this runs in cycle, if we break the cycle and put required number of characters in line, we get required string.

This cant be applied, or at least I do not know how to apply this to general $n$. We might be able to prove this for any prime power, if there are such polynomials where $x$ is a primitive root in the corresponding field for any finite field. Or maybe $x$ does not need to be primitive root. The fact about not repeating sequence of $n$ characters should remain true if we use any primitive root of the finite field. However I can only use it as a good argument, but I can't prove it. Still, that would prove prime powers and the question remains, how to combine this prime power sequences together to obtain such a string for general $n$.

The reason I know this for LFSR is because I was able to create a reverse-engineering process of the initial state of the LFSR from obtained $n$ bits, therefore there is bijective mapping between $n$ bits and state of the register. However for other finite fields I do not know.

For general $n$, I also considered proving that a certain graph is Hamiltonian (oriented graph where two words are connected with an edge if one's suffix without first letter is the other one's prefix without the last letter). But for Hamiltonian graph there is no simple characteristic to look for or prove, so I gave up on that idea.

All of this might be worthless, but I have no idea what other observation could be used here. Those were my attempts, perhaps overly complicated, but if there is no simple solution, they might serve as an inspiration.

And to provide with some example of $2$ letter words over alphabet of size $3$: $1233221131$

$\endgroup$
  • 2
    $\begingroup$ Hmm... it sounds like De Brujin sequence. $\endgroup$ – achille hui Sep 20 '17 at 20:02
  • $\begingroup$ Right, you can cut a De Brujin sequence and then repeat the first $n-1$ characters to get one of these sequences. Your example is such a case, since $n=2$ and your last $n-1$ characters are the same as the first $n-1$ characters. $\endgroup$ – Thomas Andrews Sep 20 '17 at 20:06
  • $\begingroup$ @achillehui Thanks, I thought it either will be simple or something known, but no matter what I put in the google describing this issue, I could not find any reference to this. $\endgroup$ – TStancek Sep 20 '17 at 20:11

Your Answer

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

Browse other questions tagged or ask your own question.