Editing Signed-digit representation (section)

==Definition and properties==
===Digit set===
Let <math>\mathcal{D}</math> be a [[finite set]] of [[numerical digits]] with [[cardinality]] <math>b > 1</math> (If <math>b \leq 1</math>, then the positional number system is [[Triviality (mathematics)|trivial]] and only represents the [[trivial ring]]), with each digit denoted as <math>d_i</math> for <math>0 \leq i < b.</math> <math>b</math> is known as the <em>[[radix]]</em> or <em>[[number base]]</em>. <math>\mathcal{D}</math> can be used for a signed-digit representation if it's associated with a unique [[Function (mathematics)|function]] <math>f_\mathcal{D}:\mathcal{D}\rightarrow\mathbb{Z}</math> such that <math>f_\mathcal{D}(d_i) \equiv i \bmod b</math> for all <math>0 \leq i < b.</math> 
This function, <math>f_{\mathcal{D}},</math> is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in <math>\mathcal{D}.</math> One benefit of this formalism is that the definition of "the integers" (however they may be defined) is not conflated with any particular system for writing/representing them; in this way, these two distinct (albeit closely related) concepts are kept separate. 

<math>\mathcal{D}</math> can be [[Partition of a set|partitioned]] into three distinct sets <math>\mathcal{D}_{+}</math>, <math>\mathcal{D}_{0}</math>, and <math>\mathcal{D}_{-}</math>, representing the positive, zero, and negative digits respectively, such that all digits <math>d_{+}\in\mathcal{D}_{+}</math> satisfy <math>f_\mathcal{D}(d_{+}) > 0</math>, all digits <math>d_{0}\in\mathcal{D}_{0}</math> satisfy <math>f_\mathcal{D}(d_{0}) = 0</math> and all digits <math>d_{-}\in\mathcal{D}_{-}</math> satisfy <math>f_\mathcal{D}(d_{-}) < 0</math>. The cardinality of <math>\mathcal{D}_{+}</math> is <math>b_{+}</math>, the cardinality of <math>\mathcal{D}_{0}</math> is <math>b_{0}</math>, and the cardinality of <math>\mathcal{D}_{-}</math> is <math>b_{-}</math>, giving the number of positive and negative digits respectively, such that <math>b = b_{+} + b_{0} + b_{-}</math>. 

====Balanced form representations====
{{See also|Balanced ternary}}
Balanced form representations are representations where for every positive digit <math>d_{+}</math>, there exist a corresponding negative digit <math>d_{-}</math> such that <math>f_\mathcal{D}(d_{+}) = -f_\mathcal{D}(d_{-})</math>. It follows that <math>b_{+} = b_{-}</math>. Only [[odd number|odd]] bases can have balanced form representations, as otherwise <math>d_{b/2}</math> has to be the opposite of itself and hence 0, but <math>0\ne \frac b2</math>. In balanced form, the negative digits <math>d_{-}\in\mathcal{D}_{-}</math> are usually denoted as positive digits with a bar over the digit, as <math>d_{-} = \bar{d}_{+}</math> for <math>d_{+}\in\mathcal{D}_{+}</math>. For example, the digit set of [[balanced ternary]] would be <math>\mathcal{D}_{3} = \lbrace\bar{1},0,1\rbrace</math> with <math>f_{\mathcal{D}_{3}}(\bar{1}) = -1</math>, <math>f_{\mathcal{D}_{3}}(0) = 0</math>, and <math>f_{\mathcal{D}_{3}}(1) = 1</math>. This convention is adopted in [[finite field]]s of odd [[Prime number|prime]] order <math>q</math>:<ref>{{Cite book|title=Projective Geometries Over Finite Fields|first1=J. W. P.|last1=Hirschfeld|author-link=J. W. P. Hirschfeld|publisher=[[Oxford University Press]]|year=1979|page=8|isbn=978-0-19-850295-1}}</ref>
:<math>\mathbb{F}_{q} = \lbrace0, 1, \bar{1} = -1,... d = \frac{q - 1}{2},\ \bar{d} = \frac{1-q}{2}\ |\ q = 0\rbrace.</math>

