## Abstract

Constructing realizations of random media with a specified two-point phase probability function *S*_{2} has attracted considerable attention in the recent literature. However, little is known about conditions under which a prescribed *S*_{2} is realizable. The only known necessary and sufficient condition, due to McMillan, involves a class of square matrices, called corner-positive matrices, about which almost nothing is known except their definition. As a result, McMillan's theorem has gone mostly unused in the literature for over 50 years. In this paper, we present a general decomposition formula for corner-positive matrices, which allows McMillan's theorem to be written in a significantly more tractable and testable form. We also connect McMillan's theorem with many known but heretofore unrelated necessary conditions on *S*_{2}, extending many of these conditions.

## 1. Introduction

Much progress has been made in characterizing the microstructure of statistically homogeneous two-phase random media. One commonly used characterization of the microstructure is the two-point phase probability function *S*_{2}(*t*_{1}, *t*_{2}), which is the probability that the two points *t*_{1} and *t*_{2} both lie in a given phase (say phase 1). We may explicitly write this function as *S*_{2}(*t*_{1}, *t*_{2})=*E*[*I*(*t*_{1})*I*(*t*_{2})], where *I*(** t**) is the indicator function for phase 1. Typically, we assume that

*S*

_{2}is translationally invariant, so that we may write

*S*

_{2}(

*t*_{1},

*t*_{2})=

*S*

_{2}(

**), where**

*r***=**

*r*

*t*_{2}−

*t*_{1}. Since

*S*

_{2}(

*t*_{1},

*t*_{2})=

*S*

_{2}(

*t*_{2},

*t*_{1}), we note that

*S*

_{2}(

**)=**

*r**S*

_{2}(−

**), so that**

*r**S*

_{2}is an even function.

This function and its higher order analogues are fundamental to rigorously determining the effective transport, electromagnetic and mechanical properties of ergodic two-phase random media (Weissberg & Prager 1970; Doi 1976; Milton 1981; Milton & Phan-Thien 1982; Sen & Torquato 1989; Quintanilla & Torquato 1995; Helsing 1998; Quintanilla 1999*a*; Milton 2002; Torquato 2002; Monetto & Drugan 2004; Buryachenko 2007). A wide variety of techniques have been introduced in the literature for computing *S*_{2} for various mathematical models (Torquato & Stell 1982; Roberts & Teubner 1995; Stoyan *et al.* 1995; Markov *et al.* 1996; Roberts & Knackstedt 1996; Quintanilla 1999*a*,*b*; Torquato 2002).

Recently, the inverse problem of constructing visualizations of random materials with a specified *S*_{2} has received significant attention. In principle, *S*_{2} can be inferred from a given random material by using small-angle scattering data (Guinier *et al.* 1955; Torquato 2002); however, the required inversion is susceptible to numerical errors. To overcome this difficulty, different techniques have been proposed in the literature for constructing random media with a predetermined *S*_{2}, including stochastic optimization (Yeong & Torquato 1998; Cule & Torquato 1999; Sheehan & Torquato 2001; Rozman & Utz 2001, 2002) and Gaussian random field models (Roberts 1997; Nott & Rydén 1999; Nott & Wilson 2000; Quintanilla & Jones 2007; Quintanilla *et al.* 2007).

However, very little is known about the class of functions that admit a solution to the inverse problem. The only known necessary and sufficient condition on *S*_{2} may be inferred from the properties of *X*(** r**)=2

*I*(

**)−1, a ±1-valued stochastic process. We define(1.1)to be a**

*r**unit function*. By expanding (1.1), we note that(1.2)where

*ϕ*=

*S*

_{2}(

**0**) is the volume fraction.

McMillan (1955) stated the following necessary and sufficient condition for *ρ*(*n*) to be a unit function of some ±1-valued zero-mean stochastic process on . Since this theorem does not appear to be well known to the stochastic geometry community, we have included the proof of Shepp (1967) in the electronic supplementary material.

*An even function ρ is a unit function on* *if and only if ρ*(0)=1 *and*(1.3)*for every positive integer n and all corner-positive matrices* ** Q**=[

*q*

_{ij}]

*, where an n×n matrix*

*Q**is corner-positive if*(1.4)

*for every n-tuple*(

*e*

_{1}, …,

*e*

_{n})

*with e*

_{k}

*=±*1

*, k=*1

