11
$\begingroup$

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 ?

$\endgroup$
5
  • $\begingroup$ Are A and B fixed? $\endgroup$ Oct 27, 2010 at 20:17
  • $\begingroup$ 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? $\endgroup$ Oct 27, 2010 at 20:26
  • $\begingroup$ @Yuan: yes, A and B are fixed. @Robin: yes, true. (Shall add this in the main post). Sorry about being unclear. $\endgroup$
    – mmm
    Oct 27, 2010 at 20:47
  • $\begingroup$ 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. $\endgroup$
    – Fiktor
    Oct 27, 2010 at 21:21
  • $\begingroup$ @Fiktor: true, thank you!...I'd delete my answers. The question still remains, though. $\endgroup$
    – mmm
    Oct 27, 2010 at 21:43

7 Answers 7

6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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... $\endgroup$
    – mmm
    Oct 28, 2010 at 16:15
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Actually if $A=2, B=-1$ or more generarily $A+B=1$ the minimal set $S$ is $S=\{ 1 \}$. $\endgroup$
    – Nick S
    Oct 27, 2010 at 23:59
  • $\begingroup$ 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}$. $\endgroup$
    – Tony Huynh
    Oct 28, 2010 at 0:06
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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