125
$\begingroup$

This sandbox is intended for saving drafts of long, complex posts, especially posts whose composition takes a long time. It serves to localize to one thread the front-page "bumps" caused by edits to drafts of such posts, so that they may be easily ignored. Also, it helps to guard against losing longly-composed posts due to system crashes.

When you are happy with your draft here, you may simply copy the code and paste it to the desired location.

Proper Use of the Sandbox

  1. Do not post a new answer! We wish all the answers on this page to be owned by the Community user (so that only a non-sentient bot is informed of edits to these answers). Posting a new answer will make you the owner, meaning that you will be notified whenever another user makes an edit to that answer.

    The sandbox has been "wiki locked" to prevent the creation of new answers. There are more than enough existing answers for users to edit over, and this will greatly reduce the frequency at which we request that the answers be disassociated from specific users.

  2. Do not delete answers! Deleting seems like a reasonable option, but there are no "hard deletions" on Stack Exchange, and users with sufficient privileges will still see your supposedly deleted postings. Deleted answers will be undeleted and cleared for the use of others.

  3. Do look for an answer which indicates that it is free and then edit it to your heart's content. If none appears available, take over the one that has been left unchanged the longest (which will appear at the bottom of the page if you order answers by "activity").

  4. Do not expect your draft to remain untouched for days. There are no guarantees that your draft will be the latest revision if you return days later. While users will try not to step over others' toes, it may happen that an unfinished draft is edited out. Your draft will, however, still exist as a revision of the answer it was made in. If your drafting is expected to take place over a longer period of time, either

    • take note of the URL of the answer provided by clicking the share button, or
    • save a copy of your draft locally (or even "in the cloud").
  5. Do clear your draft when you are finished. This includes removing all $\LaTeX$ from your answers. Replacing all code with a simple statement like

    This answer is free for anyone to use

    is sufficient. Periodically users may go through and free up answer slots that have not been edited in, say, over one month. But you can aid in the smooth running of this sandbox by clearing away your drafts when you are finished with them.

  6. Do not "claim" multiple answers concurrently. Since this post is closed, the answers are a limited resource. If you really must compose several long, complex posts at the same time, you can still use a single answer, separating the different drafts using Markup: horizontal rules (---) and/or headings (# Header 1 #) are natural choices.

  7. Do not create new such sandboxes. The point of having a unique such sandbox is that it minimizes the noise on the front page when the sandbox is edited. If there were multiple sandboxes they will frequently occupy numerous front page slots, pushing other topics off the front page, and increasing noise.

$\endgroup$
  • 8
    $\begingroup$ I have added a [sandbox] tag to allow people ignore it more easily (via software support of ignoring tags), and since it seems that we have two sandboxes now, a tag may seem a bit more in place here. $\endgroup$ – Asaf Karagila Jul 18 '12 at 8:35
  • 21
    $\begingroup$ (+1) For thinking outside the (sand)box. $\endgroup$ – cardinal Jul 18 '12 at 19:40
  • 14
    $\begingroup$ At the suggestion of the moderators, I have gone and changed the associated owners of all the answers here to the Community user. This way, the original owners will not receive excess pings for each time another user uses the draft space for their work. Enjoy! $\endgroup$ – Grace Note Oct 5 '12 at 14:45
  • 3
    $\begingroup$ To prevent crashes I've found the "Bookmarks to disable/enable MathJax", provided in here, pretty useful. $\endgroup$ – leo Dec 17 '12 at 18:03
  • 3
    $\begingroup$ PSA: Between the creation of this sandbox (in July 2012) and today (December 2015), technology has advanced. Something like StackEdit (or others, it's simply the only one I know) essentially solves all the limitations of this sandbox. You can have multiple concurrent drafts, you don't have to worry about polluting meta's front page, you can leave your draft untouched for days and expect it to still be there, you don't have to explicitly clear up your draft when you're done... Maybe someday we can get rid of this outdated crutch. $\endgroup$ – Najib Idrissi Dec 2 '15 at 14:07

17 Answers 17

18
$\begingroup$

This answer is available for anyone to use.

$\endgroup$
16
$\begingroup$

Proposals to improve your PARI/GP-routines

\\ define global constants instead of calling recomputations of costly functions
beta=log(3)/log(2)    \\ of course with sufficient internal precision, I use 200 by default

\\ then your functions become

nj(i)=3^i*frac((2^i*3^(2^(ceil(i*beta)-i-2)))
      /(2^ceil(i*beta)*3^i))-2^i/2^ceil(i*beta)

n0(i)=2^ceil(i*beta)*
         frac((2^i*3^(2^(ceil(i*beta)-i-2)))
          /(2^ceil(i*beta)*3^i))-1

I think it is a good habit, to use (and reserve) one-letter variable like i,j,k always for indices of loops, vectors etc. I take $N$ for the (N)umber-of-odd-steps

nj(N)=3^N*frac((2^N*3^(2^(ceil(N*beta)-N-2)))
      /(2^ceil(N*beta)*3^N))-2^N/2^ceil(N*beta)

n0(N)=2^ceil(N*beta)*
         frac((2^N*3^(2^(ceil(N*beta)-N-2)))
          /(2^ceil(N*beta)*3^N))-1

Now a new constant internal to your function which captures the repeated "ceil()"-expression. I use "S" for it, the number of even steps, or (S)um of exponents of 2. This is depending on the argument of your function and must be computed inside your function as a local constant:

nj(N)=my(S=ceil(N*beta));
      3^N*frac((2^N*3^(2^(S-N-2)))/(2^S*3^N))-2^N/2^S

n0(N)=my(S=ceil(N*beta));
      2^S*frac((2^N*3^(2^(S-N-2)))/(2^S*3^N))-1

Next, another local constant with letter $B$, because I've to use often the difference $S-N=B$ and cancel $2^S/2^N = 2^B$

nj(N)=my(S=ceil(N*beta),B=S-N);
      3^N    * frac(3^(2^(B-2)-N) /2^B )  -  1/2^B

n0(N)=my(S=ceil(N*beta),B=S-N);
      2^S    * frac(3^(2^(B-2)-N) /2^B )   - 1

Finally two more improvements are possible. One is the avoiding of intermediate gigantic numbers like $3^{2^B}$ by putting cancellations into the exponents, and second, the common expression of the frac() into an own function - to make sure the reader sees immediately, that it is the same term in both functions:

beta = log(3)/log(2)
fr(N,B)=  frac(2^(  beta*(2^(B-2)-N)  - B  ))

nj(N)  =  my(S=ceil(N*beta),B=S-N,fr);
          3^N * fr(N,B) -  1/2^B

n0(N)  =  my(S=ceil(N*beta),B=S-N,fr);
          2^S * fr(N,B) -  1
$\endgroup$
15
$\begingroup$

This answer is available for anyone to use.

$\endgroup$
10
$\begingroup$

The following is about getting help for a proof on existence and indexability of periodic points of the exponential-function, here with base $e:=\exp(1)$.

Update The question is a complete rewriting of the previous formulation of my question which I hope is much better focused and straightforward.

Let us define $f(z):=\exp(z)$ for $z \in \mathbb C$. Iteration may be denoted by $f°^1(z)=f(z)$ and $f°^{h+1}(z)=f°^{h}(f°^1(z))$.

Fixpoints: it is known (for instance W. Bergweiler1, pg 16),

  • that $f$ has infinitely many fixpoints (=$1$-periodic points) $p_1$,
  • that all of them are non-real, and
  • that all of them are repelling.

They may be indexed by the branchindex $k \in \mathbb Z$ used in the Lambert-$W(k;z)$-function like $p_{1:k}$.

Periodic points: it is even more known that for all $n$ the sets of $n$-periodic points are as well infinite1(pg.16). Let us denote such a set from now $\mathbb P_n$. So, in generalization of the indexing of $1$-periodic points, one might say, that the set $\mathbb P$ of all $\mathbb P_n , \text{with } n=1 \ldots \infty $ can be indexed by $\mathbb Z^\infty$.
But I think this is not precise enough; I assume, and would like to prove,

  • (Conj. 1) that actually $\mathbb P_n$ can exactly be indexed by $\mathbb Z^n$ $\qquad \Leftarrow \mathbb {\text{problem to be proved}}$

Fo my approach improving (Conj. 1) I refer to the property, that a fixed- or periodic points, which is repelling for iteration over function $f()$, is attracting for iteration over its inverse, which means is attracting for the iteration over the $\log()$-function. From Bergweiler, pg. 17, I take, that all periodic points are repelling on iteration on $f()$ and thus are all attracting for its inverse.

For convenience of further notation let us define $\log()$ as $g(x):=\log(x)$ and as well the iteration $g°^1(z)=g(z)$ and $g°^{h+1}(z)=g°^{h}(g°^1(z))$.

To make $g()$ a true inverse of $f()$, we'll need the branch index(es) explicite, so let us simply extend the notation $$g(x,k):=\log(x) + k \cdot C \qquad \text{where } C=2 \pi î$$ This allows to make precisely for some fixed $z$ $$ g(f(z),0)=z $$ but for the reversion of some $z'=z + k\cdot C$ we need $$ g(f(z'),k)=g(f(z+k\cdot C),k) =g(f(z),k)=z+k \cdot C=z' $$

For adressing periodic points of period-length $n$ we expand the notation further $$ \begin{array}{} g(z,[k_1])&:= g(z,k_1) \\ g(z,[k_1,k_2])&:= g(g(z,k_1),k_2) \\ g(z,[k_1,k_2,...,k_n])&:= g(...g(g(z,k_1),k_2)...,k_n) \\ &\small \text{where all $k_j \in \mathbb Z$}\\ \end{array}$$

Finally I use $K_n:=[k_1,k_2,...,k_n]$ for the vector of branch-indexes. With this I conjecture now the following:

  1. iterations of each expression $z_{i+1}=g(z_i,K_n)$ are attracting.
  2. we can approximate any periodic point $p_{n,K}$ by simple fixed-point iteration of the previous with some suitable initial value $z_0 \ne 0$ according to $$p_{n,K} = \lim_{i \to \infty} z_{i+1}=g(z_i,K_n)$$ (of course we can increase speed of approximation when Newton-iteration on $g()$ follows).
  3. the iteration for a given $K_n$ is attracting over the whole complex plane except for the initial values $z_0 \in \{0,1,e,e^e,...\}$.
    Non uniqueness occurs only for $K=[0]$ (and its non-primitive repetitions $K=[0,0]$,... $K=[0,0,...,0]$) in that the initial value $z_0$ is relevant for to converge towards the $1$-periodic point either in the upper or in the lower half plane.
  4. Main conjecture to be proved: All $n$-periodic points with the exception of the conjugated primary fixed points $p_{1:[0]}$ and $\overline {p_{1:[0]}}$ (which have the same branch index-vector $K=[0]$) are in bijection to the indexes $K_n$ and can be approximated by simple fixed-point iteration over $g(z,K_n)$ (if desired followed by Newton-iteration on $g(z,K_n)$ to speed up convergence).

Remark: I have seen, that with exponential bases different from $e:=exp(1)$ spuriously non-uniquenesses and non-existences of $n$-periodic points occur, which I cannot yet nail down except by giving a couple of heuristic examples. However, large surveys on the exponential with base $e$ -as discussed here- seem to have only that one exception as mentioned in (3.).


An illustration of periodic points of periods $n=1..5$ . Those were found by screening the square $-4-4î...4+4î$ on the complex plane in steps by $1/40$ with the newton-iteration applied. The list has then been checked whether they all agree with the $K_n$-indexing scheme; all found periodic points have a valid $K$-index.
picture


A handful of used literature: I've found some resources on fixed points and their properties for the exponential function base $e$, but less about $n$-periodic points. The most fruitful so far was the habilitation of Walter Bergweiler, 1991. If there are more comprehensive texts (optimally online available), please leave a comment.

1Bergweiler, Walter, Periodische Punkte bei der Iteration ganzer Funktionen, Aachen: Rheinisch-Westfälische Techn. Hochsch., Math.-Naturwiss. Fak., Habil.-Schr. 51 S. (1991). ZBL0728.30021.

Pg.16:

  • "Dieses Ergebnis wurde im Jahre 1948 duch Rosenbloom verallgemeinert, der zeigte, daß für jedes $n \gt 2$ unendlich viele periodische Punkte der Periode $n$ existieren"
  • "Baker im Jahre 1960 (...) bewies (...), daß höchstens eine (von $f$ abhängige) natürliche Zahl $n$ existiert mit der Eigenschaft, daß $f$ nur endlich viele periodische Punkte der primitive Periode $n$ hat."

Pg. 17:

  • "Satz 2: Es sei $f$ eine ganze transendente Funktion und es sei $n \ge 2$. Dann hat $f$ unendlich viele abstoßende periodische Punkte der primitiven Periode $n$."
  • "Wir bemerken noch, daß ganze Funktionen keine anziehenden periodischen Punkte zu haben brauchen. Ein Beispiel, (...) ist durch $f(z)=e^z$ gegeben."

Additional readings:
Hellmuth Kneser, [Real analytic solutions of the equation $φ(φ(x))=e^x$ and related functional equations. (Reelle analytische Lösungen der Gleichung $φ(φ(x))=e^x$ und verwandter Funktionalgleichungen.)], J. Reine Angew. Math. 187, 56-67 (1949)(German).Zbl0035.04801.3

Shen, Zhaiming; Rempe-Gillen, Lasse, The exponential map is chaotic: an invitation to transcendental dynamics, Am. Math. Mon. 122, No. 10, 919-940 (2015). ZBL1361.37002.4
Here general aspects of the set of $n$-periodic points are presented in existence-theorems. Even the concept of infinite non-periodic, but not diverging-to-infinity, orbits -as part of the general chaotic behaviour- is covered by the list of theorems.(G.H.)

An introductory article which deals with the question of $\mathbb P_1$ (fixed-) points on the branches of the $\log()$-function by Stanislav Sykora (2016) at his web-space.

$\endgroup$
8
$\begingroup$

This answer is available for anyone to use

$\endgroup$
8
$\begingroup$

Since $P$ is a quadratic polynomial and $P(0) = 0$, one can write $$ P(q) = aq+ bq^2$$ for some real numbers $a, b$. The conditions $$P'(\bar{q}_P)+\bar{q}_P=1, \frac{P(\hat{q}_P)}{\hat{q}_P}+\hat{q}_P=1$$ translates to \begin{align*}\tag{1} a + (2b+1) \bar q_P &= 1, \\ a+ (b+1) \hat q_P &= 1 \end{align*} or $$ \bar q_P = \frac{1-a}{2b+1}, \ \ \hat q_P = \frac{1-a}{b+1}.$$ We will assume that our conditions are that $\bar q_P ,\hat q_P>0$ instead of $\ge 0$ (when one of them is zero, $J(P) = 0$. Thus it suffices to check that the maximum of $J$ is positive, which we will do later).

The above conditions together with (1) imply that $b\neq -1$ and $b\neq -1/2$.

Next, note that $\bar q_P = \hat q_P$ only when $a=1$. The lines $$ a=1, \ \ b=-1, \ \ b = -1/2$$ split the $a-b$ plane into six region. Only two of them $$R_1 = \{a<1, b>-1/2\}, \ \ R_2 = \{ a>1, b<-1\}$$ gives BOTH positive $\bar q_P, \hat q_P$.

In each region either $q^*_P = \bar q_P$ or $\hat q_P$. For example, in $R_1$ we have $\hat q_P > \bar q_P$, giving $q^*_P = \bar q_P$.

Then one can check in each region: For example in $R_1$,

\begin{align*} J(aq+ bq^2) &= \int_0^{\frac{1-a}{2b+1}} (a+2bq-c)(1+q-\lambda (a+bq)-(1-\lambda)(a+2bq))dq \\ &=\int_0^{\frac{1-a}{2b+1}} (a+2bq-c)(1+q-(a+bq)+\lambda bq)dq \\ &=\int_0^{\frac{1-a}{2b+1}} (a-c+2bq)(1-a +(1 +(\lambda -1)b)q) dq \\ &=\int_0^{\frac{1-a}{2b+1}} \bigg(a(1-a) + \big(2(1-a)b +a(1 +(\lambda -1)b) \big)q + 2b(1 +(\lambda -1)b)q^2\bigg) dq\\ &= \frac{a(1-a)^2}{2b+1} + \frac{2(1-a)b +a(1 +(\lambda -1)b)}{2(2b+1)^2} \end{align*}

$\endgroup$
7
$\begingroup$

This answer is available for anyone to use.

$\endgroup$
7
$\begingroup$

This space is available for anyone

$\endgroup$
7
$\begingroup$

this box is free for anyone to use

$\endgroup$
5
$\begingroup$

This slot is free for everyone to use

$\endgroup$
5
$\begingroup$

This answer is available for anyone to use.

$\endgroup$
4
$\begingroup$

This answer is available for anyone to use.

$\endgroup$
4
$\begingroup$

With the substitution $u=e^x$, the integral is transformed to $$I=\int^\infty_0\frac{x\sqrt{e^x-1}}{1-2\cosh x}dx=-\int^\infty_1\frac{\ln x \sqrt{x-1}}{x^2-x+1}dx$$

Consider $$\oint_C \frac{\ln z \sqrt{z-1}}{z^2-z+1}dz$$ with $C$ being a double keyhole contour, avoiding branch cut of $\sqrt{z-1}$ along $[1,\infty)$ and that of principal logarithm $\ln z$ along $(-\infty,0]$.

Simple estimations show that all circular integrals are zero, thus by residue theorem $$\left(\int_{[1,\infty)^+}-\int_{[1,\infty)^-}+\int_{(-\infty,0]^+}-\int_{(-\infty,0]^-}\right)\frac{\ln z \sqrt{z-1}}{z^2-z+1}dz=2\pi i\sum\text{Res}$$

Note that the second integral is the negative of the first one, which equals $-I$.

The third integral is $$\int_{-\infty}^0 \frac{(\ln |t|+\pi i) \sqrt{t-1}}{t^2-t+1}dt$$ while the fourth is $$\int_{-\infty}^0 \frac{(\ln |t|-\pi i) \sqrt{t-1}}{t^2-t+1}dt$$

Hence, $$2\pi i\sum\text{Res}=-2I+\int_{-\infty}^0 \frac{(2\pi i) \sqrt{t-1}}{t^2-t+1}dt$$ $$I=-\pi i\sum\text{Res}+\pi i\int_{-\infty}^0 \frac{\sqrt{t-1}}{t^2-t+1}dt$$ $$I=-\pi i\sum\text{Res}-\pi \int^{\infty}_0 \frac{\sqrt{t+1}}{t^2+t+1}dt$$

By elementary methods, the integral on the right can be evaluated to $\displaystyle{\frac\pi 2-\frac{\ln(2-\sqrt 3)}{\sqrt3}}$.


What is left is calculations of the residue at $r$ and $\overline r$, where $r=\frac{1+i\sqrt 3}{2}=e^{i\pi/3}$, a root of $z^2-z+1$.

Note that with our choice of branch cut of $\sqrt{z-1}$ (i.e. $\arg z\in[0,2\pi)$), we have $$\sqrt{\overline{r}-1}=-\overline{\sqrt{r-1}}$$

Therefore, $$\text{Res}_{z=r}=\frac{\ln r\sqrt{r-1}}{i\sqrt 3}$$ $$\text{Res}_{z=\overline r}=\frac{\ln \overline r\sqrt{\overline r-1}}{-i\sqrt 3}=\frac{ \overline{\ln r} \left(-\overline{\sqrt{r-1}}\right)}{\overline{i\sqrt 3}}=-\overline{\text{Res}_{z=r}}$$

Hence, $$\sum\text{Res}=2i\text{Im}\text{Res}_{z=r}=2i\text{Im}\frac{\ln e^{i\pi/3}\sqrt{e^{i\pi/3}-1}}{i\sqrt 3}=2i\text{Im}\frac{\frac{i\pi}{3}e^{i\pi/3}}{i\sqrt 3}=\frac{\pi i}3$$


As a result, $$I=\frac{\pi}{\sqrt 3}\ln(2-\sqrt 3)-\frac{\pi^2}{6}$$

$\endgroup$
4
$\begingroup$

Let's prove, without using any set theory, that the natural numbers are the natural numbers!

Specifically, we're going to show that the natural numbers, defined as the inductive data type generated by one constant and one unary operation, are the natural numbers, defined as the free monoid with one generator. We'll do this by sheer symbol manipulation, without recourse to any underlying foundational theory.

Starting definitions

Define a general presentation as an algebraic theory. When we talk about general presentations, we are interested in the initial algebra of the underlying theory, and we call it the algebra presented by that presentation. Given two general presentations $P$ and $Q$, we say that $Q$ is a conservative extension of $P$ if every axiom (that is, every term (generator) and every equation) of $P$ is also an axiom of $Q$, and the algebras generated by $P$ and $Q$ are isomorphic (when considered as algebras for the underlying theory of $P$).

$\newcommand{Nat}{\mathbb{N}}\newcommand{Nind}{\Nat_\mathrm{ind}}\newcommand{Nmon}{\Nat_\mathrm{mon}}$In order to show that "the natural numbers are the natural numbers", we will consider two general presentations $\Nind$, representing the first definition of the natural numbers, and $\Nmon$, representing the second, and we will show that there is a third general presentation, $\Nat_\mathrm{ind+mon}$, which is a conservative extension of both.

First, here is $\Nind$:

  • $\newcommand{Zero}{\mathrm{Zero}}\Zero : \Nat$
  • $\newcommand{PlusOne}{\mathrm{PlusOne}}\PlusOne : \Nat \to \Nat$

In other words, $\Nind$ consists of a generator (or term) called $\Zero$ of arity zero; a generator called $\PlusOne$ of arity one; and no equations.

The general presentation $\Nmon$ is more complex. Here it is:

  • $\Zero : \Nat$
  • $\newcommand{Plus}{\mathrm{Plus}}\Plus : \Nat \times \Nat \to \Nat$
  • $\newcommand{One}{\mathrm{One}}\One : \Nat$
  • $\Plus(\Zero, x) = x$
  • $\Plus(x, \Zero) = x$
  • $\Plus(x, \Plus(y, z)) = \Plus(\Plus(x, y), z)$

The general presentation $\Nmon$ consists of three generators (two of arity 0, one of arity 2) and three equations. Notice that the axioms of $\Nmon$, aside from $\One$, are simply the axioms of a monoid. Adding $\Nmon$ to the general presentation turns it into a presentation of a monoid with one generator.

How can we prove things?

Now, before we continue, here's a question: how can we identify conservative extensions of $\mathbb{N}_\mathrm{ind}$ without recourse to an underlying foundational theory?

Well, the Tietze transformations are a collection of rules for transforming a group presentation into another equivalent group presentation. The new group presentation is equivalent in the sense that the group generated by the new presentation is isomorphic to the group generated by the old presentation, and, furthermore, the isomorphism preserves any generators which were not affected by the transformation.

There are four Tietze transformations:

  • Adding a generator: You may add a generator, along with an equation asserting that the new generator equals some term.
  • Removing a generator: If an equation asserts that some generator equals some term, and that generator does not appear in the right-hand side of that equation, or anywhere in any other equation, then you may remove that generator and that equation.
  • Adding an equation: You may add an equation, if you can prove that equation from the other equations.
  • Removing an equation: You may remove an equation, if you can prove that equation from the other equations.

For the purposes of adding and removing an equation, a proof is not allowed to refer to outside axioms, or even to use first-order logic; the proof must be performed entirely using the substitution and reflexive properties of equality.

The Tietze transformations work just fine for general presentations, too. Specifically, if one applies the "add a generator" or "add an equation" transformation to a general presentation, the new presentation will be a conservative extension of the old one. If one applies the "remove a generator" or "remove an equation" transformation, the converse happens: the new presentation will be conservatively extended by the old one.

Given an underlying theory such as ZFC, hopefully the assertions I made in the above paragraph would not be too difficult to prove. For now, we simply take the four transformations as axioms.

The Tietze transformations will get us part of the way where we want to go, but in order to go the entire way, we will need to use two additional transformations:

  • Adding a function: You may add a function, along with a collection of equations which constitute a primitive recursive definition of that function.
  • Removing a function: You may perform the reverse of adding a function.

There will be an example of just what I mean by this below.

In addition, inductive proofs of equality will be permitted. I apologize for not giving a definition of what constitutes an inductive proof of equality.

The proof

We now have all we need to show that there is a general presentation $\Nat_{\mathrm{ind+mon}}$ which is a conservative extension of both $\Nind$ and $\Nmon$.

We start with $\Nind$, which consists of only these two axioms:

  1. $\Zero : \Nat$
  2. $\PlusOne : \Nat \to \Nat$

We will now apply the "adding a function" transformation. We add a function symbol and two equations:

  1. $\Plus : \Nat \times \Nat \to \Nat$
  2. $\Plus(\Zero, y) = y$
  3. $\Plus(\PlusOne(x), y) = \PlusOne(\Plus(x, y))$

Notice that the definition of $\Plus$ is by cases, and the cases are perfectly exhaustive: every possible pair of terms of $\Nind$ fits exactly one of the cases. Furthermore, although the definition of $\Plus$ is recursive, the recursion is primitive recursion.

We now desire to apply the "adding an equation" transformation:

  1. $\Plus(x, \Zero) = x$

This can be proven inductively by noting that $\Plus(\Zero, \Zero) = \Zero$ and $\Plus(\PlusOne(x), \Zero = \PlusOne(\Plus(x, \Zero)) = \PlusOne(x)$.

We apply the "adding an equation" transformation again:

  1. $\Plus(x, \Plus(y, z)) = \Plus(\Plus(x, y), z)$

Once again, we can do a proof by induction, noting that $\Plus(\Zero, \Plus(y, z)) = \Plus(y, z) = \Plus(\Plus(\Zero, y), z)$ and that

$$\Plus(\PlusOne(x), \Plus(y, z)) = \PlusOne(\Plus(x, \Plus(y, z))) = \PlusOne(\Plus(\Plus(x, y), z)) = \Plus(\PlusOne(\Plus(x, y)), z) = \Plus(\Plus(\PlusOne(x), y), z).$$

Next, we apply the "adding a generator" transformation:

  1. $\One : \Nat$
  2. $\One = \PlusOne(\Zero)$

Finally, we apply the "adding an equation" transformation again:

  1. $\PlusOne(x) = \Plus(\One, x)$

We have created a general presentation with 10 axioms which is a conservative extension of $\Nind$. This general presentation is called $\Nat_\mathrm{ind + mon}$.

Next, it only remains to show that $\Nat_\mathrm{ind + mon}$ is a conservative extension of $\Nmon$ as well. In order to do this, we will start by listing the axioms of $\Nat_\mathrm{ind + mon}$ again, but in a different order:

  1. $\Zero : \Nat$
  2. $\Plus : \Nat \times \Nat \to \Nat$
  3. $\One : \Nat$
  4. $\Plus(\Zero, y) = y$
  5. $\Plus(x, \Zero) = x$
  6. $\Plus(x, \Plus(y, z)) = \Plus(\Plus(x, y), z)$
  7. $\PlusOne : \Nat \to \Nat$
  8. $\PlusOne(x) = \Plus(\One, x)$
  9. $\Plus(\PlusOne(x), y) = \PlusOne(\Plus(x, y))$
  10. $\One = \PlusOne(\Zero)$

Equation 10 can be proven from the other equations: $\One = \Plus(\One, \Zero) = \PlusOne(\Zero)$. So we may remove it.

Next, equation 9 can also be proven from the other equations: $\Plus(\PlusOne(x), y) = \Plus(\Plus(\One, x), y) = \Plus(\One, \Plus(x, y)) = \PlusOne(\Plus(x, y))$. So we may remove it as well.

At this point, only axioms 1 through 8 remain. We can use the "removing a function" rule to remove axioms 7 and 8, leaving only axioms 1 through 6. These axioms are $\Nmon$.

This completes the proof that both $\Nind$ and $\Nmon$ are both conservatively extended by a single presentation $\Nat_\mathrm{ind + mon}$.

To restate, we have shown that the natural numbers, defined as the inductive data type generated by one constant and one unary operation, are the natural numbers, defined as the free monoid with one generator.

The question

Surely I'm not the first person to think of all this.

Has anyone studied these "generalized Tietze transformations" before? How powerful are they? Are they sufficiently powerful to prove, say, the fundamental theorem of arithmetic? (We would do that by showing that the positive integers, as usually defined, are isomorphic to the free monoid on countably infinitely many generators, with the monoid operation being multiplication.)

$\endgroup$
3
$\begingroup$

this box is free for anyone to use

$\endgroup$
2
$\begingroup$

Q1) Let $X_1,X_2,\dots,X_n$ be random sample from Poisson($\theta$). Find MVUE of $e^{-2\theta}$

$\ $

Ans) I'm going to assume that $X_1, \dots, X_n$ are independent.

Let $\mathbf{I}$ be the indicator function with $\mathbf{I}(A) = 1$ if the statement $A$ is true, and $0$ otherwise. Since $X_1, X_2$ are independent, it follows that $Y = X_1 + X_2 \sim \text{Poisson}(2\theta)$.

Hence, the PMF of $Y$ is $$f_{Y}(y) = \dfrac{e^{-2\theta}(2\theta)^{y}}{y!}$$ for $y = 0, 1, \dots$.

Observe that $f_{Y}(0) = e^{-2\theta}$.

Recall that the expected value of the indicator function based on an event is the probability of the event. Hence, $$\mathbf{I}(Y = 0) = \mathbf{I}(X_1 + X_2 = 0)$$ is an unbiased estimator of $e^{-2\theta}$. Let $W(X):= \mathbf{I}(X_1 + X_2 = 0)$

$\ $

Now, as the distribution is Poisson, thus $T(X) := \sum_{i=1}^n X_i$ is a complete sufficient statistic.

then by Lehmann-Scheffe,
$$\tau(T)= \mathbb{E}(W(T)\mid T(X)) $$ is the UMVUE of $e^{-2\theta}$.

We cancel out the joint terms, i.e., $$ \tau(X) = \mathbb{E}[W(X)\mid T=s]=\frac{\mathbb{P}(X_1 + X_2 = 0)\mathbb{P}(\sum_{i=3}^n X_i = s)}{\mathbb{P}(\sum_{i=1}^n X_i = s)} \\= \frac{e^{-2\theta} e^{-(n-2)\theta} (n-2)^s \theta^s/s!}{ e^{-n\theta} n^s \theta^s/s! }, $$ with some canceling and rearrangement you have $$ \tau(X) = \left( \left( 1 - \frac{2}{n} \right)^n \right)^{\bar{X}_n} = \left( 1 - \frac{2}{n} \right)^{\sum{X_i}} $$

To be sure you can use the continuous mapping theorem and the WLLN to note that as $(1-2/n)^n \to e^{-2}$ and $\bar{X}_n \xrightarrow{P} \theta $, $\tau(X) \xrightarrow{P} e^{-2\theta}$.

And for the expectation use the fact that $\sum_{i=1}^n X_i \sim \mathcal{P}oiss(n\theta)$, hence $$ \mathbb{E}\tau(X) = e^{-\theta n}\sum_{s=0}^{\infty}\left( \theta n( 1- 2/n\right))^s/s!=e^{-\theta n + \theta n - 2\theta} = e^{-2\theta}. $$

$\ $

Thus our required answer is: $$\left( 1 - \frac{2}{n} \right)^{\sum{X_i}}$$

$\ $

$\ $

Q2) $X_1,\dots,X_n$ iid observation from cdf $$F_{\theta}(x) = \begin{cases} 1 - (\frac {\theta_1}{x})^{\theta_2} & \theta_1 < x \\ 0 & \text{otherwise} \end{cases}$$ Find MLE of $\theta_1, \theta_2$

$\ $

Ans) The first step would of course be to find the pdf from given cdf. So I differentiate the cdf to get the expression of pdf = $$f_{\theta}(x) = \frac{d}{dx}F_{\theta}(x) = \begin{cases} \frac{\theta_2}{x}(\frac {\theta_1^{}}{x})^{\theta_2} & \theta_1 < x \\ 0 & \text{otherwise} \end{cases}$$

$\ $

The Pareto distribution $P(a,c)$, with positive parameters $a$ and $c$, has density function $$ p(x;a,c) = \frac{ac^a}{x^{a+1}} $$ for $x \geq c$. Then, if $X_1, \dots, X_n$ is a random sample from the above distribution, we are asked to find the MLEs of $a$ and $c$. The likelihood function is $$\mathcal{L}(a,c;x_1,\dots,x_n) = \prod_{i=1}^n \frac{ac^a}{x_i^{a+1}} = a^n c^{an} \prod_{i=1}^n x_i^{-(a+1)},$$ and so, the log-likelihood is $$ \log\mathcal{L} = n \log a + an \log c - (a+1)\sum_{i=1}^n \log x_i. $$ This is a strictly increasing function in $c$, so we see that the MLE for $c$ is $$ \hat{c} = \min_i x_i = x_{(1)}. $$ Taking partial with respect to $a$ gives us that $$ \frac{\partial \log\mathcal{L}}{\partial a} = \frac{n}{a} + n\log c - \sum_{i=1}^n \log x_i. $$ Note that the second partial is always negative. Hence, setting the above expression to zero and solving for $a$ gives us the MLE for $a$: $$ \hat{a} = \frac{n}{\sum \log {x_i} - n \log \hat{c}} = \frac{n}{\sum_{i=1}^n \log\left(x_i/x_{(1)}\right)}. $$

So in our case $a = \theta_2 \text{ and } c = \theta_1$

$\ $

Thus our required answer is: $$ \hat{\theta_1} = X_{(1)}. $$ $$ \hat{\theta_2} = \frac{n}{\sum_{i=1}^n \log\left(X_i/X_{(1)}\right)}. $$

$\ $

$\ $

Q3) Let $X$ be a single observation from a pdf $f(x)$. Find a Most Powerful test size $\alpha$ for testing $H_0:f(x)=N(0,1) \text{ vs } H_A:f(x)=Cauchy(0,1)$

