Kybernetika 56 no. 5, 916-933, 2020

Violations of the Ingleton inequality and revising the four-atom conjecture

Nigel Boston and Ting-Ting NanDOI: 10.14736/kyb-2020-5-0916

Abstract:

The entropy region is a fundamental object of study in mathematics, statistics, and information theory. On the one hand, it involves pure group theory, governing inequalities satisfied by subgroup indices, whereas on the other hand, computing network coding capacities amounts to a convex optimization over this region. In the case of four random variables, the points in the region that satisfy the Ingleton inequality (corresponding to abelian groups and to linear network codes) form a well-understood polyhedron, and so attention has turned to Ingleton-violating points in the region. How far these points extend is measured by their Ingleton score, where points with positive score are Ingleton-violating. The Four-Atom Conjecture stated that the Ingleton score cannot exceed $0.089373$, but this was disproved by Matúš and Csirmaz. In this paper we employ two methods to investigate Ingleton-violating points and thereby produce the currently largest known Ingleton scores. First, we obtain many Ingleton-violating examples from non-abelian groups. Factorizability appears in many of those and is used to propose a systematic way to produce more. Second, we rephrase the problem of maximizing Ingleton score as an optimization question and introduce a new Ingleton score function, which is a limit of Ingleton scores with maximum unchanged. We use group theory to exploit symmetry in these new Ingleton score functions and the relations between them. Our approach yields some large Ingleton scores and, using this methodology, we find that there are entropic points with score $0.0925000777$, currently the largest known score.

Keywords:

information inequalities, entropy vectors, subgroup indices

Classification:

94A15, 20B35

References:

  1. R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung: Network information flow. IEEE Trans. Inform. Theory 46 (2007), 1204-1216.   DOI:10.1109/18.850663
  2. S. Alam, S. Thakor and S. Abbas: On Enumerating Distributions for Associated Vectors in the Entropy Space. arXiv:1807.08573, 2018.   CrossRef
  3. W. Bosma, J. Cannon and C. Playoust: The Magma algebra system. The user language, J. Symbolic Comput. 24 (1997), 235-265.   DOI:10.1006/jsco.1996.0125
  4. N. Boston and T.-T. Nan: Large violations of the Ingleton inequality. In: 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012.   DOI:10.1109/allerton.2012.6483410
  5. N. Boston and T.-T. Nan: A refinement of the four-atom conjecture. In: International Symposium on Network Coding (NetCod), 2013.   DOI:10.1109/netcod.2013.6570833
  6. T. Chen: Group characterizable entropiy functions. In: Proc. of the 2005 IEEE International Symposium on Information Theory, Nice 2007, pp. 507-510.   DOI:10.1109/isit.2007.4557275
  7. T. H. Chen and R. W. Yeung: On a relation between information inequalities and group theory. IEEE Trans. Inform. Theory 48 (2002), 1992-1995.   DOI:10.1109/tit.2002.1013138
  8. P. A. Chou, Y. Wu and K. Jain: Practical network coding. In: Proc. 2003 Allerton Conf. on Commun., Control, and Computing, 2003, pp. 40-49.   CrossRef
  9. R. Dougherty, C. Freiling and K. Zeger: Insufficiency of linear coding in network information flow. IEEE Trans. Inform. Theory 51 (2005), 2745-2759.   DOI:10.1109/tit.2005.851744
  10. R. Dougherty, C. Freiling and K. Zeger: Networks, matroids, and non-Shannon information inequalities. IEEE Trans. Inform. Theory 53 (2007), 1949-1969.   DOI:10.1109/tit.2007.896862
  11. R. Dougherty, C. Freiling and K. Zeger: Non-Shannon information inequalities in four random variables. arXiv:1104.3602v1, 2011.   CrossRef
  12. T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi and B. Leong: A random linear network coding approach to multicast. IEEE Trans. Inform. Theory 52 (2006), 4413-4430.   DOI:10.1109/tit.2006.881746
  13. A. Ingleton: Representation of matroids. In: Combinatorial Mathematics and its Applications, 1971, pp. 149-167.   CrossRef
  14. I. M.Isaacs: Finite Group Theory. American Mathematical Society, 2008.   DOI:10.1090/gsm/092
  15. R. Koetter and M. Médard: An algebraic approach to network coding. IEEE/ACM Trans. Network. 2 (2003), 782-795.   DOI:10.1109/tnet.2003.818197
  16. R. Li, R. Yeung and N. Cai: Linear network coding. IEEE Trans. Inform. Theory 49 (2003), 371-381.   DOI:10.1109/tit.2002.807285
  17. K. Makarycheve, L. Makarycheve, A. E. Romashchenko and N. K. Vereshchagin: A new class of non-Shannon type inequalities for entropies. Com. Inform. Syst. 2 (2002), 147-166.   DOI:10.4310/cis.2002.v2.n2.a3
  18. W. Mao, M. Thill and B. Hassibi: On Ingleton-violating finite groups. IEEE Trans. Inform. Theory 63 (2017), 183-200.   DOI:10.1109/tit.2016.2627530
  19. F. Matúš: Conditional independences among four random variables II. Combin. Probab. Comput. 4 (1995), 407-417.   DOI:10.1017/s0963548300001747
  20. F. Matúš: Conditional independences among four random variables III: Final conclusion. Combin. Probab. Comput. 8 (1999), 269-276.   DOI:10.1017/s0963548399003740
  21. F. Matúš: Infinitely many information inequalities. In: IEEE International Symposium on Information Theory, IEEE 2007, pp. 41-44.   DOI:10.1109/isit.2007.4557201
  22. F. Matúš and L. Csirmaz: Entropy region and convolution. IEEE Trans. Inform. Theory 62 (2016), 6007-6018.   DOI:10.1109/tit.2016.2601598
  23. F. Matúš and M. Studený: Conditional independences among four random variables I. Combin. Probab. Comput. 4 (1995), 269-278.   DOI:10.1017/s0963548300001644
  24. V. T. Muralidharan and B. S. Rajan: On the vector linear solvability of networks and discrete polymatroids. GLOBECOM 2013, pp. 1979-1984.   CrossRef
  25. T.-T. Nan: Entropy Regions and the Four-Atom Conjecture. PhD. Dissertation, Department of Mathematics, University of Wisconsin-Madison, 2015.   CrossRef
  26. P. Paajanen: Finite p-groups, entropy vectors and the ingleton inequality for nilpotent groups. IEEE Trans. Inform. Theory 60 (2014), 3821-3824.   CrossRef
  27. R. Stancu and F. Oggier: Finite nilpotent and metacyclic groups never violate the Ingleton inequality. 2012 International Symposium on Network Coding (NetCod), 2012, pp. 25-30.   DOI:10.1109/netcod.2012.6261879
  28. W. Waterhouse: Do symmetric problems have symmetric solutions? Amer. Math. Monthly 90 (1983), 378-387.   DOI:10.1080/00029890.1983.11971235
  29. R. W. Yeung: Information Theory and Network Coding. Springer, 2008.   CrossRef
  30. Z. Zhang and R. W. Yeung: A non-Shannon type conditional inequality of information quantities. IEEE Trans. Inform. Theory 43 (1997), 1982-1986.   DOI:10.1109/18.641561
  31. Z. Zhang and R. W. Yeung: On characterization of entropy function via information inequalities. IEEE Trans. Inform. Theory 44 (1998), 1440-1452.   DOI:10.1109/18.681320