Sets closed on addition

724 Views Asked by At

Consider a set of positive real numbers $S$ which is closed on addition. Also if we have a set of positive real numbers $S_2$ such that each element in $S$ can be expressed as the sum of elements in $S_2$, allowing an element to be used multiple times, then we say $S_2$ generates $S$.

For any set $S$ (of positive real numbers) closed on addition, we say element is special if it cannot be expressed as the finite sum of other elements (obviously, you can't use the element itself). Then, we call a set good if the set of special elements of $S$ generates $S$.

The problem in question was that if you are given an infinite sequence of positive reals $a_n$ that is decreasing and $a_i$ is in $S$ for all $i$ and $a_i - a_{i+1}$ is also in $S$ for all $i$, can we find a subset of S closed on addition that is bad? (By the way, S is closed under addition as well) I think the answer is yes but couldn't prove it.

Some things i tried to prove was that the set generated by numbers of the form $a_i$ and $a_{i}-a_{i+1}$ for all $i$ is a bad set, and obviously this is a subset of S, but this seemed to fail since i dont know how to express $a_i-a_{i+1}$ as the sum of other elements, but $a_i$ is easy as $a_i = (a_i -a_{i+1})+a_{i+1}$

Also something cool i found was that $a_i-a_{i+1}$ is eventually less than $c$ for any positive real number $c$, which gives that for any open interval $(a,b)$ with $a<b$, we have an infinite number of elements in that range

1

There are 1 best solutions below

0
On BEST ANSWER

Update: Yes, we can always find a bad subset. Here is a proof.

Proof

Let $b_{n+1}=a_n-a_{n+1}$. Choose a sequence of indices $n_i$ (precisely how to be determined below), with $n_0=0$, and define $c_i:=\sum_{k=n_{i-1}+1}^{n_i}b_n$.

Let $R\subseteq S$ be generated by $\{c_i\}$ and $\{a_{n_i}\}$. Then certainly the elements $a_{n_i}$ are not special (since $a_{n_{i+1}}+c_{i+1}=a_{n_i}$), and so any special elements must be among the $c_i$.

We claim we can choose the indices $n_i$ so that $a_0$ is not generated by any of the $c_i$, from which it follows that $R$ is bad.

To see this, suppose we have chosen $n_j$ for all $j<i$, so that the chosen $c_j$'s do not generate $a_0$. Since there are finitely many $c_j$'s, it follows that there are finitely many possible combinations of coefficients that can generate a sum of less than $a_0$, so we will call this number of combinations $K$.

On the other hand, since each $b_n$ is positive, there is some $k\in \mathbb N$ for which $b_{n_{i-1}+1}>\frac{a_0}{k+1}$, so that a fortiori $\sum_{n= n_{i-1}+1}^mb_n >\frac{a_0}{k+1}$ for all $m>n_{i-1}$.

Now, suppose we choose $n_i>n_{i-1}$. It may be the case that we have $c_1,\dots,c_i$ generate $a_0$, however, if so, we must have the coefficient of $c_i$ be between $1$ and $k$, and there are only $K$ possibilities for the other coefficients, so there are only $kK$ total possibilities for the coefficients that express $a_0$. Therefore, if every possible choice of $n_i$ allows us to generate $a_0$, then there are two choices $n_i'$ and $n_i''$ that allow us to generate $a_0$ with the same coefficients. But this is impossible, since denoting the two corresponding values of $c_i$ as $c_i'$ and $c_i''$, if we have $$a_0=\sum_{k\leq i-1} m_kc_k + m_ic_i' = \sum_{k\leq i-1} m_kc_k + m_ic_i'',$$

then certainly $c_i'=c_i''$, whereby $n_i'=n_i''$. Thus some choice of $n_i$ allows us to continue to avoid generating $a_0$, so the existence of the desired sequence $\{n_i\}$ follows by induction.


(original remark)

This is not an answer, but a remark that is too long for a comment.

A natural way to try to disprove the conjecture (which is implicit in some attempts that have already been made) is to come up with a sequence $a_n$ and $b_n:=a_n-a_{n+1}$, let $S$ be generated by the terms of these sequences, and define some kind of complexity function $\phi\colon S\to \mathbb N$, such that $\phi^{-1}(\{n\})$ is finite for each $n$, and such that whenever $\phi(s_1+s_2)\leq n$ we have $\phi(s_1)\leq n$ and $\phi(s_2)\leq n$.

Given such a $\phi$, one immediately sees that every subsemigroup $R\subseteq S$ is good, since if $r\in R$ is not generated by special elements of $R$, and has $\phi(r)\leq n$, then we have $r=r'+r''$ where WLOG $r'$ is not generated by special elements, and has $\phi(r')\leq n$, and repeating gives us an infinite descending sequence of distinct members of $\bigcup_{k\leq n}\phi^{-1}(\{k\})$, contradicting the finiteness of that set.

However, one can never find such a complexity function $\phi$ in the first place, since we would always have the original infinite sequence $a_n$ whose distinct members all would have to satisfy $\phi(a_n)\leq \phi(a_0)$, so that $\bigcup_{k\leq \phi(a_0)}\phi^{-1}(\{k\})$ is infinite.

This is something to keep in mind for those attempting to construct counter-examples.