# 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. – Bob Hanlon Jun 16 '15 at 21:51
• @Bob Hi, I did and I used expand because it is supposed to speed up the computation. – bobbym Jun 16 '15 at 22:02
• @BobHanlon: See here... – ciao Jun 16 '15 at 22:27
• Added the bugs tag; thanks for not putting it yourself until others have tried things. :) – J. M. will be back soon Jun 16 '15 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). – Michael E2 Jun 17 '15 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. – bobbym Jun 17 '15 at 7:28
• Can you update the version where it got fixed? The problem is not present with my CPU. – Szabolcs Oct 17 '15 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. – ilian Oct 17 '15 at 15:16