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?
3SUM problem solution on the basis of cubic function and a line?
algorithms;algorithm analysis;combinatorics;search algorithms
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$.