{"entities":{"Q931867":{"pageid":933715,"ns":120,"title":"Item:Q931867","lastrevid":65437833,"modified":"2026-04-12T02:36:12Z","type":"item","id":"Q931867","labels":{"en":{"language":"en","value":"On the complexity of the quasi-isometry and virtual isomorphism problems for finitely generated groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5296721"}},"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":"Q931867$59DEF308-914C-4AC7-A49E-CEF724D5D89D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1ef5dec2f6049acb84da5830c329be1ec9a2ae58","datavalue":{"value":{"text":"On the complexity of the quasi-isometry and virtual isomorphism problems for finitely generated groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q931867$26FD7D22-CD4F-45D0-B82F-59F6115A609A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"18237c4652d17f60ffa40d31de1276da54536d39","datavalue":{"value":"1151.03026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q931867$620D1DC8-4F22-4A0A-893D-EFC71753BC97","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec88d824689c774ae562b504d5ababbfedf6bf1b","datavalue":{"value":"10.4171/GGD/41","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q931867$2290B0FC-D94D-4AA9-B7CF-FB1ECFF6B7E7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fee6d7c6a61a047db4fa1acc0036957ae324bbfa","datavalue":{"value":{"entity-type":"item","numeric-id":194963,"id":"Q194963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q931867$74DD31F4-21C5-410E-AE08-6F7B2D38F3C1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"12e3e9652f934c7e19471889c1a9038496516295","datavalue":{"value":{"entity-type":"item","numeric-id":260093,"id":"Q260093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q931867$4DE7695D-B440-4960-8B2E-56F06EE12FEE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"03dc85bcb852416a69558ff26ee872119ad863d0","datavalue":{"value":{"time":"+2008-07-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q931867$B1459AEA-E5B0-4BC9-B3D8-B89C06ABF779","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f3f090d0d03bf5a82fed827883e496306eea22cc","datavalue":{"value":"http://www.ems-ph.org/journals/show_pdf.php?issn=1661-7207&vol=2&iss=2&rank=8","type":"string"},"datatype":"url"},"type":"statement","id":"Q931867$6AAC4A20-6C68-4AB6-B61A-94C93ECFF1FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c41f3c04560ceeb91b5cea035d28e9d8d5bf43b8","datavalue":{"value":"Let \\(S\\) and~\\(T\\) be finite sets of generators of groups \\(G\\) and~\\(H\\) with word metrics \\(d_S\\) and~\\(d_T\\), respectively.  The groups \\(G\\) and~\\(H\\) are said to be quasi-isometric, written \\(G\\approx_{\\text{QI}}H\\), if there exist \\(\\lambda\\geq1\\), \\(C\\geq0\\), and a~mapping \\(\\varphi:G\\to H\\) such that \\(\\frac1\\lambda d_S(x,y)-C\\leq d_T(\\varphi(x),\\varphi(y))\\leq \\lambda d_S(x,y)+C\\) for all \\(x,y\\in G\\) and \\(d_T(z,\\varphi[G])\\leq C\\) for all \\(z\\in H\\). Two finitely generated groups \\(G_1\\) and~\\(G_2\\) are said to be virtually isomorphic up to finite kernels, written \\(G_1\\approx_{\\text{VI}}G_2\\), if there exist subgroups \\(N_i\\leq H_i\\leq G_i\\) for \\(i=1\\),~\\(2\\) such that \\([G_i:H_i]<\\infty\\), \\(N_i\\)~is a~finite normal subgroup of~\\(H_i\\) for \\(i=1\\),~\\(2\\) and \\(H_1/N_1\\cong H_2/N_2\\). It is known that virtually isomorphic finitely generated groups are quasi-isometric.  The converse does not hold and it is natural to conjecture that the quasi-isometry relation is strictly more complex than the virtual isomorphism relation in the sense of Borel reducibility.  A~known theorem of the author of the paper that the quasi-isometry relation~\\(\\approx_{\\text{QI}}\\) is strictly more complex than the isomorphism relation~\\(\\cong\\) on the space of finitely generated groups can serve as a~justification of this conjecture.   In the paper under the review the author studies the Borel complexity of the relations \\(\\cong\\), \\(\\approx_{\\text{QI}}\\), and \\(\\approx_{\\text{VI}}\\) for the class of finitely generated groups. He proves that they are \\(K_\\sigma\\)-equivalence relations. The quasi-isometry relation makes sense for arbitrary metric spaces, and the author proves that the quasi-isometry relation on the space of connected \\(4\\)-regular graphs is a~universal \\(K_\\sigma\\)-equivalence relation. The conjecture that \\(\\approx_{\\text{QI}}\\) is a~universal \\(K_\\sigma\\)-equivalence relation remains open. But \\(\\approx_{\\text{VI}}\\) for finitely generated groups is shown to be a~non-universal \\(K_\\sigma\\)-equivalence relation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q931867$E49623F9-12F5-4EFC-94D8-46735401E2BA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"24f8d16b2be3be7c389bb7bc4bfcdf6adc672a29","datavalue":{"value":{"entity-type":"item","numeric-id":173771,"id":"Q173771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q931867$FE60BA71-D586-4C92-AAB0-3BD0AEA67EE5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3636caf529c49b2a7d814c7a65de2b21aedf761","datavalue":{"value":"03E15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q931867$44827A53-926B-4893-933C-331085E4F56F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"639e35a4d8066ba3b320b7c5998ad4d73a0cf431","datavalue":{"value":"20F65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q931867$70E220CC-0306-4ECF-BAD6-08FF1A12BDD2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5aae9d8a5f4e5208bee90e190c635bc78046093","datavalue":{"value":"5296721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q931867$F23FC536-BA37-47F3-B883-95AC73030A3C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1afb0f0bcaf0e9dd05ae2cff2f0a02cd29931d0","datavalue":{"value":"Borel equivalence relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q931867$0773AE15-6CF8-413F-8479-BE460B71FEA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c48369a13f5a36d8f23b6b86aae50dfc447d79f","datavalue":{"value":"quasi-isometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q931867$54D92EF0-0B01-43B9-9BC0-319C8D40092D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d943a29050774e8f96e114dd2b5282d8891bf1f5","datavalue":{"value":"virtual isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q931867$75035463-0701-44C0-9D46-5931D7C48846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9330abe130451586665a92b0ac2207e1fbd65df8","datavalue":{"value":"Borel reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q931867$175F394B-F111-4A4F-B1E4-BFF5B919CA69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed7c9e8b471b034eb25fe7adf1982e656192444c","datavalue":{"value":"Borel complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q931867$5D76CB04-2299-43B4-8BB7-647BFB21CA46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"542470d6f63fefcd2ae937cc78d1c833a1db112c","datavalue":{"value":"finitely generated groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q931867$DE6C2825-7760-4A52-9621-732FC660FB0A","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":"Q931867$0E792F8A-609D-4BCD-AF17-64D6D18DF16E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7bcac66bb3dc49c58eac971c8f573186f643d4c","datavalue":{"value":{"entity-type":"item","numeric-id":4331784,"id":"Q4331784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q931867$5BFD8FC3-185F-423B-9BE6-AC1EB0541F39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"994cc16076e319085384000c51a3f3fd03d87388","datavalue":{"value":{"entity-type":"item","numeric-id":1392745,"id":"Q1392745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q931867$DCCA9A75-BE74-485E-9755-C5F5F0A02AFB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ee7c4dc0131e560ca64245c4c74c5c4a57bfe688","datavalue":{"value":"W2064206945","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q931867$7D5859EF-2CE2-4439-A312-45AE64FAEDFD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88baaef875fb95d446ab7d084e3c95a62a756652","datavalue":{"value":{"entity-type":"item","numeric-id":4437744,"id":"Q4437744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af5cd62c896922ad37304002f0aa4aad8efa3e81","datavalue":{"value":{"amount":"+0.8230285048484802","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":"Q931867$D8769E46-D991-4C50-9E0A-D3960F45DB03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25d7e020e51ac927427c8ae58488ec62db81cdc1","datavalue":{"value":{"entity-type":"item","numeric-id":1305085,"id":"Q1305085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6aad1ea624e12ec189ffef81f3e49b08a3897cb2","datavalue":{"value":{"amount":"+0.7870725393295288","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":"Q931867$50F0CF53-0432-4EE8-A01C-2E254E847E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02c620fdb5f9fc64d68cb02d979d45a6ae5f835c","datavalue":{"value":{"entity-type":"item","numeric-id":605905,"id":"Q605905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6aad1ea624e12ec189ffef81f3e49b08a3897cb2","datavalue":{"value":{"amount":"+0.7870725393295288","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":"Q931867$E184A150-021A-4F5E-A416-275F3CF580E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebb8449a8aa2e96f026811e02581dc9d81464277","datavalue":{"value":{"entity-type":"item","numeric-id":3401164,"id":"Q3401164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a95f4ecd5706049604657ed597f8780ad4bd68fc","datavalue":{"value":{"amount":"+0.7834627628326416","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":"Q931867$A84C6D78-4D1C-4952-9F50-5EDE7BF1B0FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be865dc276bd63d2a532cf02e908e875f03c84a0","datavalue":{"value":{"entity-type":"item","numeric-id":5314952,"id":"Q5314952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f82b31050593d33ae2304253379ec6e35c1e6aa","datavalue":{"value":{"amount":"+0.7552126049995422","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":"Q931867$90BFB435-B8C1-47CE-A6B9-8001CB1198C6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of the quasi-isometry and virtual isomorphism problems for finitely generated groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_the_quasi-isometry_and_virtual_isomorphism_problems_for_finitely_generated_groups"}}}}}