2010395-404Nancy, France 395

Lance Fortnow

Jack H. Lutz

Elvira Mayordomo

# Inseparability and Strong Hypotheses for Disjoint NP Pairs

L. Fortnow  Northwestern University, EECS Department, Evanston, Illinois, USA.
<EMAIL_ADDRESS>,  J. H. Lutz  Department of Computer Science,
Iowa State University, Ames, IA 50011 USA<EMAIL_ADDRESS>and  E.
Mayordomo  Departamento de Informática e Ingeniería de Sistemas, Instituto de
Investigación en Ingeniería de Aragón, María de Luna 1, Universidad de
Zaragoza, 50018 Zaragoza, SPAIN.  elvira at unizar.es

###### Abstract.

This paper investigates the existence of inseparable disjoint pairs of NP
languages and related strong hypotheses in computational complexity. Our main
theorem says that, if NP does not have measure 0 in EXP, then there exist
disjoint pairs of NP languages that are P-inseparable, in fact TIME(2(n
k))-inseparable. We also relate these conditions to strong hypotheses
concerning randomness and genericity of disjoint pairs.

###### Key words and phrases:

Computational Complexity, Disjoint NP-pairs, Resource-Bounded Measure,
Genericity

###### 1991 Mathematics Subject Classification:

F.1.3

Thanks: Fortnow’s research supported in part by NSF grants CCF-0829754 and
DMS-0652521. Lutz’s research supported in part by National Science Foundation
Grants 0344187, 0652569, and 0728806. Mayordomo’s research supported in part
by Spanish Government MICINN Project TIN2008-06582-C03-02.

##  1\. Introduction

The main objective of complexity theory is to assess the intrinsic
difficulties of naturally arising computational problems. It is often the case
that a problem of interest can be formulated as a decision problem, or else
associated with a decision problem of the same complexity, so much of
complexity theory is focused on decision problems. Nevertheless, other types
of problems also require investigation.

This paper concerns promise problems, a natural generalization of decision
problems introduced by Even, Selman, and Yacobi [7]. A decision problem can be
formulated as a set $A\subseteq\\{0,1\\}^{*}$, where a solution of this
problem is an algorithm, circuit, or other device that decides $A$, i.e.,
tells whether or not an arbitrary input $x\in\\{0,1\\}^{*}$ is an element of
$A$. In contrast, a promise problem is formulated as an ordered pair $(A,B)$
of disjoint sets $A,B\subseteq\\{0,1\\}^{*}$, where a solution is an algorithm
or other device that decides any set $S\subseteq\\{0,1\\}^{*}$ such that
$A\subseteq S$ and $B\cap S=\emptyset$. Such a set $S$ is called a separator
of the disjoint pair $(A,B)$. Intuitively, if we are promised that every input
will be an element of $A\cup B$, then a separator of $(A,B)$ enables us to
distinguish inputs in $A$ from inputs in $B$. Since each decision problem $A$
is clearly equivalent to the promise problem $(A,A^{c})$, where
$A^{c}=\\{0,1\\}^{*}-A$ is the complement of $A$, promise problems are,
indeed, a generalization of decision problems.

A disjoint NP pair is a promise problem $(A,B)$ in which
$A,B\in{\mathrm{NP}}$. Disjoint NP pairs were first investigated by Selman and
others in connection with public key cryptosystems [7, 15, 26, 17]. They were
later investigated by Razborov [25] as a setting in which to prove the
independence of complexity-theoretic conjectures from theories of bounded
arithmetic. In this same paper, Razborov established a fundamental connection
between disjoint NP pairs and propositional proof systems. Propositional proof
systems had been used by Cook and Reckhow [6] to characterize the NP versus
co-NP problem. Razborov [25] showed that each propositional proof system has
associated with it a canonical disjoint NP pair and that important questions
about propositional proof systems are thereby closely related to natural
questions about disjoint NP pairs. This connection with propositional proof
systems has motivated more recent work on disjoint NP pairs by Glaßer, Selman,
Sengupta, and Zhang [10, 9, 12, 13]. It is now known that the degree structure
of propositional proof systems under the natural notion of proof simulation is
identical to the degree structure of disjoint NP pairs under reducibility of
separators [12]. Much of this recent work is surveyed in [11]. Goldreich [14]
gives a recent survey of promise problems in general.

Our specific interest in this paper is the existence of disjoint NP pairs that
are P-inseparable, or even ${\mathrm{TIME}(2^{n^{k}})}$-inseparable. As the
terminology suggests, if ${\mathcal{C}}$ is a class of decision problems, then
a disjoint pair is ${\mathcal{C}}$-inseparable if it has no separator in
${\mathcal{C}}$. The existence of P-inseparable disjoint NP pairs is a strong
hypothesis in the sense that (1) it clearly implies
${\mathrm{P}}\neq{\mathrm{NP}}$, and (2) the converse implication is not known
(and fails relative to some oracles [17]). It is clear that
${\mathrm{P}}\neq{\mathrm{NP}}\cap\mathrm{co}{\mathrm{NP}}$ implies the
existence of P-inseparable disjoint NP pairs, and Grollmann and Selman [15]
proved that ${\mathrm{P}}\neq\mathrm{UP}$ also implies the existence of
P-inseparable disjoint NP pairs.

The hypothesis that NP is a non-measure 0 subset of EXP, written
$\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$, is a strong hypothesis in the above
sense. This hypothesis has been shown to have many consequences not known to
follow from more traditional hypotheses such as
${\mathrm{P}}\neq{\mathrm{NP}}$ or the separation of the polynomial-time
hierarchy into infinitely many levels. Each of these known consequences has
resolved some pre-existing complexity-theoretic question in the way that
agreed with the conjecture of most experts. This explanatory power of the
$\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$ hypothesis is discussed in the early
survey papers [23, 2, 24] and is further substantiated by more recent papers
listed at [16] (and too numerous to discuss here). In several instances, the
discovery that $\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$ implies some plausible
conclusion has led to subsequent work deriving the same conclusion from some
weaker hypothesis, thereby further illuminating the relationships among strong
hypotheses.

Our main theorem states that, if NP does not have measure zero in EXP, then,
for every positive integer $k$, there exist disjoint NP pairs that are
${\mathrm{TIME}(2^{n^{k}})}$-inseparable. Such pairs are a fortiori
P-inseparable, but the conclusion of our main theorem actually gives
exponential lower bounds on the inseparability of some disjoint NP pairs.
These are the lower bounds that most experts conjecture to be true, even
though an unconditional proof of such bounds may be long in coming.

The proof of our main theorem combines known closure properties of NP with the
randomness that the $\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$ hypothesis implies
must be present in NP to give an explicit construction of a disjoint NP pair
that is ${\mathrm{TIME}(2^{n^{k}})}$-inseparable. (Technically, this is an
overstatement. The last step of the “construction” is the removal of a finite
set whose existence we prove, but which we do not construct.) The details are
perhaps involved, but we preface the proof with an intuitive motivation for
the approach.

We also investigate the relationships between the two strong hypotheses in our
main theorem (i.e., its hypothesis and its conclusion) and strong hypotheses
involving the existence of disjoint NP pairs with randomness and genericity
properties. Roughly speaking (i.e., omitting quantitative parameters), we show
that the existence of disjoint NP pairs that are random implies both the
$\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$ hypothesis and the existence of
disjoint NP pairs that are generic in the sense of Ambos-Spies, Fleischhack,
and Huwig [1]. We also show that the existence of such generic pairs implies
the existence of disjoint NP pairs that are
${\mathrm{TIME}(2^{n^{k}})}$-inseparable. Taken together, these results give
the four implications at the top of Figure 1. (The four implications at the
bottom are well known.) We prove that three of these implications cannot be
reversed by relativizable techniques, and we conjecture that this also holds
for the remaining implication.

##  2\. Preliminaries

We write $\mathbb{N}$ for the set of nonnegative integers and $\mathbb{Z}^{+}$
for the set of (strictly) positive integers. The Boolean value of an assertion
$\phi$ is $[\\![\phi]\\!]=$ if $\phi$ then 1 else 0. All logarithms here are
base-2.

