Part 1: the integers

Integers, divisibility, gcd, prime factorization

# Check whether a divides b
b = 12348
a = 12
q = b // a
r = b % a
print(b, a*q+r, q,r )

12348 12348 1029 0

# Check if 13 divides 1669

# List all positive divisors of 1234
divisors(1234)

[1, 2, 617, 1234]

# List all positive divisors of 2345
# List all positive divisors of 1234*2345

# Plot the Hasse diagram of all positive divisors of 360
P=posets.DivisorLattice(360)
P.show()
# Then Plot the intervall between 4 and 360
P.subposet( P.order_filter([4]) ).show()

# Now Plot the Hasse diagram of the positive divisors of 90. Conclusions?

# Calculate the gcd of a and b and express it as a linear combination

a = 123454
b = 234564
d,x,y = xgcd(a,b)
print(d,x,y)
# test that d is lin comb
print(d - a*x - b*y)

2 50261 -26453
0

xgcd?

# Calculate the gcd of 98765 and 12345 and express it as a linear combination

# Find the multiplicative inverse of a mod n, check
# Method: ax cong 1 mod n iff ax = 1 + ny
# i.e. ax -ny =1
a = 1233
n = 3237
d,x,y = xgcd(a,n)
print(d,x,y)
print(d.divides(1))

3 -21 8
False

# So, not possible

# Find the multiplicative inverse of a mod n, check
a = 1273
n = 3237
d,x,y = xgcd(a,n)
print(d,x,y)
print(d.divides(1))
print(a*x % n)

1 -1574 619
True
1

# Now you:
# Find the multiplicative inverse of 54321 mod 75231, if it exists
# Find the multiplicative inverse of 54322 mod 75231, if it exists
# Find the multiplicative inverse of 54323 mod 75231, if it exists

Congruences, CRT

# Solve the linear congruence ax cong b mod n, if possible. Check result.
a = 8
n = 4
b = 3
d,u,v = xgcd(a,n)
print(d,u,v)
print(d.divides(b))

4 0 1
False

# directly
solve_mod?

var('x')
solve_mod([a*x==b],n)

[]

# Solve the linear congruence ax cong b mod n, if possible. Check result.
a = 7
n = 40
b = 3
d,u,v = xgcd(a,n)
print(d,u,v)
# ax cong b mod n becomes x cong a^{-1}*b mod n
print(u*b)
print(u*b % n)
#check 
print(a*u*b % n)

# directly
var('x')
a = 7
n = 40
b = 3
solve_mod([a*x==b],n)

[(29,)]

# You can also solve quadratic modular congruences
var('x')
a = 7
n = 11
solve_mod([x^2==5],n)

[(4,), (7,)]

Exercise modular square roots

Which congruences mod 19 have square roots?
Mod which small primes does 19 have a square root?

Chinese remainder theorem

# CRT
crt?

# solve x cong 4  mod 11
#       x cong 5  mod 13
x = crt([4,5],[11,13])
x

# check
x % 11

x % 13

# solve x cong 4  mod 101
#       x cong 5  mod 107
# check your result

x=crt([-1,-2],[2,3])
x

# check
print(x % 2)
print(x % 3)

1
1

x=crt([-1,-2,-3,-3,-5],[2,3,5,7,11])
x

x/(2*3*5*7*11)

1117/2310

Exercise CRT

Define f(n) as smallest positive x such that x cong -k mod p_k for the first k primes p_1,..,p_k

Plot the values of f(n)/(prod p_k)

Integers modulo n

n = 8
Zn = Integers(n)

a = Zn(3)
a+a+a

Zn.addition_table(names='elements')

+  0 1 2 3 4 5 6 7
 +----------------
0| 0 1 2 3 4 5 6 7
1| 1 2 3 4 5 6 7 0
2| 2 3 4 5 6 7 0 1
3| 3 4 5 6 7 0 1 2
4| 4 5 6 7 0 1 2 3
5| 5 6 7 0 1 2 3 4
6| 6 7 0 1 2 3 4 5
7| 7 0 1 2 3 4 5 6

# orders of elements

for a in Zn:
    print(a, a.order())

