open problem? divisors and antichains

[mriedel@xxxxxxxxxxxxx (Marko Riedel)]

Hi all,

I would like to pose the following problem, which may or may not have
been solved already.

The divisors of a positive integer n form a partially ordered set. Let
g(n) be the size of the largest antichain. Compute the asymptotic
expansion of the average order of g(n), i.e.


                                   n
                                  ====
                          1       \
                          -        >    g(k)
                          n       /
                                  ====
                                  k = 1

It looks like the first term may be 1/3 log n:


 2.8 ++-------+--------+--------+-------+--------+--------+--------+-------++
     +        +        +        +       +        +    AAA'/tmp/data'AAAAAAAAA
 2.6 ++                               AAAAAAAAAAAAAAAAA                    ++
     |                      AAAAAAAAAAAA                                    |
 2.4 ++             AAAAAAAAA                                              ++
     |          AAAAA                                                       |
 2.2 ++     AAAAA                                                          ++
     |    AAA                                                               |
   2 ++  AA                                                                ++
     | AAA                                                                  |
 1.8 ++A                                                                   ++
     |AA                                                                    |
 1.6 +A                                                                    ++
     |A                                                                     |
 1.4 AA                                                                    ++
     A                                                                      |
 1.2 A+                                                                    ++
     A                                                                      |
   1 A+                                                                    ++
     +        +        +        +       +        +        +        +        +
 0.8 ++-------+--------+--------+-------+--------+--------+--------+-------++
     0       500     1000     1500    2000     2500     3000     3500     4000


I have written a Perl program that computes this statistic. It outputs
the average order on STDOUT and the factorization shape and g(n) on
STDERR. Here it is:

#! /usr/bin/perl -w
#

sub fshape {
  my ($n) = @_;
  my @res;
  
  my ($d) = 2;
  while($d*$d<=$n){
    my $p = 0;
    while(!($n % $d)){
      $n /= $d;
      $p++;
    }
    push @res, $p if $p>0;
    $d++;
  }

  push @res, 1 if $n>1;
  return @res;
}

sub achain {
  my (@shape) = @_;
  my ($dc) = scalar @shape;

  my $t = 0;
  foreach my $p (@shape){
    $t += $p;
  }

  my (@tv) = (0) x ($t+1);
  my (@dg) = (0) x $dc;
  while(1){
    $t = 0;
    foreach my $d (@dg){
      $t += $d;
    }
    $tv[$t]++;

    my $pos = 0;
    while($pos<$dc && $dg[$pos]==$shape[$pos]){
      $dg[$pos] = 0;
      $pos++;
    }
    last if $pos==$dc;
    $dg[$pos]++;
  }

  $mx = -1;
  foreach $t (@tv){
    $mx = $t if $t>$mx;
  }

  return $mx;
}

MAIN : {
  my $mx = shift || 20;

  print STDERR "1 . 1\n";
  print "1 1\n";
  
  my $total = 1;
  for(my $n=2; $n<=$mx; $n++){
    my @shape = fshape($n);
    my ($ac) = achain(@shape);
    $total += $ac;

    print STDERR "$n " . join('-', @shape) . " $ac\n";
    print "$n " . ($total/$n) . "\n";
  }
}


Best regards,

-- 
+------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, mriedel@neuearbeit.de |
| http://www.geocities.com/markoriedelde/index.html          |
+------------------------------------------------------------+