# Partitions of Natural Numbers with the Intersection Not Empty

Authors: Wen Yu; Min Tang
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

Letℕ be the set of nonnegative integers. For a given set A⊂ℕ the representation functions R2(A,n), R3(A,n) are defined as the number of solutions of the equation n=a+a′,a,a′∈A with condition a<a′, a≤a′, respectively. In this paper, we prove that if ℕ=A∪B and A∩B={8k:k∈ℕ}, then Ri(A,n)=Ri(B,n) cannot hold for all sufficiently large integers n where i=2,3.


---

## Body

## 1. Introduction

Letℕ be the set of nonnegative integers. For A⊂ℕ, let R1(A,n), R2(A,n), R3(A,n) denote the number of solutions of
(1)a+a′=n,a,a′∈A,a+a′=n,a,a′∈A,a<a′,a+a′=n,a,a′∈A,a<a′,
respectively. Sárközy asked ever whether there exist two sets A and B of nonnegative integers with infinite symmetric difference, that is:
(2)|(A∪B)∖(A∩B)|=∞,Ri(A,n)=Ri(B,n),n≥n0
for i=1,2,3. As Dombi [1] has shown, the answer is negative for i=1 by the simple observation that R1(A,n) is odd if and only if n=2a for some a∈A. For i=2, Dombi presented a partition of the set of all positive integers into two disjoint subsets A and B such that R2(A,n)=R2(B,n) for all sufficiently large n. For i=3, Chen and Wang [2] constructed sets A,B such that R3(A,n)=R3(B,n) for all integers n≥3, where A is the set of all those positive integers n such that the number of zeroes in the binary representation of n-1 is even, and B is the set of all those positive integers n such that the number of zeroes in the binary representation of n-1 is odd. For the other related results, the reader is referred to see [3–7].It is natural to ask the following: fori=2,3, are there subsets A,B⊂ℕ with Ri(A,n)=Ri(B,n) for all large enough integers n such that ℕ=A∪B and A∩B≠∅? Recently, the authors of this paper [8] obtained some results in this direction.In this paper, we obtain the following results.Theorem 1.
Ifℕ=A∪B and A∩B={8k:k∈ℕ}, then R2(A,n)=R2(B,n) cannot hold for all sufficiently large integers n.Theorem 2.
Ifℕ=A∪B and A∩B={8k:k∈ℕ}, then R3(A,n)=R3(B,n) cannot hold for all sufficiently large integers n.Remark 3.
Forr=1,2,3,4,5,6,7, similarly, we can prove that if ℕ=A∪B and A∩B={8k+r:k∈ℕ}, then Ri(A,n)=Ri(B,n) cannot hold for all sufficiently large integers n, where i=2,3.


## 2. Proof of Theorem1