$\ $

Ans: According to the Neyman-Pearson lemma, any MP level $\alpha$ test will reject $H_0$ for large values of the likelihood ratio, which is $$\Lambda(x) = \frac{\frac{1}{\pi}\frac{1}{1 + x^2}}{\frac{1}{\root \of{2\pi}}e^{-x^2/2}} = c \frac{e^{x^2/2}}{1 + x^2} $$ We want to know for which values of $x$, $\frac{e^{x^2/2}}{1 + x^2}$ is larger than a threshold $k$.

Now taking $f(x) = \frac{e^{x^2/2}}{1 + x^2}$, I plot the graph of $f(x) \text{ vs } x$:

$\ $

enter image description here

$\ $

A plot of the function $\frac{e^{x^2/2}}{1 + x^2}$ shows that depending on the value of $k$, the set of values of $x$ for which $\frac{e^{x^2/2}}{1 + x^2} > k$ is the a union of two disjoint intervals $x < a, x > b$, which happens if the threshold $k > 1$

The rejection regions of the MP test then takes the form: $X< A \bigcup X > B$. In fact the graph is symmetric, and we would get that $A = -B$ which gives the rejection region as $X < -|A| \bigcup X > |A|$ where $A \in \Bbb R$ and depends on $k$.

Note: The intuition for the MP test to reject $H_0$ for X far away from zero when $\alpha$ is large is the following. Using a large $\alpha$ is tantamount to asking for a large power. That is, we are looking for a test which will know that the true $f$ is not normal, but Cauchy, if it really was Cauchy. Now, the standard Cauchy has a heavier tail than the standard normal. So, if X is far away from zero, the test will see signature of the Cauchy, and reject $H_0$.

