{"entities":{"Q557915":{"pageid":559682,"ns":120,"title":"Item:Q557915","lastrevid":62756244,"modified":"2026-04-11T08:14:59Z","type":"item","id":"Q557915","labels":{"en":{"language":"en","value":"Generalised fine and Wilf's theorem for arbitrary number of periods"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2184110"}},"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":"Q557915$6CE89F7B-67AB-4C87-8CF8-6785C75DB5C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"77709befbfd472f6ed18a503613d382a6fd69735","datavalue":{"value":{"text":"Generalised fine and Wilf's theorem for arbitrary number of periods","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q557915$2850E117-44AA-4E68-8D6D-A61E9C57B188","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"99484daee00ae8af18d99ee81ea42e9950b328e1","datavalue":{"value":"1127.68074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557915$9EA23BAE-7388-44CB-B718-ECBFAD73154B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6177d47d4fd2a30ef7d6f0d50464c7374966172d","datavalue":{"value":{"entity-type":"item","numeric-id":557914,"id":"Q557914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$E4B2AF50-1FEF-4B30-A301-8C7A449B2544","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e59e0422655bd2646fd5870f292a28530526e280","datavalue":{"value":{"entity-type":"item","numeric-id":287019,"id":"Q287019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$42FFF466-078B-4194-9F43-2EE101AF8F5A","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":"Q557915$8FE2DC41-5864-4FEF-A5D5-3D1D56AE8597","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3be35b99bc40d25914143aa31268a19fcdde1b9d","datavalue":{"value":{"time":"+2005-06-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":"Q557915$949CC0E1-AA88-4FAE-A91D-62E37EB90B75","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"09078a7b757a3e8144d620d7203774d5daaee23c","datavalue":{"value":"The notion of period of a word is central in combinatorics on words. There are many fundamental results on periods of words. Among them is the well known and basic periodicity result of Fine and Wilf which intuitively determines how far two periodic events have to match in order to guarantee a common period. More precisely, any word with length at least \\(p+q-\\gcd(p,q)\\) having periods \\(p\\) and \\(q\\) has also period the greatest common divisor of \\(p\\) and \\(q\\), \\(\\gcd(p,q)\\). Moreover, the bound \\(p+q-\\gcd(p,q)\\) is optimal since counterexamples can be provided for words of smaller length.  Fine and Wilf's result was generalized for more than two periods but the problem of finding the optimal bounds had not been settled. In this very interesting paper, the authors give an extension of Fine and Wilf's theorem for an arbitrary number of periods and prove that their bounds are optimal. More precisely, they show that any word having periods \\(p_1, \\ldots, p_n\\) and length at least the so-denoted \\({f_w}_n (p_1, \\ldots, p_n)\\), has also the greatest common divisor of \\(p_1, \\ldots, p_n\\) as period, and they prove that their bound \\({f_w}_n (p_1, \\ldots, p_n)\\) is optimal. The optimality proof is based on results of graphs associated with bounds and tuples of periods. They obtain a uniqueness result concerning extremal words for the optimal bounds (a word \\(w\\) of length \\({f_w}_n ({\\mathbf p})-1\\) is extremal for the bound \\({f_w}_n ({\\mathbf p})\\) if all integers in \\({\\mathbf p} = (p_1, \\ldots, p_n)\\) are periods of \\(w\\) but \\(\\gcd({\\mathbf p})\\) is not a period of \\(w\\)). Moreover, they give an algorithm which given an \\(n\\)-tuple of periods \\({\\mathbf p}\\), computes the optimal bound \\({f_w}_n ({\\mathbf p})\\) and an extremal word for that bound.","type":"string"},"datatype":"string"},"type":"statement","id":"Q557915$AA309A34-852A-4DC3-8DD1-842A368A2F34","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":"Q557915$D3469679-D306-4740-A7FE-6F63D39E8CC4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557915$86095099-DE35-4E67-B357-1AE217B1DAFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557915$F2D978D6-E238-4001-818E-3B11F7A90C9C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"61b1fd19a90f349ec80648624b90968c641e1ae8","datavalue":{"value":"2184110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557915$CDCBC286-EB4B-4582-8F99-8726BBCB3C92","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8967d0a934eaa6194b5afbe1fbb4e78c8127645d","datavalue":{"value":"combinatorics on words","type":"string"},"datatype":"string"},"type":"statement","id":"Q557915$2A3BAE3C-9DA4-4351-B61D-21BF8E0C5249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c420e01a4c7ebed8995727fb3d65fa03799b0a9","datavalue":{"value":"periods","type":"string"},"datatype":"string"},"type":"statement","id":"Q557915$CFDA0B4A-4DFC-44B9-A966-50617D8B1205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fe22c6d6f872ed9c3b6266971d2807c86bb723d","datavalue":{"value":"Fine and Wilf's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q557915$47DAA17E-0A56-4C3C-B9D1-6768FA0427FF","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":"Q557915$3E751542-89DF-4EEB-8894-329239039265","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4978ab6989ad64709d56768df34453bd12ee7baf","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2005.01.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q557915$4C284EF8-BDF9-4FAD-81EB-200CF992257C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b0e6071677f570dcc089b5ea1dcfe1215ba701e3","datavalue":{"value":"W1967306786","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557915$08D357C2-9BC8-4C43-9ECA-91EAD5914CE9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbbea9efe49a8fa4b049b0379279b0f54f9349ea","datavalue":{"value":{"entity-type":"item","numeric-id":1292487,"id":"Q1292487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$27B93F92-0BCF-4D72-9A3B-4FC342CE13D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8bbc326178cc09a150cac941ba53292c18929a6","datavalue":{"value":{"entity-type":"item","numeric-id":5958314,"id":"Q5958314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$14391845-616E-4288-8C2A-C9CBB1E96818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be3f5c69c13ad822e88ac6c7d835a37be1b4ae9f","datavalue":{"value":{"entity-type":"item","numeric-id":1292483,"id":"Q1292483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$9B0A9CF8-9BB9-41AD-AF9F-971A28D1B31A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52b4fff3544726f36cd6d8648e51360d5976c7b4","datavalue":{"value":{"entity-type":"item","numeric-id":1401234,"id":"Q1401234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$2FE92C27-D14A-4DE9-B6C5-6D2401B90FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe929f01fa86af5ec1780a3fd0d8f9ac3346a63b","datavalue":{"value":{"entity-type":"item","numeric-id":4714446,"id":"Q4714446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$65E1D409-C6C4-42BE-99C6-8ACFE3730939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$056FA907-BB21-42DF-A44D-9E9266A8A6FF","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":"Q557915$4AF3CF2A-BD8F-4ABC-B719-4898F2ECF2F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a159206f8580c268f1c3274abb94dabff2d95745","datavalue":{"value":{"entity-type":"item","numeric-id":2720410,"id":"Q2720410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$7526EFDD-94E9-4D26-B162-24DC3C8CF52F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2355482dbc37a911cde9b74ab32ffb5b6939f6","datavalue":{"value":{"entity-type":"item","numeric-id":3659988,"id":"Q3659988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$54610DB2-15B9-41D5-8EEF-0DFF1D7D8D02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab968868a27793512725f9615e172750ff9d631","datavalue":{"value":{"entity-type":"item","numeric-id":4529547,"id":"Q4529547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$180083EF-0879-413C-BB22-D3CA2BDC49D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2899d014680bba7232a319ad1176ea463f58d827","datavalue":{"value":{"entity-type":"item","numeric-id":1853743,"id":"Q1853743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$C8867714-C2F6-417B-B1FF-E6163E8ED118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1efac0239f1939c1b5beafe4a6de7aaf5e496796","datavalue":{"value":{"entity-type":"item","numeric-id":1433188,"id":"Q1433188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557915$AC84390D-2470-4A89-9EAB-54050623BD99","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d1e0721d4817206e60ce24ea0e4427070bfb1df3","datavalue":{"value":"10.1016/J.TCS.2005.01.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557915$48833299-4068-4354-A74D-80A4D6DF20C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ea6d1d26a2cba3e10447c7d23743da343cbb9ca","datavalue":{"value":{"entity-type":"item","numeric-id":4453440,"id":"Q4453440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1db373dfedbd32bf47e5d0ebbd7d2257513abd3","datavalue":{"value":{"amount":"+0.9776535034179688","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":"Q557915$6D17A47C-7128-422F-9B66-9A9868A8BDEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36600e1b2948ad0b3f265b5c0eb7f4d8e96caaee","datavalue":{"value":{"entity-type":"item","numeric-id":1433188,"id":"Q1433188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b40956aeece3f687caa8f9fc8f160161cdf12481","datavalue":{"value":{"amount":"+0.8987032771110535","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":"Q557915$E42D5F27-C0F3-4649-97A6-E910966FB9C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83079d7480af39ee8bbdb4822b5ac9f9565d2823","datavalue":{"value":{"entity-type":"item","numeric-id":2855629,"id":"Q2855629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bd129c7a45411efaf8d4a1a83c6efc4dd90b2d2","datavalue":{"value":{"amount":"+0.8722052574157715","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":"Q557915$D792574F-97DD-4601-A864-D91AEB3D483C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2e948f5ad80293385815bdf7e1f6f76fc1a4ee5","datavalue":{"value":{"entity-type":"item","numeric-id":4432096,"id":"Q4432096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a6e92b9ddd897dd1ea512d62d7789c98136c17f","datavalue":{"value":{"amount":"+0.867224395275116","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":"Q557915$AD063143-3AC5-4E78-BAA9-86242E62438C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5939b74ded81f51b69acdb6963e71e39e56616c","datavalue":{"value":{"entity-type":"item","numeric-id":890931,"id":"Q890931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04099c020d7d8663e676c1d4b5dae148891566c0","datavalue":{"value":{"amount":"+0.8629781007766724","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":"Q557915$9197EE2D-B053-4A26-9A36-85A01BB89B5E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalised fine and Wilf's theorem for arbitrary number of periods","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalised_fine_and_Wilf%27s_theorem_for_arbitrary_number_of_periods"}}}}}