{"entities":{"Q648401":{"pageid":650250,"ns":120,"title":"Item:Q648401","lastrevid":57102936,"modified":"2026-03-26T15:46:06Z","type":"item","id":"Q648401","labels":{"en":{"language":"en","value":"Nonrepetitive sequences on arithmetic progressions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5976487"}},"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":"Q648401$F1B987FB-A2F8-4C4B-AC37-86C28E303776","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eac45c0ca2d55e959efeb6e7b3c8f9ae2edb2627","datavalue":{"value":{"text":"Nonrepetitive sequences on arithmetic progressions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q648401$5874370B-6CB0-447B-B3D1-50EA851EF36A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c6de6833e15ce45d37ffea8cbc280bd66eac6105","datavalue":{"value":"1229.68063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q648401$94AC2FC0-3498-4DCF-9DA0-5D32DB78FD79","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9efe106b3c39b129b376e8258a66132030c4b918","datavalue":{"value":{"entity-type":"item","numeric-id":282742,"id":"Q282742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q648401$F4E6EA34-53D3-4ABD-BBF1-3EDC9E89A0C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc629f0be60f72a336737629e351e85a1cdd011c","datavalue":{"value":{"entity-type":"item","numeric-id":322291,"id":"Q322291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q648401$C12217E9-76EB-4D2F-8B90-0FD3EE155AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c08ad2d3f5faf85e3af6f96da86423b725b384d","datavalue":{"value":{"entity-type":"item","numeric-id":648400,"id":"Q648400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q648401$108AAC39-1922-411D-9655-68DB11482355","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q648401$111DF98F-BDEE-4A99-A1BD-E89ADF7BA3FC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6d06d6de084d6566994eb3940381939ab0e2877d","datavalue":{"value":{"time":"+2011-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q648401$205A649A-C2A7-4BAC-833E-45773DFD3EA5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0737e153dacff7b24dd1e303c57682dfbbab72e9","datavalue":{"value":"https://arxiv.org/abs/1102.5438","type":"string"},"datatype":"url"},"type":"statement","id":"Q648401$5D93BB14-68E0-4A63-A939-96DF7B9F3C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"82433e15eb27e9674c0446fbcd245917dfb17875","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p209.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q648401$2BAE87CD-D4A9-495D-82A8-0DB4569828D2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba6b125651028c004516ffe5dbfec6128737b2f6","datavalue":{"value":"Summary: A sequence \\(S=s_1s_2\\dots s_n\\) is said to be nonrepetitive if no two adjacent blocks of \\(S\\) are identical. In 1906, \\textit{A. Thue} [Christiania Vidensk.-Selsk. Skr. 1906, Nr. 7, 22 S. (1906; JFM 39.0283.01)] proved that there exist arbitrarily long nonrepetitive sequences over a 3-element set of symbols. We study a generalization of nonrepetitive sequences involving arithmetic progressions. We prove that for every \\(k\\geq 1\\), there exist arbitrarily long sequences over at most \\(2k+10\\sqrt{k}\\) symbols whose subsequences, indexed by arithmetic progressions with common differences from the set \\(\\{1,2,\\dots,k\\}\\), are nonrepetitive. This improves a previous bound of \\(e^{33}k\\) obtained by the first author. Our approach is based on a technique introduced recently by the first two authors and \\textit{P. Micek} [``A new approach to nonrepetitive sequences'' (submitted), \\url{arXiv:1103.3809}] which was originally inspired by a constructive proof of the Lov\u00e1sz local lemma due to \\textit{R. A. Moser} and \\textit{G. Tardos} [``A constructive proof of the general Lov\u00e1sz local lemma'', J. ACM 57, No. 2, Art. No. 11, 15 p. (2010), \\url{arXiv:0903.0544}]. We also discuss some related problems that can be attacked by this method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q648401$4EA547F7-A273-4D5D-B54E-E017C64E4F06","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q648401$8BC88C52-F2E5-4B44-AF93-F0A70B8864FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q648401$FBF66231-E839-4634-8262-544EAFD3C9A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"59ff1173f55ceccb7042119df1cda673726c7815","datavalue":{"value":"11B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q648401$3A2E74DD-B291-45B4-A5EF-0FCE6359DBFE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"870ff8c8c2d1c856dcc001a216a653dcb51da659","datavalue":{"value":"5976487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q648401$6A03DD0D-0E49-4F57-8137-244BB50762AE","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":"Q648401$F07FFE31-C91A-4328-930A-1C4C00132DA4","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ac414533b082e44bb81d6b810bf0d94702d1214e","datavalue":{"value":"bafkreibx7pgntblnlds432n2ltxarl5tnhixraa3hmlia7emecwl7fiybe","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q648401$3F7F5489-81F1-432C-ADA9-38C464185897","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b4bd8d0335def0d17ed47d080fda9bb566eda1b","datavalue":{"value":{"entity-type":"item","numeric-id":4909201,"id":"Q4909201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4edf2a8db5ffd9a94c70332df86f9d7b4d955ee0","datavalue":{"value":{"amount":"+0.8550068140029907","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":"Q648401$1F923313-F6FD-42B0-BA83-985BCC112A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6726d2f33d4e42a3bbb76c3680e096ed6042fde1","datavalue":{"value":{"entity-type":"item","numeric-id":2181220,"id":"Q2181220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d37ed44437ef2925c3e879c4c4ff2bbd456615e","datavalue":{"value":{"amount":"+0.8492882251739502","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":"Q648401$8C798F8C-E32C-4F44-BB82-4AFC1BC62C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca1516fd140405d143cedefb1b9139e719f922f5","datavalue":{"value":{"entity-type":"item","numeric-id":1856338,"id":"Q1856338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2efe24c6b03364df966f91ff533bf9416cd0a7a","datavalue":{"value":{"amount":"+0.8205341696739197","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":"Q648401$FBCFD825-B2EB-46BE-BF35-68FDF2D1C084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd208bb20c83084987ed60074ff3d34415ddaa33","datavalue":{"value":{"entity-type":"item","numeric-id":4798171,"id":"Q4798171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7374c375d0cdb5b6953c63756d81291b009115f","datavalue":{"value":{"amount":"+0.8204456567764282","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":"Q648401$9E41B421-367C-48CD-BE00-32EB39887EF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"159f43db476b4c21a3851f2fad34a9be3e7be47e","datavalue":{"value":{"entity-type":"item","numeric-id":941381,"id":"Q941381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faae6f31f8b2f54a17d7a921812fdf3f75e88267","datavalue":{"value":{"amount":"+0.8166807293891907","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":"Q648401$A0ED26D1-56C8-448C-A2BD-09ECCAC36A27","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:648401","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:648401"}}}}}