How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma

We discuss linear programming techniques that help to deduce corollaries of non classic inequalities for Shannon's entropy. We focus on direct applications of the copy lemma. These applications involve implicitly some (known or unknown) non-classic universal inequalities for Shannon's entropy, though we do not derive these inequalities explicitly. To reduce the computational complexity of these problems, we extensively use symmetry considerations. We present two examples of usage of these techniques: we provide a reduced size formal inference of the best known bound for the Ingleton score (originally proven by Dougherty \emph{et al.} with explicitly derived non Shannon type inequalities), and improve the lower bound for the optimal information ratio of the secret sharing scheme for an access structure based on the Vamos matroid.


I. INTRODUCTION
We can associate with an n-tuple of jointly distributed random variables its entropy profile that consists of the 2 n − 1 values of Shannon's entropy of each sub-tuple of the given tuple. We say that a point in R 2 n −1 is entropic if it represents the entropy profile of some distribution. The entropic points satisfy different information inequalities -the constraints that characterize the range of admissible entropies for jointly distributed variables. The most known and well understood information inequalities are so-called Shannon-type inequalities that are defined as linear combinations of several instances of the basic inequality I(A : B|C) ≥ 0, where A, B, C are any subsets (possible empty) of random variables.
In 1998 Z. Zhang and R.W. Yeung discovered the first example of an (unconditional) non Shannon-type information inequality, which was a linear inequality for entropies of a quadruple of random variables that cannot be represented as a combination of basic inequalities [4]. Now many other non Shannon-type information are known (including several infinite families of non Shannon-type information inequality), see, e.g., [6], [11], [17].
The works on non-Shannon type information inequalities are focused on the following fundamental question: can we prove some particular property for Shannon's entropy (usually expressed as an equality or an inequality), assuming some specific constraints (which are also given as equalities and inequalities for Shannon's entropy, including Shannon type and non Shannon type universal information inequalities). Not surprisingly, these arguments typically use the technique of linear programming: at the first stage, to derive new informa-tion inequalities (and to prove that they are indeed new) and then, at the second stage, to apply the derived inequalities to some specific problem (e.g., in secret sharing, network coding, and so on). Many applications of this type involve heavy computations: the number of information inequalities in n random variables grows exponentially with n. It seems that in several problems the progress is stopped since the computational complexity of the corresponding linear programs is too high for the modern computers. So the question arises: can we reduce the computational complexity of the relevant problems of linear programming? In this paper we show that in some cases new progress can be made with a reasonable combination of previously known techniques.
Recently Farràs et al., [26], observed that the two stages of the scheme mentioned above (deriving new information inequalities and applying them) can be merged in a unique problem of linear programming: in a specific application of information inequalities, instead of enumerating explicitly all known non-Shannon information inequalities, we can include in a linear program the constraints from which those inequalities are (or can be) derived. The constraints used in [26] were instances of the Ahlswede-Körner lemma, [7]. As a tool of inference of non Shannon type inequalities, the Ahlswede-Körner lemma is essentially equivalent to the Copy Lemma from [17] "cloning" one single random variable, see [20]. In this paper we use a technique similar to [26], but employing the constraints obtained from the Copy Lemma. This permits us to extend the technique: we apply the Copy Lemma to make "clones" of pairs of jointly distributed random variables (instead of copies of individual random variables used in [26]).
To reduce the dimension of the corresponding problem of linear programming, we use symmetries of the problems under consideration. Our usage of symmetries is similar to the ideas proposed in [24], where the authors suggested to use symmetries to reduce the complexity of computing the outer bounds on network coding capacity. For a study of the general problem of Shannon and non Shannon type inequalities for symmetric entropy points we refer the reader to [25].
To illustrate the power of this technique, we discuss two examples. In the first one we give a formal inference of the best known bound for the Ingleton score (originally proven in [17]), with only four auxiliary random variable and three applications of the Copy Lemma. The obtained computerassistant proof is very fast, and the "formally checkable" version of the proof can be reduced to a combination of 167 equalities and inequalities with rational coefficients. In our second example we improve the known lower bound for the optimal information ratio of the secret sharing schemes associated with the Vámos matroid (for the access structure denoted V 0 ).
Though the techniques used in this paper are rather simple, their combination proves to be fruitful. We believe that this approach can be used in other problems of information theory.

