API tools faq
paste
Guest User

Finite non-abelian simple groups

a guest
May 15th, 2016
106
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 9.83 KB | None | 0 0
raw download clone embed print report
  1. ###
  2. # General packages and algorithms
  3. ###
  4. import sympy as sp
  5. import math as ma
  6. import time
  7. from functools import reduce
  8. from operator import mul
  9.  
  10. # Quickly calculcate the product of elements in a list
  11. def prod(L):
  12.     return reduce(mul, L, 1)
  13.  
  14. # Check if 4|G|+1 is a perfect square
  15. def hasRequiredOrder(x,name='Unidentified group'):
  16.     if isSquare(4*x+1):
  17.         print(name+' of order '+str(x))
  18.     return
  19.  
  20. # Check if integer is a perfect square
  21. def isSquare(n):
  22.     return n == int(ma.sqrt(n)) ** 2
  23.  
  24. # Generate all prime powers <= m
  25. def primePowerRange(N):
  26.     L = []
  27.     for p in sp.primerange(2,N+1):
  28.         Lp = [p]
  29.         m = ma.floor(ma.log(N,p))
  30.         for _ in range(2,m+1):
  31.             Lp += [Lp[-1]*p]
  32.         L += Lp
  33.     return sorted(L)
  34.  
  35. ###
  36. # Generate orders of non-abelian simple groups
  37. ###
  38.  
  39. # Alternating groups
  40. def alternatingOrders(m):
  41.     # A_n
  42.     n = 5
  43.     O = 120
  44.     while O <= m:
  45.         hasRequiredOrder(O,'Alternating group A('+str(n)+')')
  46.         n += 1
  47.         O *= n
  48.     return
  49.  
  50. # Classical Chevalley groups
  51. def classicalChevalleyOrders(m):
  52.     # A_n(q)
  53.     n = 1
  54.     i = 2
  55.     # Starting at i=2 avoids A_1(2) and A_1(3)
  56.     q = primePowers[i]
  57.     O = (sp.Pow(q,(n*(n+1))//2)*prod([sp.Pow(q,i+1)-1 for i in range(1,n+1)]))//ma.gcd(n+1,q-1)
  58.     while O <= m:
  59.         while O <= m:
  60.             hasRequiredOrder(O,'Classical Chevalley group A_'+str(n)+'('+str(q)+')')
  61.             i += 1
  62.             q = primePowers[i]
  63.             O = (sp.Pow(q,(n*(n+1))//2)*prod([sp.Pow(q,i+1)-1 for i in range(1,n+1)]))//ma.gcd(n+1,q-1)
  64.         i = 0
  65.         q = primePowers[i]
  66.         n += 1
  67.         O = (sp.Pow(q,(n*(n+1))//2)*prod([sp.Pow(q,i+1)-1 for i in range(1,n+1)]))//ma.gcd(n+1,q-1)
  68.     # B_n(q)
  69.     n = 2
  70.     i = 1
  71.     # starting at i=1 avoids B_2(2)
  72.     q = primePowers[i]
  73.     O = (sp.Pow(q,n*n)*prod([sp.Pow(q,2*i)-1 for i in range(1,n+1)]))//ma.gcd(2,q-1)
  74.     while O <= m:
  75.         while O <= m:
  76.             hasRequiredOrder(O,'Classical Chevalley group B_'+str(n)+'('+str(q)+')')
  77.             i += 1
  78.             q = primePowers[i]
  79.             O = (sp.Pow(q,n*n)*prod([sp.Pow(q,2*i)-1 for i in range(1,n+1)]))//ma.gcd(2,q-1)
  80.         i = 0
  81.         q = primePowers[i]
  82.         n += 1
  83.         O = (sp.Pow(q,n*n)*prod([sp.Pow(q,2*i)-1 for i in range(1,n+1)]))//ma.gcd(2,q-1)
  84.     # C_n(q) is obsolete, same order as B_n(q)
  85.     # D_n(q)
  86.     n = 4
  87.     i = 0
  88.     q = primePowers[i]
  89.     O = (sp.Pow(q,n*(n-1))*(sp.Pow(q,n)-1)*prod([sp.Pow(q,2*i)-1 for i in range(1,n)]))//ma.gcd(4,q**n-1)
  90.     while O <= m:
  91.         while O <= m:
  92.             hasRequiredOrder(O,'Classical Chevalley group B_'+str(n)+'('+str(q)+')')
  93.             i += 1
  94.             q = primePowers[i]
  95.             O = (sp.Pow(q,n*(n-1))*(sp.Pow(q,n)-1)*prod([sp.Pow(q,2*i)-1 for i in range(1,n)]))//ma.gcd(4,q**n-1)
  96.         i = 0
  97.         q = primePowers[i]
  98.         n += 1
  99.         O = (sp.Pow(q,n*(n-1))*(sp.Pow(q,n)-1)*prod([sp.Pow(q,2*i)-1 for i in range(1,n)]))//ma.gcd(4,q**n-1)
  100.     return
  101.  
  102. # Exceptional Chevalley groups
  103. def exceptionalChevalleyOrders(m):
  104.     # E_6(q)
  105.     i = 0
  106.     q = primePowers[i]
  107.     O = (sp.Pow(q,36)*prod([sp.Pow(q,i)-1 for i in [2,5,6,8,9,12]]))//ma.gcd(3,q-1)
  108.     while O<=m:
  109.         hasRequiredOrder(O,'Exceptional Chevalley group E_6('+str(q)+')')
  110.         i += 1
  111.         q = primePowers[i]
  112.         O = (sp.Pow(q,36)*prod([sp.Pow(q,i)-1 for i in [2,5,6,8,9,12]]))//ma.gcd(3,q-1)
  113.     # E_7(q)
  114.     i = 0
  115.     q = primePowers[i]
  116.     O = (sp.Pow(q,63)*prod([sp.Pow(q,i)-1 for i in [2,6,8,10,12,14,18]]))//ma.gcd(2,q-1)
  117.     while O<=m:
  118.         hasRequiredOrder(O,'Exceptional Chevalley group E_7('+str(q)+')')
  119.         i += 1
  120.         q = primePowers[i]
  121.         O = (sp.Pow(q,63)*prod([sp.Pow(q,i)-1 for i in [2,6,8,10,12,14,18]]))//ma.gcd(2,q-1)
  122.     # E_8(q)
  123.     i = 0
  124.     q = primePowers[i]
  125.     O = sp.Pow(q,120)*prod([sp.Pow(q,i)-1 for i in [2,8,12,14,18,20,24,30]])
  126.     while O<=m:
  127.         hasRequiredOrder(O,'Exceptional Chevalley group E_8('+str(q)+')')
  128.         i += 1
  129.         q = primePowers[i]
  130.         O = sp.Pow(q,120)*prod([sp.Pow(q,i)-1 for i in [2,8,12,14,18,20,24,30]])
  131.     # F_4(q)
  132.     i = 0
  133.     q = primePowers[i]
  134.     O = sp.Pow(q,24)*prod([sp.Pow(q,i)-1 for i in [2,6,8,12]])
  135.     while O<=m:
  136.         hasRequiredOrder(O,'Exceptional Chevalley group F_4('+str(q)+')')
  137.         i += 1
  138.         q = primePowers[i]
  139.         O = sp.Pow(q,24)*prod([sp.Pow(q,i)-1 for i in [2,6,8,12]])
  140.     # G_2(q)
  141.     i = 1
  142.     # starting at i=1 avoids G_2(2)
  143.     q = primePowers[i]
  144.     O = sp.Pow(q,6)*prod([sp.Pow(q,i)-1 for i in [2,6]])
  145.     while O<=m:
  146.         hasRequiredOrder(O,'Exceptional Chevalley group G_2('+str(q)+')')
  147.         i += 1
  148.         q = primePowers[i]
  149.         O = sp.Pow(q,6)*prod([sp.Pow(q,i)-1 for i in [2,6]])
  150.     return
  151.    
  152. # Classical Steinberg groups
  153. def classicalSteinbergOrders(m):
  154.     # 2A_n(q^2)
  155.     n = 2
  156.     i = 1
  157.     # Starting at i=1 avoids 2A_2(2^2)
  158.     q = primePowers[i]
  159.     O = (sp.Pow(q,(n*(n+1))//2)*prod([sp.Pow(q,i+1)-sp.Pow(-1,i+1) for i in range(1,n+1)]))//ma.gcd(n+1,q+1)
  160.     while O <= m:
  161.         while O <= m:
  162.             hasRequiredOrder(O,'Classical Steinberg group 2A_'+str(n)+'('+str(q)+'^2)')
  163.             i += 1
  164.             q = primePowers[i]
  165.             O = (sp.Pow(q,(n*(n+1))//2)*prod([sp.Pow(q,i+1)-sp.Pow(-1,i+1) for i in range(1,n+1)]))//ma.gcd(n+1,q+1)
  166.         i = 0
  167.         q = primePowers[i]
  168.         n += 1
  169.         O = (sp.Pow(q,(n*(n+1))//2)*prod([sp.Pow(q,i+1)-sp.Pow(-1,i+1) for i in range(1,n+1)]))//ma.gcd(n+1,q+1)
  170.     # 2D_n(q^2)
  171.     n = 4
  172.     i = 0
  173.     q = primePowers[i]
  174.     O = sp.Pow(q,n*(n-1))*(sp.Pow(q,n)+1)*prod([sp.Pow(q,2*i)-1 for i in range(1,n)])//ma.gcd(4,q**n+1)
  175.     while O <= m:
  176.         while O <= m:
  177.             hasRequiredOrder(O,'Classical Steinberg group 2D_'+str(n)+'('+str(q)+'^2)')
  178.             i += 1
  179.             q = primePowers[i]
  180.             O = sp.Pow(q,n*(n-1))*(sp.Pow(q,n)+1)*prod([sp.Pow(q,2*i)-1 for i in range(1,n)])//ma.gcd(4,q**n+1)
  181.         i = 0
  182.         q = primePowers[i]
  183.         n += 1
  184.         O = sp.Pow(q,n*(n-1))*(sp.Pow(q,n)+1)*prod([sp.Pow(q,2*i)-1 for i in range(1,n)])//ma.gcd(4,q**n+1)
  185.     return
  186.    
  187. def exceptionalSteinbergOrders(m):
  188.     # 2E_6(q^2)
  189.     i = 0
  190.     q = primePowers[i]
  191.     O = sp.Pow(q,36)*prod([sp.Pow(q,i)-sp.Pow(-1,i) for i in [2,5,6,8,9,12]])//ma.gcd(3,q+1)
  192.     while O<=m:
  193.         hasRequiredOrder(O,'Exceptional Steinberg group 2E_6('+str(q)+'^2)')
  194.         i += 1
  195.         q = primePowers[i]
  196.         O = sp.Pow(q,36)*prod([sp.Pow(q,i)-sp.Pow(-1,i) for i in [2,5,6,8,9,12]])//ma.gcd(3,q+1)
  197.     # 3D_4(q^3)
  198.     i = 0
  199.     q = primePowers[i]
  200.     O = sp.Pow(q,12)*(sp.Pow(q,8)+sp.Pow(q,4)+1)*(sp.Pow(q,6)-1)*(sp.Pow(q,2)-1)
  201.     while O<=m:
  202.         hasRequiredOrder(O,'Exceptional Steinberg group 3D_4('+str(q)+'^3)')
  203.         i += 1
  204.         q = primePowers[i]
  205.         O = sp.Pow(q,12)*(sp.Pow(q,8)+sp.Pow(q,4)+1)*(sp.Pow(q,6)-1)*(sp.Pow(q,2)-1)
  206.     return
  207.  
  208. def suzukiOrders(m):
  209.     # 2B_2(q)
  210.     n = 1
  211.     q = sp.Pow(2,2*n+1)
  212.     O = sp.Pow(q,2)*(sp.Pow(q,2)+1)*(q-1)
  213.     while O<=m:
  214.         hasRequiredOrder(O,'Suzuki group 2B_2('+str(q)+')')
  215.         n +=1
  216.         q = sp.Pow(2,2*n+1)
  217.         O = sp.Pow(q,2)*(sp.Pow(q,2)+1)*(q-1)
  218.     return
  219.    
  220. def reeTitsOrders(m):
  221.     #2F_4(q)
  222.     n = 1
  223.     q = sp.Pow(2,2*n+1)
  224.     O = sp.Pow(q,12)*(sp.Pow(q,6)+1)*(sp.Pow(q,4)-1)*(sp.Pow(q,3)+1)*(q-1)
  225.     while O<=m:
  226.         hasRequiredOrder(O,'Lee group 2F_4('+str(q)+')')
  227.         n +=1
  228.         q = sp.Pow(2,2*n+1)
  229.         O = sp.Pow(q,12)*(sp.Pow(q,6)+1)*(sp.Pow(q,4)-1)*(sp.Pow(q,3)+1)*(q-1)
  230.     return
  231.     #2F_4(2)' Tits
  232.     O = 17971200
  233.     if O <= m:
  234.         hasRequiredOrder(O,'Tits group 2F_4('+str(q)+')\'')
  235.     #2G_2(q)
  236.     n = 1
  237.     q = sp.Pow(3,2*n+1)
  238.     O = sp.Pow(q,3)*(sp.Pow(q,3)+1)*(q-1)
  239.     while O<=m:
  240.         hasRequiredOrder(O,'Lee group 2G_2('+str(q)+')')
  241.         n +=1
  242.         q = sp.Pow(3,2*n+1)
  243.         O = sp.Pow(q,3)*(sp.Pow(q,3)+1)*(q-1)
  244.     return
  245.  
  246. def sporadicOrders(m):
  247.     L = [7920,
  248.          95040,
  249.          443520,
  250.          10200960,
  251.          244823040,
  252.          175560,
  253.          604800,
  254.          50232960,
  255.          86775571046077562880,
  256.          495766656000,
  257.          42305421312000,
  258.          4157776806543360000,
  259.          64561751654400,
  260.          4089470473293004800,
  261.          1255205709190661721292800,
  262.          44352000,
  263.          898128000,
  264.          4030387200,
  265.          145926144000,
  266.          448345497600,
  267.          460815505920,
  268.          273030912000000,
  269.          51765179004000000,
  270.          90745943887872000,
  271.          4154781481226426191177580544000000,
  272.          808017424794512875886459904961710757005754368000000000
  273.          ]
  274.     for O in L:
  275.         if O <= m:
  276.             hasRequiredOrder(O,'Sporadic group')
  277.     return
  278.  
  279. def allOrders(m):
  280.     alternatingOrders(m)
  281.     classicalChevalleyOrders(m)
  282.     exceptionalChevalleyOrders(m)
  283.     classicalSteinbergOrders(m)
  284.     exceptionalSteinbergOrders(m)
  285.     suzukiOrders(m)
  286.     reeTitsOrders(m)
  287.     sporadicOrders(m)
  288.     return
  289.    
  290. begin = time.clock()
  291. n = 8
  292. primePowers = primePowerRange(10**n)
  293. print('Time to generate prime powers up to 10^'+str(n)+': '+str(sp.ceiling(time.clock()-begin))+' seconds.')
  294.  
  295. begin = time.clock()
  296. n = 23
  297. allOrders(10**n)
  298. print('Time to check all finite non-abelian simple groups up to order 10^'+str(n)+': '+str(sp.ceiling(time.clock()-begin))+' seconds.')
  299.  
  300. # for m >= 10**12: need 10^5 prime powers
  301. # for m >= 10**15: need 10^6 prime powers
  302. # for m >= 10**18: need 10^7 prime powers
  303. # for m >= 10**21: need 10^8 prime powers
  304.  
  305. # Powers up to 10^6: 6 seconds
  306. # Powers up to 10^7: 65 seconds
  307. # Powers up to 10^8: 676 seconds
  308.  
  309. # Groups up to 10^18: 7 seconds
  310. # Groups up to 10^19: 17 seconds
  311. # Groups up to 10^20: 34 seconds
  312. # Groups up to 10^21: 68 seconds
  313. # Groups up to 10^22: 139 seconds
  314. # Groups up to 10^23: 289 seconds
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!