*, …, n.*(

*Without loss of generality, we denote the set of all such ±*1

*-valued n-tuples with e*

_{1}

*=*1

*by*

_{n}

*.*)

For each *n*, the necessary and sufficient condition (1.3) gives an infinite number of inequalities that *ρ* (and hence *S*_{2}) must satisfy. To directly use theorem 1.1, therefore, we must develop a better understanding of corner-positive matrices, which are defined by the 2^{n−1} different inequalities represented by (1.4). However, owing to this intractable form of (1.3) and (1.4), theorem 1.1 has gone mostly unused in the literature since 1955.

The aim of this paper is to restate theorem 1.1 in a more testable and tractable form. To this end, in §2, we present certain properties of corner-positive matrices and, in §3, we present generalizations of theorem 1.1 for ^{d}. In §4, we prove theorem 4.2, a general decomposition formula for all corner-positive matrices. These decompositions allow theorem 1.1 to be rewritten as theorem 4.3. We have explicitly derived these conditions for *n*≤7; these inequalities are presented in §5. We note that, for *n*≤7, condition (1.3), when generalized to ^{d}, is equivalent to inequalities (5.11), (5.15) and (5.16*a*)–(5.16*g*).

In §6, we consider necessary conditions that arise for the important special case of isotropic random media. Finally, in §7, we restate many of our results in terms of *S*_{2} and derive a new lower bound on *S*_{2} for isotropic random media. We note that alternate techniques have been suggested for characterizing *ρ* for certain ±1-valued stationary processes on (Masry 1972) and (Scarf 1953; Martins de Carvalho & Clark 1983; Kiefer & Wynn 1983, 1984; Karakostas & Wynn 1993; Bondesson 2003). We relate several of these necessary conditions to the conceptual framework of corner-positive matrices, extending many of these conditions.

## 2. Properties of corner-positive matrices

For small values of *n*, the corner-positive matrices are easily characterized. For example, [*q*] is corner-positive exactly when *q*≥0, andis corner-positive if and only if *a*+*d*≥|*b*+*c*|. Condition (1.3) thus reduces to *ρ*(0)≥0, for *n*=1, and to |*ρ*(1)|≤1, for *n*=2. These are automatically true by the definition of *ρ*, and hence (1.3) gives no extra information about unit functions for *n*≤2.

To characterize larger corner-positive matrices, we say that ** Q**∼

**for two**

*R**n*×

*n*matrices

**and**

*Q***if there is a positive constant**

*R**k*, so that and if

*i*≠

*j*. Also, if

**is an upper triangular**

*Q**n*×

*n*matrix and

*z*is an

*N*

_{n}-dimensional vector, where

*N*

_{n}=1+

*n*(

*n*−1)/2, we define

**∼**

*Q***if and the other entries of**

*z***are also the upper triangular entries of**

*z***according to a row-first ordering. For example,The first matrix is corner-positive (Shamai & Bar-David 1989), and, as we will note in (5.2), the third matrix is one of the four extremal 3×3 corner-positive matrices.**

*Q*Clearly, ∼ is an equivalence relation on the set of *n*×*n* matrices. Also, if ** Q** is corner-positive and

**∼**

*Q***, then**

*R***is corner-positive, so that ∼ divides the set of corner-positive matrices into equivalence classes. Furthermore, if**

*R***≁**

*Q***0**is a corner-positive matrix, then there are unique numbers

*z*

_{ij}(1≤

*i*<

*j*≤

*n*), so that(2.1)We use this indexing convention throughout this paper. (The formal proofs of these propositions may be found in the electronic supplementary material.)

The relation ∼ may be used to restate definition (1.4), which is as follows. Let *B*_{n} be a 2^{n−1}×*N*_{n} matrix with row vectors of the form(2.2)All *n*-tuples of _{n} with *e*_{1}=1 (to prevent duplicate rows) are used to form the matrix *B*_{n}. Then, the *n*×*n* matrix ** Q** is corner-positive if and only if there is an

*N*

_{n}-dimensional vector

**, so that**

*z***∼**

*Q***and**

*z*

*B*_{n}

**≥**

*z***0**(i.e. each entry of

*B*_{n}

**is non-negative).**

*z*For example, if *n*=3, thenWe note that *B*_{3} is specified up to permutations of the rows. In the electronic supplementary material, we also present the 8×7 matrix *B*_{4}, the 16×11 matrix *B*_{5} and the 32×16 matrix *B*_{6}.

