1632
правки
Изменения
м
rollbackEdits.php mass rollback
<tex>|F_j|=fn,|B_j|=bn</tex>
== Анализ сепараторов разделителей ==
лемма 6.3
<tex> p = \dfrac{1}{kn}\sum\limits _{i=1}^k r_i </tex>
<tex>\dbinom{n}{k}\dbinom{j - fk/2}{k} \le \dbinom{n}{k}\dbinom{j}{k} < \bigg(\dfrac{e^2(f+2)^2n}{k^2}\bigg)^k </tex>
<tex> 1 + \sum\bigg(\dfrac{e^2(f+2)^2n}{k^2}\bigg)^k < \dfrac{90}{89} \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2j/(f+2)} </tex>
<tex>e^2nj \ge e^2j > 90 </tex>
<tex>x \le 2j/(f+2) </tex>
<tex>\dfrac{d}{dx}\ln\bigg(\bigg(\dfrac{e^2nj}{x^2}\bigg)^x\bigg) = \ln\dfrac{nj}{x^2} \ge \ln\dfrac{n(f + 2)^2}{4j} \ge \ln\dfrac{25(f+2)^2}{4f} \ge \ln 90</tex>
<tex> \dfrac{90}{89} \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2j/(f+2)} \cdot \dfrac{1 + e^{-5}}{1 - e^{-5}} \Bigg(\bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f}\dfrac{2ej}{fn}\Bigg)^{\varepsilon_Fj} </tex>
<tex>x = \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2/\varepsilon_Ff} \cdot \bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f} \cdot \dfrac{2ej}{fn}; </tex>
<tex>(e^2/\varepsilon_F)^{2/f} = ((e^2/\varepsilon_F)^{\varepsilon_F})^{2/\varepsilon_Ff} \le (e^2))^{2/\varepsilon_Ff} </tex>
<tex>x \le \bigg(\dfrac{e^4(f+2)^2n}{4j}\bigg)^{2//\varepsilon_Ff}\bigg(\dfrac{2ej}{fn}\bigg)^{(f-2)/f} </tex>
<tex>t = \varepsilon_F(f-2)/2 </tex>
<tex> x^{f/(f-2)} \le 0.24\Bigg(\dfrac{e^5(f+2)^2}{0.48f}\bigg(\dfrac{ej}{0.12fn}\bigg)^{t-1}\Bigg)^{1/t} \\ \le 0.24\Bigg(3e^5f\bigg(\dfrac{e\delta_F}{0.12}\bigg)^{t-1}\Bigg)^{1/t} </tex>
<tex> t-1 \ge \dfrac{\ln(3e^5f)}{\ln(0.12/e\delta_F)} </tex>
<tex> x^{f/(f-2)} \le 0.24 </tex>
<tex>x <0.32 </tex>
<tex> 1.025 \sum\limits_{i\ge1} 0.32^i </tex>
== Доказательство ==
Будем считать, что
<tex>A=k^2</tex> и <tex>\nu = 1/k </tex>.
<tex>\mu = k ^{-5},\; \delta = \dfrac{1}{3}k^{-5}, \; \delta_F = \dfrac{2k}{k^2 - 1} </tex>
Тогда получим, что
<tex> t_f = 3d - 20 </tex> и <tex>\alpha(t_f) = \omega(t_f) = d - 6 </tex>, где <tex>d = \log N/\log k </tex>.
<tex> \varepsilon_B \le \dfrac{1}{4}k^{-4} \cdot \dfrac{4k-1}{4k} </tex>
<tex> \varepsilon_F \le \dfrac{1}{4}k^{-4} \cdot\dfrac{4k-1}{4k} </tex>
<tex> \varepsilon^* = 2^{-39}\sqrt{1 + 79\ln 2} < 2 ^{-36} </tex>
<tex> f > 2^{34} \cdot \dfrac{1-2^{-12}}{1 - 2^{-36}} > 1.7 \times 10^{10} </tex>
<tex> \varepsilon_B = 2 ^{-29}\sqrt{1 + 59\ln 2} < 1.25 \times 10 ^{-8} </tex>
<tex> \delta_F = 128/4095 </tex>
<tex> \varepsilon_F = 1/(8\times 10^7) = 1.25 \times 10^{-8} </tex>
<tex> \sqrt{\dfrac{2(1+\ln m)}{m}} \le k ^{-6} </tex>
<tex> M/32 < m \le M/16 </tex>
<tex> \log k = (\dfrac{1}{12} + o(1))\log M </tex> <tex> M \to \infty </tex>
<tex> f \ge (1 + o(1))\dfrac{m}{2k^4} \ge (1+o(1))k^8\ln k </tex>
<tex>M \to \infty </tex>
<tex> \varepsilon_B = k^{-6}, \; \delta_F = \dfrac{2k}{k^2 - 1}, \; \varepsilon_F = k^{-8} </tex>
<tex> \sqrt{\dfrac{2(1+\ln m)}{m}} \le \dfrac{1}{5}k^{-4} </tex>
<tex> \log k = (\dfrac{1}{8} + o(1))\log M </tex>
<tex> \sqrt{\dfrac{2(1 + \ln \lfloor M^{3/2}\rfloor)}{\lfloor M^{3/2}\rfloor}} \le k^{-6} </tex>
<tex> \varepsilon_B = \dfrac{1}{5}k^{-4}, \; \delta_F = \dfrac{2k}{k^2 - 1}, \; \varepsilon_F = \dfrac{1}{5}k^{-4} </tex>
