| Sbornik: Mathematics |
|
|
|
|
|
Unique expansions in number systems via refinement equations S. V. Konyagina, V. Yu. Protasovbc, A. L. Talambutsaad a Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia b Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica, University of L'Aquila, L'Aquila, Italy c Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia d Laboratory of Theoretical Computer Science, National Research University Higher School of Economics, Moscow, Russia
Bibliographic databases:
   § 1. Number systems and semigroup freenessGiven an integer $n\geqslant 2$, we consider a set of nonnegative integers $A=\{a_1, \dots, a_m\}$, which are called digits of the (nonstandard) $n$-ary number system $A$. The main results of this paper are obtained under the assumption that $m=n$, but this equality is not necessary in general. For an integer $k\geqslant 0$, by an $A$-expansion we mean any tuple of digits $(\alpha_0,\dots,\alpha_J)$ such that
$$
\begin{equation}
k= \sum_{j=0}^{J} \alpha_{j} n^j, \quad\text{where } \alpha_{J} \ne 0.
\end{equation}
\tag{1}
$$
In particular, for $k=0$ its $A$-expansion is an empty tuple. We say that the $n$-ary number system $A$ has the uniqueness property if each integer $k\geqslant 0$ has at most one $A$-expansion. The uniqueness property was studied in the literature mainly because of two applications. The first is the theory of self-similar tiles, where uniqueness gives an existence criterion for a tile. See [14], [20] and [21] and the references there for the general multivariate case. The second application is related to coding theory, but as we will show, it also turns out to be connected with the freeness of particular semigroups and the densities of integer orbit sets arising from the action of integer affine functions. The active analysis of number systems with positive digits was initiated in the early 1980s by Maurer, Salomaa and Wood in [22], where they introduced L-codes and discovered that if the code alphabet is unary, then the L-code corresponds to a nonstandard number system.1 They proved that such a unary code can uniquely be decoded if and only if the corresponding number system has the uniqueness property. It was also proved that this property fails necessarily if $m>n$, while if all the $\alpha_i$ are distinct modulo $n$, then the property holds. The authors also suggested a general decision problem of checking whether a number system has the uniqueness property. As shown by Honkala [11], this problem is decidable. Some other results concerning number systems were obtained in the next decade; for their description, we refer the reader to [12]. Even a little earlier than Maurer, Salomaa and Wood, in [15] Klarner came to the study of another decision problem, which is closely related to the uniqueness of number systems. The motivation was coming from the question of Erdős on when the density of an orbit set $\langle F:S \rangle$ is positive (see [9], p. 23, and [19]). Here the set $\langle F:S \rangle$ contains all the images of a finite set of nonnegative integers $S$ under the action of any number of integer-valued affine functions taken from the set
$$
\begin{equation}
F=\{f_i=n_i x+a_i,\, i=1,\dots,m\} \quad\text{for } n_i\geqslant 2 \text{ and } a_i\in \mathbb N\cup \{0\}.
\end{equation}
\tag{2}
$$
Klarner studied the particular case when all slopes $n_i$ are equal to some integer $n\geqslant 2$ and noted that for $m=n$ the (upper) density
$$
\begin{equation*}
\delta(\langle F : S \rangle)=\lim\sup_{T\to \infty} \frac{\langle F : S \rangle\cap\{0,\dots, T\}}{T+1}
\end{equation*}
\notag
$$
is equal to $0$ if and only if the set $F$ satisfies a nontrivial semigroup relation, that is,
$$
\begin{equation}
f_{u_1}\circ \dots\circ f_{u_p}=f_{v_1}\circ \dots\circ f_{v_q}
\end{equation}
\tag{3}
$$
for some $u_1,\dots, u_p,v_1,\dots, v_q\in \{1,\dots,m\}$ such that $(u_1,\dots, u_p)\ne (v_1,\dots, v_s)$. The decision problem in which, for an input set $F$, one needs to answer whether or not a relation of the form (3) exists, is known as the freeness problem for a semigroup.2 Klarner noted that if all slopes in (2) are equal to $n$, the inequality $m>n$ implies that there exists a relation of type (3); for unequal slopes this was generalized in [16] and [18]. The important subcase $m=n$ was considered separately, but for its solution the reader was referred to a preprint which has never appeared. However, it was noted that the freeness can be obtained if the set
$$
\begin{equation*}
\biggl\{0, \frac{a_2-a_1}{d}, \dots, \frac{a_m-a_1}{d}\biggr\}
\end{equation*}
\notag
$$
is a complete residue system modulo $n$, where $d = \gcd(a_2 - a_1, \dots, a_m - a_1)$. As we will see in § 4, in the case of a prime number $n=m$ freeness and this condition on residues are actually equivalent. The uniqueness problem for a number system and the freeness problem for a set of integer-valued affine functions of the same slope can be related by means of the following observation. Proposition 1. Let $F=\{f_i(x)=nx+a_i \mid i=1,\dots,m\}$ be the set of affine functions such that $n,a_2,\dots,a_m \in \mathbb{N}$, $n\geqslant 2$ and $a_1=0$. Then the $n$-ary system $A=\{a_1,\dots,a_m\}$ has the uniqueness property if and only if the set $F$ is a free semigroup basis. Proof. Suppose first that there is a semigroup relation (3). A straightforward computation shows that
$$
\begin{equation*}
f_{u_1}\circ \dots\circ f_{u_p}=n^p x + c=f_{v_1}\circ \dots\circ f_{v_q}=n^q x + d,
\end{equation*}
\notag
$$
where
$$
\begin{equation}
\begin{aligned} \, c&=a_{u_1}+a_{u_2}n+a_{u_3}n^2+\dots+a_{u_p}n^{p-1}, \\ d&=a_{v_1}+a_{v_2}n+a_{v_3}n^2+\dots+a_{v_q}n^{q-1}. \end{aligned}
\end{equation}
\tag{4}
$$
Since $c=d$, from (4), we obtain two distinct $A$-expansions of the same number.
Assume that there exist two tuples $(a_{u_1},\dots, a_{u_p})$ and $(a_{v_1},\dots, a_{v_q})$ giving $A$-expansions of the same number $c=d$ in (4). Without loss of generality we suppose $p\geqslant q$ and consider $S=f^{(p-q)}_{1}=n^{p-q}x$. Then we immediately obtain that
$$
\begin{equation*}
L=f_{u_1}\circ \dots\circ f_{u_p}=n^px+c \quad\text{and}\quad R=f_{v_1}\circ \dots\circ f_{v_q}\circ S=n^px+d,
\end{equation*}
\notag
$$
and $L=R$ is a nontrivial semigroup relation since $a_{u_p}\ne 0$ by condition (1).
The proposition is proved. The restriction $a_1=0$ in the statement of Proposition 1 is actually slightly artificial, and it can be bypassed by using the following tool. Proposition 2. Let $F=\{f_i(x)=nx+a_i \mid i=1,\dots,m\}$ be a set of affine functions such that $n,a_1,a_2,\dots,a_m \in \mathbb{Z}$ and $n\geqslant 2$. Then for any $s\in \mathbb{Z}$ the set $F$ is a free semigroup basis if and only if the set $F=\{\widetilde{f}_i(x)=nx+(a_i-s) \mid i=1,\dots,m\}$ is a free semigroup basis. Proof. For the function $g(x)=x-c$ we have $g^{-1}\circ f_i \circ g=nx+(a_i-cn+c)$. We take $c=s/(n-1)$; then $g^{-1}\circ f_i \circ g=\widetilde{f}_i$. Consequently, the existence of a group relation
$$
\begin{equation*}
f_{u_1}\circ \dots\circ f_{u_p}=f_{v_1}\circ \dots\circ f_{v_q}
\end{equation*}
\notag
$$
is equivalent to the existence of the conjugate relation which can also be written as
The proposition is proved. Propositions 1 and 2, in combination with Theorem 2 in § 3, provide an algorithm to check freeness for the set $F$ in the case $m=n$, which was missing from Klarner’s considerations. If $n$ is a prime number, the freeness check for the set $F$ (and for the density $\delta(\langle F:S \rangle$) to be positive) can be done much easier by use of Theorem 4 in § 4. § 2. Subdivision scheme and transition operatorSubdivision schemes are iterative algorithms for the linear approximation of functions from their values on a mesh. They originated in the late 1980s with Dyn, Levin, Gregory, De Boor, Dubuc and other authors: see [2], [7] and [8] for many references. They are widely used for the interpolation and approximation of smooth functions and in modelling curves and surfaces. Their applications to combinatorics and number theory are also known: see [10], [20], [26] and [27]. In [28] refinement schemes were applied to the problem of the representation of numbers in a binary number system with an arbitrary set of digits. Some special cases of subdivisions appeared previously in works by de Rham [4], [5] (the cutting angle scheme), Chaikin [3], Micchelli and Prautzsch [23] and other authors. We consider only stationary univariate schemes defined by an integer contraction factor $n\geqslant 2$ and a sequence of real numbers with finite support $\{c_i\}_{i\in \mathbb{Z}}$. After a suitable shift of numbering we can assume that $c_i = 0$ for all $i\notin \{0, \dots, N\}$ and $c_0c_N \ne 0$. We denote by $l_{\infty}$ the space of bounded sequences $\{x_k\}_{k\in \mathbb{Z}}$ and by $\delta \in l_{\infty}$ the sequence $(\delta )_k = \delta_{0k}$ (Kronecker symbol). The subdivision operator $S\colon l_{\infty} \to l_{\infty}$ acts on $l_{\infty}$ as follows: where $g = (g_i)_{i \in \mathbb Z} \in l_{\infty}$. Furthermore, we consider the transition operator $T$ on the space of tempered distributions with compact support $\mathcal{S}_0'$:
$$
\begin{equation}
[Tf](t)= \sum_{k\in \mathbb Z} c_k f(n t-k), \qquad f \in \mathcal{S}_0'.
\end{equation}
\tag{6}
$$
There is a simple relation between the subdivision scheme and the transition operator. For every $j\in \mathbb{N}$ we have:
$$
\begin{equation}
[T^jf](t)= \sum_{k\in \mathbb Z} (S^j\delta )_k f(n^j t-k), \qquad f\in \mathcal{S}'.
\end{equation}
\tag{7}
$$
The proof can be found, for example, in [2] or verified by direct computation. The following theorem is well known [24]. Theorem A. Assume that $\sum_k c_k = n$. Then for every $f \in \mathcal{S}_0'$ such that $(f,\boldsymbol{1}) = 1$ the sequence $T^jf$ converges in $\mathcal{S}'$ to the unique solution $\varphi \in \mathcal{S}_0'$ of the functional equation such that $(\varphi, \boldsymbol{1}) = 1$ This solution has support on the interval $[0,N]$ and satisfies the equation $T\varphi = \varphi$. Of course, we could have dropped the normalization condition $(f,\boldsymbol{1}) = 1$ and obtain by homogeneity the following: for every $f\in \mathcal{S}_0'$ the sequence $T^jf$ converges to $(f, \boldsymbol{1})\, \varphi$. The function $\varphi$ is called a refinable function in the literature, and equation (8) is called a refinement equation. With every refinement equation we associate the trigonometric polynomial
$$
\begin{equation*}
{\boldsymbol c}(\xi) = \frac1n \sum_{k \in \mathbb Z} c_k e^{-2\pi i k \xi},
\end{equation*}
\notag
$$
called its mask. This is the characteristic function of the sequence $\{c_k\}_{k\in \mathbb{Z}}$. Computing the Fourier transforms of both parts of the refinement equation gives us the following equation in the frequency domain:
$$
\begin{equation}
\widehat \varphi(\xi) = {\boldsymbol c}\biggl(\frac{\xi}{n}\biggr) \widehat \varphi\biggl(\frac{\xi}{n}\biggr).
\end{equation}
\tag{9}
$$
Iterating $j$ times we obtain
$$
\begin{equation}
\widehat \varphi(\xi) = {\boldsymbol c} (n^{-1}\xi) \cdots {\boldsymbol c} (n^{-j}\xi) \widehat \varphi(n^{-j}\xi).
\end{equation}
\tag{10}
$$
Now we focus on the case of nonnegative coefficients $c_k$. Some of the results below are known [25]; we give their proofs for the convenience of the reader. The following simple observation was made independently in a number of papers: see [6], [7], [25] and [29]. Lemma 1. If all the $c_k$ are nonnegative, then $\varphi$ is a Borel measure of pure type, namely it is either absolutely continuous (that is, $\varphi \in L_1$) or purely singular. Proof. Choosing $f=\chi_{[0,1]}$, we see that all functions $T^jf$ are nonnegative, hence so is their limit. Thus, $\varphi$ is a nonnegative distribution, that is, a Borel measure.
According to Lebesgue’s theorem, there exists a unique representation of $\varphi$ as a sum of absolutely continuous and singular measures: $\varphi = \varphi_{\mathrm{cont}} + \varphi_{\mathrm{sing}}$. Uniqueness implies that both $\varphi_{\mathrm{cont}}$ and $\varphi_{\mathrm{sing}}$ satisfy the refinement equation (8). However, this equation possesses a unique solution up to normalization. Therefore, one of these functions is zero. The lemma is proved. Lemma 1 rises the question of separating the cases of absolute continuity and singularity of the measure $\varphi$. The following criterion is proved by using (10) and Poisson’s summation formula. Proposition 3. Suppose all the $c_k$ are nonnegative; then $\varphi \in L_1$ if and only if $\widehat \varphi (m) = 0$ for all integers ${m\ne 0}$. Moreover, in this case $\varphi(t) \leqslant 1$ almost everywhere. Proof. Necessity. Assume that there exists $m\in \mathbb{Z}\setminus \{0\}$ such that $\widehat \varphi (m) \ne 0$. Taking an arbitrary integer $j\in \mathbb{N}$ and substituting $\xi = n^jm$ into (10) we obtain The latter equality holds because all numbers $n^{j-s}m$, $s=1, \dots, j$, are integers, and therefore $ {\boldsymbol c} (n^{j-s}m ) = {\boldsymbol c}(0) = 1$. Thus, $\widehat \varphi(n^jm) = \widehat \varphi (m)$ for all $j\in \mathbb{N}$. On the other hand, if $\varphi \in L_1(\mathbb{R})$, then $\widehat{\varphi}(\xi) \to 0$ as $\xi\to \infty$. This is not true for $\xi = n^jm$ where $j\to \infty$, hence $\varphi \notin L_1$.
Sufficiency. If $\widehat\varphi(m) = \delta_{m0}$, then applying Poisson’s summation formula to the function $\varphi (t-\cdot\,)$ we obtain
$$
\begin{equation}
\sum_{k\in \mathbb Z} \varphi (t-k)= \sum_{m\in \mathbb Z} \widehat \varphi (m) e^{ 2\pi i m t} = \widehat \varphi (0) =1.
\end{equation}
\tag{11}
$$
Thus, $\sum_{k\in \mathbb{Z}} \varphi (t - k) = \boldsymbol{1}$. Since $\varphi\geqslant 0$, we see that $\varphi \leqslant \boldsymbol{1}$, that is, for every nonnegative test function $f\in \mathcal{S}$ we have Hence $\varphi$ is majorized by the Lebesgue measure, and therefore $\varphi\in L_1$.
The proposition is proved. The criterion of Proposition 3 has a disadvantage: it involves the function $\widehat \varphi$, which is a priori unknown. A criterion in terms of the coefficients $\{c_k\}_{k\in \mathbb{Z}}$ exploits the $n$-ary tree. We define the tree $\mathcal{T}$ as follows. The root is associated with zero and has ${n-1}$ children with indices $k/n$, $k = 1, \dots, n-1$. The further construction is by induction: every vertex $\alpha$, apart from the root, has the $n$ children $(\alpha + k)/n$, $k = 0, \dots, n-1$. The root has level zero, its children form the first level, and so on. Thus, the $j$th root consists of $(n-1)n^{j-1}$ numbers $n^{-j}k$, $k = 1, \dots, n^{j}-1$, ${k\not\equiv 0\pmod{n}}$. A subset $\mathcal{A}$ of vertices of $\mathcal{T}$ is called a minimal cut set if every infinite path from the root along the tree (paths are without backtracking and the root is not in a path) has a unique common vertex with $\mathcal{A}$. All minimal cut sets are finite. The simplest one is the set of vertices of the first level, $\mathcal{A}=\{{1}/{n}, \dots, (n-1)/{n}\}$. Proposition 4. Suppose all the $c_k$ are nonnegative; then $\varphi \in L_1$ if and only if there exists a minimal cut set of the $n$-ary tree $\mathcal{T}$ that consists of zeros of the mask $\boldsymbol{c}$. Proof. Necessity. Since $\varphi$ has a compact support, it follows from the Paley–Wiener theorem that $\widehat \varphi$ is an entire function. Therefore, it has finitely many zeros, if any, on the unit disc. This implies that there exists $j\geqslant 1$ such that $\widehat \varphi $ does not have zeros on the $j$th level of $\mathcal{T}$, that is, $\boldsymbol{c}(n^{-j}m)\ne 0$ for every natural number $m < n^j$, $m\not\equiv 0\pmod{n}$. Let $m = \sum_{k=0}^j d_kn^k =d_j \dots d_0$ be the standard $n$-adic expansion of $m$, possibly starting with zeros, such that $d_0 \ne 0$. We add the digit $d_{j+1} = 0$ and substitute $\xi = m$ into equation (10). Then we obtain Since $\widehat \varphi(m) = 0$ and $\widehat \varphi(n^{-j}m) \ne 0$, we see that one of the numbers $n^{q-j}m =0.d_{j-q}\dots d_0$ must be a zero of $\boldsymbol{c}$. These numbers form a finite path of length $j$. Thus, every path of length $j$ contains a zero of the polynomial $\boldsymbol{c}$.
Sufficiency. Assume that there exists a minimal cut set $\mathcal{A} \subset \mathcal{T}$ such that $\boldsymbol{c}(\mathcal{A}) = 0$. Then taking an arbitrary natural number $m$ and applying formula (12) we obtain $\widehat \varphi(m) =0$, which completes the proof for positive $m$. The proof for negative $m$ is the same. The proposition is proved. § 3. Criterion of uniqueness for a number systemNow we consider a set of digits $A = \{a_1, \dots, a_n\}$ for a (nonstandard) $n$-ary number system. We assume that $0 = a_1 < \dots < a_n$. For any integer $k \geqslant 0$ we denote by $b(k)$ the total number of its $A$-expansions having the form (1) and set formally $b(k)=0$ for any integer $k<0$. The unique expansion property means that $b(k) \leqslant 1$ for all $k\in\mathbb{Z}$. We are going to see if the sequence $\{b(k)\}_{k\in\mathbb{Z}}$ is generated by the subdivision operator $S$ with the following coefficients:
$$
\begin{equation}
c_i =\begin{cases} 1, & i \in A, \\ 0 & \text{otherwise}. \end{cases}
\end{equation}
\tag{13}
$$
This sequence will be referred to as the indicator sequence of $A$. We start with the following simple observation. Proof. In the expansion (1) for $k=nq+d$, the digit $\alpha_0 \in A$ must satisfy $\alpha_0 \equiv d\pmod{n}$, hence $\alpha_0 =ns + d$ for some $s$. Subtracting $d$ from both sides of (1) and dividing by $n$, we obtain $q-s = \sum_{j} \alpha_j n^{j-1}$, provided that $ns + d \in A$, that is, $\alpha_{ns + d} = 1$. Thus, the total number of expansions of the integer $nq+d$ is equal to the sum of the numbers of expansions of $q-s$ over all $s$ such that $\alpha_{ns + d} =1$. This completes the proof. If we set $k=nq+d$ and $i=q-s$, then equation (14) becomes The right-hand side is precisely the subdivision operator (5). Thus, we obtain the following result.Corollary. Let $\boldsymbol{b}^{(j)} \in l_{\infty}$ be the sequence $\{b(k)\}_{k=0}^{n^j-1}$ complemented by zeros for $k < 1$ and $k \geqslant n^j$. Then $\boldsymbol{b}^{(j)} =S\boldsymbol{b}^{(j-1)}$. Theorem 1. For every $j\geqslant 1$, where $S$ is the subdivision operator defined by the indicator sequence of $A$. Thus, the sequence $\boldsymbol{b}^{(j)}$ defined in the corollary coincides with the sequence $S^j\delta$. Proof of Theorem 1. We argue by induction on $j$. For $j=0$ we have $b(0) = 1$ and $(S^0\delta)_0 = (\delta)_0 = 1$, so the required result is true. The transition $j-1\mapsto j$ is provided by the corollary.
The theorem is proved. Now we formulate the fundamental result. Let $\{c_k\}_{k\in \mathbb{Z}}$ be the indicator sequence of $A$, $\boldsymbol{c}(\,\cdot\,)$ be the mask of this sequence and $\mathcal{T}$ be the $n$-ary tree. Theorem 2. The following assertions are equivalent: Proof. The equivalence of (b) and (c) follows from Proposition 4. Let us prove the equivalence of (a) and (b).
(a) $\Rightarrow$ (b). Assume the contrary: property (a) holds, that is, $b(k) \leqslant 1$, $k\in \mathbb{Z}$, but $\varphi \notin L_1$. This means that $\varphi$ is a purely singular Borel measure (Lemma 1). Consider the transition operator $[Tf](t)=\sum_{i=1}^n \varphi(nt - a_i)$ and take $f=\chi_{[0,1]}$. By equation (7) we have
$$
\begin{equation*}
[T^jf](t)= \sum_{k\in \mathbb Z} (S^j\delta )_k f(n^j t-k) = \sum_{k\in \mathbb Z} (S^j\delta )_k \chi_{[n^{-j}k, n^{-j}(k+1)]}.
\end{equation*}
\notag
$$
On the other hand $T^jf\to \varphi$ by Theorem A. Convergence is in $\mathcal{S}'$, which, for nonnegative distributions, means convergence in measure. Applying now Theorem 1 we obtain $(S^j\delta)_k=b(k)$ for all $k\leqslant n^j-1$. Since for $k$ ranging from zero to $n^j-1$ the intervals $[n^{-j}k, n^{-j}(k+1)]$ cover $[0,1]$, we conclude that the restriction of the function $\sum_{k\in \mathbb Z} (S^j\delta )_k \chi_{[n^{-j}k, n^{-j}(k+1)]}$ to the interval $[0,1]$ is equal to
$$
\begin{equation*}
f_j=\sum_{k=0}^{n^j-1} b(k) \chi_{[n^{-j}k, n^{-j}(k+1)]}.
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation}
f_j =T^jf \bigl|_{[0,1]} \to \varphi \bigl|_{[0,1]} \quad \text{as } j\to \infty.
\end{equation}
\tag{17}
$$
By Proposition 1 the function $\varphi$ is of pure type, hence the assumption $\varphi \notin L_1$ implies that $\varphi$ is purely singular. So its restriction to $[0,1]$ is purely singular too. On the other hand, if $b(x)\leqslant 1$ for all $b(k)$, then the function on the right-hand side of (17) does not exceed one, and neither does its limit $\varphi\bigl|_{[0,1]}$. Thus the function $\varphi\bigl|_{[0,1]}$ is majorized by the Lebesgue measure and is not purely singular.
(b) $\Rightarrow$ (a). Assume that there is an integer with at least two $A$-expansions, the longest of which contains $r$ digits. Let $A_r = \bigl\{\sum_{j=0}^{r-1} \alpha_jn^j,\,\alpha_j\in A,\, j \leqslant r\bigr\}$. Since $a_1=0$, the set $A_r$ contains all $A$-presentable numbers of length at most $r$. Hence at least two elements of $A_r$ coincide, so we have $|A_r| < n^r$. Consider the $r$th power of the transition operator:
$$
\begin{equation}
[T^rf](t) = \sum_{k\in A_r}^n b_r(k) \varphi(n^r t-k),
\end{equation}
\tag{18}
$$
where $b_r(k)$ is the total number of $A$-expansions of the integer $k$ with at most $r$ digits. Clearly, $T^r\varphi=\varphi$, hence the refinement equation with the transition operator $T^r$ possesses the same solution $\varphi$. By Hutchinson’s theorem [13] there exists a unique compact set $Q\subset \mathbb{R}$ such that This is a fractal generated by the affine contractions $n^{-r}(\cdot +k)$. The Lebesgue measure $\mu(Q)$ does not exceed Since $n^{-r}|A_r| < 1$, it follows that $\mu(Q) = 0$. On the other hand $T^r$ preserves the set of Borel measures with support on $Q$. Taking an arbitrary measure $\psi$ of this type normalized by the condition $(\psi,\boldsymbol{1})=1$ and applying Theorem A we obtain Therefore, $\varphi$ also has support on $Q$, hence it is purely singular.
Theorem 2 is proved. Remark 1. Now we see that Theorem 2, in combination with Proposition 1 and Proposition 2, provides an algorithm to check freeness for a set $F=\{f_i=n x+ a_i, i=1,\dots,n\}$, where $n,a_1,\dots,a_n \in \mathbb{Z}$ and $n\geqslant 2$. Indeed, the degree of the trigonometric polynomial $\sum_{k=1}^n e^{-2\pi i a_k t}$ is bounded above, and so is the cardinality of the set of its zeros on $[0,1]$. Thus, the possible minimal cut sets of the $n$-ary tree in Theorem 2 also have a bounded size, which in it turn bounds the height of possible tree vertices in the minimal cut. It follows that the check of all such vertices can be done by means of their finite enumeration and the calculation of a polynomial at the corresponding points. § 4. Uniqueness of the expansion and digits residuesIn this section we use the criterion from Theorem 2 to study the uniqueness property for the $n$-ary number system consisting of precisely $n$ digits. Again, let $A=\{a_1, \dots, a_n\}$ be a set of nonnegative digits such that $0\leqslant a_1 < \dots < a_n$. We say that the $n$-ary number system $A$ is irreducible if Since zero is allowed in the set of digits, we recall that the $A$-expansion of an integer $k$ has the form
$$
\begin{equation}
k=\sum_{j=0}^J \alpha_j n^j, \quad\text{where } a_J\neq 0.
\end{equation}
\tag{20}
$$
If $k$ has at least one such representation, we say that $k$ is a representable number. We say that the $n$-ary number system $A$ has the weak uniqueness property if two different $A$-expansions of the same length represent different numbers. The following statement is useful for working with sets of digits that contain only positive numbers. Proposition 5. Let $A=\{a_1,\dots,a_m\}$ be a set of digits such that $0<a_1<a_2<\dots<a_m$. Then the $n$-ary system $A$ has the weak uniqueness property if and only if the $n$-ary system $B=\{0, a_2-a_1,\dots, a_m-a_1\}$ has the uniqueness property. Proof. We prove by contradiction in both directions. First, if $A$ does not have the weak uniqueness property, then there exist two tuples $U=(u_0,u_1,\dots,u_s)$ and $V=(v_0,v_1,\dots,v_s)$ in $A^s$ such that and subtracting $a_0(1+n+\dots +a^s)$ from both sides we obtain which gives us two distinct tuples $U'$ and $V'$ in $B^p$. By removing the most significant digits until they are distinct from zero, we obtain two tuples refuting the uniqueness property of the system $B$.
Now suppose that the $n$-ary system $B$ does not have the uniqueness property and there exists $U=(u_0,u_1,\dots,u_s)\in B^s$ and $V=(v_0,v_1,\dots,v_t)\in B^t$ such that Without loss of generality we may assume that $s\geqslant t$. Consider the following two tuples $U',V'\in A^{s+1}$:
$$
\begin{equation*}
U'=(u_0+a_0,u_1+a_0,\dots,u_s+a_0) \ \ \text{and}\ \ V'=(v_0+a_0,v_1+a_0,\dots,v_t+a_0,a_0,\dots, a_0).
\end{equation*}
\notag
$$
They represent the same number in the system $A$, obtained from (21) by adding $a_0(1+n+\dots +a^s)$.
The proposition is proved. Now we are ready to prove two results on how the uniqueness property of the $n$-ary system with $n$ digits is related to their residues modulo $n$. Theorem 3. Let $n$ be a composite number. Then there exists an irreducible set $A$ consisting of $n$ nonnegative digits such that the $n$-ary number system $A$ possesses the uniqueness property, but $A$ contains two numbers congruent modulo $n$. Proof. Since $n$ is a composite number, there exist integers $n_1$ and $n_2$, both greater than $1$, such that $n = n_1 n_2$. We construct the following set of digits
$$
\begin{equation}
A=\{un_1n + v\colon 0\leqslant u < n_2,\,0\leqslant v < n_1\}.
\end{equation}
\tag{22}
$$
As $n_1>1$, taking $u=0$ we obtain the digits $a_1 = 0$ and $a_2 = 1$, so condition (19) holds. Since $n_1$ divides $un_1n$ and $0\leqslant v<n_1$ in (22), no digit can be congruent to $n_1$ modulo $n$. Hence the digits do not form a complete system of residues modulo $n$.
From (22) it follows that no digits $a$ and $a'$ can satisfy the congruence $a - a'\equiv un_1\pmod n$ for $1\leqslant u < n_2$. Then, considering the difference of two expansions of type (20) modulo $n$ we see that if $y$ and $y'$ are representable numbers, then we also have
$$
\begin{equation}
y-y'\not\equiv un_1 \pmod n \quad\text{when } 1\leqslant u < n_2.
\end{equation}
\tag{23}
$$
Now we prove that a positive integer has at most one expansion of type (20). Assume the contrary, and let $x$ be the least positive integer having at least two expansions
$$
\begin{equation*}
x=\sum_{j=0}^J \alpha_j n^j=\sum_{j=0}^{J'} \alpha'_j n^j \quad\text{with } \alpha_J\neq 0 \text{ and } \alpha'_{J'}\neq 0.
\end{equation*}
\notag
$$
Then the last digits $\alpha_0$ and $\alpha'_0$ must be distinct: otherwise the number $(x - \alpha_0)/n$ also has two distinct expansions, but this contradicts the assumption of minimality for $x$ selected. Hence $\alpha_0\neq \alpha'_0$. Without loss of generality we assume that $\alpha_0 < \alpha'_0$. Then we have and $y>y'$ are some representable numbers. Thus, $\alpha'_0-\alpha_0=n(y-y')$, hence If the digits $\alpha'_0$ and $\alpha_0$ were formed in $A$ as $\alpha'_0=u_1n_1n+v_1$ and $\alpha'=u_2n_1n+v_2$, then from (24) we obtain $v_1=v_2$, hence $\alpha'_0-\alpha_0 = (u_2-u_1) n_1n$. Therefore, $y-y'=(u_2-u_1)n_1$, where $1\leqslant u_2-u_1 < n_2$, which contradicts (23). This proves the uniqueness of the expansion.
Theorem 3 is proved. Theorem 4. For an arbitrary prime number $p$ the following holds: an irreducible $p$-ary number system $A$ has a uniqueness property if and only if the set $A$ does not contain two integers congruent modulo $p$. Proof. Sufficiency is straightforward (see, for example, [22], Theorem 4), so we prove necessity.
Let $a_1 < \dots < a_p$ be an irreducible set of nonnegative digits such that every number has at most one representation in base $p$ with digits $a_1, \dots, a_p$. We show that in this case $a_1, \dots, a_p$ form a complete system of residues modulo $p$. To do this we use Theorem 2. For any tuple $\boldsymbol{c} = (c_1,\dots,c_p)\in\mathbb{Z}_{\geqslant 0}^p$ we define the polynomial $P_{\boldsymbol c} (z)=\sum_{j=1}^p z^{c_j}$. For $m\in\mathbb{N}$ a complex number $z$ is a primitive $p^m$th root of unity if $z^{p^m} = 1$, but $z^{p^{m-1}}\neq 1$. Set $\boldsymbol{a} = (a_1,\dots,a_p)$ and $\boldsymbol{b}=(0,a_2-a_1,\dots,a_p-a_1)$. From Proposition 5 we can see that the uniqueness property of the $n$-ary system $A$ implies uniqueness for the system $B=\{0,a_2-a_1,\dots,a_p-a_1\}$, to which we can apply Theorem 2. The implication (a) $\Rightarrow$ (c) in Theorem 2 shows that some zero of the polynomial $P_{\boldsymbol{b}}$ is a primitive $p^m$th root of unity for some $m\in\mathbb{N}$, from which it follows that for some $m$ all primitive $p^m$th roots of unity are zeros of $P_{\boldsymbol{b}}$. Since $P_{\boldsymbol{a}}=e^{-2\pi i a_0}P_{\boldsymbol{b}}$, the same is true for the polynomial $P_{\boldsymbol{a}}$. This suffices for our purposes. Recall that $z$ is a $p^m$th primitive root of unity if and only if it is a zero of the cyclotomic polynomial Next we observe that for all $a,\widetilde a\in\mathbb{Z}_+$ such that $a\geqslant\widetilde a$ and $a\equiv\widetilde a\ (\bmod\ p^m)$ the polynomial $z^a - z^{\widetilde a}$ is divisible by $z^{p^m}-1$, which is in its turn divisible by $Q$. Hence all primitive $p^m$th roots of unity are zeros of $z^a - z^{\widetilde a}$. For any $j=1,\dots,p$ we choose $\widetilde a_j$ such that $0 \leqslant \widetilde a_j < p^m$ and $\widetilde a_j\equiv a_j\pmod{p^m}$. Set $\widetilde P(z)=\sum_{j=1}^p z^{\widetilde a_j}$. Then primitive $p^m$th roots of unity are zeros of $\widetilde P$. This implies that $ \widetilde P = QR,$ where $R$ is an integral polynomial of degree $<p^{m-1}$. Moreover, all coefficients of $R$ are nonnegative. We have $\widetilde P(1) = Q(1) = p$. Hence $R(1) =1$ and $R(z) = z^u$ for some $u$ satisfying $0\leqslant u<p^{m-1}$.If $m=1$, then $R(z) = 1$ and $\widetilde P(z) = \sum_{j=0}^{p-1} z^j$. We see that the multiset $\{\widetilde a_1,\dots,\widetilde a_p\}$ is actually the set $\{0,\dots,p-1\}$. This means that $a_1, \dots, a_p $ form a complete system of residues modulo $p$ as required. Let $m>1$. Then all numbers $\widetilde a_j$ are congruent to $u$ modulo $p^{m-1}$. Consequently, all numbers $a_j$ are also congruent to $u$ modulo $p^{m-1}$. This does not agree with the irreducibility of the set $\{a_1, \dots, a_p\}$. Theorem 4 is proved. Remark 2. If $n$ is a prime number, Theorem 4 provides an easy freeness test for a set of functions First, we order the set $A=\{a_1,\dots,a_n\}$ in increasing order and compute $d=\gcd(a_2-a_1, \dots, a_p-a_1)$. Then the set $\{0,(a_2-a_1)/d,\dots,(a_p-a_1)/d\}$ is an irreducible $p$-ary number system, and we are left to check whether all of its elements are distinct modulo $p$. Here the admissibility of scaling the coefficients by $d$ can be proved similarly to the admissibility of the shift in Proposition 2, by use of the conjugating function $g(x)=dx$. 
Citation in format AMSBIB
\Bibitem{KonProTal25} |
|
||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|