{"entities":{"Q507407":{"pageid":509174,"ns":120,"title":"Item:Q507407","lastrevid":62359914,"modified":"2026-04-11T05:33:27Z","type":"item","id":"Q507407","labels":{"en":{"language":"en","value":"An abelian periodicity lemma"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6680851"}},"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":"Q507407$9240A9E4-772C-4CDF-9C99-B0BBE34CBD27","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6cc0365c6cc5c056ee89cfd57377188e09aaa227","datavalue":{"value":{"text":"An abelian periodicity lemma","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q507407$25D09148-3F74-4751-BF8E-95831DE4260C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dcdac852d7a5becfd1e40e240636f34b2806d7ee","datavalue":{"value":"1362.68241","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507407$3059728A-4D22-4DFB-A947-B62A2313B13C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507407$F9A7B2A2-9EF3-4E3E-94D4-0A5C193035CC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"69224595960101be6ec21574e4c403135d7942f5","datavalue":{"value":{"time":"+2017-02-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q507407$1DD2C297-4FB3-43EE-AAE7-D47A6E5C4CE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"72355be93b3c119480bd1bc174303b71cca2ae7b","datavalue":{"value":"Denote the length of a word \\(w\\) by \\(|w|\\) and the Parikh vector of \\(w\\) by \\({\\mathcal P}(w)\\), which records the number of occurrences of each letter in \\(w\\). For two words \\(u\\) and \\(v\\), \\({\\mathcal P}(u)={\\mathcal P}(v)\\) if and only if \\(u\\) is a permutation of \\(v\\) and \\({\\mathcal P}(u)\\leq {\\mathcal P}(v)\\) if and only if \\(u\\) can be obtained by permuting and, possibly, deleting some of the letters of \\(v\\). A word \\(w\\) has \\textit{abelian period} \\(p\\) if \\(w=u_0u_1u_2\\cdots u_mu_{m+1}\\), where \\(m \\geq 1\\), \\(|u_1|=|u_2|=\\cdots=|u_m|=p\\), \\(|u_0|>0\\), and \\({\\mathcal P}(u_0) \\leq {\\mathcal P}(u_1)={\\mathcal P}(u_2)=\\cdots={\\mathcal P}(u_m)\\geq {\\mathcal P}(u_{m+1})\\). The reviewer et al. [``Fine and Wilf's theorem for abelian periods in partial words'', in: Proceedings of the 13th Mons theoretical computer science days, 2010. Amiens: Univ. de Picardie Jules Verne (2010)] proved that if a word \\(w\\) has abelian periods \\(p\\) and \\(q\\) with \\(\\operatorname{gcd}(p,q)=d\\), \\(d> 1\\), and \\(\\left||u_{0}|-|v_{0}|\\right|\\) is a multiple of \\(d\\), then \\(w\\) has at most cardinality \\(d\\) for \\(\\left|w\\right|\\geq 2 \\,\\operatorname{lcm}(p,q)-1\\). They conjectured that if a word \\(w\\) has abelian periods \\(p\\) and \\(q\\) with \\(\\operatorname{gcd}(p,q)=d\\), \\(d> 1\\), and \\(\\left|\\left|u_0\\right|-\\left|v_0\\right|\\right|\\) is not a multiple of \\(d\\), then \\(w\\) has at most cardinality \\(d\\) for \\(\\left|w\\right|\\geq 2 \\, \\operatorname{lcm}(p,q)-2\\) and they proved that their conjecture is true under some conditions on \\(p\\) and \\(q\\). In this very interesting paper, the author proves that the conjecture is true. Thus, a word \\(w\\) having abelian periods \\(p\\) and \\(q\\) with \\(\\operatorname{gcd}(p,q)=d\\), \\(d\\geq1\\), has at most cardinality \\(d\\) for \\(\\left|w\\right|\\geq 2 \\, \\operatorname{lcm}(p,q)-1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q507407$40253D85-2AE6-4DA0-928E-D8D2B9F69687","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":"Q507407$626FC11A-15F3-4ECB-ACB1-4AA4E2536BE5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507407$78652681-EE55-43BF-A649-55F30D35D7BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2a95bc0fa5a79489821a326911ccc4493083889b","datavalue":{"value":"6680851","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507407$64BCE760-2A1C-46BE-B1CA-EFFBFB89B1F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49f14d7f162703e75f5c2fd3141793b1dc4216c2","datavalue":{"value":"periodicity lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q507407$646E11F1-E544-4A64-A1B7-0B08CA9BA5AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e55b9f6371b66ff10effe367c8ebbaea97b45b6","datavalue":{"value":"abelian periodicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q507407$06E0D853-5C2D-4C7F-BC6A-615867848BE2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b28c6f6ce4209a418adaa2986ad2ae7359e1de4","datavalue":{"value":{"entity-type":"item","numeric-id":686459,"id":"Q686459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507407$5C75FF4B-37A2-4181-AA3B-F85C04F0198F","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":"Q507407$72D891F6-EAE6-4EE5-BF6A-70EE8C9D94C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1abeb3b094e0dc0173525adb7ef25c8cd1eacb8a","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2015.12.014","type":"string"},"datatype":"url"},"type":"statement","id":"Q507407$E0044748-0574-4F81-ABA7-E31C739385D3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"172b532f3d47ae7f91bf6c02da70a6ea5b08f297","datavalue":{"value":"W2283259025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507407$047BC03A-39D4-4C78-BF8F-0A04690CCA7D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2cbb1ce24a3d3f1ce67b10a7be205a562dc13e59","datavalue":{"value":"Q124813705","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507407$4226BFD2-1BC4-4B80-B934-17D93BC416C0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2382c07c5bad6aff75130283101f3d1628a62c84","datavalue":{"value":{"entity-type":"item","numeric-id":5359492,"id":"Q5359492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507407$89FDED6D-21B3-4B79-867B-A49DE174F66B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32023ba61a423c14e911333b95b53c0e06b09c63","datavalue":{"value":{"entity-type":"item","numeric-id":5397716,"id":"Q5397716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507407$78E2D94B-92CD-4A68-BD3D-76279412FECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c02c6f5e21ad186282aaf9339cfd44f3efd2d42a","datavalue":{"value":{"entity-type":"item","numeric-id":3396591,"id":"Q3396591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507407$21004185-622B-49DC-A10C-2B24572B8DA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec063e97134a956b4adef0cc993fcbb16c7d0af9","datavalue":{"value":{"entity-type":"item","numeric-id":5340253,"id":"Q5340253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507407$BD989790-E4E3-4675-81BA-05BE271B1014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a971470fccd454eb1931b81129ae986017c1dbbd","datavalue":{"value":{"entity-type":"item","numeric-id":5204304,"id":"Q5204304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507407$2756608F-A00D-4FFE-85C4-81F48BDF07D6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7adb3f06d24a6291a989d43fd5f42f66ea9b84e4","datavalue":{"value":"10.1016/J.TCS.2015.12.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507407$9D8F7258-7082-4AEF-9DFE-E6A1EBFA0330","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d8e4a25d21498b54decb71a62c4aae4b96400f0","datavalue":{"value":{"entity-type":"item","numeric-id":5397716,"id":"Q5397716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e78d59d8f04e4a310fa1c13effea13328da6298","datavalue":{"value":{"amount":"+0.858006477355957","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":"Q507407$11EB628F-C5CA-4F7A-9BCF-BC8104F58DE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9c3a083b1d1fbb2ee33c90806e8214838dde148","datavalue":{"value":{"entity-type":"item","numeric-id":2327230,"id":"Q2327230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcc60daf8b1df42ac471c40a7b22fe49cd62ce85","datavalue":{"value":{"amount":"+0.8233389258384705","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":"Q507407$25E1FA1F-0455-4A16-89F7-E302D64B8E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9488dbbdc3b33c4323577d6a92418241881c582","datavalue":{"value":{"entity-type":"item","numeric-id":4547738,"id":"Q4547738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54c469704daf97f15cf9b17f1a3f428b1b0a512d","datavalue":{"value":{"amount":"+0.792118489742279","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":"Q507407$82403182-5B66-4E1E-861E-B909D6B2F061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7eabfc74af0b563143983caaaca3773b5b531d1","datavalue":{"value":{"entity-type":"item","numeric-id":3167504,"id":"Q3167504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ce19338c2668bf287d5325b65ea5aaf22609d34","datavalue":{"value":{"amount":"+0.7919793725013733","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":"Q507407$1FC1225D-CF10-41F6-AA71-73E24515E55E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0be69be8c2de3d8e1fddb82b2c1d30d0a1389a8b","datavalue":{"value":{"entity-type":"item","numeric-id":5495424,"id":"Q5495424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de5c04b84497f6d4e0a477069c36a88f2d3f8b0f","datavalue":{"value":{"amount":"+0.7914913892745972","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":"Q507407$D6029AA8-5DDD-437C-BA71-DDA878D62A14","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An abelian periodicity lemma","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_abelian_periodicity_lemma"}}}}}