pith. sign in

arxiv: 2602.16536 · v2 · pith:AY2R4DLLnew · submitted 2026-02-18 · 💻 cs.IT · math.IT

Spectral Conditions for the Ingleton Inequality

Rostislav Matveev , Andrei Romashchenko This is my paper

Pith reviewed 2026-05-21 12:48 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords Ingleton inequalityexpander graphsinformation inequalitiesspectral graph theorymutual informationlinear inequalitiesbiregular graphs
0
0 comments X

The pith

Pairs of random variables uniform on expander graph edges satisfy the Ingleton inequality up to a spectral error term.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that when X and Y are chosen uniformly at random from the edges of a biregular bipartite expander graph, the Ingleton quantity stays bounded away from large negative values for any choice of auxiliary random variables A and B. The lower bound is expressed directly in terms of the second-largest eigenvalue of the graph, which controls how much the distribution deviates from independence. This holds even though the mutual information between X and Y cannot be extracted in the usual way. The argument proceeds by applying the expander mixing lemma to sets defined by the values of A and B.

Core claim

For pairs (X,Y) uniformly distributed on the support of a biregular bipartite expander graph, and for all auxiliary A,B, the Ingleton quantity I(X;Y | A) + I(X;Y | B) + I(A;B) - I(X;Y) is at least a positive quantity depending on the second-largest eigenvalue of the graph.

What carries the argument

The expander mixing lemma applied after partitioning the vertex sets according to the values of the auxiliary variables A and B.

If this is right

  • The Ingleton inequality cannot be violated by more than a term controlled by the expansion quality.
  • Strongly non-extractable mutual information between X and Y still respects the inequality up to a small additive error.
  • Spectral expansion supplies a concrete sufficient condition for approximate validity of this linear information inequality.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar spectral conditions might stabilize other non-Shannon inequalities for the same class of distributions.
  • Explicit constructions of good expanders could be used to generate families of distributions that nearly satisfy the Ingleton inequality.
  • The partitioning technique may extend to bounding other linear combinations of mutual informations on graphs with controlled expansion.

Load-bearing premise

The joint distribution of X and Y is exactly uniform over the edges of a biregular bipartite graph whose second eigenvalue is sufficiently small.

What would settle it

A concrete biregular bipartite expander together with auxiliary variables A and B for which the Ingleton quantity falls below the explicit lower bound given by the second-largest eigenvalue.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that when (X,Y) is uniformly distributed over the edges of a biregular bipartite expander graph, the Ingleton quantity I(X;Y|A) + I(X;Y|B) + I(A;B) − I(X;Y) admits a positive lower bound depending only on the second-largest eigenvalue λ of the graph, for every choice of auxiliary random variables A,B jointly distributed with (X,Y). The proof invokes the expander mixing lemma on sets induced by the level sets of A and B, followed by a partitioning argument to control the four terms.

Significance. If the claimed spectral lower bound holds, the result shows that strong non-extractability of I(X;Y) does not produce large Ingleton violations inside this concrete family of distributions. It supplies an explicit, graph-theoretic sufficient condition under which a classical linear information inequality is approximately satisfied, which may be useful for constructing or ruling out entropic vectors that violate Ingleton.

major comments (2)
  1. Proof section (partitioning argument after application of the expander mixing lemma): the deviation term produced by the mixing lemma is O(λ √(|S||T|)). When the level sets of A or B have mass o(1/λ²), this additive error can become comparable to or larger than the main positive spectral contribution. The manuscript must exhibit explicitly how the partitioning aggregates these small sets while preserving a uniform positive lower bound that does not depend on the fineness of A and B; without that control the claimed inequality may fail to be strictly positive.
  2. Statement of the main theorem: the lower bound is asserted for all auxiliary A,B without further restrictions on their alphabets or on the joint support. It is not clear whether the partitioning technique continues to work when A or B are allowed to be functions of (X,Y) that isolate individual edges; a concrete counter-example construction or an additional hypothesis on the minimal mass of level sets would be needed to close this gap.
minor comments (2)
  1. The abstract contains a repeated word (“even even”).
  2. Notation for the second-largest eigenvalue should be introduced once and used consistently; currently λ appears without a prior definition in the main text.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and indicate the revisions we will make to strengthen the manuscript.

