Essays/Landau's Function

From J Wiki
Jump to: navigation, search

Landau's function g n on non-negative integer n is the maximal order of an element of S,,n,,, the largest size of a subgroup generated by a permutation of order n .


Partitions

A partition of n is an integer vector v of positive integers such that n=+/v . If a permutation has cycles with lengths v then the order of the permutation is *./v , the LCM of the cycle lengths. Therefore, g n is >./ *./&> part n . 

part is from the partitions essay.

part =: 3 : 'final (, new)^:y <<i.1 0'
new  =: (-i.)@# <@:(cat&.>) ]
cat  =: [ ;@:(,.&.>) -@(<.#) {. ]
final=: ; @: (<@-.&0"1&.>) @ > @ {:

   part 7
┌─┬───┬───┬─────┬───┬─────┬───────┬─────┬─────┬───────┬─────────┬───────┬─────────┬───────────┬─────────────┐
│7│6 1│5 2│5 1 1│4 3│4 2 1│4 1 1 1│3 3 1│3 2 2│3 2 1 1│3 1 1 1 1│2 2 2 1│2 2 1 1 1│2 1 1 1 1 1│1 1 1 1 1 1 1│
└─┴───┴───┴─────┴───┴─────┴───────┴─────┴─────┴───────┴─────────┴───────┴─────────┴───────────┴─────────────┘

   *./&> part 7
7 6 10 5 12 4 4 3 6 6 3 2 2 2 1

   >./ *./&> part 7
12

Given the lengths, it is straightforward to derive a permutation having those cycle lengths.

   v=: 4 3
   ((# i.@#) v) </. i.+/v
┌───────┬─────┐
│0 1 2 3│4 5 6│
└───────┴─────┘
   ] p=: C. ((# i.@#) v) </. i.+/v
1 2 3 0 5 6 4
   # ~. {/\ (*./v)#,:p
12
   {/ (*./v)#,:p
0 1 2 3 4 5 6

Landau's Function

Partitions are not an efficient means for computing g . For example, there are 458004788008144308553622 partitions of 600 . A more efficient computation derives by observing that:

  • The maximal order obtains with lengths that are relatively prime; moreover, with lengths that are prime powers.
  • The largest prime dividing g n is bounded by 1.328 * %: n*^.n Grantham, 1995.
pv=: i.&.(_1&p:) @ >. @ (1.328&*) @ %: @ (*^.)  NB. Grantham 1995

plists=: 3 : 0  NB. prime lists  y>:+/&>p
 p=. pv 4>.y
 m=. - (5<.#p) >. y (<i.1:) *:p
 r=. m}.p
 s=. m{.p
 b=. #:i.2^#s
 (<r) ,&.> s <@#~ b #~ (y-+/r) >: b +/ .*s
)

adj=: 4 : 0
 d=. x-+/y
 t=. y #~ d>:y*y-1
 k=. 1>.<.t^.1>.d
 e=. t^"1 >:(#: i.@(*/)) k+d>:(t^1+k)-t
 e=. e #~ (x-+/(#t)}.y)>:+/"1 e
 x: (e {~ (i.>./) */"1 e), (#t)}.y
)

g=: >./ @ (*/@adj&> plists) " 0

<!> Note: For n>814 , it is not known whether g n gives the maximal order. The result should be considered a lower bound on the maximal order rather than the actual maximal order.

   g 600
471499293064816023352745400

   g i.20
1 1 2 3 4 6 6 12 15 20 30 30 60 60 84 105 140 210 210 420
   >./@(*./&>"_)@part"0 i.20
1 1 2 3 4 6 6 12 15 20 30 30 60 60 84 105 140 210 210 420

Given the maximal order g n , it is straightforward to compute the lengths that give rise to that order:

   lfg=: *//.~@q:  NB. lengths from g

   g 600
471499293064816023352745400
   lfg g 600
8 9 25 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
   *./ lfg g 600
471499293064816023352745400

Collected Definitions

part =: 3 : 'final (, new)^:y <<i.1 0'
new  =: (-i.)@# <@:(cat&.>) ]
cat  =: [ ;@:(,.&.>) -@(<.#) {. ]
final=: ; @: (<@-.&0"1&.>) @ > @ {:

pv=: i.&.(_1&p:) @ >. @ (1.328&*) @ %: @ (*^.)  NB. Grantham 1995

plists=: 3 : 0  NB. prime lists  y>:+/&>p
 p=. pv 4>.y
 m=. - (5<.#p) >. y (<i.1:) *:p
 r=. m}.p
 s=. m{.p
 b=. #:i.2^#s
 (<r) ,&.> s <@#~ b #~ (y-+/r) >: b +/ .*s
)

adj=: 4 : 0
 d=. x-+/y
 t=. y #~ d>:y*y-1
 k=. 1>.<.t^.1>.d
 e=. t^"1 >:(#: i.@(*/)) k+d>:(t^1+k)-t
 e=. e #~ (x-+/(#t)}.y)>:+/"1 e
 x: (e {~ (i.>./) */"1 e), (#t)}.y
)

g=: >./ @ (*/@adj&> plists) " 0

lfg=: *//.~@q:  NB. lengths from g



See also



Contributed by Roger Hui.