RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Mat. Zametki: Year: Volume: Issue: Page: Find

 Mat. Zametki, 2016, Volume 100, Issue 2, Pages 196–211 (Mi mz10626)

On the Additive Complexity of GCD and LCM Matrices

S. B. Gashkova, I. S. Sergeevb

a Lomonosov Moscow State University
b Research Institute "Kvant"

Abstract: In the paper, the additive complexity of matrices formed by positive integer powers of greatest common divisors and least common multiples of the indices of the rows and columns is considered. It is proved that the complexity of the $n\times n$ matrix formed by the numbers $GCD^r(i,k)$ over the basis $\{x+y\}$ is asymptotically equal to $rn \log_2 n$ as $n\to\infty$, and the complexity of the $n\times n$ matrix formed by the numbers $LCM^r(i,k)$ over the basis $\{x+y,-x\}$ is asymptotically equal to $2rn \log_2 n$ as $n\to \infty$.

Keywords: greatest common divisor, least common multiple, additive complexity of matrices, Smith determinant, circuit complexity.

 Funding Agency Grant Number Russian Foundation for Basic Research 14-01-00671à This work was financially supported by the Russian Foundation for Basic Research under grant 14-01-00671a.

DOI: https://doi.org/10.4213/mzm10626

Full text: PDF file (568 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Mathematical Notes, 2016, 100:2, 199–212

Bibliographic databases:

Document Type: Article
UDC: 519.714+511.17

Citation: S. B. Gashkov, I. S. Sergeev, “On the Additive Complexity of GCD and LCM Matrices”, Mat. Zametki, 100:2 (2016), 196–211; Math. Notes, 100:2 (2016), 199–212

Citation in format AMSBIB
\Bibitem{GasSer16} \by S.~B.~Gashkov, I.~S.~Sergeev \paper On the Additive Complexity of GCD and LCM Matrices \jour Mat. Zametki \yr 2016 \vol 100 \issue 2 \pages 196--211 \mathnet{http://mi.mathnet.ru/mz10626} \crossref{https://doi.org/10.4213/mzm10626} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3588838} \elib{http://elibrary.ru/item.asp?id=26414289} \transl \jour Math. Notes \yr 2016 \vol 100 \issue 2 \pages 199--212 \crossref{https://doi.org/10.1134/S0001434616070166} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000382193300016} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84983739045}