text:
# Efficient Determination of Gibbs Estimators with Submodular Energy Functions

## 1 Introduction

Nowadays Gibbs models are successfully employed in mathematical statistics, statistical physics, image processing etc. Often these models allow to get satisfactory solutions of various problems but usually they turn out very hard to be solved efficiently. Finding of Gibbs estimates is equivalent to the problem of identification of minima of corresponding energy functions. In this paper we present fast methods of finding the Gibbs estimates for some models that occur in application (for instance, in image processing).

The Simulated annealing  was one of the first method that was used to find the Gibbs estimates. In spite of its slowness, it remains a very popular tool to evaluate the estimates as well as other problems of general global optimization. To speed up computation of the estimator of the Ising model Grieg, Porteous and Seheult  in 1989 described the network flow technique that allowed the exact Boolean minimizing the Ising energy function. In the last few years several new approaches, which enable efficient estimation  or even efficient minimizing some wide classes of functions of many Boolean or integer variables, have been developed . These approaches, which are based on the graph cut technique, demonstrate possibility to solve real practical problems including handling of 3D data for acceptable time (for instance, segmentation of 3D $`200\times 200\times 300`$ gray-scale image by the such type method took 14min. of Pentiym 4 1.6GH CPU).

Recently *the combinatorial algorithm of minimization of submodular functions* (SFM) have been developed . To minimize a submodular function of $`n`$ variables it needs either $`O(n^5\mathrm{log}M)`$ (where $`M`$ is some number depending on the function considered) or $`O(n^8)`$ operations. Therefore, the SFM can not be immediately used for finding of high dimensional Gibbs estimates for its comparatively high computational expenses. We present a modification of the SFM that can be useful for minimization of submodular Boolean representations of energy functions, which occur in applications, for instance, in image processing.

In order to use the SFM algorithm and the graph cut technique for energy functions, which depend on variables taking values in finite totally ordered sets, we represent the functions by Boolean polynomials. Then we develop methods that allow efficient minimization of submodular Boolean polynomials of special structure. Some Boolean polynomials admit finding parts of Boolean vectors, which minimize these polynomials, by use only parts of their monomials. We illustrate this property with image processing terminology. It means colours of far points of images estimates are independent, i.e. a change of colours of some image pixels in the estimate does not affect colours of other far pixels. Therefore, *the modified SFM* (MSFM) operates, first, not with an original Boolean polynomial but with separated its parts, trying to find part of coordinates of a solution of the original problem. Then the values found are set in the original polynomial and the procedure are repeated either with other parts of the residual polynomial or with the entire residual polynomial. At worst, it takes as many operations as the usual SFM and, at best, the number of operations is even $`O(n)`$, where $`n`$ is a number of Boolean variables.

As we mentioned above, new graph cut methods  are now an efficient tool to determine Gibbs estimators with energy functions $`U=g_\mu (x_\mu )+g_{\mu ,\nu }(x_\mu ,x_\nu )+g_{\mu ,\nu ,\kappa }(x_\mu ,x_\nu ,x_\kappa )`$ that are Boolean polynomials of the third order. We failed to represent an arbitrary submodular Boolean polynomial by a graph but we made it for submodular Boolean polynomials of the special structure that can be met in applications. The set of those polynomials contains, for instance, Boolean polynomials with all nonlinear monomials negative (of course, such polynomials are submodular) and submodular Boolean polynomials with monomials of order three and higher positive.

## 2 Representation of Functions by Boolean Polynomials

Below the function $`U(𝐱),𝐱=(x_1,\mathrm{},x_n)`$ is supposed to be dependent on variables that take values in an arbitrary finite totally ordered set $`=\{r_0,r_1,\mathrm{},r_k\},`$ $`r_0r_1\mathrm{}r_k`$. The multiindex $`𝐣=(j_1,j_2,\mathrm{},j_n)`$ is with coordinates $`j_l\{0,1,\mathrm{},k\}=_k`$. The function of integer variables

$$V(𝐣)=U(r_{j_1},r_{j_2},\mathrm{},r_{j_n})$$

is considered instead of the initial $`U(𝐱)`$.

To exploit the MSF and graph cut technique we, first, represent the integer variables $`j_i`$ as the sum of ordered Boolean ones

$$j_i=\underset{l=1}{\overset{k}{}}x_i(l),$$
(1)
where $`x_i(l)\{0,1\},x_i(1)x_i(2)\mathrm{}x_i(k).`$ By other words, we establish one-to-one correspondence between each variable $`j_i`$ and the ordered sequence of Boolean variables $`x_i(1)x_i(2)\mathrm{}x_i(k)`$. After we represent the function $`V(𝐣)`$ by a Boolean polynomial and then minimize the polynomial.

Denote the Boolean vector $`𝐱(l)=(x_1(l),x_2(l),\mathrm{},x_n(l))`$, and for two vectors $`𝐱,𝐳`$ say $`𝐱𝐳`$, if $`x_iz_i,i=1÷n`$ (respectively, $`𝐱𝐳`$, if there is a couple of indexes $`i,j`$ such that $`x_i<z_i`$ and $`x_j>z_j`$). Then

$$V(𝐣)=V\left(\underset{l=1}{\overset{k}{}}𝐱(l)\right),𝐱(1)𝐱(2)\mathrm{}𝐱(k).$$

For simplicity let us start with the function of two variables $`V(j_1,j_2)`$. It is not hard to check the equality

$$V(j_1,j_2)=V(0,j_2)+\underset{\mu =1}{\overset{k}{}}(V(\mu ,j_2)V(\mu 1,j_2))x_1(\mu ),$$
(2)
where ordered Boolean variables $`x_1(\mu )`$ satisfy the equality (1). Now the expansion

$$\begin{array}{c}V(j_1,j_2)\hfill \\ \hfill =V(0,0)+\underset{\mu =1}{\overset{k}{}}(V(\mu ,0)V(\mu 1,0))x_1(\mu )+\underset{\nu =1}{\overset{k}{}}(V(0,\nu )V(0,\nu 1))x_2(\nu )\\ \hfill +\underset{\mu ,\nu =1}{\overset{k}{}}(V(\mu ,\nu )V(\mu 1,\nu )V(\mu ,\nu 1)+V(\mu 1,\nu 1))x_1(\mu )x_2(\nu ),\end{array}$$
(3)
can be constructed by use of equality (2) for the second variable $`j_2`$ of each difference $`V(\mu ,j_2)V(\mu 1,j_2).`$

In general case, for $`𝐣_n`$ we say

$$\mathrm{\Delta }_iV(𝐣)=V(𝐣)V(𝐣𝐞_i),𝐞_i=(\stackrel{n}{\stackrel{}{\underset{i1}{\underset{}{0,\mathrm{},0}},1,0,\mathrm{},0}})$$

is difference derivative of the first order, and define the mixed difference derivative of higher orders by the recursion

$$\mathrm{\Delta }_{j_1,j_2,\mathrm{},j_{l+1}}V(𝐣)=\mathrm{\Delta }_{j_1,j_2,\mathrm{},j_l}V(𝐣)\mathrm{\Delta }_{j_1,j_2,\mathrm{},j_l}V(𝐣𝐞_{j_{l+1}}).$$

Note that for any permutation of indices $`\pi (j_1,j_2,\mathrm{},j_n)`$

$$\mathrm{\Delta }_{\pi (j_1,j_2,\mathrm{},j_{l+1})}=\mathrm{\Delta }_{j_1,j_2,\mathrm{},j_{l+1}}.$$

By analogy with 2D case

$$V(𝐣)=U(0,j_2,\mathrm{},j_n)+\underset{\mu =1}{\overset{k}{}}\mathrm{\Delta }_1V(\mu ,j_2,\mathrm{},j_n))x_1(\mu ).$$
(4)
Let the $`G_m`$ be the projection operator onto the space of last $`nm`$ coordinate, i.e.

$$G_m𝐣=(0,\mathrm{},0,j_{m+1},j_{m+2},\mathrm{},j_n).$$

Applying formula (4) recursively $`m`$ times to each its item we get the equality

$$\begin{array}{c}V(𝐣)=V(G_m𝐣)+\underset{1lm}{}\underset{\mu =1}{\overset{k}{}}\mathrm{\Delta }_lV(G_m𝐣+\mu 𝐞_l)x_l(\mu )\hfill \\ \hfill +\underset{1l_1<l_2m}{}\underset{\mu _1,\mu _2=1}{\overset{k}{}}\mathrm{\Delta }_{l_1,l_2}V(G_m𝐣+\mu _1𝐞_{l_1}+\mu _2𝐞_{l_2})x_{l_1}(\mu _1)x_{l_2}(\mu _2)+\mathrm{}\\ \hfill +\underset{\mu _1,\mathrm{},\mu _m=1}{\overset{k}{}}\mathrm{\Delta }_{1,2,\mathrm{},m}V(G_m𝐣+\mu _1𝐞_1+\mu _2𝐞_2+\mathrm{}+\mu _m𝐞_m)x_1(\mu _1)x_2(\mu _2)\mathrm{}x_m(\mu _m)\end{array}$$

Therefore, the following statement is valid.

###### Proposition 1.

The expansion of $`V(𝐣)`$ into a polynomial in ordered Boolean variables $`𝐱(1)𝐱(2)\mathrm{}𝐱(k)`$ is of the form

$$\begin{array}{c}V(𝐣)=\stackrel{~}{P}_V(𝐱(1),𝐱(2)\mathrm{},𝐱(k))\hfill \\ \hfill =V(\mathrm{𝟎})+\underset{m=1}{\overset{n}{}}\underset{1l_1<\mathrm{}<l_mn}{}\underset{\mu _1,\mathrm{},\mu _m=1}{\overset{k}{}}\mathrm{\Delta }_{l_1,\mathrm{},l_m}V\left(\underset{\varkappa =1}{\overset{m}{}}\mu _\varkappa 𝐞_{l_\varkappa }\right)\underset{\varkappa =1}{\overset{m}{}}x_{l_\varkappa }(\mu _\varkappa ).\end{array}$$
(5)
The expansion (5) does not allow to turn immediately to the problem of the Boolean minimization because of ordered variables. To avoid this disadvantage we will use another polynomial

$$P_V(𝐱(1),𝐱(2)\mathrm{},𝐱(k))=\stackrel{~}{P}_V(𝐱(1),𝐱(2)\mathrm{},𝐱(k))+𝒞\underset{\mu =1}{\overset{n}{}}\underset{l=2}{\overset{k}{}}(x_\mu (l)x_\mu (l1))x_\mu (l),$$

for sufficiently large constant $`𝒞>0`$. This polynomial satisfy the following properties.

###### Proposition 2.

The inequality $`\stackrel{~}{P}_VP_V`$ holds true. Any collection of Boolean vectors $`𝐮^{}=(𝐱^{}(1),𝐱^{}(2)`$ $`\mathrm{},𝐱^{}(k))`$ that minimizes $`P_V`$

$$𝐮^{}=\underset{𝐱(1),𝐱(2),\mathrm{},𝐱(k)}{argmin}P_V(𝐱(1),𝐱(2)\mathrm{},𝐱(k))$$

turns to be ordered (non-increasing). This collection minimizes the polynomial $`\stackrel{~}{P}_V`$, and, therefore, the integer vector $`𝐣^{}=_{l=1}^k𝐱^{}(l)`$ minimizes the original function $`V(𝐣)`$.

Therefore, instead of minimization of $`V(𝐣)`$ we can consider the problem of Boolean minimization of the polynomial

$$P_V(𝐮)=a_0+\underset{m=1}{\overset{n}{}}\underset{1l_1<\mathrm{}<l_mn}{}a_{l_1,l_2,\mathrm{},l_m}\underset{i=1}{\overset{m}{}}u_{l_i},dim(𝐮)=kn.$$

Because of the representation of functions $`V(𝐣)`$ by Boolean polynomials developed we consider the problem of minimization of general Boolean polynomials $`P(𝐱)`$.

## 3 Submodular Boolean Polynomials

For two Boolean vectors $`𝐱,𝐲`$ let us denote by $`𝐱𝐲`$ (respectively, by $`𝐱𝐲`$) the vector with coordinates $`\mathrm{max}(x_i,y_i)`$ (respectively, with coordinates $`\mathrm{min}(x_i,y_i)`$).

###### Definition 3.

A function $`f`$ is called *submodular* if for any Boolean vectors $`𝐱,𝐲`$ it satisfies the inequality

$$f(𝐱𝐲)+f(𝐱𝐲)f(𝐱)+f(𝐲).$$

Let the set $`𝒱=\{1,\mathrm{},n\}`$, and for any $`𝒟𝒱`$ the set $`𝒟^c=𝒱\backslash 𝒟`$. Let the vector $`𝐱_𝒟`$ with coordinated $`x_i,i𝒟`$ be the restriction of $`𝐱`$ to the set $`𝒟`$, the abbreviation $`P(𝐱_𝒟)=P(𝐱_𝒟,\mathrm{𝟎}_{𝒟^c})`$.

Below we always suppose $`P(\mathrm{𝟎})=0`$. Therefore, $`P`$ is of the form

$$P(𝐱)=\underset{m=1}{\overset{n}{}}\underset{1l_1<\mathrm{}<l_mn}{}a_{l_1,l_2,\mathrm{},l_m}\underset{i=1}{\overset{m}{}}x_{l_i}.$$
(6)
For any $`i,j𝒱`$ a polynomial $`P(𝐱)`$ can be written in the form

$$P(𝐱)=P(𝐱_{\{i,j\}^c})+x_iP_i(𝐱_{\{i,j\}^c})+x_jP_j(𝐱_{\{i,j\}^c})+x_ix_jP_{i,j}(𝐱_{\{i,j\}^c})$$
(7)
or in the form

$$P(𝐱)=Q(𝐱)+L(𝐱),$$

where $`Q(𝐱)`$ is the polynomial consisting of monomials of degree $`2`$ and higher, and $`L(𝐱)`$ is a linear polynomial. It also can be represented as

$$P(𝐱)=P\{𝒟\}(𝐱)+P(𝐱_{𝒟^c}),𝒟𝒱,$$

