# 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?

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. 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):

• Yes, $F(\emptyset) = 0$ can be assumed, thanks. So $F$ is submodular for intervals but not in general. "...that the derivative in $s_3$..." maybe?, otherwise it's messy. Oct 21, 2020 at 16:19
• I took the derivative in $R_3$, as I wrote, and it is manifestly $\ge0$ when expressed in terms of $R_j$' s (and $t_j$'s). Oct 21, 2020 at 17:12
• Sorry, how do you get to $\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,$ with $R_2 = R_3$? Oct 24, 2020 at 17:17
• @CharlesPehlivanian : I did the routine algebraic calculations with Mathematica, rather than by hand; see the pdf image of the Mathematica notebook at u.pcloud.link/publink/… I think these calculations are doable by hand. Otherwise, you can use Mathematica or any other commercial or freely available computer algebra system to check the calculations. Oct 25, 2020 at 0:39
• @CharlesPehlivanian : Why are saying this? The substitution R3->R2 was made into dif, which latter is the difference between the left- and right-hand sides of (2). See the pdf image of the updated Mathematica notebook at u.pcloud.link/publink/… . I have now also rechecked (3) manually -- took me 5 or 10 minutes. Oct 25, 2020 at 2:16