Essays/Landau's Function
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.