where each monomial of $`P\{𝒟\}(𝐱)`$ contains at least one variable $`x_i,i𝒟`$ (and, in general, it depends on $`𝐱_{𝒟^c}`$), and $`P(𝐱_{𝒟^c})`$ is independent of $`𝐱_𝒟`$. The following useful properties can be easily veryfied.

###### Proposition 4.

a) A Boolean polynomial $`P(𝐱)`$ is submodular if and only if for any vector $`𝐱`$ and any couple of indices $`i,j𝒩`$ the polynomials $`P_{i,j}(𝐱_{\{i,j\}^c})0`$.

b) In order to Boolean polynomial $`P(𝐱)`$ be submodular it is necessary and sufficient its nonlinear part $`Q(𝐱)`$ will be submodular.

c) If $`P(𝐱)`$ is submodular, then the polynomial $`Q(𝐱)`$ is nonincreasing, in the sense that $`Q(𝐲)Q(𝐱)`$ for any ordered pair of vectors $`𝐲𝐱`$. Therefore, $`argmin_𝐱Q(𝐱)=\mathrm{𝟏}_𝒱`$.

d) If $`P(𝐱)`$ is submodular, then $`P\{𝒟\}(𝐱)`$ is submodular polynomial in $`𝐱_𝒟`$ for each fixed vector $`𝐱_{𝒟^c}`$.

The sentences a), b) and d) are deduced directly from Definition 3. To prove c) let us consider a couple of vectors: $`𝐱`$ with $`x_i=0`$ and $`𝐲=𝐱+𝐞_i`$ and inequality

$$Q(\mathrm{𝟎}_𝒱)+Q(𝐲)Q(𝐞_i)+Q(𝐱)$$

that follows from Definition 3. Since $`Q(\mathrm{𝟎}_𝒱)=Q(𝐞_i)=0`$ we have $`Q(𝐲)Q(𝐱)`$. To prove c) in general case it is enough to repeat the last inequality successively.

We need two properties of polynomials $`P\{𝒟\}(𝐱)`$. The first one is rather clear.

###### Proposition 5.

If $`𝐱_𝒟^{}`$ minimizes the polynomial $`P\{𝒟\}(𝐱)`$ for some fixed $`\underset{𝒟^c}{\overset{}{𝐱}}`$, then for any set $`𝒟`$ the restriction $`𝐱_{}^{}`$ minimizes the polynomial $`P\{\}(𝐱_{},𝐱_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐱}})`$ with respect to $`𝐱_{}`$, and vice versa, if the vector $`\widehat{𝐱}_{}`$ minimizes $`P\{\}(𝐱_{},𝐱_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐱}}),`$ then the vector $`(\widehat{𝐱}_{},𝐱_{𝒟\backslash }^{})`$ minimizes $`P\{𝒟\}(𝐱_𝒟,\underset{𝒟^c}{\overset{}{𝐱}}).`$ with respect to $`𝐱_𝒟`$.

The second property concerns monotonic (in some sense) dependence of the solution $`𝐱_𝒟^{}=argmin_{𝐱_𝒟}P\{𝒟\}(𝐱_𝒟,\underset{𝒟^c}{\overset{}{𝐱}})`$ on boundary vector $`\underset{𝒟^c}{\overset{}{𝐱}}`$ for a submodular polynomial $`P`$. Let

$$(\underset{𝒟^c}{\overset{}{𝐱}})=\left\{\underset{𝐱_𝒟}{argmin}P\{𝒟\}(𝐱_𝒟,\underset{𝒟^c}{\overset{}{𝐱}})\right\}$$

be the set of minima of the polynomial $`P\{𝒟\}`$ for fixed $`\underset{𝒟^c}{\overset{}{𝐱}}`$. It can be shown that for two ordered boundary vectors $`\underset{𝒟^c}{\overset{}{𝐱}}\underset{𝒟^c}{\overset{}{𝐳}}`$ can exist either unordered $`𝐱_𝒟^{}𝐳_𝒟^{}`$ or non-increasing $`𝐱_𝒟^{}𝐳_𝒟^{}`$ solutions, but for any $`𝐱_𝒟^{}`$ there exists $`𝐳_𝒟^{}`$ such that $`𝐱_𝒟^{}𝐳_𝒟^{}`$, and vice versa, for any $`𝐳_𝒟^{}`$ there is $`𝐱_𝒟^{}`$ satisfying the same inequality.

###### Theorem 6.

Let a polynomial $`P`$ be submodular. Let for $`\underset{𝒟^c}{\overset{}{𝐱}}\underset{𝒟^c}{\overset{}{𝐳}}`$ solutions $`𝐱^{}(\underset{𝒟^c}{\overset{}{𝐱}})`$ and $`𝐳^{}(\underset{𝒟^c}{\overset{}{𝐳}})`$ do not satisfy the inequality $`𝐱_𝒟^{}𝐳_𝒟^{}`$.

Then for the maximal nonempty set of the inverse order $`=\{i𝒟|x_i^{}=1,z_i^{}=0\}`$, such that $`\mathrm{𝟏}_{}=𝐱_{}^{}>𝐳_{}^{}=\mathrm{𝟎}_{}`$, the vector $`(𝐳_{}^{},𝐱_{𝒟\backslash }^{})=(\mathrm{𝟎}_{},𝐱_{𝒟\backslash }^{})(\underset{𝒟^c}{\overset{}{𝐱}})`$ as well as $`(𝐱_{}^{},𝐳_{𝒟\backslash }^{})=(\mathrm{𝟏}_{},𝐳_{𝒟\backslash }^{})(\underset{𝒟^c}{\overset{}{𝐳}})`$ and, therefore, $`(𝐳_{}^{},𝐱_{𝒟\backslash }^{})(𝐱_{}^{},𝐳_{𝒟\backslash }^{}).`$

###### Proof.

For boundary vectors $`\underset{𝒟^c}{\overset{}{𝐱}}\underset{𝒟^c}{\overset{}{𝐳}}`$ suppose the condition $`𝐱_𝒟^{}𝐳_𝒟^{}`$ is not valid, i.e. either $`𝐱_𝒟^{}𝐳_𝒟^{}`$ or $`𝐱_𝒟^{}𝐳_𝒟^{}`$. In this case the set $`=\{i𝒟|x_i^{}=1,z_i^{}=0\}`$ is nonempty. Let us consider the chain of relations. The inequality

$$P\{\}(𝐳_{}^{},𝐳_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐳}})P\{\}(𝐱_{}^{},𝐳_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐳}})$$
(8)
holds true since the vector $`𝐳_{}^{}`$ minimizes $`P\{\}(,𝐳_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐳}})`$ (see, Proposition 5). The inequality

$$P\{\}(𝐱_{}^{},𝐳_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐳}})P\{\}(𝐱_{}^{},𝐱_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐱}})$$
(9)
will be proved later. The relation

$$P\{\}(𝐱_{}^{},𝐱_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐱}})P\{\}(𝐳_{}^{},𝐱_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐱}})$$
(10)
is verified the same way as (8). Equalities

$$P\{\}(𝐳_{}^{},𝐱_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐱}})=P\{\}(𝐳_{}^{},𝐳_{𝒟\backslash }^{},\underset{𝒟^c}{\overset{}{𝐳}})=0$$
(11)
are valid because $`𝐳_{}^{}=\mathrm{𝟎}_{}`$. Therefore, relations (8)-(11) are, actually, equalities, and the claim of the Theorem can be derived from Proposition 5.

Thus, the Theorem will be proved if we ground the inequality (9). For that we need additional notations. One-element sets $`\{j\}𝒱`$ will be denoted by $`j`$. Instead of $`\{j\}`$ and $`\backslash \{j\}`$ we will use abbreviations $`+j`$ and $`j`$. For arbitrary sets $`𝒜,,𝒞𝒱`$ we denote by $`P\{𝒜,|𝒞\}(𝐱)`$ polynomials that consist of monomials of $`P(𝐱)`$ with variables $`x_i,i𝒜,x_j,j`$ but without $`x_k,k𝒞`$.

First, consider Boolean vectors that for some $`j^c`$ satisfy the equation $`\underset{^c}{\overset{}{𝐱}}+𝐞_j=\underset{^c}{\overset{}{𝐳}}`$ and the polynomial $`P\{+j\}(𝐱_{+j},\underset{^cj}{\overset{}{𝐱}}),`$ which is a submodular function of $`𝐱_{+j}`$. Let us write the condition of submodularity of the polynomial for vectors $`𝐚_{+j}=(\mathrm{𝟎}_{},1_j)`$ and $`𝐛_{+j}=(𝐱_{},0_j)`$ using the representation

$$\begin{array}{c}P\{+j\}(𝐱_{+j},\underset{^cj}{\overset{}{𝐱}})=P\{|^c\}(𝐱_{})+P\{,j\}(𝐱_{+j},\underset{^cj}{\overset{}{𝐱}})+\hfill \\ \hfill P\{,^cj|j\}(𝐱_{},\underset{^cj}{\overset{}{𝐱}})+P\{j,^cj|\}(x_j,\underset{^cj}{\overset{}{𝐱}})+a_jx_j.\end{array}$$

Since $`𝐚_{+j}𝐛_{+j}=\mathrm{𝟎}_{+j}`$ and $`𝐚_{+j}𝐛_{+j}=(𝐱_{},1_j),`$ it looks as

$$\begin{array}{c}P\{|^c\}(𝐱_{})+P\{,j\}(𝐱_{},1_j,\underset{^cj}{\overset{}{𝐱}})+\hfill \\ \hfill P\{,^cj|j\}(𝐱_{},\underset{^cj}{\overset{}{𝐱}})+P\{j,^cj|\}(1_j,\underset{^cj}{\overset{}{𝐱}})+a_j\\ \hfill P\{j,^cj|\}(1_j,\underset{^cj}{\overset{}{𝐱}})+a_j+\\ \hfill P\{|^c\}(𝐱_{})+P\{,j\}(𝐱_{},0_j,\underset{^cj}{\overset{}{𝐱}})+P\{,^cj|j\}(𝐱_{},\underset{^cj}{\overset{}{𝐱}}).\end{array}$$

Therefore,

$$P\{,j\}(𝐱_{},1_j,\underset{^cj}{\overset{}{𝐱}})P\{,j\}(𝐱_{},0_j,\underset{^cj}{\overset{}{𝐱}})=0.$$
(12)
But

$$P\{\}(𝐱_{},\underset{^c}{\overset{}{𝐱}})=P\{|^c\}(𝐱_{})+P\{,j\}(𝐱_{},x_j,\underset{^cj}{\overset{}{𝐱}})+P\{,^cj|j\}(𝐱_{},\underset{^cj}{\overset{}{𝐱}})$$
(13)
Inequality (12), equation (13) and condition $`\underset{^cj}{\overset{}{𝐱}}=\underset{^cj}{\overset{}{𝐳}}`$ allows to conclude

$$P\{\}(𝐱_{},\underset{^c}{\overset{}{𝐱}})P\{\}(𝐱_{},\underset{^c}{\overset{}{𝐳}}).$$
(14)
To prove (14) for an arbitrary pair $`\underset{^c}{\overset{}{𝐱}}\underset{^c}{\overset{}{𝐳}}`$ it is enough to use monotone increasing sequence of boundary vectors $`\underset{^c}{\overset{}{𝐱}}<\underset{^c,1}{\overset{}{𝐱}}<\mathrm{}<\underset{^c,k}{\overset{}{𝐱}}<\underset{^c}{\overset{}{𝐳}}`$ that differ with one coordinate only. ∎

Theorem 6 allows to describe some properties of the set of solutions

$$=\left\{\underset{𝐱}{argmin}P(𝐱)\right\}.$$

###### Corollary 7.

Let $`\underset{^c}{\overset{}{𝐱}}\underset{^c}{\overset{}{𝐳}}`$ be any ordered pair of vectors, then:

(i) for any $`𝐱_𝒟^{}(\underset{𝒟^c}{\overset{}{𝐱}})`$ there exists a solution $`𝐳_𝒟^{}(\underset{𝒟^c}{\overset{}{𝐳}})`$ such that $`𝐱_𝒟^{}𝐳_𝒟^{}`$.

(ii) For any $`𝐳_𝒟^{}(\underset{𝒟^c}{\overset{}{𝐳}})`$ there exists a solution $`𝐱_𝒟^{}(\underset{𝒟^c}{\overset{}{𝐱}})`$ such that $`𝐱_𝒟^{}𝐳_𝒟^{}`$.

(iii) The sets $`(\underset{𝒟^c}{\overset{}{𝐱}})`$ and $`(\underset{𝒟^c}{\overset{}{𝐳}})`$ have minimal $`\underset{¯}{𝐱}_𝒟^{},\underset{¯}{𝐳}_𝒟^{}`$ and maximal $`\overline{𝐱}_𝒟^{},\overline{𝐳}_𝒟^{}`$ elements.

(iv) The minimal and maximal elements are ordered, i.e. $`\underset{¯}{𝐱}_𝒟^{}\underset{¯}{𝐳}_𝒟^{}`$ and $`\overline{𝐱}_𝒟^{}\overline{𝐳}_𝒟^{}.`$

The sentences (*i*) and (*ii*) follow directly from Theorem 6. Sentence (*iii*) is deduced from Theorem 6 for $`\underset{^c}{\overset{}{𝐱}}=\underset{^c}{\overset{}{𝐳}}.`$ And, at last, (*iv*) can be derived from (*i,ii*) and definitions of minimal and maximal elements.

## 4 Modified SFM Algorithm

The main idea of the *Modified SFM algorithm* (MSFM) is to determine (if possible) parts of a solution $`𝐱^{}=`$ by use separate parts $`P\{𝒟_i\}(𝐱_{𝒟_i},𝐱_{𝒟_i^c}),`$ $`(𝒟_i𝒟_j=\mathrm{},𝒟_i=𝒱)`$ of the original polynomial $`P(𝐱)`$. For this purpose monotone dependence of local solutions $`𝐱_{𝒟_i}^{}`$ (in the sense of Corollary 7) on the frontier vector $`𝐱_{_i^c}`$ can be exploited. If the vector $`𝐱_{𝒟_i}^{}(\mathrm{𝟏}_{_i^c})`$ has some coordinates $`x_j^{}=0`$, then there is a solution $`𝐱^{}`$ with the same coordinates $`x_j^{}=0`$. Similarly, if the solution $`𝐱_{𝒟_i}^{}(\mathrm{𝟎}_{_i^c})`$ is with coordinates $`x_j^{}=1`$, then there is a solution $`𝐱^{}`$ that has $`x_j^{}=1.`$