read point-by-point responses

  1. Referee: Proof section (partitioning argument after application of the expander mixing lemma): the deviation term produced by the mixing lemma is O(λ √(|S||T|)). When the level sets of A or B have mass o(1/λ²), this additive error can become comparable to or larger than the main positive spectral contribution. The manuscript must exhibit explicitly how the partitioning aggregates these small sets while preserving a uniform positive lower bound that does not depend on the fineness of A and B; without that control the claimed inequality may fail to be strictly positive.

    Authors: We agree that an explicit accounting is needed to confirm the deviation term remains controlled. The partitioning procedure groups level sets of small individual mass into collections whose aggregate probability mass is at least on the order of λ, ensuring the main spectral term (which is linear in the product of the aggregate masses) dominates the O(λ √(|S||T|)) error uniformly. We will revise the proof section to include a detailed description of the partitioning rule, the bound on the number of such groups, and the resulting lower bound that depends only on λ and the biregularity parameters. revision: yes

  2. Referee: Statement of the main theorem: the lower bound is asserted for all auxiliary A,B without further restrictions on their alphabets or on the joint support. It is not clear whether the partitioning technique continues to work when A or B are allowed to be functions of (X,Y) that isolate individual edges; a concrete counter-example construction or an additional hypothesis on the minimal mass of level sets would be needed to close this gap.

    Authors: The theorem is stated for arbitrary A and B, and the proof applies the mixing lemma to arbitrary level sets before partitioning. Singleton or near-singleton level sets (as may arise when A or B isolates edges) are aggregated across multiple partitions so that each aggregated set satisfies the mass threshold required for the spectral contribution to dominate. We do not believe an additional minimal-mass hypothesis is required, nor do we see a counter-example within the expander setting, because the mixing lemma holds for any pair of sets regardless of granularity. To address the concern we will add a clarifying paragraph and a short illustrative calculation for fine partitions in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation relies on external expander mixing lemma plus partitioning

full rationale

The paper derives a lower bound on the Ingleton quantity for uniform distributions on biregular bipartite expanders by applying the standard expander mixing lemma (an external combinatorial fact) to sets induced by arbitrary auxiliaries A and B, followed by a partitioning argument to aggregate small sets. No quantity in the final bound is obtained by fitting a parameter to the target Ingleton expression itself, no self-citation supplies a load-bearing uniqueness or ansatz, and the spectral gap enters as an independent hypothesis rather than being redefined from the conclusion. The derivation is therefore self-contained against external benchmarks and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the expander mixing lemma (standard) and the assumption that the support graph is biregular and expander; no free parameters or new entities are introduced.

axioms (1)
  • standard math The expander mixing lemma holds for the biregular bipartite graph associated with the support of (X,Y).
    Invoked to bound the deviation from uniform mixing when conditioning on A or B.