## 3. Generalizations of theorem 1.1 for other unit functions

Theorem 1.1 was originally stated and proved for ±1-valued processes on . Nevertheless, theorem 1.1 may be somewhat generalized; the formal proofs of these generalizations may be found in the electronic supplementary material. First, the assumption that the stochastic process *X* has zero mean can be completely eliminated without changing Shepp's proof of theorem 1.1. We remark in passing that, by including the assumption of zero mean, the function *ρ* is seen to be the autocovariance function of *X*, and the maximal class of unit covariance functions occurs if *X* has zero mean (Shepp 1963).

Second, as shown in the electronic supplementary material, (1.3) is equivalent to the condition (Masry 1972)(3.1)for every positive integer *n*, all *n*×*n* corner-positive matrices ** Q**=[

*q*

_{ij}] and all . We refer to the infinite set of inequalities represented by (3.1) as

_{n}. Each

_{n}is a necessary condition on

*ρ*, while the full set of inequalities

_{3},

_{4}, … is both necessary and sufficient for

*ρ*to be a unit function.

The equivalence relationship ∼ provides the following useful lemma.

*Suppose that* *Q**is an n×n corner-positive matrix, so that* (*3.1*) *holds. Then,* (*3.1*) *also holds for any matrix* *R**in the equivalence class of* ** Q**.

*Therefore, to verify the inequalities*

_{n}

*, it suffices to show that, for every vector*

*z**, corresponding to a corner-positive matrix, we have*

*where we have used the shorthand notation ρ*

_{ij}

*=ρ*(

*t*

_{i})

*−ρ*(

*t*

_{j})

*.*

Third, the index set of the stochastic process *X* can be ^{d} instead of without changing any other details of Shepp's proof of theorem 1.1; this generalization may be inferred from Shepp (1967) and was explicitly stated by Masry (1972) for . Using this third generalization, theorem 1.1 can be related to the well-known necessary condition of positive-definiteness (Ripley 1981; Torquato 1999, 2002). To demonstrate this, let us consider that if ** q**∈

^{n}, then the

*n*×

*n*matrix is clearly corner-positive since the expression in (1.4) reduces to a perfect square asUsing

**, condition (3.1) becomesIf this is true for all**

*Q**n*, all

**∈**

*q*^{n}and all ; this is another way of stating that

*ρ*is a positive-definite function.

## 4. General form of corner-positive matrices

In this section, we show that, for each , each set of inequalities _{n} may be verified by computing (3.1) for a *finite* number of extremal corner-positive matrices. In other words, this short list of inequalities, which we denote by _{n}, implies the full list of inequalities _{n}.

We prove this by determining the convex hull of the row vectors of the matrix *B*_{n}. Recall that *B*_{n}, defined by (2.2), is a 2^{n−1}×*N*_{n} matrix. Consider the 2^{n−1} row vectors of *B*_{n} as points in ^{N}; the first coordinate of each of these points is 1. Let us define _{n} to be the set of 2^{n−1}+1 pointsand let *D*_{n} be the matrix, so that the inequalitiesdescribe the convex hull of _{n}. (Note that the first coordinate of ** x** is indexed using the same convention as in (2.1).) We define

*M*

_{n}to be the number of row vectors of

*D*_{n}, so that

*D*_{n}is an

*M*

_{n}×

*N*

_{n}matrix.

*Let* *y*^{T} *be a row vector of* *D*_{n}*. If* ** Q**∼

*y**, then*

*Q**is corner-positive. In other words, each row vector of*

*D*_{n}

*corresponds to a corner-positive matrix.*

Let *x*^{T} be any row vector of *B*_{n}. By definition, ** x** lies in the convex hull of

_{n}, and so

*D*_{n}

**≥0. Therefore, since**

*x*

*y*^{T}is a row vector of

*D*_{n}, we have

*y*^{T}

**≥0 or**

*x*

*x*^{T}

**≥0.**

*y*Since this inequality is true for all row vectors *x*^{T} of *B*_{n}, it follows that *B*_{n}** y**≥

**0**. In other words, if

**∼**

*Q***, then**

*y***is a corner-positive matrix. ▪**

*Q*We denote the corner-positive matrices of lemma 4.1 by , where . The following theorem states that the are *extremal* corner-positive matrices. That is, if ** Q** is any