The strategy developed leads to success not for all Boolean polynomials, but it is useful for polynomials that have local dependence of variables. Such polynomials are quite often used in applications, for instance, in Bayesian estimation or image processing.

Describe the MSFM in details. Partition the set $`𝒱`$ by suitable sets $`𝒟_i(1),\mathrm{},𝒟_{k_1}(1)`$ $`(𝒟_i(1)𝒟_j(1)=\mathrm{},𝒟_i(1)=𝒱).`$ It follows from Proposition 5 that $`𝐱_{𝒟_i(1)}^{}(𝐱_{𝒟_i^c(1)}^{}),`$ i.e. $`𝐱_{D_i(1)}^{}`$ minimizes the polynomial $`P\{𝒟_i\}(𝐱_{𝒟_i},𝐱_{𝒟_i(1)}^{}).`$ Corollary 7 substantiates existence of triple of solutions

$$𝐱_{0,𝒟_i(1)}(\mathrm{𝟎}_{𝒟_i^c(1)}),𝐱_{1,𝒟_i(1)}(\mathrm{𝟏}_{𝒟_i^c(1)})\text{and}𝐱_{D_i(1)}^{}(𝐱_{𝒟_i^c(1)}^{})$$

such that $`𝐱_{0,𝒟_i(1)}𝐱_{𝒟_i(1)}^{}𝐱_{1,𝒟_i(1)}`$ (the vectors can be found by the usual SFM algorithm). Therefore, solutions $`𝐱_{𝒟_i(1)}^{}`$ have coordinates $`x_{𝒟_i(1),j}^{}=0`$ for sets of indices $`_i(1)=\{j𝒟_i(1)|x_{1,D_i(1),j}=0\}`$ as well as they have coordinates $`x_{D_i(1),j}^{}=1`$ for sets of indices $`𝒲_i(1)=\{j𝒟_i(1)|x_{0,𝒟_i(1),j}=1\}.`$

Check the set $`(1)=_{i=1}^{k_1}(𝒲_i(1)_i(1))`$. If it is empty we either try another partition or start the standard SFM for the original polynomial $`P(𝐱).`$

If $`(1)\mathrm{}`$, we identified the part of the solution $`𝐱_{(1)}^{}=𝐱_{(1)}^{}`$. Set $`𝒱(2)=𝒱\backslash (1)`$ and consider the reduced problem of identification of

$$𝐱_{𝒱(2)}^{}=\underset{𝐱_{𝒱(2)}}{argmin}P(𝐱_{𝒱(2)},𝐱_{(1)}^{}).$$

Partition $`𝒱(2)=_{i=1}^{k_2}𝒟_i(2),𝒟_i(2)𝒟_j(2)=\mathrm{}`$ and estimate $`𝐱_{𝒟_i(2)}^{}`$ by solutions

$$𝐱_{0,𝒟_i(2)}(\mathrm{𝟎}_{𝒟_i^c(2)\backslash (1)},𝐱_{(1)}^{})\text{and}𝐱_{1,𝒟_i(2)}(\mathrm{𝟏}_{𝒟_i^c(2)\backslash (1)},𝐱_{(1)}^{}),$$

using sets $`_i(2)=\{j𝒟_i(2)|x_{1,D_i(2),j}=0\}`$ and $`𝒲_i(2)=\{j𝒟_i(2)|x_{0,𝒟_i(2),j}=1\}`$ (Corollary 7 grounds existence of triple of vectors $`𝐱_{0,𝒟_i(2)}𝐱_{𝒟_i(2)}^{}𝐱_{1,𝒟_i(2)}`$ ). The algorithm is iterated at high levels until the problem will be completely solved or until $`(l)\mathrm{}`$. In the last case the standard SFM is after applied. Sizes of partitioning sets $`𝒟_i(l)`$ should be sufficient to have $`(l)`$ nonempty but not very large to have small enough number of operations. It is unlikely possible to estimate them in general case since for some polynomials the MSFM is reduced to the usual SFM for any partition. However, in many applied problems of image processing or Bayesian estimation the finding suitable sizes of $`𝒟_i(l)`$ is not difficult. In these problems energy functions usually have lack of long distance interactions (or phase transitions). It means solutions $`𝐱_𝒟^{}`$ for the original image and an image, which coincides with the original on sufficiently large set $`𝒟𝒱`$ and differs from it on $`𝒟^c`$, are approximately equal. By other words, for real applications estimates of image details do not depend on its surrounding objects. In this case the MSFM is preferable to the standard SFM. The number operation required can be here even $`O(n)`$.

The identification of $`𝐱_{_i(l){\scriptscriptstyle 𝒲_i(l)}}^{}`$ can be done in concurrent mode. The number of levels depend on the polynomial $`P`$. Usually, it is enough two or three ones. Formal description of the MSFM is rather simple. It is placed in Fig.1.

MSFM($`P`$):       Initialization:    $`m`$ $``$ $`1`$ the enumerator of levels    $`L`$ $``$ a number of levels    $`𝒱(1)`$ $``$ $`𝒱`$    $`\{𝒟_i(1)\}`$ $``$ a partition of $`𝒱`$    $`\{𝐱_{0,𝒟_i(1)},𝐱_{1,𝒟_i(1)}\}`$ $``$ such that $`𝐱_{0,𝒟_i(1)}𝐱_{1,𝒟_i(1)}`$, by the SFM    $`\{_i(1),𝒲_i(1)\}`$ $``$ coordinates of the part of the solution found    $`(1)`$ $``$ $`_{i=1}^{k_1}(𝒲_i(1)_i(1))`$   If $`(1)=\mathrm{}`$ then use the SFM, *Stop*    $`x_{𝒟_i(1),j}^{}`$ $``$ $`0`$ for $`j_i(1)`$    $`x_{𝒟_i(1),j}^{}`$ $``$ $`1`$ for $`j𝒲_i(1)`$   While $`m<L`$ do    $`m`$ $``$ $`m+1`$    $`𝒱(m)`$ $``$ $`𝒱(m1)\backslash (m1)`$    $`\{𝒟_i(m)\}`$ $``$ partition of $`𝒱(m)`$    $`P_l(𝐱_{𝒱(m)})`$ $``$ the residual polynomial $`P(𝐱_{𝒱(m)},𝐱_{𝒱^c(m)}^{})`$    $`\{𝐱_{0,𝒟_i(m)},𝐱_{1,𝒟_i(m)}\}`$ $``$ such that $`𝐱_{0,𝒟_i(m)}𝐱_{1,𝒟_i(m)}`$, by the SFM      for $`P_l(𝐱_{𝒱(m)})`$    $`\{_i(m),𝒲_i(m)\}`$ $``$ coordinates of the part of the solution found    If $`_{i=1}^{k_m}\left(𝒲_i(m)_i(m)\right)=\mathrm{}`$ then use the SFM, *Stop*    $`(m)`$ $``$ $`(m1)(_{i=1}^{k_m}(𝒲_i(m)_i(m))`$)    $`x_{𝒟_i(m),j}^{}`$ $``$ $`0`$ for $`j_i(m)`$    $`x_{𝒟_i(m),j}^{}`$ $``$ $`1`$ for $`j𝒲_i(m)`$   If $`(L)\mathrm{}`$ then use the SFM   Return $`𝐱^{}`$   End

Fig.1

## 5 Representability of Some Submodular Polynomials by Graphs

Recently Kolmogorov&Zabih  have described some class of functions $`V(𝐱)`$ in Boolean variables $`𝐱=(x_1,\mathrm{},x_n)`$ that permit minimization by the graph cut technique. For convenience we reformulate and then use their results in terms of Boolean polynomials. We also represent some submodular Boolean polynomials by graphs to make possible their efficient minimization via graph gut technique (recall that finding the minimum graph cut requires $`O(N^3)`$ operations on number $`N`$ of nodes).

Let the network $`\mathrm{\Gamma }=(𝒮,𝒜)`$ consist of $`N+2`$ numbered nodes $`𝒮=\{0,\mathrm{},N+1\}`$, where $`s=0`$ is the *source*, $`t=N+1`$ is the *sink* and $`𝒱^{}=\{1,\mathrm{},N\}`$ are usual nodes. The set of directed arcs is $`𝒜=\{(i,j):i,j𝒮\}`$. The capacities of arcs are denoted by $`d_{i,j}>0`$.

The *cut* (we use this term as abbreviation of the term *s-t cut*) is a partition of the set $`𝒮`$ by two disjoint sets $`W,B`$ such that $`sW`$ and $`tB`$. For any cut $`(W,B)`$ nodes $`iW`$ will be labeled by $`z_i=1`$ and nodes $`iB`$ – by $`z_i=0`$ so that there is one-to-one map between cuts and Boolean vectors $`𝐳=(z_1,\mathrm{},z_N)`$.

### 5.1 Graph representability

In  the following definition of graph representability is given.

###### Definition 8.

A function $`V(𝐱)`$ of $`n`$ Boolean variables is called graph representable if there exists a network $`\mathrm{\Gamma }=(𝒮,𝒜)`$ with number of nodes $`Nn`$ and the cost function $`C(𝐳)`$ such that for some constant  c

$$V(𝐱)=\underset{z_{n+1},\mathrm{},z_N}{\mathrm{min}}C(x_1,\mathrm{},x_n,z_{n+1},\mathrm{},z_N)+\text{ c }.$$

Costs of the graph cuts $`C(𝐳)`$ are equal to values of the quadratic Boolean polynomial $`p(𝐳)`$ of the form (see, ).

$$C(𝐳)=p(𝐳)=\underset{i𝒱}{}d_{s,i}(1z_i)+\underset{i𝒱}{}d_{i,t}z_i+\underset{i,j𝒱}{}d_{i,j}(z_iz_j)z_i+\text{ c },d_{i,j},\text{ c }0.$$
(15)
Therefore, we can give an equivalent definition of the graph representability.

###### Definition 9.

We say a function $`V(𝐱)`$ of $`n`$ Boolean variables can be represented by graph if there exists a quadratic polynomial $`𝐩(𝐳)`$ of $`N(Nn)`$ Boolean variables of the form (15), which satisfies the equality

$$V(𝐱)=\underset{z_{n+1},\mathrm{},z_N}{\mathrm{min}}𝐩(x_1,\mathrm{},x_n,z_{n+1},\mathrm{},z_N)+\text{ c }.$$

The class $`^2`$ of Boolean functions that are often used in applications and that are, actually, quadratic Boolean polynomials

$$V^2V(𝐱)=P_V(𝐱)=\underset{1ln}{}a_lx_l+\underset{1l_1<l_2n}{}a_{l_1,l_2}x_{l_1}x_{l_2}+\text{ c }.$$
(16)
was considered in . The characterization of the graph representability of $`V^2`$ in terms of Boolean polynomials has been done. It can be used, in particular, to minimize functions of integer variables.

###### Theorem 10.

A function $`V^2`$ is graph representable if and only if all quadratic coefficients of its polynomial representation $`P_V(𝐱)`$ are nonpositive, i.e. $`a_{l_1,l_2}0`$. Therefore, in order to function $`V^2`$ be graph representable it is necessary an sufficient it will be submodular.

The sufficiency of the Theorem follows immediately from Definition 9 and Proposition 4 a). The necessity will be proven below for more general case. The following result has been proven in  by graph cut technique.

###### Theorem 11.

In order to polynomial $`P(𝐱)`$ of degree $`m`$ can be represented by a graph it should be submodular.

###### Proof.

To prove this sentence we use representation (7) of the polynomial $`P(𝐱)`$ at page 6. For arbitrary couple of indices $`i,j`$ let us fixed the vector $`𝐱_{\{i,j\}^c}`$. Since $`P(𝐱)`$ is graph representable the quadratic polynomial $`x_ix_jP_{i,j}(𝐱_{\{i,j\}^c})`$ of two variables $`x_i,x_j`$ is graph representable, as well. That is

$$x_ix_jP_{i,j}(𝐱_{\{i,j\}^c})=\underset{z_{n+1},\mathrm{},z_N}{\mathrm{min}}𝐩(x_1,x_2,z_{n+1},\mathrm{},z_N)+\text{ c }$$

(in general, the quadratic submodular polynomial $`𝐩`$ and  c  depend on $`𝐱_{\{i,j\}^c}`$ but it is fixed now). Suppose $`P_{i,j}(𝐱_{\{i,j\}^c})>0`$. Then $`𝐩`$ has at least two values of the argument $`(x_1,x_2,z_{n+1},\mathrm{},z_N)`$ that minimize the polynomial globally. One of them is with coordinates $`(0,1,\mathrm{})`$, and the other is of the form $`(1,0,\mathrm{})`$. Because of submodularity of $`𝐩`$ it follows from Corollary 7 (i) there exists the third vector, which minimizes $`p`$ globally. This vector has coordinates $`(1,1,\mathrm{})`$. The existence of such the vector contradicts with the assumption $`P_{i,j}(𝐱_{\{i,j\}^c})>0`$. Therefore, $`P_{i,j}(𝐱_{\{i,j\}^c})0`$ for any couple of indices $`i,j`$ and vector $`𝐱_{\{i,j\}^c}`$ and the sentence of the Theorem follows from Corollary 4 a). ∎

### 5.2 Graph represtability of some subset of submodular polynomials

The submodularity is necessary condition in order to a Boolean polynomial can be represented by a graph. Below we prove representability by graphs of some subset $`𝒫_{suf}`$ of submodular polynomials. To define this subset we use formula (7) at page 6. Let $`b_{l_1,\mathrm{},l_m}(i,j)=a_{l_1,\mathrm{},i,\mathrm{},j,\mathrm{},l_m}`$, $`(l_1<\mathrm{}<i<\mathrm{}<j<\mathrm{}<l_m,m=0÷n2)`$ be coefficients of $`P_{i,j}(𝐱_{\{i,j\}^c})`$ and $`b_{l_1,l_2,\mathrm{},l_m}^+(i,j)`$ be the positive ones (note that $`b(i,j)=a_{i,j}<0`$). Let the set of polynomials

