This directory contains the following files associated with the paper
"Linear rank inequalities on five or more variables" by
Dougherty, Freiling, and Zeger.  (Note: the ineqs, coefs, and rays files
all contain just one representative from each equivalence class obtained
by permuting the 5 or 6 basic variables.  Use the programs perm5.c and perm6.c
to expand the coefs and rays files to full lists.  Also, the coefs files
may not contain the same representatives as the corresponding ineqs files,
but for the most recent files ineqs66 and coefs66 the representatives do match.
Commas in variable combinations are omitted in the ineqs files.)
Some of the larger files are also available in gzip-compressed form
(suffix .gz).

Also, until we set up a separate location for it, this directory
contains a file nonshan4 with a list of non-Shannon information
inequalities on four variables, to be described in a forthcoming
paper (a draft of which is now at arXiv 1104.3602).  The methods used
were described in an earlier conference paper "Six new non-Shannon
information inequalities"; the inequalities here were proved the same
way, but using three or four copy variables instead of one or two.


---------- Five-variable inequalities ----------

ineqs50:
   The elemental Shannon inequalities on five variables.
coefs50:
   The elemental Shannon inequalities in coefficient form (each line is a
   list of 32 integers giving the coefficients of the inequality in the
   order described under the utility program perm5.c; the first number on
   each line is always 0).
ineqs54:
   The non-redundant five-variable instances of the Ingleton inequality; i.e.,
   those which give faces of the linear rank region on five variables.
coefs54:
   The five-variable instances of the Ingleton inequality in coefficient form.
ineqs55:
   The twenty-four new five-variable linear rank inequalities.
coefs55:
   The twenty-four new inequalities in coefficient form.


---------- Five-variable extreme rays ----------

rays5:
   The 32-dimensional vectors which generate the extreme rays
   for the 5-variable linear rank region (each line is a
   list of 32 integers giving the coordinates of the vector in the
   order described under the utility program perm5.c; the first number on
   each line is always 0).
checkrays5.m:
   MATLAB program which contains the generators for the 5-variable
   linear rank extreme rays and a linear representation for each of them
   (which is supposed to work for all fields; in a few cases
   the representation is for a small constant multiple of the given vector),
   and verifies that the representations are correct.


---------- Six-variable inequalities ----------

ineqs60:
   The elemental Shannon inequalities on five variables.
coefs60:
   The elemental Shannon inequalities in coefficient form (each line is a
   list of 64 integers giving the coefficients of the inequality in the
   order described under the utility program perm6.c).
ineqs64:
   The non-redundant six-variable instances of the Ingleton inequality; i.e.,
   those which give faces of the linear rank region on six variables.  (Note:
   in files ineqs46, ineqs56, and ineqs66, each inequality marked with an
   asterisk is a substitution instance of the most recent unmarked inequality.
   However, the checking is not complete; there are some unmarked
   inequalities in ineqs66 which are substitution instances of other
   inequalities.)
coefs64:
   The six-variable instances of the Ingleton inequality in coefficient form.
ineqs65:
   The non-redundant six-variable instances of the new five-variable linear
   rank inequalities.
coefs65:
   The six-variable instances of the five-variable inequalities in coefficient
   form.
ineqs66:
   A partial list of new six-variable linear rank inequalities.  The first
   part of the file is the inequalities produced using one common information;
   these have all been verified to be instances of the construction theorems
   in the paper (with the inequalities provable from Theorem 3 listed before
   the inequalities provable from Theorem 6).  The next part of the file is
   the inequalities produced using two common informations; finally come the
   inequalities proved using three common informations.  See file ineqs66CI
   to tell which inequalities are which.
ineqs66CI:
   For each inequality in ineqs66, the corresponding line in ineqs66CI tells
   which pairs of (combinations of) variables one can assume a common
   information for in order to prove the inequality.  For instance, the line
      A BC     D BCE
   indicates that the inequality must be true if a common information for
   A and B,C and a common information for D and B,C,E both exist.  The
   variables Z and Y refer to the common informations from the first and
   second pairs, respectively; so the line
      A B     A C     D EY
   means assume a common information for A and B, a common information called Y
   for A and C, and a common information for D and E,Y.
