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

Nigel Boston; Ting-Ting Nan

Kybernetika (2020)

  • Volume: 56, Issue: 5, page 916-933
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Boston, Nigel, and Nan, Ting-Ting. "Violations of the Ingleton inequality and revising the four-atom conjecture." Kybernetika 56.5 (2020): 916-933. <http://eudml.org/doc/297406>.

@article{Boston2020,
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.},
author = {Boston, Nigel, Nan, Ting-Ting},
journal = {Kybernetika},
keywords = {entropy vectors; information inequalities; subgroup indices},
language = {eng},
number = {5},
pages = {916-933},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Violations of the Ingleton inequality and revising the four-atom conjecture},
url = {http://eudml.org/doc/297406},
volume = {56},
year = {2020},
}

TY - JOUR
AU - Boston, Nigel
AU - Nan, Ting-Ting
TI - Violations of the Ingleton inequality and revising the four-atom conjecture
JO - Kybernetika
PY - 2020
PB - Institute of Information Theory and Automation AS CR
VL - 56
IS - 5
SP - 916
EP - 933
AB - 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.
LA - eng
KW - entropy vectors; information inequalities; subgroup indices
UR - http://eudml.org/doc/297406
ER -

References

top
  1. Ahlswede, R., Cai, N., Li, S.-Y. R., Yeung, R. W., 10.1109/18.850663, IEEE Trans. Inform. Theory 46 (2007), 1204-1216. MR1768542DOI10.1109/18.850663
  2. Alam, S., Thakor, S., Abbas, S., On Enumerating Distributions for Associated Vectors in the Entropy Space., arXiv:1807.08573, 2018. 
  3. Bosma, W., Cannon, J., Playoust, C., 10.1006/jsco.1996.0125, The user language, J. Symbolic Comput. 24 (1997), 235-265. MR1484478DOI10.1006/jsco.1996.0125
  4. Boston, N., Nan, T.-T., 10.1109/allerton.2012.6483410, In: 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012. DOI10.1109/allerton.2012.6483410
  5. Boston, N., Nan, T.-T., 10.1109/netcod.2013.6570833, In: International Symposium on Network Coding (NetCod), 2013. DOI10.1109/netcod.2013.6570833
  6. Chen, T., 10.1109/isit.2007.4557275, In: Proc. of the 2005 IEEE International Symposium on Information Theory, Nice 2007, pp. 507-510. DOI10.1109/isit.2007.4557275
  7. Chen, T. H., Yeung, R. W., 10.1109/tit.2002.1013138, IEEE Trans. Inform. Theory 48 (2002), 1992-1995. MR1930005DOI10.1109/tit.2002.1013138
  8. Chou, P. A., Wu, Y., Jain, K., Practical network coding., In: Proc. 2003 Allerton Conf. on Commun., Control, and Computing, 2003, pp. 40-49. 
  9. Dougherty, R., Freiling, C., Zeger, K., 10.1109/tit.2005.851744, IEEE Trans. Inform. Theory 51 (2005), 2745-2759. MR2236245DOI10.1109/tit.2005.851744
  10. Dougherty, R., Freiling, C., Zeger, K., 10.1109/tit.2007.896862, IEEE Trans. Inform. Theory 53 (2007), 1949-1969. MR2321860DOI10.1109/tit.2007.896862
  11. Dougherty, R., Freiling, C., Zeger, K., Non-Shannon information inequalities in four random variables., arXiv:1104.3602v1, 2011. MR2321860
  12. Ho, T., Médard, M., Koetter, R., Karger, D. R., Effros, M., Shi, J., Leong, B., 10.1109/tit.2006.881746, IEEE Trans. Inform. Theory 52 (2006), 4413-4430. MR2300827DOI10.1109/tit.2006.881746
  13. Ingleton, A., Representation of matroids., In: Combinatorial Mathematics and its Applications, 1971, pp. 149-167. MR0278974
  14. M.Isaacs, I., 10.1090/gsm/092, American Mathematical Society, 2008. MR2426855DOI10.1090/gsm/092
  15. Koetter, R., Médard, M., 10.1109/tnet.2003.818197, IEEE/ACM Trans. Network. 2 (2003), 782-795. DOI10.1109/tnet.2003.818197
  16. Li, R., Yeung, R., Cai, N., 10.1109/tit.2002.807285, IEEE Trans. Inform. Theory 49 (2003), 371-381. MR1966785DOI10.1109/tit.2002.807285
  17. Makarycheve, K., Makarycheve, L., Romashchenko, A. E., Vereshchagin, N. K., 10.4310/cis.2002.v2.n2.a3, Com. Inform. Syst. 2 (2002), 147-166. MR1958013DOI10.4310/cis.2002.v2.n2.a3
  18. Mao, W., Thill, M., Hassibi, B., 10.1109/tit.2016.2627530, IEEE Trans. Inform. Theory 63 (2017), 183-200. MR3599943DOI10.1109/tit.2016.2627530
  19. Matúš, F., 10.1017/s0963548300001747, Combin. Probab. Comput. 4 (1995), 407-417. MR1377558DOI10.1017/s0963548300001747
  20. Matúš, F., 10.1017/s0963548399003740, Combin. Probab. Comput. 8 (1999), 269-276. MR1702569DOI10.1017/s0963548399003740
  21. Matúš, F., 10.1109/isit.2007.4557201, In: IEEE International Symposium on Information Theory, IEEE 2007, pp. 41-44. DOI10.1109/isit.2007.4557201
  22. Matúš, F., Csirmaz, L., 10.1109/tit.2016.2601598, IEEE Trans. Inform. Theory 62 (2016), 6007-6018. MR3565097DOI10.1109/tit.2016.2601598
  23. Matúš, F., Studený, M., 10.1017/s0963548300001644, Combin. Probab. Comput. 4 (1995), 269-278. MR1356579DOI10.1017/s0963548300001644
  24. Muralidharan, V. T., Rajan, B. S., On the vector linear solvability of networks and discrete polymatroids., GLOBECOM 2013, pp. 1979-1984. 
  25. Nan, T.-T., Entropy Regions and the Four-Atom Conjecture., PhD. Dissertation, Department of Mathematics, University of Wisconsin-Madison, 2015. MR3358242
  26. Paajanen, P., 10.1109/TIT.2014.2321561, IEEE Trans. Inform. Theory 60 (2014), 3821-3824. MR3225931DOI10.1109/TIT.2014.2321561
  27. Stancu, R., Oggier, F., 10.1109/netcod.2012.6261879, 2012 International Symposium on Network Coding (NetCod), 2012, pp. 25-30. DOI10.1109/netcod.2012.6261879
  28. Waterhouse, W., 10.1080/00029890.1983.11971235, Amer. Math. Monthly 90 (1983), 378-387. MR0707152DOI10.1080/00029890.1983.11971235
  29. Yeung, R. W., Information Theory and Network Coding., Springer, 2008. 
  30. Zhang, Z., Yeung, R. W., 10.1109/18.641561, IEEE Trans. Inform. Theory 43 (1997), 1982-1986. MR1481054DOI10.1109/18.641561
  31. Zhang, Z., Yeung, R. W., 10.1109/18.681320, IEEE Trans. Inform. Theory 44 (1998), 1440-1452. MR1665794DOI10.1109/18.681320

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.