Periods and Borders of Strings and How They Are Related

The Relationship Between the Period and the Border

Theorem:

If a string of length n has a border of length k, then it also has a period of length n−k.

Proof:

Let a string αα be given.

Let us formally write the definition of a border of length kk of the string αα:

Let us make the substitution x=n−k:

We have obtained the definition of a period of length x. But x=n−k, so the string αα has a period of length n−k.

Properties of the Period

Theorem (on multiple periods):

If a string has a period of length k, then it also has a period of length kx, where x∈N.

Proof:

Let the length of the string be nn, and the string itself — α.

We carry out the proof by induction on the number x.

• Base

  For x=1 the statement is obvious.

• Inductive step

  Suppose it is true for x⩽m. Let us prove the same for x=m+1.

  From the definition of a period we have

  

  and from the induction hypothesis

  

  Taking this into account, we obtain that

  

  hence

  

  So the string has a period of length k(m+1).

The statement is proved.

Before proving the next theorem, let us check a couple of intuitively clear statements.

Lemma (1):

Let a string ss have periods p and q, where q

Proof:

Let us show the truth of the statement for the prefix; the proof for the suffix is analogous.

We need to show:

Since ss has period p, we have

Also s has period q, and from the constraints on ii it holds that , hence

Lemma (2):

Let a string ww have period qq, and let there exist a substring vv of ww such that |v|⩾q|v|⩾q and vv has period rr, where qq ⋮⋮ rr. Then ww has period rr.

Proof:

Let

We need to show: .

Let us fix ii and jj. Note that since |v|⩾q|v|⩾q, the segment [h,k][h,k] contains at least qq integers, so there will be found

j.

Given that qq ⋮⋮ rr, we can write i≡i′(modr), j≡j′(modr)i≡i′(modr), j≡j′(modr).

Moreover, i≡j(modr), and in that case i′≡j′(modr) also holds.

Now let us use the following fact: if a string ss has period rr, then i≡j(modr) ⇒ si=sj (indeed, without loss of generality we may assume that i⩽, and from this build the chain of equalities si=si+r, si+r=si+2r, …, sj−r=s).

Since ww has period qq, the equalities si=si′ si=si′ and sj=sj′ sj=sj′ hold. Moreover vv has period rr, so si′=sj′si′=sj′ holds. Hence si=sjsi=sj as well.

Theorem (Fine and Wilf):

If a string ww has periods p and q, where is also a period of this string.

Proof:

Let us denote r=gcd(p,q). We carry out the proof by induction on n=(p+q)/r.

In the case p=q we see that n=2, which corresponds to the base case, whereas for p≠q we have max(p,q)>gcd(p,q), so n>2.

• Base

  The truth of the statement follows from p=q=r.

• Inductive step

  Since p≠q, without loss of generality let us assume q

  Let w=uv, where |u|=q.

  By Lemma 1 vv has period p−qp−q, and vv also has period qq as a substring of ww. Now let us consider the length of vv:

  

  Note also that for the periods p−q, q the value of n will be smaller than for p, q, since . Then by the induction hypothesis we conclude: v has period Taking into account , we can say that vv has period r.

  As already mentioned, , hence , and consequently, by Lemma 2, ww has period rr.

See Also

• Basic definitions related to strings