Difference between revisions of "Main Page"

From MWiki
Jump to: navigation, search
(Intex method)
(Counting theorem for algebraic numbers)
(21 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
= Welcome to MWiki =
 
= Welcome to MWiki =
 
== Theorem of the month ==
 
== Theorem of the month ==
The intex method solves every solvable LP in <math>\mathcal{O}({\vartheta}^{3})</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.
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 the <em>height</em> <math>h</math> have the initial value <math>h_0 := s |\min \; \{b_1, ..., b_m, -d_1, ..., -d_n\}|</math> for the <em>elongation factor</em> <math>s \in \, ]1, 2]</math>.</br>
 
The LP min <math>\{h \in [0, h_0] : x \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}, y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m},{b}^{T}y - {c}^{T}x \le h, Ax - b \le (h, ..., h)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, c - {A}^{T}y \le (h, ..., h)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}\}</math> has <math>k</math> constraints and the feasible starting point <math>(x_0, y_0, h_0/s)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m+n+1}</math>, e.g. <math>(0, 0, h_0/s)^{T}</math>.</br>
 
It identifies the mutually dual 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>.
 
  
Let the point <math>p := (x, y, h)^T</math> approximate the subpolytope’s centre of gravity <math>P^*</math> as <math>p_k^* := (\min p_k + \max p_k)/2</math> until <math>{|| \Delta p ||}_{1}</math> is sufficiently small. Here <math>x</math> takes precedence over <math>y</math>. Then extrapolate <math>p</math> via <math>{p}^{*}</math> into <math>\partial P^*</math> as <math>u</math>. Put <math>p := p^* + (u - p^*)/s</math> to shun <math>\partial P^*</math>. Hereon approximate <math>p</math> more deeply again as centre of gravity. After optionally solving all LPs min<math>{}_{k} {h}_{k}</math> by bisection methods for <math>{h}_{k} \in {}^{\omega}\mathbb{R}_{\ge 0}</math> in <math>\mathcal{O}({\vartheta}^{2})</math> each time, <math>v \in {}^{\omega}\mathbb{R}^{k}</math> may be determined such that <math>v_k := \Delta{p}_{k} \Delta{h}_{k}/r</math> and <math>r :=</math> min<math>{}_{k} \Delta{h}_{k}</math>. Simplified let <math>|\Delta{p}_{1}| = ... = |\Delta{p}_{m+n}|</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\sum\limits_{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>
  
Here min <math>{h}_{m+n+1}</math> may be solved for <math>p^* := p + tv</math> where <math>t \in {}^{\omega}\mathbb{R}_{\ge 0}</math> and <math>{v}_{m+n+1} = 0</math>. If min<math>{}_{k} {h}_{k} r = 0</math> follows, end, otherwise start over until min <math>h = 0</math> or min <math>h &gt; 0</math> is certain. If necessary, relax the constraints temporarily by the same small modulus.</br>
+
== Recommended reading ==
Since almost every iteration step in <math>\mathcal{O}({\omega\vartheta}^{2})</math> halves <math>h</math> at least, the strong duality theorem yields the result.<math>\square</math>
 
  
== 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 22:23, 30 June 2022

Welcome to MWiki

Theorem 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\sum\limits_{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]

Recommended reading

Nonstandard Mathematics

References

  1. Scheid, Harald: Zahlentheorie : 1st Ed.; 1991; Bibliographisches Institut; Mannheim; ISBN 9783411148417, p. 323.