We write $\lambda$ for the empty string, $|w|$ for the length of a string $w$,
and $s_{0},s_{1},s_{2},\ldots$ for the standard enumeration of
$\\{0,1\\}^{*}$. The index of a string $x$ is the value
$\mathrm{ind}(x)\in\mathbb{N}$ such that $s_{\mathrm{ind}(x)}=x$. We write
$\mathrm{next}(x)$ for the string following $x$ in the standard enumeration,
i.e., $\mathrm{next}(s_{n})=s_{n+1}$. More generally, for $k\in\mathbb{N}$, we
write $\mathrm{next}^{k}$ for the $k$-fold composition of next with itself, so
that $\mathrm{next}^{k}(s_{n})=s_{n+k}$.

A Boolean function is a function $f:\left\\{0,1\right\\}^{m}\to\\{0,1\\}$ for
some $m\in\mathbb{N}$. The support of such a function $f$ is
$\mathrm{supp}(f)=\left\\{{x\in\left\\{0,1\right\\}^{m}}\>\Big{|}\>{f(x)=1}\right\\}$.

We write $w[i]$ for the $i^{\mathrm{th}}$ symbol in a string $w$ and $w[i..j]$
for the string consisting of the $i^{\mathrm{th}}$ through $j^{\mathrm{th}}$
symbols. The leftmost symbol of $w$ is $w[0]$, so that $w=w[0..|w|-1]$. For
(infinite) sequences $S\in\Sigma^{\infty}$, the notations $S[i]$ and $S[i..j]$
are defined similarly. A string $w\in\Sigma^{*}$ is a prefix of a string or
sequence $x\in\Sigma^{*}\cup\Sigma^{\infty}$, and we write $w\sqsubseteq x$,
if there is a string or sequence $y\in\Sigma^{*}\cup\Sigma^{\infty}$ such that
$wy=x$. A language, or decision problem, is a set $A\subseteq\\{0,1\\}^{*}$.
We identify each language $A$ with the sequence $A\in\\{0,1\\}^{\infty}$
defined by $A[n]=[\\![s_{n}\in A]\\!]$ for all $n\in\mathbb{N}$. If $A$ is a
language, then expressions like $\lim_{w\to A}f(w)$ refer to prefixes
$w\sqsubseteq A$, e.g., $\lim_{w\to A}f(w)=\lim_{n\to\infty}f(A[0..n-1])$.

A martingale is a function $d:\\{0,1\\}^{*}\to[0,\infty)$ satisfying

$d(w)=\frac{d(w0)+d(w1)}{2}$ (2.1)

for all $w\in\\{0,1\\}^{*}$. Intuitively, $d$ is a strategy for betting on the
successive bits of a sequence $S\in\\{0,1\\}^{\infty}$: The quantity $d(w)$ is
the amount of money that the gambler using this strategy has after $|w|$ bets
if $w\sqsubseteq S$. Condition (2.1) says that the payoffs are fair.

