The question was already asked here, but doesn't have any meaningful answer, hence I'd like to re-post it.
Assuming that we have an algebra with conjugation, we can use Cayley-Dickson construction to define an algebra on pairs:
$$ (a, b)^* = (a^*,-b), \\ (a,b)(c,d) = (ac-d^*b, da+bc^*). $$ It is well known that, starting with real numbers, we can construct complex numbers, quaternions, octonions, etc with this. Hence, on $n$-th step we have an $2^n$-dimensional space with this weird multiplication operation defined.
That said, assume that $2$ Cayley-Dickson hypercomplex numbers are represented by a vector of $2^n$ numbers each. Is it possible to compute their product faster than $O(4^n)$, that is, in a sub-quadratic time?
I imagine that some potentially simpler way to do it would be to reduce the multiplication of $2$ numbers to $3$ recursive multiplications instead of $4$, similarly to what happens in Karatsuba and Strassen algorithms, so that the runtime of a single multiplication is $O(3^n)$. One other possibility could be some transform, similar in nature to the fast Fourier transform, that reduces Cayley-Dickson multiplication to a coordinate-wise multiplication in some weird space.
I know for certain that, be the multiplication recursively defined as $(ac+bd, ad+bc)$, there would be such a transform, in fact, fast Walsh-Hadamard transform would allow us to compute the whole product in $O(2^n n)$. But I don't see any reasonably simple way to do this for hyper complexes... So, any other ideas?
UPD: Per this (see also the paper), it's possible to reduce quaternion multiplication to just $8$ multiplications instead of $16$. If a similar formula exists for octonions, it will likely suffice to just apply its transitions recursively.
UPD 2: Apparently, the current best algorithm for octonion product uses $30$ multiplications instead of $64$. It still seems complicated, so it's hard to understand if it generalizes well.
