Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

r""" 

Free abelian monoids 

 

AUTHORS: 

 

- David Kohel (2005-09) 

 

Sage supports free abelian monoids on any prescribed finite number 

`n\geq 0` of generators. Use the 

``FreeAbelianMonoid`` function to create a free abelian 

monoid, and the ``gen`` and ``gens`` 

functions to obtain the corresponding generators. You can print the 

generators as arbitrary strings using the optional 

``names`` argument to the 

``FreeAbelianMonoid`` function. 

 

EXAMPLE 1: It is possible to create an abelian monoid in zero or 

more variables; the syntax T(1) creates the monoid identity 

element even in the rank zero case. 

 

:: 

 

sage: T = FreeAbelianMonoid(0, '') 

sage: T 

Free abelian monoid on 0 generators () 

sage: T.gens() 

() 

sage: T(1) 

1 

 

EXAMPLE 2: A free abelian monoid uses a multiplicative 

representation of elements, but the underlying representation is 

lists of integer exponents. 

 

:: 

 

sage: F = FreeAbelianMonoid(5,names='a,b,c,d,e') 

sage: (a,b,c,d,e) = F.gens() 

sage: a*b^2*e*d 

a*b^2*d*e 

sage: x = b^2*e*d*a^7 

sage: x 

a^7*b^2*d*e 

sage: x.list() 

[7, 2, 0, 1, 1] 

""" 

#***************************************************************************** 

# Copyright (C) 2005 David Kohel <kohel@maths.usyd.edu> 

# 

# This program is free software: you can redistribute it and/or modify 

# it under the terms of the GNU General Public License as published by 

# the Free Software Foundation, either version 2 of the License, or 

# (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from __future__ import absolute_import 

from six import integer_types 

 

from sage.misc.cachefunc import cached_method 

from sage.structure.category_object import normalize_names 

from sage.structure.parent import Parent 

from sage.categories.monoids import Monoids 

from .free_abelian_monoid_element import FreeAbelianMonoidElement 

from sage.rings.integer import Integer 

from sage.rings.all import ZZ 

 

from sage.structure.factory import UniqueFactory 

from sage.misc.decorators import rename_keyword 

 

class FreeAbelianMonoidFactory(UniqueFactory): 

""" 

Create the free abelian monoid in `n` generators. 

 

INPUT: 

 

 

- ``n`` - integer 

 

- ``names`` - names of generators 

 

 

OUTPUT: free abelian monoid 

 

EXAMPLES:: 

 

sage: FreeAbelianMonoid(0, '') 

Free abelian monoid on 0 generators () 

sage: F = FreeAbelianMonoid(5,names = list("abcde")) 

sage: F 

Free abelian monoid on 5 generators (a, b, c, d, e) 

sage: F(1) 

1 

sage: (a, b, c, d, e) = F.gens() 

sage: mul([ a, b, a, c, b, d, c, d ], F(1)) 

a^2*b^2*c^2*d^2 

sage: a**2 * b**3 * a**2 * b**4 

a^4*b^7 

 

:: 

 

sage: loads(dumps(F)) is F 

True 

""" 

def create_key(self, n, names): 

n = int(n) 

names = normalize_names(n, names) 

return (n, names) 

def create_object(self, version, key): 

return FreeAbelianMonoid_class(*key) 

 

FreeAbelianMonoid_factory = FreeAbelianMonoidFactory("sage.monoids.free_abelian_monoid.FreeAbelianMonoid_factory") 

 

@rename_keyword(deprecation=15289, n="index_set") 

def FreeAbelianMonoid(index_set=None, names=None, **kwds): 

""" 

Return a free abelian monoid on `n` generators or with the generators 

indexed by a set `I`. 

 

We construct free abelian monoids by specifing either: 

 

- the number of generators and/or the names of the generators 

- the indexing set for the generators (this ignores the other two inputs) 

 

INPUT: 

 

- ``index_set`` -- an indexing set for the generators; if an integer, 

then this becomes `\{0, 1, \ldots, n-1\}` 

 

- ``names`` -- names of generators 

 

OUTPUT: 

 

A free abelian monoid. 

 

EXAMPLES:: 

 

sage: F.<a,b,c,d,e> = FreeAbelianMonoid(); F 

Free abelian monoid on 5 generators (a, b, c, d, e) 

sage: FreeAbelianMonoid(index_set=ZZ) 

Free abelian monoid indexed by Integer Ring 

""" 

if isinstance(index_set, str): # Swap args (this works if names is None as well) 

names, index_set = index_set, names 

 

if index_set is None and names is not None: 

if isinstance(names, str): 