A martingale $d$ succeeds on a language $A\subseteq\\{0,1\\}^{*}$, and we
write $A\in S^{\infty}[d]$, if
$\limsup_{w\to A}d(w)=\infty$. If $t:\mathbb{N}\to\mathbb{N}$, then a
martingale $d$ is (exactly) $t(n)$-computable if its values are rational and
there is an algorithm that computes each $d(w)$ in $t(|w|)$ time. A martingale
is p-computable if it is $n^{k}$-computable for some $k\in\mathbb{N}$, and it
is ${{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}$-computable if it is
$2^{(\log n)^{k}}$-computable for some $k\in\mathbb{N}$.

######  Definition 2.1.

[22] Let $X$ be a set of languages, and let $R$ be a language.

  1. (1)

$X$ has p-measure 0, and we write $\mu_{\mathrm{p}}(X)=0$, if there is a
p-computable martingale $d$ such that $X\subseteq S^{\infty}[d]$. The
condition $\mu_{{{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}}(X)=0$ is
defined analogously.

  2. (2)

$X$ has measure 0 in EXP, and we write $\mu(X\mid{\rm EXP})=0$, if
$\mu_{{{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}}(X\cap{\rm EXP})=0$.

  3. (3)

$R$ is p-random if $\mu_{\mathrm{p}}(\\{R\\})\neq 0$, i.e., if there is no
p-computable martingale that succeeds on $R$. Similarly, $R$ is $t(n)$-random
if no $t(n)$\- computable martingale succeeds on $R$.

It is well known that these definitions impose a nontrivial measure structure
on EXP [22]. For example, $\mu({\rm EXP}\mid{\rm EXP})\neq 0$.

We use the following fact in our arguments.

######  Lemma 2.2.

[3, 18] The following five conditions are equivalent.

  1. (1)

$\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$.

  2. (2)

$\mu_{\mathrm{p}}({\mathrm{NP}})\neq 0$.

  3. (3)

$\mu_{{{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}}({\mathrm{NP}})\neq 0$.

  4. (4)

There exists a p-random language $R\in{\mathrm{NP}}$.

  5. (5)

For every $k\geq 2$, there exists an $2^{\log n^{k}}$-random language
$R\in{\mathrm{NP}}$.

Finally, we note that $\mu({\mathrm{P}}\mid{\rm EXP})=0$ [22], so
$\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$ implies
${\mathrm{P}}\neq{\mathrm{NP}}$.

##  3\. Inseparable Disjoint NP Pairs and the Measure of NP

This section presents our main theorem, which says that, if NP does not have
measure 0 in EXP, then there are disjoint NP pairs that are P-inseparable. In
fact, for each $k\in\mathbb{N}$, there is a disjoint NP pair that is
${\mathrm{TIME}(2^{n^{k}})}$-inseparable.

It is convenient for our arguments to use a slight variant of the separability
notion.

######  Definition 3.1.

Let $(A,B)$ be a pair of (not necessarily disjoint) languages, and let
${\mathcal{C}}$ be a class of languages.

  1. (1)

A language $S\subseteq\\{0,1\\}^{*}$ almost separates $(A,B)$ if there is a
finite set $D\subseteq\\{0,1\\}^{*}$ such that $S$ separates $(A-D,B-D)$.

  2. (2)

We say that $(A,B)$ is ${\mathcal{C}}$-almost separable  if there is a
language $S\in{\mathcal{C}}$ that almost separates $(A,B)$.

If a pair $(A,B)$ is not ${\mathcal{C}}$-almost separable, then $(A-D,B-D)$ is
${\mathcal{C}}$-inseparable for every finite set $D$.

Before proving our main theorem, we sketch the intuitive idea of the proof. We
want to construct a disjoint NP pair $(A,B)$ that is P-inseparable. Our
hypothesis, that NP does not have measure 0 in EXP, implies that NP contains a
language $R$ that is p-random. Since we are being intuitive, we ignore the
subtleties of p-randomness and regard $R$ as a sequence of independent, fair
coin tosses (with the $n^{\mathrm{th}}$ toss heads iff $s_{n}\in R$) that just
happens to be in NP. If we use these coins to randomly put strings in $A$ or
$B$ but not both, we can count on the randomness to thwart any would-be
separator in P.

The challenge here is that, if we are to deduce $A,B\in{\mathrm{NP}}$ from
$R\in{\mathrm{NP}}$, we must make the conditions “$s_{n}\in A$” and “$s_{n}\in
B$” depend on the coin tosses in a monotone way; i.e., adding a string to $R$
must not move a string out of $A$ or out of $B$.

This monotonicity restriction might at first seem to prevent us from ensuring
that $A$ and $B$ are disjoint. However, this is not the case. Suppose that we
decide membership of the $n^{\mathrm{th}}$ string $s_{n}$ in $A$ and $B$ in
the following manner. We toss $2\log n$ independent coins. If the first $\log
n$ tosses all come up heads, we put $s_{n}$ in $A$. If the second $\log n$
tosses all come up heads, we put $s_{n}$ in $B$. If our coin tosses are taken
from $R$, which is in NP, then $A$ and $B$ will be in NP. Each string $s_{n}$
will be in $A$ with probability $\frac{1}{n}$, in $B$ with probability
$\frac{1}{n}$, and in $A\cap B$ with probability $\frac{1}{n^{2}}$. Since
$\sum_{n=1}^{\infty}\frac{1}{n}$ diverges and
$\sum_{n=1}^{\infty}\frac{1}{n^{2}}$ converges, the first and second Borel-
Cantelli lemmas tell us that $A$ and $B$ are infinite and $A\cap B$ is finite.
Since $A\cap B$ is finite, we can subtract it from $A$ and $B$, leaving two
disjoint NP languages that are, by the randomness of the construction,
P-inseparable.

What prevents this intuitive argument from being a proof sketch is the fact
that the language $R$ is not truly random, but only p-random. The proof that
$A\cap B$ is finite thus becomes problematic. There is a resource-bounded
extension of the first Borel-Cantelli lemma [22] that works for p-random
sequences, but this extension requires the relevant sum of probabilities to be
p-convergent, i.e., to converge much more quickly than
$\sum_{n=1}^{\infty}\frac{1}{n^{2}}$.

Fortunately, in this particular instance, we can achieve our objective without
p-convergence or the (classical or resource-bounded) Borel-Cantelli lemmas. We
do this by modifying the above construction. Instead of putting the
$n^{\mathrm{th}}$ string into each language with probability $\frac{1}{n}$, we
put each string $x$ into each of $A$ and $B$ with probability $2^{-|x|}$ so
that $x$ is in $A\cap B$ with probability $2^{-2|x|}$. By the Cauchy
condensation test, the relevant series have the same convergence behavior as
those in our intuitive argument, but we can now replace slow approximations of
tails of $\sum_{n=1}^{\infty}\frac{1}{n^{2}}$ with fast and exact computations
of geometric series.

We now turn to the details.

######  Construction 1.

  1. (1)

Define the functions $u,v:\\{0,1\\}^{*}\to\\{0,1\\}^{*}$ by the recursion

$\begin{array}[]{l}u(\lambda)=\lambda,\\\ v(x)=\mathrm{next}^{|x|}(u(x)),\\\
u(\mathrm{next}(x)=\mathrm{next}^{|x|}(v(x)).\end{array}$

  2. (2)

For each $x\in\\{0,1\\}^{*}$, define the intervals

$I_{x}=[u(x),v(x)),\ J_{x}=[v(x),u(next(x))).$

  3. (3)

For each $R\subseteq\\{0,1\\}^{*}$, define the languages

$\begin{array}[]{l}A^{+}(R)=\left\\{{x}\>\Big{|}\>{I_{x}\subseteq
R}\right\\},\ B^{+}(R)=\left\\{{x}\>\Big{|}\>{J_{x}\subseteq R}\right\\},\\\
A(R)=A^{+}(R)-B^{+}(R),\ B(R)=B^{+}(R)-A^{+}(R).\end{array}$

Note that each $|I_{x}|=|J_{x}|=|x|$. Also,
$I_{\lambda}=J_{\lambda}=\emptyset$ (so $\lambda\in A^{+}(R)\cap B^{+}(R)$),
and

$I_{0}<J_{0}<I_{1}<J_{1}<I_{00}<J_{00}<I_{01}<\ldots,$

with these intervals covering all of $\\{0,1\\}^{*}$.

A routine witness argument gives the following.

  1. (1)

If $R\in{\mathrm{NP}}$, then $A^{+}(R),B^{+}(R)\in{\mathrm{NP}}$.

  2. (2)

If $R\in{\mathrm{NP}}$ and $|A^{+}(R)\cap B^{+}(R)|<\infty$, then
$(A(R),B(R))$ is a disjoint NP pair.

We now prove two lemmas about Construction 1.

######  Lemma 3.2.

Let $k\in\mathbb{N}$. If $R\subseteq\\{0,1\\}^{*}$ is $2^{(\log n)^{k+2}}$\-
random, then $(A^{+}(R),B^{+}(R))$ is not ${\mathrm{TIME}(2^{n^{k}})}$-almost
separable.

######  Lemma 3.3.

If $R\subseteq\\{0,1\\}^{*}$ is p-random, then $|A^{+}(R)\cap
B^{+}(R)|<\infty$.

We now have what we need to prove our main result.

######  Theorem 3.4.

(main theorem) If NP does not have measure 0 in EXP, then, for every
$k\in\mathbb{Z}^{+}$, there is a disjoint NP pair that is
${\mathrm{TIME}(2^{n^{k}})}$-inseparable, hence certainly P-inseparable.

######  Proof 3.5.

Assume that $\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$, and let $k\in\mathbb{N}$.
Then, by Lemma 2.2, there is a $2^{(\log n)^{k+2}}$-random language
$R\in{\mathrm{NP}}$. By Lemma 3.2, the pair $(A^{+}(R),B^{+}(R))$ is not
${\mathrm{TIME}(2^{n^{k}})}$-almost separable. Since $R$ is certainly
p-random, Lemma 3.3 tells us that $|A^{+}(R)\cap B^{+}(R)|<\infty$. It follows
by Observation 3 that $(A(R),B(R))$ is a disjoint NP pair, and it follows by
Observation 3 that $(A(R),B(R))$ is ${\mathrm{TIME}(2^{n^{k}})}$-inseparable.

##  4\. Genericity and Measure of Disjoint NP Pairs

In this section we introduce the natural notions of resource-bounded measure
and genericity for disjoint pairs and relate them to the existence of
P-inseparable pairs in NP. We compare the different strength hypothesis on the
measure and genericity of NP and disjNP establishing all the relations in
Figure 1.

Notation. Each disjoint pair $(A,B)$ will be coded as an infinite sequence
$T\in\\{-1,0,1\\}^{\infty}$ defined by

$T[n]=\left\\{\begin{array}[]{ll}1&\mathrm{if}\ s_{n}\in A\\\ -1&\mathrm{if}\
s_{n}\in B\\\ 0&\mathrm{if}\ s_{n}\not\in A\cup B\end{array}\right.$

We identify each disjoint pair with the corresponding sequence.

Resource-bounded genericity for disjoint pairs is the natural extension of the
concept introduced for languages by Ambos-Spies, Fleischhack and Huwig [1].

######  Definition 4.1.

A condition $C$ is a set $C\subseteq\\{-1,0,1\\}^{*}$. A $t(n)$-condition is a
condition $C\in\mathrm{DTIME}(t(n))$. A condition $C$ is dense along a pair
$(A,B)$ if there are infinitely many $n\in\mathbb{N}$ such that
$(A,B)[0..n-1]i\in C$ for some $i\in\\{-1,0,1\\}$. A pair $(A,B)$ meets a
condition $C$ if $(A,B)[0..n-1]\in C$ for some $n$. A pair $(A,B)$ is
$t(n)$-generic if $(A,B)$ meets every $t(n)$-condition that is dense along
$(A,B)$.

We first prove that generic pairs are inseparable.

######  Theorem 4.2.

Every $t(\log n)$-generic disjoint pair is $\mathrm{TIME}(t(n))$-inseparable.

We can now relate genericity in disjNP and inseparable pairs as follows.

######  Corollary 4.3.

If disjNP contains a $2^{(\log n)^{k}}$-generic pair for every
$k\in\mathbb{N}$, then disjNP contains a
${\mathrm{TIME}(2^{n^{k}})}$-inseparable pair for every $k\in\mathbb{N}$.

Resource-bounded measure on classes of disjoint pairs is the natural extension
of the concept introduced for languages by Lutz [22], and is defined by using
martingales on a three-symbol alphabet as follows.

######  Definition 4.4.

  1. (1)

A pair martingale is a function $d:\\{-1,0,1\\}^{*}\to[0,\infty)$ such that
for every $w\in\\{-1,0,1\\}^{*}$

$d(w)=\frac{1}{4}d(w0)+\frac{3}{8}d(w1)+\frac{3}{8}d(w(-1)).$

  2. (2)

A pair martingale $d$ succeeds on a pair $(A,B)$ if
$\limsup_{w\to(A,B)}d(w)=\infty$.

  3. (3)

A pair martingale $d$ succeeds on a class of pairs
$X\subseteq\\{-1,0,1\\}^{\infty}$ if it succeeds on each $(A,B)\in X$.

Our intuitive rationale for the coefficients in part 1 of this definition is
the following. We toss one fair coin to decide whether $s_{|w|}\in A$ and
another to decide whether $s_{|w|}\in B$. If both coins come up heads, we toss
a third coin to break the tie. The reader may feel that some other
coefficients, such as $\frac{1}{3},\frac{1}{3},\frac{1}{3}$ are more natural
here. Fortunately, a routine extension of the main theorem of [5] shows that
the value of $\mu(\mathrm{disjNP}\mid\mathrm{disjEXP})$ will be the same for
any choice of three positive coefficients summing to 1.

When restricting martingales to those computable within a certain resource
bound, we obtain a resource-bounded measure that is useful within a complexity
class. Here we are interested in the class of disjoint EXP pairs, disjEXP.

######  Definition 4.5.

  1. (1)

Let ${{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}$ be the class of functions
that can be computed in time $2^{(\log n)^{O(1)}}$.

  2. (2)

A class of pairs $X\subseteq\\{-1,0,1\\}^{\infty}$ has
${{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}$-measure 0 if there is a
martingale $d\in{{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}$ that succeeds
on $X$.

  3. (3)

$X\subseteq\\{-1,0,1\\}^{\infty}$ has
${{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}$-measure 1 if $X^{c}$ has
${{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}$-measure 0.

  4. (4)

A class of pairs $X\subseteq\\{-1,0,1\\}^{\infty}$ has measure 0 in disjEXP,
denoted $\mu(X\mid\mathrm{disjEXP})=0$, if $X\cap\mathrm{disjEXP}$ has
${{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}$-measure 0.

  5. (5)

$X\subseteq\\{-1,0,1\\}^{\infty}$ has measure 1 in disjEXP if $X^{c}$ has
measure 0 in disjEXP.

It is easy to verify that
${{\mathrm{p}}_{\thinspace\negthinspace{}_{2}}}$-measure is nontrivial on
disjEXP (as proven for languages in [22]).

In the following we consider the hypothesis that disjNP does not have measure
0 in disjEXP (written $\mu(\mathrm{disjNP}\mid\mathrm{disjEXP})\neq 0$). We
start by proving that this hypothesis is at least as strong as the well
studied $\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$ hypothesis.

######  Theorem 4.6.

If $\mu(\mathrm{disjNP}\mid\mathrm{disjEXP})\neq 0$ then
$\mu({\mathrm{NP}}\mid{\rm EXP})\neq 0$.

We finish by relating measure and genericity for disjoint pairs.

######  Theorem 4.7.

If $\mu(\mathrm{disjNP}\mid\mathrm{disjEXP})\neq 0$, then disjNP contains a
$2^{(\log n)^{k}}$-generic pair for every $k\in\mathbb{N}$.

Figure 1. Relations among some strong hypotheses.

##  5\. Oracle Results

All the techniques in this and related papers relativize, that is they hold
when all machines involved have access to the same oracle $A$. In this section
we give relativized worlds where the converses of most of the results in this
paper, as expressed in Figure 1, do not hold. Since the implications trivially
all hold in any relativized world where ${\mathrm{P}}={\mathrm{NP}}$ [4], one
cannot use relativizable techniques to settle these converses.

We’ll work our way from the bottom up of Figure 1.

######  Theorem 5.1 (Homer-Selman [17], Fortnow-Rogers [8]).

There exists oracles $A$ and $B$ such that

  * •

${\mathrm{P}}^{A}\neq{\mathrm{NP}}^{A}$ and $\mathrm{disjNP}^{A}$ does not
contain ${\mathrm{P}}^{A}$-inseparable pairs.

  * •

${\mathrm{P}}^{B}={\mathrm{NP}}^{B}\cap\mathrm{co}{\mathrm{NP}}^{B}=\mathrm{UP}^{B}$
and $\mathrm{disjNP}^{B}$ does contain ${\mathrm{P}}^{B}$-inseparable pairs.

######  Theorem 5.2.

There exists an oracle $C$ such that ${\mathrm{P}}^{C}\neq\mathrm{UP}^{C}$ but
${\mathrm{NP}}^{C}$ is contained in $\mathrm{TIME}^{C}(n^{O(\log n)})$. In
particular this means that relative to $C$, $\mathrm{disjNP}$ contains
${\mathrm{P}}$-inseparable pairs but there is a $k$ (and in fact any real
$k>0$) such that $\mathrm{disjNP}$ has no
$\mathrm{TIME}(2^{n^{k}})$-inseparable pairs.

######  Theorem 5.3.

There exists a relativized world $D$, relative to which for all $k$,
$\mathrm{disjNP}$ contains a $\mathrm{TIME}(2^{n^{k}})$-inseparable pair but
$\mu({\mathrm{NP}}|{\rm EXP})=0$ and $\mathrm{disjNP}$ does not contain a
$2^{(\log n)^{k}}$-generic pair.

######  Theorem 5.4.

There exists an oracle $E$ relative to which for all $k$, $\mathrm{disjNP}$
contains a $2^{(\log n)^{k}}$-generic pair but
$\mu(\mathrm{disjNP}|\mathrm{disjEXP})=0$.

######  Conjecture 5.5.

There exists an oracle $H$ relative to which $\mu({\mathrm{NP}}|{\rm EXP})\neq
0$ but
$\mu(\mathrm{disjNP}|\mathrm{disjEXP})=0$.

Let $K$ be a ${\rm PSPACE}$-compete set, $R$ be a “random” oracle and let

$H=K\oplus R=\\{\langle 0,x\rangle\ |\ x\in K\\}\cup\\{\langle 1,y\rangle\ |\
y\in R\\}.$

Kautz and Miltersen show in [20] that relative to $H$, $\mu({\mathrm{NP}}|{\rm
EXP})\neq 0$. Kahn, Saks and Smyth [19] combined with unpublished work of
Impagliazzo and Rudich show that relative to $H$ there is a polynomial-time
algorithm that solves languages in ${\mathrm{NP}}\cap\mathrm{co}{\mathrm{NP}}$
on average for infinitely-many lengths which would imply
$\mu({\mathrm{NP}}\cap\mathrm{co}{\mathrm{NP}}|{\rm EXP})=0$ relative to $H$.
We conjecture that one can modify this proof to show
$\mu(\mathrm{disjNP}^{H}|\mathrm{disjEXP}^{H})=0$.

## References

  * [1] K. Ambos-Spies, H. Fleischhack, and H. Huwig.  Diagonalizations over polynomial time computable sets.  Theoretical Computer Science, 51:177–204, 1987.
  * [2] K. Ambos-Spies and E. Mayordomo.  Resource-bounded measure and randomness.  In A. Sorbi, editor, Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics, pages 1–47. Marcel Dekker, New York, N.Y., 1997.
  * [3] K. Ambos-Spies, S. A. Terwijn, and X. Zheng.  Resource bounded randomness and weakly complete problems.  Theoretical Computer Science, 172:195–207, 1997.
  * [4] T. Baker, J. Gill, and R. Solovay.  Relativizations of the P =? NP question.  SIAM Journal on Computing, 4:431–442, 1975.
  * [5] J.M. Breutzmann and J.H. Lutz.  Equivalence of measures of complexity classes.  SIAM Journal on Computing, 29(1):302–326, 1999.
  * [6] S. Cook and R. Reckhow.  The relative efficiency of propositional proof systems.  Journal of Symbolic Logic, 44:36–50, 1979.
  * [7] S. Even, A. L. Selman, and Y. Yacobi.  The complexity of promise problems with applications to public-key cryptography.  Information and Control, 61(2):159–173, 1984.
  * [8] L. Fortnow and J. Rogers.  Separability and one-way functions.  Computational Complexity, 11:137–157, 2002.
  * [9] C. Glaßer, A. L. Selman, and S. Sengupta.  Reductions between disjoint NP-pairs.  Information and Computation, 200:247–267, 2005.
  * [10] C. Glaßer, A. L. Selman, S. Sengupta, and L. Zhang.  Disjoint NP-pairs.  SIAM Journal on Computing, 33:1369–1416, 2004.
  * [11] C. Glaßer, A. L. Selman, and L. Zhang.  Survey of disjoint NP-pairs and relations to propositional proof systems.  In Theoretical Computer Science: Essays in Memory of Shimon Even, pages 241–253. Springer, 2006.
  * [12] C. Glaßer, A. L. Selman, and L. Zhang.  Canonical disjoint NP-pairs of propositional proof systems.  Theoretical Computer Science, 370:60–73, 2007.
  * [13] C. Glaßer, A. L. Selman, and L. Zhang.  The informational content of canonical disjoint NP-pairs.  In COCOON, LNCS, pages 307–317. Springer, 2007.
  * [14] O. Goldreich.  On promise problems: A survey.  In Theoretical Computer Science: Essays in Memory of Shimon Even, pages 254–290. Springer, 2006.
  * [15] J. Grollmann and A. Selman.  Complexity measures for public-key cryptosystems.  SIAM Journal on Computing, 11:309–335, 1988.
  * [16] J.M. Hitchcock.  Resource-bounded measure bibliography.  http://www.cs.uwyo.edu/~jhitchco/bib/rbm.shtml.
  * [17] S. Homer and A. L. Selman.  Oracles for structural properties: The isomorphism problem and public-key cryptography.  Journal of Computer and System Sciences, 44:287–301, 1992.
  * [18] D.W. Juedes and J.H. Lutz.  Weak completeness in E and $\mathrm{E}_{2}$, 1995.
  * [19] J. Kahn, M. E. Saks, and C. D. Smyth:.  A dual version of reimer’s inequality and a proof of rudich’s conjecture.  In Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pages 98–103, 2000.
  * [20] S. M. Kautz and P. B. Miltersen.  Relative to a random oracle, NP is not small.  Journal of Computer and System Sciences, 53:235–250, 1996.
  * [21] A.K. Lorentz and J.H. Lutz.  Genericity and randomness over feasible probability measures.  Theoretical Computer Science, 207(1):245–259, 1998.
  * [22] J. H. Lutz.  Almost everywhere high nonuniform complexity.  Journal of Computer and System Sciences, 44(2):220–258, 1992.
  * [23] J. H. Lutz.  The quantitative structure of exponential time.  In L. A. Hemaspaandra and A. L. Selman, editors, Complexity Theory Retrospective II, pages 225–254. Springer-Verlag, 1997.
  * [24] J. H. Lutz and E. Mayordomo.  Twelve problems in resource-bounded measure.  In G. Păun, G. Rozenberg, and A. Salomaa, editors, Current Trends in Theoretical Computer Science, entering the 21st century, pages 83–101. World Scientific Publishing, 2001.
  * [25] A. Razborov.  On provably disjoint NP pairs.  Technical Report 94-006, ECCC, 1994.
  * [26] A.L. Selman.  Complexity issues in cryptography.  In Computational complexity theory (Atlanta, GA, 1988), volume 38 of Proc. Sympos. Appl. Math., pages 92–107. Amer. Math. Soc., 1989.


ON PERIODIC GIBBS MEASURES FOR POTTS-SOS MODEL ON THE CAYLEY TREE
M.A.Rasulova 111Namangan State University, Uychi str. 316, Namangan,
Uzbekistan, e-mail<EMAIL_ADDRESS>
Abstract

In this paper we give a description of periodic Gibbs measures for Potts-SOS
model on the Cayley tree of order $k\geq 1$, i.e. a characterization of such
measures with respect to any normal subgroup of finite index of the group
representation of a Cayley tree.

Keywords: Cayley tree, configuration, Potts-SOS model, periodic Gibbs measure.

Mathematics Subject Classification: 82B20, 82B26.

Introduction

One of the central problems in the theory of Gibbs measures (GMs) is to
describe infinite-volume (or limiting) GMs corresponding to a given
Hamiltonian. The existence of such measures for a wide class of Hamiltonians
was established in the ground-breaking work of Dobrushin (see, e.g., Ref. 1).
However, a complete analysis of the set of limiting GMs for a specific
Hamiltonian is often a difficult problem.

In this paper we consider models with a nearest neighbour interaction on a
Cayley tree (CT). Models on a CT were discussed in Refs. 2 and 4-6. A
classical example of such a model is the Ising model, with two values of
spin,1. It was considered in Refs. 2, 6, 14, 16, 17 and became a focus of
active research in the first half of the 90s and afterwards; see Refs. 7-14.

In [18] all translation-invariant Gibbs measures for the Potts model on the CT
are described. In [19], [20] periodic Gibbs measures, in [21] weakly periodic
Gibbs measures for the Potts model are studied.

In [22], [23] translation-invariant and periodic Gibbs measures for the SOS
model on the CT are studied.

Model considered in this paper (Potts-SOS model) are generalizations of the
Potts and SOS (solid-on-solid) models. In [15] translation-invariant Gibbs
measures for the Potts-SOS model on the CT are studied, but periodic Gibbs
measures were not studied yet. In this paper we will study periodic Gibbs
measures for this model.

Preliminaries and main facts

The Cayley tree. The Cayley tree $\Gamma^{k}$ (See [14]) of order $k\geq 1$ is
an infinite tree, i.e., a graph without cycles, from each vertex of which
exactly $k+1$ edges issue. Let $\Gamma^{k}=(V,L,i)$ , where $V$ is the set of
vertices of $\Gamma^{k}$, $L$ is the set of edges of $\Gamma^{k}$ and $i$ is
the incidence function associating each edge $l\in L$ with its endpoints
$x,y\in V$. If $i(l)=\\{x,y\\}$, then $x$ and $y$ are called nearest
neighboring vertices, and we write $l=<x,y>$.

The distance $d(x,y),x,y\in V$ on the Cayley tree is defined by the formula

$d(x,y)=\min\\{d|\exists x=x_{0},x_{1},...,x_{d-1},x_{d}=y\in V\ \ \mbox{such
that}\ \ <x_{0},x_{1}>,...,<x_{d-1},x_{d}>\\}.$

For the fixed $x^{0}\in V$ we set $W_{n}=\\{x\in V\ \ |\ \ d(x,x^{0})=n\\},$

$V_{n}=\\{x\in V\ \ |\ \ d(x,x^{0})\leq n\\},\ \ L_{n}=\\{l=<x,y>\in L\ \ |\ \
x,y\in V_{n}\\}.$ $None$

Denote $|x|=d(x,x^{0})$, $x\in V$.

A collection of the pairs $<x,x_{1}>,...,<x_{d-1},y>$ is called a path from
$x$ to $y$ and we write $\pi(x,y)$ . We write $x<y$ if the path from $x^{0}$
to $y$ goes through $x$.

It is known (see [14]) that there exists a one-to-one correspondence between
the set $V$ of vertices of the Cayley tree of order $k\geq 1$ and the group
$G_{k}$ of the free products of $k+1$ cyclic groups $\\{e,a_{i}\\}$,
$i=1,...,k+1$ of the second order (i.e. $a^{2}_{i}=e$, $a^{-1}_{i}=a_{i}$)
with generators $a_{1},a_{2},...,a_{k+1}$.

Denote $S(x)$ the set of ”direct successors” of $x\in G_{k}$. Let $S_{1}(x)$
be denotes the set of all nearest neighboring vertices of $x\in G_{k},$ i.e.
$S_{1}(x)=\\{y\in G_{k}:<x,y>\\}$ and $x_{\downarrow}=S_{1}(x)\setminus S(x)$.

The model and a system vector-valued functional equations. Here we shall give
main definitions and facts about the model. Consider models where the spin
takes values in the set $\Phi=\\{0,1,2,...,m\\},m\geq 1$. For $A\subseteq V$ a
spin configuration $\sigma_{A}$ on $A$ is defined as a function $x\in
A\to\sigma_{A}(x)\in\Phi$; the set of all configurations coincides with
$\Omega_{A}=\Phi^{A}$. Denote $\Omega=\Omega_{V}$ and $\sigma=\sigma_{V}.$
Define a periodic configuration as a configuration $\sigma\in\Omega$ which is
invariant under a subgroup of shifts $K\subset G_{k}$ of finite index. More
precisely, a configuration $\sigma\in\Omega$ is called $K$ -periodic if
$\sigma(yx)=\sigma(x)$ for any $x\in G_{k}$ and $y\in K$.

For a given periodic configuration the index of the subgroup is called the
period of the configuration. A configuration that is invariant with respect to
all shifts is called translational-invariant. Let
$G_{k}/K=\\{K_{0},K_{1}...,K_{r-1}\\}$ factor group, where $K$ is a normal
subgroup of index $r\geq 1$.

The Hamiltonian of the Potts-SOS model with nearest-neighbor interaction has
the form

$H(\sigma)=-J\sum_{<x,y>\in L}|\sigma(x)-\sigma(y)|-J_{p}\sum_{<x,y>\in
L}\delta_{\sigma(x)\sigma(y)}$ $None$

where $J,J_{p}\in R$ are nonzero coupling constants.

Let $h:x\mapsto h_{x}=(h_{0,x},h_{1,x},...,h_{m,x})\in R^{m+1}$ be a real
vector-valued function of $x\in V\backslash\\{x^{0}\\}$. Let take into
consideration the probability distributions $\mu^{n}$ on $\Phi^{V_{n}}$ for
given $n=1,2,...$ defined by

$\mu^{(n)}(\sigma_{n})=Z_{n}^{-1}\exp\big{(}-\beta H(\sigma_{n})+\sum_{x\in
W_{n}}h_{\sigma(x),x}\big{)}$ $None$

where $\sigma_{n}\in\Phi^{V_{n}}$ and the related partition function $Z_{n}$
can be expressed as follows:

$Z_{n}(\widetilde{\sigma}_{n})=\sum_{\widetilde{\sigma}_{n}\in\Phi^{V_{n}}}\exp\big{(}-\beta
H(\widetilde{\sigma_{n}})+\sum_{x\in
W_{n}}h_{\widetilde{\sigma}(x),x}\big{)}.$ $None$

We say that the probability distributions $\mu^{(n)}$ are compatible if
$\forall n\geq 1$ and $\sigma_{n-1}\in\Phi^{V_{n-1}}$:

$\sum_{\omega_{n}\in\Phi^{V_{n}}}\mu^{(n)}\big{(}\sigma_{n-1}\vee\omega_{n}\big{)}=\mu^{(n-1)}\big{(}\sigma_{n-1}\big{)},$
$None$

here $\big{(}\sigma_{n-1}\vee\omega_{n}\big{)}\in\Phi^{V_{n}}$ is the
concatenation of $\sigma_{n-1}$ and $\omega_{n}$.

Definition 1. If probability distribution $\mu^{(n)}$ on $\Phi^{V_{n}}$ holds
the equality $(5)$, we can say that a unique measures $\mu$ on $\Phi^{V}$
exists such that, $\forall n$ and
$\sigma_{n}\in\Phi^{V_{n}},\mu\big{(}{\sigma|V_{n}=\sigma_{n}}\big{)}=\mu^{(n)}(\sigma_{n})$.
The measure $\mu$ is called splitting Gibbs measure $\big{(}$SGM$\big{)}$
corresponding to Hamiltonian $H$ and function $h:x\mapsto h_{x},x\neq x^{0}$.

The next theorem expresses the requirement on function $h$ that the
distributions $\mu^{(n)}(\sigma_{n})$ hold the compatibility conditions.

Theorem 1.[15] Defined as in (3) the probability distributions
$\mu^{(n)}(\sigma_{n}),n=1,2,...,$ satisfy the compatibility condition if and
only if

$h_{x}^{*}=\sum_{y\in S(x)}F\big{(}h_{y}^{*},m,\theta,r\big{)}$ $None$

is satisfied for any $x\in V\backslash\\{x^{0}\\}$, where

$\theta=\exp(J\beta),\ \ r=\exp(J_{p}\beta)$ $None$

and also $\beta=1/T$ is the inverse temperature. Here $h_{x}^{*}$ represents
the vector $(h_{0,x}-h_{m,x},h_{1,x}-h_{m,x},...,h_{m-1,x}-h_{m,x})$ and the
vector function $F(.,m,\theta,r):R^{m}\rightarrow R^{m}$ is defined as follows

$F(h,m,\theta,r)=\big{(}F_{0}(h,m,\theta,r),F_{1}(h,m,\theta,r),...,F_{m-1}(h,m,\theta,r)\big{)}$

where

$F_{i}(h,m,\theta,r)=\ln\frac{\sum_{j=0}^{m-1}\theta^{|i-j|}r^{\delta_{ij}}e^{h_{j}}+\theta^{m-i}r^{\delta_{mi}}}{\sum_{j=0}^{m-1}\theta^{m-j}r^{\delta_{mj}}e^{h_{j}}+r},$
$None$

$h=(h_{0},h_{1},...,h_{m-1}),i=0,1,2,...,m-1.$

Namely, for any collection of functions satisfying the functional equation (6)
there exists a unique splitting Gibbs measure, the correspondence being one-
to-one.

Definition 2. Let $K$ be a subgroup of $G_{k}$. A collection of vectors
$h=\\{h_{x}\in R^{m}:x\in G_{k}\\}$ is said to be $K-periodic$ , if
$h_{yx}=h_{x}$ for all $x\in G_{k}$ and $y\in K$. A $G_{k}-$ periodic
collections is said to be translation-invariant.

Definition 3. A Gibbs measure is called $K-periodic$ (translation-invariant),
if it corresponds to $K-periodic$ (translation-invariant) collection $h$.

Proposition 1. A SGM $\mu$ is traslation-invariant if only if $h_{j,x}$ does
not depend on $x:h_{j,x}\equiv h_{i},x\in V,j\in\Phi.$

Proof. Straightforward.

Proposition 2. Any extreme Gibbs measure is an SGM.

Proof. See [4], Theorem 12.6.

In [15] traslation-invariant splitting Gibbs measures are investigated.

Periodic SGMs. In this section we study periodic solutions of the functional
equation (6), i.e. periodic splitting Gibbs measures. We give a description of
periodic SGMs, i.e. a characterization of such measures with respect to any
normal subgroup of finite index of $G_{k}$.

For convenience of the reader we recall some necessary notations: Let $K$ be a
subgroup of index $r$ in $G_{k}$, and let
$G_{k}/K=\\{K_{0},K_{1},...,K_{r-1}\\}$ be the quotient group, with the coset
$K_{0}=K$. Let $q_{i}(x)=|S_{1}(x)\cap K_{i}|,\ \ i=0,1,...,r-1;\ \
N(x)=|\\{j:q_{j}(x)\neq 0\\}|$, where $S_{1}(x)=\\{y\in G_{k}:<x,y>\\},\ \
x\in G_{k}$ and $|\cdot|$ is the number of elements in the set. Denote
$Q(x)=(q_{0}(x),q_{1}(x),...,q_{r-1}(x))$.

We note (see [24]) that for every $x\in G_{k}$ there is a permutation
$\pi_{x}$ of the coordinates of the vector $Q(e)$ (where $e$ is the identity
of $G_{k}$) such that

$\pi_{x}Q(e)=Q(x).$ $None$

Each $K-$periodic collection is given by $\\{h_{x}=h_{i}$ for $x\in
K_{i},i=0,1,...,r-1\\}.$

By Theorem 1 (for m=2) and (9), vector $h_{n},n=0,1,...,r-1$, satisfies the
system

$h_{n}=\sum_{j=1}^{N(e)}q_{{i}_{j}}(e)F(h_{\pi_{n}(i_{j})};\theta,r)-F(h_{\pi_{n}(i_{j_{0}})};\theta,r),$
$None$

where $j_{0}=1,...,N(e)$, and function $h\mapsto F(h,m,\theta,r)$ defined in
Theorem 1 now takes the form $h\mapsto
F(h)=(F_{0}(h,\theta,r),F_{1}(h,\theta,r))$ where

$F_{0}(h,\theta,r)=\ln\frac{re^{h_{0}}+\theta
e^{h_{1}}+\theta^{2}}{\theta^{2}e^{h_{0}}+\theta e^{h_{1}}+r},$ $None$
$F_{1}(h,\theta,r)=\ln\frac{\theta
e^{h_{0}}+re^{h_{1}}+\theta}{\theta^{2}e^{h_{0}}+\theta e^{h_{1}}+r}.$

Proposition 3. If $\theta\neq 1$, then $F(h)=F(l)$ if and only if $h=l$.

Proof. _Necessity._ From $F(h)=F(l)$ we get the system of equations

$\left\\{\begin{array}[]{ll}$$\frac{re^{h_{0}}+\theta
e^{h_{1}}+\theta^{2}}{\theta^{2}e^{h_{0}}+\theta
e^{h_{1}}+r}=\frac{re^{l_{0}}+\theta
e^{l_{1}}+\theta^{2}}{\theta^{2}e^{l_{0}}+\theta e^{l_{1}}+r},$$\\\ \\\
$$\frac{\theta e^{h_{0}}+re^{h_{1}}+\theta}{\theta^{2}e^{h_{0}}+\theta
e^{h_{1}}+r}=\frac{\theta
e^{l_{0}}+re^{l_{1}}+\theta}{\theta^{2}e^{l_{0}}+\theta e^{l_{1}}+r},$$\\\
\end{array}\right.$ $None$

where $h=(h_{0},h_{1}),l=(l_{0},l_{1})$. We obtain

$\left\\{\begin{array}[]{ll}(r-\theta^{2})\big{(}\theta(e^{h_{0}+l_{1}}-e^{h_{1}+l_{0}})+\theta(e^{h_{1}}-e^{l_{1}})+(r+\theta^{2})(e^{h_{0}}-e^{l_{0}})\big{)}=0,\\\
\theta^{2}(r-1)(e^{h_{1}+l_{0}}-e^{h_{0}+l_{1}})+\theta(r-\theta^{2})(e^{h_{0}}-e^{l_{0}})+(r^{2}-\theta^{2})(e^{h_{1}}-e^{l_{1}})=0.\\\
\end{array}\right.$ $None$

Using the fact that

$e^{h_{0}+l_{1}}-e^{h_{1}+l_{0}}=e^{l_{1}}(e^{h_{0}}-e^{l_{0}})-e^{l_{0}}(e^{h_{1}}-e^{l_{1}}),$

we will have the following system of equations

$\left\\{\begin{array}[]{ll}(r-\theta^{2})(\theta
e^{l_{1}}+\theta^{2}+r)(e^{h_{0}}-e^{l_{0}})+\theta(1-e^{l_{0}})(e^{h_{1}}-e^{l_{1}})=0,\\\
\theta(r-\theta^{2}-\theta
e^{l_{1}}(r-1))(e^{h_{0}}-e^{l_{0}})+(r^{2}-\theta^{2}+e^{l_{0}}\theta^{2}(r-1))(e^{h_{1}}-e^{l_{1}})=0.\\\
\end{array}\right.$ $None$

It follows from (14), for the case $\theta\neq 1$, that
$h_{0}=l_{0},h_{1}=l_{1}.$

_Sufficiency._ Straightforward.
Let $G_{k}^{(2)}$ be the subgroup in $G_{k}$ consisting of all words of even
length, i.e. $G_{k}^{(2)}=\\{x\in G_{k}:\mbox{the length of word $x$ is
even}\\}$. Clearly, $G_{k}^{(2)}$ is a subgroup of index 2.

Theorem 2. _Let $K$ be a normal subgroup of finite index in $G_{k}$. Then each
$K-$ periodic GM for Potts-SOS model is either TI or $G_{k}^{(2)}-$periodic._

Proof.We see from $(10)$ that

$F(h_{\pi_{n}(i_{1})})=F(h_{\pi_{n}(i_{2})})=...=F(h_{\pi_{n}(i_{N(e)})}).$

Hence from Proposition 1 we have

$h_{\pi_{n}(i_{1})}=h_{\pi_{n}(i_{2})}=...=h_{\pi_{n}(i_{N(e)})}.$

Therefore,

$h_{x}=\left\\{\begin{array}[]{ll}h_{y}=h,&if\ {x,y\in S_{1}(z)},\ z\in K;\\\
h_{y}=l,&if\ {x,y\in S_{1}(z)},\ z\in G_{k}\setminus K.\\\ \end{array}\right.$

Thus the measures are TI (if $h=l$) or $G_{k}^{(2)}-$periodic (if $h\neq l$).
This completes the proof of Theorem 2.

Let $K$ be a normal subgroup of finite index in $G_{k}$. What condition on $K$
will guarantee that each $K-$ periodic GM is TI? We put
$I(K)=K\cap\\{a_{1},...,a_{k+1}\\},$ where $a_{i},\ i=1,...,k+1$ are
generators of $G_{k}$.

Theorem 3. _If $I(K)\neq\emptyset$, then each $K-$periodic GM for Potts-SOS
model is TI._

Proof. Take $x\in K$. We note that the inclusion $xa_{i}\in K$ holds if and
only if $a_{i}\in K$. Since $I(K)\neq\emptyset$, there is an element $a_{i}\in
K$.Therefore $K$ contains the subset $Ka_{i}=\\{xa_{i}:x\in K\\}$. By Theorem
2 we have $h_{x}=h$ and $h_{xa_{i}}=l$. Since $x$ and $xa_{i}$ belong to $K$,
it follows that $h_{x}=h_{xa_{i}}=h=l.$ Thus each $K-$periodic GM is TI. This
proves Theorem 3.

Theorems 2 and 3 reduce the problem of describing $K-$periodic GM with
$I(K)\neq\emptyset$ to describing the fixed points of $kF(h,\theta,r)$ which
describs TIGM. If $I(K)=\emptyset$, this problem is reduced to describing the
solutions of the system:

$\left\\{\begin{array}[]{ll}h=kF(l,\theta,r),\\\\[8.53581pt]
l=kF(h,\theta,r).\\\\[8.53581pt] \end{array}\right.$ $None$

Denote $z_{i}=e^{h_{i}},t_{i}=e^{l_{i}},i=0,1$. Then from (15) we get

$\left\\{\begin{array}[]{ll}z_{0}=\big{(}\frac{rt_{0}+\theta
t_{1}+\theta^{2}}{\theta^{2}t_{0}+\theta t_{1}+r}\big{)}^{k},\\\\[8.53581pt]
z_{1}=\big{(}\frac{\theta t_{0}+rt_{1}+\theta}{\theta^{2}t_{0}+\theta
t_{1}+r}\big{)}^{k},\\\\[8.53581pt] t_{0}=\big{(}\frac{rz_{0}+\theta
z_{1}+\theta^{2}}{\theta^{2}z_{0}+\theta z_{1}+r}\big{)}^{k},\\\\[8.53581pt]
t_{1}=\big{(}\frac{\theta z_{0}+rz_{1}+\theta}{\theta^{2}z_{0}+\theta
z_{1}+r}\big{)}^{k}.\\\\[8.53581pt] \end{array}\right.$ $None$

From the first and third equations of (16), we get the following:

$\left\\{\begin{array}[]{ll}z_{0}^{\frac{1}{k}}-1=\frac{(z_{0}-1)(r-\theta^{2})}{\theta^{2}t_{0}+\theta
t_{1}+r},\\\\[8.53581pt]
t_{0}^{\frac{1}{k}}-1=\frac{(t_{0}-1)(r-\theta^{2})}{\theta^{2}z_{0}+\theta
z_{1}+r}.\\\ \end{array}\right.$ $None$

From this, we will see that $(z_{0};t_{0})=(1;1)$ is a solution of the system
of equations (17) for every $\theta,r,z_{1},t_{1}$. In this case, we will have
the following system of equations from the second and fourth equations system
of equations (16):

$\left\\{\begin{array}[]{ll}z_{1}=\big{(}\frac{2\theta+rt_{1}}{\theta^{2}+\theta
t_{1}+r}\big{)}^{k},\\\\[8.53581pt]
t_{1}=\big{(}\frac{2\theta+rz_{1}}{\theta^{2}+\theta z_{1}+r}\big{)}^{k}.\\\
\end{array}\right.$ $None$

Denote:

$f{(z_{1})}=\big{(}\frac{2\theta+rz_{1}}{\theta^{2}+\theta
z_{1}+r}\big{)}^{k}.$

Then the system of equations (18) will come to the following equation:

$f\big{(}f(z_{1})\big{)}-z_{1}=0.$ $None$

Obviously, the solutions of $f(z_{1})=z_{1}$ are also the solutions of the
equation (19). We are interested in the solutions of the equation (19), except
for the solutions of the equation $f(z_{1})=z_{1}$. This solution is complied
with $G_{k}^{(2)}-$periodic measure Gibbs, which is not translation-invariant.
We should exclude the solutions of $f(z_{1})=z_{1}$ from those of equation
(19) for the case $k=2$, simplify it, and get the following quadratic
equation:

$(\theta^{6}+2\theta^{4}r+\theta^{2}r^{2}+r^{4}+2\theta
r^{3}+2\theta^{3}r^{2})z_{1}^{2}+$
$+(2\theta^{7}+6\theta^{5}r+6\theta^{3}r^{2}+6\theta
r^{3}-4\theta^{4}+\theta^{4}r^{2}+8\theta^{2}r^{2}+2\theta^{2}r^{3}+8\theta^{4}r+r^{4})z_{1}+$
$+4\theta^{2}r^{2}+4\theta^{6}r+r^{4}+6\theta^{4}r^{2}+4\theta^{2}r^{3}+\theta^{8}+4\theta^{5}r+8\theta^{3}r^{2}+4\theta
r^{3}=0.$

In order to have two positive real roots in that equation, there should the
following conditions: $D>0,b<0$, where

$D=(2\theta^{7}+6\theta^{5}r+6\theta^{3}r^{2}+6\theta
r^{3}-4\theta^{4}+\theta^{4}r^{2}+8\theta^{2}r^{2}+2\theta^{2}r^{3}+8\theta^{4}r+r^{4})^{2}-$
$-(\theta^{6}+2\theta^{4}r+\theta^{2}r^{2}+r^{4}+2\theta
r^{3}+2\theta^{3}r^{2})\cdot(4\theta^{2}r^{2}+4\theta^{6}r+r^{4}+6\theta^{4}r^{2}+4\theta^{2}r^{3}+\theta^{8}+4\theta^{5}r+8\theta^{3}r^{2}+4\theta
r^{3}),$ $b=2\theta^{7}+6\theta^{5}r+6\theta^{3}r^{2}+6\theta
r^{3}-4\theta^{4}+\theta^{4}r^{2}+8\theta^{2}r^{2}+2\theta^{2}r^{3}+8\theta^{4}r+r^{4}.$

As a result, we obtain the following theorem

Theorem 4. _Let $k=2$. If $D>0,b<0$, then there exist at least two
$G_{k}^{(2)}-$periodic (not translation-invariant) Gibbs measures for Potts-
SOS model; If $D=0,b<0$, then there exists at least one $G_{k}^{(2)}-$periodic
(not translation-invariant) Gibbs measure for Potts-SOS model._

Let’s show that the set $\\{{(r,\theta)\in R^{2}:D\geq 0,b<0}\\}$ is not
empty. Indeed, let $r=\theta^{2}$. Then we have the following:

$D=-16\theta^{8}(\theta^{2}-1)^{2}(3\theta^{4}+10\theta^{3}+6\theta^{2}-1),$
$b=4\theta^{4}(\theta^{4}+5\theta^{3}+4\theta^{2}-1).$

If $\theta<\theta_{D}(\theta_{D}\approx 0,32359)$, then we have $D>0,b<0$,
that is to say that there exist at least two $G_{k}^{(2)}-$periodic (not
translation-invariant) Gibbs measures; If $\theta=\theta_{D}$, in that case,
the followings are obvious: $D=0,b<0$, which means there exists at least one
$G_{k}^{(2)}-$periodic (not translation-invariant) Gibbs measure for Potts-SOS
model.

Remark. Note that, when $k=2$ for the Potts model there is no periodic Gibbs
measure (see [19]), but as Theorem 4 shows for the Potts-SOS model, there
exists such kind of measures under some conditions.

Aknowledgments. The author is grateful to Professors U.A.Rozikov and
M.M.Rahmatullaev for useful discussions and for valuable comments.

References

[1] Ya. G. Sinai, Theory of Phase Transitions: Rigorous Results, (Pergamon,
1982).

[2] C. Preston, Gibbs States on Countable Sets, Cambridge Univ.Press, 1974;

[3] V. A. Malyshev and R. A. Minlos, Gibbs Random Fields, Nauka, 1985.

[4] H. O. Georgii, Gibbs Measures and Phase Transitions,  Walter de Gruyter,
1988.

[5] S. Zachary, Ann. Probab. 11:4 (1983), 894–903.

[6] S. Zachary,  Stoch. Process. Appl. 20:2 (1985), 247–256.

[7] P. M. Bleher and N. N. Ganikhodjaev, Theor. Probab. Appl. 35 (1990),
216–227.

[8] P. M. Bleher, Commun. Math. Phys. 128 (1990), 411–419.

[9] P. M. Bleher, J. Ruiz and V. A. Zagrebnov, J.Stat.Phys., 79 (1995),
473–482.

[10] P. M. Bleher, J. Ruiz and V. A. Zagrebnov, J.Stat.Phys. 93, (1998),
33–78.

[11] D. Ioffe, Lett. Math. Phys. 37 (1996), 137–143.

[12] D. Ioffe, Extremality of the disordered state for the Ising model on
general trees, in Trees, Versailles, 1995, Prog. Probab. Vol. 40, (Birkhauser,
1996), pp. 314.

[13] P. M. Bleher, J. Ruiz, R. H. Schonmann, S. Shlosman and V. A. Zagrebnov,
Moscow Math. J. 3, (2001), 345–363.

[14] U.A. Rozikov, Gibbs measures on Cayley trees. World scientific, 2013.

[15] H. Saygili, Asian Journal of Current Research V. 1, N 3, (2017), 114–121.

[16] M. M. Rahmatullaev, Russian Mathematics, 59:11 (2015), 45–53.

[17] M. M. Rahmatullaev, Uzb. Mat. Zh., 2,(2009), 144–152

[18] C. Kulske, U. A. Rozikov, R. M. Khakimov. Jour. Stat. Phys. 156:1,
(2014), 189–200.

[19] U.A.Rozikov and R.M.Khakimov, Theor. Math.Phys., 175, (2013), 699 -709.

[20] R.M.Khakimov, Uzb. Mat. Zh., 3, (2014), 134 -142.

[21] M.M.Rahmatullaev, Theor. Math. Phys., 180, (2014), 1019 -1029.

[22] U.A.Rozikov, Y.M.Suhov, Infinite Dimensional Analysis, Quantum
Probability and Related Topics., Vol.9, No. 3 (2006), 471–488.

[23] C. Kulske, U. A. Rozikov, J.Stat.Phys. 160, (2015) 659–680.

[24] U. A. Rozikov, Theor. Math. Phys. 112 (1997), 929–933.