Onde está o erro nesse algoritmo de multiplicação aparentemente O (n lg n)?

Um post recente do blog sobre quebra-cabeças sobre como encontrar três itens espaçados de maneira uniforme me leva a uma pergunta sobre o stackoverflow com uma resposta excelente que afirma fazê-lo em O (n lg n) tempo. A parte interessante é que a solução envolve quadratura de um polinômio, referenciando um artigo que descreve como fazê-lo em O (n lg n) tempo .

Agora, multiplicar polinômios é praticamente o mesmo que multiplicar números. A única diferença real é a falta de carregamentos. Mas ... os carregamentos também podem ser feitos em O (n lg n) tempo. Por exemplo:

    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

Então, minha pergunta é a seguinte: onde está o erro, aqui? Multiplicar números em O (n lg n) é um problema gigantesco em aberto na ciência da computação, e eu realmente duvido que a resposta seja simples assim.

• O carregamento está errado ou não O (n lg n)? Descobri que lg n + 1 bits por valor é suficiente para rastrear os carregamentos, e o algoritmo é tão simples que ficaria surpreso se estivesse errado. Observe que, embora um incremento individual possa levar tempo O (lg n), o custo agregado para incrementos de x é O (x).
• O algoritmo de multiplicação polinomial do papel está errado ou tem condições que estou violando? O artigo usa uma transformação rápida de Fourier em vez de uma transformação teórica dos números, o que pode ser um problema.
• Muitas pessoas inteligentes perderam uma variante óbvia do algoritmo de Schönhage-Strassen por 40 anos? Isso parece de longe o menos provável.

Na verdade, eu escrevi um código para implementar isso, exceto pela multiplicação polinomial eficiente (ainda não entendi bem a transformação teórica dos números). O teste aleatório parece confirmar que o algoritmo está correto; portanto, o problema é provável na análise de complexidade do tempo.

$O(\log n)$

O "erro" aqui é que uma transformação de Fourier pode ser calculada em O (n log n) etapas de adição ou multiplicação dos números a serem transformados, mas conforme n cresce muito, os números que são transformados também aumentam, o que acrescenta outro fator log log n.

Na prática, eu pensaria que o uso de ponto flutuante de precisão quádrupla (ponto flutuante de 128 bits usando dois valores duplos) ou ponto fixo de 128 bits na FFT seria suficiente para qualquer produto pequeno o suficiente para ser calculado.