$\ $

If $\alpha = 0.05$, the MP level $\alpha$ test rejects $H_0$ for $|X| > 1.96$.
The power of this test is $\gamma = P_{C(0,1)}(|X| > 1.96) = 0.3003$

$\ $

To be more precise, rejecting $H_0$ if $|X|> 1.96$ Then $\alpha = P(\mathrm{Rej}\,H_0|H_0\,\mathrm{true})= 0.05 = 5\%.$

        2*pnorm(-1.96)
        [1] 0.04999579

Also, $\beta = P(\mathrm{Not\,Rej}\,H_0|H_0\,\mathrm{false})=0.70.$

        diff(pt(c(-1.96,1.96),1))
        [1] 0.6996571

So the power of the single-observation test is about $30\%.$

$\ $

In the figure below, the rejection region is outside the vertical black lines in both tails.

        hdr = "Densities of Std Norm (solid blue) and Cauchy"
        curve(dnorm(x), -6,6, col="blue", lwd=2, ylab="PDF", main=hdr)
        curve(dt(x,1), add=T, col="maroon", lwd=2, lty="dotted")
        abline(h=0, col="green2"); abline(v=c(-1.96, 1.96))

enter image description here

$\endgroup$
1
$\begingroup$

This answer is available for anyone to use

$\endgroup$

You must log in to answer this question.