November  2016, 10(4): 871-893. doi: 10.3934/amc.2016047

On group violations of inequalities in five subgroups

1. 

Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

Received  March 2015 Revised  August 2015 Published  November 2016

In this paper we use group theoretic tools to obtain random variables which violate linear rank inequalities, that is inequalities which always hold on ranks of subspaces. We consider ten of the 24 (non-Shannon type) generators of linear rank inequalities in five variables and look at them as group inequalities. We prove that for primes $p,q$, groups of order $pq$ always satisfy these ten group inequalities. We give partial results for groups of order $p^2q$, and find that the symmetric group $S_4$ is the smallest group to yield violations for two among the ten group inequalities.
Citation: Nadya Markin, Eldho K. Thomas, Frédérique Oggier. On group violations of inequalities in five subgroups. Advances in Mathematics of Communications, 2016, 10 (4) : 871-893. doi: 10.3934/amc.2016047
References:
[1]

T. H. Chan 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.  Google Scholar

[2]

R. Dougherty, C. Freiling and K. Zeger, Linear rank inequalities on five or more variables,, preprint, ().   Google Scholar

[3]

D. S. Dummit and R. M. Foote, Abstract Algebra, Hoboken, Wiley, 2004.  Google Scholar

[4]

C. F. Gardiner, A First Course in Group Theory, Springer, 2013.  Google Scholar

[5]

D. Hammer, A. Romashchenko, A. Shen and N. Vereshchagin, Inequalities for Shannon entropy and Kolmogorov complexity, in Proc. 12th Ann. IEEE Conf. Comp. Compl., IEEE, 1997, 13-23. doi: 10.1109/CCC.1997.612296.  Google Scholar

[6]

B. Hassibi and S. Shadbakht, Normalized entropy vectors, network information theory and convex optimization, in 2007 Inform. Theory Workshop (ITW 2007), 2007. Google Scholar

[7]

A. Ingleton, Representation of matroids, Combin. Math. Appl., (1971), 23.  Google Scholar

[8]

H. Mann, Additive group theory - a progress report, Bull. Amer. Math. Soc., 79 (1973), 1069-1075.  Google Scholar

[9]

W. Mao and B. Hassibi, Violating the Ingleton inequality with finite groups, in 47th Ann. Allerton Conf. Commun. Contr. Comp., IEEE, 2009, 1053-1060. Google Scholar

[10]

N. Markin, E. Thomas and F. Oggier, Groups and information inequalities in 5 variables, in Allerton'14 Proc. 52nd Ann. Allerton Conf. Commun. Control Comp., IEEE, 2013, 804-809. Google Scholar

[11]

F. Matús, Conditional independences among four random variables I, Combin. Prob. Comp., 4 (1995), 269-278. doi: 10.1017/S0963548300001644.  Google Scholar

[12]

J. J. Rotman, An Introduction to the Theory of Groups, Springer, 1999. doi: 10.1007/978-1-4612-4176-8.  Google Scholar

[13]

J.-P. Serre, Propriétés galoisiennes des points d'ordre fini des courbes elliptiques, Invent. Math., 15 (1971), 259-331.  Google Scholar

[14]

E. K. Thomas, N. Markin and F. Oggier, On Abelian Group Representability of Finite Groups, Adv. Math. Commun., 8 (2014), 139-152. doi: 10.3934/amc.2014.8.139.  Google Scholar

[15]

X. Yan, R. Yeung and Z. Zhang, The capacity for multi-source multi-sink network coding, in 2007 Int. Symp. Inform. Theory (ISIT 2007), Nice, 2007. Google Scholar

show all references

References:
[1]

T. H. Chan 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.  Google Scholar

[2]

R. Dougherty, C. Freiling and K. Zeger, Linear rank inequalities on five or more variables,, preprint, ().   Google Scholar

[3]

D. S. Dummit and R. M. Foote, Abstract Algebra, Hoboken, Wiley, 2004.  Google Scholar

[4]

C. F. Gardiner, A First Course in Group Theory, Springer, 2013.  Google Scholar

[5]

D. Hammer, A. Romashchenko, A. Shen and N. Vereshchagin, Inequalities for Shannon entropy and Kolmogorov complexity, in Proc. 12th Ann. IEEE Conf. Comp. Compl., IEEE, 1997, 13-23. doi: 10.1109/CCC.1997.612296.  Google Scholar

[6]

B. Hassibi and S. Shadbakht, Normalized entropy vectors, network information theory and convex optimization, in 2007 Inform. Theory Workshop (ITW 2007), 2007. Google Scholar

[7]

A. Ingleton, Representation of matroids, Combin. Math. Appl., (1971), 23.  Google Scholar

[8]

H. Mann, Additive group theory - a progress report, Bull. Amer. Math. Soc., 79 (1973), 1069-1075.  Google Scholar

[9]

W. Mao and B. Hassibi, Violating the Ingleton inequality with finite groups, in 47th Ann. Allerton Conf. Commun. Contr. Comp., IEEE, 2009, 1053-1060. Google Scholar

[10]

N. Markin, E. Thomas and F. Oggier, Groups and information inequalities in 5 variables, in Allerton'14 Proc. 52nd Ann. Allerton Conf. Commun. Control Comp., IEEE, 2013, 804-809. Google Scholar

[11]

F. Matús, Conditional independences among four random variables I, Combin. Prob. Comp., 4 (1995), 269-278. doi: 10.1017/S0963548300001644.  Google Scholar

[12]

