describe subsets of the integers closed under the binary operation Ax+By

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 ?

-
Are A and B fixed? – Qiaochu Yuan Oct 27 '10 at 20:17
I can't figure out what you mean: $Ax+By$ whatever it is, is not a "binary operation". So does "$A=2$, $B=1$" mean that if $x$ and $y$ are elements of your set, then $2x+y$ is? – Robin Chapman Oct 27 '10 at 20:26
@Yuan: yes, A and B are fixed. @Robin: yes, true. (Shall add this in the main post). Sorry about being unclear. – mmm Oct 27 '10 at 20:47
Your claim about "it's an arithmetical progression in the case A=B" is wrong. You can just write the terms of minimal $S$ containing 1 as polynomials in A, and note that for any $d$ there is only finite number of polynomials in $S$, whose degree is less than $d$. And in the case $A=2$, $B=1$ you get $S$ equal to the set of odd positive numbers, i.e. just one arithmetical progression. – Fiktor Oct 27 '10 at 21:21
@Fiktor: true, thank you!...I'd delete my answers. The question still remains, though. – mmm Oct 27 '10 at 21:43

7 Answers

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

-
Thanks, these references are helpful! Essentially they seem to imply that such (minimal) sets are finite unions of possibly bouunded arithmetical progressions. If I could bother you further by asking whether these questions are indeed in the f7ield of additive combinatorics ? So that I know whom to ask about such questions... – mmm Oct 28 '10 at 16:15

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$.

-
Actually if $A=2, B=-1$ or more generarily $A+B=1$ the minimal set $S$ is $S=\{ 1 \}$. – Nick S Oct 27 '10 at 23:59
Yes indeed, but I am randomly assuming that in this case that 2 is also in $S$. I am addressing the first part of the question. It is probably hard to characterize $S$ for arbitrary $A$ and $B$, but as a start perhaps we can give simple conditions for when $S=\mathbb{Z}$. – Tony Huynh Oct 28 '10 at 0:06

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...

-
Wouldn't $(1)$ be the set of all integers of the form $F(A+B)$ where $F$ is a polynomial with positive integer coefficients? – Hany Oct 28 '10 at 7:09
No, $A^2$ is not in $(1)$ and $A(A+B)+B\in (1)$ is not in your set. – Bugs Bunny Oct 28 '10 at 8:47

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.

-