$$𝒫_{suf}=\left\{P\right|a_{i,j}+\underset{m=1}{\overset{n2}{}}\underset{l_1<l_2<\mathrm{}<l_m}{}b_{l_1,l_2,\mathrm{},l_m}^+(i,j)0,i,j𝒱\}.$$

This set is a proper subset of all submodular polynomials $`𝒫_{submod}`$ (see Proposition 4 a)). It contains, for instance, the set $`_{}^m=\{P|a_{l_1,l_2,\mathrm{},l_k}0,k=2÷m\}`$ of Boolean polynomials with all coefficients of nonlinear monomials nonpositive and the set $`_+^m=\{P|P𝒫_{submod},a_{l_1,l_2,\mathrm{},l_k}0,k=3÷m\}`$ of submodular polynomials with all coefficients of order more than two nonnegative.

###### Remark 1.

Note the condition

$$a_{i,j}+\underset{m=1}{\overset{n2}{}}\underset{l_1<l_2<\mathrm{}<l_m}{}b_{l_1,l_2,\mathrm{},l_m}^+(i,j)0,i,j𝒱$$

is necessary and sufficient in order to the polynomial, which has all coefficients of order more than two positive (i.e. $`P𝒫_{submod}`$), be submodular.

Polynomials of those types can be used, for instance, in image processing for recognition of images or Bayesian estimation. To prove representability of $`P𝒫_{suf}`$ by graphs we need two lemmas, which give a constructive tool to build a corresponding graph as well.

###### Lemma 12.

For any natural $`m`$ and real $`a<0`$ the Boolean polynomial $`ax_1x_2\mathrm{}x_m`$ is graph representable.

The graph that represents $`ax_1x_2\mathrm{}x_m`$ is drawn in Fig.2. It needs one additional node $`z`$. The corresponding polynomial is $`p(x_1,x_2,\mathrm{},x_m,z)=a_{i=1}^m(zx_i)z+az`$. If at least one $`x_i=0`$, then $`\mathrm{min}_zp(x_1,x_2,\mathrm{},x_m,z)=0`$ otherwise $`\mathrm{min}_zp(1,1,\mathrm{},1,z)=a`$. Hence, $`ax_1x_2\mathrm{}x_m`$ $`=\mathrm{min}_zp(x_1,x_2,\mathrm{},x_m,z).`$

The monomials of order greater than $`2`$ with positive coeffisients can not be represented by graphs directly. To do it we should accompany those positive monomials by quadratic items with large enough negative coefficients. It requires additional nodes in graphs that represent the monomials.

Fig.2

###### Lemma 13.

For any natural $`m>2`$ and $`a>0`$ the Boolean polynomial $`P(x_1,x_2,\mathrm{},x_n)=ax_1x_2\mathrm{}x_ma_{1i<jm}x_ix_j`$ is graph representable.

###### Proof.

In order to prove the Lemma we construct for each $`m>2`$ a quadratic Boolean polynomial that specifies graph (the examples of graphs for $`m=3÷6`$ are drawn in Fig.3 at page 5.2). The number of additional variables of this polynomial is $`l={\displaystyle \frac{m1}{2}}`$ if $`m`$ is odd and is $`l={\displaystyle \frac{m2}{2}}`$ if $`m`$ is even. It is of the form

$$p(x_1,\mathrm{},x_m,z_1,\mathrm{},z_l)=\underset{j=1}{\overset{l}{}}b_j\underset{i=1}{\overset{m}{}}(z_jx_i)z_j+\underset{j=1}{\overset{l}{}}e_jz_j$$
(17)
with all $`b_j>0`$ and $`e_j<0`$, such that the minimum of $`p`$ with respect to $`z_1,\mathrm{},z_l`$ is equal to corresponding values of $`P`$. Those values are

