Could one describe the subsets of the integers closed under the binary operation Ax+By where A and B are arbitrary fixed integers ? That is, describe the subsets S of the integers such that if $x,y\in S$ then $Ax+By\in S$. Or just the minimal such subsets containing 1.
Do I guess correctly that this question belongs to additive combinatorics ?
I think the problem is pretty much solved in a series of papers by Klarner et al;
David A Klarner and Karel Post, Some fascinating integer sequences. A collection of contributions in honour of Jack van Lint. Discrete Math. 106/107 (1992), 303–309, MR 93i:11031
D G Hoffman and D A Klarner, Sets of integers closed under affine operators—the finite basis theorem. Pacific J. Math. 83 (1979), no. 1, 135–144, MR 83e:10080
D G Hoffman and D A Klarner, Sets of integers closed under affine operators—the closure of finite sets. Pacific J. Math. 78 (1978), no. 2, 337–344, MR 80i:10075
Some trivial observations.
If $A=1, B=-1$ we get subgroups of $\mathbb{Z}$.
If $A=1, B=1$ we get positive cones (sets closed under positive linear combinations).
If $A=k, B=0$ we get sets closed under multiplication by $k$.
If $A=2, B=-1$ and $1, 2 \in S$, then $S=\mathbb{Z}$. To see this, let $n \in \mathbb{N}$. By induction we may assume that $n-2, n-1 \in S$. But then $n=2(n-1)-(n-2) \in S$. Note also that clearly $0 \in S$, and that $-n=n-2n \in S$.
All sets of integers are closed under this binary operation when A=1 and B=0.
Let $(n)$ be the closed set generated by $n$. Clearly, $(0)=${0}. As you probably figured out, it suffices to describe $(1)$. Indeed, $(n)=n(1)$ and any such set is a union of all $(n)$ it contains.
I am too drunk right now to try to describe $(1)$ in any nontrivial way. Clearly, $(1)$ is contained in ${ F(A,B) }$ where $F$ is the set of integer polynomials with positive coefficients. You can pinpoint this set further by saying that it contains $1$ and $A+B$ and closed under substitutions. Now I have no clue how to describe sets of polynomials closed under substitutions but will have a go at it later...
Finding all the solutions is probably hard, if I am not mistaken any set containing $d\ZZ$ where $d$ is gcd $(A, B)$ is a solution, but this is far from optimal.
If you are looking for the the minimal $S$, just by looking over the general pattern, you are solving multiple higher order recurences at once (at each step the number of recurences increases).
You start with $x_0=1, x_1= A+B$ and at each step, given $x_0,..., x_{2^n}$ you try to figure out a new term $x_{??} = A x_{k}+ B x_{m}$ with $k,m \leq 2^n$.
In particular the solutions to the following recurences will always be in your set: $$x_1=1, x_{n+1}= (A+B) x_n \,.$$ $$x_1=1, x_2= A+B x_{n+1}= A x_n+ Bx_{n-1} \,.$$ $$x_1=1, x_2= A+B x_{n+1}= B x_n+ Ax_{n-1} \,.$$ but also you have things like
$$x_1, x_2, x_3 \in \{ 1, A+B, A+AA+B^2, A^2+AB+B , (A+B)^2 \} x_{n+1}= A x_n+ Bx_{n-2} \,.$$ $$x_1, x_2, x_3 \in \{ A+AA+B^2, A^2+AB+B , (A+B)^2 \} x_{n+1}= A x_{n-1}+ Bx_{n-2} \,.$$ $$x_1, x_2, x_3 \in \{ A+AA+B^2, A^2+AB+B , (A+B)^2 \} x_{n+1}= B x_{n-1}+ Ax_{n-2} \,.$$ $$x_1, x_2, x_3 \in \{ A+AA+B^2, A^2+AB+B , (A+B)^2 \} x_{n+1}= B x_{n}+ Ax_{n-2} \,.$$
and so on.
I migth be wrong, but if I am not mistaken, the Question you are asking is equivalent to the following:
For all the possible $k$ describe recursivelly the general solution to all the recurences of order $k$ of the type $x_{n+k} = A x_{n+m} + Bx_n$ and $x_{n+k} = B x_{n+m} + Ax_n$, where $x_1,..., x_{k-1}$ are solutions to a reccurence of this type of order at most $k-1$.
Rather than attempt an answer, I suggest a generalization: look at the appropriate clones on the integers, or even on the natural numbers when A and B are positive.
Considering the latter, it is clear that the 2-clone (set of functions in two variables closed under projections and composition) containing x + y contains any other 2-clone generated by Ax + By, where A and B are positive integers. Also, the clone containing Ax + By also contains many operations of the form Ax + Cy and Dx + By, where C is a positive multiple of B and belongs to a certain subsemigroup of the natural numbers, and where D has analogous restrictions.
Once the various clones are understood, then you can plug in values for x and y to see what semigroups arise. If A and B are larger than two, you will get things that are related, but I suspect are properly contained in, subsemigroups studied in the Frobenius postage-stamp (or coin) problem. I think the clones will be a richer class of items to study, however.
Gerhard "Ask Me About System Design" Paseman, 2010.10.27
I look forward to reading those papers of Klarner and Hoffman. It appears that (as a special case of their results) when $\gcd(A,B)=1$ then any closed set is a finite union of arithmetic progressions ( infinite or bi-infinite) possibly augmented by a finite set of integers. I can't tell from mathscinet if they discuss the case $\gcd(A,B)>1$.
If $A=B=2$ then $\{1\} \cup \{6k+4 \mid k \ge 0\}$ describes a closed set.
The case $A=B=3$ is more intricate. Consider the infinite set of integers $\{1,6,21,66,201,\dots\}$ and the infinite set of (disjoint) positive integer progressions $\{36+45k,111+135k, 336+405k\dots\}$ where each element is 3 more than 3 times the previous one (A nice base 3 description is possible). I believe I can prove that together they make the smallest closed set containing $1$. None of the integers in the first set belong to any arithmetic progression in the second set.
