3SUM problem solution on the basis of cubic function and a line?

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?

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

StackExchange Computer Science Q#55039, answer score: 2