index_set = names.count(',') 

else: 

index_set = len(names) 

 

if index_set not in ZZ: 

if names is not None: 

names = normalize_names(len(names), names) 

from sage.monoids.indexed_free_monoid import IndexedFreeAbelianMonoid 

return IndexedFreeAbelianMonoid(index_set, names=names, **kwds) 

 

if names is None: 

raise ValueError("names must be specified") 

return FreeAbelianMonoid_factory(index_set, names) 

 

def is_FreeAbelianMonoid(x): 

""" 

Return True if `x` is a free abelian monoid. 

 

EXAMPLES:: 

 

sage: from sage.monoids.free_abelian_monoid import is_FreeAbelianMonoid 

sage: is_FreeAbelianMonoid(5) 

False 

sage: is_FreeAbelianMonoid(FreeAbelianMonoid(7,'a')) 

True 

sage: is_FreeAbelianMonoid(FreeMonoid(7,'a')) 

False 

sage: is_FreeAbelianMonoid(FreeMonoid(0,'')) 

False 

""" 

return isinstance(x, FreeAbelianMonoid_class) 

 

class FreeAbelianMonoid_class(Parent): 

""" 

Free abelian monoid on `n` generators. 

""" 

Element = FreeAbelianMonoidElement 

 

def __init__(self, n, names): 

""" 

Initialize ``self``. 

 

EXAMPLES:: 

 

sage: F = FreeAbelianMonoid(6,'b') 

sage: TestSuite(F).run() 

""" 

if not isinstance(n, integer_types + (Integer,)): 

raise TypeError("n (=%s) must be an integer"%n) 

if n < 0: 

raise ValueError("n (=%s) must be nonnegative"%n) 

self.__ngens = int(n) 

assert names is not None 

Parent.__init__(self, names=names, category=Monoids().Commutative()) 

 

def __repr__(self): 

n = self.__ngens 

return "Free abelian monoid on %s generators %s"%(n,self.gens()) 

 

def __call__(self, x): 

""" 

Create an element of this abelian monoid from `x`. 

 

EXAMPLES:: 

 

sage: F = FreeAbelianMonoid(10,'x') 

sage: F(F.gen(2)) 

x2 

sage: F(1) 

1 

""" 

if isinstance(x, FreeAbelianMonoidElement) and x.parent() == self: 

return x 

return self.element_class(self, x) 

 

 

def __contains__(self, x): 

""" 

Return True if `x` is an element of this abelian monoid. 

 

EXAMPLES:: 

 

sage: F = FreeAbelianMonoid(10,'b') 

sage: F.gen(2)*F.gen(3) in F 

True 

 

Note that a monoid on `9` generators is not considered a 

submonoid of one on `10` generators. 

 

:: 

 

sage: FreeAbelianMonoid(9,'c').gen(2) in F 

False 

 

However, multiple calls to the monoid constructor do *not* return 

multiple distinct monoids. 

 

:: 

 

sage: FreeAbelianMonoid(10,'b').gen(2) in F 

True 

""" 

return isinstance(x, FreeAbelianMonoidElement) and x.parent() == self 

 

def gen(self, i=0): 

""" 

The `i`-th generator of the abelian monoid. 

 

EXAMPLES:: 

 

sage: F = FreeAbelianMonoid(5,'a') 

sage: F.gen(0) 

a0 

sage: F.gen(2) 

a2 

""" 

n = self.__ngens 

if i < 0 or not i < n: 

raise IndexError("Argument i (= %s) must be between 0 and %s."%(i, n-1)) 

x = [ 0 for j in range(n) ] 

x[int(i)] = 1 

return self.element_class(self, x) 

 

@cached_method 

def gens(self): 

""" 

Return the generators of ``self``. 

 

EXAMPLES:: 

 

sage: F = FreeAbelianMonoid(5,'a') 

sage: F.gens() 

(a0, a1, a2, a3, a4) 

""" 

return tuple([self.gen(i) for i in range(self.__ngens)]) 

 

def ngens(self): 

""" 

The number of free generators of the abelian monoid. 

 

EXAMPLES:: 

 

sage: F = FreeAbelianMonoid(3000, 'a') 

sage: F.ngens() 

3000 

""" 

return self.__ngens 

 

def cardinality(self): 

r""" 

Return the cardinality of ``self``, which is `\infty`. 

 

EXAMPLES:: 

 

sage: F = FreeAbelianMonoid(3000, 'a') 

sage: F.cardinality() 

+Infinity 

""" 

if self.__ngens == 0: 

from sage.rings.all import ZZ 

return ZZ.one() 

from sage.rings.infinity import infinity 

return infinity