The notion of sumset of two sets is defined as A+B={a+b:a in A, b in B}. If the elements of A and B are not in AP, then can the elements of A+B be an arithmetic progression? If so, what are the conditions required for that? Please can you recommend me some good references.
Thanking you in advance,
Sudev Naduvath
It seems the following.
The answer is positive. Let n>= 4 be any natural number, A be the set of all n-digits binary numbers which have 1’s only at the odd indices (for instance, for n=4, A={0000, 0001, 0100, 0101}) and B be the set of all n-digits binary numbers which have 1’s only at the even indices (for instance, for n=4, B={0000, 0010, 1000, 1010}). Then both A and B are not arithmetic progressions, but A+B={0,1,2,3,...,2^n-1} is an arithmetic progression.
It seems the following.
The answer is positive. Let n>= 4 be any natural number, A be the set of all n-digits binary numbers which have 1’s only at the odd indices (for instance, for n=4, A={0000, 0001, 0100, 0101}) and B be the set of all n-digits binary numbers which have 1’s only at the even indices (for instance, for n=4, B={0000, 0010, 1000, 1010}). Then both A and B are not arithmetic progressions, but A+B={0,1,2,3,...,2^n-1} is an arithmetic progression.
I don’t understand. Again, if n=4 then I have A={0,1,4,5} and B={0,2,8,10} which are _not_ arithmetic progressions. Calculate A+B. This sum contains at most 16 different numbers. An fact, it contains exactly 16 numbers, because:
0=0+0
1=1+0
2=0+2
3=1+2
4=4+0
5=5+0
6=4+2
7=5+2
8=0+8
9=1+8
10=0+10
11=1+10
12=4+8
13=5+8
14=4+10
15=5+10
So A+B={0,...,15} is an arithmetic progression.
Alex: There is a typo 3=1+3, should be 1+2. But is there a sufficient condition ?
Tapas Chatterjee
Thanks for pointing me to a typo. It seems the following.
On the sufficiency. My construction can be naturally generalized as follows.
Let n be a natural number and (k1,...,kn) be a sequence of natural numbers with each ki>=2. Consider a product G=\prod_{i=1}^n Zk_i of groups Zk_i={0,1,2,...,ki-1} of residues mod ki. For a subset S of the set [n]={1,...,n} put
G(S)=\prod_{i=1}^n Hi, where Hi=Zk_i if i belongs to S and Hi={0} otherwise.
Let a1, a2 and b0 be arbitrary integers. Define a map f from G to the integers by putting f(x1,...,xk)=x1+k1x2+k1k2x3+...+k1k2...kn-1xn. Now put A=a1+bf(G(S)), B=a2+bf(G([n]\S)). Because for each x\in G(S) and y\in G([n]\S) we have f(x+y)=f(x)+f(y), we see that A+B=a1+a2+bf(G) is an arithmetic progression with the first term a1+a2 and the difference b. But it is easy to check that f(G(S)) is an arithmetic progression iff S is empty or S={l,l+1,...,m} for some numbers 1
As other answers give examples, I'll mention that many sets are examples even with A=B. The most simple is perhaps A=B={1,2,4,5}, with sumset {2,3,4,5,6,7,8,9,10}. In a rigorous sense, just over 1% of sets are examples.
In "Many Sets Have More Sums Than Differences" (which you can find on the arXiv), Greg Martin and I show that about 1.387% (with rigorous bounds) of the subsets A of {1,2,...,n} have sumset A+A exactly {2,3,4,..., 2n}, provided that n is sufficiently large. See also "Distribution of Missing Sums in Sumsets", by Lazarov, Miller, and myself.
If A = {n | exists x exists y n = x2 + y2 } then A + A = N, the whole set of natural numbers, because every natural number is a sum of four squares. So an arithmetic progression. Also, if the Goldbach's conjecture was true, and Q is the set of all odd primes, then Q + Q will be the set of even numbers greater than or equal 6, which is again an arithmetic progression. I am sure that one can imagine a lot of other examples.
Another simple pair of sets is A={1, 2, 4}, B={1, 3, 4}, which are clearly not arithmetic progressions, with sumset A+B={2, 3, 4, 5, 6, 7, 8}.
Apparently, there is no method to solve this problem. Either you get it right, or you don't.
Hi Mr. Naduvath,
I'd say that the answer to your question is yes.
Let an and bn be two progressions that are not arithmetic. I'd say that the conditions for the sumset to be an arithmetic progression are that :
- (aj+bi)-(ak+bl)=k*d for all aj, ak in an and bi, bl in bn. d being the difference between two consecutive terms of the sequence and k being a positive integer.
- there exists aj, ak in an and bi, bl in bn such that (aj+bi)-(ak+bl)=k*d for all positive integers k.
This is just an intuition, tell me what you think of it. I hope this helps,
Best regards,
Imène.
Don't know if that was already pointed out, but the example by Alex Ravsky is as "bad" as that neither A nor B contain a an arithmetic progression of length 3.
- Badges
- Science topic
- Similar topics
- Mathematics