Ardışık endeksler için zayıf alt modülerlik
İzin Vermek $f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$ tarafından tanımlanmak $f(x,y) = \frac{x^2}{y}$. İzin Vermek$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}^+$ öyle sipariş verilsin $\frac{x_1}{y_1} \leq \dots \leq \frac{x_n}{y_n}$. Ayarlanan işlevi tanımlayın$F\colon 2^n \rightarrow \mathbf{R}$ tarafından $F(S) = \frac{(\sum_{i \in S}x_i)^2}{\sum_{i \in S}y_i}$ için $S \subseteq \left\lbrace 1, \dots n\right\rbrace$
$F$ için bile alt modüler olamayabilir $X$ pozitif - için $X = \left\lbrace0, 7, 8, 9\right\rbrace$, $Y = \left\lbrace4, 7, 1, 1\right\rbrace$ almak $$ \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} $$ ve $$ F(S) + F(T) \approx 80.1667 \\ F(S \cup T) + F(S \cap T) \approx 125.3077 $$
Bence $F$ aralıklar için alt modülerdir, ancak başka bir deyişle $$ F(S) + F(T) \geq F(S \cup T) + F(S \cap T) $$
için $S$, $T$ formun aralıkları $\left\lbrace j, j+1, \dots k\right\rbrace$, için $j \leq k$herhangi bir spesifikasyon için $X$, $Y$. Bunu kanıtlayamadım - herhangi biri bunu kanıtlayabilir veya karşı örnek verebilir mi?
Yanıtlar
Alt modülerlik, aşağıdaki hüküm ile geçerlidir: OP'de, $F(\emptyset)$tanımsız. Şöyle tanımlayalım$0$.
İzin Vermek $$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.$$ Genellik kaybı olmadan (wlog), $S$ ve $T$ boş değildir ve aralığın sol uç noktası $S$ aralığın sol uç noktasından büyük değil $T$. Açıkçası,$t_1,t_2,t_3\ge0$. Varsayım$t_1,t_2,t_3>0$, kondisyon $\frac{x_1}{y_1}\le\dots\le\frac{x_n}{y_n}$ ima eder $$\frac{s_1}{t_1}\le\frac{s_2}{t_2}\le\frac{s_3}{t_3}.\tag{1}$$
Bu koşullar ayrıca şu anlama gelir: $$\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}$$ Yani, $$F(S)+F(T)\ge F(S\cup T)+F(S\cap T)$$ Eğer $t_1,t_2,t_3>0$. Şunlardan birinin olduğu davalar$t_j$'s (ve karşılık gelen $s_j$s) eşittir $0$ benzer ve daha basittir.
Böylece, $F$ alt modülerdir.
(1) 'deki ilk eşitsizliği kanıtlamak (söylemek) için, $r_i:=x_i/y_i$, $j:=\max(S\setminus T)$, ve $k:=\min(S\cap T)$. Sonra$x_i=r_i y_i$, $r_i$ azalmıyor $i$, ve $j<k$. Yani,$s_1\le r_j t_1$, ve $s_2\ge r_k t_2$, ve $r_j\le r_k$. Bu eşitsizlikler, (1) 'deki ilk eşitsizliği ifade eder. (1) 'deki ikinci eşitsizlik oldukça benzer şekilde kanıtlanmıştır.
(2) 'yi ispatlamak için orayı değiştirin $s_j$ tarafından $R_jt_j$, nerede $R_j:=s_j/t_j$, böylece (1), $R_1\le R_2\le R_3$. O halde, türevinin$R_3$ (2) 'nin sol ve sağ tarafları arasındaki farkın ( $s_j$ ile ikame edilmiş $R_jt_j$) dır-dir $$\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.$$ Yani, wlog $R_3=R_2$, bu durumda (2) şu şekilde yeniden yazılabilir: $$\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}$$ ki bu açıkça doğrudur.
Bunu da görebiliriz. $t_1,t_2,t_3>0$, eşitsizlik (2) katı olmadığı sürece $R_1=R_2=R_3$.
Ayrıca, karşılık gelen koşullar altında kanıtlama (2), aşağıdaki Mathematica not defterinden görüldüğü gibi, algoritmik / düşüncesizce ele alınabilen gerçek cebirsel geometrinin basit bir problemidir (büyütmek için resme tıklayın):