$$P(x_1,x_2,\mathrm{},x_m)=\{\begin{array}{cc}0,\hfill & \text{if all}x_i=0,\hfill \\ 0,\hfill & \text{if}x_{i_1}=1\text{and}x_{i_2}=\mathrm{}=x_{i_m}=0\hfill \\ a\left(\genfrac{}{}{0pt}{}{k}{2}\right),\hfill & \text{if}x_{i_1}=\mathrm{}=x_{i_k}=1\text{and}x_{i_{k+1}}=\mathrm{}=x_{i_m}=0\hfill \\ & \\ a\left(\genfrac{}{}{0pt}{}{m}{2}\right)+a,\hfill & \text{if}x_1=\mathrm{}=x_m=1.\hfill \end{array}$$

Let the vector $`\mathrm{𝟏}_k=(\stackrel{m}{\stackrel{}{\underset{k}{\underset{}{1,\mathrm{},1}},0,\mathrm{},0}})`$. The polynomial $`p`$ (as well as $`P`$) is symmetrical with respect to $`x_1,\mathrm{},x_m`$. It has the same value $`p(\mathrm{𝟏}_k)=_{j=1}^l((mk)b_j+e_j)z_j`$ for all permutations of $`\mathrm{𝟏}_k`$. Therefore, the set of inequalities should hold true

$$\{\begin{array}{cc}\underset{j=1}{\overset{l}{}}(mb_j+e_j)z_j\hfill & 0\hfill \\ \underset{j=1}{\overset{l}{}}((m1)b_j+e_j)z_j\hfill & 0\hfill \\ \underset{j=1}{\overset{l}{}}((m2)b_j+e_j)z_j\hfill & a\hfill \\ \mathrm{}\hfill & \\ \underset{j=1}{\overset{l}{}}((mk)b_j+e_j)z_j\hfill & a\left(\genfrac{}{}{0pt}{}{k}{2}\right)\hfill \\ \mathrm{}\hfill & \\ \underset{j=1}{\overset{l}{}}(b_j+e_j)z_j\hfill & a\left(\genfrac{}{}{0pt}{}{m1}{2}\right)\hfill \\ \underset{j=1}{\overset{l}{}}e_jz_j\hfill & a\left(\genfrac{}{}{0pt}{}{m}{2}\right)+a\hfill \end{array}$$
(18)
together with the additional condition:

(M) *There exist vectors $`\{𝐳_k^{}\}`$ that turn corresponding inequalities into equality.*

For any odd $`m>2`$ we propose one of possible collections of variables $`b_i,e_i`$ that satisfy (18) for Boolean variables $`(z_1,\mathrm{},z_m)`$ as well as condition (M). The collection is identified by the following system of equations

$`\{\begin{array}{cc}\left((m2)b_1+e_1\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{2}{2}}\right)\hfill \\ \left((m3)b_1+e_1\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{3}{2}}\right)\hfill \\ \left((m4)b_1+e_1\right)+\left((m4)b_2+e_2\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{4}{2}}\right)\hfill \\ \left((m5)b_1+e_1\right)+\left((m5)b_2+e_2\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{5}{2}}\right)\hfill \\ \mathrm{}\hfill & \\ \underset{j=1}{\overset{k}{}}\left((m2k)b_j+e_j\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{2k}{2}}\right)\hfill \\ \underset{j=1}{\overset{k}{}}\left((m2k1)b_j+e_j\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{2k+1}{2}}\right)\hfill \\ \mathrm{}\hfill & \\ \underset{j=1}{\overset{l}{}}\left(b_j+e_j\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{m1}{2}}\right)\hfill \\ \underset{j=1}{\overset{l}{}}e_j\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{m}{2}}\right)+a\hfill \end{array}`$ (19)
It is

$`b_1`$ $`=b_2=\mathrm{}=b_{l1}=2a,b_l=a,`$
$`e_j`$ $`=(2m4j+1)a,(j=1÷l1),e_l=2a.`$
Since the inequalities

$`(m1)b_j+e_j>0,j=1÷l,`$
$`(m2k)b_j+e_j<0,(m2k1)b_j+e_j<0,\text{if}jk,k=1÷l1,`$
$`(m2k)b_j+e_j>0,(m2k1)b_j+e_j>0,\text{if}j>k,k=1÷l1,`$
$`b_j+e_j<0,j=1÷l,`$
$`e_j<0,j=1÷l.`$
hold true, the solution (5.2) actually satisfies inequality (18) together with condition (M) for vectors $`𝐳_1^{}=𝐳_2^{}=\mathrm{𝟎},𝐳_3^{}=𝐳_4^{}=\mathrm{𝟏}_1,\mathrm{},𝐳_{2k+1}^{}=𝐳_{2k+2}^{}=\mathrm{𝟏}_k,\mathrm{},𝐳_m^{}=𝐳_{m+1}^{}=\mathrm{𝟏}_l`$ .

For even $`m>2`$ the collection of $`l={\displaystyle \frac{m2}{2}}`$ variables $`b_i,e_i`$ can be found as a solution of the system of equation

$`\{\begin{array}{cc}\left((m2)b_1+e_1\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{2}{2}}\right)\hfill \\ \left((m3)b_1+e_1\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{3}{2}}\right)\hfill \\ \left((m4)b_1+e_1\right)+\left((m4)b_2+e_2\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{4}{2}}\right)\hfill \\ \left((m5)b_1+e_1\right)+\left((m5)b_2+e_2\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{5}{2}}\right)\hfill \\ \mathrm{}\hfill & \\ \underset{j=1}{\overset{k}{}}\left((m2k)b_j+e_j\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{2k}{2}}\right)\hfill \\ \underset{j=1}{\overset{k}{}}\left((m2k1)b_j+e_j\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{2k+1}{2}}\right)\hfill \\ \mathrm{}\hfill & \\ \underset{j=1}{\overset{l}{}}\left(2b_j+e_j\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{m2}{2}}\right)\hfill \\ \underset{j=1}{\overset{l}{}}\left(b_j+e_j\right)\hfill & =a\left({\displaystyle \genfrac{}{}{0pt}{}{m1}{2}}\right)\hfill \end{array}`$ (21)
that looks similar to (19) but consists of only $`m`$ equations, since the equation

$$\underset{j=1}{\overset{l}{}}e_jz_j=a\left(\genfrac{}{}{0pt}{}{m}{2}\right)+a$$

follows from the last two ones of system (21). The solution of the system is

$$b_j=2a,e_j=(2m4j+1)a,j=1÷l.$$
(22)
Again the inequalities

$`(m1)b_j+e_j>0,j=1÷l,`$
$`(m2k)b_j+e_j<0,(m2k1)b_j+e_j<0,\text{if}jk,k=1÷l,`$
$`(m2k)b_j+e_j>0,(m2k1)b_j+e_j>0,\text{if}j>k,k=1÷l,`$
hold true and, therefore, (18) together with condition (M) is fulfilled for vectors $`𝐳_1^{}=𝐳_2^{}=\mathrm{𝟎},𝐳_3^{}=𝐳_4^{}=\mathrm{𝟏}_1,\mathrm{},𝐳_{2k+1}^{}=𝐳_{2k+2}^{}=\mathrm{𝟏}_k,\mathrm{},𝐳_{m1}^{}=𝐳_m^{}=𝐳_{m+1}^{}=\mathrm{𝟏}_l`$ .

So, the coefficients of the polynomial $`𝐩`$ (see (17)) that represents $`P`$ for odd and even $`m`$ are determined by (5.2) and (22). ∎

Lemmas 12 and 13 allow to prove each $`P𝒫_{suf}`$ can be represented by a graph.

Fig.3

###### Theorem 14.

The polynomials $`P𝒫_{suf}`$ are graph representable.

In order to proof the Theorem it is enough to use Lemma 12 to represent nonlinear items of $`P`$ with negative coefficients and, then, to exploit Lemma 13 to determine that all items with positive coefficients can be accompanied by quadratic monomials and after be represented by graphs as well.

Let the Boolean polynomial $`P(x_1,\mathrm{},x_n)𝒫_{suf}`$ of degree $`m`$ consists of $`L_h`$ monomials of degree more than two, then it can be represented by a graph with $`\frac{L_h(m1)}{2}+n`$ nodes. The worst case is when $`P(x_1,\mathrm{},x_n)_+^m`$. The polynomial $`P(x_1,\mathrm{},x_n)_{}^m`$ can be represented by a graph with $`L_h+n`$ nodes. Hence, the global minimization of $`P(x_1,\mathrm{},x_n)𝒫_{suf}`$ require less than $`O\left(\frac{L_h(m1)}{2}+n\right)^3`$ operations, though for some classes of polynomials that occur in applications the number of operations can be reduced even to $`O\left(\frac{L_h(m1)}{2}+n\right)`$ (see, ).


format: text

text:
# Locally accessible information: How much can the parties gain by cooperating?

## Abstract

We investigate measurements of bipartite ensembles restricted to local operations and classical communication and find a universal Holevo-like upper bound on the locally accessible information. We analyze our bound and exhibit a class of states which saturate it. Finally, we link the bound to the problem of quantification of the nonlocality of the operations necessary to extract locally unaccessible information.

The problem of local distinguishability of orthogonal quantum states has direct implications on the use of quantum correlations as a resource in quantum information theory. Although there is no clear universal delineation of what is and what is not possible for parties restricted to local operations and classical communication (LOCC), a number of interesting, often counterintuitive results have been reached. E.g., *any* two pure orthogonal states can be distinguished locally as well as globally Walgate . On the other hand, there are ensembles of orthogonal *product* states which cannot be locally distinguished Bennet1 ; Bennet2 . Moreover, there are ensembles of locally distinguishable orthogonal states, for which one can destroy local distinguishability by *reducing* the average entanglement of the ensemble states LocDisting1 .

Naturally, one would like to *quantify* the message contained in all these examples (cf. Terhal ; Bennet1 ). When there are no restrictions on the allowed measurement strategy, the classical information about the identity of the state in an ensemble $`Q=\{p_x,\varrho ^x\}`$, accessible to a measurement is limited by the Holevo bound Holevo :

$$I_{acc}\chi _QS(\varrho )\underset{x}{}p_xS(\varrho ^x),$$
(1)
where $`\varrho =_xp_x\varrho ^x`$ and $`S`$ is von Neumann entropy. A fundamental message carried by this bound is that
*The amount of information that can be sent via $`n`$ qubits is bounded by $`n`$ bits.*
In the present contribution, we will generalize bound (1) to the case when the information is coded in bipartite states and the allowed measurement strategies are limited to LOCC-based measurements. We show that for any asymptotic measure of entanglement $`E`$,
*The amount of locally accessible information locally-LOCC  that can be sent via $`n`$ qubits with average entanglement $`\overline{E}`$ is bounded by $`n\overline{E}`$ bits.*
We then discuss the possible saturation of our bound. Also, we link the bound to entanglement manipulations.

We begin by considering a quantum ensemble $`\{p_x,\varrho _x\}`$ and the mutual information $`I(X:Y)`$ between the signals $`X`$ and the measurement results $`Y`$ accessible in sequential measurements. In the first step, the measurement $`_1`$ produces outcome $`aY_1`$ with probability $`p_a`$. In the second step, measurement $`_2^a`$ (choice of $`_2`$ may depend on the result ($`a`$) of $`_1`$) gives outcomes $`b_aY_2`$, etc. For such measurements, $`I(X:Y)I(X:Y_1,Y_2,\mathrm{})`$. The well known chain rule for mutual information (see e.g. CoverThomas ) allows one to express the right-hand side of this identity in terms of the information gains in the single measurement steps, $`I_A^1I(X:Y_1)`$, $`I_B^2I(X:Y_2|Y_1)=_ap_aI(X:Y_2|Y_1=a)`$, etc. The chain rule reads

$$I(X:Y_1,Y_2,\mathrm{})=I(X:Y_1)+I(X:Y_2|Y_1)+\mathrm{}.$$
(2)
In other words, the total mutual information is the sum of the contributions obtained in the consecutive steps. A multi-step-measurement can be viewed as a tree; total mutual information is then equal to the sum of the average mutual information obtained at each level.

In addition to the chain rule, in order to proceed, we will need to adapt the Holevo bound to sequential measurements, as given by the following lemma.

###### Lemma 1

If a measurement on ensemble $`Q=\{p_x,\varrho _x\}`$ produces result $`y`$ and leaves a post-measurement ensemble $`Q^y=\{p_{x|y},\varrho _{x|y}\}`$ with probability $`p_y`$, then information $`I^{\left(1\right)}`$ extracted from the measurement is bounded by

$$I^{(1)}\chi _Q\overline{\chi }_Q^y.$$
(3)
where $`\overline{\chi }_Q^y`$ is the average Holevo bound for the possible post-measurement ensembles.

To prove the lemma, we consider a system consisting of the state identifiers ($`X`$), the ensemble ($`Q`$)and the measuring device ($`Y`$).

Before the measurement, system $`XQY`$ is in the state$`.\rho _{XQY}=_xp_x|xx|\rho _x|0_Y0|`$. The measurement changes it to $`\rho _{XQY}^{}=_xp_x|xx|V_y\rho _xV_y^{}|yy|`$ which can be rewritten as $`\rho _{XQY}^{}=_yp_y_xp_{x|y}|xx|\rho _x^y|yy|,`$ where $`\rho _x^y=V_y\rho _xV_y^{}/p_{y|x}`$. We may further notice that $`\overline{\chi }_Q^y=_yp_y[S(_xp_{x|y}\rho _x^y)_xp_{x|y}S(\rho _x^y)]`$ as well as $`I^{(1)}=I_M(\rho _{X:Y}^{})`$ and $`\chi _Q=I_M(\rho _{X:Q})`$ where $`I_M`$ is quantum mutual information, i.e. $`I_M(\rho _{X:Y})=S_X+S_YS_{XY}`$.

Since quantum mutual information cannot increase under local map we have

$$I_M(\rho _{X:QY}^{})I_M(\rho _{X:Q})=\chi _Q.$$
(4)
On the other hand, the chain rule requires that $`I_M\left(\rho _{X:QY}^{}\right)=I_M\left(\rho _{X:Y}^{}\right)+I_M\left(\rho _{X:Q|Y}^{}\right)`$. The first term here is $`I^{\left(1\right)}`$, the second is $`\overline{\chi }_Q^y`$, which together with (4) gives the claimed inequality (3) and the lemma.

The chain rule, together with the lemma and a little algebra allow us to prove the following theorem.

###### Theorem 1

Given ensemble $`\{p_x,\varrho _{AB}^x\}`$ of quantum states $`\varrho _{AB}^x`$ on a bipartite system, the maximal mutual information $`I(X:Y)`$ accessible via LOCC between $`A`$ and $`B`$ satisfies the following inequality

$$I_{acc}^{LOCC}S(\varrho _A)+S(\varrho _B)\underset{Z=A,B}{\mathrm{max}}\underset{x}{}p_xS(\varrho _Z^x),$$
(5)
where $`\varrho _A`$ and $`\varrho _B`$ are the reductions of $`\varrho _{AB}=_xp_x\varrho _{AB}^x`$, and $`\varrho _Z^x`$ is a reduction of $`\varrho _{AB}^x`$.

In addition to the chain rule and the lemma, in order to prove the theorem we will need the following two facts:
(i) Knowledge of Alice’s result may reduce the entropies of Bob’s parts of the ensemble states. The average reduction, $`\mathrm{\Delta }\overline{S}_B^x`$ cannot, however, exceed either $`S_B^x`$ (the final entropies cannot be negative) or the corresponding decrease in the entropy of the Alice’s parts of the states, $`\mathrm{\Delta }\overline{S}_A^x`$ (a measurement on $`A`$ cannot reveal more information about $`B`$ than about $`A`$). Also $`\mathrm{\Delta }\overline{S}_B^x\overline{S}_A^x`$.
(ii) Concavity of entropy and the fact that Alice’s measurement does not change Bob’s density matrix $`\varrho _B=_ap_a\varrho _B^{|a}`$ (Bob’s ensemble density matrix after he has learned that Alice’s result was $`a`$ (with probability $`p_a`$) is denoted by $`\varrho _B^{|a}`$) require that Alice’s measurement does not increase entropy of Bob’s part of the ensemble, i.e. $`_ap_aS(\varrho _B^{|a})S(\varrho _B)`$.

For definiteness, let Alice make the first measurement, Bob the second, Alice the third, etc. By the chain rule, the total information gain in this sequence is given by $`I_{acc}^{LOCC}=_{s=1}I_Z^s`$ with $`Z`$ denoting Alice when $`s`$ is odd and Bob when $`s`$ is even. The lemma bounds this as follows:

$$\begin{array}{ccc}I_{acc}^{LOCC}\hfill & \hfill & \left(\chi _A\overline{\chi }_A^1\right)+\left(\overline{\chi }_A^2\overline{\chi }_A^3\right)+\mathrm{}\hfill \\ & +\hfill & \left(\chi _B^1\overline{\chi }_B^2\right)+\left(\overline{\chi }_B^3\overline{\chi }_B^4\right)+\mathrm{}\hfill \end{array}$$
(6)
This inequality can be easily combined with the quoted fact (ii) into the following bound on information accessible in a multi-step local measurement:

$$I_{acc}^{LOCC}S_A+S_B\overline{S}_A^x\overline{S}_B^x+g_A+g_B.$$
(7)
where $`g_B=\left(\overline{S}_B^x\overline{S}_B^{x|1}\right)+\left(\overline{S}_B^{x|2}\overline{S}_B^{x|3}\right)+\mathrm{}`$is the accumulated reduction of the average entropy of Bob’s part of the signal states due to his knowledge of Alice’s results. Likewise, $`g_A=\left(\overline{S}_A^{x|1}\overline{S}_A^{x|2}\right)+\left(\overline{S}_A^{x|3}\overline{S}_A^{x|4}\right)+\mathrm{}`$ is the accumulated reduction of the average entropy of Alice’s part of the signal states due to her knowledge of Bob’s results. A multiple use of fact (i) immediately implies that $`g_A+g_B\mathrm{min}(\overline{S}_A^x,\overline{S}_B^x)`$, which proves the theorem. $`\mathrm{}`$

While discussing the theorem, note that $`S(\varrho _A)+S(\varrho _B)n`$ ($`n=\mathrm{log}_2d_1d_2`$ for a $`d_1d_2`$ system) and $`\mathrm{max}\{\overline{S}_A^x,\overline{S}_B^x\}\overline{E}_F`$, the average entanglement of formation huge  of the ensemble states. Moreover we know that any asymptotic measure of entanglement is smaller than entanglement of formation limits . This immediately gives the following simple bound on the locally accessible information in ensembles of bipartite states:

$$I_{acc}^{LOCC}n\overline{E}$$
(8)
with $`\overline{E}`$ standing for any asymptotically consistent measure of the average entanglement of the ensemble states. As noted in the beginning, this formulation is a direct analogue of Holevo’s result. It can be seen as “*entanglement correction*” to Holevo bound for LOCC-based measurements. Bound (8) can also be viewed as *a complementarity relation between locally accessible information and the average bipartite entanglement*, once we write it as $`I_{acc}^{LOCC}+\overline{E}n`$ (cf. comp-seijey ). Note also that we have here a unification of the “opposite” facts that any two Bell states are locally distinguishable and that the four Bell states are locally indistinguishable amaderBellPRLPRA . Both cases saturate relation (8). Finally, inequality (8) immediately proves that a complete orthogonal basis of multipartite states must not contain any entangled state if it is to be locally distinguishable LocDisting1  (cf. Chefles ).

The fact that the LOCC restriction imposed on the allowed measurements reduces Holevo bound, brings to mind, associations with coarse-graining. It is a well known fact in mathematical physics, that under a smaller algebra of observables, a given state appears as having increased entropy. Likewise, if one restricts the allowed measurements to LOCC, then the restriction brings some additional entropy on the entangled states, just like that due to coarse-graining. In our case, however, the set of the allowable observables (LOCC) does not have a structure of an algebra. Therefore, the additional entropy brought by the LOCC restriction cannot be easily calculated in general. Moreover, unlike Holevo’s, our bound cannot be universally saturated, even in the asymptotic limit.

A possible additional source of this lack of the saturation is seen by considering an ensemble of $`d`$ pure states $`|i,i`$, $`(i=1,\mathrm{},d)`$ in $`dd`$. This ensemble saturates Holevo bound (the states are also locally distinguishable). On the other hand, any non-trivial measurement on Alice’s side of the ensemble reduces $`S_B`$, thus making Bob’s information gain $`g_B`$ negative, and inequality (5) cannot be saturated. Negative $`g`$, like here, indicates an ensemble where information accessible to Alice overlaps with that to Bob. Ensembles with positive $`g`$ are in a way more interesting. There, Alice’s measurement not only provides valuable information about her local state, it also increases information accessible to Bob. Thus, Alice and Bob will benefit from genuine cooperation while extracting information from such ensembles. A room for this cooperation permitted by LOCC allows one to, e.g., locally distinguish any two pure orthogonal states even if these states are entangled Walgate . Note that inequality (5) can only be saturated when the cooperative gain $`g`$ attains its upper bound. It is then legitimate to ask about the extent to which such a situation is universal. Specifically, in $`d_1d_2`$, with an *arbitrary* average entanglement $`\overline{E}\mathrm{min}\{\mathrm{log}_2d_1,\mathrm{log}_2d_2\}`$, can one always find an ensemble with $`I_{acc}^{LOCC}=n\overline{E}`$ ($`n=\mathrm{log}_2d_1d_2`$)?

Although we were not able to answer the question in full generality, we found an affirmative answer for $`2^{n_1}2^{n_1}`$ systems, by designing a class of the required ensembles. Our ensembles are modifications of the ensemble consisting of the “canonical” set of mutually orthogonal maximally entangled states in $`dd`$ problem-generic . To construct a desired ensemble, we take the states $`a_1|00+a_2|11`$, $`a_2|00+a_1|11`$, $`a_1|01+a_2|10`$ and $`a_2|01+a_1|10`$ in $`22`$. The ensemble consisting of these states with equal prior probabilities saturates (8) for a measurement in the computational basis. The ensemble in $`2^{n_1}2^{n_1}`$ contains then (with equal prior probabilities) all the possible $`n_1`$-times tensor products of the above four states. E.g., if the partners are Alice and Bob, then in $`44`$, the states are $`(a_1|00+a_2|11)_{A_1B_1}(a_1^{^{}}|00+a_2^{^{}}|11)_{A_2B_2}`$, $`(a_1|00+a_2|11)_{A_1B_1}(a_2^{^{}}|00+a_1^{^{}}|11)_{A_2B_2}`$, etc. where $`A_1A_2`$ is at Alice and $`B_1B_2`$ is at Bob. Separate measurements by $`A_1B_1`$ and by $`A_2B_2`$ in their computational bases saturates bound (8) (see 2X3 ).

Having obtained the bound $`n\overline{E}`$ for $`I_{acc}^{LOCC}`$, one would also like to understand the deeper physical principles that facilitate it. This could, among others, help us to generalize the result into a multipartite scenario. In a search for such principles, we linked the bound to the rules of local manipulations of entanglement. This can be regarded as a step towards quantification of the nonlocality of the operations which are required to access locally inaccessible information stored in orthogonal sets of states.

Consider then an ensemble of arbitrary signal states $`\{p_x,\varrho _{AB}^x\}`$ and arbitrary “detector” states $`\{\gamma _{CD}^x\}`$ (cf. Smolin ; amaderBellPRLPRA ; LocDisting1 ). Initially, let the signals and the detectors be in a joint state $`\varrho _{ABCD}=_xp_x\varrho _{AB}^x\gamma _{CD}^x`$ with relative entropy of entanglement $`^{AC:BD}\left(\varrho _{ABCD}\right)`$ VPRK  in the AC:BD cut. At this point, neither the signals, nor the detectors are mutually orthogonal or pure. We will use this set-up in order to address the following question: *Can the information deficit* $`I_{acc}^{global}I_{acc}^{LOCC}`$ *be linked to the minimum *potential* for average entanglement production (in the distinguishing process) necessary to reach the globally accessible information* $`I_{acc}^{global}`$*?*  We need the set-up, since gaining information about the signal ($`x`$) can destroy the signal states ($`\varrho _{AB}^x`$) and their entanglement. But the signal states can (in principle) be correlated with any ancilla (detector). An information gain about $`x`$ will then usually purify the detector state, thus allowing for a potential average production of entanglement, even if the entanglement of the signal states is destroyed.

A measurement in the AB part (not necessarily restricted to LOCC) and obtaining results $`j`$ with probability $`q_j`$, will leave CD in $`\eta _{CD}^j=_xp_{x|j}\gamma _{CD}^x`$, thus accessing information $`H_s_jq_jH(\{p_{x|j}\})`$, which is no greater than $`H_s_jq_jS\left(\eta _{CD}^j\right)+_xp_xS\left(\gamma _{CD}^x\right)`$ (equality holds for orthogonal detector states), where $`H(\{r_i\})=_ir_i\mathrm{log}_2r_i`$, and $`H_s=H(\{p_x\})`$ is the Shannon entropy of the source. Let $`\delta =\overline{}_{in}^{det}^{AC:BD}\left(\varrho _{ABCD}\right)`$, where $`\overline{}_{in}^{det}=_xp_x(\gamma ^x)`$. Restricting now to LOCC-based measurements in the AB part, and considering it as an LOCC in the AC:BD cut, we have $`\delta \overline{}_{in}^{det}_jq_j(\eta _{CD}^j)`$, which equals $`_xp_xS\left(\gamma ^x\right)+_jq_jS\left(\eta ^j\right)_xp_x\mathrm{max}_{\zeta ^x}\text{tr}\gamma ^x\mathrm{log}_2\zeta ^x+_jq_j_xp_{x|j}\mathrm{max}_\zeta \text{tr}\gamma ^x\mathrm{log}_2\zeta `$ (maximizations over separable states), which is in turn clearly not more than $`_jq_jS\left(\eta ^j\right)_xp_xS\left(\gamma ^x\right)`$. And so we have

$$H_sI_{acc}^{LOCC}\delta .$$
(9)
For orthogonal ensembles, $`H_s`$ is the globally accessible information $`(I_{acc}^{global})`$, so that $`I_{acc}^{global}I_{acc}^{LOCC}\delta `$, where $`\delta `$ is just the average amount of entanglement produced (in the distinguishing process) by a superoperator that distinguishes between the ensemble states, if we disregard the entanglement possibly left in the ensemble states. The relation (9) holds for arbitrary detectors, and hence when $`\delta `$ is maximized over detectors. The nontrivial cases are when the orthogonal ensemble is locally indistinguishable, so that one requires a nonlocal superoperator to distinguish between them, and correspondingly one has a possibility of positive $`\delta `$. We assume here a “black box” model of the superoperator that distinguishes between the ensemble states. So, we are allowed to look at the *classical* output of the superoperator after it distinguishes, but are *not* allowed to manipulate the *quantum* output. One may also consider the entanglement produced in the whole state in the AC:BD cut and include a minimization over measurement strategies, required to (possibly nonlocally) distinguish the ensemble. This formulation is of course the same as the previous one (due to the minimization here). Thus $`\delta `$ gives us a notion of entanglement production, on average, in the process of (possibly nonlocally) distinguishing an ensemble when the black box is fed with the state $`\varrho _{ABCD}`$, we used. We hope that it holds even when the signals and detectors are quantum correlated. That is, we conjecture that
*The difference between globally and locally accessible information for an ensemble of orthogonal (not necessarily pure) states is not less than the amount of the relative entropy of entanglement which can be created in a global measurement to access $`I_{acc}^{global}`$ (i.e. distinguish the ensemble).*
For nonorthogonal ensembles, there is a further reduction of globally accessible information from $`H_s`$, due to the (global) indistinguishability of nonorthogonal states, which can make the problem more complicated.

To further link relation (8) to entanglement manipulations, we will prove it for a restricted case, by using the inequality in (9).

Taking the orthogonal ensemble $`\{p_x,\varrho _{AB}^x\}`$ as $`\{p_{nm},|\psi _{nm}^{max}\}`$ problem-generic  in $`dd`$ and the detectors as $`\{|\psi _{nm}^{max}^{}\}`$ (with conjugation in the computational basis), we have $`^{AC:BD}(\varrho _{ABCD}(\{p_{nm}\}))S(\varrho _{AC:BD}(\{p_{nm}\})|\varrho _{AC:BD}(\{p_{nm}=1/d^2\}))=2\mathrm{log}_2dH_s`$, where $`S(\rho |\sigma )=\mathrm{tr}(\rho \mathrm{log}_2\rho \rho \mathrm{log}_2\sigma )`$ (note that $`\rho _{AC:BD}(\{p_{nm}=1/d^2\})`$ is separable (cf. Smolin )). Therefore for *such ensembles*, we again obtain $`I_{acc}^{LOCC}2\mathrm{log}_2d\overline{E}n\overline{E}`$, (see eq. (9)) by a completely different method. In the general case, can we always find such detectors that $`^{AC:BD}(\varrho _{ABCD})2\mathrm{log}_2dH_s`$ or $`^{AC:BD}(\varrho _{ABCD})S_A+S_BH_s`$? We believe that understanding this question would be important in generalising our considerations here to a multipartite scenario.

A possible way to improve the bound (5) for bipartite states, would be to relate the accumulated bound on $`\mathrm{\Delta }\overline{S}_B^x`$ due to Alice’s measurement not to $`\overline{S}_A^x`$ but to classical mutual information contained in $`\varrho _{AB}^x`$. Likewise, there should be some room for handling nonlocality without entanglement -like examples Bennet1 ; Bennet2 ; LocDisting1 . For that, a possible candidate would be an object like “information deficit” OHHH2001 , although with some modifications. In particular, information deficit would have to be redefined for *ensembles* rather than for states, e.g., as the information loss under a fixed map applied independently of the coming signal. Another obstacle is that the present definition of information deficit is slightly different in spirit from accessible information. In particular, it is known that to achieve $`I_{acc}^{LOCC}`$, one sometimes has to add pure ancillas Bennet2 , which most likely is not the case for information deficit. The proper direction would then be to extend the definition of information deficit to relative entropy loss, rather than negentropy loss.

The concept of the main inequality came up at the meeting of Gdańsk Quantum Information Group (2002). We thank Karol Horodecki and Jonathan Oppenheim for useful discussions. The concept of estimate (9) arose in discussions with Karol Horodecki. P.B. thanks the University of Gdańsk for hospitality. This work is supported by EU grants EQUIP, RESQ and QUPRODIS, and by the University of Gdańsk, Grant No. BW/5400-5-0256-3.


text:
# From areas to lengths in quantum Regge calculus

## Abstract

Quantum area tensor Regge calculus is considered, some properties are discussed. The path integral quantisation is defined for the usual length-based Regge calculus considered as a particular case (a kind of a state) of the area tensor Regge calculus. Under natural physical assumptions the quantisation of interest is practically unique up to an additional one-parametric local factor of the type of a power of $`detg_{\lambda \mu }`$ in the measure. In particular, this factor can be adjusted so that in the continuum limit we would have any of the measures usually discussed in the continuum quantum gravity, namely, Misner, DeWitt or Leutwyler measure. It is the latter two cases when the discrete measure turns out to be well-defined at small lengths and lead to finite expectation values of the lengths.

The present paper combines results of the previous author’s works  to derive quantisation of the usual length-based Regge calculus from quantisation of the area Regge calculus model in the framework of the path integral and canonical quantisation approaches. Namely, area Regge calculus model has been quantised and shown to lead to finite expectation values of areas in . In the same Letter a suggestion has been made and developed in  that quantisation of Regge calculus is defined as that induced from the more general Regge-like system with independent 4-simplex linklengths. In terms of metric, we issue from the superspace of the metrics $`\{g\}`$ discontinuous on the 3-faces. The usual Regge calculus follows by imposing continuity conditions describing a hypersurface $`\mathrm{\Gamma }_{\mathrm{cont}}`$ in this superspace. The functionals $`\psi (\{g\})`$ on Regge calculus hypersurface $`\mathrm{\Gamma }_{\mathrm{cont}}`$ are naturally mapped into the set of the functionals $`\mathrm{\Psi }(\{g\})`$ on the original superspace of discontinuous metrics,

$$\mathrm{\Psi }(\{g\})=\psi (\{g\})\delta _{\mathrm{cont}}(\{g\})$$
(1)
where $`\delta _{\mathrm{cont}}(\{g\})`$ is a $`\delta `$-function with support on $`\mathrm{\Gamma }_{\mathrm{cont}}`$ so that the quantum measure viewed as a functional on the space of functionals is the result of the pull-back of such the embedding,

$$\mu _{\mathrm{cont}}()=\mu (\delta _{\mathrm{cont}}(\{g\})).$$
(2)
In  it has been shown that requirement that continuity conditions be imposed in a ”face-independent” manner fixes $`\delta _{\mathrm{cont}}`$ uniquely. The term ”face-independent” means that the $`\delta `$-function factor responsible for the continuity of the metric across a face depends only on the plane formed by the face, not on the form and size of the face,

The situation can be represented by the following (noncommutative) diagram,

where lower path shown by thick arrows means conventional approach to quantisation. Our approach is shown by thin upper line. Using some analogy, we can say that Regge calculus is considered as a kind of the state of the area tensor Regge calculus.

The result of  takes the form

$`<\mathrm{\Psi }(\{\pi \},\{\mathrm{\Omega }\})>`$ $`=`$ $`{\displaystyle \mathrm{\Psi }(i\{\pi \},\{\mathrm{\Omega }\})\mathrm{exp}\left(\underset{\stackrel{t\mathrm{like}}{(ABC)}}{}\tau _{(ABC)}R_{(ABC)}(\mathrm{\Omega })\right)}`$ (3)
$`\mathrm{exp}\left(i{\displaystyle \underset{\stackrel{\stackrel{\mathrm{not}}{t\mathrm{like}}}{(ABC)}}{}}\pi _{(ABC)}R_{(ABC)}(\mathrm{\Omega })\right){\displaystyle \underset{\stackrel{\stackrel{\mathrm{not}}{t\mathrm{like}}}{(ABC)}}{}}d^6\pi _{(ABC)}{\displaystyle \underset{(ABCD)}{}}𝒟\mathrm{\Omega }_{(ABCD)}`$
$``$ $`{\displaystyle \mathrm{\Psi }(i\{\pi \},\{\mathrm{\Omega }\})d\mu _{\mathrm{area}}(i\{\pi \},\{\mathrm{\Omega }\})}.`$
Here $`AB`$ $`\stackrel{\mathrm{def}}{=}`$ $`\frac{1}{2}A^{ab}B_{ab}`$. The field variables are area tensors $`\pi _{(ABC)}`$ on the triangles $`(ABC)`$ (the 2-simplices $`\sigma ^2`$) and SO(4) connection matrices $`\mathrm{\Omega }_{(ABCD)}`$ on the tetrahedrons $`(ABCD)`$ (the 3-simplices $`\sigma ^3`$). This looks as the usual field-theoretical path integral expression with exception of the following three points. First, occurence of the Haar measure on the group SO(4) of connections on separate 3-faces $`𝒟\mathrm{\Omega }_{(ABCD)}`$ connected with the specific form of the kinetic term $`\pi _{(ikl)}\mathrm{\Omega }_{(ikl)}^{}\dot{\mathrm{\Omega }}_{(ikl)}`$ if one passes to the continuous limit along any of the coordinate direction chosen as time. Such form of the kinetic term in the general 3D discrete gravity model has been deduced by Waelbroeck .

Second, the sum of the terms $`\pi _{(ABC)}R_{(ABC)}`$ in the exponential whereas the exact connection representation of the Regge action is the sum of the terms with ’arcsin’ of the type $`|\pi |\mathrm{arcsin}(\pi R/|\pi |)`$ . The matter is in the way the eq. (3) has been obtained. Namely, we issue from the requirement that Feynman path integral based on the canonical quantisation prescription should arise whenever we pass to the continuous time limit along whichever coordinate taken as time. The phase factor in the integral is defined by the constraints. The latter follow from the equations of motion which lead in the case of area Regge calculus to the trivial solution $`R`$ $``$ $`\overline{R}`$ = 0, and the constraints are the same as if ’arcsin’ were omitted (in empty space; situation might be much more complicated in the presence of matter fields!). The exponential in (3) just originates from the sum of the constraints times Lagrange multipliers and is not the original action.

Finally, third, occurence of a set of the triangles over area tensors $`\tau _{(ABC)}`$ of which integrations are absent. It is the set of those triangles the curvature matrices on which are functions, via Bianchi identities, of all the rest curvatures. (Integrations over them might result in the singularities of the type of $`[\delta (R\overline{R})]^2`$). The eq. (3) displays the simplest choice of this set. Namely, choose any of the coordinates $`t`$ and take all the $`t`$-like triangles. The notion ”$`t`$-like” suggests a certain regular structure  of the Regge manifold considered as consisting of sequence of the 3D Regge manifolds $`t`$ = $`const`$ of the same structure usually called the leaves of the foliation along $`t`$. That $`t`$-like triangles turn out to be just those ones on which the curvature matrices can be expressed in terms of those matrices on the other, contained in the 3D leaves (”leaf” triangles) and diagonal triangles might seem to be accidental, but it seems quite interesting to connect 1-dimensionality of the coordinates along which quantum fluctuations are absent (”time”) with Bianchi identities.

The cutoff and positivity properties of the measure (3) can be seen for the trivial choice of the $`t`$-like area tensors $`\tau `$ = 0. In this case the measure in the eq. (3) splits into the product of the measures over separate (not $`t`$-like) triangles of the type

$$\mathrm{exp}(i\pi R)d^6\pi 𝒟R.$$
(4)
In turn, this splits into self- and antiselfdual counterparts each taking the form

$$\mathrm{exp}\left(i𝒍\mathit{\varphi }\frac{\mathrm{sin}\varphi }{\varphi }\right)d^3𝒍\frac{\mathrm{sin}^2(\varphi /2)}{4\pi ^2\varphi ^2}d^3\mathit{\varphi }$$
(5)
where $`𝒍`$, $`\mathit{\varphi }`$ are 3D vectors into which selfdual (or antiselfdual) parts of $`\pi `$ and generator of $`R`$, respectively, are mapped. If applied to a (analitical) function $`f(i𝒍)`$ this results in

$$<f(𝒍)>=f(𝒍)\nu (l)\frac{d^3𝒍}{4\pi l^2},\nu (l)=\frac{2l}{\pi }_0^\pi \mathrm{exp}\left(\frac{l}{\mathrm{sin}\phi }\right)𝑑\phi .$$
(6)
Here the two remarks are in order. First, one could proceed directly from the Lorentzian signature case. (This concerns the local frame indices, and we shall distinguish between the terms ”timelike”, ”spacelike” and ”$`t`$-like”, ”leaf”, ”diagonal” referred to the local frame index and to the Regge analog of the world index, respectively.) Considering effect of integrations over the Lorentz generators $`𝝍`$ = $`(\psi ^{01},\psi ^{02},\psi ^{03})`$ of rotations around the spacelike area components with vector $`𝒍`$ we find analogous to (5) expression

$$\mathrm{exp}\left(i𝒍𝝍\frac{\mathrm{sinh}\psi }{\psi }\right)d^3𝒍\frac{\mathrm{sinh}^2(\psi /2)}{4\pi ^2\psi ^2}d^3𝝍$$
(7)
with hyperbolic functions. Note that area spanned by a triangle is described by the dual to $`\pi `$, and the term ”timelike” or ”spacelike” area components just refers to this object. Now (7) should be applied directly to $`f(𝒍)`$ with real $`𝒍`$. The result is the same, eq. (6). The difficulty arises when we incorporate the rest of the rotations, the Euclidean ones, and get complex selfdual and antiselfdual parts when trying to factorise anyhow. Therefore we prefer to pass to integration over imaginary $`\psi ^{0i}`$ = $`i\varphi ^{0i}`$, i. e. over completely Euclidean rotations. At the same time, we pass to the purely imaginary variables characterising spacelike area components ($`𝒍`$ in (7)) leaving timelike components unchanged. This just corresponds to making Wick rotation of the timelike vector components together with the overall rescaling by $`i`$ area tensors over which integration is made, as mentioned above. Note that we make these redefinitions only over the field variables which are, in turn, dummy variables in the path integral. Necessity to make these over spacetime coordinates is absent since Regge calculus is coordinateless formulation ($`t`$ simply numerates the leaves). May be, this solves the problem of Wick rotation in quantum gravity?

Second remark concerns taking into account contribution of the nonzero $`t`$-like triangles $`\tau _{(ABC)}`$. This is necessary in order to describe evolution in $`t`$. Meanwhile, corresponding terms in the exponential violate factorisation of the measure (3) into the ”elementary” ones (4) making calculation in closed form hardly achievable. Since integrals considered are only conditionally convergent, the properties of analyticity at $`\tau `$ = 0 and of positivity are not quite evident. To get some idea of possible form of the answer take some simplified model of dependence on $`\mathit{\varphi }`$ of the additional terms in the exponential of the measure. Whereas $`\mathrm{sin}\varphi `$ characterises antisymmetric part of the curvature matrix, it’s symmetric part containes $`\mathrm{cos}\varphi `$ and just arises in the considered terms due to the dependence on the given curvature via Bianchi identities. Therefore perform the following calculation,

$`{\displaystyle f(i𝒍)\mathrm{exp}\left(i𝒍\mathit{\varphi }\frac{\mathrm{sin}\varphi }{\varphi }\epsilon \mathrm{cos}\varphi \right)d^3𝒍\frac{\mathrm{sin}^2(\varphi /2)}{4\pi ^2\varphi ^2}d^3\mathit{\varphi }}`$ $`=`$ $`{\displaystyle f(𝒍)\nu _\epsilon (l)\frac{d^3𝒍}{4\pi l^2}},`$
$`\nu _\epsilon (l)={\displaystyle \frac{2l}{\pi }}{\displaystyle _0^\pi }\mathrm{exp}\left({\displaystyle \frac{l}{\mathrm{sin}\phi }}\right)\mathrm{cos}(\epsilon \mathrm{cot}\phi )𝑑\phi .`$ (8)
The $`\nu _\epsilon (l)`$ is positive. It admits expansion in powers of $`\epsilon `$, although each subsequent term of this expansion possesses more singular behaviour at small $`l`$. The same properties can be conjectured for the exact measure and for it’s dependence on $`\tau `$.

Now proceed to reducing the described measure to the usual length-based Regge calculus. Roughly speaking, area tensor Regge calculus can be considered as a simplicial theory with metric defined in each the 4-simplex independently of others, i. e. discontinuous on the 3-faces. To be more precise, we have even more general theory in which even the 4-simplex metric is defined ambiguously. This is because to define metric in a given 4-simplex it is sufficient to know it’s ten areas of the 2-faces; meanwhile, introducing tensors instead of scalar areas we thus introduce some redundant scalars which can be constructed of these tensors. Thus we need the constraints which would enforce area tensors to be bivectors constructed of the tetrad corresponding to a certain metric inside a given 4-simplex. Denote corresponding $`\delta `$-function factor in the measure $`\delta _{\mathrm{tetrad}}`$. Besides that, the constraints are required which ”glue” together different 4-simplex metrics, i. e. just the above $`\delta `$-function factor $`\delta _{\mathrm{cont}}`$. The constraints on the scalar areas have been discussed in . In our case of area tensors a new possibility arises to get a system of bilinear constraints although at the price of extending the set of variables . In fact, the above notation for area tensor $`\pi _{(ABC)}`$ refers to the frame of a certain 4-simplex $`(ABCDE)`$ where this tensor is defined. The more detailed notation we use is $`\pi _{(ABC)DE}`$. The idea is to introduce for any triangle the set of area tensors defined in all the 4-simplices $`\sigma ^4`$ containing the given triangle $`\sigma ^2`$. Correspondingly, also integrations over new variables should be introduced in the measure.

Let us pass to the 3D leaf notations for the simplices respecting the above mentioned division of the simplices into $`t`$-like and other, spacelike and diagonal ones. The vertices of the 3D leaf are $`i`$, $`k`$, $`l`$, …. The $`i^+`$ means image in the next-in-$`t`$ leaf of the vertex $`i`$ taken at the moment $`t`$. The notation $`(A_1A_2\mathrm{}A_{n+1})`$ means unordered $`n`$-simplex with vertices $`A_1`$, $`A_2`$, …, $`A_{n+1}`$ (triangle at $`n`$ = 2) while that without parentheses means ordered simplex. The 4-simplices are arranged into the 4-prisms between the pairs of the neighbouring 3D leaves. Let the 4-prism with bases $`(iklm)`$ and $`(i^+k^+l^+m^+)`$ consists of the 4-simplices $`(ii^+klm)`$, $`(i^+kk^+lm)`$, $`(i^+k^+ll^+m)`$, $`(i^+k^+l^+mm^+)`$. Take, e. g., $`(ii^+klm)`$ and consider area tensors of it’s 6 2-faces containing vertex $`i`$. These are $`\pi _{(ikl)}`$ ($`\pi _{(ikl)i^+m}`$ in more detailed notations),

$$\pi _{(ii^+k)}\stackrel{\mathrm{def}}{=}\tau _{(ii^+k)}\stackrel{\mathrm{def}}{=}\tau _{ik}$$
(9)
and the two cycle permutations of $`k`$, $`l`$, $`m`$. The other 4 tensors are expressible as algebraic sums of these ones ensuring closure of the 3-faces, e. g.

$$\pi _{(i^+kl)}=\pi _{(ikl)}+\tau _{ik}\tau _{il}.$$
(10)
The tetrad constraints take the form

$`\pi _{(ikl)}\pi _{(ikl)}=0,\pi _{(ikl)}\pi _{(ikm)}=0,`$
$`\pi _{(ikl)}\tau _{ik}=0,\pi _{(ikl)}\tau _{il}=0,`$
$`\tau _{ik}\tau _{ik}=0,\tau _{ik}\tau _{il}=0,`$
$`\mathrm{}2\mathrm{cycle}\mathrm{perm}(k,l,m)\mathrm{},`$ (11)
$`\pi _{(ikl)}\tau _{im}=\pi _{(ilm)}\tau _{ik}=\pi _{(imk)}\tau _{il}(=V_{(ii^+klm)}),`$ (12)
the total number of them being 20. Here $`AB`$ = $`\frac{1}{4}A^{ab}B^{cd}ϵ_{abcd}`$ for the two tensors $`A`$, $`B`$. The two constraints (12) provide unambiguous definition of the 4-volume $`V_{(ii^+klm)}`$.

Important is that now integrations over $`\tau _{(ABC)}`$ should also be included. This is because fixing these tensors as parameters in the length-based framework put severe restriction on area tensors $`\pi `$ of the leaf and diagonal triangles. On the other hand, the reason that these integrations were omitted is absent now. Namely, integrals over $`\pi `$ cannot lead to $`\delta `$-functions of curvatures because of the nontrivial preexponent factor. It quite may be that all integrations over $`\tau _{(ABC)}`$ will prove to be finite. However, for our purposes it is important to keep $`\tau _{(ABC)}`$ small so that we could use the possibility of factorisation into elementary measures (4). But to do this it is sufficient to equate to small values the appropriately chosen 4 scalars per vertex composed of $`\tau `$ components. For example, let these constraints at the vertex $`i`$ be defined in the considered 4-simplex $`(ii^+klm)`$. Thereby restrictions are imposed on the linklength of $`(ii^+)`$, discrete analog of the lapse-shift vector. The product over all the vertices $`\sigma ^0`$, $`\delta _{\mathrm{lapse}\mathrm{shift}}`$ serves to restrict all the $`t`$-like links.

$`\delta _{\mathrm{lapse}\mathrm{shift}}(i)=\delta (\tau _{ik}\tau _{ik}\epsilon _1^2)\delta (\tau _{il}\tau _{il}\epsilon _2^2)\delta (\tau _{im}\tau _{im}\epsilon _3^2)\delta (\tau _{ik}\tau _{il}\zeta \epsilon _1\epsilon _2),`$ (13)
$`\delta _{\mathrm{lapse}\mathrm{shift}}={\displaystyle \underset{\sigma ^0}{}}\delta _{\mathrm{lapse}\mathrm{shift}}(\sigma ^0).`$ (14)
Proceeding from the answer (finite expectation values for the leaf and diagonal linklengths) the (13) means smallness of the $`(ii^+)`$ linklength and thereby smallness $`O(\epsilon )`$ of all tensors of the type $`\tau _i\mathrm{}`$. This corresponds to fixing lapse-shift vector in the continuum general relativity.

Evidently, there is one-to-one correspondence of the constraints (From areas to lengths in quantum Regge calculus-12) to those on area tensors $`\pi _{\lambda \mu }^{ab}`$ in the continuum theory at a given point. It is possible by temporarily (in the given 4-simplex) redenoting $`\pi _{(ikl)}`$ $``$ $`\pi _{12}`$, $`\tau _{ik}`$ $``$ $`\pi _{01}`$, …$`2\mathrm{cycle}\mathrm{perm}(i,k,l)`$ and $`(1,2,3)`$…to rewrite (From areas to lengths in quantum Regge calculus -12) in the form

$$ϵ_{abcd}\pi _{\lambda \mu }^{ab}\pi _{\nu \rho }^{cd}ϵ_{\lambda \mu \nu \rho }.$$
(15)
The constraints are in the form covariant w.r.t. the world index. This is essential if we require that the theory would have continuum limit measure invariant w. r. t. the world index. However, usually this requirement is relaxed, and local continuum measure is allowed to be not necessarily invariant w. r. t. the conformal degree of freedom. Therefore a power of $`detg`$, $`g`$ being metric tensor, or $`dete`$, $`e`$ being tetrad, is accepted as additional factor. This gives the general form of the $`\delta `$-factor taking the constraints into account. The product of such factors over all the 4-simplices just gives $`\delta _{\mathrm{tetrad}}`$.

$$\delta _{\mathrm{tetrad}}(ii^+klm)=V^\eta \delta ^{21}(\pi _{\lambda \mu }\pi _{\nu \rho }Vϵ_{\lambda \mu \nu \rho })𝑑V,\delta _{\mathrm{tetrad}}=\underset{\sigma ^4}{}\delta _{\mathrm{tetrad}}(\sigma ^4),$$
(16)
$`\eta `$ being a parameter.

To study convergence properties of the integrals it is convenient to make selfdual-antiselfdual splitting, in particular, $`\pi _{\lambda \mu }`$ maps into 3-vectors $`{}_{}{}^{+}𝝅_{\lambda \mu }^{}`$, $`{}_{}{}^{}𝝅_{\lambda \mu }^{}`$. Here convenient are 3D notations $`ϵ_{\alpha \beta \gamma }^\pm 𝝅^\gamma `$ $`\stackrel{\mathrm{def}}{=}`$ $`{}_{}{}^{\pm }𝝅_{\alpha \beta }^{}`$, $`{}_{}{}^{\pm }𝝉_{\alpha }^{}`$ $`\stackrel{\mathrm{def}}{=}`$ $`{}_{}{}^{\pm }𝝅_{0\alpha }^{}`$. Then the constraints (15) yield

$${}_{}{}^{\pm }𝝉_{\alpha }^{}=ϵ_{\alpha \beta \gamma }c^\beta {}_{}{}^{\pm }𝝅_{}^{\gamma }+\frac{1}{2}Cϵ_{\alpha \beta \gamma }^\pm 𝝅^\beta \times ^\pm 𝝅^\gamma .$$
(17)
The selfdual and antiselfdual area vectors in a given 4-simplex differ by an overall rotation. Therefore choose as independent variables $`𝝅^\alpha `$ (under which we mean $`{}_{}{}^{+}𝝅_{}^{\alpha }`$ for definiteness), $`c^\alpha `$, $`C`$ and SO(3) rotation $`𝒪`$ which connects antiselfdual and selfdual sectors, the overall number 16 just corresponds to the number of the tetrad components. Integrating over all the 36 4-simplex components $`\pi _{\lambda \mu }^{ab}`$ we find

$$()\delta _{\mathrm{tetrad}}(ii^+klm)\mathrm{d}^{36}\pi =()C^{\eta 6}[𝝅^1\times 𝝅^2𝝅^3]^{\eta 6}dC\mathrm{d}^3𝒄\mathrm{d}^9𝝅𝒟𝒪.$$
(18)
Consider for a moment continuum limit. It has been proven  that modulo partial use of the eqs. of motion our area tensor Regge calculus model results in the continuum limit in the area-generalised Hilbert-Palatini form of GR such that upon postulating the tetrad form of area tensors we get usual GR. Therefore integration over $`𝒟\mathrm{\Omega }`$ by stationary phase method just results in the integration over infinitesimal connections $`\mathrm{d}^{24}\omega _\lambda ^{ab}`$ in the functional integral with Hilbert-Palatini form of the action yielding an additional factor $`V^6`$ = $`C^6[𝝅^1\times 𝝅^2𝝅^3]^6`$ = $`(detg_{\lambda \mu })^3`$ in (18). On the functionals of purely metric $`g_{\lambda \mu }`$ this leads to the measure $`(detg_{\lambda \mu })^{\frac{\eta 13}{2}}\mathrm{d}^{10}g_{\lambda \mu }`$. It is Misner measure  at $`\eta `$ = 8 or the DeWitt measure  at $`\eta `$ = 13. It is also easy to define $`\delta _{\mathrm{tetrad}}`$ so that in the continuum limit we would have the Leutwyler measure $`(detg_{\lambda \mu })^{\frac{3}{2}}g^{00}\mathrm{d}^{10}g_{\lambda \mu }`$ . Namely, we should insert $`[𝝅^1\times 𝝅^2𝝅^3]`$ into (18) at $`\eta `$ = 8 for that.

Now in the discrete framework integrating over connections we get for each leaf or diagonal triangle $`\sigma ^2`$ the tensor of which in (3) is defined in the given 4-simplex the additional factor in (18),

$$\frac{\nu (|^+𝝅_{\sigma ^2}|)}{|^+𝝅_{\sigma ^2}|^2}\frac{\nu (|^{}𝝅_{\sigma ^2}|)}{|^{}𝝅_{\sigma ^2}|^2}=\frac{\nu (|𝝅_{\sigma ^2}|)^2}{|𝝅_{\sigma ^2}|^4}.$$
(19)
Possibility to get the factor in this form is connected with factorisation into simple measures (4) possible due to $`\epsilon `$ $``$ 1 in $`\delta _{\mathrm{lapse}\mathrm{shift}}`$.

The expression (19) varies at small $`|𝝅_{\sigma ^2}|`$ as $`|𝝅_{\sigma ^2}|^2`$. The behaviour at small areas is essential for the area expectation values be vanishing or not. To see what triangles to which 4-simplices can be attributed (i. e. their tensors defined) in a regular way let us begin with the leaf triangles and distribute these among the 3-simplices. Since $`N_2^{(3)}`$ = $`2N_3^{(3)}`$ where $`N_k^{(d)}`$ is the number of $`k`$-simplices in the $`d`$-dimensional Regge manifold we have two triangles in each tetrahedron, e. g. let $`(ikl)`$ and $`(ikm)`$ be assigned to $`(iklm)`$. Then define these in the frame of that one of the two 4-simplices sharing $`(iklm)`$ which is in the future in $`t`$, i. e. here in $`(ii^+klm)`$. The diagonal triangles differing by occurence of superscript $`+`$ on some of the vertices will be assigned to the future 4-simplices in the same 4-prism. For example, $`(i^+kl)`$, $`(i^+km)`$ are defined in $`(i^+kk^+lm)`$; $`(i^+k^+l)`$, $`(i^+k^+m)`$ are defined in $`(i^+k^+ll^+m)`$; no triangles are defined in $`(i^+k^+l^+mm^+)`$. Considered are the 4 4-simplices which constitute a 4-prism. There are 6 triangles defined in the 4-simplices of any 4-prism (the triangle $`(i^+k^+l^+)`$ refers to the next-in-$`t`$ 4-prism). Because of smallness of the lateral ($`t`$-like) 2-surface the areas of the future in $`t`$ triangles are almost the same (differ by $`O(\epsilon )`$). Therefore the cutoff factor is

$$\left(\frac{\nu (|𝝅_{\sigma _1^2}|)^2}{|𝝅_{\sigma _1^2}|^4}\right)^3\left(\frac{\nu (|𝝅_{\sigma _2^2}|)^2}{|𝝅_{\sigma _2^2}|^4}\right)^3+O(\epsilon )$$
(20)
for the 4-prism where $`\sigma _1^2`$, $`\sigma _2^2`$ are the triangles defined in the (base of) 4-prism.

It remains to insert $`\delta _{\mathrm{cont}}`$ which imposes continuity conditions on the common 3-faces between the 4-simplices. The result of  looks as

$$\delta _{\mathrm{cont}}=\underset{\sigma ^3}{}V_{\sigma ^3}^4\delta ^6(\mathrm{\Delta }_{\sigma ^3}S_{\sigma ^3})\left(\underset{\sigma ^2}{}V_{\sigma ^2}^3\delta ^3(\mathrm{\Delta }_{\sigma ^2}S_{\sigma ^2})\right)^1\underset{\sigma ^1}{}V_{\sigma ^1}^2\delta (\mathrm{\Delta }_{\sigma ^1}S_{\sigma ^1})$$
(21)
where $`S_{\sigma ^k}`$ is induced metric on the $`k`$-face $`\sigma ^k`$ in the form of the edge components , i. e. $`k\frac{k+1}{2}`$ edge lengths squared of the $`k`$-face, $`\mathrm{\Delta }_{\sigma ^k}`$ is discontinuity across the $`k`$-face $`\sigma ^k`$, $`V_{\sigma ^k}`$ is the face $`k`$-volume. Occurence of the factors with $`k`$ = 1, 2 serves to cancel effect of the cycles enclosing the triangles and leading to the singularities of the type of $`\delta `$-function squared. The $`\delta `$-function in the denominator means that the same function is contained in the numerator and is thereby cancelled.

Let us reexpress $`\delta _{\mathrm{cont}}`$ in terms of area tensor variables. Essential for us is division of the set of $`k`$-faces into the two groups, $`t`$-like and not $`t`$-like (leaf and diagonal) ones. Take the above 4-simplex $`(ii^+klm)`$ and use the above local selfdual notations in it. The face-independent $`\delta `$-factor responsible for the metric continuity across the leaf 3-face $`(iklm)`$ takes the form

$$[𝝅^1\times 𝝅^2𝝅^3]^4\delta ^6(\mathrm{\Delta }_{(iklm)}(𝝅^\alpha 𝝅^\beta )).$$
(22)
Such the factor for the $`t`$-like 3-face $`(ii^+kl)`$ looks analogously up to evident redenoting area vectors,

$$[𝝉_1\times 𝝉_2𝝅^3]^4\delta (\mathrm{\Delta }(𝝅^3)^2)\delta (\mathrm{\Delta }(𝝅^3𝝉_1))\delta (\mathrm{\Delta }(𝝅^3𝝉_2))\delta (\mathrm{\Delta }(𝝉_1)^2)\delta (\mathrm{\Delta }(𝝉_2)^2)\delta (\mathrm{\Delta }(𝝉_1𝝉_2)).$$
(23)
Here $`\mathrm{\Delta }`$ $``$ $`\mathrm{\Delta }_{(ii^+kl)}`$. The $`\delta `$-factor for the $`t`$-like 2-face $`(ii^+k)`$ takes the form (definition of the $`\mathrm{\Delta }_{\sigma ^k}`$ at $`k`$ $`<`$ 3 is ambigious, $`\mathrm{\Delta }_{(ii^+k)}`$ = $`\mathrm{\Delta }_{(ii^+k\stackrel{~}{l})}`$ for some vertex $`\stackrel{~}{l}`$, and we assume that $`\stackrel{~}{l}`$ is just $`l`$).

$$|𝝉_1|^3|[𝝉_1\times 𝝉_2𝝅^3]|^3\delta (\mathrm{\Delta }(𝝉_1\times 𝝉_2)^2)\delta (\mathrm{\Delta }((𝝉_1\times 𝝉_2)(𝝉_1\times 𝝅^3)))\delta (\mathrm{\Delta }(𝝉_1\times 𝝅^3)^2).$$
(24)
Here $`\mathrm{\Delta }`$ $``$ $`\mathrm{\Delta }_{(ii^+k)}`$. Write out also $`\delta `$-factor for the $`t`$-like 1-face (link) $`(ii^+)`$,

$$(𝝉_1\times 𝝉_2)^2\delta (\mathrm{\Delta }_{(ii^+)}(𝝉_1\times 𝝉_2)^2).$$
(25)
Consider effect of inserting $`\delta _{\mathrm{cont}}`$ on the expectation values. Perform simple power-counting estimate. Remarkable feature of $`\delta _{\mathrm{cont}}`$ is that it is invariant w.r.t. the overall rescaling area tensors of the $`t`$-like and not $`t`$-like triangles separately, see (22-25). This is important since we have fixed the scale of the $`t`$-like area tensors. Qualitatively, behaviour of the 4-simplex measure upon taking into account $`\delta _{\mathrm{lapse}\mathrm{shift}}`$ and $`\delta _{\mathrm{tetrad}}`$ can be modelled by the 1-dimensional one on the interval $`(0,\mathrm{})`$,

$$x^{\eta 7}\mathrm{d}x,e^xx^{\eta 9}\mathrm{d}x,\mathrm{or}e^{2x}x^{\eta 11}\mathrm{d}x$$
(26)
if 0, 1 or 2 area tensors in (3) are defined in the given 4-simplex, respectively. Here $`x`$ models the scale of areas. If we adjust $`\delta _{\mathrm{tetrad}}`$ to reproduce the Leutwyler measure in the continuum limit (cf. discussion after eq. (18)) this would be equivalent to putting $`\eta `$ = 11 in (26). Inserting $`\delta _{\mathrm{cont}}`$ can be modelled by inserting the scale-invariant functions $`x\delta (\mathrm{\Delta }x)`$ so that the two measures $`f_1(x_1)\mathrm{d}x_1`$, $`f_2(x_2)\mathrm{d}x_2`$ intended to model the two measures in the 4-simplices sharing a $`t`$-like face map into

$$f_1(x_1)\mathrm{d}x_1x_1\delta (x_1x_2)f_1(x_2)\mathrm{d}x_2xf_1(x)f_2(x)\mathrm{d}x.$$
(27)
In the case of the two neighbouring 4-simplices one being in the future in $`t`$ w.r.t. another one things are somewhat more complicated because now $`\delta _{\mathrm{cont}}`$ compares area tensors of the ”earlier” triangles of the ”later” 4-simplex and area tensors of the ”later” triangles of the ”earlier” 4-simplex. The latter tensors are expressible as algebraic sums of those ones taken above as independent set in the given 4-simplex, (10). Modulo $`\delta _{\mathrm{lapse}\mathrm{shift}}`$ inserted, this eq. means that $`\pi _{(i^+kl)}`$ is $`\pi _{(ikl)}`$ up to $`O(\epsilon )`$. Therefore the two measures $`f_1(x_1)\mathrm{d}x_1`$, $`f_2(x_2)\mathrm{d}x_2`$ modelling the measures in the considered 4-simplices can be considered to map into

$$f_1(x_1)\mathrm{d}x_1\delta (\epsilon |x_1^{}x_1|)x_1^{}\delta (x_1^{}x_2)f_1(x_2)\mathrm{d}x_2xf_1(x)f_2(x)\mathrm{d}x$$
(28)
up to $`O(\epsilon )`$. Here $`\delta (\epsilon |x_1^{}x_1|)`$ models the $`\delta _{\mathrm{lapse}\mathrm{shift}}`$. Taking into account the 4-prism factor (20) the model measure for $`n`$ 4-prisms reads

$$\left(e^{6x}x^{4\eta 36}\right)^n\frac{\mathrm{d}x}{x}.$$
(29)
This gives for $`n`$ $``$ $`j`$

$$<x^j>=\left(\frac{2}{3}\eta 6\right)^j$$
(30)
(but the number of the prisms along $`t`$ should be much less than $`\epsilon ^1`$ to ensure possibility of neglecting tensors $`\tau `$ in the exponential of (3) and possibility to treat leaf and diagonal tensors $`\pi `$ as practically unchanged in $`t`$). The eq. (30) corresponds formally to the $`\delta `$-function-like limiting ($`n`$ $``$ $`\mathrm{}`$) measure, but this is due to, first, neglecting tensors $`\tau `$ ($`\epsilon `$ $``$ 0), second, simplicity of the suggested 1D model of estimating. The main outcome is that the length expectation values are finite and nonzero at $`\eta `$ $`>`$ 9. This is the case for the above choices of $`\delta _{\mathrm{tetrad}}`$ leading in the continuum limit to the Leutwyler or DeWitt measures. At $`\eta `$ $``$ 9, in particular, in the Misner measure case, the length expectation values are zero, and this is connected with an overall divergence of the measure at small length scale.

To summarize, we have considered the following expression for quantum measure for the usual length-based Regge calculus,

$$\mathrm{d}\mu _{\mathrm{length}}=\left(\delta _{\mathrm{lapse}\mathrm{shift}}\underset{\stackrel{t\mathrm{like}}{(ABC)}}{}d^6\tau _{(ABC)}\right)\delta _{\mathrm{tetrad}}\delta _{\mathrm{cont}}\mathrm{d}\mu _{\mathrm{area}}.$$
(31)
This practically one-parametric (depending on the choice of $`\delta _{\mathrm{tetrad}}`$) equation results in quantisation of the general relativity in the continuum (long-wavelength) limit with some usual local measure at the same time providing finite expectation values of the linklengths.

The present work was supported in part by the Russian Foundation for Basic Research through Grant No. 03-02-17612, through Grant No. 00-15-96811 for Leading Scientific Schools and by the Ministry of Education Grant No. E00-3.3-148.