연속 인덱스에 대한 약한 하위 모듈성
허락하다 $f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$ 에 의해 정의되다 $f(x,y) = \frac{x^2}{y}$. 허락하다$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}^+$ 명령을 받다 $\frac{x_1}{y_1} \leq \dots \leq \frac{x_n}{y_n}$. 설정 기능 정의$F\colon 2^n \rightarrow \mathbf{R}$ 으로 $F(S) = \frac{(\sum_{i \in S}x_i)^2}{\sum_{i \in S}y_i}$ ...에 대한 $S \subseteq \left\lbrace 1, \dots n\right\rbrace$
$F$ 하위 모듈화되지 않을 수 있습니다. $X$ 긍정적- $X = \left\lbrace0, 7, 8, 9\right\rbrace$, $Y = \left\lbrace4, 7, 1, 1\right\rbrace$ 취하다 $$ \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} $$ 과 $$ F(S) + F(T) \approx 80.1667 \\ F(S \cup T) + F(S \cap T) \approx 125.3077 $$
나는 생각한다 $F$ 즉, 간격에 대해 하위 모듈입니다. $$ F(S) + F(T) \geq F(S \cup T) + F(S \cap T) $$
...에 대한 $S$, $T$ 형태의 간격 $\left\lbrace j, j+1, \dots k\right\rbrace$, for $j \leq k$, 모든 사양에 대해 $X$, $Y$. 나는 이것을 증명할 수 없었습니다. 누구든지 반증을 증명하거나 제공 할 수 있습니까?
답변
하위 모듈성은 다음 조항으로 유지됩니다. OP에서, $F(\emptyset)$정의되지 않았습니다. 그것을 다음과 같이 정의합시다.$0$.
허락하다 $$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.$$ 일반성 (wlog) 손실없이 $S$ 과 $T$ 비어 있지 않고 간격의 왼쪽 끝점 $S$ 간격의 왼쪽 끝점보다 크지 않습니다. $T$. 명백하게,$t_1,t_2,t_3\ge0$. 가정$t_1,t_2,t_3>0$, 조건 $\frac{x_1}{y_1}\le\dots\le\frac{x_n}{y_n}$ 암시 $$\frac{s_1}{t_1}\le\frac{s_2}{t_2}\le\frac{s_3}{t_3}.\tag{1}$$
이러한 조건은 $$\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}$$ 그건, $$F(S)+F(T)\ge F(S\cup T)+F(S\cap T)$$ 만약 $t_1,t_2,t_3>0$. 다음 중 하나가있는 경우$t_j$의 (및 해당 $s_j$의) 같음 $0$ 비슷하고 더 간단합니다.
그러므로, $F$ 하위 모듈입니다.
(1)의 첫 번째 불평등을 증명하려면 $r_i:=x_i/y_i$, $j:=\max(S\setminus T)$, 및 $k:=\min(S\cap T)$. 그때$x_i=r_i y_i$, $r_i$ 감소하지 않음 $i$, 및 $j<k$. 그래서,$s_1\le r_j t_1$, 및 $s_2\ge r_k t_2$, 및 $r_j\le r_k$. 이러한 불평등은 (1)의 첫 번째 불평등을 의미합니다. (1)의 두 번째 부등식은 매우 유사하게 증명됩니다.
(2)를 증명하려면 거기를 대체하십시오 $s_j$ 으로 $R_jt_j$, 어디 $R_j:=s_j/t_j$, 그래서, (1)에 의해, $R_1\le R_2\le R_3$. 그런 다음 미분$R_3$ (2)의 왼쪽과 오른쪽의 차이 $s_j$ ~로 교체되다 $R_jt_j$)은 $$\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.$$ 그래서, wlog $R_3=R_2$,이 경우 (2)는 다음과 같이 다시 작성할 수 있습니다. $$\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}$$ 분명히 사실입니다.
우리는 또한 그것을 볼 수 있습니다. $t_1,t_2,t_3>0$, 불평등 (2)은 $R_1=R_2=R_3$.
또한 해당 조건에서 (2)를 증명하는 것은 실제 대수 기하학의 간단한 문제이며, Mathematica 노트북의 다음 이미지에서 볼 수 있듯이 알고리즘 적으로 / 생각없이 처리 할 수 있습니다 (확대하려면 이미지를 클릭하십시오).
