Difference between revisions of "Main Page"

From MWiki
Jump to: navigation, search
m (RU method)
(Counting theorem for algebraic numbers)
(24 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 ==
=== RU method ===
+
=== Counting theorem for algebraic numbers ===
If <math>A \in {}^{\nu}\mathbb{Q}^{n \times n}</math> is regular in the linear system (LS) <math>Ax = b \in  {}^{\nu}\mathbb{Q}^{n}</math> 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 ===
+
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>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: ====
 +
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>
  
=== Corollary ===
 
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>.
 
 
'''Remark:''' Extending the theorem to complex <math>A</math> and <math>b</math> is easy. By the Banach fixed-point theorem, the <math>RU</math> method converges linearly for every regular LS.
 
 
== Recommended reading ==
 
== Recommended reading ==
  
 
[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.