Quasilinear multiplication in the Cayley-Dickson tower
Abstract
Direct evaluation of the defining product of the Cayley-Dickson algebra An of rank N:=2n over a unital commutative ring R in which $2$ is invertible requires a quadratic number of arithmetic operations. This paper gives a uniform bilinear algorithm for multiplication in this algebra costing O(N log N) arithmetic operations in R and O(N) auxiliary storage when the doubling parameters of An are units whose square roots lie in a fixed commutative coefficient algebra S finitely generated as an R-module and admitting an R-linear map π: S → R with π(1) = 1. In particular, over ℝ and every finite field 𝔽q of odd characteristic, a quadratic field extension contains a square root of every possible doubling parameter, so the algorithm applies to every Cayley-Dickson tower over these fields, and the tensor rank of multiplication in An over them is at most (9n−21)2n+28 when n≥2. When the top doubling parameter is a non-square, as in the standard real tower, the bound is (9n−15)2n−1+10. To the author's knowledge, the algorithm presented in this paper is the first uniform subquadratic algorithm for multiplication in An. When R=ℝ with every doubling parameter equal to −1, the real quasilinear schedule uses fewer total arithmetic operations than both direct multiplication and a uniform algorithm of Cariow-Cariowa for n≥4. An implementation for the standard real tower is available in the MIT-licensed C11 library fastCD, with a NumPy-backed Python interface. In single-core benchmarks against direct multiplication and the uniform Cariow-Cariowa method, the quasilinear implementation had the lowest mean time of the three at every tested dimension N≥32, for both single and batched products, and was over $17$ times faster than direct multiplication at N=1024.
Related
- Orthogonality graphs of real Cayley-Dickson algebras. Part II: The subgraph on pairs of basis elements
- General Polynomials and Eigenvalues Over Cayley--Dickson Algebras
- Orthogonality graphs of real Cayley-Dickson algebras. Part I: Doubly alternative zero divisors and their hexagons
- Surjective Stability of Dickson-Siegel-Eichler-Roy Elementary Orthogonal Group over Projective Modules
- A note on generalized distributive sets of a finite Dickson nearfield
BibTeX
@misc{lemley2026quasilinear,
title = {{Quasilinear multiplication in the Cayley-Dickson tower}},
author = {Harrison Lemley},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.11588},
eprint = {2609.11588},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11588},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quasilinear multiplication in the Cayley-Dickson tower
AU - Harrison Lemley
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2609.11588
UR - https://arxiv.org/abs/2609.11588
AB - Direct evaluation of the defining product of the Cayley-Dickson algebra A_n of rank N:=2^n over a unital commutative ring R in which $2$ is invertible requires a quadratic number of arithmetic operations. This paper gives a uniform bilinear algorithm for multiplication in this algebra costing O(N log N) arithmetic operations in R and O(N) auxiliary storage when the doubling parameters of A_n are units whose square roots lie in a fixed commutative coefficient algebra S finitely generated as an R-module and admitting an R-linear map π: S → R with π(1) = 1. In particular, over ℝ and every finite field 𝔽_q of odd characteristic, a quadratic field extension contains a square root of every possible doubling parameter, so the algorithm applies to every Cayley-Dickson tower over these fields, and the tensor rank of multiplication in A_n over them is at most (9n−21)2^n+28 when n≥2. When the top doubling parameter is a non-square, as in the standard real tower, the bound is (9n−15)2^n−1+10. To the author's knowledge, the algorithm presented in this paper is the first uniform subquadratic algorithm for multiplication in A_n. When R=ℝ with every doubling parameter equal to −1, the real quasilinear schedule uses fewer total arithmetic operations than both direct multiplication and a uniform algorithm of Cariow-Cariowa for n≥4. An implementation for the standard real tower is available in the MIT-licensed C11 library fastCD, with a NumPy-backed Python interface. In single-core benchmarks against direct multiplication and the uniform Cariow-Cariowa method, the quasilinear implementation had the lowest mean time of the three at every tested dimension N≥32, for both single and batched products, and was over $17$ times faster than direct multiplication at N=1024.
ER -