10
$\begingroup$

Suppose $A = (a_n) = (a_1, a_2, a_3, . . .)$ is an positive, increasing sequence of integers.

Define an $A$- expressible number $c$ if $c$ is the alternating sum of a finite subsequence of $A.$ To form such a sum, choose a finite subset of the sequence $A,$ list those numbers in increasing order (no repetitions allowed), and combine them with alternating plus and minus signs. We allow the trivial case of one-element subsequences, so that each an is $A-$expressible.

Definition. Sequence $A = (a_n)$ is an “alt-basis” if every positive integer is uniquely $A-$ expressible. That is, for every integer $m > 0,$ there is exactly one way to express $m$ as an alternating sum of a finite subsequence of $A.$

Examples. Sequence $B = (2^{n−1}) = (1, 2, 4, 8, 16, . . .)$ is not an alt-basis because some numbers are B-expressible in more than one way. For instance $3 = −1 + 4 = 1 − 2 + 4.$

Sequence $C = (3^{n−1}) = (1, 3, 9, 27, 81, . . .)$ is not an alt-basis because some numbers (like 4 and 5) are not C-expressible.

An example of an alt-basis is $\{2^n-1\}=\{1,3,7,15,31,\ldots\}$

Is there a fairly simple test to determine whether a given sequence is an alt basis?