Notation:
We denote [n] = {1, . . . , n}. Given a tuple of jointly distributed random variable (X 1 , . . . , X n ) and a set of indices V = {i 1 , . . . , l k } ⊂ [n] we denote by H(X V ) the Shannon entropy H(X i1 , . . . , X i k ). We fix an arbitrary order on nonempty subsets of the set of indices [n] and assign to each distribution X = (X 1 , . . . , X n ) its entropy profile, i.e., the vector of 2 n −1 entropies H(X V ) (for all non-empty V ⊂ [n]).
We say that a point in the space V n = R 2 n −1 is entropic if it represents the entropy profile of some distribution. Following [4], we denote by Γ * n the set of all entropic points. We denote byΓ * n the topological close Γ * n ; its elements are called almost entropic.
We use the standard abbreviations for linear combinations of coordinates in the entropy profile: We extend this notation to almost entropic points.

II. COPY LEMMA
The following lemma was used (somewhat implicitly) in the very first proof of a non Shannon type inequality in [4], see also [18,Lemma 14.8]. The general version of this lemma appeared in [9] and [17]. In [17] it was presented explicitly, with a complete and detailed proof.
Lemma 1 (Copy Lemma): For every tuples of jointly distributed random variables (X, Y, Z) there exists a distribution (A, B, C, C ′ ) such that • the distribution (A, B, C) coincides with the distribution of (X, Y, Z); the distribution of (A, C ′ ) coincides with the distribution of (X, Z), and In what follows we abuse the notation and identify (A, B, C) with (X, Y, Z). That is, we say that the initial distribution (X, Y, Z) can be extended 1 to the distribution (X, Y, Z, Z ′ ), where (X, Z) and (X, Z ′ ) have isomorphic joint distributions, and I(Z ′ ; Y, Z|X) = 0. Following [17], we say that Z ′ is a Y -copy of Z over X, denoted by Z ′ := Y -copy(Z|X). 1 Formally speaking, such an "extension" may require a subdivision of the initial probabilistic space, so technically (A, B, C) and (X, Y, Z) are defined on different probabilistic spaces.
Note that Lemma 1 remains valid if X, Y, Z are not individual variables but tuples of variables.
F. Matúš and L. Csirmaz proposed several extensions and generalizations of the Copy Lemma (polymatroid convolution, book extension, maximum entropy extension, see, e.g., [12], [22], [23]). However, to the best of our knowledge, the "classic" version of the Copy Lemma is strong enough for all known proofs of non Shannon type inequalities All known proofs of (unconditional) non Shannon type information inequalities can be presented in the following style: we start with a distribution (X 1 , . . . , X n ); using the Copy Lemma we supplement to this distribution several new variable (Y 1 , . . . , Y k ); then we enumerate the basic Shannon's inequalities for the joint distribution (X 1 , . . . , X n , Y 1 , . . . , Y k ) and show that a combination of these inequalities (together with the constraints from the Copy Lemma) gives the desired new inequality for (X 1 , . . . , X n ) (the entropy terms with new variable Y j should be canceled). We refer the reader to [17] for many instances of this argument.
In what follows we use a very similar scheme of proof. The difference is that we superimpose constraints (equalities for the coordinates of the entropy profile of (X 1 , . . . , X n )) that are specific for the given specific problem. That is, in each application we prove a conditional non Shannon type inequality (which is valid only assuming some linear constraints for the entropy quantities). Each of these arguments can be theoretically translated in a more conventional style: we can at first prove some new unconditional non Shannon type inequalities, and then combine them with the given constraints and deduce the desired corollary. However, we do not need to reveal and formulate explicitly these unconditional inequalities hidden behind the proof.