from collections import Counter
orderlist = [a.order() for a in Zn]
print(orderlist)
co =Counter(orderlist)
print(sorted(co.items()))

[1, 8, 4, 8, 2, 8, 4, 8]
[(1, 1), (2, 1), (4, 2), (8, 4)]

Exercise order of elements in cyclic group

For various n, use the above code to find the number of elements of order k in Zn.
Formulate a hypothesis
(prove it if you can)

Part 2: permutations

Representations of Permutations

# Symmetric group on 4 letters
G = SymmetricGroup(4)

# Element iterator
for g in G:
    print(g,order(g))

() 1
(1,3)(2,4) 2
(1,4)(2,3) 2
(1,2)(3,4) 2
(2,3,4) 3
(1,3,2) 3
(1,4,3) 3
(1,2,4) 3
(2,4,3) 3
(1,3,4) 3
(1,4,2) 3
(1,2,3) 3
(3,4) 2
(1,3,2,4) 4
(1,4,2,3) 4
(1,2) 2
(2,3) 2
(1,3,4,2) 4
(1,4) 2
(1,2,4,3) 4
(2,4) 2
(1,3) 2
(1,4,3,2) 4
(1,2,3,4) 4

# Random element
h = G.an_element()
h

(2,3,4)

# Specify an element
h = G([(1,2),(3,4)])
h

(1,2)(3,4)

h.cycle_type()

[2, 2]

h.dict()

{1: 2, 2: 1, 3: 4, 4: 3}

h.matrix()

[0 1 0 0]
[1 0 0 0]
[0 0 0 1]
[0 0 1 0]

# Another type of permutation... sometimes you need to coonvert

Permutation(h)

[2, 1, 4, 3]

# and back...
G(Permutation(h))

(1,2)(3,4)

Permutation(h).to_digraph()

# Larger example
S20 = SymmetricGroup(20)
si = S20.random_element()
SI = Permutation(si)

print(si)
print(SI)
SI.to_digraph().plot()

(1,14,16,7,8,17,12,13,15,18,11,9)(2,10,19)(3,6,4)(5,20)
[14, 10, 6, 3, 20, 4, 8, 17, 1, 19, 9, 13, 15, 16, 18, 7, 12, 11, 2, 5]

IOStream.flush timed out

# Define a  permutation, 
r = Permutation([2,3,4,5,1])
s = Permutation([2,1])
print(r,s)
print(r.left_action_product(s))
print(r.right_action_product(s))
print("as elements of S5:\n")
G = SymmetricGroup(5)
R=G(r)
S=G(s)
print(R,S)
#alternatively
print(r.to_permutation_group_element(), s.to_permutation_group_element())
print("R*S =",R*S)
print("S*R =",S*R)

[2, 3, 4, 5, 1] [2, 1]
[3, 2, 4, 5, 1]
[1, 3, 4, 5, 2]
as elements of S5:

(1,2,3,4,5) (1,2)
(1,2,3,4,5) (1,2)
R*S = (2,3,4,5)
S*R = (1,3,4,5)

R*S

(2,3,4,5)

S*R

(1,3,4,5)

R.matrix()

