Skip to main content
MathOverflow

Return to Question

fixed typesetting
Source Link
Igor Rivin
Igor Rivin
  • 96.4k
  • 11
  • 153
  • 366

I have a feeling that the following question might have been studied: Suppose I have a finite alphabet $A,$ with $|A| = n,$ and a string $S$ of length $N.$ A string can be said to contain a $k$-th power, if $$S = S_1 S_2^k S_3,$$$S = S_1 S_2^k S_3,$$ where exponentiation means that $S_2$$S_2$ is repeated $k$$k$ times, and $S_1$$S_1$ and $S_3$$S_3$ might be empty. Let $P(n, N)$$P(n, N)$ be the function defined by: every string of length $N$$N$ over an alphabet of length $n$$n$ contains a $P(n, N)$$P(n, N)$-th power. Now, the question(s):

  1. What is the (asymptotic) behavior of $P(n, N)?$
  2. Given a string $S$ as above, how hard is it to compute whether $S$ contains a $k$-th power?
  3. What can one say about random strings?

I have a feeling that the following question might have been studied: Suppose I have a finite alphabet $A,$ with $|A| = n,$ and a string $S$ of length $N.$ A string can be said to contain a $k$-th power, if $$S = S_1 S_2^k S_3,$ where exponentiation means that $S_2$ is repeated $k$ times, and $S_1$ and $S_3$ might be empty. Let $P(n, N)$ be the function defined by: every string of length $N$ over an alphabet of length $n$ contains a $P(n, N)$-th power. Now, the question(s):

  1. What is the (asymptotic) behavior of $P(n, N)?$
  2. Given a string $S$ as above, how hard is it to compute whether $S$ contains a $k$-th power?
  3. What can one say about random strings?

I have a feeling that the following question might have been studied: Suppose I have a finite alphabet $A,$ with $|A| = n,$ and a string $S$ of length $N.$ A string can be said to contain a $k$-th power, if $$S = S_1 S_2^k S_3,$$ where exponentiation means that $S_2$ is repeated $k$ times, and $S_1$ and $S_3$ might be empty. Let $P(n, N)$ be the function defined by: every string of length $N$ over an alphabet of length $n$ contains a $P(n, N)$-th power. Now, the question(s):

  1. What is the (asymptotic) behavior of $P(n, N)?$
  2. Given a string $S$ as above, how hard is it to compute whether $S$ contains a $k$-th power?
  3. What can one say about random strings?
Source Link
Igor Rivin
Igor Rivin
  • 96.4k
  • 11
  • 153
  • 366

powers in strings

I have a feeling that the following question might have been studied: Suppose I have a finite alphabet $A,$ with $|A| = n,$ and a string $S$ of length $N.$ A string can be said to contain a $k$-th power, if $$S = S_1 S_2^k S_3,$ where exponentiation means that $S_2$ is repeated $k$ times, and $S_1$ and $S_3$ might be empty. Let $P(n, N)$ be the function defined by: every string of length $N$ over an alphabet of length $n$ contains a $P(n, N)$-th power. Now, the question(s):

  1. What is the (asymptotic) behavior of $P(n, N)?$
  2. Given a string $S$ as above, how hard is it to compute whether $S$ contains a $k$-th power?
  3. What can one say about random strings?