probabilistic algorithm

The algorithms used for the computation of characteristic classes are probabilistic. Theoretically, they calculate the classes correctly for a general choice of certain polynomials. That is, there is an open dense Zariski set for which the algorithm yields the correct class, i.e., the correct class is calculated with probability 1. However, since the implementation works over a discrete probability space there is a very small, but non-zero, probability of not computing the correct class. Skeptical users should repeat calculations several times to increase the probability of computing the correct class.

In the case of the symbolic implementation of the ProjectiveDegree method practical experience and algorithm testing indicate that a finite field with over 25000 elements is more than sufficient to expect a correct result with high probability, i.e. using the finite field kk=ZZ/25073 the experimental chance of failure with the ProjectiveDegree algorithm on a variety of examples was less than 1/2000. Using the finite field kk=ZZ/32749 resulted in no failures in over 10000 attempts of several different examples.

We illustrate the probabilistic behaviour with an example where the chosen random seed leads to a wrong result in the first calculation.

i1 : setRandomSeed 121;

i2 : R = QQ[x,y,z,w]

o2 = R

o2 : PolynomialRing

i3 : I = minors(2,matrix{{x,y,z},{y,z,w}})

               2                        2
o3 = ideal (- y  + x*z, - y*z + x*w, - z  + y*w)

o3 : Ideal of R

i4 : Chern (I,CompMethod=>PnResidual)

       2
o4 = 4H

     ZZ[H]
o4 : -----
        4
       H

i5 : Chern (I,CompMethod=>PnResidual)

       3     2
o5 = 2H  + 3H

     ZZ[H]
o5 : -----
        4
       H

i6 : Chern (I,CompMethod=>PnResidual)

       3     2
o6 = 2H  + 3H

     ZZ[H]
o6 : -----
        4
       H

i7 : Chern(I,CompMethod=>ProjectiveDegree)

       3     2
o7 = 2h  + 3h
       1     1

     ZZ[h ]
         1
o7 : ------
        4
       h
        1