# American Institute of Mathematical Sciences

• Previous Article
On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity
• AMC Home
• This Issue
• Next Article
A note on the order bound on the minimum distance of AG codes and acute semigroups
May  2008, 2(2): 183-200. doi: 10.3934/amc.2008.2.183

## Young subgroups for reversible computers

 1 Imec v.z.w. and Vakgroep elektronika en informatiesystemen, Universiteit Gent, Sint Pietersnieuwstraat 41, B - 9000 Gent, Belgium 2 Vakgroep elektronika en informatiesystemen, Universiteit Gent, Sint Pietersnieuwstraat 41, B - 9000 Gent, Belgium

Received  November 2007 Revised  February 2008 Published  April 2008

We consider the symmetric group $S_n$ in the special case where $n$ is composite: $n = pq$ (both $p$ and $q$ being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of $S$ pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup $S_p^q$, whereas the second one is an element of the dual Young subgroup $S_q^p$. This leads to synthesis methods for arbitrary reversible logic circuits of logic width $w$. These circuits form a group isomorphic to $S$2w. A particularly efficient synthesis is found by choosing $p=2$ and thus $q=2$w−1. The approach illustrates a direct link between combinatorics, group theory, and reversible computing.
Citation: Alexis De Vos, Yvan Van Rentergem. Young subgroups for reversible computers. Advances in Mathematics of Communications, 2008, 2 (2) : 183-200. doi: 10.3934/amc.2008.2.183
 [1] Jinsong Xu. Reversible hidden data access algorithm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1219-1232. doi: 10.3934/dcdss.2019084 [2] Yves Guivarc'h. On the spectrum of a large subgroup of a semisimple group. Journal of Modern Dynamics, 2008, 2 (1) : 15-42. doi: 10.3934/jmd.2008.2.15 [3] Stefano Luzzatto, Marks Ruziboev. Young towers for product systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (3) : 1465-1491. doi: 10.3934/dcds.2016.36.1465 [4] Daniel T. Wise. Nonpositive immersions, sectional curvature, and subgroup properties. Electronic Research Announcements, 2003, 9: 1-9. [5] Marco Castrillón López, Pedro Luis García Pérez. The problem of Lagrange on principal bundles under a subgroup of symmetries. Journal of Geometric Mechanics, 2019, 11 (4) : 539-552. doi: 10.3934/jgm.2019026 [6] Sheena D. Branton. Sub-actions for young towers. Discrete & Continuous Dynamical Systems - A, 2008, 22 (3) : 541-556. doi: 10.3934/dcds.2008.22.541 [7] Konstantinos Drakakis, Francesco Iorio, Scott Rickard, John Walsh. Results of the enumeration of Costas arrays of order 29. Advances in Mathematics of Communications, 2011, 5 (3) : 547-553. doi: 10.3934/amc.2011.5.547 [8] Konstantinos Drakakis, Francesco Iorio, Scott Rickard. The enumeration of Costas arrays of order 28 and its consequences. Advances in Mathematics of Communications, 2011, 5 (1) : 69-86. doi: 10.3934/amc.2011.5.69 [9] Hideyuki Suzuki, Shunji Ito, Kazuyuki Aihara. Double rotations. Discrete & Continuous Dynamical Systems - A, 2005, 13 (2) : 515-532. doi: 10.3934/dcds.2005.13.515 [10] Masahiro Yamaguchi, Yasuhiro Takeuchi, Wanbiao Ma. Population dynamics of sea bass and young sea bass. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 833-840. doi: 10.3934/dcdsb.2004.4.833 [11] Steffen Arnrich. Modelling phase transitions via Young measures. Discrete & Continuous Dynamical Systems - S, 2012, 5 (1) : 29-48. doi: 10.3934/dcdss.2012.5.29 [12] G. Dal Maso, Antonio DeSimone, M. G. Mora, M. Morini. Time-dependent systems of generalized Young measures. Networks & Heterogeneous Media, 2007, 2 (1) : 1-36. doi: 10.3934/nhm.2007.2.1 [13] Katherine Morrison. An enumeration of the equivalence classes of self-dual matrix codes. Advances in Mathematics of Communications, 2015, 9 (4) : 415-436. doi: 10.3934/amc.2015.9.415 [14] Paul H. Rabinowitz. On a class of reversible elliptic systems. Networks & Heterogeneous Media, 2012, 7 (4) : 927-939. doi: 10.3934/nhm.2012.7.927 [15] James C. Robinson. Computing inertial manifolds. Discrete & Continuous Dynamical Systems - A, 2002, 8 (4) : 815-833. doi: 10.3934/dcds.2002.8.815 [16] Antonio Pumariño, Claudia Valls. On the double pendulum: An example of double resonant situations. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 413-448. doi: 10.3934/dcds.2004.11.413 [17] Seok-Jin Kang and Jae-Hoon Kwon. Quantum affine algebras, combinatorics of Young walls, and global bases. Electronic Research Announcements, 2002, 8: 35-46. [18] Claudio A. Buzzi, Jeroen S.W. Lamb. Reversible Hamiltonian Liapunov center theorem. Discrete & Continuous Dynamical Systems - B, 2005, 5 (1) : 51-66. doi: 10.3934/dcdsb.2005.5.51 [19] Santiago Cañez. Double groupoids and the symplectic category. Journal of Geometric Mechanics, 2018, 10 (2) : 217-250. doi: 10.3934/jgm.2018009 [20] Michael Hutchings, Frank Morgan, Manuel Ritore and Antonio Ros. Proof of the double bubble conjecture. Electronic Research Announcements, 2000, 6: 45-49.

2019 Impact Factor: 0.734