# Trouble with polynomial multiplication

Bug introduced in 10.1.0 and fixed in 10.4.0

Coefficient[
Sum[x^k, {k, 0, 1000}]
Sum[x^k, {k, 0, 1000, 2}]
Sum[x^k, {k, 0, 1000, 5}]
Sum[x^k, {k, 0, 1000, 10}]
Sum[x^k, {k, 0, 1000, 20}]
Sum[x^k, {k, 0, 1000, 50}]
Sum[x^k, {k, 0, 1000, 100}] // Expand, x, 1000] // AbsoluteTiming

{0.032555, 11583833929}


That is why I love Mathematica. Now I just tack on another polynomial...

Coefficient[
Sum[x^k, {k, 0, 1000}]
Sum[x^k, {k, 0, 1000, 2}]
Sum[x^k, {k, 0, 1000, 5}]
Sum[x^k, {k, 0, 1000, 10}]
Sum[x^k, {k, 0, 1000, 20}]
Sum[x^k, {k, 0, 1000, 50}]
Sum[x^k, {k, 0, 1000, 100}]
Sum[x^k,{k,0,1000,200}] // Expand, x, 1000] // AbsoluteTiming

{0.039276, -190969169941}


How do I get a negative coefficient for x^1000 when all those polys have positive coefficients? Where did I go wrong?

I am afraid that in light of Bob's calculations which I know are correct I am going to have to say that this is a bug in 10.1 when running on Linux Mint 17.1 Rebecca.

If I do it this way:

Coefficient[
Series[Sum[x^k, {k, 0, 1000}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 2}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 5}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 10}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 20}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 50}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 100}], {x, 0, 1000}], x, 1000] // AbsoluteTiming

{0.009989, 234896541}

Coefficient[
Series[Sum[x^k, {k, 0, 1000}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 2}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 5}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 10}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 20}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 50}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 100}], {x, 0, 1000}]
Series[Sum[x^k, {k, 0, 1000, 200}], {x, 0, 1000}] , x, 1000] // AbsoluteTiming

{0.007549, 321335886}


we get the correct answer, this is probably due to fact that the series command truncates each poly not allowing intermediate calculations to trigger the anomaly that happens when large polys are multiplied in 10.1 on this OS.

• With v10.1 on a Mac, I do not get the same results as you did. I get 234896541 for the first coefficient and 321335886 for the second. By the way, the use of Expand is not necessary to get the coefficients. Commented Jun 16, 2015 at 21:51
• @Bob Hi, I did and I used expand because it is supposed to speed up the computation. Commented Jun 16, 2015 at 22:02
• @BobHanlon: See here...
– ciao
Commented Jun 16, 2015 at 22:27
• Added the bugs tag; thanks for not putting it yourself until others have tried things. :) Commented Jun 16, 2015 at 23:09
• I think your timings on Series are because Series caches its computations. When you repeat them, it just looks up the previous result. (Correct answer aside). Commented Jun 17, 2015 at 0:06

Update

This bug has been fixed in Mathematica 10.4.0.

I can confirm the above incorrect results are due to a bug in the Intel MKL library shipping with Mathematica 10.1 which affects FFT convolution. The problem is only known to be triggered on some processors (for example AMD chips, or virtual machine emulated CPUs).

The following workaround will use an alternative implementation that does not rely on MKL

SetSystemOptions["FourierOptions" -> {"ConvolutionLibrary" -> "Mathematica"}];

• That is an important bit of info and fix for me, thank you. Commented Jun 17, 2015 at 7:28
• Can you update the version where it got fixed? The problem is not present with my CPU. Commented Oct 17, 2015 at 9:17
• @Szabolcs Still present in 10.3 (it affects fairly "exotic" CPUs), but I expect it will be fixed in the next release. Commented Oct 17, 2015 at 15:16