Weak submodularity for consecutive indices Let $f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$ be defined by $f(x,y) = \frac{x^2}{y}$. Let $X = \left\lbrace x_1, \dots, x_n\right\rbrace \subseteq \mathbf{R}$, $Y = \left\lbrace y_1, \dots, y_n\right\rbrace \subseteq \mathbf{R}^+$ be ordered so that $\frac{x_1}{y_1} \leq \dots \leq \frac{x_n}{y_n}$. Define the set function $F\colon 2^n \rightarrow \mathbf{R}$ by $F(S) = \frac{(\sum_{i \in S}x_i)^2}{\sum_{i \in S}y_i}$ for $S \subseteq \left\lbrace 1, \dots n\right\rbrace$
$F$ may fail to be submodular, even for $X$ positive -  for $X = \left\lbrace0, 7, 8, 9\right\rbrace$, $Y = \left\lbrace4, 7, 1, 1\right\rbrace$ take
$$
\begin{align}
S &= \left\lbrace 1, 3\right\rbrace \\
T &= \left\lbrace0, 2, 3\right\rbrace \\
S \cap T &= \left\lbrace 3\right\rbrace\\
S \cup T &= \left\lbrace 0, 1, 2, 3\right\rbrace \\
\end{align}
$$
and
$$
F(S) + F(T) \approx 80.1667 \\
F(S \cup T) + F(S \cap T) \approx 125.3077
$$
I think $F$ is submodular for intervals, however, in other words
$$
F(S) + F(T) \geq F(S \cup T) + F(S \cap T)
$$
for $S$, $T$ intervals of the form $\left\lbrace j, j+1, \dots k\right\rbrace$, for $j \leq k$, for any specification of $X$, $Y$. I haven't been able to prove this - can anyone prove or provide a counterexample?
 A: The submodularity holds, with the following provision: In the OP, $F(\emptyset)$ is undefined. Let us define it as $0$.
Let
$$s_1:=\sum_{S\setminus T}x_i,\quad s_2:=\sum_{S\cap T}x_i,\quad s_3:=\sum_{T\setminus S}x_i,$$
$$t_1:=\sum_{S\setminus T}y_i,\quad t_2:=\sum_{S\cap T}y_i,\quad t_3:=\sum_{T\setminus S}y_i.$$
Without loss of generality (wlog), $S$ and $T$ are nonempty, and the left endpoint of the interval $S$ is no greater than the left endpoint of the interval $T$. Obviously, $t_1,t_2,t_3\ge0$. Assuming $t_1,t_2,t_3>0$, the condition $\frac{x_1}{y_1}\le\dots\le\frac{x_n}{y_n}$ implies
$$\frac{s_1}{t_1}\le\frac{s_2}{t_2}\le\frac{s_3}{t_3}.\tag{1}$$
These conditions further imply
$$\frac{(s_1+s_2)^2}{t_1+t_2}+\frac{(s_2+s_3)^2}{t_2+t_3}\ge\frac{(s_1+s_2+s_3)^2}{t_1+t_2+t_3}+\frac{s_2^2}{t_2}.\tag{2}$$
That is,
$$F(S)+F(T)\ge F(S\cup T)+F(S\cap T)$$
if $t_1,t_2,t_3>0$. The cases with one of the $t_j$'s (and the corresponding $s_j$'s) equal $0$ are similar, and simpler.
Thus, $F$ is submodular.

To prove (say) the first inequality in (1), let $r_i:=x_i/y_i$, $j:=\max(S\setminus T)$, and $k:=\min(S\cap T)$. Then $x_i=r_i y_i$, $r_i$ is nondecreasing in $i$, and $j<k$. So, $s_1\le r_j t_1$, and $s_2\ge r_k t_2$, and $r_j\le r_k$. These inequalities imply the first inequality in (1). The second inequality in (1) is proved quite similarly.

To prove (2), replace there $s_j$ by $R_jt_j$, where $R_j:=s_j/t_j$, so that, by (1), $R_1\le R_2\le R_3$. Note then that the derivative in $R_3$ of the difference between the left- and right-hand sides of (2) (with $s_j$ replaced by $R_jt_j$) is
$$\frac{2 t_1 t_3 \left(\left(R_2-R_1\right) t_2+\left(R_3-R_1\right) t_3\right)}{\left(t_2+t_3\right)
   \left(t_1+t_2+t_3\right)}\ge0.$$
So, wlog $R_3=R_2$, in which case (2) can be rewritten as
$$\frac{\left(R_1-R_2\right){}^2 t_1^2 t_3}{\left(t_1+t_2\right) \left(t_1+t_2+t_3\right)}\ge0,\tag{3}$$
which is obviously true.
We can also see that, with $t_1,t_2,t_3>0$, inequality (2) is strict unless $R_1=R_2=R_3$.

Also, proving (2) under the corresponding conditions is a simple problem of real algebraic geometry, which can be algorithmically/thoughtlessly handled, as is seen from the following image of a Mathematica notebook (click on the image to enlarge it):

