{'fraction_non_alphanumeric': 0.04273231031543052, 'fraction_numerical': 0.0076193520886615514, 'mean_word_length': 3.6665837891596222, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Entropic Weighted Rank Function

It is known that the entropy function over a set of jointly distributed random variables is a submodular set function. However, not any submodular function is of this form. In this paper, we consider a family of submodular set functions, called weighted rank functions of matroids, and study the necessary or sufficient conditions under which they are entropic. We prove that weighted rank functions are located on the boundary of the submodularity cone. For the representable matroids over a characteristic 2 field, we show that the integer valued weighted rank functions are entropic. We derive a necessary condition for constant weight rank functions to be entropic and show that for the case of graphic matroids, this condition is indeed sufficient. Since these functions generalize the rank of a matroid, our findings generalize some of the results of Abbe et. al. about entropic properties of the rank function of matroids.


INTRODUCTION
For a set of random variables with a given joint distribution, the entropy region is defined as the collection of the entropies of the joint of non-empty subsets of those variables. Entropic region plays an important role in information theory. A geometric representation of the entropy region is the set of points in R 2 n −1 where n is the number of random variables. Consider a point in R 2 n −1 with its coordinates indexed by the nonempty subsets of the variables and the value of the S-th position is the joint entropy of the variables in the set S. We refer to any such point as an entropic point. The set of all entropic points is called the entropic region and is denoted by Γ * n . It is known that the closure of Γ * n is a convex cone. However, we do not exactly know the structure of the boundary of this set. Another important property of Γ * n is the submodularity; (See [7].) Any inequality that is obtained by taking a non-negative linear combination of submodularity constraints is called a Shannon type inequality. Let Γ n be the set of all the nonnegative points in R 2 n −1 which satisfy all the submodularity constraints and is also non-decreasing. Γ n is known to be a convex cone. ( [7].) Γ n is called the submodularity cone. Therefore, the submodularity constraint of the entropic point can be written as Γ * n ⊆ Γ n . In [7], it is proven that for n > 3, the above containment is strict. There has been a significant effort to derive inequalities beyond Shannon type ones, that are satisfied for any entropic point. These inequalities, called non-Shannon type, are necessary conditions for a submodular function to be entropic. In this work, we take a different path and instead of finding necessary conditions, we investigate sufficient conditions for a class of submodular functions, called weighted ranks, to be entropic. The reason we are interested in weighted rank functions, besides the fact that they contain the family of rank function of matroids, is that they have nice geometric interpretation which we explain more in Theorem 1.
In [1], it is shown that if M is a matroid on a ground set of size n, then the rank function of M is entropic when the matroid is representable over a characteristic 2 finite field. Our founding is an extension of this result since, for these matroids, we prove that weighted rank functions are entropic and the rank function is a special case of weighted rank functions. We must emphasise that, as we show an example in Figure  2 a simple reduction of weighted rank function to the rank function of a new matroid does not work.
Beyond integral weights, we also consider the case where all the weights are equal non negative numbers. We derive necessary as well as sufficient conditions for the general weighted rank function of binary matroids to be entropic. For graphic matroids, we provide a necessary and sufficient condition for a constant weight rank function to be entropic.
In the rest of this paper, after we briefly review the basic definitions and notations, we state the problem of interest and the main results. Then we present the technical proofs and finally, we discuss two important points about our results.

PRELIMINARIES
In this section we review some standard definitions and basic facts related to convex polytopes [2], matroids [5] and information theory [3], [7].

A. Matroid Theory
A matroid M = (M, I) is defined as a pair of a finite set E and a family I ⊆ 2 M satisfying the following conditions: • ∅ ∈ I • I 1 ⊆ I 2 ∈ I implies I 1 ∈ I • if I 1 , I 2 ∈ I and |I 1 | ≤ |I 2 | then there is an element e ∈ I 2 \I 1 , such that I 1 ∪ {e} ∈ I The M is called the ground set and each I ∈ I is called an independent set.
The matroid rank function denoted by r(.) is defined as: where |I| is cardinality of I. Matroid rank function enjoys the following properties.
Furthermore, any function which satisfies the above properties is the rank function of some matroid. (See [5]).
A circuit of M is a nonempty minimial dependent set and a base of M , B(M), is a maximal independent set. Proposition 1. If C 1 and C 2 are distinct circuits and e ∈ C 1 ∩ C 2 , then (C 1 ∪ C 2 )\e contains a circuit.
A graphic matroid is a matroid whose ground set is the edge set of a graph and its independent sets are the edges which form a forest. Another important class of matroids is the class of linear matroids that is defined as follows. Let M = {1, 2, . . . , n} and A be a matrix with columns v 1 , . . . , v n over F. Define: A matroid is representable over a field F if it is isomorphic to a linear matroid over the field F.
All graphic matroids are representable over F 2 and R and their representative matrices are the incidence matrix of the graph.

B. Convex Polytopes
Next, we review basics of convex polytopes. We follow the. terminology of [2]. More results and examples on this topic can be found in [6].
A set C is convex when the closed segment between any two points of C is contained in C. C is called affine when the line through any two distinct points in it lies entirely inside C.
A polyhedron in R n is the intersection of finitely many halfspaces. A polytope is a bounded polyhedron. Equivalently, a polytope is the smallest convex set containing a given finite set of points called its. vertices. (See [2] for a proof.) Given a convex set P ⊆ R n , a point x ∈ P is an extreme point of P if there do not exist points u, v = x in P such that x is a convex combination of u and v. For polytopes, both the notions of vertex points and extreme points coincide. (See [2] for more details.) A cone is a set C ⊆ R n such that it is closed under nonnegative scalar multiplication. A convex cone is a cone that is also convex.

C. Information theory
For a random variable X the entropy H(X) is defined as: Definition 1. We define Ber(p) to be a Bernoulli variable that takes value 1 with probability p and the value 0 with probability q = 1 − p.
When X is distributed as Ber( 1 2 ) we have H(X) = 1. Let H n be the k-dimensional Euclidean space with the coordinates labeled by h α , α ∈ 2 Nn \{∅}, where N = {1, 2, . . . , n} and h α corresponds to the value of H θ (α) for any collection θ of n random variables. We will refer to H n as the entropy space for n random variables. Then an entropy function H θ can be represented by a column vector in H n . A column vector h ∈ H n is called entropic if h is equal to the entropy function H θ of some collection θ of n random variables.( [7])

PROBLEM FORMULATION AND RESULTS
Throughout this section, we assume that M = (M, I) is a representable matroid over the finite field F and the ground set M = {1, 2, . . . , n}. We let w : M → R ≥0 be a weight function defined on M . Given w, we define the function φ w : 2 M → R as follows: We will use φ w for φ M,w when M is clear from the context. For an arbitrary weight function w, φ w is called the weighted rank of M with respect to w.

Proposition 2. For every non-negative weight function w, φ w is a submodular function.
In Appendix -C, we present our proof of the fact that for any non-negative weight w, φ w is submodular. Therefore, if we consider the vector Φ = (φ(A)) ∅ =A∈2 M , it belongs to Γ n , the convex submodularity cone of order n. In the next section we prove that Φ is in fact a vertex of the polytope P = Γ n ∩S in which S is an Affine subspace of co-dimension n containing all the points in R 2 n −1 whose coordinates {a} is equal to w(a) for every single point a ∈ M . In other words, if we consider all the points in R 2 n −1 that share the same values w(a) at the coordinates indexed by the subsets {a}. This is summarised in the following theorem.
Theorem 1. For every choice of non-negative weights w and any matroid M, φ M,w is a vertex of the polytope P defined as above.
In particular, this implies that Φ belongs to the boundary of Γ n . Now, the question of interest is that, for a given matroid M and the weight function w, is Φ an entropic point; i.e. is Φ ∈ Γ * n ?
In [1], Abbe et.al. proved that for any representable matroid over the binary field and the constant weight function w = 1, the answer is affirmative. In fact, for the constant function w = 1, φ w is simply the usual rank function of the matroid. In this paper we prove the following results.
Theorem 2. Let M be a representable matroid over the field F 2 and w is any non-negative integer weight function on M . Then, φ w,M is entropic.
We also consider the non-integral weight function over certain matroids and derive necessary or sufficient conditions under which Φ is entropic.
Finally, we prove the converse of Theorem 3 for graphic matroids.

TECHNICAL DETAILS OF THE PROOFS
In this section after we stated some useful lemmas, we prove the main results of the paper stated in the previous section. Proof. Since there is no circuit in B, it is an independent set. Also, at each round, the remaining elements are generating since we always remove the element from a circuit. Take any other base B ′ . Let e be an element that e ∈ B\B ′ . Adding e to B ′ creates a circuit, and deleting any element of that circuit would create another base. Let's add e and delete the lightest element of that circuit. That lightest element is definitely not e, because e is not the lightest element of any circuit. Thus, we added e to B ′ , and then deleted an element lighter than e. This means that we have increased the total weight of B ′ . Therefore, B ′ is not a maximum weighted base. Since some maximum weighted base must exist, it can only be B.
An immediate corollary of Lemma 1 is that the maximum weighted base of a matroid, after removing the minimum weight element of a circuit in the matroid, remains unchanged. We are now ready to prove Theorem 1.
Proof. Fix a weight function w on [n]. Let P ⊆ R 2n−1 be the affine space of all the points v such that v i = w i . One can easily observe that P is convex. Let S := P ∩Γ. Since Γ n is a convex cone and P is convex, S is a convex polyhedron. Also, it is trivial that the submodulartiy implies that for any point v ∈ Γ n , v is contained in the hypercube whose A-th coordinate is between 0 and Therefore, S is indeed a polytope. Therefore, in order to prove that a point is a vertex of S, it is enough to show that it is an extreme point.
Suppose there is a matroid M such that φ M,w is not a vertex of the polytope S or equivalently, there are two functions f w , q w in S such that for every subset X ⊆ [n]: With induction on size of X we prove that Since f w and g w are in P , for each i ∈ [n] we have Now, assuming the claim for every subset X of size of at most k, if X ⊆ [n] and |X| ≤ k we have: Let Y be of size k + 1, and j be the smallest weight in Y . We know that: Consider the following cases: 1) r(Y \j) < r(Y ). In this case, On the other hand, from the submodularity conditions we have: Since φ is a convex combination of f w and g w , therefore f w (Y ) and g w (Y ) must be equal to φ w (Y ). 2) r(Y \j) = r(Y ). Since j has the smallest weight in Y and j belongs to some circuit in Y , by Lemma 1 we have φ M,w (Y ) = φ M,w (Y \j).
Also, from monotonicity of f w and g w we have: and similarly g w (Y ) ≥ φ w (Y ). Thus, both f w (Y ) and g w (Y ) must be equal to φ w (Y ) and this proves the claim.
Let M = (M, I) be a binary matroid with representative matrix where |M | = n and v i is a m × 1 vector. Define w max = max{w e | e ∈ M }. We define the matrix X of variables as: Y e is the variable corresponding to the element e of weight w e . It is the join of the variables of the first w e variables in the matrix X × v e such that each X k i is an independent Ber( 1 2 ). If we define X i to be the i-th row of the matrix X, then: Proof. Define Y t i to be: Since for every j we have that w ij ≥ w i k : Therefore, if we remove v i k from the matroid, its entropy remains the same.
To prove Theorem 2, we need one more technical lemma about the statistical independence of linearly independent combinations of statistically independent Bernoulli random variables with parameter 1 2 . The following proposition, proved in [4], (Page 2, Theorem 1) is particularly useful. Proof. First of all, notice that the summation of two independent Bernoulli random variables with parameter 1 2 is again a Ber( 1 2 ) random variables. Thus, to complete the proof, all we need to justify is that the random variables assigned to the elements are independent.
1, (X v1 1 + X v2 1 ) Figure 1. The construction of variables for graphic matroids case; each edge is shown by its weight and the variable corresponding to it.
In fact, assuming the independency condition, the entropy function of the random variables becomes the summation of the entropies of the individual ones. From this, the entropy of each element is equal to the summation of the entropies of the same number of Bernoulli random variables with parameter 1 2 as its weight. Also, the entropy of the random variables assigned to the elements in I can be expanded as the summation of the entropies of the variables in each element, again under the independence condition.
Therefore, we just have to prove that the set of all the random variables assigned to the elements of an independent set I are statistically independent. This is also a direct implication of proposition 3.
Proof (Theorem 2 graphic matroids). Let G = (V, E) be a graphic matroid. We define variable Y e corresponding to edge e = (v, u) ∈ E of weight w e to be Y e = (X v 1 + X u 1 , X v 2 + X u 2 , ..., X v we + X u we ) That each X k i is an independent Ber( 1 2 ). All forests in a graphic matroid are independent sets. Therefore, a base in a graphic matroid is a spanning forest. Given a subset G ′ = (V, E ′ ⊆ E), by Lemma 2 and Lemma 1 the entropy of the variables defined on E ′ is equal to the entropy of the variables defined on the edges of the maximum weighted forest F . By Lemma 3 we have that: For each i, X k i is independent from others. So X v i + X u i is also independent from others. By definition of entropies for each e = (u, v) ∈ E we have that: The special case above is intended to give intuition about the proof for the general case. Below, we prove the theorem in the general setting.
Proof (Theorem 2 general case). Given a subset I ⊆ M , by Lemma 2 and Lemma 1 the entropy of the variables defined on the elements of I is equal to the entropy of the variables defined on the elements of the maximum weighted independent set B ⊆ I. Since X 1 , X 2 , ..., X w are independent, multiplying them by a non zero vector v e does not change the independence. Therefore, X 1 v e , X 2 v e , ..., X we v e are independent. X j v e for each j is the summation of some independent Ber( 1 2 )s. Therefore, H(X j v e ) = 1.
Therefore, if we the values of X 1 , ..., X m−1 are known, the value of X m is uniquely determined. Thus, if X i = α i for arbitrary values of α i ∈ χ i for 1 ≤ i ≤ m − 1, then: Since C is a circuit, each set S = {X i |i ∈ L ⊆ [m] and |L| ≤ m − 1} is independent. Therefore, And because H(X m |X 1 , X 2 , ..., X m−1 ) = 0 there exists α m ∈ X m such that Also, for each i: Thus, we also have: Since we chose α i and α j arbitrarily, we proved that: Therefore, ∀i : X i is uniform and Then H(X i ) = log |X i | for all i. Therefore, w = log |X 1 |.
Proof (Theorem 4). Let G = (V, E) be a graph of weight function w on E. Take a random orientation on the edges that gives an incidence matrix A. For each directed edge e = (u, v), define the variable corresponding to e to be Y e = X v − X u where for ∀i ∈ V each X i is a uniform random variable on =⇒ Xv e = X −1 α e l j=1,j =e Therefore, after removing an element from each cycle of the graph, the entropy of the variables defined above remains the same. So the entropy of the graph is the entropy of its spanning tree T . Now take an arbitrary root u of T and its neighbour vertex by the edge e * is v.
Since u is a root of T , it does not appear on the variables of other edges of T . So : As we know, if X u is a uniform random variable on [k], then X u − α is also a uniform random variable on [k]. So, we have

DISCUSSION
When the weight function is constantly equal to w on the singletons, the weighted rank function is identical to the usual rank function multiplied by the constant w. This function is shown to be entropic when the underlying matroid is representable over a finite field F q and w = log(q). Similarly, if we evaluate the entropy with the logarithm function in base q, then Theorem 2 holds for any representable matroid over the field F q . The proof is identical to the binary case. For the sake of simplicity, we only consider the binary case in the statement of the theorem.
Another important point is that when we deal with integral weight functions on mathematical objects, it is often the case that one can replace the integral weights by modifying the objects and making all the weights equal to one. A typical example is the case of integral weighs on the edges of a graph. If we replace each edge with a path of length equal to the weight of the edge, then many properties in the graph remains unchanged. For example, this procedure does not change the shortest path between any pair of the original vertices. For our problem, one may naturally expect that when the weight of an element is multiplied by an integer, the same argument as [1] on a new matroid whose corresponding element is replaced by a sequence of parallel elements will show that still the weighted rank function is entropic. However, in Figure 2, we present an example that shows that this idea does not work. The idea of replacing an element of the matroid with a series of elements does not work either as shown in Figure 2. This shows that our result indeed uses different ideas as the one in the paper [1].