Difference between revisions of "Main Page"

From MWiki
Jump to: navigation, search
(Centre Method)
m (→‎Reversion theorem of Taylor series)
(38 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 centre method solves every solvable LP in <math>\mathcal{O}(\omega{\vartheta}^{2})</math>.
+
=== Counting theorem for algebraic numbers ===
  
−
== Proof and algorithm ==
+
The number <math>\mathbb{A}(m, n)</math> of algebraic numbers of polynomial or series degree <math>m</math> and thus in general for the Riemann zeta function <math>\zeta</math> asymptotically satisfies the equation <math>\mathbb{A}(m, n) = \widetilde{\zeta(\grave{m})}\,z(m){{(2n+1)}^{m}}\left( n+\mathcal{O}({_e}n) \right)</math>, where <math>z(m)</math> is the average number of zeros of a polynomial or series.
−
Let <math>z := \grave{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, \check{r}], Ax - b \le \underline{r}_m, c - {A}^{T}y \le \underline{r}_n\}</math> have the radius <math>\check{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_{\check{r}}</math>. By the strong duality theorem, the LP min <math>\{ r \in [0, \check{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: ====
 +
The case <math>m = 1</math> requires by <ref name="Scheid">[[w:Harald Scheid|<span class="wikipedia">Scheid, Harald</span>]]: ''Zahlentheorie'' : 1st Ed.; 1991; Bibliographisches Institut; Mannheim; ISBN 9783411148417, p. 323.</ref> the error term <math>\mathcal{O}({_e}n n)</math> and represents the number <math>4{+}_{k=1}^{n}{\varphi (k)}-1</math> by the <math>\varphi</math>-function. For <math>m > 1</math>, the divisibility conditions neither change the error term <math>\mathcal{O}({_e}n)</math> nor the leading term. Polynomials or series such that <math>\text{gcd}({a}_{0}, {a}_{1}, ..., {a}_{m}) \ne 1</math> are excluded by <math>1/\zeta(\grave{m})</math>: The latter is given by taking the product over the prime numbers <math>p</math> of all <math>(1 - {p}^{-\grave{m}})</math> absorbing here multiples of <math>p</math> and representing sums of geometric series.<math>\square</math>
  
−
Its solution is the geometric centre <math>g</math> of the polytope <math>P_0</math>. For <math>p_k^* := (\text{min}\,p_k + \text{max}\,p_k)/2</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, \check{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 \check{r}/\sqrt{\grave{z}}</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}({}_z\check{r} {}_e\check{r}dmn)</math> if it exists. Numbers of length <math>\mathcal{O}({\omega})</math> can only be processed in <math>\mathcal{O}(\vartheta)</math> as is generally known.
+
=== Brocard's theorem ===
 +
It holds that <math>\{(m, n) \in {}^{\omega} \mathbb{N}^2 : n! + 1 = m^2\} = \{(5, 4), (11, 5), (71, 7)\}.</math>
  
 +
==== Proof: ====
 +
From <math>n! = \acute{m}\grave{m}</math>, it follows that <math>m = \hat{r} \pm 1</math> für <math>r \in {}^{\omega} \mathbb{N}^{*}</math> and <math>n \ge 3</math>. Thus <math>n! = \hat{r}(\hat{r}\pm2) = 8s(\hat{s} \pm 1)</math> holds for <math>s \in {}^{\omega} \mathbb{N}^{*}</math>. Let <math>2^q \mid n!</math> and <math>2^{\grave{q}} \nmid n!</math> for maximal <math>q \in {}^{\omega} \mathbb{N}^{*}</math>. Therefore <math>n! = 2^q(\hat{u} + 1)</math> holds for <math>u \in {}^{\omega} \mathbb{N}^{*}</math> and necessarily <math>n! = 2^q(2^{q-2} \pm 1)</math>. Then the prime factorisation of <math>n!</math> requires <math>n \le 7</math> giving the claim.<math>\square</math>
  
−
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, otherwise repeat until min <math>r = 0</math> or min <math>r &gt; 0</math> is sure. If necessary, constraints are temporarily relaxed by the same small modulus.<math>\square</math>
+
=== Reversion theorem of Taylor series ===
 +
For <math>y \in f(\mathbb{D}), y(a) = b</math> and <math>y^{\prime}(a) \ne 0</math>, [[w:Lagrange_inversion_theorem#Lagrange–Bürmann_formula|<span class="wikipedia">Bürmann's theorem</span>]] yields:<div style="text-align:center;"><math>f^{-1}(y) = a + \tilde{n} {\LARGE{\textbf{+}}}_{m=1}^n{\widetilde{m}{\tilde{\varepsilon}}^{\acute{m}}(y - b)^m({\tilde{u}}^{\acute{m}k})^T(f(\varepsilon u^k + a)^{-m})}+\mathcal{O}(\varepsilon^n).\square</math></div>
 +
 
 +
== Recommended reading ==
  
−
== Recommended readings ==
 
 
[https://en.calameo.com/books/003777977258f7b4aa332 Nonstandard Mathematics]
 
[https://en.calameo.com/books/003777977258f7b4aa332 Nonstandard Mathematics]
 +
 +
== References ==
 +
<references />
  
 
[[de:Hauptseite]]
 
[[de:Hauptseite]]

Revision as of 00:22, 18 July 2024

Welcome to MWiki

Theorems of the month

Counting theorem for algebraic numbers

The number [math]\displaystyle{ \mathbb{A}(m, n) }[/math] of algebraic numbers of polynomial or series degree [math]\displaystyle{ m }[/math] and thus in general for the Riemann zeta function [math]\displaystyle{ \zeta }[/math] asymptotically satisfies the equation [math]\displaystyle{ \mathbb{A}(m, n) = \widetilde{\zeta(\grave{m})}\,z(m){{(2n+1)}^{m}}\left( n+\mathcal{O}({_e}n) \right) }[/math], where [math]\displaystyle{ z(m) }[/math] is the average number of zeros of a polynomial or series.

Proof:

The case [math]\displaystyle{ m = 1 }[/math] requires by [1] the error term [math]\displaystyle{ \mathcal{O}({_e}n n) }[/math] and represents the number [math]\displaystyle{ 4{+}_{k=1}^{n}{\varphi (k)}-1 }[/math] by the [math]\displaystyle{ \varphi }[/math]-function. For [math]\displaystyle{ m \gt 1 }[/math], the divisibility conditions neither change the error term [math]\displaystyle{ \mathcal{O}({_e}n) }[/math] nor the leading term. Polynomials or series such that [math]\displaystyle{ \text{gcd}({a}_{0}, {a}_{1}, ..., {a}_{m}) \ne 1 }[/math] are excluded by [math]\displaystyle{ 1/\zeta(\grave{m}) }[/math]: The latter is given by taking the product over the prime numbers [math]\displaystyle{ p }[/math] of all [math]\displaystyle{ (1 - {p}^{-\grave{m}}) }[/math] absorbing here multiples of [math]\displaystyle{ p }[/math] and representing sums of geometric series.[math]\displaystyle{ \square }[/math]

Brocard's theorem

It holds that [math]\displaystyle{ \{(m, n) \in {}^{\omega} \mathbb{N}^2 : n! + 1 = m^2\} = \{(5, 4), (11, 5), (71, 7)\}. }[/math]

Proof:

From [math]\displaystyle{ n! = \acute{m}\grave{m} }[/math], it follows that [math]\displaystyle{ m = \hat{r} \pm 1 }[/math] für [math]\displaystyle{ r \in {}^{\omega} \mathbb{N}^{*} }[/math] and [math]\displaystyle{ n \ge 3 }[/math]. Thus [math]\displaystyle{ n! = \hat{r}(\hat{r}\pm2) = 8s(\hat{s} \pm 1) }[/math] holds for [math]\displaystyle{ s \in {}^{\omega} \mathbb{N}^{*} }[/math]. Let [math]\displaystyle{ 2^q \mid n! }[/math] and [math]\displaystyle{ 2^{\grave{q}} \nmid n! }[/math] for maximal [math]\displaystyle{ q \in {}^{\omega} \mathbb{N}^{*} }[/math]. Therefore [math]\displaystyle{ n! = 2^q(\hat{u} + 1) }[/math] holds for [math]\displaystyle{ u \in {}^{\omega} \mathbb{N}^{*} }[/math] and necessarily [math]\displaystyle{ n! = 2^q(2^{q-2} \pm 1) }[/math]. Then the prime factorisation of [math]\displaystyle{ n! }[/math] requires [math]\displaystyle{ n \le 7 }[/math] giving the claim.[math]\displaystyle{ \square }[/math]

Reversion theorem of Taylor series

For [math]\displaystyle{ y \in f(\mathbb{D}), y(a) = b }[/math] and [math]\displaystyle{ y^{\prime}(a) \ne 0 }[/math], Bürmann's theorem yields:

[math]\displaystyle{ f^{-1}(y) = a + \tilde{n} {\LARGE{\textbf{+}}}_{m=1}^n{\widetilde{m}{\tilde{\varepsilon}}^{\acute{m}}(y - b)^m({\tilde{u}}^{\acute{m}k})^T(f(\varepsilon u^k + a)^{-m})}+\mathcal{O}(\varepsilon^n).\square }[/math]

Recommended reading

Nonstandard Mathematics

References

  1. ↑ Scheid, Harald: Zahlentheorie : 1st Ed.; 1991; Bibliographisches Institut; Mannheim; ISBN 9783411148417, p. 323.
Retrieved from "https://en.mwiki.de/index.php?title=Main_Page&oldid=310"