1. Introduction
The study of sequences have applications in numerous fields such as biology, computer science, mathematics, and physics. DNA molecules, which carry the genetic information in almost all organisms, play an important role in molecular biology (see [3, 5, 6, 13]). DNA computing experiments use informationencoding strings that possess WatsonCrick complementarity property between DNA singlestrands which allows informationencoding strands to potentially interact. Formally, the WatsonCrick complementarity property on strings over is an involution with the additional property that for all strings where is an involution, i.e., equals the identity.
The notion of palindrome was defined in [9] to study palindromes from the perspective of DNA computing. It was defined independently in [4], where closure operators for palindromes were considered. The classical results on conjugacy and commutativity of words are present in [14]. In [2], the authors study the properties of primitive words. They prove the existence of a unique primitive root of a given word, and provided some constraints under which two distinct words share their primitive root. The combinatorial properties of strings in connection to partial words were investigated in [1]. The notions of conjugacy and commutativity was generalized to incorporate the notion of WatsonCrick complementarity of DNA singlestrands in [9]. The authors define and study properties of WatsonCrick conjugate and commutative words, as well as WatsonCrick palindromes. They provide a complete characterization of the set of all words that are not WatsonCrick palindromes. Some properties that link the WatsonCrick palindromes to classical notions such as that of primitive words are established in [10]. The authors show that the set of WatsonCrickpalindromic words that cannot be written as the product of two nonempty WatsonCrickpalindromes equals the set of primitive WatsonCrickpalindromes.
In this paper, we extend the notion of palindromes in conjugacy class of a word to WatsonCrick palindromes and WatsonCrick conjugates of a word. The number of palindromes in the conjugacy class of a word is studied in [7]. We investigate the set of conjugates of a word. We study the number of WatsonCrick palindromes in a conjugacy class. We then consider the number of palindromes and WatsonCrick palindromes in the WatsonCrick conjugacy set of a given word.
The paper is organised as follows. In Section 3, we study the properties of the set of conjugates of a word. We first show that for a given word , the maximum number of elements in the conjugacy of a word is , and we also characterize the words that attain this maximum number. In Section 4, we study the distribution of palindromes in the conjugacy class of a word. We show that the conjugacy class of a word can contain at most two distinct palindromes. In Section 5, we study the number of palindromes in the set of conjugates of the word. We find the structure of the words which have at least one palindrome among its conjugates. Lastly, in Section 5, we analyse the number of palindromes in the set of conjugates of a word. We find the structure of the words which have at least one palindrome among its conjugates. We end the paper with some concluding remarks.
2. Basic definitions and notations
An alphabet is a finite nonempty set of symbols. A word over is defined to be a finite sequence of symbols from . denotes the set of all words over including the empty word and . The length of a word is the number of symbols in a word and is denoted by . The reversal of is defined to be a string where . denotes the set of all subwords of of length . A word is said to be a palindrome if .
A word is called primitive if implies and . Let denote the set of all primitive words. For every word , there exists a unique word , called the primitive root of , such that and for some . A function is said to be an antimorphism if . The function is called an involution if is an identity on .
A word is said to be a factor of if where . If , then is a prefix of and if , then is a suffix of . A word is a conjugate of if there exists such that . The set of all conjugates of , denoted as , is the conjugacy class of . A word is a conjugate of another word if for some . The set of all conjugates of is denoted by . For an antimorphic involution , a finite word is called a palindrome if . Consider and an antimorphic involution such that and . Then, the word is a palindrome but not a palindrome. For all other concepts in formal language theory and combinatorics on words, the reader is referred to [8, 11].
Throughout the paper, we take to be an antimorphic involution over .
3. Conjugacy and thetaConjugacy of a word.
In this section, we study the conjugacy class and the conjugacy set for a word . We show some general properties of the set . We also characterize words for which which is the maximum number of of conjugates that a word of length can have.
We recall the following result from [9] for conjugates of a word.
Proposition 3.1.
Let be a conjugate of . Then, for an antimorphic involution , there exists such that either and or .
Thus, we can deduce that for a word ,
Also, Proposition 3.1 implies that the maximum number of elements in is . It is also clear that if is a palindrome, then the maximum number of elements in is . We illustrate the concept of conjugacy of a word with the help of an example and show that the number of elements in the conjugacy of a word may or may not reach the maximum.
Example 3.2.
Consider and such that , .

If , then and . Note that is a primitive word that is neither a palindrome nor a palindrome.

If , then and . Note that is a primitive word that is neither a palindrome nor a palindrome.

If , then and . Note that is a palindrome.

If , then and . Note that is a palindrome.

If , then and . Note that is a palindrome.

If , then and . Note that is a palindrome.

