The shortest common superpattern conjecture

About 24 years old · traced to

Let n(l,m)n(l,m) be the length of the shortest word containing every pattern of length mm on at most ll letters. In the conjecture below, ll is a positive integer.

Shortest common superpattern conjecture. For any l≥1l\ge 1,

n(l,l)=l2−l+1.n(l,l)=l^2-l+1.

This would show that the previously stated upper bound n(l,m)≤l(m−1)+1n(l,m)\le l(m-1)+1 is sharp when m=lm=l. The source says that the matching lower bound is apparent in this case but that it has not been proved.

References

Primary source

A. Burstein, Peter Hästö and T. Mansour, “Packing patterns into words”, arXiv:math/0212343 (2003).

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.