Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
    
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
add comment

7 Answers

up vote 6 down vote accepted

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

share|improve this answer
1  
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
add comment

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

share|improve this answer
    
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
add comment

All sets of integers are closed under this binary operation when A=1 and B=0.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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