If , then and . Note that is not a primitive word but .
It is well known that the maximum number of elements in a conjugacy class of a word is and it is attained if is primitive. This is not true in general for conjugacy of . It is clear from Example 3.2 that there are primitive words with the maximum number of elements in the set to be less than , equal to and equal to . It is also clear from Example 3.2 that the maximum number of elements in the set , i.e., , can be attained by both primitive as well as a nonprimitive word.
We now characterize words with exactly elements in . We first recall some general results from [12].
Lemma 3.3.
Let .

If then, and are powers of a common primitive word.

If then, for , and ,, , .
We have the following result.
Proposition 3.4.
Let . Then, iff is not of the form where , , and are palindromes.
Proof.
Let . We prove that iff where , , and and are palindromes.
Let , then at least two conjugates of are equal. Let and be the two conjugates of that are equal where for . Without loss of generality, let us assume that . Then, , and for some .
Now,
Then by Lemma 3.3, , where , such that and are palindromes.
Hence, and are palindromes.
Conversely, let where , , and are palindromes. Now, and . Consider
Therefore, . ∎
The conjugacy operation on words is an equivalence relation. However, the conjugacy on words is not an equivalence relation. Note that from Example 3.2, it is clear that is a conjugate of , but is not a conjugate of . Thus, conjugacy on words is not a
symmetric relation, and hence, not an
equivalence relation.
We recall the following from [14].
Lemma 3.5.
Let for a primitive word over . Then, the conjugacy class of contains exactly words.
We show that Lemma 3.5 do not hold for conjugacy. Infact we show that for any word , the number of conjugates in may not be equal to that of the number of conjugates in the word . We illustrate with the help of an example.
Example 3.6.
Let , and such that . Then,

;

;

We show that the number of conjugates of a word are greater than the number of conjugates of a word for and and . We have the following result.
Lemma 3.7.
Let . If , then .
Proof.
Let such that . Let such that . Now where . Then, . So for each element in , there exist an element in such that is a prefix of . Let . Then . So there exist an element in where . Now if then . Hence, .
Now . Note that the words and have as their prefix. If , we get such that for all .
Thus, we get for all , so , i.e., which is a contradiction.
Therefore, there exist at least two distinct elements and in whose prefix is . Thus .
∎
We deduce an immediate result.
Corollary 3.8.
Let . If , then for .
We recall the following from [10].
Proposition 3.9.
If and is an antimorphic involution, then , where and are palindromes, where .
Lemma 3.10.
Let then iff such that for .
Proof.
Let , then is a palindrome. So, is of the form where is a palindrome. Let where . As , we have, . Then, . Take , then . By Proposition 3.9, we have and where . Then and as is a palindrome, and . Hence, . Converse is straightforward. ∎
Theorem 3.11.
Let such that for such that , then for .
4. Theta palindromes in the conjugacy class of a word
The distribution of palindromes in the conjugacy class of a word was studied in [7]. The authors proved that there are at most two distinct palindromes in the conjugacy class of a given word. In this section, we show an analogous result pertaining to the distribution of palindromes and prove that the conjugacy class of any given word also contains at most two palindromes. We also provide the structure of such words. We begin by recalling the following from [7].
Lemma 4.1.
If the conjugacy class of a word contains two distinct palindromes, say and , then there exists a word and a number such that is primitive, , and .
In this section, we study the distribution of palindromes in the conjugacy class of a word.
We first observe the following.
Proposition 4.2.
If is a palindrome, then is a palindrome for .
We recall the following from [7].
Lemma 4.3.
We deduce the following.
Lemma 4.4.
Suppose and for a primitive word . Then, is odd and = for some .
Proof.
If is even, then . Hence, , contradicting the conditions of the lemma. So is odd and then is even. Let , where . We see that is a prefix of and is a suffix of . Hence, , as required. ∎
Lemma 4.5.
If the conjugacy class of a word contains two distinct palindromes, say and , then there exists a word and a number such that is primitive, , and .
Proof.
We use induction on .
For , if there are two distinct palindromes, then they must be of the form and where and , i.e., is primitive.
For the inductive step, assume without loss of generality.
If , then . By Lemma 4.4, we get for a primitive
word and .
Now let . Then is a prefix and suffix of .
for . This implies by Lemma 3.3, we obtain , and hence, ,
for , and .
Looking at the central factor of the palindromes
we see that and are also palindromes. If , then is a palindrome, implying , which is a contradiction as and are distinct. If , then by Lemma 3.3, both and are powers of some primitive word and by Proposition 4.2, , and are palindromes, which again implie which is a contradiction. Thus, with and by inductive hypothesis we get , for some primitive word . Then, we have
(1) 
Note that, if where , then Eq 1 becomes
Then by the comparing suffix, which is a contradiction, since all conjugates of are distinct by Lemma 3.5. The argument for the case when is similar. If , then Eq 1 becomes
and by comparing the suffix, we get which is a contradiction as is primitive. Thus, for some . Then we can easily compute , and by using (we know the value of ) to get . Hence, the proof. ∎
We give examples of words that have zero, one and two palindromes each in their conjugacy class.
Example 4.6.
Let , and such that and . Then

