Bicycle Dimension and Special Points of the Tutte Polynomial

For each pair of algebraic numbers (x, y) and each fieldF, the complexity of computing the Tutte polynomialT(M; x, y) of a matroidMrepresentable overFis determined. This computation is found to be#P-complete except when (x−1)(y−1)=1 or when |F| divides (x−1)(y−1) and (x, y) is one of the seven points (0, −1), (−1, 0), (i, −i), (−i, i), (j, j2), (j2, j) or (−1, −1), wherej=e2πi/3. Expressions are given for the Tutte polynomial in the exceptional cases. These expressions involve the bicycle dimension ofMoverF. A related result determines when this bicycle dimension is well defined.