*n*×

*n*corner-positive matrix, then

**may be written as a non-negative linear combination of the .**

*Q**An n×n matrix* *Q**is corner-positive if and only if there are non-negative numbers* *, so that*(4.1)*In other words,* *Q**is corner-positive if and only if there is a non-negative M*_{n}*-dimensional vector* *k**, so that*(4.2)*where* ** Q**∼

**.**

*z*To begin, we note from definition (1.4) that the non-negative linear combination (4.1) is corner-positive since each is corner-positive. Therefore, to prove theorem 4.2, it remains to show that if ** Q** is corner-positive, then (4.1) holds.

To this end, let ** Q**∼

**, where**

*z***∈**

*z*^{N}, and consider the following linear program with

*M*

_{n}+1 constraints on

*N*

_{n}free variables:(4.3a)(4.3b)(4.3c)(4.3d)

The feasibility region of (4.3*b*)–(4.3*d*) is clearly both feasible and bounded since it is the convex hull of _{n}. Since the objective function (4.3*a*) is linear, its minimal value is achieved at one of the vertices (Chvátal 1983). In other words, the solution of the linear program (4.3*a*) is .

Since the linear program (4.3*a*)–(4.3*d*) is both feasible and bounded, the dual of (4.3*a*)–(4.3*d*) is also feasible and bounded, and the primal and dual objective functions share the same optimal value (Chvátal 1983). The dual of (4.3*a*)–(4.3*d*) is the following linear program with *N*_{n} constraints on *M*_{n}+1 non-negative variables:(4.4a)

(4.4b)

(4.4c)

Therefore, the optimal value of (4.4*a*)–(4.4*c*) is also given by . That is, the least non-negative value of *q* for whichfor some non-negative vector ** k** isCondition (4.2) holds if and only if

*q*=0, which is equivalent to the inequality

*B*_{n}

**≥**

*z***0**. In other words, (4.2) holds if and only if

**is a corner-positive matrix. ▪**

*Q*Using theorem 4.2, we can restate the necessary and sufficient conditions (3.1).

*Suppose that ρ is an even function on* ^{d}*, so that ρ*(**0**)=1*. Then, for every integer n, ρ satisfies the inequalities* _{n} *if and only if*(4.5)*for all* *and all* .

We refer to inequalities (4.5) as _{n}; there are a finite number of inequalities in _{n} associated with each . Clearly, ; theorem 4.3 states that _{n} implies _{n}. As before, each set of inequalities _{n} is a necessary condition on *ρ*, while the full set of inequalities _{3}, _{4}, … is both necessary and sufficient for *ρ* to be a unit function.

Condition (4.5) may be written more compactly aswhereand we have again used the shorthand notation . Since *D*_{n} defines the convex hull of _{n}, we have the following geometric interpretation of theorem 1.1.

*Suppose that ρ is an even function on* ^{d} *satisfying ρ*(**0**)=1*. Then, ρ is a unit function if and only if, for every n, the image of* *P*_{n} *lies in the convex hull of the row vectors of* *B*_{n}.

## 5. Computation of the inequalities

We have noted that, for each , there is a finite number of inequalities _{n} that imply the full list of inequalities _{n}. In particular, theorem 4.3 permits a restatement of _{n} in terms of the matrix *D*_{n}. In turn, the matrix *D*_{n} is determined by the vertices _{n} or, equivalently, the row vectors of *B*_{n}.

In this and the following sections, we use the double description method (Motzkin *et al.* 1953; Fukuda & Prodon 1996) to explicitly compute *D*_{n} for *n*≤7. An efficient implementation of the double description method may be downloaded from www.ifor.math.ethz.ch/∼fukuda/cdd_home. We also use our computations of *D*_{n} to explicitly describe _{n} for *n*≤7.

We note that the inequalities _{3}, _{4} and _{5} reduce to (5.11), which is a known necessary condition on unit functions (Shepp 1967; Torquato 2006). However, _{6} is equivalent to (5.12) and (5.14), while _{7} is equivalent to these two necessary conditions and the more complex set of inequalities (5.16*a*)–(5.16*g*). Based on these increasingly complex necessary conditions on *ρ*, it would appear that the general problem of reducing the *n*th corner-positive condition is very difficult.

### (a) Computation of _{3}

