Differences between revisions 10 and 11
 ⇤ ← Revision 10 as of 2007-11-14 14:34:23 → Size: 4701 Editor: RogerHui Comment: ← Revision 11 as of 2008-12-08 10:45:31 → ⇥ Size: 4628 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 8: Line 8: [[TableOfContents(2)]] <> Line 17: Line 17: `part `is from the [:../Partitions:partitions essay]. `part `is from the [[../Partitions|partitions essay]]. Line 60: Line 60: * The largest prime dividing` g n `is bounded by` 1.328 * %: n*^.n ` [http://www.pseudoprime.com/landau.pdf Grantham], 1995. * The largest prime dividing` g n `is bounded by` 1.328 * %: n*^.n ` [[http://www.pseudoprime.com/landau.pdf|Grantham]], 1995. Line 147: Line 147: [[BR]] <
> Line 150: Line 150: * [http://mathworld.wolfram.com/LandausFunction.html MathWorld] * [http://www.research.att.com/~njas/sequences/A000793 On-line Encyclopedia of Integer Sequences A000793] * [http://en.wikipedia.org/wiki/Landau%27s_function Wikipedia] * [[MathWorld:LandausFunction|MathWorld]] * [[OEIS:A000793|On-line Encyclopedia of Integer Sequences A000793]] * [[WikiPedia:Landau%27s_function|Wikipedia]] Line 154: Line 154: [[BR]] <
>

Landau's function g n on non-negative integer n is the maximal order of an element of Sn, 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```