Longest arithmetic progressions in generalised Thue–Morse sequences

About 5 years old · traced to

Let p,q,n∈N+p,q,n\in\mathbb{N}^{+}, set Q=p+qQ=p+q, and let Ap,q(d)A_{p,q}(d) denote the maximum length of an arithmetic progression of difference dd occurring in the generalised Thue–Morse sequence associated with parameters p,qp,q. Assume n>2n>2. Longest-progression conjecture.

max⁡d⩽Qn+1Ap,q(d)={Ap,q(Qn−1)=Qn+Q+2,if p=q=1 and n is even,Ap,q(Qn−1)=Qn+Q,if p=q>1 and n is even,Ap,q(Qn+1)=Qn+Q,if p=q=1 and n is odd,Ap,q(Qn+1)=Qn+Q−1,if q>p=1 or p>q=1,Ap,q(Qn+1)=Qn+Q−2,if p,q>1 and p≠q or n is odd.\max_{d\leqslant Q^n+1}A_{p,q}(d)=\begin{cases} A_{p,q}(Q^n-1)=Q^n+Q+2, & \text{if }p=q=1\text{ and }n\text{ is even},\\ A_{p,q}(Q^n-1)=Q^n+Q, & \text{if }p=q>1\text{ and }n\text{ is even},\\ A_{p,q}(Q^n+1)=Q^n+Q, & \text{if }p=q=1\text{ and }n\text{ is odd},\\ A_{p,q}(Q^n+1)=Q^n+Q-1, & \text{if }q>p=1\text{ or }p>q=1,\\ A_{p,q}(Q^n+1)=Q^n+Q-2, & \text{if }p,q>1\text{ and }p\ne q\text{ or }n\text{ is odd}.\end{cases}

The preceding results establish the relevant long progressions for differences Qn+1Q^n+1, and for differences Qn−1Q^n-1 when p=qp=q; the conjecture asserts that no longer progression occurs for any difference up to Qn+1Q^n+1.

References

Primary source

Ibai Aedo, Uwe Grimm, Yasushi Nagai and Petra Staynova, “On long arithmetic progressions in binary Morse-like words”, arXiv:2101.02056 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.