III. SYMMETRIES
In this section we discuss a simple formalism of symmetry considerations that helps to reduce the dimension of a linear programs associated with problems concerning information inequalities (assuming that the problem has a particular symmetric structure). A similar formalism (action of permutations on multidimensional distributions and their entropy profiles, information inequalities for distributions with symmetric entropy profiles) was systematically studied in [25].
Let X (n) = (X 1 , . . . , X n ) be a joint distribution of n random variables. We denote by H(X) its entropy profile. Let π : [n] → [n] be a permutation of indices (an n-permutation). This permutation induces a natural transformation of the distribution X, and therefore a transformation of the entropy profile Example 1: If π is the transposition of indices 1 and 2, then the mapping defined above exchanges the entropy values H(X 1 ) and H(X 2 ), the values H(X 1 , X 3 ) and H(X 2 , X 3 ), etc., and does not change the values H(X 1 , X 2 ), Thus, every permutation of indices π induces a transformation of the set of all entropic points Γ * n . This transformation of the entropic points can be naturally extended to a linear transformation of the entire space V n (defined by a suitable permutation of the coordinate axis). In what follows we denote this transformation by T π . (Note that π is a permutation on n elements, while T π is a transformation of the space of dimension 2 n − 1.) In the usual algebraic terminology, we can say that we defined a representation of the symmetric group (the group of all n-permutations) by linear transformations of the space V n .
We say that a point We denote the set of G-invariant points in V n by Inv(G). In what follows we typically study linear and affine spaces that are G-invariant for some specific group of permutations G. Note that every G-invariant linear space in V n contains the set Inv(G) as a subspace.
The sets of all entropic and all almost entropic points (Γ * n andΓ * n respectively) are obviously π-invariant for every npermutation π. For every group G of n-permutations, the intersections of Γ * n orΓ * n with any G-invariant set gives another G-invariant set. In what follows we discuss several simple examples of this type.
Example 2: Let L ent be the set of points in Γ * 4 such that Since L ent is defined by affine conditions, it can be represented as the intersection of Γ * 4 with an affine subspace L (of co-dimension 5) in the entire space V 4 = R 15 . It is easy to see that this subspace L is invariant with respect to transpositions π 12 and π 34 (π 12 exchanges the indices 1 and 2, and π 12 exchanges the indices 3 and 4). Therefore, this subspace is G-invariant, where G is the subgroup of the symmetric group generated by the transpositions π 12 and π 34 (this subgroup consists of four permutations).
We say that a linear function Similarly, for a subgroup of n-permutations G, we say that a linear function is G-invariant, if it is π-invariant for every π ∈ G.
Example 3: Ingleton's quantity Ing(X 1 , X 2 , X 3 , X 4 ) defined as can be extended to a linear function on the space V 4 = R 15 . This function is invariant with respect to the transposition of indices 1 and 2, to the transposition of indices 3 and 4, and with respect to the group (of size four) generated by these two transpositions.
Claim 1: Let G = {π 1 , . . . , π k } be a subgroup of npermutations, and let x be a point in V n . Then the center of mass of the points is G-invariant. Proof: It is easy to see that the set of points (1) is πinvariant for each π ∈ G. Therefore, the center of mass of this set is also G-invariant.
Lemma 2: Let G = {π 1 , . . . , π k } be a subgroup of npermutations, L be a G-invariant convex set in V n , and F : V n → R be a G-invariant linear function. Then Proof: It is enough to prove that for every x ∈ L there exists a y ∈ L ∩ Inv(G) such that To this end we take the points and define y as the center of mass of these k points. Since L is G-invariant, each point T πi (x) belongs to L. From convexity of L it follows that y also belongs to L, and Claim 1 implies that y belongs to Inv(G). Thus, the constructed point belongs to L ∩ Inv(G).
On the other hand, from G-invariance of F it follows that Since F is linear, we conclude that F at the center of mass of T πi (x) is equal to the same values as the points in (2), and the lemma is proven. Example 4: Assume we are looking for the minimum of Ing(X 1 , X 2 , X 3 , X 4 ) (see Example 3) on the set of almost entropic points (points inΓ * 4 ) that satisfy the linear constraints (see Example 2). We define G as the group of permutations generated by two transpositions π 12 and π 34 that exchange the indices (1, 2) and (3, 4) respectively.
We claim that the required extremal value of Ing(X 1 , X 2 , X 3 , X 4 ) is achieved at some G-invariant point. Indeed, the given constraints define in V 4 a G-invariant affine subspace. The intersection of this subspace with the convex coneΓ * 4 is a G-invariant convex set. On the other hand, Ingleton's quantity Ing(X 1 , X 2 , X 3 , X 4 ) is a G-invariant linear function. Therefore, we can apply Lemma 2 and conclude that desired extremum is achieved at some point in Inv(G).