We begin with the case *n*=3. Using the double description method, we find that the convex hull of _{3} is prescribed by(5.1)so that the extremal 3×3 corner-positive matrices are(5.2)As it turns out, *D*_{3}=*B*_{3}, a coincidence that does not hold for larger values of *n*.

For this simple case, these four matrices may be shown to be extremal without explicitly using theorem 4.2 by instead solving a non-singular system of four equations in four unknowns. The four *k*_{i} required in (4.1) are found to bewhere *z*_{12}, *z*_{13} and *z*_{23} are defined by (2.1). Each of the *k*_{i} must be non-negative if and only if *B*_{3}** z**≥

**0**.

We now use *D*_{3} to find the inequalities _{3}. For , (4.5) becomes(5.3a)for all , where without loss of generality, we have chosen *t*_{3}=**0**. For , and , (4.5) becomes(5.3b)after reindexing. In summary, (5.3*a*) and (5.3*b*) fully describes _{3}.

Inequality (5.3*b*) was noted by Shepp (1967); it does not appear that (5.3*a*) has explicitly appeared in the literature. Both may be derived (Torquato 2006) without explicitly using corner-positive matrices by noting that(5.4)if . This condition is clearly true since each is equal to either 1 or −1, and the sum of three odd numbers must be odd. Expanding (5.4) yields (5.3*a*) if *e*_{1}=*e*_{2}=*e*_{3}. On the other hand, if the three *e*_{i} are not the same, then (5.4) implies (5.3*b*), subject to reindexing.

### (b) Computation of _{4} and _{5}

The double description method may also be used to compute *D*_{4} and *D*_{5} from *B*_{4} and *B*_{5}. The 16×7 matrix *D*_{4} and the 56×11 matrix *D*_{5} are presented in the electronic supplementary material. (Another computation of *D*_{4}, using a different technique from that of theorem 4.2, is also presented in the electronic supplementary material.)

As it turns out, each row of *D*_{4} has the form(5.5)where the 4-tuples satisfy the following properties:(5.6a)(5.6b)(5.6c)(Condition (5.6*c*) is required to prevent a double listing of the row vectors of _{4}.) Substituting into (4.5), we find that the inequalities _{4} are entirely equivalent to (5.3*a*) and (5.3*b*).

For *n*=5, we find that each of the 56 rows of *D*_{5} has the form(5.7)where each 5-tuple satisfies properties (5.6*a*)–(5.6*c*). For the row vectors of *D*_{5} with , (4.5) once again reduces to (5.3*a*) and (5.3*b*). On the other hand, for the other row vectors with , (4.5) reduces to(5.8)where .

As with (5.3*a*) and (5.3*b*), the necessary condition (5.8) may also be found without explicitly using corner-positive matrices by observing that(5.9)This inequality is clearly true since each is equal to either 1 or −1, and the sum of five odd numbers must be odd. Expanding (5.9) yields condition (5.8).

To determine whether (5.8) is a different condition from (5.3*a*) and (5.3*b*), let *ρ*(**0**)=1 and *ρ*(** t**)=−1/3 for all

**≠0. Clearly,**

*t**ρ*satisfies (5.3

*a*) and (5.3

*b*). However, if we choose

*e*

_{1}=⋯=

*e*

_{5}=1 and

*t*_{1}, …,

*t*_{5}distinct, thenthus failing (5.8).

### (c) Computation of _{6}

We have noted that the inequalities _{3}, _{4} and _{5} are equivalent to the simply stated inequalities (5.3*a*) and (5.3*b*) and (5.8). Indeed, suppose that(5.10)where *α* satisfies (5.6*a*)–(5.6*c*). Then, ** Q** must be corner-positive since there must be a positive

*k*, so thatBy (5.6

*b*), this last expression is non-negative, proving that

**is corner-positive. Using (5.10), we obtain the necessary condition(5.11)Inequalities (5.11) are certainly a subset of**

*Q*_{n}, and we suspect that they are also in

_{n}as well for all

*n*. Furthermore, (5.11) may be found without explicitly using corner-positive matrices by expanding the inequality(5.12)

Unfortunately, beginning with *D*_{6}, not all of the row vectors have the form (5.10). This matrix does have row matrices of the form (5.10). However, *D*_{6} also has 192 row vectors of the form(5.13)where the (32)(6)=192 6-tuples are formed by doubling exactly one of the entries of each of the 32 6-tuples of _{6}. The full 368×16 matrix *D*_{6} is presented in the electronic supplementary material.

