# On OptimalM-Sets Related to Motzkin’s Problem

Authors: Quan-Hui Yang; Ting Pan; Jian-Dong Wu
Journal: Journal of Mathematics
 (2020)

---

## Abstract

LetM be a set of positive integers. A set S of nonnegative integers is called an M‐set if aandb∈S, then a−b∉M. If S⊆0,1,…,n is an M−set with the maximal cardinality, then S is called a maximal M−set of 0,1,…,n. If S∩0,1,…,n is a maximal M−set of 0,1,…,n for all integers n≥0, then we call S an optimal M−set. In this paper, we study the existence of an optimal M−set.


---

## Body

## 1. Introduction

Letℕ be the set of all nonnegative integers. For a positive real number x and S⊆ℕ, we denote by Sx the number of elements n∈S such that n≤x. The upper and lower densities of S denoted by δ¯S and δ¯S, respectively, are given by(1)δ¯S≔limx⟶∞supSxx,δ¯S≔limx⟶∞infSxx.If δ¯S=δ¯S, let δS=δ¯S=δ¯S, then we say that S has density δS.Given a setM of positive integers, we call S⊆ℕ an M‐set if a∈Sandb∈S, then a−b∉M. Motzkin [1] presented the problem of determining the quantity(2)μM≔supSδ¯S,where the supremum is taken over all M‐sets S. Cantor and Gordon [2] proved that if M=1, μM=1/2 and that if M=m1,m2, then μM=m1+m2/2/m1+m2. Later, Haralambis [3] determined μM for many members of the families 1,j,k and 1,2,j,k. In 1999, Gupta and Tripathi [4] completely determined μM when M is a finite arithmetic progression. In 2011, Pandey and Tripathi [5] investigated this quantity when M is related to an arithmetic progression. After that, Pandey and Tripathi [6] and the first author and Tang [7] determined μM when M is a geometric progression. For other results, one may refer to [8–11].In 2010, Chen and Yang [12] and Khovanova and Konyagin [13] studied the upper density among sets of nonnegative integers in which no two elements have quotient belonging to M.SupposeG is a graph and T is a set of nonnegative integers. A T−coloring of G is an assignment of a positive integer fx to each vertex x of G so that if x and y are joined by an edge of G, then fx−fy is not in T. T‐colorings were introduced by Hale [14] in connection with the channel assignment problem in communications. Motzkin’s problem has connections with the T‐colouring problem. For more results on this topic, one can refer to [15–19].Motzkin’s problem also has connections with some other problems, such as problems related to the fractional chromatic number of distance graphs and the Lonely Runner Conjecture. One can refer to [9, 20–29].In this paper, for any integersa and b, we define a,b=a≤n≤b:n∈ℤ. For an M‐set S⊆0,n, if S≥S′ for any M‐set S′⊆0,n, then S is said to be a maximal M‐set of 0,n. If S∩0,n is a maximal M‐set of 0,n for all integers n≥0, then we call S an optimal M‐set. If M is finite, then an optimal M‐set is infinite. For a finite set M, let GM be the infinite sequence 0,a1,a2,… recursively by choosing ak+1 to be the least integer exceeding ak such that 0,a1,a2,…,ak+1 is also an M‐set. It is easy to see that, for a given set M, if there exists an optimal M−set, then this set must be GM.In this paper, we determine all the optimalM−set when M≤2.Theorem 1.
For any setM with M=1, there exists an optimal M−set.Theorem 2.
LetM=m1,m2, where m1<m2, and let gcdm1,m2=d. Then, there exists an optimal M−set if and only if m1|m2 or m2=km1±d with an odd k.Remark 1.
By Theorem2, we know that there exists an optimal M−set when m1=2.


## 2. Proofs of Theorem 1