pith-pipeline@v0.9.0 · 5739 in / 1095 out tokens · 62850 ms · 2026-05-21T12:48:17.816230+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · 2 internal anchors

  1. [1]

    Representation of matroids,

    A. W. Ingleton, “Representation of matroids,”Combinatorial mathematics and its applications, vol. 23, pp. 149–167, 1971

    work page 1971

  2. [2]

    Conditional independences among four random variables ii,

    F. Mat´ uˇ s, “Conditional independences among four random variables ii,” Combinatorics, Probability and Computing, vol. 4, no. 4, pp. 407–417, 1995

    work page 1995

  3. [3]

    The dealer’s random bits in perfect secret sharing schemes,

    L. Csirmaz, “The dealer’s random bits in perfect secret sharing schemes,” Studia Scientiarum Mathematicarum Hungarica, vol. 32, no. 3, pp. 429– 438, 1996

    work page 1996

  4. [4]

    On characterization of entropy function via in- formation inequalities,

    Z. Zhang and R. W. Yeung, “On characterization of entropy function via in- formation inequalities,”IEEE Transactions on Information Theory, vol. 44, no. 4, pp. 1440–1452, 1998

    work page 1998

  5. [5]

    Conditional independences among four random variables iii: Final conclusion,

    F. Mat´ uˇ s, “Conditional independences among four random variables iii: Final conclusion,”Combinatorics, Probability and Computing, vol. 8, no. 3, pp. 269–276, 1999

    work page 1999

  6. [6]

    Inequali- ties for shannon entropy and kolmogorov complexity,

    D. Hammer, A. Romashchenko, A. Shen, and N. Vereshchagin, “Inequali- ties for shannon entropy and kolmogorov complexity,”Journal of Computer and System Sciences, vol. 60, no. 2, pp. 442–464, 2000. 25

    work page 2000

  7. [7]

    Non-Shannon Information Inequalities in Four Random Variables

    R. Dougherty, C. Freiling, and K. Zeger, “Non-shannon information in- equalities in four random variables,”arXiv preprint arXiv:1104.3602, 2011

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  8. [8]

    Entropy region and convolution,

    F. Mat´ uˇ s and L. Csirmaz, “Entropy region and convolution,”IEEE Trans- actions on Information Theory, vol. 62, no. 11, pp. 6007–6018, 2016

    work page 2016

  9. [9]

    Violations of the ingleton inequality and re- vising the four-atom conjecture,

    N. Boston and T.-T. Nan, “Violations of the ingleton inequality and re- vising the four-atom conjecture,”Kybernetika, vol. 56, no. 5, pp. 916–933, 2020

    work page 2020

  10. [10]

    Insufficiency of linear network codes,

    R. Dougherty, C. Freiling, and K. Zeger, “Insufficiency of linear network codes,”IEEE Transactions on Information Theory, vol. 51, no. 8, pp. 2745– 2759, 2005

    work page 2005

  11. [11]

    Networks, matroids, and non- shannon information inequalities,

    R. Dougherty, C. Freiling, and K. Zeger, “Networks, matroids, and non- shannon information inequalities,”IEEE Transactions on Information Theory, vol. 53, no. 6, pp. 1949–1969, 2007

    work page 1949

  12. [12]

    Linear network coding,

    S.-Y. Li, R. W. Yeung, and N. Cai, “Linear network coding,”IEEE trans- actions on information theory, vol. 49, no. 2, pp. 371–381, 2003

    work page 2003

  13. [13]

    Finding lower bounds on the com- plexity of secret sharing schemes by linear programming,

    C. Padr´ o, L. V´ azquez, and A. Yang, “Finding lower bounds on the com- plexity of secret sharing schemes by linear programming,”Discrete applied mathematics, vol. 161, no. 7-8, pp. 1072–1084, 2013

    work page 2013

  14. [14]

    Matroids can be far from ideal secret sharing,

    A. Beimel, N. Livne, and C. Padr´ o, “Matroids can be far from ideal secret sharing,” inTheory of Cryptography Conference, pp. 194–212, Springer, 2008

    work page 2008

  15. [15]

    An impossibility result on graph secret sharing,

    L. Csirmaz, “An impossibility result on graph secret sharing,”Designs, Codes and Cryptography, vol. 53, no. 3, pp. 195–209, 2009

    work page 2009

  16. [16]

    Common information is far less than mutual infor- mation.,

    P. G´ acs and J. K¨ orner, “Common information is far less than mutual infor- mation.,”Problems of Control and Information Theory, vol. 2, pp. 149–162, 1973

    work page 1973

  17. [17]

    In- teraction between skew-representability, tensor products, extension proper- ties, and rank inequalities,

    K. B´ erczi, B. Geh´ er, A. Imolay, L. Lov´ asz, C. Padr´ o, and T. Schwarcz, “In- teraction between skew-representability, tensor products, extension proper- ties, and rank inequalities,” inProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 328–354, SIAM, 2026

    work page 2026

  18. [18]

    Linear rank inequalities on five or more variables

    R. Dougherty, C. Freiling, and K. Zeger, “Linear rank inequalities on five or more variables,”arXiv preprint arXiv:0910.0284, 2009

    work page internal anchor Pith review Pith/arXiv arXiv 2009

  19. [19]

    A new class of non-shannon-type inequalities for entropies,

    K. Makarychev, Y. Makarychev, A. Romashchenko, and N. Vereshchagin, “A new class of non-shannon-type inequalities for entropies,”Communica- tions in Information and Systems, vol. 2, no. 2, pp. 147–166, 2002. 26

    work page 2002

  20. [20]

    Common in- formation in well-mixing graphs and applications to information-theoretic cryptography,

    G. Caillat-Grenier, A. Romashchenko, and R. Zyavgarov, “Common in- formation in well-mixing graphs and applications to information-theoretic cryptography,” in2024 IEEE Information Theory Workshop (ITW), pp. 181–186, IEEE, 2024

    work page 2024

  21. [21]

    Mixing properties and the chro- matic number of ramanujan complexes,

    S. Evra, K. Golubev, and A. Lubotzky, “Mixing properties and the chro- matic number of ramanujan complexes,”International Mathematics Re- search Notices, vol. 2015, no. 22, pp. 11520–11548, 2015

    work page 2015

  22. [22]

    Parti- tioning multi-dimensional sets in a small number of “uniform

    N. Alon, I. Newman, A. Shen, G. Tardos, and N. Vereshchagin, “Parti- tioning multi-dimensional sets in a small number of “uniform” parts,” European Journal of Combinatorics, vol. 28, no. 1, pp. 134–144, 2007

    work page 2007

  23. [23]

    T. M. Cover,Elements of information theory. John Wiley & Sons, 1999

    work page 1999

  24. [24]

    Explicit construction of linear sized tolerant networks,

    N. Alon and F. R. Chung, “Explicit construction of linear sized tolerant networks,”Discrete Mathematics, vol. 72, no. 1-3, pp. 15–19, 1988

    work page 1988

  25. [25]

    Expander graphs and their ap- plications,

    S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their ap- plications,”Bulletin of the American Mathematical Society, vol. 43, no. 4, pp. 439–561, 2006

    work page 2006

  26. [26]

    Eigenvalues and expanders,

    N. Alon, “Eigenvalues and expanders,”Combinatorica, vol. 6, no. 2, pp. 83– 96, 1986

    work page 1986

  27. [27]

    On the second eigenvalue of a graph,

    A. Nilli, “On the second eigenvalue of a graph,”Discrete Mathematics, vol. 91, no. 2, pp. 207–210, 1991

    work page 1991

  28. [28]

    Eigenvalues and expansion of bipartite graphs,

    T. Høholdt and H. Janwa, “Eigenvalues and expansion of bipartite graphs,” Designs, Codes and Cryptography, vol. 65, no. 3, pp. 259–273, 2012

    work page 2012

  29. [29]

    On the line graph of a projective plane,

    A. Hoffman, “On the line graph of a projective plane,”Proceedings of the American Mathematical Society, vol. 16, no. 2, pp. 297–302, 1965. 27

    work page 1965