We now turn to the simplification of (4.5) for *n*=6. It is straightforward to show that _{6} is equivalent to (5.4), (5.9) and the 32 inequalities(5.14)where . As before, the necessary condition (5.14) may be derived without explicitly using corner-positive matrices by expanding the l.h.s. of(5.15)Inequality (5.15) holds since the sum of one even number and five odd numbers must be an odd number.

### (d) Computation of _{7}

We also used the double description method to compute the 116 764×22 matrix *D*_{7}; this matrix is presented in the electronic supplementary material. As expected, of its row vectors have the form (5.10), and of its row vectors may be obtained from (5.15).

Unfortunately, the other rows of *D*_{7} defy easy characterization. As it turns out, the seventh corner-positive condition is equivalent to (5.12), (5.15) and inequalities (5.16*a*)–(5.16*g*). More specifically, 448 row vectors of *D*_{7} may be obtained from (5.16*a*), 1344 row vectors may be obtained from (5.16*b*), 6720 from (5.16*c*), 26 880 from (5.16*d*), 16 128 from (5.16*e*), 40 320 from (5.16*f*) and 23 040 from (5.16*g*).

In (5.16*a*)–(5.16*g*), we use the shorthand notation , where and . It follows that , and it may be directly verified that inequalities (5.16*a*)–(5.16*g*) are true for all 7-tuples in _{7}. However, for (5.16*c*)–(5.16*g*), this verification is significantly more computationally intensive than the intuitive verifications of (5.12) and (5.15),(5.16a)

(5.16b)

(5.16c)

(5.16d)

(5.16e)

(5.16f)

(5.16g)

Inequalities (5.16*a*)–(5.16*g*) may be expanded to yield conditions on *ρ*; the coefficients on *ρ*(*t*_{i}−*t*_{j}), which arise from these expansions, form the row vectors of *D*_{7}.

## 6. Necessary conditions for isotropic *ρ*(*r*)

The inequalities _{3}, …, _{7} are necessary conditions on unit functions *ρ*(** r**); however, directly testing these conditions can be computationally taxing even if

*ρ*is discretized. In this section, we restrict our attention to isotropic random fields, so that we may write

*ρ*(

**)=**

*r**ρ*(

*r*), where

*r*=|

**|. We find inequalities within**

*r*_{3}, …,

_{7}that must be satisfied by

*ρ*(

*r*). Even though these new necessary conditions do not imply (4.5), they may be used as a screen before attempting verification of the inequalities

_{n}.

To begin, we choose *t*_{k}=*k*** r**, where

**∈**

*r*^{d}, for

*k*=1, …,

*n*. Then, condition (4.5) becomesfor all . Since each is upper triangular, we may rewrite this condition as(6.1)The inner sum of (6.1) adds the entries on the main diagonal and superdiagonals of .

For example, for *n*=3, we may use the four extremal matrices (5.2) to obtain the inequalities(6.2a)(6.2b)(6.2c)recall that *ρ*(0)=1. (We observe that both and produce (6.2*b*).) Inequalities (6.2*a*)–(6.2*c*) describe a triangle in the plane and hence do not contain any other redundancies.

For larger values of *n*, the *M*_{n} inequalities (6.1) will contain multiple repetitions. Also, these inequalities will be redundant, and these redundancies may be computationally eliminated by using the double description algorithm of Fukuda & Prodon (1996). We have noted that (6.1) reduces to the three inequalities (6.2*a*)–(6.2*c*) for *n*=3. As it turns out, (6.1) reduces to six inequalities for *n*=4, 12 inequalities for *n*=5, 28 inequalities for *n*=6 and 74 inequalities for *n*=7. These inequalities are explicitly given in the electronic supplementary material.

The inequalities that we find with (6.1) mostly match the results of Martins de Carvalho & Clark (1983), which was perhaps the most computationally comprehensive previous study concerning necessary conditions on *ρ* for *n*≤6. The original context of this study was unit functions *ρ* on ; however, this work may be applied to isotropic unit functions on ^{d}. The necessary conditions reported by Martins de Carvalho & Clark were not found by explicitly using corner-positive matrices. Nevertheless, this work is logically equivalent to eliminating redundancies to find the convex hull of all the inequalities described by (6.1).