Before presenting the proof of Theorem 1, we first give some lemmas here. Lemma1 is a small generalization of Corollary 1, which is used by Cantor and Gordon in [2].Lemma 1.
LetM1=m1,m2,… and M2=dm1,dm2,…, where d is a positive integer. For any M1−sets S0,S1,…,Sd−1,(3)S=∪i=0d−1da+i:a∈Si,is an M2−set. Conversely, for any M2−set T and i∈0,1,…,d−1,(4)Ti=a−id:a∈T,a≡imodd,is an M1−set.Proof.
Suppose that there exist two elementsu,v∈S such that u−v=dmi for some positive integer i. Let u=da+i and v=db+j with a,b∈Sj and 0≤i,j≤d−1. Then, by d|u−v, we obtain i=j. Hence, a,b∈Si and a−b=mi∈M1. This contradicts that Si is an M1−set.
Conversely, suppose that there exists an integeri with 0≤i≤d−1 such that Ti is not an M1−set. Then, there exist x,y∈Ti such that x−y=mi for some positive integer i. Let x=m−i/d,y=n−i/d, where mandn∈T. Then, m−n=dmi∈M2. This contradicts that T is an M2−set.Corollary 1.
LetM1=m1,m2,… and M2=dm1,dm2,…, where d is a positive integer. For any M1−sets S, the set ∪i=0d−1da+i:a∈S is an M2−set.
Corollary 1 follows from Lemma1 immediately by taking S0=S1=⋯=Sd−1=S.For two setsA and B and an integer d, let A+B=a+b:a∈A,b∈B, A−B=a−b:a∈A,b∈B,d⋅A=da:a∈A,andd+A=d+a:a∈A.Lemma 2.
LetM1=m1,m2,… and M2=dm1,dm2,…, where d is a positive integer. Then, GM1 is an optimal M1−set if and only if GM2 is an optimal M2−set.Proof.
We first prove the relationship betweenGM1 and GM2, i.e.,(5)GM2=d⋅GM1+D,where,D=0,1,…,d−1.
Suppose that equality (5) does not hold. Let n be the smallest integer such that GM2∩0,n≠d⋅GM1+D∩0,n. For any integer m≤n, let m=qmd+rm, where 0≤rm≤d−1. Then, n∈GM2 is equivalent to n−m∉M2 for all m<n and m∈GM2. If rm≠rn, then n−m∉M2 must hold. Hence, we only need to consider the case rm=rn. So, n∈GM2 is equivalent to qn−qm∉M1 for all integers qm with qm<qn and qm∈GM1, that is, qn∈GM1. Hence, n∈GM2 is equivalent to n∈d⋅GM1+D, a contradiction.
Now, we shall proveGM1 is an optimal M1−set if and only if GM2 is an optimal M2−set.
Suppose thatGM2 is an optimal M2−set. If GM1 is not an optimal M1−set, then there exists an integer n1 and an M1−set S1⊆0,n1 such that S1>GM1∩0,n1. Let S2=d⋅S1+D. Then, S2⊆0,dn1+d−1. By (5), we have S2>GM2∩0,dn1+d−1. By Lemma 1, S2 is an M2−set. Thus, GM2 is not an optimal M2−set.
Now, suppose thatGM1 is an optimal M1−set. If GM2 is not an optimal M2−set, then there exists an integer n2 and an M2−set S2⊆0,n2 such that S2>GM2∩0,n2.
Suppose thatn2∈GM2. Let n2′ be the maximal integer such that n2′≤n2 and n2′≡d−1modd. Then, by (5), we have n2′+1,n2⊆GM2. Thus,(6)S2∩0,n2′>GM2∩0,n2′.
Suppose thatn2∉GM2. Let n2〞 be the minimal integer such that n2〞≥n2 and n2〞≡d−1modd. Then, by (5), we have n2,n2〞∩GM2=ϕ. Thus,(7)S2∩0,n2″>GM2∩0,n2″.
Hence, without loss of generality, we may assumen2≡d−1modd. By (5), we have(8)GM2∩0,n2=d⋅GM1∩0,n2−d+1d+D.
For0≤i≤d−1, let Ti=a−i/d:a∈S2,a≡imodd. Then, Ti⊆0,n2−d+1/d. Since S2>GM2∩0,n2, by (8), there exists an integer i0 with 0≤i0≤d−1 such that Ti0>GM1∩0,n2−d+1/d. By Lemma 1, Ti0 is an M1−set. Thus, GM1 is not an optimal M1−set.
Therefore,GM1 is an optimal M1−set if and only if GM2 is an optimal M2−set.
Proof of Theorem1: it suffices to prove that GM is an optimal M−set when M=1. By Lemma 2, we may assume that M=1. Clearly, GM is the set of all even numbers. Since any M−set S contains no consecutive integers, it follows that GM is an optimal M−set.


## 3. Proofs of Theorem 2

