1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 // 1. Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // 3. The name of the author may not be used to endorse or promote products
17 // derived from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // ---------------------------------------------------------------------------
31
32
33 #ifndef GIANT_TEST_H_
34 #define GIANT_TEST_H_
35
36 #include <permlib/generator/product_replacement_generator.h>
37 #include <permlib/transversal/explicit_transversal.h>
38 #include <permlib/bsgs.h>
39 #include <permlib/construct/schreier_sims_construction.h>
40 #include <permlib/prime_helper.h>
41
42 #include <boost/foreach.hpp>
43 #include <boost/integer/common_factor_rt.hpp>
44 #include <cmath>
45 #include <algorithm>
46
47 namespace permlib {
48
49
50 struct GiantTestBase {
51 /// Enumeration of "giant" groups, i.e. Alternating and Symmetric group
52 enum GiantGroupType { None, Alternating, Symmetric };
53 };
54
55 /// Tests a group given by generators for being an Alternating Group or a Symmetric Group
56 /**
57 * This an implementation of the algorithm given in
58 * Holt, Eick, O'Brien: Handbook of Computational Group Theory, 2005. Chapter 4.2
59 */
60 template<typename PERM>
61 class GiantTest : public GiantTestBase {
62 public:
63 /// tests whether group given by generators is an Alternating or a Symmetric Group
64 /**
65 * The test is deterministic for n < 8 and randomized for n >= 8.
66 * The randomized test assumes that n is smaller than
67 *
68 * @param eps If randomized, 1-eps is the probability that the decision "None" is wrong
69 * @param n Degree of the group
70 * @param begin iterator of Permutation::ptr, group generators
71 * @param end iterator of Permutation::ptr, group generators
72 * @param bsgs if for the test a BSGS is computed, it is stored into this variable
73 * @param isKnownPrimitive true if group is known to be primitive
74 * @return Result "None" may be wrong if n >= 8 with probability eps
75 */
76 template<typename ForwardIterator, typename TRANS>
77 GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, BSGS<PERM, TRANS>& bsgs, bool isKnownPrimitive = false) const;
78
79 /// tests whether group given by generators is an Alternating or a Symmetric Group
80 /**
81 * The test is deterministic for n < 8 and randomized for n >= 8.
82 * The randomized test assumes that n is smaller than
83 *
84 * @param eps If randomized, 1-eps is the probability that the decision "None" is wrong
85 * @param n Degree of the group
86 * @param begin iterator of Permutation::ptr, group generators
87 * @param end iterator of Permutation::ptr, group generators
88 * @param isKnownPrimitive true if group is known to be primitive
89 * @return Result "None" may be wrong if n >= 8 with probability eps
90 */
91 template<typename ForwardIterator>
92 GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, bool isKnownPrimitive = false) const {
93 typedef ExplicitTransversal<PERM> TRANS;
94 BSGS<PERM, TRANS> bsgs(n);
95 return determineGiantType<ForwardIterator, TRANS>(eps, n, begin, end, bsgs, isKnownPrimitive);
96 }
97
98 /// tests whether group given by generators is a subgroup of an Alternating Group
99 /**
100 * Tests subgroup property by computing parity of all generators.
101 * @param begin iterator of Permutation::ptr, group generators
102 * @param end iterator of Permutation::ptr, group generators
103 * @return true if the group is a subgroup of an alternating group
104 */
105 template<typename ForwardIterator>
106 static bool isSubgroupOfAlternatingGroup(ForwardIterator begin, ForwardIterator end);
107
108 private:
109 template<class T>
110 static GiantGroupType giantTypeByOrder(const T& order, const T& symOrder);
111 };
112
113
114 template<typename PERM>
115 template<typename ForwardIterator>
isSubgroupOfAlternatingGroup(ForwardIterator begin,ForwardIterator end)116 bool GiantTest<PERM>::isSubgroupOfAlternatingGroup(ForwardIterator begin, ForwardIterator end) {
117 typedef std::pair<dom_int, unsigned int> CyclePair;
118 for (ForwardIterator pit = begin; pit != end; ++pit) {
119 unsigned int parity = 0;
120 std::list<CyclePair> genCycles = (*pit)->cycles();
121 BOOST_FOREACH(const CyclePair& c, genCycles) {
122 if (c.second % 2 == 0)
123 ++parity;
124 }
125 if (parity % 2 != 0)
126 return false;
127 }
128 return true;
129 }
130
131 template<typename PERM>
132 template<typename T>
giantTypeByOrder(const T & order,const T & symOrder)133 GiantTestBase::GiantGroupType GiantTest<PERM>::giantTypeByOrder(const T& order, const T& symOrder) {
134 if (order == symOrder / 2)
135 return Alternating;
136 if (order == symOrder)
137 return Symmetric;
138 return None;
139 }
140
141 template<typename PERM>
142 template<typename ForwardIterator, typename TRANS>
determineGiantType(double eps,unsigned int n,ForwardIterator begin,ForwardIterator end,BSGS<PERM,TRANS> & bsgs,bool isKnownPrimitive)143 GiantTestBase::GiantGroupType GiantTest<PERM>::determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, BSGS<PERM, TRANS>& bsgs, bool isKnownPrimitive) const {
144 BOOST_ASSERT(n > 1);
145
146 // special cases for n < 8
147
148 if (n == 2) {
149 for (ForwardIterator pit = begin; pit != end; ++pit) {
150 if ( ! (*pit)->isIdentity() )
151 return Symmetric;
152 }
153 return None;
154 } else if (n < 8) {
155 SchreierSimsConstruction<PERM, TRANS> ssc(n);
156 bsgs = ssc.construct(begin, end);
157 const boost::uint64_t order = bsgs.order();
158 switch (n) {
159 case 3:
160 return giantTypeByOrder(order, static_cast<boost::uint64_t>(6));
161 case 4:
162 return giantTypeByOrder(order, static_cast<boost::uint64_t>(24));
163 case 5:
164 return giantTypeByOrder(order, static_cast<boost::uint64_t>(120));
165 case 6:
166 return giantTypeByOrder(order, static_cast<boost::uint64_t>(720));
167 case 7:
168 return giantTypeByOrder(order, static_cast<boost::uint64_t>(5040));
169 default:
170 // should not happen
171 BOOST_ASSERT(false);
172 return None;
173 }
174 }
175
176 // This constant 0.395 comes from 0.57 * log(2)
177 const unsigned int randomRuns = static_cast<unsigned int>(-std::log(eps) * std::log(n) / 0.395);
178
179 ProductReplacementGenerator<PERM> rng(n, begin, end);
180 for (unsigned int i = 0; i < randomRuns; ++i) {
181 PERM randPerm = rng.next();
182 typedef std::pair<dom_int, unsigned int> CyclePair;
183 std::list<CyclePair> cycleList = randPerm.cycles();
184 std::vector<unsigned int> cycleLength(cycleList.size());
185 unsigned int j = 0;
186 BOOST_FOREACH(const CyclePair& c, cycleList) {
187 cycleLength[j++] = c.second;
188 }
189 for (j = 0; j < cycleLength.size(); ++j) {
190 const unsigned int len = cycleLength[j];
191 if (len < n-2 && PrimeHelper::isPrimeNumber(len, true) && (isKnownPrimitive || len > n/2)) {
192 // check whether $len is co-prime to all other cycle length.
193 // if so, the group contains a real cycle of length $len
194 bool isCoprime = true;
195 for (unsigned int k = 0; k < cycleLength.size(); ++k) {
196 if (j == k)
197 continue;
198 if (boost::integer::gcd(cycleLength[j], cycleLength[k]) != 1) {
199 isCoprime = false;
200 break;
201 }
202 }
203 if ( ! isCoprime )
204 continue;
205
206 if (isSubgroupOfAlternatingGroup(begin, end))
207 return Alternating;
208 else
209 return Symmetric;
210 }
211 }
212 }
213
214 return None;
215 }
216
217
218 } // end NS permlib
219
220 #endif
221