{"entities":{"Q691591":{"pageid":693440,"ns":120,"title":"Item:Q691591","lastrevid":63758931,"modified":"2026-04-11T15:21:22Z","type":"item","id":"Q691591","labels":{"en":{"language":"en","value":"Multidimensional extension of the Morse-Hedlund theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6111989"}},"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":"Q691591$227B927B-4B8A-4A92-A333-54DDC29C78C4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fdb5c30e2f27f39bb6a9fc3fc049fb60ef334478","datavalue":{"value":{"text":"Multidimensional extension of the Morse-Hedlund theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q691591$9CC3E780-66E0-4FF7-877D-C9E580BD8AB6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0c58f04ea13abf4dbc59eaa1c7a66393382bd291","datavalue":{"value":"1338.68227","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691591$4AD1E074-F9C3-4BFB-A76C-535D2CF2BEB1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7eeba6660a6c16b2a7a1c0eadcaaa59f25a43d0d","datavalue":{"value":{"entity-type":"item","numeric-id":558364,"id":"Q558364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q691591$875934FC-42BF-4127-86ED-8532740B4763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"01e048c609c571a9032d2c0f19ccde9301c9fc1f","datavalue":{"value":{"entity-type":"item","numeric-id":236475,"id":"Q236475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q691591$F601FD8C-DFC1-4813-9569-AEA74092F048","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q691591$FBE73492-A16A-413C-AFE5-94D31B0E572E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0fd3ad4961dd3b754cee18b6f99fcca42b4edd99","datavalue":{"value":{"time":"+2012-12-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q691591$AC9FC6BD-18F3-4CA9-B324-8006A6FE944F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f07e68c72b434297ba96feb81c7e71e201019fbe","datavalue":{"value":"https://arxiv.org/abs/1109.5801","type":"string"},"datatype":"url"},"type":"statement","id":"Q691591$B5AC88DF-8ABA-4A7D-8497-00668106E6BA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a7e4f439b67c2d94f0e5ec854e62aec74a7b23a","datavalue":{"value":"A well-known theorem by \\textit{M. Morse} and \\textit{G. A. Hedlund} [Am. J. Math. 60, 815--866 (1938; Zbl 0019.33502); ibid. 62, 1--42 (1940; Zbl 0022.34003)] states that if \\(x \\in A^{\\mathbb{N}}\\), where \\(A\\) is a finite alphabet, then \\(x\\) is ultimately periodic if and only if there exists \\(n\\) such that the number of different factors of length \\(n\\) appearing in \\(x\\) is bounded from above by \\(n\\). A version of this theorem applies to any subset \\(M\\) of \\(\\mathbb{N}\\) by considering its characteristic sequence over the alphabet \\(\\{0,1\\}\\), the ultimate periodicity of this sequence translating to \\(M\\) being a finite union of arithmetic progressions. In this very interesting paper, the authors provide a complete extension of this fundamental theorem to an arbitrary higher dimension \\(d\\), \\(d \\geq 2\\). They also obtain a characterization of sets \\(M\\) in \\(\\mathbb{Z}^d\\) defined by a first-order formula of the Presburger arithmetic \\(\\langle \\mathbb{Z}<, + \\rangle\\) (this is their notion of periodicity). To do so, they estimate the number of different blocks of size \\(n\\) occurring infinitely often in \\(M\\) via the powerful criterion for definability in Presburger arithmetic due to \\textit{An. A. Muchnik} [Theor. Comput. Sci. 290, No. 3, 1433--1444 (2003; Zbl 1052.68079)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q691591$783204F4-B0E2-45C7-928F-8C0077472BD2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691591$0114EA04-8299-45F0-8B70-8DA83D3BEB43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691591$69E98769-FF1F-4D4A-90C3-1F1AF18AEC13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4920bcb5055cf3da94830f00d832c01308357d4b","datavalue":{"value":"05B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691591$EC30C87A-1F31-4E4C-817E-4F87775E57C5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e2a9060595fe494c2f50de6aad5ab614ea034bc","datavalue":{"value":"6111989","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691591$3FE13BCB-62E0-48C6-BB4E-1861DFEB3207","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5dc7a033c303fcc84584a203b0b7ae192902143","datavalue":{"value":"Morse-Hedlund theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q691591$04BEBEF7-EC1D-4646-956F-B44977201E8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e5e6e64f7f171dc89f3c77310230730ce57088b","datavalue":{"value":"Presburger arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q691591$10E77BFA-3D40-45DE-B4F4-74B554BD4A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e77f89c43f407c67d3af68162dfa8983d4c6a887","datavalue":{"value":"ultimate periodicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q691591$CF55904B-832A-4AD0-A1AB-A9B24258759C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a50e0ff63a33ef215b79c50a05577b0042ebd452","datavalue":{"value":"recurrent blocks","type":"string"},"datatype":"string"},"type":"statement","id":"Q691591$AAE7347A-C103-46F4-9BDF-7A0394FC22AC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3f9e311a53969bed982204d1446a9d77dda26ac9","datavalue":{"value":{"entity-type":"item","numeric-id":591667,"id":"Q591667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q691591$D0E603F5-B7AB-4977-9096-B196BF49FDC2","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":"Q691591$976CCE01-59C1-4773-8BFB-0F5A8D42C01B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2f436140afb1fb3e83f50a580244a1192a5cb223","datavalue":{"value":"W1999186591","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691591$FD7A9670-BD34-4FC8-A075-DE5E13FB184D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6b5ae83333873d040c12a3079632dee94be71710","datavalue":{"value":"10.1016/J.EJC.2012.08.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691591$EFEAB72E-E226-4E05-B120-DA064C77BB84","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9ad4c1da7059b4d73ae1d339446161feeade185","datavalue":{"value":{"entity-type":"item","numeric-id":2708947,"id":"Q2708947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccdd963c2f764dda8c479785f8a866341a80f179","datavalue":{"value":{"amount":"+0.7399498224258423","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":"Q691591$FED855A4-262C-4D98-A698-D070A58172BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9198db18c16c7163bb815c500928f35587710e54","datavalue":{"value":{"entity-type":"item","numeric-id":896072,"id":"Q896072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75703cc385376a8592272f9c8aba0b593b7d7e92","datavalue":{"value":{"amount":"+0.729072630405426","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":"Q691591$F7852AFB-C8EE-4029-9D98-6D5C13B4B980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02b83ccf427a8ec58cd8546952c435980ebf63c2","datavalue":{"value":{"entity-type":"item","numeric-id":596054,"id":"Q596054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"614c20d7a7095204c19e394bdf7efc3b84f7c399","datavalue":{"value":{"amount":"+0.7218204140663147","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":"Q691591$9D4F33F6-5789-48AD-95ED-295E72E51C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c4294764f6e4cecdea2a4bbf8833776e0109cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1968575,"id":"Q1968575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11a13ffc02fa13efb304d16067dbfc319ea4d7b1","datavalue":{"value":{"amount":"+0.7202781438827515","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":"Q691591$8EFFB3D1-93F8-4FB4-828F-88AA48987810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"214a047bd13cbaa46616522d93c06270f940f9d8","datavalue":{"value":{"entity-type":"item","numeric-id":5939704,"id":"Q5939704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c84c013a623a202ae16bd1451537328af98ff36d","datavalue":{"value":{"amount":"+0.7188689708709717","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":"Q691591$8BEDAD1A-EF52-485F-9616-AD173E840C67","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Multidimensional extension of the Morse-Hedlund theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Multidimensional_extension_of_the_Morse-Hedlund_theorem"}}}}}