The word has zero palindromes in its conjugacy class.

The word has exactly one palindrome in its conjugacy class.

The word has two exactly two palindromes and in its conjugacy class.
We know from Example 4.6 that there exists words that contain exactly, zero, one or two palindromes in their conjugacy class. However, in the following result, we show that a conjugacy class of any word contains at most two distinct palindromes and we also find the structure of words that contain exactly two palindromes in their conjugacy class.
Theorem 4.7.
The conjugacy class of a word contains at most two palindromes. It has exactly two palindromes iff it contains a word of the form , where is primitive and . Note that such a word has even length.
Proof.
It is clear from Example 1 that a word can have upto palindromes. WLOG, we may assume that is primitive. Suppose there are two palindromic conjugates of a word , then by Lemma 4.5, they are of the form and where is primitive. We show that the conjugacy class of contains no other palindromes.
Consider the conjugacy class of . Let and be such that and is a palindrome. If , say, , then we apply the same argument in Lemma 4.5 and obtain for some and . But this is impossible, because is primitive. Hence, , and . Thus, the conjugacy class contains exactly two palindromes and the words are of the structure described in Lemma 4.5. ∎
5. Palindromes in the set of all Thetaconjugates of a word
The concept of conjugacy of a word was introduced in [9] to incorporate the notion of WatsonCrick involution map to the conjugacy relation. In this section, we count the number of distinct palindromes in , . We find the structure of words which have at least one palindrome in the set of their conjugates. We also show that if a word is a palindrome, then there can be at most two palindromes among its conjugates.
It is clear from Example 3.2, that the words , and have zero, one and two palindromes, respectively, in their respective conjugacy classes. We now find the structure of words with at least one palindrome among their conjugates.
Theorem 5.1.
Given , contains at least one palindrome iff or where and are palindromes.
Proof.
We first show the converse. Let , for a palindrome such that . Then, is a palindrome. Similarly, for where and is a palindrome, is a palindrome. Therefore, when or for palindromes and , contains at least one palindrome. Now, let there exist at least one palindrome in . Let where such that is a palindrome in . Then, we have the following cases:

Let and let such that . Now, . Since, is a palindrome and , we get and is a palindrome. Then,
Since is a palindrome, is a palindrome.

If then, , i.e., , and hence, .

Let and let such that . Since, we obtain, and a palindrome. Then, .
Hence, in all cases either or where and are palindromes. ∎
It is evident from the definition of conjugacy of a word that, contains both and . Hence, if is a palindrome, then contains at least two palindromes and . In the following, we show that for a palindrome , and are the only palindromes in the set of all conjugates of .
Theorem 5.2.
For a palindrome , the number of palindromes in is atmost two and is exactly two if .
Proof.
Let be a palindrome. Then is also a palindrome. Suppose there exists a where such that is a palindrome, then . We have the following cases.

If , then there exists a such that . We then have, i.e., . Now, . As is a palindrome, , i.e., . Then, .

If , then and since is a palindrome, we have, which implies and . Thus, and .

If , then is a prefix of and is a suffix of since both and are palindromes. If and since is a prefix of and is a suffix of , then with such that and . Thus, , and hence, . If , then for some . Since , and are palindromes, we get
(2) (3) Equations 2 and 3 gives, and , respectively. Since is a palindrome, and is a palindrome. Now
Then, we get,
Then by Lemma 3.3, , and where , and . Now , i.e., . So and are palindromes and hence,
Then using Equation 2, we get,
So, .
Hence, in all the cases, we are done. ∎
Consider the word where is a palindrome but not a palindrome. Then, are palindromes. Moreover the word , where is a palindrome but not a palindrome, has at least two palindromes. It is evident that there exists a nonpalindrome such that contains more than one palindrome.
6. Theta palindromes in the Thetaconjugacy set of a word
In this section, for a given word , we study the number of palindromes in the set . We find the structure of words which have at least one palindrome in the set of their conjugates. We also show that if a word is a palindrome, then there can be at most one palindrome among its conjugates.
We first give examples of words that have zero and one palindrome in their .
Example 6.1.
Let , and consider such that and . Then

Thus, it has zero palindromes .

The word has exactly one palindrome .
We now find the structure of words with at least one palindrome among their conjugates.
Theorem 6.2.
Given , contains at least one palindrome iff or where and is a palindrome.
Proof.
Let there exist at least one palindrome in and let where such that is a palindrome in . Then, we have the following cases:

Let . Let such that . Now, . Since is a palindrome and , we get and is a palindrome. Then, and is a palindrome.

Let . Since is a palindrome and , . Then,

Let . Let such that . Now, . Since is a palindrome and , and is a palindrome. Then, where is a palindrome.
Hence, in all the cases either or where and is a palindrome.
Conversely, let be a palindrome. If for some then,
Comments
There are no comments yet.