Pseudointegers

From Polymath1Wiki
Jump to: navigation, search

We have been considering more than one type of "pseudointegers", but here is the most general I think is useful in the EDP (I think we should create another article about EDP on pseudointegers):

A set of pseudointegers is the set [math]X=l_0(\mathbb{N}_0)[/math] of sequences over the non-negative integers that are 0 from some point, with a total ordering that fulfills:

  • [math]a\geq b, c\geq d \Rightarrow ac\geq bd[/math] and
  • [math]\forall a\in X: |\{b\in X|b\lta\}|\lt\infty [/math]

Here multiplication is defined by termwise addition: [math]ab=(a_1,a_2,\dots)(b_1,b_2,\dots)=(a_1+b_1,a_2+b_2)[/math]. For simplicity we furthermore assume that [math]p_1=(1,0,0,\dots)\ltp_2=(0,1,0,\dots)\lt...[/math] is an increasing sequence. These pseudointegers are called (pseudo)primes.

Logarithm and [math]\varphi[/math]

We would like to find a function [math]\varphi: X\to \mathbb{R}[/math] that preserves multiplication and order. In general, this function will not be injective. Look at a fixed element [math]x\in X, x\neq (0,0,0,\dots)[/math]. We now define the logarithm in base x by [math]\log_x(y)=\sup\{a/b|a\in\mathbb{N}_0,b\in \mathbb{N},x^a\leq y^b\}.[/math] This function fulfills some basis formulas

  1. [math]\log_x(x)=1[/math]
  2. [math]a/b\gt log_x(y)\Rightarrow x^a\gt y^b[/math]
  3. [math]a/b\lt log_x(y)\Rightarrow x^a\lt y^b[/math]
  4. [math]\forall y\in X\setminus \{(0,0,\dots)\}: \log_x(y)\in (0,\infty)[/math]
  5. [math]\log_x(yz)=\log_x(y)+\log_x(z)[/math]
  6. [math]y\leq z \Rightarrow\log_x(y)\leq \log_x(z)[/math]
  7. [math]\log_x(z)=\log_y(z)\log_x(y)[/math]

Proof: 1: We have [math]x^1\leq x^1[/math], so [math]\log_x(x)\geq 1/1=1[/math]. If [math]a\gtb[/math] then [math]x^a\gtx^b[/math], since otherwise [math]x^{b+n(a-b)}[/math] would be an infinite decreasing sequence. This shows [math]\log_x(x)\leq 1[/math].

2: If [math]a/b\gtlog_x(y)[/math], a/b can't be in the set we take sup of. So [math]x^a\gt y^b[/math].

3: For [math]y=(0,0,\dots)[/math] we have [math]\log_x(y)=0[/math] and the theorem is true, so we may assume [math]y\neq (0,0,\dots)[/math]. If [math]a/b \lt\log_x(y)[/math] we can find c and d so that [math]a/b\ltc/d[/math] and [math]x^c\leq y^d[/math]. Now we have [math](x^a)^{bc}=x^{abc}\leq y^{abd}=(y^b)^{ad}[/math] and using [math]ad\ltbd[/math] and that the power function is increasing for [math]y\neq (0,0,\dots)[/math] (see the proof of 1) we get [math]x^a\lty^b[/math]

4: If [math]\log_x(y)\leq 0[/math] (2) tells us that [math]x^1\gty^n[/math] for all n. But that we have a infinite bounded sequence which contradicts an axiom of the ordering on the pseudointegers. If [math]\log_x(y)=\infty[/math] (3) tells us that [math]x^n\lty^1[/math] for all n. Again we get a contradiction.

5: First I show [math]\log_x(yz)\leq \log_x(y)+\log_x(y)[/math]. Assume for contradiction that [math]\log_x(yz)\gt \log_x(y)+\log_x(y)[/math]. Now we can find [math]a_1,a_2,b[/math] so that [math]\frac{a_1}{b}\gt\log_x(y)[/math], [math]\frac{a_2}{b}\gt\log_x(z)[/math], and [math]\log_x(yz)\gt\frac{a_1+a_2}{b}[/math]. Form (2) we know that [math]x^{a_1}\gty^b[/math] and [math]x^{a_2}\gtz^b[/math]. And thus [math]x^{a_1+a_2}\gty^bz^b=(yz)^b[/math]. Using (3) we get a contradiction with [math]\log_x(yz)\gt\frac{a_1+a_2}{b}[/math]. The proof of the opposite inequality is similar.

