¿Dónde está el error en este algoritmo de multiplicación aparentemente-O (n lg n)?

Una reciente publicación de blog sobre cómo encontrar tres espacios espaciados de manera uniforme me lleva a una pregunta de stackoverflow con una respuesta superior que dice hacerlo en tiempo O (n lg n). La parte interesante es que la solución consiste en cuadrar un polinomio, haciendo referencia a un documento que describe cómo hacerlo en tiempo O (n lg n) .

Ahora, multiplicar polinomios es prácticamente lo mismo que multiplicar números. La única diferencia real es la falta de acarreos. Pero ... los acarreos también se pueden hacer en O (n lg n) tiempo. Por ejemplo:

    var value = 100; // = 0b1100100

    var inputBitCount = value.BitCount(); // 7 (because 2^7 > 100 >= 2^6)
    var n = inputBitCount * 2; // 14
    var lgn = n.BitCount(); // 4 (because 2^4 > 14 => 2^3)
    var c = lgn + 1; //5; enough space for 2n carries without overflowing

    // do apparently O(n log n) polynomial multiplication
    var p = ToPolynomialWhereBitsAreCoefficients(value); // x^6 + x^5 + x^2
    var p2 = SquarePolynomialInNLogNUsingFFT(p); // x^12 + 2x^11 + 2x^10 + x^8 + 2x^7 + x^4
    var s = CoefficientsOfPolynomial(p2); // [0,0,0,0,1,0,0,2,1,0,2,2,1]
    // note: s takes O(n lg n) space to store (each value requires at most c-1 bits)

    // propagate carries in O(n c) = O(n lg n) time
    for (var i = 0; i < n; i++)
        for (var j = 1; j < c; j++)
            if (s[i].Bit(j))
                s[i + j].IncrementInPlace();

    // extract bits of result (in little endian order)
    var r = new bool[n];
    for (var i = 0; i < n; i++)
        r[i] = s[i].Bit(0);

    // r encodes 0b10011100010000 = 10000

Entonces mi pregunta es esta: ¿dónde está el error, aquí? Multiplicar números en O (n lg n) es un gigantesco problema abierto en informática, y realmente dudo que la respuesta sea así de simple.

• ¿El transporte es incorrecto o no O (n lg n)? He deducido que lg n + 1 bits por valor es suficiente para rastrear los acarreos, y el algoritmo es tan simple que me sorprendería si estuviera equivocado. Tenga en cuenta que, aunque un incremento individual puede llevar tiempo O (lg n), el costo agregado para los incrementos x es O (x).
• ¿El algoritmo de multiplicación polinómica del documento es incorrecto o tiene condiciones que estoy violando? El documento usa una transformación rápida de Fourier en lugar de una transformación teórica de números, lo que podría ser un problema.
• ¿Mucha gente inteligente se perdió una variante obvia del algoritmo Schönhage – Strassen durante 40 años? Esto parece, con mucho, el menos probable.

De hecho, he escrito código para implementar esto, excepto por la multiplicación polinómica eficiente (todavía no entiendo la transformación teórica de números). Las pruebas aleatorias parecen confirmar que el algoritmo es correcto, por lo que es probable que el problema esté en el análisis de la complejidad del tiempo.

$O(\log n)$

El "error" aquí es que una transformación de Fourier se puede calcular en pasos O (n log n) de sumar o multiplicar los números a transformar, pero a medida que n crece realmente, los números que se transforman también se hacen más grandes, lo que agrega otro factor log log n.

En la práctica, creo que usar un punto flotante de precisión cuádruple (punto flotante de 128 bits con dos valores dobles) o un punto fijo de 128 bits en la FFT sería suficiente para calcular cualquier producto que sea lo suficientemente pequeño.