P-adische Zahlen/Definition der beta Funktion/Textabschnitt

Eine natürliche Zahl ${}n$ lässt sich bekanntlich im Zehnersystem als

${}n=a_{0}1+a_{1}10+a_{2}10^{2}+\cdots +a_{k}10^{k}\,$

schreiben, wobei die ${}a_{i}$ zwischen ${}0$ und ${}9$ liegen. Umgekehrt definiert eine endliche Ziffernfolge ${}(a_{0},a_{1},\ldots ,a_{k})$ (bzw. in alltäglicher Schreibweise $a_{k}a_{k-1}\ldots a_{1}a_{0}$) eine natürliche Zahl. Anstatt der Basis ${}10$ kann man jede natürliche Zahl  ${}p\geq 2$  als Basis nehmen (für viele Zwecke ist auch die Basis ${}1$ erlaubt, eine Zahl ${}n$ wird dann einfach durch das ${}n$-fache Hintereinanderschreiben der ${}1$ repräsentiert). Man spricht dann von der ${}p$-adischen Entwicklung (oder Darstellung) der Zahl. Die ${}p$-adische Entwicklung einer natürlichen Zahl ist eindeutig.

Sei  ${}p\geq 2$  fixiert. Wie berechnet man die Ziffernfolge einer gegebenen Zahl ${}n$? Zuerst betrachten wir die Ziffer (die Einerziffer)  ${}a_{0}(n)=a(n,0)$.  Es gilt die rekursive Beziehung

${}a(n,0)={\begin{cases}n,{\text{falls }}n<p\,,\\a(n-p,0){\text{ sonst}}\,.\end{cases}}\,$

Dies beruht einfach darauf, dass bei  ${}n\geq p$  das Abziehen von ${}p$ die Ziffer zu ${}p^{0}$ nicht ändert. Man beachte, dass sowohl die Abfrage, die die Fallunterscheidung in dieser Definition konstituiert, als auch die Subtraktion im Fall ${}2$ mit einer Registermaschine durchführbar sind, und dass dadurch eine ${}R$-berechenbare Funktion vorliegt.

Auch die Definition der anderen Ziffern geschieht rekursiv. Wenn man von ${}n$ die (schon berechnete) Ziffer zu ${}p^{0}$ abzieht, so erhält man eine durch ${}p$ teilbare Zahl. Zwischen der Ziffernentwicklung von ${}n$ und von  ${}m={\frac {n-a(n,0)}{p}}$  besteht ein direkter Zusammenhang, die Ziffer ${}a_{i+1}$ von ${}n$ ist einfach die Ziffer ${}a_{i}$ von ${}m$. Daher ist für  ${}i\geq 0$ 

${}a(n,i+1)={\begin{cases}0,{\text{falls }}n<p^{i+1}\,,\\a{\left({\frac {n-a(n,0)}{p}},i\right)}{\text{ sonst}}\,.\end{cases}}\,$

Damit ist die Berechnung der ${}(i+1)$-ten Ziffer auf die Berechnung der ${}i$-ten Ziffer einer kleineren Zahl rekursiv zurückgeführt. Die Bedingung in der Abfrage und die Subtraktion und die Division in der Definition sind durch eine Registermaschine durchführbar. Diese Funktionsvorschrift berechnet nicht nur die „benötigten“ Ziffern, sondern auch alle höheren, wobei natürlich für alle unbenötigten ${}0$ herauskommt.

Wir führen nun die ${}\beta$-Funktion ein. Der Hauptzweck dieser Funktion soll sein, endliche Folgen von natürlichen Zahlen unterschiedlicher Länge durch drei Zahlen zu kodieren. Die Grundidee ist, dies über die ${}p$-adische Entwicklung zu tun, wobei die drei Eingabezahlen einen Zahlwert, eine Basis und eine Ziffernstelle repräsentieren, und die Ausgabe die Ziffernfolge ist. Zugleich soll diese Funktion arithmetisch repräsentierbar sein, sodass die folgende Funktion etwas komplizierter aussieht. Wir folgen weitgehend dem Zugang von Ebbinghaus, Flum, Thomas.

Definition

Unter der ${}\beta$-Funktion versteht man die Abbildung

$\mathbb {N} ^{3}\longrightarrow \mathbb {N} ,\,(p,n,i)\longmapsto \beta (p,n,i),$

die folgendermaßen festgelegt ist. ${}\beta (p,n,i)$ ist die kleinste Zahl  ${}a\in \mathbb {N}$,  die die Bedingung erfüllt, dass es natürliche Zahlen ${}b_{0},b_{1},b_{2}$ gibt, die die folgenden Eigenschaften erfüllen:

