A Lower Bound for the Parallel Complexity of Periodicity on Multi Dimensional Arrays

Given that an array \(A[i_{1}, \ldots, i_{d}]\), \(1 \leq i_1 \leq m, \ldots 1 \leq i_d \leq m\), has a \emph{period} \(A[p_{1}, \ldots, p_{d}]\) of dimension \(p_1 \times \cdots p_{d}\) if \(A[i_{1}, \ldots, i_{d}] = A[i_{1} + p_{1}, \ldots, i_{d} + p_{d}]\)
for \(i_{1}, \ldots, i_{d} = 1, \ldots, m – (p_{1}, \ldots, p_{d})\). The \emph{period} of the array is \(A[p_{1}, \ldots, p_{d}]\) for the shortest such \(q = p_{1}, \ldots, p_{d}\).

Consider this array \(A\); we prove a lower bound on the computation of the period length less than \(m^{d}/2^d\) of \(A\) with time complexity
\[
\Omega({\log \log_a m}), \text{ where } a = m^{d^2}
\]
for \(O(m^d)\) work on the CRCW PRAM model of computation.