Landau’s function

A few weeks ago, when I was writing about the general group-theoretical version of the Elgamal cryptosystem, I was led to try to find elements of the symmetric group S_n with maximum possible orders. Given that any e\in S_n can be written as disjoint cycles, and given that the order of any cycle is its length, the order of e is the lowest common multiple of the lengths of its cycles. Since a set of cycle lengths may be considered as an integer partition of n, the maximum possible order will be the maximum lcm of all partitions p of n.

For any n let g(n) be the largest order of elements of S_n. It turns out that this function is quite well known, and is called Landau’s function, after Edmund Landau, who first investigated it. Some values are given in the OEIS as sequence number 793.

It can be calculated for small values of n by a brute force approach:

def landau(n):
    p=Partitions(n)
    return max([lcm(i) for i in p])

A somewhat more elegant approach uses the fact that the largest prime factor p of g(n) satisfies

p<1.328\sqrt{n\ln(n)}

and has been coded in Python by David Radcliffe and can be seen here. David’s insight was to use dynamic programming, as he explains in his comments:

We compute Landau’s function using dynamic programming, by adding one prime at a time. Let L(N,k) be the maximum order of a permutation in S_N, subject to the constraint that all cycle lengths are powers of the first k primes. Then L(N,k+1) = \max q*L(N-q,k), where q ranges through all powers of the (k+1)-st prime up to N. We stop when all possible prime factors have been exhausted.

Taking the heart of David’s program for use in Sage produces:

def gpf(N):
    return int(1.328 * (N*log(N))**0.5) + 1

def landau(N):
    g=gpf(N)
    sieve = [True]*(g+1)
    prime = []
    for n in xrange(2,g+1):
        if sieve[n]:
            prime.append(n)
            if n^2 <= N:
                for m in xrange(n^2,g+1,n):
                    sieve[m] = False
    landau_vals = [1]*(N+1)
    for p in prime:
        for n in xrange(N,1,-1):
            q = p
            while q <= n:
                newval = q * landau_vals[n-q]
                if newval > landau_vals[n]:
                    landau_vals[n] = newval
                q *= p
    return landau_vals[N]

This is very fast:

sage: landau(2000)
  5301036508850487626975427714489912082038158551922510400

The first brute force method would most definitely not be suitable here:

sage: p=Partitions(2000)
sage: p.cardinality()
  4720819175619413888601432406799959512200344166
About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 45 other followers

%d bloggers like this: