3
$\begingroup$

The 3SUM problem formulation: in a given set of n real numbers find 3 elements that sum to specified value S.

I am trying to understand mathematical solution of the 3SUM problem based on a polynomial of 3 degree. I found some information about 3SUM problem as a special case of geometrical problems. It says:

There are m points on a plane and it is required to check if some 3 points are located on on the same straight line. So, there is a straight line function: $y = ax + b$ and a curve: $ y = f(x) = x^3 - Sx^2 $

Intersection of the above two equations is roots of the following equation: $x^3 - Sx^2 - ax - b = 0 $

So, set of points $(a_1 , f(a_1)), ..., (a_m , f(a_m))$ contains 3 points $(a_x , f(a_x)), (a_y , f(a_y)), (a_z , f(a_z))$ on the samle straight line if and only if $a_x + a_y + a_z = S$

I can't fully percieve the relation between 3SUM problem and the above geometrical problem. AFAIK, in the equation: $x^3 - Sx^2 - ax - b = 0 $ variable $a$ represents set of points $(a_1 , f(a_1)), ..., (a_m , f(a_m))$ and probably all real numbers in which I search for some 3 numbers that sum to S. So 3 numbers $a_x + a_y + a_z$ sum to S if all of them are on the same line. But what x, y, z represent here? What is $a_z$ or $a_y$? And what is coefficient before $x^3$ equal to? How do I define b?

Can someone clarify relation between 3SUM problem and the above geometric problem?

$\endgroup$
2
$\begingroup$

Consider the problem of finding whether the list $a_1,\ldots,a_n$ contains $d$ points summing to $S$. We assume that these points are all distinct.

Let us suppose that the $d$ points $a_{i_1},\ldots,a_{i_d}$ do sum to $S$. All of these points are roots of the polynomial $$ (x-a_{i_1})(x-a_{i_2})\cdots(x-a_{i_d}) = x^d - Sx^{d-1} - P_{d-2}(x), $$ where $P_{d-2}$ is a polynomial of degree at most $d-2$; the point is that we know that the coefficient of $x^{d-1}$ is $-S$, since (in this case) it equals the negative sum of the roots.

In view of this, we are motivated to consider the points $p_i = (a_i, a_i^d - Sa_i^{d-1})$. If $a_{i_1},\ldots,a_{i_d}$ sum to $d$ then the points $p_{i_1},\ldots,p_{i_d}$ all lie on the polynomial $y = P_{d-2}(x)$ of degree at most $d-2$ (we have seen that above).

Conversely, suppose that there exist $d$ points $p_{j_1},\ldots,p_{j_d}$ which all lie on a polynomial $y = Q_{d-2}(x)$ of degree at most $d-2$. This means that these points satisfy $$ a_{j_t}^d - Sa_{j_t}^{d-1} = Q_{d-2}(a_j), \text{ for $j=1,\ldots,d$}. $$ Stated differently, the values $a_{j_1},\ldots,a_{j_d}$ are all roots of the polynomial $$ Q = x^d - Sx^{d-1} - Q_{d-2}(x). $$ Since $a_{j_1},\ldots,a_{j_d}$ are all distinct (by assumption) and a polynomial of degree $d$ has at most $d$ roots, we conclude that $a_{j_1},\ldots,a_{j_d}$ are all the roots of $Q$, which means that $$ Q = (x - a_{j_1}) (x - a_{j_2}) \cdots (x - a_{j_d}), $$ implying that $S = a_{j_1} + \cdots + a_{j_d}$, as before.

Summarizing, the $d$ values $a_{i_1},\ldots,a_{i_d}$ sum to $S$ if and only if the points $p_{i_1},\ldots,p_{i_d}$ lie on a polynomial of degree at most $d-2$. Stated differently, there are $d$ values summing to $S$ if and only if there are $d$ points lying on a polynomial of degree at most $d-2$.

This criterion should be contrasted with the fact that every $d$ points lie on some polynomial of degree at most $d-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.