# Carry propagation-free number systems and a kind of approximate groups (I)

Avizienis introduced a signed-digit number representation which allows fast, carry propagation-free addition (A. Avizienis, Signed-digit number representation for fast parallel arithmetic, IRE Trans. Comput., vol. EC-10, pp. 389-400, 1961, see also B. Parhami, Carry-Free Addition of Recoded Binary Signed-Digit Numbers, IEEE Trans. Computers, Vol. 37, No. 11, pp. 1470-1476, November 1988.)

Here, just for fun, I shall use a kind of approximate groups to define a carry-free addition-like operation.

1. The hypothesis is: you have three finite sets $A$, $B$, $K$, all sitting in a group $G$. I shall suppose that the group $G$ is commutative, although it seems that’s not really needed further if one takes a bit of care. In order to reflect this, I shall use  $+$ for the group operation on $G$, but I shall write $M N$  for the set of all elements of the form  $x + y$ with $x \in M$ and $y \in N$.

We know the following about the three (non-empty, of course) sets $A, B, K$:

1. $B \subset A$,
2. $0 \in B$, $0 \in K$, $A = -A$, $B = -B$, $K = -K$,
3. $\mid B \mid = \mid K \mid$   (where $\mid M \mid$ is the cardinal of the finite set $M$),
4. $A A B \subset A K$  (that’s what qualifies $A$ as a kind of an approximate group).

Let now choose a bijective function $\phi: K \rightarrow B$ and two functions $\psi: AAB \rightarrow A$ and $\chi: AAB \rightarrow K$ such that

(1)   for any $x, y \in A$ and any $b \in B$ we have $x+y+b = \psi(x+y+b) + \chi(x+y+b)$.

______________

2. Let $X$ be the family of functions defined on $\mathbb{Z}$ with values in $A$, with compact support, i.e. if $x: \mathbb{Z} \rightarrow A$ belongs to $X$, then only a finite number of $k \in \mathbb{Z}$ have the property that $x_{k} = x(k) \not = 0$.  The element $0 \in X$ is defined by $x_{k} = 0$ for any $k \in \mathbb{Z}$.  If $x \in X$ with $x \not = 0$ then $ind(x) \in \mathbb{Z}$ is the smallest index $k \in \mathbb{Z}$ with $x_{k} \not = 0$.

______________

3.  The structure introduced at 1. allows the definition of an operation $*$ on $X$. The definition of the operation is inspired from a carry-free addition algorithm.

Definition 1. If both $x, y \in X$ are equal to $0$ then $x*y = 0$. Otherwise, let $j \in \mathbb{Z}$ be the smallest index $k$ such that one of $x_{k}$ or $y_{k}$ is different than $0$.  The element $z = x*y$ is defined by the following algorithm:

1. $z_{k} = 0$ for any $k < j$,
2. let $t_{j} = 0$$k = j$. Repeat:

$p_{k} = x_{k} + y_{k} + t_{k}$

$z_{k} = \psi(p_{k})$

$t_{k+1} = \phi(\chi(p_{k}))$

$k \rightarrow k+1$

______________

4.  We may choose the functions $\phi, \psi, \chi$ such that the operation $*$ is starting to become interesting. Before doing this, let’s remark that:

• the operation $*$ is commutative as a consequence of the fact that $+$ is commutative,
• the operation $*$ is conical, i.e. it admits the shift $\delta: X \rightarrow X$, $\delta(x)(k+1) = x_{k}$ as automorphism ( a property encountered before for dilation structures on ultrametric spaces, see  arXiv:0709.2224  )

Proposition 1.  If the functions $\phi, \chi, \psi$ satisfy the following:

1. $\phi(0) = \chi(0) = \psi(0) = 0$
2. $\chi(x) = 0$ for any $x \in A$
3. $\psi(-x) = - \psi(x)$$\phi(-x) = -\phi(x)$ for any $x \in A A B$, $\chi(-x) = -\chi(x)$ for any $x \in K$,

then $(X, *)$ is a conical quasigroup.