[Solved]: Is detecting "doubly" arithmetic progressions 3SUM-hard?

Problem Detail: 

This is inspired by an interview question.

We are given an array of integers $a_1, \dots, a_n$ and have to determine if there are distinct $i \lt j \lt k$ such that

• $a_k - a_j = a_j - a_i$
• $k - j = j - i$

i.e, the sequences $\{a_i, a_j, a_k\}$ and $\{i,j,k\}$ are both in arithmetic progression.

There is an easy $O(n^2)$ algorithm for this, but finding a sub-quadratic algorithm seems elusive.

Is this a known problem? Can we prove 3SUM-hardness of this? (or maybe provide a sub-quadratic algorithm?)

If you like, you can assume $0 \lt a_1 \lt a_2 \lt ... \lt a_n$ and that $a_{r+1} - a_{r} \le K$ for some known constant $K > 2$. (In the interview problem, $K = 9$).

Asked By : Knoothe

Answered By : JeffE

This is an open problem.

Possibly some weak form of 3SUM-hardness could be proved by adapting a result from Mihai Pǎtrașcu's STOC 2010 paper "Towards Polynomial Lower Bounds for Dynamic Problems". First, let me define a sequence of closely related problems. The input to each problem is a sorted array $A[1..n]$ of distinct integers.

• 3SUM: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = A[k]$?

• Convolution3SUM: Are there indices $i<j$ such that $A[i] + A[j] = A[i+j]$?

• Average: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = 2 A[k]$?

• ConvolutionAverage: Are there indices $i<j$ such that $A[i] + A[j] = 2A[(i+j)/2]$? (This is the problem you're asking about.)

In my PhD thesis, I proved that all four of these problems require $\Omega(n^2)$ time in a decision-tree model of computation that allows only queries of the form "Is $\alpha A[i] + \beta A[j] + \gamma A[k] + \delta$ positive, negative, or zero?", where $\alpha,\beta,\gamma,\delta$ are real numbers (that don't depend on the input). In particular, any 3SUM algorithm in this model must ask the question "Is $A[i] + A[j]$ bigger, smaller, or equal to $A[k]$?" at least $\Omega(n^2)$ times. That lower bound doesn't rule out subquadratic algorithms in a more general model of computation — indeed, it is possible to shave off some log factors in various integer RAM models. But nobody knows what sort of more general model would help more significantly.

Using a careful hashing reduction, Pǎtrașcu proved that if 3SUM requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then Convolution3SUM requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time. Thus, it's reasonable to say that Convolution3SUM is "weakly 3SUM-hard". For example, if Convolution3SUM can be solved in $O(n^{1.8})$ time, then 3SUM can be solved in $O(n^{1.9})$ time.

I haven't ground through the details, but I'd bet that a parallel argument implies that if Average requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then ConvolutionAverage requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time. In other words, ConvolutionAverage is "weakly Average-hard".

Unfortunately, it is not known whether Average is (even weakly) 3SUM-hard! I suspect that Average is actually not 3SUM-hard, if only because the $\Omega(n^2)$ lower bound for Average is considerably harder to prove than the $\Omega(n^2)$ lower bound for 3SUM.

---

You also ask about the special case where adjacent array elements differ by less than some fixed integer $K$. For 3SUM and Average, this variant can be solved in $O(n \log n)$ time using Fast Fourier transforms as follows. (This observation is due to Raimund Seidel.)

Build a bit vector $B[0..Kn]$, where $B[i]=1$ if and only if the integer $A[1]+i$ appears in the input array $A$. Compute the convolution of $B$ with itself in $O(Kn\log Kn) = O(n\log n)$ time using FFTs. The resulting array has a non-zero value in the $j$th position if and only if some pair of elements in $A$ sum to $2A[1] + j$. Thus, we can extract a sorted list of sums $A[i]+A[j]$ from the convolution in $O(n)$ time. From here, it's easy to solve Average or 3SUM in $O(n)$ time.

But I don't know a similar trick for Convolution3SUM or ConvolutionAverage!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10681