6: This is equivalent to [math]\log_x(y)\gt\log_x(z)\Rightarrow y\gtz[/math], so assume that [math]\log_x(y)\gt\log_x(z)[/math]. Now we can find [math]\log_x(y)\gt\frac{a}{b}\gt\log_x(z)[/math]. This implies [math]z^b\ltx^a\lty^b[/math] and then [math]z\lty[/math].

7: First I show that [math]\log_x(z)\leq \log_y(z)\log_x(y)[/math]. Assume for contradiction that [math]\log_x(z)\gt\log_y(z)\log_x(y)[/math]. Now we can find [math]a,b,c\in\mathbb{N}[/math] with [math]\log_x(z)\gt\frac{a}{b}[/math], [math]\frac{a}{c}\gt\log_y(z)[/math], and [math]\frac{c}{b}\gt\log_x(y)[/math]. Using (2) we get [math]y^a\gtz^c[/math] and [math]x^c\gty^b[/math] and from this we get [math]x^{ac}\gty^{ab}\gtz^{bc}[/math] and then [math]x^a\gtz^b[/math] contradicting [math]\log_x(z)\gt\frac{a}{b}[/math]. The proof of the opposite inequality is similar.

We can now define a function [math]\varphi_x(y)=e^{\log_x(y)}[/math]. For this function we have:

  1. [math]\varphi_x(yz)=\varphi_x(y)\varphi_x(z)[/math]
  2. [math]y\leq z\Rightarrow\varphi_x(y)\leq \varphi_x(z)[/math]

Densities of the pseudointegers divisible by y

Let [math]n_p[/math] where [math]n\in\mathbb{N}[/math] denote the nth pseudointeger (here p stands for pseudo, it is not a variable) and let [math][n_p][/math] denote the set of the n smallest pseudointegers. We define the density of the pseudointegers divisible by y to be

[math]d_y=\lim_{n\to\infty}\frac{|yX\cap [n_p]|}{n}=\lim_{n\to\infty}\frac{|\{z\in X|yz\leq n_p\}|}{n}[/math]

if the limit exist. Clearly [math]d_y\in [0,1][/math] if the limit exist. More generally we can always define

[math]i_y=\liminf_{n\to\infty}\frac{|yX\cap [n_p]|}{n}=\liminf_{n\to\infty}\frac{|\{z\in X|yz\leq n_p\}|}{n}[/math]

[math]s_y=\limsup_{n\to\infty}\frac{|yX\cap [n_p]|}{n}=\limsup_{n\to\infty}\frac{|\{z\in X|yz\leq n_p\}|}{n}[/math]

Using that the set [math]\{z\in X|yz\leq n_p\}[/math] is a set of the form [math][m_p][/math] for some m, we get:

[math]\{z\in X|xyz\leq n_p\}=\{z\in X|x(yz)\leq n_p\}=\{z\in X|yz\in\{a\in X|xa\leq n_p\}\}=\{z\in X|yz\leq|\{a\in X|xa\leq n_p\}|_p\}.[/math]

From this we get the inequalities: [math]i_xi_y\leq i_{xy} [/math] and [math]s_{xy}\leq s_xs_y[/math]. In particular if [math]d_x[/math] and [math]d_y[/math] exists, then [math]d_{xy}[/math] exists and [math]d_{xy}=d_xd_y[/math]. By induction we get that [math]d_{x^n}[/math] exists and [math]d_{x^n}=d_x^n[/math]. If [math]x\leq y[/math] we have [math]\{z\in X|yz\leq n_p\}\subset \{z\in X|yz\leq n_p\}[/math] so in general [math]i_y\leq i_x[/math] and [math]s_y\leq s_x[/math] and if both densities exists [math]d_y\leq d_x[/math].

If [math]d_x=1[/math] for some [math]x\neq (0,0,\dots)[/math] we have [math]d_{x^n}=1[/math] of all n, and for any y there is a n so that [math]y\geq x^n[/math]. This gives us [math]1=i_{x^n}\leq i_y[/math] which implies that [math]d_y[/math] exists for any y and [math]d_y=1[/math].

If [math]d_x=0[/math] for some x then for any [math]y\neq (0,0,\dots)[/math] we know that [math]d_y[/math] exists and [math]d_y=0[/math]: Assume for contradiction that [math]s_y\gt0[/math]. Then for some n, [math]y^n\geq x[/math]. This implies that [math]s_y^n=s_{y^n}\leq s_x=0[/math]. Contradiction.