IV. THE STANDARD BENCHMARK: BOUNDS FOR INGLETON'S QUANTITY
It is widely believed that one of the most interesting questions on the structure ofΓ * 4 is the question on the Ingleton's quantity: what is the worst possible violation of Ingleton's' inequality Ing(A, B, C, D) ≥ 0.
This inequality is true for linearly representable entropic points but for some other entropic points it is violated (see [5]). The question is how far below 0 can go the Ingleton score Ing(A, B, C, D) H(A, B, C, D) (here we use the terminology from [17]). From the Shannon type inequalities it follows only that this score is greater than −1/4. The first non Shannon type inequality from [4] implies that this score is greater than −1/6. The best bound was discovered by Dougherty et al.: Theorem 1 (originally proven in [17] The objective function Ing(A, B, C, D) and the normalization constraint are invariant with respect to the transpositions π A,B and π C,D that exchange the variables A, B and C, D respectively. Therefore, we can apply Lemma 2 and conclude that the required minimal value can be found in the space of points that are π A,B -and π C,D -invariant.
The invariance means that we can restrict ourselves to the points inΓ * 4 such that     Technically, this means that we take the conditions (equalities) from the Copy Lemma (Lemma 1) that determine the entropies of the introduced variables and the properties of conditional independence for each instance of the Copy Lemma. At last, we add to the normalization condition H(A, B, C, D) = 1 and the constraints (4) and (5)  This problem is easily for the standard linear programming solvers (we made experiments with the solvers [27]- [29]). We can extract from the dual solution of this linear program a rational combination of inequalities that gives the desired bound (without floating point arithmetics nor rounding). We present this "formally checkable" proof in Appendix.

V. SECRET SHARING SCHEMES ON THE VÁMOS MATROID
The notion of a secret sharing scheme was introduced by Shamir [2] and Blakley [1]. Nowadays, secret sharing is an important component of many cryptographic protocols. We refer the reader to [15] for an excellent survey of secret sharing and its applications.
The aim of perfect secret sharing is to distribute a secret value among a set of parties in such a way that only the qualified sets of parties can recover the secret value; the nonqualified sets should have no information about the secret. The family of qualified sets of parties is called the access structure of the scheme. This family of sets must be monotone (a superset of a qualified set is also qualified).
The information ratio of a secret sharing schemes is the maximal ratio between the size (the entropy) of a share and the size (the entropy) of the secret. The optimization of this parameter is the central problem of secret sharing. This question was extensively studied for several families of access structures. The main technique for proving lower bounds on complexity of secret sharing schemes is nowadays the linear programming applied to the constraints formulated in terms of classic and non-classic information inequalities, see [19].
In what follows we apply our technique (the Copy Lemma combined with symmetry considerations and linear programming) to one of the classic access structures -the access structure defined on the Vámos matroid (more technically, one of two access structures that can be defined on the Vámos matroid). We skip the general motivation (the Vámos matroid is particularly interesting as a simple example of a non-representable matroid, see [15] for details) and formulate directly the problem of the information ratio for this access structure in terms of Shannon's entropy of the involved random variables.
We define an access structure with parties {1, . . . , 7}. The minimal qualified sets are the 3-sets {1, 2, 3}, {1, 4, 5} and all 4-sets not containing them, with three exceptions {2, 3, 4, 5}, {2, 3, 6, 7}, {4, 5, 4, 7}. We deal with jointly distributed random variables (S 0 , . . . , S 7 ), where S 0 is the secret and S 1 , . . . , S 7 are the shares given to the seven parties involved in the scheme. We require that (i) for every minimal qualified set V listed above . Under these constraints, we are looking for the extremal value Since the set of almost-entropic points is a closed convex cone, we can add the normalization H(S 0 ) = 1 and rewrite the objective function as It is known that the required minimum is not greater than 4/3, [14]. The history of improvements of the lower bound for this problem is presented in the Notice that the objective function, the normalization condition H(S 0 ) = 1, and the linear constraints in (i) and (ii) above are invariant with respect to the permutation that • swap the indices 2 and 3, • swap the indices 4 and 5, • swap the indices 6 and 7, • swap the pairs (2, 3) and (4, 5). Therefore we can apply Lemma 2 and reduce the problem to those almost entropic points that satisfy the symmetries defined above.
These two conditions can be merged in one (more symmetric) constraint Thus, we obtain a linear program with the following constraints: • the conditions (i) and (ii) that define the access structure of the secret sharing scheme, • the normalization H(S 0 ) = 1, • the equalities that follow from the symmetry of the access structure, • the conditions of the two instances of the Copy Lemma, • and the Shannon type inequalities for twelve random variables (S 0 , . . . , S 7 , V ′ , V ′′ , W ′ , W ′′ ) (i.e., for 2 12 − 1 coordinates of their entropy profile). The goal is to optimize the objective function (6).
Remark 2: We do not need to include in the linear program the variables V and W and their entropies -these two variables are used only as a notation in the Copy Lemma. With a help of a computer (we used the solvers [27]- [29]) we find the optimal solution of this linear program: it is equal to 561/491. Thus we establish the following statement.
Theorem 2: The optimal information rate of the secret sharing scheme for the access structure V 0 on the Vámos matroid is not less than 561/491 = 1.142566 . . .

Remark 3:
The standard linear programming solvers use the floating point arithmetic, and we should keep in mind the rounding errors. Our linear program contains only constraints with integer coefficients, so the values of the variables for the optimal solution of this linear program (the primal and the dual) can be taken rational. These rational values can be found by exact computing, without rounding. To compute the exact solution of a linear program we use the rational linear programming solver QSopt_ex, see [10], [27].
The found exact dual solutions (rational linear combinations of constraints) for this linear program consist of more than 10 3 equalities and inequalities. The found rational linear combinations of equalities and inequalities provide a formal mathematical proof of Theorem 2, though such a proof hardly can be called "human-readable." Computing the exact solution of a linear program is rather time consuming. If we only need a lower bound for the optimal solution, it is enough to find a feasible solution of the dual problem that approximates (well enough) the optimal solution. Such an approximation can be found much faster than the exact ration solution, with more conventional floating point LP solvers.

Remark 4:
The linear program constructed in this section would have the same optimal value if we omit the symmetry conditions (note that, unlike the previous section, in the proof of Theorem 2 the Copy Lemma is applied in symmetric settings). However, these symmetry conditions are not useless. In our experiments with exact computations, the symmetry constraints help to find a rational solution of the dual problem with smaller denominators. Also, in several experiments with floating point solvers, the symmetry constraints make the computation (or approximation) of the optimal solution faster. However, this is not a universal rule: in some experiments the symmetry constraints make the computation only slower -it depends on the used linear programming algorithm and on the chosen scaling of the objective function and of the constraints.

VI. CONCLUSION
When we derive balanced information inequalities, the technique of the Copy Lemma with "clones" of individual random variables is equivalent to the technique of the Ahlswede-Körner lemma, see [20]. In this paper we used the Copy Lemma in a stronger form, making "clones" of pairs of correlated variables. In the proofs of Theorem 1 and Theorem 2 it was crucial that we can "duplicate" in one shot a pair of correlated random variables, not only a single random variable The Ahlswede-Körner lemma used in [26] has a clear intuitive meaning: it can be interpreted in terms of extraction of the common information, see [7] and [6]. It would be interesting to find a structural property of the probability distribution that would give an intuitive explanation of the efficiency of the Copy Lemma with two (or more) copied variables.

APPENDIX
In what follows we present a list of 167 equalities and inequalities. An integer linear combination of these inequalities implies Theorem 1.