[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[1 0 0 0 0]

S.matrix()

[0 1 0 0 0]
[1 0 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]

(R*S).matrix()

[1 0 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 1 0 0 0]

(R.matrix())*(S.matrix())

[1 0 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 1 0 0 0]

Permutation statistics

G=SymmetricGroup(5)
R = G((1,2,3,4,5))
print(R)

(1,2,3,4,5)

R.matrix()

[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[1 0 0 0 0]

R.inversions()

[(1,2), (1,3), (1,4), (1,5)]

R.inversions?

(1,2)

S.matrix()

[0 1]
[1 0]

(S*R).inversions()

[(1,2), (1,3), (2,3), (1,4), (1,5)]

(S*R).matrix()

[0 0 1 0 0]
[0 1 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[1 0 0 0 0]

# How many inversions?
from collections import Counter
G=SymmetricGroup(5)
numinvlist = [Permutation(g).number_of_inversions() for g in G]
print(numinvlist)
co=Counter(numinvlist)
print(sorted(co.items()))
list_plot(co).show()
# Check that there are 60 even permutations
print(add([co[_] for _ in range(0,12,2)]))
#What permutation has 10 inversions?

[0, 4, 1, 6, 6, 3, 7, 4, 7, 5, 4, 8, 5, 6, 2, 3, 7, 4, 3, 5, 1, 5, 2, 7, 5, 4, 8, 5, 6, 6, 3, 7, 4, 7, 3, 4, 8, 5, 4, 6, 2, 6, 3, 8, 6, 5, 9, 6, 7, 3, 4, 8, 5, 4, 4, 1, 5, 2, 5, 7, 1, 5, 2, 7, 7, 4, 8, 5, 8, 4, 5, 9, 6, 5, 3, 2, 6, 3, 4, 6, 2, 6, 3, 8, 4, 5, 9, 6, 5, 5, 2, 6, 3, 6, 4, 3, 7, 4, 5, 7, 3, 7, 4, 9, 5, 6, 10, 7, 6, 4, 3, 7, 4, 5, 5, 2, 6, 3, 6, 8]
[(0, 1), (1, 4), (2, 9), (3, 15), (4, 20), (5, 22), (6, 20), (7, 15), (8, 9), (9, 4), (10, 1)]

Exercise partition statistics

For n from 2 to 20, say, plot the function "number of perms in S_n with k inversions"
Formulate some hypothesis
Do the same but for the number of descents
Do the same but for the number of peaks
Is there a correlation between these three statistics? How would you check that?


RP = Permutation((1,2,3),(4,5))
print(RP.descents())
print(RP.peaks())
print(RP.number_of_descents(), RP.number_of_peaks())

[2]
[1]
1 1

Groups of symmetries

P = polygon2d([(cos(2*pi*k/6),sin(2*pi*k/6)) for k in range(6)])
P

# Define D6 as subgroup of S6
S6 = SymmetricGroup(6)
r = S6((1,2,3,4,5,6))
s = S6(((2,6),(3,5)))
print(r,s)
D6 = PermutationGroup([r,s])
print(D6)
print()
print(D6.order())
print()
for g in D6:
    print(g)
print()
# conjugacy classes
# Conjugace classes in D6
for clr in D6.conjugacy_classes_representatives():
    cl = ConjugacyClass(D6,clr)
    cll = cl.list()  
    print(cll)

(1,2,3,4,5,6) (2,6)(3,5)
Permutation Group with generators [(2,6)(3,5), (1,2,3,4,5,6)]

12

()
(1,5,3)(2,6,4)
(1,3,5)(2,4,6)
(1,6,5,4,3,2)
(1,4)(2,5)(3,6)
(1,2,3,4,5,6)
(2,6)(3,5)
(1,5)(2,4)
(1,3)(4,6)
(1,6)(2,5)(3,4)
(1,4)(2,3)(5,6)
(1,2)(3,6)(4,5)

[()]
[(2,6)(3,5), (1,5)(2,4), (1,3)(4,6)]
[(1,2)(3,6)(4,5), (1,6)(2,5)(3,4), (1,4)(2,3)(5,6)]
[(1,2,3,4,5,6), (1,6,5,4,3,2)]
[(1,3,5)(2,4,6), (1,5,3)(2,6,4)]
[(1,4)(2,5)(3,6)]

D6el = [r^k for k in range(6)] + [s*r^k for k in range(6)]
D6na = ["r^" + str(k) for k in range(6)] + ["sr^" + str(k) for k in range(6)]
print(D6el,D6na)
D6.multiplication_table(elements=D6el,names=D6na)

[(), (1,2,3,4,5,6), (1,3,5)(2,4,6), (1,4)(2,5)(3,6), (1,5,3)(2,6,4), (1,6,5,4,3,2), (2,6)(3,5), (1,2)(3,6)(4,5), (1,3)(4,6), (1,4)(2,3)(5,6), (1,5)(2,4), (1,6)(2,5)(3,4)] ['r^0', 'r^1', 'r^2', 'r^3', 'r^4', 'r^5', 'sr^0', 'sr^1', 'sr^2', 'sr^3', 'sr^4', 'sr^5']

   *   r^0  r^1  r^2  r^3  r^4  r^5 sr^0 sr^1 sr^2 sr^3 sr^4 sr^5
    +------------------------------------------------------------
 r^0|  r^0  r^1  r^2  r^3  r^4  r^5 sr^0 sr^1 sr^2 sr^3 sr^4 sr^5
 r^1|  r^1  r^2  r^3  r^4  r^5  r^0 sr^5 sr^0 sr^1 sr^2 sr^3 sr^4
 r^2|  r^2  r^3  r^4  r^5  r^0  r^1 sr^4 sr^5 sr^0 sr^1 sr^2 sr^3
 r^3|  r^3  r^4  r^5  r^0  r^1  r^2 sr^3 sr^4 sr^5 sr^0 sr^1 sr^2
 r^4|  r^4  r^5  r^0  r^1  r^2  r^3 sr^2 sr^3 sr^4 sr^5 sr^0 sr^1
 r^5|  r^5  r^0  r^1  r^2  r^3  r^4 sr^1 sr^2 sr^3 sr^4 sr^5 sr^0
sr^0| sr^0 sr^1 sr^2 sr^3 sr^4 sr^5  r^0  r^1  r^2  r^3  r^4  r^5
sr^1| sr^1 sr^2 sr^3 sr^4 sr^5 sr^0  r^5  r^0  r^1  r^2  r^3  r^4
sr^2| sr^2 sr^3 sr^4 sr^5 sr^0 sr^1  r^4  r^5  r^0  r^1  r^2  r^3
sr^3| sr^3 sr^4 sr^5 sr^0 sr^1 sr^2  r^3  r^4  r^5  r^0  r^1  r^2
sr^4| sr^4 sr^5 sr^0 sr^1 sr^2 sr^3  r^2  r^3  r^4  r^5  r^0  r^1
sr^5| sr^5 sr^0 sr^1 sr^2 sr^3 sr^4  r^1  r^2  r^3  r^4  r^5  r^0

Exercise D6

Show that all elements can be written as r^k or sr^k
What is the element sr^k geometrically
What is r^ksr^m for 0 <= k,m <= 6 ?
Describe the conjugacy classes, name elements r^k or sr^k or describe them geometrically

Exercise D7

Same as for D6

Exercise 5c

# Describe the rigid symmetry group and the full symmetry group
# of the cube, and describe their  conjugacy classes, use the below for hints

P = polytopes.cube()
P.plot()

G= P.restricted_automorphism_group()

G= P.restricted_automorphism_group?

G.order()

G.an_element()

(1,3)(2,4)(5,7)(6,8)

g.parent()

Permutation Group with generators [(3,7)(4,6), (2,4)(5,7), (1,2)(3,4)(5,8)(6,7), (1,8)(2,3,4,5,6,7)]

for g in G:
    print(g,order(g))

() 1
(1,7)(2,6)(3,5)(4,8) 2
(1,3)(2,4)(5,7)(6,8) 2
(1,5)(2,8)(3,7)(4,6) 2
(1,2)(3,4)(5,8)(6,7) 2
(1,6)(2,7)(3,8)(4,5) 2
(1,4)(2,3)(5,6)(7,8) 2
(1,8)(2,5)(3,6)(4,7) 2
(2,6,4)(3,7,5) 3
(1,7,3)(4,6,8) 3
(1,3,5)(2,8,6) 3
(1,5,7)(2,4,8) 3
(1,2,7,8,5,4)(3,6) 6
(1,6,5,8,3,2)(4,7) 6
(1,4,3,8,7,6)(2,5) 6
(1,8)(2,3,4,5,6,7) 6
(2,4,6)(3,5,7) 3
(1,7,5)(2,8,4) 3
(1,3,7)(4,8,6) 3
(1,5,3)(2,6,8) 3
(1,2,3,8,5,6)(4,7) 6
(1,6,7,8,3,4)(2,5) 6
(1,4,5,8,7,2)(3,6) 6
(1,8)(2,7,6,5,4,3) 6
(3,7)(4,6) 2
(1,7,5,3)(2,6,8,4) 4
(1,3,5,7)(2,4,8,6) 4
(1,5)(2,8) 2
(1,2)(3,6)(4,7)(5,8) 2
(1,6,5,4)(2,7,8,3) 4
(1,4,5,6)(2,3,8,7) 4
(1,8)(2,5)(3,4)(6,7) 2
(2,6)(3,5) 2
(1,7)(4,8) 2
(1,3,7,5)(2,8,6,4) 4
(1,5,7,3)(2,4,6,8) 4
(1,2,7,6)(3,8,5,4) 4
(1,6,7,2)(3,4,5,8) 4
(1,4)(2,5)(3,6)(7,8) 2
(1,8)(2,3)(4,7)(5,6) 2
(2,4)(5,7) 2
(1,7,3,5)(2,8,4,6) 4
(1,3)(6,8) 2
(1,5,3,7)(2,6,4,8) 4
(1,2,3,4)(5,6,7,8) 4
(1,6)(2,5)(3,8)(4,7) 2
(1,4,3,2)(5,8,7,6) 4
(1,8)(2,7)(3,6)(4,5) 2

G.conjugacy_classes_representatives()

[(),
 (3,7)(4,6),
 (2,4,6)(3,5,7),
 (1,2)(3,4)(5,8)(6,7),
 (1,2)(3,6)(4,7)(5,8),
 (1,2,3,4)(5,6,7,8),
 (1,2,3,8,5,6)(4,7),
 (1,3)(2,4)(5,7)(6,8),
 (1,3,5,7)(2,4,8,6),
 (1,8)(2,5)(3,6)(4,7)]

# We do it ourselves:
## Rigid symmetries
QT1 = [(1,2,3,4),(5,6,7,8)]
QT2 = [(1,4,8,5),(2,3,7,6)]
QT3 = [(1,5,6,2),(4,8,7,3)]

antipode = [(1,7),(2,8),(3,5),(4,6)]
FullCube = PermutationGroup([QT1,QT2,QT3,antipode])
RigidCube=FullCube.subgroup([QT1,QT2,QT3])
print(FullCube.order(),RigidCube.order())

48 24

for g in RigidCube:
    print(g,g.order())

print()
print()

for g in FullCube:
    if not g in RigidCube:
        print(g,g.order())

() 1
(1,3)(2,4)(5,7)(6,8) 2
(1,6)(2,5)(3,8)(4,7) 2
(1,8)(2,7)(3,6)(4,5) 2
(1,4,3,2)(5,8,7,6) 4
(1,2,3,4)(5,6,7,8) 4
(1,5)(2,8)(3,7)(4,6) 2
(1,7)(2,6)(3,5)(4,8) 2
(2,5,4)(3,6,8) 3
(1,3,8)(2,7,5) 3
(1,6,3)(4,5,7) 3
(1,8,6)(2,4,7) 3
(1,4)(2,8)(3,5)(6,7) 2
(1,2,6,5)(3,7,8,4) 4
(1,5,6,2)(3,4,8,7) 4
(1,7)(2,3)(4,6)(5,8) 2
(2,4,5)(3,8,6) 3
(1,3,6)(4,7,5) 3
(1,6,8)(2,7,4) 3
(1,8,3)(2,5,7) 3
(1,4,8,5)(2,3,7,6) 4
(1,2)(3,5)(4,6)(7,8) 2
(1,5,8,4)(2,6,7,3) 4
(1,7)(2,8)(3,4)(5,6) 2


(3,6)(4,5) 2
(1,3,8,6)(2,4,7,5) 4
(1,6,8,3)(2,5,7,4) 4
(1,8)(2,7) 2
(1,4,8,7,6,2)(3,5) 6
(1,2,3,7,8,5)(4,6) 6
(1,5,6,7,3,4)(2,8) 6
(1,7)(2,6,5,8,4,3) 6
(2,5)(3,8) 2
(1,3,6,8)(2,7,5,4) 4
(1,6)(4,7) 2
(1,8,6,3)(2,4,5,7) 4
(1,4,3,7,6,5)(2,8) 6
(1,2,6,7,8,4)(3,5) 6
(1,5,8,7,3,2)(4,6) 6
(1,7)(2,3,4,8,5,6) 6
(2,4)(6,8) 2
(1,3)(5,7) 2
(1,6,3,8)(2,7,4,5) 4
(1,8,3,6)(2,5,4,7) 4
(1,4)(2,3)(5,8)(6,7) 2
(1,2)(3,4)(5,6)(7,8) 2
(1,5)(2,6)(3,7)(4,8) 2
(1,7)(2,8)(3,5)(4,6) 2

FullCube.structure_description()

'C2 x S4'

RigidCube.structure_description()

'S4'

Exercise Symmetry of cube

Describe all symmetries of the cube geometrically
Describe the conjugacy classes of the full symmetry group and of the rigid symmetry group

Exercise Symmetry of dodecaedron

How many elements are there in the full symmetry group of the dodecahedron?
What are their orders; i.e. how many elements are there of order two, of order 3, et cetera
Compare with a well-known group with the same number of elements

DOD = polytopes.dodecahedron()
DOD.plot()

GDODF = DOD.restricted_automorphism_group()

Automorphism groups of graphs

# Define an undirected graph, vertices labeled 1 to n
# Compute automorphism group: bijections on vertices that preserve edges
n=5
ve=[k for k in (1..n)]
ed=[[k,k+1] for k in (1..(n-1))]
LG = Graph([ve,ed])

LG

GLG = LG.automorphism_group()
GLG

Permutation Group with generators [(1,5)(2,4)]

list(GLG)

[(), (1,5)(2,4)]

Exercise automorphism group of linegraph

Find (guess) the automorphism group of the line graph, for all n

# Define an undirected graph (cycle graph), vertices labeled 1 to n
# Compute automorphism group: bijections on vertices that preserve edges
n=5
ve=[k for k in (1..n)]
ed=[[k,k+1] for k in (1..(n-1))] + [[1,n]]

CG = Graph([ve,ed])
CG.show()
GCG = CG.automorphism_group()
list(GCG)

[(),
 (1,5,4,3,2),
 (1,4,2,5,3),
 (1,3,5,2,4),
 (1,2,3,4,5),
 (2,5)(3,4),
 (1,5)(2,4),
 (1,4)(2,3),
 (1,3)(4,5),
 (1,2)(3,5)]

Exercise automorphism group of cyclegraph

Find (guess) the automorphism group of the cycle graph, for all n

Exercise automorphism group of complete graphs

Find (guess) the automorphism group of the complete graph
Find (guess) the automorphism group of the complete bipartite graph

Exercise automorphism group of trees

Find (guess) the automorphism group of a complete binary tree
Find (guess) the automorphism group of a tree

Cayley graphs of groups

# Define a group G and a set of S of generators
# S should not contain the identity, but both g and g^{-1}
S6 = SymmetricGroup(6)
r = S6((1,2,3,4,5,6))
s = S6(((2,6),(3,5)))

D6 = PermutationGroup([r,s])
G = D6
S=[r,s,r^(-1),s^(-1)]

G.cayley_graph?

GCG=G.cayley_graph(generators=S)
GCG

GCG.show3d(color_by_label=True, edge_size=0.01, edge_size2=0.02, vertex_size=0.03)

Exercise Cayley graph

Let G be Sn and S the set of adjacent transpositions
What is the Cayley graph?
How many vertices in the Cayley graph are at distance k from the identity?

Cycle graphs

def circulae(L):
    n=len(L)
    return [L[j:j+2] for j in range(n-1)] + [[L[-1],L[0]]]

def circulaf(L,j):
    li = circulae(L)
    return [v+[j] for v in li]

def GraphOfCycles(G):
    
    CYCLES = []
    for g in G:
        c = g.powers(g.order())
        CYCLES.append(Set(c))

    SC = Set(CYCLES)
    REDUNDANT = []
    for A in SC:
        for B in SC:
            if A.issubset(B) and A.cardinality() < B.cardinality():
                REDUNDANT.append(A)
                    
    SR = Set(REDUNDANT)
    IRRCYC = SC.difference(SR)
    VERT = G.list()
    EDG = []
    for s in IRRCYC:
        EDG= EDG + circulae(s)

    return Graph([VERT,EDG])


        
def Cdirprod(L):
    G = CyclicPermutationGroup(1)
    for b in L:
        H = CyclicPermutationGroup(b)
        G = G.direct_product(H)[0]
    return G

GraphOfCycles(Cdirprod([5,5])).show3d()
GraphOfCycles(Cdirprod([4,5])).show3d()
GraphOfCycles(SymmetricGroup(3)).show3d()

Exercise graphofcycles

Explain what the above code does
Predict what kind of graph the dihedral groups would yield
Verify your prediction

Part 3: extra

Solving linear recurence equations

def a(n):
    if (n == 0):
        return 3
    else:
        return 2*a(n-1)-1

[a(n) for n in (1..10)]

[5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049]

var('n')
from sympy import Function, rsolve
from sympy.abc import n
y = Function('y')
f = y(n+1) - 2*y(n)  + 1
soln =rsolve(f, y(n),{y(0):3})
soln

[2*2^k+1 for k in (1..10)]

[5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049]

def b(n):
    if (n == 0):
        return 3
    else:
        return b(n-1) + 7

[b(n) for n in (1..10)]

[10, 17, 24, 31, 38, 45, 52, 59, 66, 73]

rsolve(y(n+1)-y(n)-7,y(n),{y(0):3})

def c(m,n):
    if (m == 1 and n == 1):
        return 3
    elif (m > 1):
        return c(m-1,n) + 3
    elif (n > 1):
        return c(m,n-1) + 13

Cmat = matrix(QQ,15,15,lambda m,n: c(m+1,n+1))
Cmat

[  3  16  29  42  55  68  81  94 107 120 133 146 159 172 185]
[  6  19  32  45  58  71  84  97 110 123 136 149 162 175 188]
[  9  22  35  48  61  74  87 100 113 126 139 152 165 178 191]
[ 12  25  38  51  64  77  90 103 116 129 142 155 168 181 194]
[ 15  28  41  54  67  80  93 106 119 132 145 158 171 184 197]
[ 18  31  44  57  70  83  96 109 122 135 148 161 174 187 200]
[ 21  34  47  60  73  86  99 112 125 138 151 164 177 190 203]
[ 24  37  50  63  76  89 102 115 128 141 154 167 180 193 206]
[ 27  40  53  66  79  92 105 118 131 144 157 170 183 196 209]
[ 30  43  56  69  82  95 108 121 134 147 160 173 186 199 212]
[ 33  46  59  72  85  98 111 124 137 150 163 176 189 202 215]
[ 36  49  62  75  88 101 114 127 140 153 166 179 192 205 218]
[ 39  52  65  78  91 104 117 130 143 156 169 182 195 208 221]
[ 42  55  68  81  94 107 120 133 146 159 172 185 198 211 224]
[ 45  58  71  84  97 110 123 136 149 162 175 188 201 214 227]

Cmat.plot()

row1 = [c(1,n) for n in range(1,12)]
print(row1)
row2 = [c(2,n) for n in range(1,12)]
print(row2)
row3 = [c(3,n) for n in range(1,12)]
print(row3)
data1 = [(k,c(1,k)) for k in (1..12)]
print(data1)
data2 = [(k,c(2,k)) for k in (1..12)]
data3 = [(k,c(3,k)) for k in (1..12)]

[3, 16, 29, 42, 55, 68, 81, 94, 107, 120, 133]
[6, 19, 32, 45, 58, 71, 84, 97, 110, 123, 136]
[9, 22, 35, 48, 61, 74, 87, 100, 113, 126, 139]
[(1, 3), (2, 16), (3, 29), (4, 42), (5, 55), (6, 68), (7, 81), (8, 94), (9, 107), (10, 120), (11, 133), (12, 146)]

var('k')

var('a, b, c, x')
model(x) = a*x^2 + b*x + c
sol1 = find_fit(data1,model)
sol1

[a == (-2.180410926299907e-12),
 b == 13.00000000002623,
 c == -10.00000000005758]


sol2 = find_fit(data2,model)
sol2

[a == (-2.180410924629807e-12),
 b == 13.000000000026231,
 c == -7.000000000057584]

sol3 = find_fit(data3,model)
sol3

[a == (-2.1802559757588824e-12),
 b == 13.000000000028342,
 c == -4.000000000066126]