1.  ${}n=b_{0}+b_{1}{\left((i+1)+ap+b_{2}p^{2}\right)}$. 
2.  ${}a<p$. 
3.  ${}b_{0}<b_{1}$. 
4. ${}b_{1}$ ist eine Quadratzahl.
5. Alle Teiler  ${}d\neq 1$  von ${}b_{1}$ sind ein Vielfaches von ${}p$.

Wenn kein solches ${}a$ existiert, so ist  ${}\beta (p,n,i)=0$. 

Zunächst ist klar, dass diese Funktion arithmetisch repräsentierbar ist. Wenn ${}p$ eine Primzahl ist, so bedeutet Teil (5), dass ${}b_{1}$ eine Primzahlpotenz ist, und Teil (4), dass der Exponent geradzahlig ist. Das folgende Lemma sichert die gewünschte Eigenschaft der ${}\beta$-Funktion, nämlich die Eigenschaft, endliche Folgen zu repräsentieren.

Lemma

Zu jeder endlichen Folge ${}(a_{0},\ldots ,a_{s})$ aus ${}\mathbb {N}$

gibt es natürliche Zahlen ${}p,n$ derart, dass  ${}\beta (p,n,i)=a_{i}$  für  ${}i\leq s$  ist.

Beweis

Es sei die endliche Folge ${}(a_{0},a_{1},\ldots ,a_{s})$ vorgegeben. Wir wählen eine Primzahl ${}p$, die größer als alle ${}a_{i}$ und größer als ${}s+1$ ist. Es sei

${}{\begin{aligned}n&:=1\cdot p^{0}+a_{0}p^{1}+2p^{2}+a_{1}p^{3}+\cdots +(s+1)p^{2s}+a_{s}p^{2s+1}\\&=\sum _{i=0}^{s}a_{i}p^{2i+1}+\sum _{i=0}^{s}(i+1)p^{2i}\\&=\sum _{i=0}^{s}(i+1+a_{i}p)p^{2i}.\end{aligned}}$

Die vorgegebene Folge ist also die Folge der Ziffern der ungeraden Stellen in der ${}p$-adischen Ziffernentwicklung von ${}n$. Wir behaupten  ${}\beta (p,n,k)=a_{k}$  für  ${}k\leq s$.  Zunächst erfüllt ${}a_{k}$ die in der Definition der ${}\beta$-Funktion formulierten Eigenschaften, und zwar mit

$b_{0}=1p^{0}+a_{0}p^{1}+2p^{2}+a_{1}p^{3}+\cdots +kp^{2k-2}+a_{k-1}p^{2k-1}\,,$

${}b_{1}=p^{2k}\,,$

$b_{2}=(k+2)+a_{k+1}p+(k+3)p^{2}+\cdots +(s+1)p^{2(s-k)-2}+a_{s}p^{2(s-k)-1}\,.$

Die erste Eigenschaft ergibt sich aus

${}{\begin{aligned}n&=\sum _{i=0}^{s}a_{i}p^{2i+1}+\sum _{i=0}^{s}(i+1)p^{2i}\\&=\sum _{i=0}^{k-1}a_{i}p^{2i+1}+\sum _{i=0}^{k-1}(i+1)p^{2i}+\sum _{i=k}^{s}a_{i}p^{2i+1}+\sum _{i=k}^{s}(i+1)p^{2i}\\&=b_{0}+p^{2k}{\left(\sum _{i=0}^{s-k}a_{k+i}p^{2i+1}+\sum _{i=0}^{s-k}(k+i+1)p^{2i}\right)}\\&=b_{0}+p^{2k}{\left(k+1+a_{k}p+\sum _{i=1}^{s-k}a_{k+i}p^{2i+1}+\sum _{i=1}^{s-k}(k+i+1)p^{2i}\right)}\\&=b_{0}+b_{1}{\left(k+1+a_{k}p+b_{2}p^{2}\right)},\end{aligned}}$

die anderen sind klar. Wenn umgekehrt ein ${}a$ die Bedingungen erfüllt (mit $c_{0},c_{1},c_{2}$), wobei  ${}c_{1}=p^{2\ell }$  ist, so ist

${}{\begin{aligned}n&=b_{0}+(k+1)p^{2k}+a_{k}p^{2k+1}+b_{2}p^{2k+2}\\&=c_{0}+(k+1)p^{2\ell }+ap^{2\ell +1}+c_{2}p^{2\ell +2}.\end{aligned}}$

Da die ${}p$-adische Entwicklung von ${}n$ eindeutig ist, folgen daraus und aus den weiteren Bedingungen die Gleichheiten  ${}\ell =k$  und  ${}a=a_{k}$. 

$\Box$