{"entities":{"Q509060":{"pageid":510827,"ns":120,"title":"Item:Q509060","lastrevid":52737950,"modified":"2026-01-23T09:44:30Z","type":"item","id":"Q509060","labels":{"en":{"language":"en","value":"On the additive complexity of GCD and LCM matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6682150"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$5B5EDD51-C25B-458D-9F45-7CC4AE9E6EFF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3796998dbf8c92696ea2fc45385eccabb0d174e5","datavalue":{"value":{"text":"On the additive complexity of GCD and LCM matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q509060$85C3C6EC-19B5-496D-85F7-4806C9467380","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2d32902f23ba58690098cbc5c0670786017946cb","datavalue":{"value":"1371.11069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q509060$AD9617B5-2425-447C-A1AE-7C890DD4D1FD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"05370026237453e3b348c62c10ccb6d8284f8697","datavalue":{"value":"10.1134/S0001434616070166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q509060$9DA9092E-2040-4FDD-89A2-6F484A2CF4BF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"00de3e6b6cfff0576fe0e1d6bc63c05579d2cb43","datavalue":{"value":{"entity-type":"item","numeric-id":173953,"id":"Q173953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$F945D91A-8673-45C1-9C41-7E81B19EA5C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0e5e5990e36b519f41dfed9405f14b12a1e45d34","datavalue":{"value":{"time":"+2017-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q509060$2693CD18-DD53-466B-97B9-9384DD0D753A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"df7b745966fa7febd294926352bdbf5cc5a89be4","datavalue":{"value":"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\\}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q509060$236F05E5-3DCD-45DC-9538-420D8B829015","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d92207e5132f33177f4a9d633493fc0d8d742c6d","datavalue":{"value":"11C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q509060$D551931D-6D89-4B43-9BEA-5634F21864BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06299a38dab9dd1c28e96fe2a7f8cac0943d746","datavalue":{"value":"15B36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q509060$49C83107-F762-41FB-BF3A-EB239BBDFB6E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"104e267efc71db29c3f02f2a247579f5ee529fbd","datavalue":{"value":"6682150","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q509060$67CF8427-CAE3-4714-9DF4-8E099BFA3D8C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac88c7c4ceb79c868083defb73e33bb7e3d89ba0","datavalue":{"value":"greatest common divisor","type":"string"},"datatype":"string"},"type":"statement","id":"Q509060$65804FAC-0222-4000-9CEE-9C2DEADE8AE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2c2062de5f19c527ccd12cf4042772b859b439d","datavalue":{"value":"least common multiple","type":"string"},"datatype":"string"},"type":"statement","id":"Q509060$C0722BC8-3769-4136-B60B-523A33828D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1b9f23e6e3b5da4874f3562b1e571f58267dee5","datavalue":{"value":"additive complexity of a matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q509060$D3B887DF-4251-42A6-A415-D0532997FB86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"387f2e7f76a3e084f94555cad52a65dd51a5fafb","datavalue":{"value":"Smith determinant","type":"string"},"datatype":"string"},"type":"statement","id":"Q509060$6C1300F4-9F62-41CD-86C8-53706655F2B1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"115ab1234d127e085aadf8ebac1b013bb237b04f","datavalue":{"value":{"entity-type":"item","numeric-id":314123,"id":"Q314123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$7B9D5579-A0B0-4663-9B58-26AF183AA1CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7bca759d38ceb2986d169f3b3e0477372a238ba1","datavalue":{"value":{"entity-type":"item","numeric-id":1675518,"id":"Q1675518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$7DA2587C-D379-4D94-A2EC-AB9999D5ED5C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"982db592c7fdfabf3011cbaf76d1b6ec541c138d","datavalue":{"value":{"entity-type":"item","numeric-id":583322,"id":"Q583322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$455B633B-495B-4069-B767-0DB0A42A2BF4","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$54807696-61FA-4D1F-83BB-8C5A3AB85611","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b6fcb90f22a01b09f0ebb95e36fc66957ee6a47","datavalue":{"value":{"entity-type":"item","numeric-id":1359193,"id":"Q1359193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$8876BC19-3044-4346-BED7-827E9B58424E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"016e28d09ee1dec95b54fb4f25f16f4bacec6cf5","datavalue":{"value":{"entity-type":"item","numeric-id":4650315,"id":"Q4650315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$526178E7-A5D3-49EA-B202-D5B990E6382F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d27ae0c06b28e6be5ae4b470d7fdb6aba03f14f4","datavalue":{"value":{"entity-type":"item","numeric-id":5674381,"id":"Q5674381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$61EBAE5A-7491-47A1-9A87-F12333E2C25A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7863dd58946edec7a8c434995c7b2dfe2cb498b6","datavalue":{"value":{"entity-type":"item","numeric-id":5396765,"id":"Q5396765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$6B6F8024-98DD-4302-A542-2630DA176099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e517be21bf3d1a275a25b6048e005327e6a8f89","datavalue":{"value":{"entity-type":"item","numeric-id":2352607,"id":"Q2352607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$C9EA3BF7-B5C4-4430-A0F7-1A3965886C09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"485a30976e9776786c3b9bb7c2d40c75abe863ff","datavalue":{"value":{"entity-type":"item","numeric-id":314124,"id":"Q314124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$59F4DAEE-37E4-4EE4-82D6-DB546786E1BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7581633aef5fb0d72e73ad0ccf25fc91d2207339","datavalue":{"value":{"entity-type":"item","numeric-id":5704310,"id":"Q5704310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$5CFB6DB9-B715-4985-91EB-0F8C9BA778E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ac8c1a8f4fc40d6cef0aa839f46d49dc8911ab4","datavalue":{"value":{"entity-type":"item","numeric-id":1277677,"id":"Q1277677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$0D0A9BFF-38C2-4D62-8E9C-B73B50EDB54D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05633d63161b4478010a944d5e9a50d55aff02f5","datavalue":{"value":{"entity-type":"item","numeric-id":4887644,"id":"Q4887644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$ABA79E55-92A5-4320-848E-A825843DD767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa0540fd78fb7a7ac36ecb95287d9deaac0fb1e2","datavalue":{"value":{"entity-type":"item","numeric-id":5585021,"id":"Q5585021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$8BCC39A1-F6BB-4BA0-B85A-4690A7AEAB63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6a88e7c87651eeb3ff2433bf71733b763895cdc","datavalue":{"value":{"entity-type":"item","numeric-id":2626710,"id":"Q2626710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$48260A59-0023-410F-8063-25CA9D013714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4f7864af32baf8b49f72b4b1cd5aa2d17274d92","datavalue":{"value":{"entity-type":"item","numeric-id":3376053,"id":"Q3376053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$7966389C-31CF-4839-9511-50ADC19572A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62dc149ed896866c5f108585003cf7b4d676ade8","datavalue":{"value":{"entity-type":"item","numeric-id":1195336,"id":"Q1195336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$732A4F28-70D2-4B8D-AC07-1E86AB9F9D98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7c3f1ebae2273fccb81559205dae8ff7b1be7c6","datavalue":{"value":{"entity-type":"item","numeric-id":3835734,"id":"Q3835734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q509060$2BB00862-0DBB-48A3-9F4E-30C94FAFC26B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ce72333a0eba1d4f6d7521c16e65f008d0e93c9","datavalue":{"value":{"entity-type":"item","numeric-id":1304198,"id":"Q1304198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0d71240603428aeaa19b6e4f5736181ad8a9bfe","datavalue":{"value":{"amount":"+0.7760920524597168","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q509060$1D3E5426-CA88-4F27-8934-3A17553A5370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cd0f235a823dd3af6493d03e26e1f7b1d63d7b8","datavalue":{"value":{"entity-type":"item","numeric-id":4450711,"id":"Q4450711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0d71240603428aeaa19b6e4f5736181ad8a9bfe","datavalue":{"value":{"amount":"+0.7760920524597168","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q509060$8B88E7DE-1534-4415-BD2B-218A1D842858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fbd29e019c4b78cc8922974426ee186f9dd2bb0","datavalue":{"value":{"entity-type":"item","numeric-id":5310130,"id":"Q5310130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fc046eed70aa0af056468ead304d278ef973cc0","datavalue":{"value":{"amount":"+0.772132158279419","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q509060$17AF55CB-37E0-4754-8992-ABFEB31F7B47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4895b22fba63f0dc924354e74d343a539f3a50a","datavalue":{"value":{"entity-type":"item","numeric-id":1347956,"id":"Q1347956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b27b79148965ad6efdabd9ae9d976820ce3902e1","datavalue":{"value":{"amount":"+0.7700347304344177","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q509060$4B361A7D-A1F6-4599-827C-988812FE2928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87d8b73e994b6fd53f59fd1310ab751b6da53cd5","datavalue":{"value":{"entity-type":"item","numeric-id":4457973,"id":"Q4457973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b27b79148965ad6efdabd9ae9d976820ce3902e1","datavalue":{"value":{"amount":"+0.7700347304344177","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q509060$FE7190FF-954D-4A90-BA1E-10FFE402B759","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:509060","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:509060"}}}}}