On the additive complexity of GCD and LCM matrices (Q509060)

Let GCD (respectively LCM) be the \(n\times n\) greatest common divisor (least common multiple) matrix, and let \(L_B(A)\) denote the complexity of a matrix~\(A\) over a basis~\(B\). Denoting by~\(A^{[r]}\) the \(r\)'th Hadamard (i.e., entrywise) power of~\(A\), and by~\(\sim\) the asymptotic equality as \(n\to\infty\), the authors prove (Theorem~1) that \(L_B(\text{GCD}^{[r]})\sim rn\log_2n\) over \(B=\{x+y\}\) and (Theorem~2) \(L_B(\text{LCM}^{[r]})\sim 2rn\log_2n\) over \(B=\{x+y\}\cup\{ax\mid |a|\leq 1\}\). Thereafter, they note: ''Although the result of Theorem~2 is asymptotically sharp, it is obtained in a powerful basis admitting non-integer-valued operations. A derivation of a similar result in a basis with minimal family of computational tools would be of interest.'' So they prove (Theorem~3) that the above formula holds also over \(B=\{x+y,-x\}\).