Finding local patterns in a circular list

Question

Consider a list $\boldsymbol{x}=x_0,x_1,\ldots,x_{n-1}$, which we consider to be circular by taking the subscripts modulo $n$. The entries in the list are distinct integers.

A local pattern is a Boolean expression $P(i)$ involving inequalities between the values $x_i,x_{i+1},\ldots,x_{i+k}$ for some constant $k$. For example, we might have $P(i)=(x_i\lt x_{i+1})\wedge(x_i\lt x_{i+2})$. "Finding $P~$ in $\boldsymbol{x}$" means finding a value of $i$ for which $P(i)$ is true, or determining that there is no such $i$.

Trivially, we can find any local pattern in $\boldsymbol{x}$ in $O(n)$ time just by trying each $i$. Perhaps surprisingly, some nontrivial local patterns can be found in $O(\log n)$ time. Consider the pattern for a local minimum $P(i)=(x_i\gt x_{i+1})\wedge(x_{i+1}\lt x_{i+2})$. Choose any three distinct entries $x_i,x_j,x_k$, where $x_j$ is the least. Without loss of generality, we can assume that $0\le i\lt j\lt k\lt n$. Let $\ell~$ be the midpoint (rounded towards $j$) of the longest of the intervals $[i,j]$ and $[j,k]$. If $x_j\lt x_\ell$, $x_j$ is the least of $x_i,x_j,x_\ell$, while if $x_j\gt x_\ell$, $x_\ell$ is the least of $x_j,x_\ell,x_k$. It is easy to see that continuing in this fashion finds a local minimum in $O(\log n)$ steps.

The question is: which local patterns can be found in $O(\log n)$ steps?

Answer 1

Here is a partial answer, confirming Brendan’s suspicion expressed in the comments.

Let $P$ be a pattern as above, and assume $n>k$ is such that $P$ is satisfiable, but fails to occur in some circular list of length $n$. Then finding $i$ such that $P(i)$ requires time (= number of queries for $x_j$) at least $\Omega(n)$ (namely, $n/(k+1)$) on lists of length $n$.

Proof: Assume for contradiction that $A$ is an algorithm solving the problem using less than $n/(k+1)$ queries. Fix an $\boldsymbol x$ such that $P$ does not occur in $\boldsymbol x$, and run $A$ on $\boldsymbol x$. It has to reply “$P$ does not occur” after querying less than $n/(k+1)$ values of $x_j$. By the pigeonhole principle, there exists an $i$ such that none of $x_i,x_{i+1},\dots,x_{i+k}$ were queried during the computation of $A$. Since $P$ is satisfiable, we can construct a new list $\boldsymbol y$ from $\boldsymbol x$ by permuting $x_i,x_{i+1},\dots,x_{i+k}$ in such a way that $P(i)$ holds. Then $P$ occurs in $\boldsymbol y$, but $A$ fails to find it: we did not change any values of $\boldsymbol x$ used in the computation of $A$, hence the runs of $A$ on $\boldsymbol x$ and $\boldsymbol y$ are identical, and $A$ falsely reports that $P$ does not occur in $\boldsymbol y$.

Answer 2

Here is a solution to the exercise Brendan assigned in his comment to Emil's partial answer. An occurrence of the Boolean expression there can be found with a fairly straightforward bisection.

To begin, let's add one more inequality, namely $x_{i+1} \gt x_{i+2}$, so that we're now looking for a stretch of four consecutive terms where the largest occurs in the second position. (If $Q(i)$ implies $P(i)$ and you find $Q(i)$, then you've also found $P(i)$.) Now start by sampling two sets of four consecutive terms that are opposite one another on the circle, and look for the largest of these eight values. If this maximum is in the second position among its group of four, you're done. Otherwise, cut the circle so that the maximum is either the first term in the "right" group or one of the last two in the left group. (Note: You might actually already be done by this point anyway, in case the group that doesn't have the overall maximum has its own maximum in its second position, but I'm just going to ignore that and not bother to check on anything but the overall biggest number.)

Now bisect: Take another group of four consecutive terms roughly halfway between the two current groups. If the second term in this group is a new overall maximum, you're done. Otherwise, continue the bisection on the side that contains the maximum. In $O(\log n)$ steps, this will produce a stretch of consecutive terms containing the overall maximum (of the values sampled) with at least one smaller term to its immediate left and two smaller terms to its immediate right.