The Ingleton inequality is a classical linear information inequality that holds for representable matroids but fails to be universally valid for entropic vectors. Understanding the extent to which this inequality can be violated has been a longstanding problem in information theory. In this paper, we show that for a broad class of jointly distributed random variables (X,Y) the Ingleton inequality holds up to a small additive error, even even though the mutual information between X and Y is far from being extractable. Contrary to common intuition, strongly non-extractable mutual information does not lead to large violations of the Ingleton inequality in this setting. More precisely, we consider pairs (X,Y) that are uniformly distributed on their joint support and whose associated biregular bipartite graph is an expander. For all auxiliary random variables A and B jointly distributed with (X,Y), we establish a lower bound on the Ingleton quantity I(X:Y|A)+I(X:Y|B)+I(A:B) - I(X:Y) in terms of the spectral parameters of the underlying graph. Our proof combines the expander mixing lemma with a partitioning technique for finite sets.
The Ingleton inequality is a classical linear information inequality that holds for representable matroids but fails to be universally valid for entropic vectors. Understanding the extent to which this inequality can be violated has been a longstanding problem in information theory. In this paper, we show that for a broad class of jointly distributed random variables (X,Y) the Ingleton inequality holds up to a small additive error, even even though the mutual information between X and Y is far from being extractable. Contrary to common intuition, strongly non-extractable mutual information does not lead to large violations of the Ingleton inequality in this setting. More precisely, we consider pairs (X,Y) that are uniformly distributed on their joint support and whose associated biregular bipartite graph is an expander. For all auxiliary random variables A and B jointly distributed with (X,Y), we establish a lower bound on the Ingleton quantity I(X:Y|A)+I(X:Y|B)+I(A:B) - I(X:Y) in terms of the spectral parameters of the underlying graph. Our proof combines the expander mixing lemma with a partitioning technique for finite sets.
The Ingleton inequality is a classical linear information inequality that holds for representable matroids but fails to be universally valid for entropic vectors. Understanding the extent to which this inequality can be violated has been a longstanding problem in information theory. In this paper, we show that for a broad class of jointly distributed random variables (X,Y) the Ingleton inequality holds up to a small additive error, even even though the mutual information between X and Y is far from being extractable. Contrary to common intuition, strongly non-extractable mutual information does not lead to large violations of the Ingleton inequality in this setting. More precisely, we consider pairs (X,Y) that are uniformly distributed on their joint support and whose associated biregular bipartite graph is an expander. For all auxiliary random variables A and B jointly distributed with (X,Y), we establish a lower bound on the Ingleton quantity I(X;Y∣A)+I(X;Y∣B)+I(A;B)−I(X;Y) in terms of the spectral parameters of the underlying graph. Our proof combines the expander mixing lemma with a partitioning technique for finite sets.
For four finite discrete random variables, we prove that the negative of the Ingleton expression, divided by the joint entropy, is at most 19/124≈0.15323, improving the previously reported upper bound 3/19 by 11/2356. The proof uses a copy program with four copy steps and six auxiliary variables, certified by exact rational linear-programming certificates. We also show that two published information inequalities, due to Dougherty-Freiling-Zeger and Csirmaz, imply the bound 5/32 by an explicit nonnegative combination with Shannon inequalities, and that 5/32 is the exact optimum both of the union of the three published inequality catalogues considered here and of the full copy-lemma extensions of all 213 distinct copy programs occurring in them. The new program is not among these programs, and the bound 19/124 remains optimal when all of them and all catalogue inequalities are added. Ancillary files provide the parsed catalogues, exact primal and dual certificates, exact extension certificates, and verifiers that use only the Python standard library.
Given n (discrete or continuous) random variables Xi, the (2n- 1)-dimensional vector obtained by evaluating the joint entropy of all non-empty subsets of {X1,hellip, Xn} is called an entropic vector. Determining the region of entropic vectors is an important open problem in information theory. Recently, Chan has shown that the entropy regions for discrete and continuous random variables, though different, can be determined from one another. An important class of continuous random variables are those that are vector-valued and jointly Gaussian. It is known that Gaussian random variables violate the Ingleton bound, which many random variables such as those obtained from linear codes over finite fields do satisfy, and they also achieve certain non-Shannon inequalities. In this paper we give a full characterization of the entropy region for three jointly-Gaussian vector-valued random variables and, rather surprisingly, show that the region is strictly smaller than the entropy region for three arbitrary random variables. However, we also show the following result. For any given entropic vector h isin R7, there exists a thetas* > 0, such that for all thetas ges thetas*, the vector 1/thetas h can be generated by three vector-valued jointly Gaussian random variables. This implies that for three random variables the region of entropic vectors can be obtained by considering the cone generated by the space of Gaussian entropic vectors. It also suggests that studying Gaussian random variables for n ges 4 may be a fruitful approach to studying the space of entropic vectors for arbitrary n.
We prove an improved lower bound of 0.097387436922 on the largest normalised Ingleton violation among four-variable almost-entropic vectors. Previously reported constructions reach approximately 0.0925, used as a rounded benchmark; the best published universal upper bound is 19/124. Conditional parity hashing combines local binary parity labels, one common linear hash, simultaneous conditional privacy amplification and joint conditioning. Applied to a 24-atom source of Matúš and Csirmaz, it subtracts a multiple of the uniform-matroid rank function U(3,4) from all fifteen entropy coordinates. The limiting signed score lies in [-0.097387436923, -0.097387436922], and finite-alphabet distributions with score below -0.09738 exist. This record contains the preprint PDF, manuscript sources, Lean proof sources, exact numerical checkers, build instructions and verification evidence. The main theorem, including the closed rate interval, score enclosure and finite-alphabet existence statement, was rebuilt and kernel-checked in Lean 4.35.0-rc2 with pinned Mathlib dependencies. The finite sampler and fixed-path optimality argument are written proofs rather than separate Lean declarations. Søren Riis is the creator and coordinator and directed the research. Astra/Codex and Claude contributed mathematical development, computation and verification; Claude contributed the Lean formalisation and adversarial review. The source construction is due to Matúš and Csirmaz; the paper gives full references to the earlier entropy-region and privacy-amplification work. AI checks do not constitute independent human peer review. Licences by component: the paper PDF, LaTeX sources and original figures are CC BY 4.0; Lean sources, Python checkers and build scripts are Apache-2.0. Third-party dependencies retain their own licences. Repository: https://github.com/SR123/conditional-parity-hashing
Extreme point representations are utilized together with facet membership to gain insights about the relationship between various bounds on the set of normalized entropic vectors in 4 random variables. Echoing prior results from Matúš (1995), we begin by showing that the 206 extreme points of the Shannon outer bound comprise 33 forms where 16 of these forms are entropic and achievable with binary random variables (one bit), 16 of the forms are entropic and achievable using two bits, and the remaining single form of six extreme points is not entropic, not achievable with two bits, and is the only violator of the Ingleton inequality. Thus, the Ingleton inner bound is matched to the Shannon outer bound in that it contains all entropic Shannon extreme points. Further novel investigation of the structure of the Ingleton and Shannon polytopes reveal that every facet of the Shannon outer bound requires two bits per variable and can be improved upon. The inner bound formed from the convex hull of the set of binary entropic vectors is shown to neither contain nor be contained in the Ingleton inner bound, and is shown to not be a polytope. The addition of the non-Shannon-type inequality due to Zhang and Yueng plus the six non-Shannon-type inequalities due to Dougherty, Freiling, and Zeger yield a polytopic outer bound where none of the non-Shannon extreme points obey Ingleton or are binary achievable. Worst case distance gaps between the various bounds are calculated.
The paper deals with linear information inequalities valid for entropy functions induced by discrete random variables. Specifically, the so-calledconditional Ingleton inequalitiesare in the center of interest: these are valid under conditional independence assumptions on the inducing random variables. We discuss five inequalities of this particular type, four of which has appeared earlier in the literature. Besides the proof of the new fifth inequality, simpler proofs of (some of) former inequalities are presented. These five information inequalities are used to characterize all conditional independence structures induced by four discrete random variables.