On a reconstruction problem for sequences (Q1352885)

Given a word \(X\) of length \(n\) with terms from an alphabet \(\Sigma\), consider the multiset \(D_k(X)\) of all \(k\)-subwords of \(X\). When is it possible to reconstruct the word \(X\) from the multiset \(D_k(X)\)? The authors prove that any word of length \(n\) is ``\(k\)-reconstructible'' if \(k\geq\lfloor \frac {16} {7}\sqrt n\rfloor +5\). This improves the known bound \(\lfloor n/2\rfloor\), which is due to \textit{B. Manvel et al.} [Discrete Math. 94, No. 3, 209-219 (1991; Zbl 0746.05045)]. Quite interestingly, the authors prove their improvement by relating the problem to a classical problem of Diophantine analysis, usually referred to as the Prouhet-Tarry-Escott problem, which is about finding two distinct solutions for a certain system of linear Diophantine equations. The improved bound then follows immediately from a bound for the latter problem, recently found by \textit{P. Borwein} and \textit{C. Ingalls} [Enseign. Math. II. Sér. 40, No. 1-2, 3-27 (1994; Zbl 0810.11016)].