Deciding if a polynomial can be expressed as a rational function of other polynomials

In this case $$ f = \frac{(f_1-f_2+f_3-f_4)(f_1 - f_2 - f_3 + f_4)}{2(f_1+f_2-f_3-f_4)}.$$

This is obtained as one of the elements (as denominator times $f$ minus numerator) in a Gröbner basis of the ideal $$(f_1-(x_1–x_2)^2, \ldots, f_4-(x_4-x_1)^2, f-(x_1-x_3)^2)$$ where $f_1, \ldots, f_4, f$ are treated as indeterminates with a (lexicographical) ordering $$\{f_1, \ldots, f_4\} < f < \{x_1, \ldots, x_4\}.$$

The theory of system of equations in polynomial rings is only a little more complicated than the theory of linear equations.

In the linear world, you choose a "free system" of "basic variables" (the most suitable for your needs) and express all non-basic variables in terms of the basic variables. The dimension is the number of basic variables.

In polynomial rings, the number of basic variables is called the transcendence degree (of the field extension generated by the variables) and the added complexity is that a non-basic variable will in general not be expressible as a rational function of the basic variables, but will be merely algebraic over the field generated by the basic variables, and a variable will be described by its minimal polynomial over the "basic" field.

If (as if often needed and natural) you insist that the minimal polynomials be irreducible, then you will have a finite union of cases, similar to the decomposition of an algebraic variety into irreducible varieties.

From a computational perspective, all that is involved is addition, multiplication, resultants and factorization of multivariate polynomials, although of course the details of the computation quickly become painful when the number of variables grows. The fundamental result is that if two variables $a,b$ satisfy two different equations $F(a,b)=G(a,b)=0$, then taking resultants wrt to $a$ and $b$ you may find the minimal polynomial of $a$ over $K(b)$, or $b$ over $K(a)$ according to your needs, where $K$ is the field generated by the other variables. You can iterate this to adapt it to any number of variables or equations.

Here, you may simplify a little bit your initial system by removing a superfluous variable : put $r_k=x_{k+1}-x_k$ for $1\leq k \leq 3$. Then your system can be rewritten as $r_1^2=f_1,r_2^2=f_2,r_3^2=f_3,(r_1+r_2+r_3)^2=f_4$, and you wish to express $f=(r_1+r_2)^2$ in terms of $f_1,f_2,f_3,f_4$.

Here, I choose the following ordering of the variables (we want to express the "last" variables in terms of the "first" ones) : $f_1,f_2,f_3,r_1,r_2,r_3,f_4,g$.

Let $F={\mathbb Q}(f_1,f_2,f_3)$, then $F/{\mathbb Q}$ is a purely transcendental extension (so $f_1,f_2,f_3$ are "basic variables"). On the other hand, $r_1,r_2,r_3$ are clearly all algebraic (of degree $2$) over $F$. Then $f_4$ which is a polynomial in the $r_k$ must also be algebraic over $F$. In fact, one can compute that the minimal polynomial of $f_4$ over $F$ is given by

$$ M_{f_4}=\sum_{ }f_i^4-4\sum_{}f_i^2f_j+6\sum_{}(f_if_j)^2+4\sum_{}f_i^2f_jf_k-40f_1f_2f_3f_4 $$

Finally, $f=(r_1+r_2)^2$ is algebraic over $F$, and a fortiori over $F(f_4)$. Omitting here the ugly, long and boring details of the computation (which I did partly using PARI-GP), one obtains that

$$ f = \frac{(f_1-f_2+f_3-f_4)(f_1 - f_2 - f_3 + f_4)}{2(f_1+f_2-f_3-f_4)}$$

(see WimC's answer for a very elegant derivation of this identity). Note that

$$ \begin{array}{lcl} f_1-f_2+f_3-f_4 &=& 2(x_3-x_1)(x_2-x_4) \\ f_1-f_2-f_3+f_4 &=& 2(x_3-x_1)(x_2-x_1+x_4-x_3) \\ f_1+f_2-f_3-f_4 &=& 2(x_2-x_4)(x_2-x_1+x_4-x_3) \\ \end{array} $$