Difference between revisions of "Main Page"

From MWiki
Jump to: navigation, search
m (RU method)
(Green's and Singmaster's theorem)
 
(55 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 ==
−
=== RU method ===
+
=== Green's theorem ===
−
If the linear system (LS) <math>Ax = b \in  {}^{\nu}\mathbb{Q}^{n}</math> can be uniquely solved for <math>n \in {}^{\nu}\mathbb{N}^*</math>, the ''root of unity method (<math>RU</math> method)'' computes <math>x \in {}^{\nu}\mathbb{Q}^{n}</math> for <math>A \in {}^{\nu}\mathbb{Q}^{n \times n}</math> in <math>\mathcal{O}(n^2)</math>.
 
  
−
=== 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>R_1 := (r_{1jk}) = (r_{1kj}) = R_1^T \in {}^{\nu}\mathbb{C}^{n \times n}, n \in {}^{\nu}2\mathbb{N}^*, r_{11k} := 1</math> and for <math>j &gt; 1</math> as well as <math>n_{jk} := j + k - 3</math> both <math>r_{1jk} := \hat{n}e^{i\tau n_{jk}/n}</math> for <math>n_{jk} &lt; n</math> and <math>r_{1jk} := \hat{n}e^{i\tau(n_{jk} - \acute{n})/n}</math> for <math>n_{jk} \ge n</math>. Interchanging the first and <math>j</math>-th row resp. column position and correspondingly interchanging the remaining row and column positions yields matrices <math>R_j = R_j^T</math> for <math>j &gt; 1</math>. Let <math>\delta_{jk}</math> be the Kronecker delta and <math>A := (a_{jk})</math>.
 
  
−
If <math>a_{jk} \le 0</math> is given for at least one couple <math>(j, k)</math>, then compute the sums <math>s_0 := \sum\limits_{j=1}^m{b_j\varepsilon^j}</math> for an arbitrary transcendental number <math>\varepsilon</math> and <math>s_k := \sum\limits_{j=1}^m{a_{jk}\varepsilon^j} \ne 0</math> for all <math>k</math>. Replace <math>x_k</math> by <math>-x_k</math> for <math>s_k &lt; 0</math>. Add a multiple of <math>s^Tx</math> resp. <math>s_0</math> to <math>Ax = b</math>, such that <math>a_{jk} &gt; 0</math> holds for all <math>(j, k)</math>. Let <math>b_j = 1</math> for all <math>j</math> wlog. For <math>D_j := (d_{jk}), d_{jk} = \delta_{jk}⁄a_{jk}, C_j := D_j R_j</math> and <math>x_k^{(0)} := \hat{n}/ \max_j a_{jk}</math>, let <math>x^{(\grave{m})} = x^{(m)} + C_j^{-1}(b - Ax^{(m)}).\square</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>
  
−
=== Corollary ===
+
=== Singmaster's theorem ===
−
The RU method allows to determine every eigenvalue and -vector of <math>Ax = \lambda x \in {}^{\nu}\mathbb{Q}^{n} + {}^{\nu}\mathbb{Q}^{n}</math> for <math>n \in {}^{\nu}2\mathbb{N}^*, \lambda \in {}^{\nu}\mathbb{Q}+ {i}^{\nu}\mathbb{Q}</math> and <math>A  \in {}^{\nu}\mathbb{Q}^{n \times n}</math> in <math>\mathcal{O}(n^2)</math> by putting <math>x^{\prime(\grave{m})} = C_j^{-1}AC_j x^{\prime(m)}</math>.
+
 
 +
There are maximally 8 distinct binomial coefficients of the same value > 1.
 +
 
 +
==== 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>
  
−
'''Remark:''' Extending the theorem to complex <math>A</math> and <math>b</math> is easy.
 
 
== Recommended reading ==
 
== Recommended reading ==
  

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"