====Dual signed-digit representation====
Every digit set <math>\mathcal{D}</math> has a [[Duality (order theory)|dual]] digit set <math>\mathcal{D}^\operatorname{op}</math> given by the [[inverse order]] of the digits with an [[isomorphism]] <math>g:\mathcal{D}\rightarrow\mathcal{D}^\operatorname{op}</math> defined by <math>-f_\mathcal{D} = g\circ f_{\mathcal{D}^\operatorname{op}}</math>. As a result, for any signed-digit representations <math>\mathcal{N}</math> of a number system [[Ring (mathematics)|ring]] <math>N</math> constructed from <math>\mathcal{D}</math> with [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{N}\rightarrow N</math>, there exists a dual signed-digit representations of <math>N</math>, <math>\mathcal{N}^\operatorname{op}</math>, constructed from <math>\mathcal{D}^\operatorname{op}</math> with [[Valuation (algebra)|valuation]] <math>v_{\mathcal{D}^\operatorname{op}}:\mathcal{N}^\operatorname{op}\rightarrow N</math>, and an isomorphism <math>h:\mathcal{N}\rightarrow\mathcal{N}^\operatorname{op}</math> defined by <math>-v_\mathcal{D} = h\circ v_{\mathcal{D}^\operatorname{op}}</math>, where <math>-</math> is the additive inverse operator of <math>N</math>. The digit set for balanced form representations is [[self-dual]].

===For integers===
Given the digit set <math>\mathcal{D}</math> and function <math>f:\mathcal{D}\rightarrow\mathbb{Z}</math> as defined above, let us define an [[integer]] [[endofunction]] <math>T:\mathbb{Z}\rightarrow\mathbb{Z}</math> as the following:
:<math>T(n) = 
\begin{cases}
\frac{n - f(d_i)}{b} &\text{if } n \equiv i \bmod b, 0 \leq i < b
\end{cases}</math>
If the only [[periodic point]] of <math>T</math> is the [[fixed point (mathematics)|fixed point]] <math>0</math>, then the set of all signed-digit representations of the [[integers]] <math>\mathbb{Z}</math> using <math>\mathcal{D}</math> is given by the [[Kleene plus]] <math>\mathcal{D}^+</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_n \ldots d_0</math> with at least one digit, with <math>n\in\mathbb{N}</math>. Each signed-digit representation <math>m \in \mathcal{D}^+</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^+\rightarrow\mathbb{Z}</math>
:<math>v_\mathcal{D}(m) = \sum_{i=0}^{n}f_\mathcal{D}(d_{i})b^{i}</math>. 
Examples include [[balanced ternary]] with digits <math>\mathcal{D} = \lbrace \bar{1}, 0, 1\rbrace</math>.  

Otherwise, if there exist a non-zero [[periodic point]] of <math>T</math>, then there exist integers that are represented by an infinite number of non-zero digits in <math>\mathcal{D}</math>. Examples include the standard [[decimal numeral system]] with the digit set <math>\operatorname{dec} = \lbrace 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \rbrace</math>, which requires an [[Radix complement|infinite number of the digit]] <math>9</math> to represent the [[additive inverse]] <math>-1</math>, as <math>T_\operatorname{dec}(-1) = \frac{-1 - 9}{10} = -1</math>, and the positional numeral system with the digit set <math>\mathcal{D} = \lbrace \text{A}, 0, 1\rbrace</math> with <math>f(\text{A}) = -4</math>, which requires an infinite number of the digit <math>\text{A}</math> to represent the number <math>2</math>, as <math>T_\mathcal{D}(2) = \frac{2 - (-4)}{3} = 2</math>.

===For decimal fractions===
{{Main|Decimal representation}}
If the integers can be represented by the [[Kleene plus]] <math>\mathcal{D}^+</math>, then the set of all signed-digit representations of the [[decimal fraction]]s, or [[Dyadic rational|<math>b</math>-adic rationals]] <math>\mathbb{Z}[1\backslash b]</math>, is given by <math>\mathcal{Q} = \mathcal{D}^+\times\mathcal{P}\times\mathcal{D}^*</math>, the [[Cartesian product]] of the [[Kleene plus]] <math>\mathcal{D}^+</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_n \ldots d_0</math> with at least one digit, the [[Singleton (mathematics)|singleton]] <math>\mathcal{P}</math> consisting of the [[radix point]] (<math>.</math> or <math>,</math>), and the [[Kleene star]] <math>\mathcal{D}^*</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_{-1} \ldots d_{-m}</math>, with <math>m,n\in\mathbb{N}</math>. Each signed-digit representation <math>q \in \mathcal{Q}</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{Q}\rightarrow\mathbb{Z}[1\backslash b]</math>
:<math>v_\mathcal{D}(q) = \sum_{i=-m}^{n}f_\mathcal{D}(d_{i})b^{i}</math>

===For real numbers===
{{Main|Construction of the reals#Construction from Cauchy sequences}}
If the integers can be represented by the [[Kleene plus]] <math>\mathcal{D}^+</math>, then the set of all signed-digit representations of the [[real numbers]] <math>\mathbb{R}</math> is given by <math>\mathcal{R} = \mathcal{D}^+ \times \mathcal{P} \times \mathcal{D}^\mathbb{N}</math>, the [[Cartesian product]] of the [[Kleene plus]] <math>\mathcal{D}^+</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_n \ldots d_0</math> with at least one digit, the [[Singleton (mathematics)|singleton]] <math>\mathcal{P}</math> consisting of the [[radix point]] (<math>.</math> or <math>,</math>), and the [[Cantor space]] <math>\mathcal{D}^\mathbb{N}</math>, the set of all [[infinity|infinite]] [[concatenation|concatenated]] strings of digits <math>d_{-1} d_{-2} \ldots</math>, with <math>n\in\mathbb{N}</math>. Each signed-digit representation <math>r \in \mathcal{R}</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{R}\rightarrow\mathbb{R}</math>
:<math>v_\mathcal{D}(r) = \sum_{i=-\infty}^{n}f_\mathcal{D}(d_{i})b^{i}</math>. 
The [[infinite series]] always [[Convergent series|converges]] to a finite real number.

===For other number systems===
All base-<math>b</math> numerals can be represented as a subset of <math>\mathcal{D}^\mathbb{Z}</math>, the set of all [[doubly infinite sequence]]s of digits in <math>\mathcal{D}</math>, where <math>\mathbb{Z}</math> is the set of [[integers]], and the [[Ring (mathematics)|ring]] of base-<math>b</math> numerals is represented by the [[formal power series ring]] <math>\mathbb{Z}[[b,b^{-1}]]</math>, the doubly infinite series
:<math>\sum_{i = -\infty}^{\infty}a_i b^i</math>
where <math>a_i\in\mathbb{Z}</math> for <math>i\in\mathbb{Z}</math>. 

====Integers modulo powers of {{math|''b''}}====
The set of all signed-digit representations of the [[Integers modulo n|integers modulo <math>b^n</math>]], <math>\mathbb{Z}\backslash b^n\mathbb{Z}</math> is given by the set <math>\mathcal{D}^n</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_{n - 1} \ldots d_0</math> of length <math>n</math>, with <math>n\in\mathbb{N}</math>. Each signed-digit representation <math>m \in \mathcal{D}^n</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^n\rightarrow\mathbb{Z}/b^n\mathbb{Z}</math>
:<math>v_\mathcal{D}(m) \equiv \sum_{i=0}^{n - 1}f_\mathcal{D}(d_{i})b^{i} \bmod b^n</math>

====Prüfer groups====
A [[Prüfer group]] is the [[quotient group]] <math>\mathbb{Z}(b^\infty) = \mathbb{Z}[1\backslash b]/\mathbb{Z}</math> of the integers and the <math>b</math>-adic rationals. The set of all signed-digit representations of the [[Prüfer group]] is given by the [[Kleene star]] <math>\mathcal{D}^*</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_{1} \ldots d_{n}</math>, with <math>n\in\mathbb{N}</math>. Each signed-digit representation <math>p \in \mathcal{D}^*</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^*\rightarrow\mathbb{Z}(b^\infty)</math>
:<math>v_\mathcal{D}(m) \equiv \sum_{i=1}^{n}f_\mathcal{D}(d_{i})b^{-i} \bmod 1</math>

====Circle group====
The [[circle group]] is the quotient group <math>\mathbb{T} = \mathbb{R}/\mathbb{Z}</math> of the integers and the real numbers. The set of all signed-digit representations of the [[circle group]] is given by the [[Cantor space]] <math>\mathcal{D}^\mathbb{N}</math>, the set of all right-infinite concatenated strings of digits <math>d_{1} d_{2} \ldots</math>. Each signed-digit representation <math>m \in \mathcal{D}^n</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^\mathbb{N}\rightarrow\mathbb{T}</math>
:<math>v_\mathcal{D}(m) \equiv \sum_{i=1}^{\infty}f_\mathcal{D}(d_{i})b^{-i} \bmod 1</math>
The [[infinite series]] always [[Convergent series|converges]].

===={{math|''b''}}-adic integers====
The set of all signed-digit representations of the [[p-adic integers|<math>b</math>-adic integers]], <math>\mathbb{Z}_b</math> is given by the [[Cantor space]] <math>\mathcal{D}^\mathbb{N}</math>, the set of all left-infinite concatenated strings of digits <math>\ldots d_{1} d_{0}</math>. Each signed-digit representation <math>m \in \mathcal{D}^n</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^\mathbb{N}\rightarrow\mathbb{Z}_{b}</math>
:<math>v_\mathcal{D}(m) = \sum_{i=0}^{\infty}f_\mathcal{D}(d_{i})b^{i}</math>

===={{math|''b''}}-adic solenoids====
The set of all signed-digit representations of the [[Solenoid (mathematics)#p-adic solenoids|<math>b</math>-adic solenoids]], <math>\mathbb{T}_b</math> is given by the [[Cantor space]] <math>\mathcal{D}^\mathbb{Z}</math>, the set of all [[doubly infinite]] concatenated strings of digits <math>\ldots d_{1} d_{0} d_{-1} \ldots</math>. Each signed-digit representation <math>m \in \mathcal{D}^n</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^\mathbb{Z}\rightarrow\mathbb{T}_{b}</math>
:<math>v_\mathcal{D}(m) = \sum_{i=-\infty}^{\infty}f_\mathcal{D}(d_{i})b^{i}</math>