For *n*=3–5, our inequalities are identical to those reported by Martins de Carvalho & Clark. For *n*=6, however, Martins de Carvalho & Clark reported six other inequalities in addition to the 28 inequalities found in this study, for a total of 34. In the electronic supplementary material, we explicitly show that it is not possible to express these six additional inequalities as (1.3) using *any* corner-positive matrix. Therefore, it would seem that there are two possibilities for these six anomalous inequalities: either they are incorrect or else it is somehow possible to derive them from all corner-positive inequalities described by (6.1).

For *n*=7, the 74 inequalities found in this study are new. Verifying these 74 inequalities is certainly less computationally taxing than verifying all 116 764 inequalities of (4.5). Therefore, in order to check whether *ρ*(*r*) may be an isotropic unit function, we recommend that the inequalities derived from (6.1) should be verified first. If all of these inequalities are true, then verification of the full set of necessary conditions (4.5) can be attempted.

## 7. Application to random media in ^{d}

### (a) Restatement of main results in terms of stochastic geometry

Most of the preceding discussion has concerned unit functions, defined by (1.1), for ±1-valued stochastic processes on ^{d}. We now turn to characterizing the two-point phase probability function *S*_{2}(** r**) of random media in

^{d}. As discussed in §1, these two functions are related by equation (1.2), and so the necessary conditions

_{n}found in §4 may be restated as necessary conditions on

*S*

_{2}.

For example, the necessary condition (5.3*b*) becomes the so-called triangular inequality (Matheron 1993; Markov 1998; Torquato 2006)(7.1)after using (1.2). Markov (1998) has shown that (7.1) is satisfied if *S*_{2} is monotonically decreasing and convex. Also, Markov gave examples of functions so that

is positive definite, yet

*S*_{2}does not satisfy (7.1), and*S*_{2}satisfies (7.1), yet is not positive definite.

For isotropic media, Markov also showed that (7.1) implies that(7.2)if *S*_{2} is differentiable, so that (0) must be negative.

We now turn to the restatement of theorem 4.3. Clearly, *S*_{2}(** r**) is realizable in

^{d}if and only if there is a ±1-valued process with unit function

*ρ*prescribed by (1.2). Also, (1.2) implies that

*ρ*(

**0**)=1, as required by theorem 4.3. Therefore, we may restate theorem 4.3 for realizable two-point phase probability functions, and we include this restatement here for completeness. (Recall that

*M*is the number of extremal

_{n}*n*×

*n*corner-positive matrices or the number of row vectors of

*D*_{n}.)

*An even function S*_{2}(** r**)

*is a two-point phase probability function in*

^{d}

*if and only if*

*and*(7.3)

*for all*

*and all*.

In the context of stochastic geometry, the necessary conditions (5.11), (5.14) and (5.16*a*)–(5.16*g*) may also be reformulated as necessary conditions on *S*_{2}, providing a practical test for determining whether a prescribed *S*_{2} is realizable. These results complement computational algorithms such as stochastic optimization (Yeong & Torquato 1998; Cule & Torquato 1999; Rozman & Utz 2001, 2002; Sheehan & Torquato 2001), which have been used for the same purpose.

### (b) New necessary condition on inf *S*_{2}(*r*) for isotropic random media

Several necessary conditions on *S*_{2} arise from its definition (Torquato 1999, 2006). For example, we have the limit in the absence of a long-range order. Furthermore, the autocorrelation function must be positive definite, so that the Fourier transform of *Χ*(** r**) is non-negative (Ripley 1981).

We now restrict ourselves to the case of *isotropic* two-phase statistically homogeneous random media in ^{d} without the long-range order. For isotropic media, Torquato (2006) reported the following bounds:(7.4)Also, *S*_{2} must satisfy the following lower bound (Ripley 1981; Matérn 1986), which applies to *all* isotropic random fields (including 0–1 fields):(7.5)whereand where *Γ* is the gamma function and *J*_{n}(*r*) is the Bessel function of the first kind. We observe that and .

Here, we derive a new lower bound on for isotropic random media in two or more dimensions that can be more restrictive than either (7.4) or (7.5) in ^{2}. We begin by noting that the necessary condition (5.11) becomes(7.6)for all *n*-tuples that satisfy conditions (5.6*a*)–(5.6*c*). Let *n* be the least odd number greater than or equal to *d*, and choose the points to be a regular (*n*−1)-simplex with side length *r*. If we choose *α*_{i}=1 for all *i*, then (7.6) becomesAfter isolating and taking the infimum over all *r*, we obtain(7.7)Combining (7.4) with (7.7), we note that(7.8)

