4
$\begingroup$

I wish to ask a problem in periodic strings, it might be well-known but I am a beginner in this subject, so I am very glad if someones can show me. My problem is that can we add some string to the end of a periodic string ($S$) to have a new periodic string ($S'$)? If yes, what are the conditions?

More formally, given $$S = [a_1 a_2 ... a_n]_t$$​ - S is a periodic string (a string of $t$ repeated string $a_1 a_2 ... a_n$​), where $n > 1$ and $t > 1$ and $a_i∈ A$ where $A$ is the alphabet (here we only consider the minimal $n$ such that $S$ is a period string - there does not exist $n'<n$ such that $S$ is a period string of consecutive strings of length $n'$). Suppose that if we concatenate a string [$c_1 c_2...c_k$] to $S$ ($c_j∈ A$​ for all $j = 1,...,k$), then we have: $$S' = [a_1 a_2 ... a_n]_t [c_1 c_2...c_k].$$​ So, does there exist the positive integers $m, s (m>1,s>1)$ such that $S' = [a_{\pi(1)}...a_{π(m)}]_s$​ - another periodic string, where $π$ is some permutation from $\mathbf N$ to $\mathbf N$? If yes, what are the conditions? And are there some good algorithms to test this problem?

We see a trivial case when $[c_1 c_2...c_k] = [a_1 a_2 ... a_n]_v$ for any $v \in \mathbf N^*$. Do we have other cases? Could someone show me some researchs in this problem?

Thank you very much for your attention!

$\endgroup$
  • $\begingroup$ There is a substantial literature on infinite strings which have substrings of fractional periods, e.g.w=s^{7/3}. The name James Currie comes to mind. However, you assume a minimality condition which often does not occur. If this holds, then I do not see any other cases that would occur, and if the a_i are letters and not words, then you probably have very little left to conclude your analysis. Gerhard "Repeats Himself Sometimes Repeats Himself" Paseman, 2016.03.22. $\endgroup$ – Gerhard Paseman Mar 22 '16 at 15:35
  • 1
    $\begingroup$ Without restrictions on $k$ (for example $k<nt$) there are stupid example, e.g. $[ab]_2+[bababb]=[ababb]_2.$ $\endgroup$ – Mikhail Ivanov Mar 22 '16 at 17:17
  • $\begingroup$ @MikhailIvanov: Nice! I am curios particularly about the case $k < n$(certainly it is not the condition for this problem). Do you have any idea? $\endgroup$ – Cuong Mar 22 '16 at 17:39
  • $\begingroup$ Are you restricting $t$ to be an integer? $\endgroup$ – Joel Reyes Noche Mar 23 '16 at 0:40
  • 1
    $\begingroup$ Here is a nontrivial example: $[abaababa]_2 = [abaab]_2 [aababa]$. $\endgroup$ – Douglas Zare Mar 23 '16 at 5:43
2
$\begingroup$

I'll use exponents instead of subscripts to show repetition.

To have nontrivial examples, the power of the longer word must be two or three, and you can't have two complete repetitions of the longer word within the power of the shorter word. For example, $[abababa]^2$ is a prefix of $[abababaab]^2$ and $[abababaab]^3$.

It suffices to consider the case that the words have lengths that are relatively prime. Otherwise, a nontrivial example would force the existence of a nontrivial example on a subsequence. So, assume the words have coprime lengths, so the shorter has length $m$ and the longer has length $n$.

If the powers of the shorter word contain the square of the longer word and the lengths are coprime, this forces a chain of equalities connecting every position. Consider $a_0=a_n=a_{n-m}=...$ where at each step the index increases by $n$ or decreases by $m$, and the index stays smaller than $2n$. The indices cover every residue class mod $m$ since $n$ and $m$ are coprime, so this forces $a_0=a_1=...=a_{m-1}$ and thus if these are the minimal periods, $m=n=1$.

$\endgroup$
  • 1
    $\begingroup$ What I said about the coprime case being the essential one is true, but the argument I gave for the reduction doesn't quite work since it is possible for the subsequences to be trivial in incompatible ways so that the whole sequence is nontrivial while the subsequences are not, However, it is true that if there is a nontrivial example when the lengths are not coprime then you can factor out the common factor by passing to a larger alphabet. $\endgroup$ – Douglas Zare Mar 24 '16 at 0:14
  • $\begingroup$ Thank you very much, Douglas, for your idea of coprime case. I am thinking about your suggestion, I hope that it could work for the general case. $\endgroup$ – Cuong Mar 24 '16 at 7:24
  • $\begingroup$ This covers the general case. $\endgroup$ – Douglas Zare Mar 24 '16 at 7:41
  • $\begingroup$ I don't understand why "the power of the longer word must be two or three" and what you mean by "you can't have two complete repetitions of the longer word within the power of the shorter word". Could you write it more formally by equations and proofs when you have time? $\endgroup$ – Cuong Mar 24 '16 at 8:06
  • $\begingroup$ If the power of the longer word is greater than three, then in the first half (contained in the square of the shorter word), there is a square of the longer word, which can't happen, as I proved in the last paragraph. $\endgroup$ – Douglas Zare Mar 24 '16 at 16:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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