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.