Proof.
Suppose that there exist integern0 and sets A,B⊂ℕ with A∪B=ℕ and A∩B={8k:k∈ℕ} such that R2(A,n)=R2(B,n) for all n≥n0. Without loss of generality, we may assume that n0=16N-1, N is a positive integer; then there exists a polynomial p(x) of degree at most 16N-2 such that
(3)∑n=0∞(R2(A,n)-R2(B,n))xn=p(x).
Let
(4)f(x)=∑a∈Axa,g(x)=∑b∈Bxb,εi={1,i∈A,0,i∉A.
Then we have
(5)f(x)=∑a∈Axa=∑i=0∞εixi,∑n=0∞R2(A,n)xn=12(f2(x)-f(x2)).
Moreover,
(6)g(x)=∑b∈Bxb=∑b∈(ℕ∖A)∪(A∩B)xb=∑n=0∞xn-f(x)+∑k=0∞x8k=11-x+11-x8-f(x),∑n=0∞‍R2(B,n)xn=12(g2(x)-g(x2))=12((11-x+11-x8-f(x))2-(11-x2+11-x16-f(x2)))=x(1-x)(1-x2)+x8(1-x8)(1-x16)+1(1-x)(1-x8)-f(x)1-x-f(x)1-x8+12f2(x)+12f(x2).
Therefore,
(7)∑n=0∞(R2(A,n)-R2(B,n))xn=f(x)1-x+f(x)1-x8-f(x2)-x(1-x)(1-x2)-x8(1-x8)(1-x16)-1(1-x)(1-x8).
Write(8)p(x)(1-x8)=∑i=016N+6αixi.
By (3) and (7), we have
(9)(∑i=07‍xi+1)f(x)=(1-x8)f(x2)+1+x+x3+x5+x71-x+x81-x16+p(x)(1-x8).
Writing both sides of (9) in power series, then we have
(10)∑i=0∞‍2εixi+∑i=0∞‍εixi+1+⋯+∑i=0∞‍εixi+7=∑i=0∞‍εix2i-∑i=0∞‍εix2i+8+∑i=0∞‍xi+∑i=0∞‍xi+1+∑i=0∞‍xi+3+∑i=0∞‍xi+5+∑i=0∞‍xi+7+∑i=0∞‍x16i+8+∑i=016N+6‍αixi.
Comparing the coefficients ofx16N+t,t=7,9,11,13,15,17,19,21,23,25 on the both sides of (10), we have
(11)2ε16N+t+ε16N+t-1+⋯+ε16N+t-7=5,t=7,9,…,25.
Then we have
(12)2ε16N+7+ε16N+6+⋯+ε16N=5,(13)2ε16N+9=ε16N+7+ε16N+1,(14)2ε16N+11+ε16N+10=ε16N+9+ε16N+3+ε16N+2,(15)2ε16N+13+ε16N+12=ε16N+11+ε16N+5+ε16N+4,(16)2ε16N+15+ε16N+14=ε16N+13+ε16N+7+ε16N+6,(17)2ε16N+17=ε16N+15+ε16N+9,(18)2ε16N+19+ε16N+18=ε16N+17+ε16N+11+ε16N+10,(19)2ε16N+21+ε16N+20=ε16N+19+ε16N+13+ε16N+12,(20)2ε16N+23+ε16N+22=ε16N+21+ε16N+15+ε16N+14,(21)2ε16N+25=ε16N+23+ε16N+17.
Since A∩B={8k:k∈ℕ}, we have ε16N+m=1,m=0,8,16,24. Then, by (12), (ε16N+1,ε16N+2,ε16N+3,ε16N+4,ε16N+5,ε16N+6,ε16N+7) has the following 30 cases:
(22)(0,0,0,0,1,1,1),(0,0,0,1,0,1,1),(0,0,0,1,1,0,1),(0,0,1,0,0,1,1),(0,0,1,0,1,0,1),(0,0,1,1,0,0,1),(0,0,1,1,1,1,0),(0,1,0,0,0,1,1),(0,1,0,0,1,0,1),(0,1,0,1,0,0,1),(0,1,0,1,1,1,0),(0,1,1,0,0,0,1),(0,1,1,0,1,1,0),(0,1,1,1,0,1,0),(0,1,1,1,1,0,0),(1,0,0,0,0,1,1),(1,0,0,0,1,0,1),(1,0,0,1,0,0,1),(1,0,0,1,1,1,0),(1,0,1,0,0,0,1),(1,0,1,0,1,1,0),(1,0,1,1,0,1,0),(1,0,1,1,1,0,0),(1,1,0,0,0,0,1),(1,1,0,0,1,1,0),(1,1,0,1,0,1,0),(1,1,0,1,1,0,0),(1,1,1,0,0,1,0),(1,1,1,0,1,0,0),(1,1,1,1,0,0,0).
By (13), we have
(23)ε16N+9=ε16N+7=ε16N+1=0,
or
(24)ε16N+9=ε16N+7=ε16N+1=1.
Thus (ε16N+2,ε16N+3,ε16N+4,ε16N+5,ε16N+6,ε16N+7,ε16N+9) has the following 10 cases:
(25)(0,1,1,1,1,0,0),(1,0,1,1,1,0,0),(1,1,0,1,1,0,0),(1,1,1,0,1,0,0),(1,1,1,1,0,0,0),(0,0,0,0,1,1,1),(0,0,0,1,0,1,1),(0,0,1,0,0,1,1),(0,1,0,0,0,1,1),(1,0,0,0,0,1,1).
By (14) and (25), we have (ε16N+4,ε16N+5,ε16N+6,ε16N+7,ε16N+9,ε16N+10,ε16N+11) which has the following 8 cases:
(26)(1,1,1,0,0,1,0),(0,1,1,0,0,0,1),(1,0,1,0,0,0,1),(1,1,0,0,0,0,1),(0,0,1,1,1,1,0),(0,1,0,1,1,1,0),(1,0,0,1,1,1,0),(0,0,0,1,1,0,1).
By (15) and (26), we have (ε16N+6,ε16N+7,ε16N+9,ε16N+10,ε16N+11,ε16N+12,ε16N+13) which has the following 6 cases:
(27)(1,0,0,1,0,0,1),(1,0,0,0,1,0,1),(0,0,0,0,1,1,1),(1,1,1,1,0,0,0),(0,1,1,1,0,1,0),(0,1,1,0,1,1,0).
By (16) and (27), we have (ε16N+9,ε16N+10,ε16N+11,ε16N+12,ε16N+13,ε16N+14,ε16N+15) which has the following 6 cases:
(28)(0,1,0,0,1,0,1),(0,0,1,0,1,0,1),(0,0,1,1,1,1,0),(1,1,0,0,0,0,1),(1,1,0,1,0,1,0),(1,0,1,1,0,1,0).
By (17) and (28), we have (ε16N+10,ε16N+11,ε16N+12,ε16N+13,ε16N+14,ε16N+15,ε16N+17) which has the following 2 cases:
(29)(0,1,1,1,1,0,0),(1,0,0,0,0,1,1).
By (18) and (29), we have (ε16N+12,ε16N+13,ε16N+14,ε16N+15,ε16N+17,ε16N+18,ε16N+19) which has the following 2 cases:
(30)(1,1,1,0,0,1,0),(0,0,0,1,1,0,1).
By (19) and (30), we have (ε16N+14,ε16N+15,ε16N+17,ε16N+18,ε16N+19,ε16N+20,ε16N+21) which has the following 2 cases:
(31)(1,0,0,1,0,0,1),(0,1,1,0,1,1,0).
By (20) and (31), we have (ε16N+17,ε16N+18,ε16N+19,ε16N+20,ε16N+21,ε16N+22,ε16N+23) which has the following 2 cases:
(32)(0,1,0,0,1,0,1),(1,0,1,1,0,1,0).
By (21), we have
(33)ε16N+25=ε16N+23=ε16N+17=0,
or
(34)ε16N+25=ε16N+23=ε16N+17=1,
which contradicts (32).
This completes the proof of Theorem1.


## 3. Proof of Theorem2

Proof.
Suppose that there exist integern0 and sets A,B⊂ℕ with A∪B=ℕ and A∩B={8k:k∈ℕ} such that R3(A,n)=R3(B,n) for all n≥n0. Without loss of generality, we may assume that n0=16N-1, N is a positive integer then there exists a polynomial q(x) of degree at most 16N-2 such that
(35)∑n=0∞(R3(A,n)-R3(B,n))xn=q(x).
Definef(x),g(x), and εi as in the proof of Theorem 1. Then we have
(36)∑n=0∞R3(A,n)xn=12(f2(x)+f(x2)),∑n=0∞‍R3(B,n)xn=12(g2(x)+g(x2))=12((11-x+11-x8-f(x))2+(11-x2+11-x16-f(x2)))=1(1-x)(1-x2)+1(1-x8)(1-x16)+1(1-x)(1-x8)-f(x)1-x-f(x)1-x8+12f2(x)-12f(x2).
Therefore,
(37)∑n=0∞‍(R3(A,n)-R3(B,n))xn=f(x)1-x+f(x)1-x8+f(x2)-1(1-x)(1-x2)-1(1-x8)(1-x16)-1(1-x)(1-x8).
Write(38)q(x)(1-x8)=∑i=016N+6βixi.
By (35) and (37), we have
(39)(∑i=07‍xi+1)f(x)=(x8-1)f(x2)+2+x2+x4+x61-x+11-x16+q(x)(1-x8).
We write both sides of (39) in power series; then we have
(40)∑i=0∞‍2εixi+∑i=0∞‍εixi+1+⋯+∑i=0∞‍εixi+7=∑i=0∞‍εix2i+8-∑i=0∞‍εix2i+∑i=0∞‍2xi+∑i=0∞‍xi+2+∑i=0∞‍xi+4+∑i=0∞‍xi+6+∑i=0∞‍x16i+∑i=016N+6‍βixi.
Comparing the coefficients ofx16N+t,t=7,9,11,13,15,17,19,21,23,25 on the both sides of (40), we have
(41)2ε16N+t+ε16N+t-1+⋯+ε16N+t-7=5,t=7,9,…,25.
The remainder of the proof is the same as that of the proof of Theorem1. We omit it here.



---

*Source: 979487-2012-12-19.xml*