Lower Bounds for the Number of Repetitions in 2D Strings

Abstract

A two-dimensional string is simply a two-dimensional array. We continue the study of the combinatorial properties of repetitions in such strings over the binary alphabet, namely the number of distinct tandems, distinct quartics, and runs. First, we construct an infinite family of $n\times n$ 2D strings with $\Omega (n^3)$ distinct tandems. Second, we construct an infinite family of $n\times n$ 2D strings with $\Omega (n^2\log n)$ distinct quartics. Third, we construct an infinite family of $n\times n$ 2D strings with $\Omega (n^2\log n)$ runs. This resolves an open question of Charalampopoulos, Radoszewski, Rytter, Waleń, and Zuba [ESA 2020], who asked if the number of distinct quartics and runs in an $n\times n$ 2D string is $\mathcal{O}(n^2)$.