On group violations of inequalities in five subgroups

Previous Article
Variation on correlation immune Boolean and vectorial functions
AMC Home
This Issue
Next Article
Public key protocols over the ring $E_{p}^{(m)}$

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

On group violations of inequalities in five subgroups

Nadya Markin ^1, , Eldho K. Thomas ^1, and Frédérique Oggier ^1,

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

Received March 2015 Revised August 2015 Published November 2016

Abstract
Related Papers

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.

Keywords: lattice of subgroups, Group inequalities, linear inequalities, symmetric group..

Mathematics Subject Classification: Primary: 20D30; Secondary: 94A1.

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.
[2]	R. Dougherty, C. Freiling and K. Zeger, Linear rank inequalities on five or more variables, preprint, arXiv:0910.0284
[3]	D. S. Dummit and R. M. Foote, Abstract Algebra, Hoboken, Wiley, 2004.
[4]	C. F. Gardiner, A First Course in Group Theory, Springer, 2013.
[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.
[6]	B. Hassibi and S. Shadbakht, Normalized entropy vectors, network information theory and convex optimization, in 2007 Inform. Theory Workshop (ITW 2007), 2007.
[7]	A. Ingleton, Representation of matroids, Combin. Math. Appl., (1971), 23.
[8]	H. Mann, Additive group theory - a progress report, Bull. Amer. Math. Soc., 79 (1973), 1069-1075.
[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.
[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.
[11]	F. Matús, Conditional independences among four random variables I, Combin. Prob. Comp., 4 (1995), 269-278. doi: 10.1017/S0963548300001644.
[12]	J. J. Rotman, An Introduction to the Theory of Groups, Springer, 1999. doi: 10.1007/978-1-4612-4176-8.
[13]	J.-P. Serre, Propriétés galoisiennes des points d'ordre fini des courbes elliptiques, Invent. Math., 15 (1971), 259-331.
[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.
[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.

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.
[2]	R. Dougherty, C. Freiling and K. Zeger, Linear rank inequalities on five or more variables, preprint, arXiv:0910.0284
[3]	D. S. Dummit and R. M. Foote, Abstract Algebra, Hoboken, Wiley, 2004.
[4]	C. F. Gardiner, A First Course in Group Theory, Springer, 2013.
[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.
[6]	B. Hassibi and S. Shadbakht, Normalized entropy vectors, network information theory and convex optimization, in 2007 Inform. Theory Workshop (ITW 2007), 2007.
[7]	A. Ingleton, Representation of matroids, Combin. Math. Appl., (1971), 23.
[8]	H. Mann, Additive group theory - a progress report, Bull. Amer. Math. Soc., 79 (1973), 1069-1075.
[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.
[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.
[11]	F. Matús, Conditional independences among four random variables I, Combin. Prob. Comp., 4 (1995), 269-278. doi: 10.1017/S0963548300001644.
[12]	J. J. Rotman, An Introduction to the Theory of Groups, Springer, 1999. doi: 10.1007/978-1-4612-4176-8.
[13]	J.-P. Serre, Propriétés galoisiennes des points d'ordre fini des courbes elliptiques, Invent. Math., 15 (1971), 259-331.
[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.
[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.

[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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems - S, 2012, 5 (3) : 473-483. doi: 10.3934/dcdss.2012.5.473
[12]	Yanjun Wang, Shisen Liu. Relaxation schemes for the joint linear chance constraint based on probability inequalities. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021132
[13]	Jianxun Liu, Shengjie Li, Yingrang Xu. Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2599-2610. doi: 10.3934/jimo.2021083
[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 and 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 and 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 and Continuous Dynamical Systems, 2021, 41 (12) : 5579-5607. doi: 10.3934/dcds.2021089

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Nadya Markin Eldho K. Thomas Frédérique Oggier
on Google Scholar
Nadya Markin Eldho K. Thomas Frédérique Oggier

[Back to Top]