In figure 1, we present the bounds (7.5) and (7.8) for ^{2} (so that *n*=3). We note that the lower bound (7.7) is more restrictive than either (7.4) or (7.5) for 0.389≲*ϕ*≲0.611. However, since *C*_{d}→0 as *d*→∞, it appears that the maximum of the lower bounds (7.4) and (7.5) is always more restrictive than (7.7) for *d*≥3.

We now consider the sharpness of the bounds (7.5) and (7.8). The upper bound *ϕ*^{2} is clearly sharp and is attained by Boolean models of finite-sized particles as well as a certain tessellation model formed by a Poisson field of randomly oriented lines (Stoyan *et al.* 1995). The sharpness of the lower bound is currently unknown. For the sake of comparison, the values of inf *S*_{2}(*r*) for the particle phase of a system of hard discs in thermal equilibrium (Torquato & Lado 1985; Quintanilla 1999*b*) are also shown in figure 1. For this system of impenetrable particles, the values of inf *S*_{2}(*r*) are measurably less than *ϕ*^{2}. It would be interesting to determine the sharpest possible lower bound on inf *S*_{2}(*r*) by explicitly using (7.3).

## 8. Conclusions

The reconstruction of random media using the two-point phase probability function *S*_{2} has received considerable attention in the recent literature. However, the only known condition for the realizability of *S*_{2} is virtually untestable in practice. In this article, we present theorem 7.1, which gives for each a finite set of necessary conditions _{n} for a two-point phase probability function *S*_{2}. The union of these necessary conditions is sufficient for *S*_{2} to be realizable.

Theorem 7.1 was a logical consequence of theorem 4.3, which in turn followed from the decomposition formula of theorem 4.2 and McMillan's original theorem 1.1. Theorems 1.1 and 4.2 provide a framework from which many known necessary conditions on *S*_{2} and *ρ* can be derived. Over the years, multiple necessary conditions on these functions have appeared in the literature. These conditions were derived using a wide variety of techniques other than corner-positive matrices. At first glance, these conditions appear to be completely unrelated to each other. Nevertheless, these necessary conditions have been shown to be logically connected with the framework of corner-positive matrices. The examples are as follows.

The well-known necessary condition of positive-definiteness (Ripley 1981; Torquato 1999, 2002) can be derived from condition (3.1) by using the corner-positive matrices

=*Q**qq*^{T}.Shepp (1967) found the triangular inequality (5.3

*b*), which may be recast as (7.1) for*S*_{2}, by noting that the sum of three odd numbers must be odd. (The apparently independent derivation of (7.1) by Matheron (1993) and Markov (1998) is significantly longer and more intricate.)Martins de Carvalho & Clark (1983) reported multiple necessary conditions on unit functions on ; these may be recast for isotropic unit functions on

^{d}. These necessary conditions were found by explicitly studying the compact convex polyhedron formed by the possible values of the*n*-tuple (*ρ*(1), …,*ρ*(*n*)). We have noted that these inequalities may also be derived by using the extremal corner-positive matrices in (6.1) and eliminating redundancies.

We expect that the machinery of corner-positive matrices will provide more testable and tractable conditions for the realizability of a prescribed *S*_{2}(** r**). One example was the new lower bound (7.8) for isotropic random media. It would be useful to describe more fully how

_{n}simplify for the important special case of isotropic random media. For example, it may be possible to use corner-positive matrices to confirm a recent conjecture concerning the first local maximum of

*S*

_{2}(

*r*) for two-dimensional isotropic random media (Jiao

*et al.*2007).

## Acknowledgments

The author thanks Larry Shepp and Herbert Scarf for access to their unpublished technical reports. The author also thanks Jianguo Liu, Christopher Tiftickjian, Osbert Bastani, Di Wu and Salvatore Torquato for their many helpful discussions.

## Footnotes

Electronic supplementary material is available at http://dx.doi.org/10.1098/rspa.2008.0023 or via http://journals.royalsociety.org.

- Received January 22, 2008.
- Accepted February 27, 2008.

- © 2008 The Royal Society