We're given two positive integers of length $n$ in binary representation.
Design an algorithm which divides the numbers into ${n \over k}$ blocks of size $k=\lg n$ using FFT algorithm.
We can suppose that the multiplications that occur during recursive calls do not increase the length of the resulting numbers (not necessarily true in reality but can be supposed for the sake of the algorithm) therefore the multiplications can be performed in $\Theta(k^2)$ bit operations.
This is the solution of the algorithm I came across and I have some clarifications below:
1) Because we're given numbers in base $2$ then we can represent number $x$ such that $$x=2^0\cdot x_0+2^{k-1}\cdot x_1+...+2^{{kn \over k}-1}\cdot x_{{n \over k}-1}$$ where $x_i$ such that $i:0,1,2,..., {{n \over k}-1}$.
2) Now we can apply FFT (on ${2n \over k}$ roots of unity) to the vectors: $$z = \operatorname{FFT}(\{x_0,x_1,..., x_{{n \over k}-1}\})\cdot \operatorname{FFT}(\{y_0,y_1,..., y_{{n \over k}-1}\})$$ $z$ being the resulting vector.
3) We apply inverse FFT on $z$ and assign the result the vector $r$.
4) The run time complexity of the steps 3 and 4 is $O\big({n \over k}\lg{n \over k}\big)$. Because the internal bit multiplications can be performed in $\Theta(k^2)$ then overall we have $O\big({k^2\cdot n \over k}\lg{n \over k}\big)$ = $O(nk(\lg n-\lg k))$
5) Lastly we need to do the sum in order to get the final result: $$ \sum_{i=0}^{{2n} \over k} r_i\cdot 2^i $$ We'll perform the summation recursively dividing the input in half each time.
6) Because there're in step 5 there're ${n \over k\cdot 2^i}$ pairs and the size of each pair is $k\cdot 2^i$, the run time complexity of step 5 is: $$ \sum_{i=0}^{\lg{n \over k}} k\cdot 2^i\cdot {n \over k\cdot 2^i}=\sum_{i=0}^{\lg{n \over k}} n=O(n(\lg n-\lg k)) $$ 7) total run time complexity is $$O(n(\lg n-\lg k)+nk(\lg n-\lg k))=O(n\lg n(\lg n-\lg\lg n))$$
Clarifications:
step 1): why are the coefficients $2^0, 2^{k-1}, ..., 2^{{kn \over k}-1}$ and not $2^0, 2^1, 2^2,..., 2^{{n \over k}-1}$?
step 6): I don't understand how we get to the first summation.
step 7) I didn't understand the transition completely.