## Finding local patterns in a circular list

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?

-
 What if the pattern does not occur in the list? Is the goal to find an $i$ such that $P(i)$ holds whenever one exists, or are you only interested in patterns that occur in every list? – Emil Jeřábek Feb 21 2012 at 16:42 @Emil: Yes, the algorithm should return either i or "fail". However, I have a gut feeling that the answer might be related to your question. I didn't think of a pattern that can be found in $O(\log n)$ steps other than a few that always occur somewhere. – Brendan McKay Feb 22 2012 at 0:09 I am reminded of sorting routines for integers and (Knuth's?) rule that sorting circuits can be tested on just inputs of 0's and 1's. Starting with sorting circuits and using a citation index, you might find relevant literature for this problem. I think it might be easier to list those patterns which have a worst or average case time in greater than O(n) steps. Do you have any results on runtime? I suspect "or" to preserve runtime, but not much else. Gerhard "Ask Me About System Design" Paseman, 2012.02.21 – Gerhard Paseman Feb 22 2012 at 0:32 excuse, in greater than O(logn) steps. Gerhard "Have An Exponentially Nice Day" Paseman, 2012.02.21 – Gerhard Paseman Feb 22 2012 at 0:34 Well, here is a vague set of sufficient conditions: - the pattern always holds somewhere on a circular list - the pattern always holds somewhere on a linear list with property $x$. - given a circular list or a linear list with property $x$, we can find, in $O(\plog n)$ time, a linear sublist with property $x$ containing at most $(1-\epsilon)$ of the nodes. – Andrew D. King Feb 22 2012 at 1:48
show 1 more comment

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$.

-
 I think you need to change (k+1) to something like (2k+1) to have the pigeonhole argument go through. Nice result otherwise. Gerhard "Sometimes Checks For Fencepost Errors" Paseman, 2012.02.23 – Gerhard Paseman Feb 23 2012 at 22:42 Ah, I think I misread. I imagine a query as checking k+1 consecutive values in the circle. If indeed a query checks only one value, then your arithmetic is correct. Gerhard "Sometimes Reads Things As Intended" Paseman, 2012.02.23 – Gerhard Paseman Feb 23 2012 at 22:46 I think Emil's argument is solid and nice. Next, the circular lists with a single decrease, or with a single increase, severely limit the nature of a pattern that occurs in every sufficiently long circular list, which gives some hope of completing the task. A useful exercise might be $(x_i\lt x_{i+1})\wedge(x_{i+1}\gt x_{i+3})$. This occurs in all long circular lists but it doesn't necessarily occur near each local maximum. Can we find it in $O(\log n)$ time? – Brendan McKay Feb 23 2012 at 23:08

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.

-
Great! It generalizes to any pattern implied by $P(i)=\bigwedge_{1\le|j|\le c}(x_i\gt x_{i+j})$ for constant $c$. I'll give a different proof. $P(i)$ has the property $Q_c$: it occurs in every linear list whose maximum value does not occur in the first or last $c$ positions. Make such a linear list (or find $P(i)$) by examining $O(1)$ consecutive elements (about $4c$ is enough). Once we have a linear list with property $Q_c$, examine $O(1)$ consecutive elements in the middle to recurse on either the left or right halves. Does this one and the opposite one (minimum) give the complete answer? – Brendan McKay Feb 25 2012 at 3:56