Difference between revisions of "Main Page"

From MWiki
Jump to: navigation, search
(Intex method)
(Green's and Singmaster's theorem)
 
(23 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
__NOTOC__
 
__NOTOC__
 
= Welcome to MWiki =
 
= Welcome to MWiki =
−
== Theorem of the month ==
+
== Theorems of the month ==
−
The intex method solves every solvable LP in <math>\mathcal{O}(\omega{\vartheta}^{2})</math>.
+
=== Green's theorem ===
  
−
== Proof and algorithm ==
+
For some <math>h</math>-domain <math>\mathbb{D} \subseteq {}^{(\omega)}\mathbb{R}^{2}</math>, infinitesimal <math>h = |{\downarrow}x|= |{\downarrow}y| = |\overset{\rightharpoonup}{\gamma}(s) - \gamma(s)| = \mathcal{O}({\tilde{\omega}}^{m})</math>, sufficiently large <math>m \in \mathbb{N}^{*}, (x, y) \in \mathbb{D}, \mathbb{D}^{-} := \{(x, y) \in \mathbb{D} : (x + h, y + h) \in \mathbb{D}\}</math>, and a simply closed path <math>\gamma: [a, b[\rightarrow {\downarrow} \mathbb{D}</math> followed anticlockwise, choosing <math>\overset{\rightharpoonup}{\gamma}(s) = \gamma(\overset{\rightharpoonup}{s})</math> for <math>s \in [a, b[, A \subseteq {[a, b]}^{2}</math>, the following equation holds for sufficiently <math>\alpha</math>-continuous functions <math>u, v: \mathbb{D} \rightarrow \mathbb{R}</math> with not necessarily continuous <math>{\downarrow} u/{\downarrow} x, {\downarrow} u/{\downarrow} y, {\downarrow} v/{\downarrow} x</math> and <math>{\downarrow} v/{\downarrow} y</math><div style="text-align:center;"><math>{\uparrow}_{\gamma }{(u\,{\downarrow}x+v\,{\downarrow}y)}={\uparrow}_{(x,y)\in {\mathbb{D}^{-}}}{\left( \tfrac{{\downarrow} v}{{\downarrow} x}-\tfrac{{\downarrow} u}{{\downarrow} y} \right){\downarrow}(x,y)}.</math></div>
−
Let <math>z := m + n</math> and <math>d \in [0, 1]</math> the density of <math>A</math>. First, normalise and scale <math>{b}^{T}y - {c}^{T}x \le 0, Ax \le b</math> as well as <math>{A}^{T}y \ge c</math>. Let <math>P_r := \{(x, y)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{z} : {b}^{T}y - {c}^{T}x \le r \in [0, \breve{r}], Ax - b \le \underline{r}_m, c - {A}^{T}y \le \underline{r}_n\}</math> have the radius <math>\breve{r} := s|\min \; \{b_1, ..., b_m, -c_1, ..., -c_n\}|</math> and the scaling factor <math>s \in [1, 2]</math>. It follows <math>\underline{0}_{z} \in \partial P_{\breve{r}}</math>. By the strong duality theorem, the LP min <math>\{ r \in [0, \breve{r}] : (x, y)^T \in P_r\}</math> solves the LPs max <math>\{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}</math> and min <math>\{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge c\}</math>.
 
  
 +
==== Proof: ====
 +
Only <math>\mathbb{D} := \{(x, y) : r \le x \le s, f(x) \le y \le g(x)\}, r, s \in {}^{(\omega)}\mathbb{R}, f, g : {\downarrow} \mathbb{D} \rightarrow {}^{(\omega)}\mathbb{R}</math> is proved, since the proof is analogous for each case rotated by <math>\check{\pi}</math>. Every <math>h</math>-domian is union of such sets. Simply showing <div style="text-align:center;"><math>{\uparrow}_{\gamma }{u\,{\downarrow}x}=-{\uparrow}_{(x,y)\in {\mathbb{D}^{-}}}{\tfrac{{\downarrow} u}{{\downarrow} y}{\downarrow}(x,y)}.</math></div> is sufficient because the other relation is given analogously. Neglecting the regions of <math>\gamma</math> with <math>{\downarrow}x = 0</math> and <math>s := h(u(r, g(r)) - u(t, g(t)))</math> shows <div style="text-align:center;"><math>-{\uparrow}_{\gamma }{u\,{\downarrow}x}-s={\uparrow}_{t}^{r}{u(x,g(x)){\downarrow}x}-{\uparrow}_{t}^{r}{u(x,f(x)){\downarrow}x}={\uparrow}_{t}^{r}{{\uparrow}_{f(x)}^{g(x)}{\tfrac{{\downarrow} u}{{\downarrow} y}}{\downarrow}y{\downarrow}x}={\uparrow}_{(x,y)\in {\mathbb{D}^{-}}}{\tfrac{{\downarrow} u}{{\downarrow} y}{\downarrow}(x,y)}.\square</math></div>
  
−
Its solution is the geometric centre <math>g</math> of the polytope <math>P_0</math>. For <math>p_k^* := \text{min}\,\check{p}_k + \text{max}\,\check{p}_k</math> and <math>k = 1, ..., \grave{z}</math> approximate <math>g</math> by <math>p_0 := (x_0, y_0, r_0)^T</math> until <math>||\Delta p||_1</math> is sufficiently small. The solution <math>t^o(x^o, y^o, r^o)^T</math> of the two-dimensional LP min <math>\{ r \in [0, \breve{r}] : t \in {}^{\omega}\mathbb{R}_{&gt; 0}, t(x_0, y_0)^T \in P_r\}</math> approximates <math>g</math> better and achieves <math>r \le \hat{2}\breve{r}</math>. Repeat this for <math>t^o(x^o, y^o)^T</math> until <math>g \in P_0</math> is computed in <math>\mathcal{O}({}_2\breve{r}^2dmn)</math> if it exists.
+
=== Singmaster's theorem ===
  
 +
There are maximally 8 distinct binomial coefficients of the same value > 1.
  
−
Solving all two-dimensional LPs <math>\text{min}_k r_k</math> by bisection methods for <math>r_k \in {}^{\omega}\mathbb{R}_{\ge 0}</math> and <math>k = 1, ..., z</math> in <math>\mathcal{O}({\vartheta}^2)</math> each time determines <math>q \in {}^{\omega}\mathbb{R}^k</math> where <math>q_k := \Delta p_k \Delta r_k/r</math> and <math>r := \text{min}_k \Delta r_k</math>. Let simplified <math>|\Delta p_1| = … = |\Delta p_{z}|</math>. Here min <math>r_z</math> for <math>p^* := p + wq</math> and <math>w \in {}^{\omega}\mathbb{R}_{\ge 0}</math> would be also to solve. If <math>\text{min}_k \Delta r_k r = 0</math> follows, stop computing, otherwise repeat until min <math>r = 0</math> or min <math>r &gt; 0</math> is sure.
+
==== Proof: ====
 +
The existence is clear due to <math>\tbinom{3003}{1} = \tbinom{78}{2} = \tbinom{15}{5} = \tbinom{14}{6}</math> and the structure of Pascal's triangle. With <math>p \in {}^{\omega }{\mathbb{P}}, a,b ,c, d \in {}^{\omega }{\mathbb{N^*}}, \hat{a} \le r := p - b, \hat{a} < \hat{c} \le n := p - d, b < d</math> and <math>s \notin \mathbb{P}</math> for every <math>s \in [\max(r - \acute{a},\grave{n}), r]</math>, Stirling's formula <math>{n!}^2\sim\pi(\hat{n}+\tilde{3}){(\tilde{\epsilon}n)}^{\hat{n}}</math> and the prime number theorem imply <math>\omega\tbinom{r}{a} \le {}_\epsilon\omega\tbinom{n}{c}</math> for <math>p \rightarrow \omega.\square</math>
 +
 
 +
== Recommended reading ==
  
−
== Recommended readings ==
 
 
[https://en.calameo.com/books/003777977258f7b4aa332 Nonstandard Mathematics]
 
[https://en.calameo.com/books/003777977258f7b4aa332 Nonstandard Mathematics]
  
 
[[de:Hauptseite]]
 
[[de:Hauptseite]]

Latest revision as of 02:03, 1 May 2024

Welcome to MWiki

Theorems of the month

Green's theorem

For some [math]\displaystyle{ h }[/math]-domain [math]\displaystyle{ \mathbb{D} \subseteq {}^{(\omega)}\mathbb{R}^{2} }[/math], infinitesimal [math]\displaystyle{ h = |{\downarrow}x|= |{\downarrow}y| = |\overset{\rightharpoonup}{\gamma}(s) - \gamma(s)| = \mathcal{O}({\tilde{\omega}}^{m}) }[/math], sufficiently large [math]\displaystyle{ m \in \mathbb{N}^{*}, (x, y) \in \mathbb{D}, \mathbb{D}^{-} := \{(x, y) \in \mathbb{D} : (x + h, y + h) \in \mathbb{D}\} }[/math], and a simply closed path [math]\displaystyle{ \gamma: [a, b[\rightarrow {\downarrow} \mathbb{D} }[/math] followed anticlockwise, choosing [math]\displaystyle{ \overset{\rightharpoonup}{\gamma}(s) = \gamma(\overset{\rightharpoonup}{s}) }[/math] for [math]\displaystyle{ s \in [a, b[, A \subseteq {[a, b]}^{2} }[/math], the following equation holds for sufficiently [math]\displaystyle{ \alpha }[/math]-continuous functions [math]\displaystyle{ u, v: \mathbb{D} \rightarrow \mathbb{R} }[/math] with not necessarily continuous [math]\displaystyle{ {\downarrow} u/{\downarrow} x, {\downarrow} u/{\downarrow} y, {\downarrow} v/{\downarrow} x }[/math] and [math]\displaystyle{ {\downarrow} v/{\downarrow} y }[/math]

[math]\displaystyle{ {\uparrow}_{\gamma }{(u\,{\downarrow}x+v\,{\downarrow}y)}={\uparrow}_{(x,y)\in {\mathbb{D}^{-}}}{\left( \tfrac{{\downarrow} v}{{\downarrow} x}-\tfrac{{\downarrow} u}{{\downarrow} y} \right){\downarrow}(x,y)}. }[/math]

Proof:

Only [math]\displaystyle{ \mathbb{D} := \{(x, y) : r \le x \le s, f(x) \le y \le g(x)\}, r, s \in {}^{(\omega)}\mathbb{R}, f, g : {\downarrow} \mathbb{D} \rightarrow {}^{(\omega)}\mathbb{R} }[/math] is proved, since the proof is analogous for each case rotated by [math]\displaystyle{ \check{\pi} }[/math]. Every [math]\displaystyle{ h }[/math]-domian is union of such sets. Simply showing

[math]\displaystyle{ {\uparrow}_{\gamma }{u\,{\downarrow}x}=-{\uparrow}_{(x,y)\in {\mathbb{D}^{-}}}{\tfrac{{\downarrow} u}{{\downarrow} y}{\downarrow}(x,y)}. }[/math]

is sufficient because the other relation is given analogously. Neglecting the regions of [math]\displaystyle{ \gamma }[/math] with [math]\displaystyle{ {\downarrow}x = 0 }[/math] and [math]\displaystyle{ s := h(u(r, g(r)) - u(t, g(t))) }[/math] shows

[math]\displaystyle{ -{\uparrow}_{\gamma }{u\,{\downarrow}x}-s={\uparrow}_{t}^{r}{u(x,g(x)){\downarrow}x}-{\uparrow}_{t}^{r}{u(x,f(x)){\downarrow}x}={\uparrow}_{t}^{r}{{\uparrow}_{f(x)}^{g(x)}{\tfrac{{\downarrow} u}{{\downarrow} y}}{\downarrow}y{\downarrow}x}={\uparrow}_{(x,y)\in {\mathbb{D}^{-}}}{\tfrac{{\downarrow} u}{{\downarrow} y}{\downarrow}(x,y)}.\square }[/math]

Singmaster's theorem

There are maximally 8 distinct binomial coefficients of the same value > 1.

Proof:

The existence is clear due to [math]\displaystyle{ \tbinom{3003}{1} = \tbinom{78}{2} = \tbinom{15}{5} = \tbinom{14}{6} }[/math] and the structure of Pascal's triangle. With [math]\displaystyle{ p \in {}^{\omega }{\mathbb{P}}, a,b ,c, d \in {}^{\omega }{\mathbb{N^*}}, \hat{a} \le r := p - b, \hat{a} \lt \hat{c} \le n := p - d, b \lt d }[/math] and [math]\displaystyle{ s \notin \mathbb{P} }[/math] for every [math]\displaystyle{ s \in [\max(r - \acute{a},\grave{n}), r] }[/math], Stirling's formula [math]\displaystyle{ {n!}^2\sim\pi(\hat{n}+\tilde{3}){(\tilde{\epsilon}n)}^{\hat{n}} }[/math] and the prime number theorem imply [math]\displaystyle{ \omega\tbinom{r}{a} \le {}_\epsilon\omega\tbinom{n}{c} }[/math] for [math]\displaystyle{ p \rightarrow \omega.\square }[/math]

Recommended reading

Nonstandard Mathematics

Retrieved from "https://en.mwiki.de/index.php?title=Main_Page&oldid=299"