On non-repetitive sequences of arithmetic progressions:the cases k∈{4,5,6,7,8}

Abstract

A k-Thue sequence is a sequence in which every d-subsequence, for 1⩽d⩽k, is non-repetitive, i.e. it contains no consecutive equal subsequences. In 2002, Grytczuk proposed a conjecture that for any k, k+2 symbols are enough to construct a k-Thue sequence of arbitrary lengths. So far, the conjecture has been confirmed for k∈{1,2,3,5}. Here, we present two different proving techniques, and confirm it for all k, with 2⩽k⩽8.

k-Thueova posloupnost je posloupnost, v které každá d-podposloupnost, pro 1⩽d⩽k, je nerepetitivní. V r. 2002 Grytczuk navrhl hypotézu, že pro všechny k, k+2 symbolů stačí na konstrukci k-Thueové posloupnosti libovolných délek. Hypotéza byla dosud dokázaná pro k∈{1,2,3,5}. V článku prezentujeme dvě různé techniky důkazu, a potvrdíme to pro všechny k, kde 2⩽k⩽8.