# 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
)

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
)

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
```