coefs66:
   The partial list of new six-variable inequalities in coefficient form.
proofs66:
   For each inequality in ineqs66, the corresponding line in proofs66 is
   a list of integers encoding a proof of that inequality.  The first
   integer n is the number of common informations used.  The next 2n
   integers list the pairs of combinations of variables for which
   common informations are used; this is a numerical form of the corresponding
   line in ineqs66CI, where the variables A,B,C,D,E,F,Z,Y,X (here Z,Y,X are the
   names of the common informations assumed to exist) are represented by
   numbers 1,2,4,8,16,32,64,128,256, and a combination of variables is
   given by the sum of the numbers (so BC becomes 6).  The next 3n integers
   are coefficients p_i, q_i, r_i (i <= n) such that the inequality to
   be proved becomes Shannon if one adds to the right hand side:
          p_i H(v_i | c_i)
          q_i H(v_i | d_i)
          r_i ( I(c_i ; d_i) - H(v_i) )
   where the i'th assumption is that v_i is a common information of
   c_i and d_i.  The remaining integers come in triples (e_i,f_i,g_i)
   giving an expression of the above Shannon inequality as a sum
   of conditional mutual informations I(e_i ; f_i | g_i).
dualcoefs66:
   Coefficients for six-variable inequalities that are duals of inequalities
   in coefs66, and are therefore valid linear rank inequalities, but
   for which common information proofs and clean forms have
   not yet been produced.


---------- Six-variable extreme rays ----------

rays6:
   A partial list of 64-dimensional vectors which generate extreme rays
   for the 6-variable linear rank region.
filter6.c:
   C program which reads in a list of 64-dimensional integer vectors and
   prints out the ones which it cannot verify to be linearly representable
   polymatroids (and can be compiled so as to print out information on
   representations found and unsuccessful attempts).
filter6a.c:
   Improved version of filter6.c.  (For one thing, it doesn't delete the
   leading 0 from input lines.)
reps6:
   A file containing, for each vector in rays6, a line giving a coded
   linear representation of that vector.  These lines are _not_ in the
   same order as the lines in rays6; however, the output of the command
      reptoray < reps6 | lexfirst6 | sort
   should be identical to rays6.
reptoray.c:
   C program which reads in a list of coded linear representations for
   representable polymatroids and outputs the polymatroids.
dualrays6:
   Coefficients for 64-dimensional vectors that are duals of vectors
   in rays6, and are therefore linearly representable polymatroids, but
   for which coded linear representations have not yet been produced.


---------- Utility programs ----------

perm5.c:
   Filter program which reads in a list of dimension-32 integer vectors
   (where the 32 indices are considered to be subsets of a five-element set
   {A,B,C,D,E} in the order {},{A},{B},{A,B},{C},{A,C},{B,C},{A,B,C},{D},...)
   and writes out a longer list containing, for each input vector, all vectors
   obtained from it via permutations of the five-element set (but if the same
   vector is produced by more than one permutation, it is only printed once).
perm6.c:
   Filter program which reads in a list of dimension-64 integer vectors
   (where the 64 indices are considered to be subsets of a six-element set
   {A,B,C,D,E,F} in the order {},{A},{B},{A,B},{C},{A,C},{B,C},{A,B,C},{D},...)
   and writes out a longer list containing, for each input vector, all vectors
   obtained from it via permutations of the six-element set (but if the same
   vector is produced by more than one permutation, it is only printed once).
lexfirst6.c:
   Filter program which reads in a list of dimension-64 integer vectors
   (where the 64 indices are considered to be subsets of a six-element set
   {A,B,C,D,E,F} in the order {},{A},{B},{A,B},{C},{A,C},{B,C},{A,B,C},{D},...)
   and writes out a list containing, for each input vector, the permuted
   form of that vector (from among the possibilities that would be produced
   by perm6.c) which comes first in lexicographic order.