I have attempted to solve this from a limited knowledge in sequences and have found out various kinds of sequences do not work but fail to see what it is that could make it work.

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ Seems slightly (at least) related to this: encyclopediaofmath.org/index.php/Additive_basis But I think you know already about additive bases. $\endgroup$ – user757601 Mar 25 at 0:37
  • $\begingroup$ See math.stackexchange.com/questions/3579462. (Not an exact duplicate because it doesn't ask for a general test to determine whether a sequence is an alt-basis.) What is the source of this question? $\endgroup$ – joriki Mar 25 at 6:47
  • $\begingroup$ Do you know of any alt-bases that are not of the form $\{b_1,b_2,\dots,b_k,a_{k+1},a_{k+2},\dots\}$ where $A=\{a_1,a_2,\dots\}=\{2^n-1\}$ and $\{b_1,\dots,b_k\}$ is some finite increasing set of integers? $\endgroup$ – Vepir Mar 25 at 21:54
  • 1
    $\begingroup$ For example I believe that $\{5\cdot2^{n - 2} + (-1)^{n + 1} 2^{n - 2} - 1\}$ is an alt-basis. $\endgroup$ – Vepir Mar 25 at 22:50
4
$\begingroup$

I can’t answer the question, but I can at least give you a systematic large family of alt-bases.

If $A$ is a finite set of positive integers, let $S(A)$ be the set of $A$-expressible integers, and let $S^+(A)$ be the set of $A$-expressible positive integers. Then

$$S(A)=S^+(A)\cup\{-a:a\in S^+(A)\},$$

and if $b>\max A$, then

$$S^+\left(A\cup\{b\}\right)=S^+(A)\cup\{b-s:s\in S^+(A)\}\cup\{b\}.$$

Thus, if $|A|=n$, the maximum number of $A$-expressible positive integers is $2^n-1$, and $\max S(A)=\max A$.

Now suppose that $A=\{a_n:n\in\Bbb Z^+\}$, where $a_n<a_{n+1}$ for each $n\in\Bbb Z^+$. For $n\in\Bbb Z^+$ let $A_n=\{a_k\in A:1\le k\le n\}$. Then each $m\in S(A)$ is uniquely $A$-expressible iff $|S^+(A_n)|=2^n-1$ for each $n\in\Bbb Z^+$. Moreover, $S^+(A)=\Bbb Z^+$ iff for each $k\in S^+(A)$ there is a minimal $n(k)\in\Bbb Z^+$ such that $k\in S^+(A_{n(k)})$. Note that either $n(k)=1$, or $k\in S^+(A_{n(k)})\setminus S^+(A_{n(k)-1})=\{a_{n(k)}-s:s\in S^+(A_{n(k)-1})\}$.

For $n\in\Bbb Z^+$ let

$$a_n=2^n-1=\underbrace{1\ldots 1}_n\text{ in binary},$$

and let $A=\{a_n:n\in\Bbb Z^+\}$. It’s not hard to see that

$$S^+(A_n)=\{1,\ldots,2^n-1\}$$

for each $n\in\Bbb Z^+$, so $A$ is, as you already observed, an alt-basis. For instance, working in binary, we see that

$$\begin{align*} 22&=10110_{\text{two}}\\ &=11111_{\text{two}}-1111_{\text{two}}+111_{\text{two}}-1_{\text{two}}\\ &=31-15+7-1\\ &=a_5-a_4+a_3-a_1. \end{align*}$$

Now let $\ell,m\in\Bbb Z^+$. For $n=1,\ldots,\ell$ let

$$\color{red}{a_n^{(\ell,m)}}=2^ma_n=\underbrace{1\ldots 1}_n\underbrace{0\ldots 0}_m\text{ in binary}.$$

For $n=\ell+k$, where $k=1,\ldots,m$, let

$$\color{blue}{a_n^{(\ell,m)}}=2^{m-k}a_n=\underbrace{1\ldots 1}_n\underbrace{0\ldots 0}_{m-k}\text{ in binary}.$$

Finally, for $n>\ell+m$ let $a_n^{(\ell,m)}=a_n$, and let $A_{(\ell,m)}=\left\{a_n^{(\ell,m)}:n\in\Bbb Z^+\right\}$; then $A_{(\ell,m)}$ is an alt-basis.

For example,

$$\begin{align*} A_{(4,2)}&=\{\color{red}{4},\color{red}{12},\color{red}{28},\color{red}{60},\color{blue}{62},\color{blue}{63},127,\ldots\}\\ &=\{\color{red}{100},\color{red}{1100},\color{red}{11100},\color{red}{111100},\color{blue}{111110},\color{blue}{111111},1111111,\ldots\}\text{ in binary}. \end{align*}$$

To verify this it suffices to show that $S^+\left(\left\{a_n^{(\ell,m)}:1\le n\le \ell+m\right\}\right)=S^+(A_{\ell+m})$. The argument is a bit messy to write out, but the idea is straightforward; I’ll illustrate it with $A_{(4,2)}$. First, it’s clear from the discussion of $A$ that

$$\begin{align*} S^+\left(\{4,12,28,60\}\right)&=S^+\left(4\{1,3,7,15\}\right)\\ &=4S^+\left(\{1,3,7,15\}\right)\\ &=4\{1,2,\ldots,15\}\\ &=\{4,8,12,\ldots,60\}\\ &=4S^+(A_4). \end{align*}$$

Then

$$\begin{align*} S^+(\{4,&12,28,60,62\})=\\ &4S^+(A_4)\cup\left\{|62-s|:s\in S^+(\{4,12,28,60\})\right\}\cup\{62\}=\\ &4S^+(A_4)\cup\left\{|62-s|:s\in\{4,8,12,\ldots,60\}\right\}\cup\{62\}=\\ &4S^+(A_4)\cup\{2,6,10,\ldots,58,62\}=\\ &\{2,4,6,8,\ldots,60,62\}=\\ &2S^+(A_5), \end{align*}$$

and a similar calculation shows that $S^+(\{4,12,28,60,62,63\})=S^+(A_6)$.

| cite | improve this answer | | | | |
$\endgroup$
1
$\begingroup$

I did not collect the set of all alt-bases, but I did find some useful observations, including:

Alt-basis must contain an infinite number of terms of form $a_k=2^{k}-1,k\in N\subseteq\mathbb N$.

The converse does not hold. At the end, I give examples of alt-bases and not-alt-bases in this context.

Do correct me If I missed anything.



Let $A=\{a_1,a_2,\dots\}$ such that $a_1\lt a_2 \lt \dots$ are positive integers.

Definition. For $A$ to be an "alt-basis", we need to have both the "uniqueness" and "completeness". In other words, every number is expressible in exactly one way via alternating summation of subsets of $A$, which are summed in increasing order.

Definition. A finite (sub)sequence $A|_n=\{a_1,\dots,a_n\}$ is an "alt-prefix" if every integer in $[1,2^{n}-1]$ is uniquely expressible via alternating summation of subsets of $A|_n$ when summed in increasing order. The element $a_n$ is called an "anchor element".

Definition. "Anchor sequence" is a set $\mathcal A(A):=\{a_{n_1},a_{n_2},\dots\}$ of all "anchor elements" $a_{n_1},a_{n_2},\dots$

Notice that a set has $2^n$ subsets minus the empty set and that every subset can be rearranged in an increasing order. We want to assign a distinct value to each of those subsets via the alternating summation, to have an alt-basis. The alt-prefix is defined to cover exactly those $2^n-1$ subsets. It follows that:

Lemma. $A$ is an alt-basis $\iff$ $A$ is a union of alt-prefixes $A=A|_{n_1}\cup A|_{n_2}\cup \dots$

That is, $A$ is an alt-basis if and only if there exists a corresponding infinite anchor sequence $\mathcal A(A)$.

We add two more definitions to write all of this more easily:

Definition. Let $s(\{b_1,\dots,b_n\})$ be the result of the alternating summation of $b_1\lt b_2\lt \dots\le b_n$. Let $s_+$ and $s_-$ always start the alternating summation with $+,-$ respectively. Then $s_+=-s_-$. If $n$ is odd then $s=s_+$ and if $n$ is even then $s=s_-$. This guarantees $s\gt 0$ because the largest element $b_n$ will have a positive sign.

Definition. Define "$n$-th partial subset-sum set" of a positive increasing integer sequence $A$ as:

$$\mathcal S_n(A):=\{s(A_i):A_i\in\mathcal P(A|_n)\}$$

Where $\mathcal P(A|_n)$ is the set of all subsets of $A|_n=\{a_1,a_2,\dots,a_n\}$.

The set of all "anchor elements" $\mathcal A(A)=\{a_{n_1},a_{n_2},\dots\}\subseteq A$ satisfies $S_{n_i}=[1,2^{n_i-1}-1]$ for all $n_i$.

Corollary. $A$ is an alt-basis if and only if it "is covered by the anchor sequence": $\max \mathcal A(A)\to \infty$.

Notice that $\max S_n = a_n$. If $a_n$ is an anchor element, then $\max S_n = 2^n-1$. This gives:

Proposition. If $a_n$ is an anchor element, then $a_n=2^n-1$.

The converse does not hold. For example, in $\{1,4,7\}$ the $a_3=7=2^3-1$ but $a_3$ is not an anchor element, because $S_3=\{1,3,4,6,7\}\ne[1,7]$.


Example $1$. It is not hard to see that $\mathcal A(\{2^n-1\})=\{2^n-1\}$. This is because:

  • $S_1=\{(+1)\}$ $\implies$ $a_1$ is an anchor element.

  • $S_2=\{(+1),(-1+3),(3)\}$ $\implies$ $a_2$ is an anchor element.

  • $S_3=\{(+1),(-1+3),(3),(-3+7),(+1-3+7),(-1+7),(7)\}$ $\implies$ $a_3$ is an anchor element.

  • $\dots$ proceed via induction to show every $a_n$ is an anchor element.

Since $\mathcal A(\{2^n-1\})$ exists and covers the entire $\{2^n-1\}$, the $\{2^n-1\}$ is an alt-basis.


Example $2$. The $\mathcal A(\{n\})=\{1\}$ does not cover the entire $\{n\}$, hence $\{n\}$ is not an alt-basis.

It is not hard to see that $\max S_n = n \lt 2^n-1\implies a_n$ is not an anchor element, for every $n\gt 1$.


Example $3.$ We construct an alt-basis where every $2$nd element is an anchor element.

$$A=\begin{cases} 2^n-1, & n\text{ is even} \\ 2^n+2^{n-1}-1, & n\text{ is odd} \end{cases}$$

Use an inductive argument. Assume $n=2k$, $a_{n}=2^{n}-1$ is an anchor element, which means we have uniquely constructed all $I_0=[1,2^n-1]=S_{n}$ elements. Now we can subtract numbers in this interval from $a_{n+1}$ to see that:

  • $a_{n+1}=2^{n+1}+2^{n}-1$ will cover $I_1=[a_{n+1}-a_{n}, a_{n+1}]=[2^{n+1},2^{n+1}+2^{n}-1]$

Here we see that $I_0\cup I_1 \ne [1,2^{n+1}-1]$ $\implies$ $a_{n+1}$ is not an anchor elemetn.

To see that $a_{n+2}=2^{n+2}-1$ is an anchor element, lets see what will we cover with it:

  • $a_{n+2}$ combined with $I_0$ will cover $I_2=[a_{n+2}-a_{n}, a_{n+2}]=[2^{n+1}+2^{n},2^{n+2}-1]$

  • $a_{n+2}$ combined with $I_1$ will cover $I_3=[a_{n+2}-a_{n+1},a_{n+2}-2^{n+1}]=[2^n,2^{n+1}-1]$

Now observe $I=I_0\cup I_3\cup I_1\cup I_2$ is equal to:

$$ I=[1,2^n-1]\cup[2^n,2^{n+1}-1]\cup[2^{n+1},2^{n+1}+2^{n}-1]\cup[2^{n+1}+2^{n},2^{n+2}-1]=[1,2^{n+2}-1] $$

Implying $a_{n+2}$ covers $I=[1,2^{n+2}-1]=S_{n+2}$, $\implies$ $a_{n+2}$ is an anchor.

It is not hard to check base cases $n=1,2$, and we are done. We have:

$$\mathcal A\left(\left.\begin{cases} 2^n-1, & n\text{ is even} \\ 2^n+2^{n-1}-1, & n\text{ is odd} \end{cases}\right\}\right)=\{2^{2n}-1\}$$

So we have an alt-basis $A$.


Example $4$. It is not hard to show that:

$$ A=\{2^k,2^k+1,2^k+3,2^k+7,\dots,2^k+2^{k}-1,2^{k+2}-1,2^{k+3}-1,\dots\} $$

Is an alt-basis for every $k=0,1,2,\dots$, whose anchors are all elements $a_n,n\gt k$.


Example $5$. The sequence of natural, triangular, tetrahedral,... numbers, or in general, any diagonal of the pascals triangle, is not an alt basis.

This is because for every fixed $d$, there exists $n_0$, such that for all $n\ge n_0$, we have $\binom{n+d-1}{d}<2^n$ implying that $\max S_n\lt 2^n-1$ for all $n\ge n_0$. This implies the sequence of anchors has at most $n_0$ elements, implying $\max\mathcal A(A)\lt \infty$, hence we do not have an alt-basis becuase of inevetable duplicates.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ I think => part of the initial lemme requires proof. $\endgroup$ – balcinus Mar 31 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.