{"entities":{"Q6546706":{"pageid":14157860,"ns":120,"title":"Item:Q6546706","lastrevid":55671901,"modified":"2026-02-17T20:45:51Z","type":"item","id":"Q6546706","labels":{"en":{"language":"en","value":"Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7856125"}},"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":"Q6546706$04322FC3-895B-478B-AD6F-A03CB5CDB09E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8701b93c66868a1fe81b6100358e3a2cde3772d5","datavalue":{"value":{"text":"Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6546706$7B74FD1B-361B-40A2-ADB7-94A8B5F8F645","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"91349a9b7d7d68ac78e800b4b210ce7860b2c180","datavalue":{"value":"1543.11031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6546706$6F43E918-66BE-4ECE-A8D4-092C7E140CE5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"acbe3fcdaa2e72f3bce067779bfee150bff0b503","datavalue":{"value":{"entity-type":"item","numeric-id":405317,"id":"Q405317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$57EC69C5-CBBE-44AC-BE18-CF72B814C284","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7156ae6288d1cd7ff602ff259046eb2abb40ec71","datavalue":{"value":{"entity-type":"item","numeric-id":2882724,"id":"Q2882724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$700499CB-8C3A-4D7D-AE55-46BAC6D01163","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7fb46e7518608b58d8a533d1b66c78a1a687e910","datavalue":{"value":{"time":"+2024-05-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6546706$D68278D2-5015-4C68-9246-549259EFFAD5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3a492ae1f294ceb26087cd4f005814ede2afff0b","datavalue":{"value":"The cyclic complexity \\(c_x(n)\\) of an infinite word \\(x\\) was defined in [\\textit{J. Cassaigne} et al., J. Comb. Theory, Ser. A 145, 36--56 (2017; Zbl 1369.68271)] as the number of length-\\(n\\) factors of \\(x\\), where factors that are the same, up to cyclic shift, are only counted once. Unlike the classical subword complexity, it is not obliged to be \\(k\\)-regular if the word is \\(k\\)-automatic. \\textit{C. Krawchuk} and \\textit{N. Rampersad} [Integers 18A, Paper A12, 13 p. (2018; Zbl 1429.68203)] proved that nevertheless, the cyclic complexity of the classical \\(2\\)-automatic Thue-Morse word \\(t\\) is \\(2\\)-regular and can be described by a bulky linear representation. That linear representation does not directly allow to establish the asymptotic upper and lower bounds for \\(c_t(n)\\) which were just conjectured in the initial paper: \\N\\[ \\N\\lim \\sup c_t(n)/n = 2 \\mbox{ and } \\lim \\inf c_t(n)/n = 4/ 3.\\N\\] \\NHere, the author proves these bounds by induction, using both a careful case study and automated proofs with Walnut software.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6546706$44F383B4-C534-42F7-B30F-F6D57FD5B334","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1270526a40b4e0731730a3abee5a1d4390b5770e","datavalue":{"value":{"entity-type":"item","numeric-id":1750220,"id":"Q1750220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$DA6B3E67-9BC1-4C55-B6B4-F3F4338BA756","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1d3e055a17ce7fb6036131cf10d782136e2d9314","datavalue":{"value":"11B85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6546706$C1663140-A96F-4ADC-96EF-52A100F33982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6546706$83742DBC-549B-4017-B329-22FE274AA55B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"07fb8eaeecd6111f32a3ce5a5ab3e33b0ac7e92e","datavalue":{"value":"7856125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6546706$0BD69C6D-E654-43DE-A15A-0B243DF8CA03","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"084f8d4c06bc6742586096caab4934410b0f2e2c","datavalue":{"value":"cyclic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6546706$7E196672-D074-4B95-81AC-C7B46A62D896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97fc6aafae5c037c3f20c24557f1742be3fa4ba8","datavalue":{"value":"Thue-Morse word","type":"string"},"datatype":"string"},"type":"statement","id":"Q6546706$722D9331-DB7B-4F96-A2F6-7940F35E0BF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76e3cb692680e45dee53b7a34d71b20fb1a49380","datavalue":{"value":"automatic words","type":"string"},"datatype":"string"},"type":"statement","id":"Q6546706$F76C485E-09B9-4C23-8F0F-7B47AA320FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfe630b533a1f5c36674b5ff709bb809b60efb5c","datavalue":{"value":"regular sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q6546706$6CA957D1-8C16-4A8B-B209-B20C9F84841A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1225367b1c58aa38751252c599f129a0a0e283bf","datavalue":{"value":"Walnut","type":"string"},"datatype":"string"},"type":"statement","id":"Q6546706$2A126909-E34C-4259-AA6E-4939BEC66AE4","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":"Q6546706$49699866-25D4-492D-BE56-49B5489AA12D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"72481d20709a1d21a8c0b270cd78024e358f70f8","datavalue":{"value":{"entity-type":"item","numeric-id":1853729,"id":"Q1853729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$96CEEF60-6974-4AF7-BF00-2165E2981E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"223550176370d5043c2c4ccaed292fb5cb47cccf","datavalue":{"value":{"entity-type":"item","numeric-id":4330617,"id":"Q4330617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$E77F708E-8CFE-4C35-A506-5FD9C369A5AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e141f7d30bc3aed8fcd4bcdb12a2bfc0dc119a4c","datavalue":{"value":{"entity-type":"item","numeric-id":3056218,"id":"Q3056218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$F6110387-356A-4A3D-B696-ED80820DBF61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5262acdef5ab5c226bd34bafb2af823d2460adc7","datavalue":{"value":{"entity-type":"item","numeric-id":507796,"id":"Q507796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$E4F57CB9-AF02-4F18-ADC8-1D88D49B1172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41118f4aa64488a0061c3b7bdbc6717fa841ccac","datavalue":{"value":{"entity-type":"item","numeric-id":5393498,"id":"Q5393498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$EB683F91-BCF9-478E-99FC-F85354A6AFF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"266915684b91f0d11b34df57e5858240074ada9e","datavalue":{"value":{"entity-type":"item","numeric-id":5270140,"id":"Q5270140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$6410C3E1-267A-470E-9C74-D84AAB534BBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b542e497e0b083d710ad6023ea0d3876afc4450","datavalue":{"value":{"entity-type":"item","numeric-id":4037461,"id":"Q4037461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$0AD8077B-9F86-4731-95E9-BE6934EFCF91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40d85267837c33609465eb15f4a7ef4d4c8d3f18","datavalue":{"value":{"entity-type":"item","numeric-id":5300845,"id":"Q5300845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$2B2F92CF-AAF4-4184-AE53-0077A2DD0EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e405220c880f6f4d4872a6e11931d2113f27836","datavalue":{"value":{"entity-type":"item","numeric-id":5384332,"id":"Q5384332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$87CA057B-B992-43E2-A9D4-7846E7BE06A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce48dbd9ef8cc3a6dafc71e17122de42c17e802d","datavalue":{"value":{"entity-type":"item","numeric-id":5429114,"id":"Q5429114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$7443D9C9-6B20-470C-BD13-7C0633382284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"104e36857254fbe11d358a28c425c95f11cb56c0","datavalue":{"value":{"entity-type":"item","numeric-id":3074533,"id":"Q3074533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$E9225DFA-B1B4-43AA-9111-D1198E0F5071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c91060cdeca0154f02bb1775d35e9b9faddf7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":2140455,"id":"Q2140455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6546706$CFA64775-4E95-424D-B17C-8DFF915A2D4A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"257ca421d2405a3c45e508d5179c133b70a32bd4","datavalue":{"value":{"entity-type":"item","numeric-id":888175,"id":"Q888175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"169e0f70b7ccfeb68b82be24b7d8fa9572f7955e","datavalue":{"value":{"amount":"+0.7859052419662476","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":"Q6546706$2045E57E-3D72-423C-9F17-9F7D202B9860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09d38e2a36f26f130025770fa9efb50ced37c8f4","datavalue":{"value":{"entity-type":"item","numeric-id":2020439,"id":"Q2020439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"176bd206397f4d9f73212a1061fde752382995aa","datavalue":{"value":{"amount":"+0.7817299365997314","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":"Q6546706$41D3EF5B-FA32-4676-9856-23A9BAE0C774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7fcfe33899093d98ae4084faa0c65f86561f810","datavalue":{"value":{"entity-type":"item","numeric-id":5384332,"id":"Q5384332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"874f2448724a2422421be217cea7010f99acdb1b","datavalue":{"value":{"amount":"+0.7764992713928223","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":"Q6546706$7588F933-BBBA-49B4-BBE6-3989AD771D4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8acbe251f60557555b8f20ab0898f3a75e6d1205","datavalue":{"value":{"entity-type":"item","numeric-id":507796,"id":"Q507796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e1207a0116405936835456dba15051fb0e9dc90","datavalue":{"value":{"amount":"+0.7606282830238342","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":"Q6546706$68FB62E9-E081-4865-B84E-DD7CA90992CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"587a9101bcf3c957972528423c16dfd67cf96663","datavalue":{"value":{"entity-type":"item","numeric-id":2420616,"id":"Q2420616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59ade799aebc8966bc615d3a650fa55189777841","datavalue":{"value":{"amount":"+0.7597596049308777","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":"Q6546706$16A5DCCA-9027-4EB5-8353-AD20BB9E6CA4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6546706","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6546706"}}}}}