Geodesic
Violations of the Ingleton inequality and revising the four-atom conjecture
Kybernetika, Tome 56 (2020) no. 5, pp. 916-933
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2020-5-0916
Classification : 20B35, 94A15
Keywords: entropy vectors; information inequalities; subgroup indices 
@article{10_14736_kyb_2020_5_0916,
     author = {Boston, Nigel and Nan, Ting-Ting},
     title = {Violations of the {Ingleton} inequality and revising the four-atom conjecture},
     journal = {Kybernetika},
     pages = {916--933},
     year = {2020},
     volume = {56},
     number = {5},
     doi = {10.14736/kyb-2020-5-0916},
     mrnumber = {4187780},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-5-0916/}
}
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
SP  - 916
EP  - 933
VL  - 56
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-5-0916/
DO  - 10.14736/kyb-2020-5-0916
LA  - en
ID  - 10_14736_kyb_2020_5_0916
ER  - 
%0 Journal Article
%A Boston, Nigel
%A Nan, Ting-Ting
%T Violations of the Ingleton inequality and revising the four-atom conjecture
%J Kybernetika
%D 2020
%P 916-933
%V 56
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-5-0916/
%R 10.14736/kyb-2020-5-0916
%G en
%F 10_14736_kyb_2020_5_0916
Boston, Nigel; Nan, Ting-Ting. Violations of the Ingleton inequality and revising the four-atom conjecture. Kybernetika, Tome 56 (2020) no. 5, pp. 916-933. doi: 10.14736/kyb-2020-5-0916

[1] Ahlswede, R., Cai, N., Li, S.-Y. R., Yeung, R. W.: Network information flow. IEEE Trans. Inform. Theory 46 (2007), 1204-1216. | DOI | MR

[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.: The Magma algebra system. The user language, J. Symbolic Comput. 24 (1997), 235-265. | DOI | MR

[4] Boston, N., Nan, T.-T.: Large violations of the Ingleton inequality. In: 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012. | DOI

[5] Boston, N., Nan, T.-T.: A refinement of the four-atom conjecture. In: International Symposium on Network Coding (NetCod), 2013. | DOI

[6] Chen, T.: Group characterizable entropiy functions. In: Proc. of the 2005 IEEE International Symposium on Information Theory, Nice 2007, pp. 507-510. | DOI

[7] Chen, T. H., Yeung, R. W.: On a relation between information inequalities and group theory. IEEE Trans. Inform. Theory 48 (2002), 1992-1995. | DOI | MR

[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.: Insufficiency of linear coding in network information flow. IEEE Trans. Inform. Theory 51 (2005), 2745-2759. | DOI | MR

[10] Dougherty, R., Freiling, C., Zeger, K.: Networks, matroids, and non-Shannon information inequalities. IEEE Trans. Inform. Theory 53 (2007), 1949-1969. | DOI | MR

[11] Dougherty, R., Freiling, C., Zeger, K.: Non-Shannon information inequalities in four random variables. arXiv:1104.3602v1, 2011. | MR

[12] Ho, T., Médard, M., Koetter, R., Karger, D. R., Effros, M., Shi, J., Leong, B.: A random linear network coding approach to multicast. IEEE Trans. Inform. Theory 52 (2006), 4413-4430. | DOI | MR

[13] Ingleton, A.: Representation of matroids. In: Combinatorial Mathematics and its Applications, 1971, pp. 149-167. | MR

[14] M.Isaacs, I.: Finite Group Theory. American Mathematical Society, 2008. | DOI | MR

[15] Koetter, R., Médard, M.: An algebraic approach to network coding. IEEE/ACM Trans. Network. 2 (2003), 782-795. | DOI

[16] Li, R., Yeung, R., Cai, N.: Linear network coding. IEEE Trans. Inform. Theory 49 (2003), 371-381. | DOI | MR

[17] Makarycheve, K., Makarycheve, L., Romashchenko, A. E., Vereshchagin, N. K.: A new class of non-Shannon type inequalities for entropies. Com. Inform. Syst. 2 (2002), 147-166. | DOI | MR

[18] Mao, W., Thill, M., Hassibi, B.: On Ingleton-violating finite groups. IEEE Trans. Inform. Theory 63 (2017), 183-200. | DOI | MR

[19] Matúš, F.: Conditional independences among four random variables II. Combin. Probab. Comput. 4 (1995), 407-417. | DOI | MR

[20] Matúš, F.: Conditional independences among four random variables III: Final conclusion. Combin. Probab. Comput. 8 (1999), 269-276. | DOI | MR

[21] Matúš, F.: Infinitely many information inequalities. In: IEEE International Symposium on Information Theory, IEEE 2007, pp. 41-44. | DOI

[22] Matúš, F., Csirmaz, L.: Entropy region and convolution. IEEE Trans. Inform. Theory 62 (2016), 6007-6018. | DOI | MR

[23] Matúš, F., Studený, M.: Conditional independences among four random variables I. Combin. Probab. Comput. 4 (1995), 269-278. | DOI | MR

[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. | MR

[26] Paajanen, P.: Finite p-groups, entropy vectors and the ingleton inequality for nilpotent groups. IEEE Trans. Inform. Theory 60 (2014), 3821-3824. | DOI | MR

[27] Stancu, R., Oggier, F.: Finite nilpotent and metacyclic groups never violate the Ingleton inequality. 2012 International Symposium on Network Coding (NetCod), 2012, pp. 25-30. | DOI

[28] Waterhouse, W.: Do symmetric problems have symmetric solutions?. Amer. Math. Monthly 90 (1983), 378-387. | DOI | MR

[29] Yeung, R. W.: Information Theory and Network Coding. Springer, 2008.

[30] Zhang, Z., Yeung, R. W.: A non-Shannon type conditional inequality of information quantities. IEEE Trans. Inform. Theory 43 (1997), 1982-1986. | DOI | MR

[31] Zhang, Z., Yeung, R. W.: On characterization of entropy function via information inequalities. IEEE Trans. Inform. Theory 44 (1998), 1440-1452. | DOI | MR

Cité par Sources :