Assume that [math]d_x[/math] and [math]d_y[/math] exists and [math]d_x\in (0,1)[/math]. Now we know that [math]d_y\in (0,1)[/math] (I haven't been able to show this without the assumption that [math]d_y[/math] exists). We know that for [math]a,b\in \mathbb{N}[/math]:

[math]\frac{a}{b}\gt\log_x(y)\Rightarrow x^a\gty^b\Rightarrow d_{x^a}\leq d_{y^b}\Rightarrow d_x^a\leq d_y^b\Rightarrow a\log(d_x)\leq b\log(d_y)\Rightarrow \frac{a}{b}\geq \frac{\log(d_y)}{\log(d_x)}[/math]

(notice that log are taken on numbers in (0,1) so they are negative) where [math]log[/math] is the usual logarithm on the reals. Similarly we get [math]\frac{a}{b}\lt\log_x(y)\Rightarrow \frac{a}{b}\leq \frac{\log(d_y)}{\log(d_x)}[/math]. This tells us that [math]\log_x(y)=\frac{\log(d_y)}{\log(d_x)}[/math]. From this we get that [math]-\log(d_x)\log_x(z)=-\log(d_x)\log_y(z)\log_x(y)=-\log(d_y)\log_y(z)[/math], so the function [math]\log: X\to \mathbb{R}[/math] defined by [math]\log(z)=-\log(d_x)\log_x(z)[/math] for some [math]x\in X[/math] where [math]d_x[/math] exists and [math]d_x\in (0,1)[/math], doesn't depend on the x we choose. From this function we define [math]\varphi(z)=e^{\log(z)}[/math]. If [math]d_z[/math] exists (again, it would be nice to find a proof that it does or to prove that it does have to) we know that [math]\varphi(z)=e^{\log(z)}=e^{-\log(d_z)\log_z(z)}=(e^{\log(d_z)})^{-1}=\frac{1}{d_z}[/math].

Density of the set of pseudointegers

If there exists a [math]x\in X: d_x\in (0,1)[/math], we define

[math]d=\lim_{n\to\infty}\frac{|\varphi(X)\cap (0,n]|}{n}[/math]

if the limit exist. This limit can be greater than 1 and for the integers it is 1. This means that looking only at the structure of X, we can "see if there is too few/many pseudointegers" compared to the integers.

Here I would like to have a proof that d exists under some assumptions. Using the next paragraph this would imply that [math]d_x[/math] exists for all [math]x\in X[/math]. I don't think it is enough to assume that [math]d_x\in (0,1)[/math] for one x, but it might be enough to assume that [math]d_x,d_y \in (0,1)[/math] for some x,y such that [math]\log_x(y)[/math] is irrational.

From [math]d[/math] to [math]d_x[/math]

Let [math]\varphi: X \to\mathbb{R}[/math] be any function such that [math]\varphi(x)\varphi(y)=\varphi(xy)[/math] and [math]x\leq y \Rightarrow \varphi(x)\leq \varphi(y)[/math], and such that the density

[math]d=\lim_{n\to\infty}\frac{|\varphi(X)\cap (0,n]|}{n}[/math]

exists and [math]d\in (0,\infty)[/math] (in particular this implies that [math]\lim_{n\to\infty}\varphi(n_p)=\infty[/math]). We can now find [math]d_x[/math]:

[math]d_x=\lim_{n\to\infty}\frac{|\{z\in X|xz\leq n_p\}|}{n}=\lim_{n\to\infty}\frac{|\{z\in X|\varphi(x)\varphi(z)\leq \varphi(n_p)\}|}{|\{z\in X|\varphi(z)\leq \varphi(n_p)\}|}=\lim_{n\to\infty}\frac{|\varphi(X)\cap (0,\frac{\varphi(n_p)}{\varphi(x)}]|}{\varphi(n_p)}\frac{\varphi(n_p)}{|\varphi(X)\cap (0,\varphi(n_p)]|}=\frac{1}{\varphi(x)}.[/math]

Notice that in general we don't have [math]\{z\in X|xz\leq n_p\}=\{z\in X|\varphi(x)\varphi(z)\leq \varphi(n_p)\}[/math] but [math]\{z\in X|\varphi(x)\varphi(z)\lt \varphi(n_p)\}\subset\{z\in X|xz\leq n_p\}\subset\{z\in X|\varphi(x)\varphi(z)\leq \varphi(n_p)\}[/math]. The above works because we are taking limits.