Can this sum of fractions of pairwise sums be computed efficiently? Given a constant $c \in \mathbb{R}$ and two lists $X, Y \in \mathbb{R}^n$, I want to compute
$$
r = \sum_{x \in X} \sum_{y \in Y} \frac{c}{x+y+c}
$$
Of course, this can trivially be done with $\mathcal{O}(n^2)$ arithmetic operations. However, I wonder whether there is any faster way of computing this sum. Specifically, my question is: Is there any approach to computing the above sum that requires only $\mathcal{O}(n)$ arithmetic operations?

The reason I'm wondering whether this is possible is that for the "inverse" sum $r = \sum_{x \in X} \sum_{y \in Y} \frac{x+y+c}{c}$, this can easily be achieved (if I did the maths correctly) be reformulating it as $r = \frac{1}{c}\cdot(n^2\cdot c + n\sum_{y \in Y}y + n\sum_{x \in X}x)$.
 A: I take it that by "lists" $X, Y \in \mathbb{R}^n$ you mean $n$-tuples $X = (x_1, x_2, \ldots, x_n),$ $Y = (y_1, y_2, \ldots, y_n),$ where $x_i \in \mathbb{R},$ $y_j \in \mathbb{R}$ for $i, j = 1, 2, \ldots, n.$ Rather than using what seem to be confused notations $x \in X$ and $y \in Y,$ I shall write:
$$
r = \sum_{i=1}^n\sum_{j=1}^n\frac{c}{x_i + y_j + c}.
$$
(Let me know if this misrepresents your intentions.)
I don't know how to answer your question definitively, but I'll present an argument which suggests strongly that the answer is "no". I'll try to show that, if $n \geqslant 2,$ then $r$ cannot be expressed in the form
$$
r = h(f(X), g(Y))
$$
for any differentiable functions $f \colon S \to U,$ $g \colon T \to V,$ $h \colon U \times V \to \mathbb{R},$ where $S, T$ are open subsets of $\mathbb{R}^n,$ and $U, V$ are intervals of $\mathbb{R}.$ (Don't worry if you're unfamiliar with the term open subset - it's not crucial.)
In a loose notation which I hope won't cause confusion (writing composites of linear maps, with nested parentheses, is also confusing), if we think of $h$ as a "function of two variables" $u = f(X)$ and $v = g(Y),$
$$
\frac{\partial r}{\partial x_i} = \frac{\partial h}{\partial u}\frac{\partial u}{\partial x_i} \text{ and } \frac{\partial r}{\partial y_j} = \frac{\partial h}{\partial v}\frac{\partial v}{\partial y_j}.
$$
The important thing is that the partial derivatives of $u$ don't involve $Y,$ and the partial derivatives of $v$ don't involve $X,$ so the ratio of the partial derivatives of $r$ with respect to $x_i, x_{i'}$ is independent of $Y$ for all $i, i',$ and similarly the ratio of the partial derivatives of $r$ with respect to $y_j, y_{j'}$ is independent of $X$ for all $j, j'.$ But:
\begin{align*}
\frac{\partial r}{\partial x_i} & = -\sum_{j=1}^n\frac{c}{(x_i + y_j + c)^2}
\quad (i = 1, 2, \ldots, n), \\
\frac{\partial r}{\partial y_j} & = -\sum_{i=1}^n\frac{c}{(x_i + y_j + c)^2}
\quad (j = 1, 2, \ldots, n).
\end{align*}
It is enough to use just the first of these to derive a contradiction.
Take any point $X \in S$ such that no two of its coordinates $x_1, x_2, \ldots, x_n$ are equal. (Technically, this is possible because the set $S$ is open.) For $i = 1, 2, \ldots, n,$ write
$$
p_i(Y) = \sum_{j=1}^n\frac1{(x_i + y_j + c)^2},
\text{ for } Y = (y_1, y_2, \ldots, y_n) \in T.
$$
Our hypothesis is equivalent to the proposition that for every pair of indices $i, i'$ in $\{1, 2, \ldots, n\},$ the ratio $p_i(Y)/p_{i'}(Y)$ is independent of $Y.$ This is obviously unlikely, but we must obtain a contradiction from it.
Take any pair $i, i',$ it doesn't matter which. Our hypothesis implies that for $k = 1, 2, \ldots, n,$
$$
0 = \frac\partial{\partial y_k}(\log p_i(Y) - \log p_{i'}(Y)) =
\frac{-2}{p_i(Y)(x_i + y_k + c)^3} + \frac2{p_{i'}(Y)(x_{i'} + y_k + c)^3},
$$
therefore
$$
\left(\frac{x_{i'} + y_k + c}{x_i + y_k + c}\right)^3 = \frac{p_i(Y)}{p_{i'}(Y)},
$$
which is independent of $Y,$ and therefore independent of $y_k.$ But we chose $X$ so that $x_i \ne x_{i'}.$ If, say, $x_{i'} > x_i,$ then the expression in the brackets is equal to $1 + (x_{i'} - x_i)/(x_i + y_k + c),$ which decreases strictly with $y_k,$ contradicting our hypothesis.
Therefore $r(X, Y)$ cannot be expressed in the form $h(f(X), g(Y))$ for any differentiable functions $f, g, h.$ $\ \square$
What this seems to show (although I admit that the argument is far from conclusive) is that there is no way to compute $r(X, Y)$ by first processing $X$ and $Y$ separately and then combining the results. This makes the prospects for an $\mathcal{O}(n)$ algorithm look rather bleak, I think.