J. J. Rotman, An Introduction to the Theory of Groups, Springer, 1999. doi: 10.1007/978-1-4612-4176-8.  Google Scholar

[13]

J.-P. Serre, Propriétés galoisiennes des points d'ordre fini des courbes elliptiques, Invent. Math., 15 (1971), 259-331.  Google Scholar

[14]

E. K. Thomas, N. Markin and F. Oggier, On Abelian Group Representability of Finite Groups, Adv. Math. Commun., 8 (2014), 139-152. doi: 10.3934/amc.2014.8.139.  Google Scholar

[15]

X. Yan, R. Yeung and Z. Zhang, The capacity for multi-source multi-sink network coding, in 2007 Int. Symp. Inform. Theory (ISIT 2007), Nice, 2007. Google Scholar

[1]

Yuri Berest, Alimjon Eshmatov, Farkhod Eshmatov. On subgroups of the Dixmier group and Calogero-Moser spaces. Electronic Research Announcements, 2011, 18: 12-21. doi: 10.3934/era.2011.18.12

[2]

Jan J. Sławianowski, Vasyl Kovalchuk, Agnieszka Martens, Barbara Gołubowska, Ewa E. Rożko. Essential nonlinearity implied by symmetry group. Problems of affine invariance in mechanics and physics. Discrete & Continuous Dynamical Systems - B, 2012, 17 (2) : 699-733. doi: 10.3934/dcdsb.2012.17.699

[3]

John Franks, Michael Handel. Some virtually abelian subgroups of the group of analytic symplectic diffeomorphisms of a surface. Journal of Modern Dynamics, 2013, 7 (3) : 369-394. doi: 10.3934/jmd.2013.7.369

[4]

Elena Celledoni, Brynjulf Owren. Preserving first integrals with symmetric Lie group methods. Discrete & Continuous Dynamical Systems, 2014, 34 (3) : 977-990. doi: 10.3934/dcds.2014.34.977

[5]

Mahesh Nerurkar. Forced linear oscillators and the dynamics of Euclidean group extensions. Discrete & Continuous Dynamical Systems - S, 2016, 9 (4) : 1201-1234. doi: 10.3934/dcdss.2016049

[6]

Wenying Zhang, Zhaohui Xing, Keqin Feng. A construction of bent functions with optimal algebraic degree and large symmetric group. Advances in Mathematics of Communications, 2020, 14 (1) : 23-33. doi: 10.3934/amc.2020003

[7]

Carlos Matheus, Jean-Christophe Yoccoz. The action of the affine diffeomorphisms on the relative homology group of certain exceptionally symmetric origamis. Journal of Modern Dynamics, 2010, 4 (3) : 453-486. doi: 10.3934/jmd.2010.4.453

[8]

Pablo Ochoa. Approximation schemes for non-linear second order equations on the Heisenberg group. Communications on Pure & Applied Analysis, 2015, 14 (5) : 1841-1863. doi: 10.3934/cpaa.2015.14.1841

[9]

Axel Kohnert, Johannes Zwanzger. New linear codes with prescribed group of automorphisms found by heuristic search. Advances in Mathematics of Communications, 2009, 3 (2) : 157-166. doi: 10.3934/amc.2009.3.157

[10]

Raz Kupferman, Asaf Shachar. On strain measures and the geodesic distance to $SO_n$ in the general linear group. Journal of Geometric Mechanics, 2016, 8 (4) : 437-460. doi: 10.3934/jgm.2016015

[11]

Philippe Ciarlet. Korn's inequalities: The linear vs. the nonlinear case. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 473-483. doi: 10.3934/dcdss.2012.5.473

[12]

Jianxun Liu, Shengjie Li, Yingrang Xu. Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021083

[13]

Yanjun Wang, Shisen Liu. Relaxation schemes for the joint linear chance constraint based on probability inequalities. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021132

[14]

Sergio Estrada, J. R. García-Rozas, Justo Peralta, E. Sánchez-García. Group convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 83-94. doi: 10.3934/amc.2008.2.83

[15]

Heping Liu, Yu Liu. Refinable functions on the Heisenberg group. Communications on Pure & Applied Analysis, 2007, 6 (3) : 775-787. doi: 10.3934/cpaa.2007.6.775

[16]

Stefan Haller, Tomasz Rybicki, Josef Teichmann. Smooth perfectness for the group of diffeomorphisms. Journal of Geometric Mechanics, 2013, 5 (3) : 281-294. doi: 10.3934/jgm.2013.5.281

[17]

Van Cyr, John Franks, Bryna Kra, Samuel Petite. Distortion and the automorphism group of a shift. Journal of Modern Dynamics, 2018, 13: 147-161. doi: 10.3934/jmd.2018015

[18]

Woochul Jung, Keonhee Lee, Carlos Morales, Jumi Oh. Rigidity of random group actions. Discrete & Continuous Dynamical Systems, 2020, 40 (12) : 6845-6854. doi: 10.3934/dcds.2020130

[19]

Daniele D'angeli, Alfredo Donno, Michel Matter, Tatiana Nagnibeda. Schreier graphs of the Basilica group. Journal of Modern Dynamics, 2010, 4 (1) : 167-205. doi: 10.3934/jmd.2010.4.167

[20]

Kesong Yan, Qian Liu, Fanping Zeng. Classification of transitive group actions. Discrete & Continuous Dynamical Systems, 2021, 41 (12) : 5579-5607. doi: 10.3934/dcds.2021089

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (133)
  • HTML views (0)
  • Cited by (0)

[Back to Top]