In order to prove Theorem2, we first prepare some lemmas. Let xm denote the absolute value of the absolutely least remainder of x(modm). The proof of Lemma 3 follows proofs of Theorem 1 and Theorem 4 (ii) in [2]. For the convenience of the reader, we present it here.Lemma 3.
(see [2], Theorem 1 and Theorem 4 (ii)). Let M=m1,m2, where gcdm1+m2=1 and 2|m1+m2. Then, there exists an M−set S⊆0,m1+m2−1 such that S=m1+m2−1/2.Proof.
Bygcdm1+m2=1 and 2|m1+m2, we have gcdm2−m1,m1+m2=1, and then there exists c such that cm2−m1≡1modm1+m2. Thus, cm2−cm1≡1modm1+m2. Noting that cm2+cm1≡0modm1+m2, we obtain 2cm2≡1modm1+m2 and 2cm1≡−1modm1+m2. Hence, 2cm1≡−2cm2≡−1≡m1+m2−1modm1+m2, and then,(9)cm1≡−cm2≡m1+m2−12modm1+m2.
Let(10)S=∪r=0m1+m2−1/2−1n∈ℤ:0≤n≤m1+m2−1,cn≡rmodm1+m2.
Then,S⊆0,m1+m2−1 and S=m1+m2−1/2. Next, we shall prove that S is an M−set. That is, if aandb∈S, then a−b∉M. We obtain ca=q1m1+m2+r1andcb=q2m1+m2+r2, where 0≤r1,r2<m1+m2−1/2. Then, if a−b∈M, we have(11)ca−b=q1−q2m1+m2+r1−r2=cm1orcm2.
It follows thatr1−r2≡cm1 or cm2modm1+m2. However, by 0≤r1,r2<m1+m2−1/2 and (9), we have(12)r1−r2<m1+m2−12=cm1m1+m2=cm2m1+m2,a contradiction.
In the next lemma, we study the period ofGM.Lemma 4.
LetM=m1,m2. Then, GM is periodic with period m1+m2.Proof.
We shall prove thatn∈GM if and only if n+m1+m2∈GM for all n≥0.
Ifn∈GM, then n+m1andn+m2∉GM. By the definition of GM, we have n+m1+m2∈GM.
Ifn∉GM, then we shall prove n+m1+m2∉GM. Suppose that n+m1+m2∈GM. Then, n+m1andn+m2∉GM. If n+m2−m1∉GM, by n∉GM and the definition of GM, we have n+m2∈GM, a contradiction. Thus, we have n+m2−m1∈GM, and then n−m1∉GM. Similarly, we also have n+m1−m2∈GM and n−m2∉GM. Since n−m1∉GM and n−m2∉GM, by the definition of GM, it follows that n∈GM, a contradiction. Hence, n+m1+m2∉GM.
Therefore,GM is a periodic set with period m1+m2.
In 2012, the authors of [30] study the difference sets containing integer powers. Lemma 5 is the main theorem in [30], which is used to prove Lemma 6.Lemma 5.
(see [30], Theorem 1). Let n>m≥2 be positive integers and n=m+1l+r, where 0≤r≤m. Let(13)τm,n=n2+1,ifmis odd,ml2+δ,ifmis even,where δ denotes the cardinality of even numbers in the interval 0,minr,m−2. Then, we have the following:(i)
IfC is a subset of 0,n with C>τm,n, then C−C contains either 1 or m(ii)
There exists a subsetC of 0,n with C=τm,n such that C−C contains no power of mLemma 6.
LetM=1,m2. Then, GM is an optimal M−set.Proof.
It is easy to see that, ifm2 is odd, then GM is the set of all even integers; if m2 is even, then(14)GM=∪k=0∞Ak,whereAk=km2+1+2⋅0,m22−1.
Hence,GM∩0,n=τm2,n. By Lemma 5 (i), there is no set C⊆0,n such that C>GM∩0,n and C is also an M−set. Hence, GM is an optimal M−set.
Proof of Theorem2: it suffices for us to determine M such that GM is an optimal M−set. By Lemma 2, we may assume d=1. If m1=1, by Lemma 6, then GM is an optimal M−set. Now, we suppose that m1>1. Noting that m1,m2=1, we write m2=km1+r, where 1≤r≤m1−1. If k is odd, then(15)GM∩0,m1+m2−1=∪j=0k−1/22jm1+s:0≤s≤m1−1,and so GM∩0,m1+m2−1=k+1m1/2. If k is even, then(16)GM∩0,m1+m2−1=∪j=0k/2−12jm1+s:0≤s≤m1−1∪km1,km1+r−1.
It follows thatGM∩0,m1+m2−1=km1/2+r.Case 1.
2|m1,2|m2. Let M′ be the set of all even numbers contained in 0,m1+m2−1. Clearly, M′ is an M−set and M′=m1+m2/2. Since m1+m2/2>k+1m1/2 and m1+m2/2>km1/2+r, we have M′>GM∩0,m1+m2−1. Hence, GM is not an optimal M−set.Case 2.
2|m1+m2. By Lemma 3, there exists an M−set S⊆0,m1+m2−1 such that S=m1+m2−1/2. It is easy to check that S>GM∩0,m1+m2−1 except for the following two cases: (a) k is odd and r=1 and (b) k is even and r=m1−1. Hence, GM is not an optimal M−set except for these two cases.
Now, we shall prove thatGM is an optimal M−set in cases (a) and (b). By Lemma 4, GM is periodic with period m1+m2. Hence, it suffices for us to prove that GM∩0,n is a maximal M−set of 0,n for any integer n∈0,m1+m2−1.Subcase 1:k is odd and r=1. Then, m2=km1+1. Suppose that T⊆0,m1+m2−1 is an M−set. Noting that m1∈M, we have(17)T∩2jm1+i,2j+1m1+i≤1,for all integersi,j with 0≤i≤m1−1 and 0≤j≤k−1/2. Since(18)2jm1+i:0≤i≤m1−1,0≤j≤k−12⊆GM.It follows thatGM∩0,n is a maximal M−set of 0,n for all n≤k+1m1−1.Now, we consider the casen=k+1m1=m1+m2−1. If T>GM∩0,m1+m2−1, then we have k+1m1∈T and(19)T∩2jm1+i,2j+1m1+i=1,for all integersi,j with 0≤i≤m1−1 and 0≤j≤k−1/2. Hence,(20)k+1m1∈T⇒m2∈Mm1−1∉T⇒3.22m1−1∈T⇒3.2⋯⇒3.2k+1m1−1∈T⇒m2∈Mm1−2∉T⇒3.22m1−2∈T⇒3.2⋯⇒3.2k+1m1−2∈T.Similarly, we havek+1m1−3,k+1m1−4,…,km1⊆T. On the other hand, by k+1m1∈T and m1∈M, we have km1∉T, a contradiction. Thus, GM is an optimal M−set in this case.Subcase 2:k is even and r=m1−1. Then, m2=k+1m1−1. Suppose that T′⊆0,m1+m2−1 is an M−set. By m1∈M, we have(21)T′∩2jm1+i,2j+1m1+i≤1,for all integers i,jwith 0≤i≤m1−1 and 0≤j≤k/2−1. However,(22)∪j=0k/2−12jm1+s:0≤s≤m1−1∪km1,m2−1⊆GM.
It follows thatGM∩0,n is a maximal M−set of 0,n for all n≤m2−1.
Now, we consider the casem2≤n≤m1+m2−1. If GM∩0,m1+m2−1 is a maximal M−set of 0,m1+m2−1, by n+1,m1+m2−1∩GM=ϕ, then GM∩0,n is a maximal M−set of 0,n. Hence, it is enough for us to prove GM∩0,m1+m2−1 is a maximal M−set of 0,m1+m2−1. If T′>GM∩0,m1+m2−1, then we have(23)T′∩2jm1+i,2j+1m1+i=1,for all integers i,j with 0≤i≤m1−1 and 0≤j≤k/2. In particular, k+1m1−1∈T′, since k+2m1−1=m1+m2∉T′. Hence,(24)k+1m1−1∈T′⇒m2∈M0∉T′⇒3.3m1∈T′⇒3.3...⇒3.3km1∉T′⇒3.3k+1m1∈T′⇒m2∈M1∉T′⇒3.3...⇒3.3km1+1∉T′.
Similarly, we obtainkm1+2,k+1m1−1∩T′=ϕ. It is a contradiction with k+1m1−1∈T′. Hence, GM is also an optimal M−set in this case.
Therefore,GM is an optimal M−set if and only if m1=1 or m2=km1±1, where k is odd.
At the end of this paper, we pose a problem for further research.Problem 1.
Given an integerk≥3, determine all sets M with M=k such that there exists an optimal M−set.Remark 2.
IfGM is optimal, then GM gives the value of μM. If GM is not optimal, we cannot find any information about the value of μM. Thus, Problem 1 and Motzkin’s problem are incomparable.



---

*Source: 7457625-2020-12-28.xml*