Constructing realizations of random media with a specified two-point phase probability function S2 has attracted considerable attention in the recent literature. However, little is known about conditions under which a prescribed S2 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 S2, extending many of these conditions.
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 S2(t1, t2), which is the probability that the two points t1 and t2 both lie in a given phase (say phase 1). We may explicitly write this function as S2(t1, t2)=E[I(t1)I(t2)], where I(t) is the indicator function for phase 1. Typically, we assume that S2 is translationally invariant, so that we may write S2(t1, t2)=S2(r), where r=t2−t1. Since S2(t1, t2)=S2(t2, t1), we note that S2(r)=S2(−r), so that S2 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 1999a; Milton 2002; Torquato 2002; Monetto & Drugan 2004; Buryachenko 2007). A wide variety of techniques have been introduced in the literature for computing S2 for various mathematical models (Torquato & Stell 1982; Roberts & Teubner 1995; Stoyan et al. 1995; Markov et al. 1996; Roberts & Knackstedt 1996; Quintanilla 1999a,b; Torquato 2002).
Recently, the inverse problem of constructing visualizations of random materials with a specified S2 has received significant attention. In principle, S2 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 S2, 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 S2 may be inferred from the properties of X(r)=2I(r)−1, a ±1-valued stochastic process. We define(1.1)to be a unit function. By expanding (1.1), we note that(1.2)where ϕ=S2(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=[qij], where an n×n matrix Q is corner-positive if(1.4)for every n-tuple (e1, …, en) with ek=±1, k=1, …, n. (Without loss of generality, we denote the set of all such ±1-valued n-tuples with e1=1by n.)
For each n, the necessary and sufficient condition (1.3) gives an infinite number of inequalities that ρ (and hence S2) must satisfy. To directly use theorem 1.1, therefore, we must develop a better understanding of corner-positive matrices, which are defined by the 2n−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.16a)–(5.16g).
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 S2 and derive a new lower bound on S2 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∼R for two n×n matrices Q and R if there is a positive constant k, so that and if i≠j. Also, if Q is an upper triangular n×n matrix and z is an Nn-dimensional vector, where Nn=1+n(n−1)/2, we define Q∼z if and the other entries of z are also the upper triangular entries of Q 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.
Clearly, ∼ is an equivalence relation on the set of n×n matrices. Also, if Q is corner-positive and Q∼R, then R is corner-positive, so that ∼ divides the set of corner-positive matrices into equivalence classes. Furthermore, if Q≁0 is a corner-positive matrix, then there are unique numbers zij (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 Bn be a 2n−1×Nn matrix with row vectors of the form(2.2)All n-tuples of n with e1=1 (to prevent duplicate rows) are used to form the matrix Bn. Then, the n×n matrix Q is corner-positive if and only if there is an Nn-dimensional vector z, so that Q∼z and Bnz≥0 (i.e. each entry of Bnz is non-negative).
For example, if n=3, thenWe note that B3 is specified up to permutations of the rows. In the electronic supplementary material, we also present the 8×7 matrix B4, the 16×11 matrix B5 and the 32×16 matrix B6.
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=[qij] 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 havewhere we have used the shorthand notation ρij=ρ(ti)−ρ(tj).
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 Q, condition (3.1) becomesIf this is true for all 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 Bn. Recall that Bn, defined by (2.2), is a 2n−1×Nn matrix. Consider the 2n−1 row vectors of Bn as points in N; the first coordinate of each of these points is 1. Let us define n to be the set of 2n−1+1 pointsand let Dn 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 Mn to be the number of row vectors of Dn, so that Dn is an Mn×Nn matrix.
Let yT be a row vector of Dn. If Q∼y, then Q is corner-positive. In other words, each row vector of Dn corresponds to a corner-positive matrix.
Let xT be any row vector of Bn. By definition, x lies in the convex hull of n, and so Dnx≥0. Therefore, since yT is a row vector of Dn, we have yTx≥0 or xTy≥0.
Since this inequality is true for all row vectors xT of Bn, it follows that Bny≥0. In other words, if Q∼y, then Q is a corner-positive matrix. ▪
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 Q may be written as a non-negative linear combination of the .
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 Mn-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∼z, where z∈N, and consider the following linear program with Mn+1 constraints on Nn free variables:(4.3a)(4.3b)(4.3c)(4.3d)
The feasibility region of (4.3b)–(4.3d) is clearly both feasible and bounded since it is the convex hull of n. Since the objective function (4.3a) 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.3a) is .
Since the linear program (4.3a)–(4.3d) is both feasible and bounded, the dual of (4.3a)–(4.3d) is also feasible and bounded, and the primal and dual objective functions share the same optimal value (Chvátal 1983). The dual of (4.3a)–(4.3d) is the following linear program with Nn constraints on Mn+1 non-negative variables:(4.4a)
Therefore, the optimal value of (4.4a)–(4.4c) 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 Bnz≥0. In other words, (4.2) holds if and only if Q is a corner-positive matrix. ▪
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 Dn 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 Pn lies in the convex hull of the row vectors of Bn.
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 Dn. In turn, the matrix Dn is determined by the vertices n or, equivalently, the row vectors of Bn.
In this and the following sections, we use the double description method (Motzkin et al. 1953; Fukuda & Prodon 1996) to explicitly compute Dn 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 Dn 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.16a)–(5.16g). Based on these increasingly complex necessary conditions on ρ, it would appear that the general problem of reducing the nth 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, D3=B3, 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 ki required in (4.1) are found to bewhere z12, z13 and z23 are defined by (2.1). Each of the ki must be non-negative if and only if B3z≥0.
We now use D3 to find the inequalities 3. For , (4.5) becomes(5.3a)for all , where without loss of generality, we have chosen t3=0. For , and , (4.5) becomes(5.3b)after reindexing. In summary, (5.3a) and (5.3b) fully describes 3.
Inequality (5.3b) was noted by Shepp (1967); it does not appear that (5.3a) 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.3a) if e1=e2=e3. On the other hand, if the three ei are not the same, then (5.4) implies (5.3b), subject to reindexing.
(b) Computation of 4 and 5
The double description method may also be used to compute D4 and D5 from B4 and B5. The 16×7 matrix D4 and the 56×11 matrix D5 are presented in the electronic supplementary material. (Another computation of D4, 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 D4 has the form(5.5)where the 4-tuples satisfy the following properties:(5.6a)(5.6b)(5.6c)(Condition (5.6c) 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.3a) and (5.3b).
For n=5, we find that each of the 56 rows of D5 has the form(5.7)where each 5-tuple satisfies properties (5.6a)–(5.6c). For the row vectors of D5 with , (4.5) once again reduces to (5.3a) and (5.3b). On the other hand, for the other row vectors with , (4.5) reduces to(5.8)where .
As with (5.3a) and (5.3b), 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.3a) and (5.3b), let ρ(0)=1 and ρ(t)=−1/3 for all t≠0. Clearly, ρ satisfies (5.3a) and (5.3b). However, if we choose e1=⋯=e5=1 and t1, …, t5 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.3a) and (5.3b) and (5.8). Indeed, suppose that(5.10)where α satisfies (5.6a)–(5.6c). Then, Q must be corner-positive since there must be a positive k, so thatBy (5.6b), this last expression is non-negative, proving that Q is corner-positive. Using (5.10), we obtain the necessary condition(5.11)Inequalities (5.11) are certainly a subset of 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 D6, not all of the row vectors have the form (5.10). This matrix does have row matrices of the form (5.10). However, D6 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 D6 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 D7; 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 D7 defy easy characterization. As it turns out, the seventh corner-positive condition is equivalent to (5.12), (5.15) and inequalities (5.16a)–(5.16g). More specifically, 448 row vectors of D7 may be obtained from (5.16a), 1344 row vectors may be obtained from (5.16b), 6720 from (5.16c), 26 880 from (5.16d), 16 128 from (5.16e), 40 320 from (5.16f) and 23 040 from (5.16g).
In (5.16a)–(5.16g), we use the shorthand notation , where and . It follows that , and it may be directly verified that inequalities (5.16a)–(5.16g) are true for all 7-tuples in 7. However, for (5.16c)–(5.16g), this verification is significantly more computationally intensive than the intuitive verifications of (5.12) and (5.15),(5.16a)
Inequalities (5.16a)–(5.16g) may be expanded to yield conditions on ρ; the coefficients on ρ(ti−tj), which arise from these expansions, form the row vectors of D7.
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=|r|. We find inequalities within 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 tk=kr, 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.2b).) Inequalities (6.2a)–(6.2c) describe a triangle in the plane and hence do not contain any other redundancies.
For larger values of n, the Mn 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.2a)–(6.2c) 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 S2(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 S2.
For example, the necessary condition (5.3b) 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 S2 is monotonically decreasing and convex. Also, Markov gave examples of functions so that
is positive definite, yet S2 does not satisfy (7.1), and
S2 satisfies (7.1), yet is not positive definite.
For isotropic media, Markov also showed that (7.1) implies that(7.2)if S2 is differentiable, so that (0) must be negative.
We now turn to the restatement of theorem 4.3. Clearly, S2(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 Mn is the number of extremal n×n corner-positive matrices or the number of row vectors of Dn.)
An even function S2(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.16a)–(5.16g) may also be reformulated as necessary conditions on S2, providing a practical test for determining whether a prescribed S2 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 S2(r) for isotropic random media
Several necessary conditions on S2 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, S2 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 Jn(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.6a)–(5.6c). 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 Cd→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 S2(r) for the particle phase of a system of hard discs in thermal equilibrium (Torquato & Lado 1985; Quintanilla 1999b) are also shown in figure 1. For this system of impenetrable particles, the values of inf S2(r) are measurably less than ϕ2. It would be interesting to determine the sharpest possible lower bound on inf S2(r) by explicitly using (7.3).
The reconstruction of random media using the two-point phase probability function S2 has received considerable attention in the recent literature. However, the only known condition for the realizability of S2 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 S2. The union of these necessary conditions is sufficient for S2 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 S2 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.
Shepp (1967) found the triangular inequality (5.3b), which may be recast as (7.1) for S2, 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 S2(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 S2(r) for two-dimensional isotropic random media (Jiao et al. 2007).
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.