A Note on a Problem of Motzkin Regarding Density of Integral Sets with Missing

Differences

Ram Krishna Pandey^{1} Department of Mathematics Indian Institute of Technology Patliputra Colony, Patna – 800013 India

                    ram@iitp.ac.in

Amitabha Tripathi^{2} Department of Mathematics Indian Institute of Technology Hauz Khas, New Delhi – 110016 India

               atripath@maths.iitd.ac.in

Abstract

For a given set M of positive integers, a problem of Motzkin asks to determine the maximal density μ(M) among sets of nonnegative integers in which no two elements differ by an element of M. The problem is completely settled when |M| ≤ 2, and some partial results are known for several families of M when |M| ≥ 3. In 1985 Rabinowitz & Proulx provided a lower bound for μ({a, b, a + b}) and conjectured that their bound was sharp. Liu & Zhu proved this conjecture in 2004. For each n ≥ 1, we determine κ({a, b, n(a + b)}), which is a lower bound for μ({a, b, n(a + b)}), and conjecture this to be the exact value of μ({a, b, n(a + b)}).

1 Introduction

For x ∈ ℝ and a set S of nonnegative integers, let S(x) denote the number of elements n ∈ S such that n ≤ x. The upper and lower densities of S, denoted by \overline{δ}(S) and \underline{δ}(S) respectively, are given by

\overline{δ}(S) := lim sup_{x→∞} \frac{S(x)}{x}, \underline{δ}(S) := lim inf_{x→∞} \frac{S(x)}{x}.

If \overline{δ}(S) = \underline{δ}(S), we denote the common value by δ(S), and say that S has density δ(S). Given a set of positive integers M, S is said to be an M-set if a ∈ S, b ∈ S imply a − b ∉ M. Motzkin [15] asked to determine μ(M) given by

μ(M) := sup_{S} \overline{δ}(S)

where S varies over all M-sets. Cantor & Gordon [3] showed the existence of μ(M) for any M, determined μ(M) when |M| ≤ 2, and gave the following lower bound for μ(M):

μ(M) ≥ κ(M) := sup_{gcd(c,m)=1} \frac{1}{m} min_{i} |cm_{i}|_{m},  (1)

where m_{i} are the elements of M, and |x|_{m} denotes the absolute value of the absolutely least remainder of x modulo m. We use the following equivalent form for the lower bound for μ(M), due to Haralambis [11]:

κ(M) = max_{1≤k≤ \frac{m}{2}^{m=m_{i}+m_{j}}} \frac{1}{m} min_{m_{i}∈M} |km_{i}|_{m},  (2)

where m_{i}, m_{j} represent distinct elements of M. The following useful upper bound for μ(M) is due to Haralambis [11]:

μ(M) ≤ α  (3)

provided there exists a positive integer k such that S(k) ≤ (k + 1)α for every M-set S with 0 ∈ S and for some α ∈ [0, 1]. The problem of Motzkin has a rich and diverse history but little progress towards the general problem has been made so far. Exact results for μ(M) have been few, and computation of μ(M) has only been completely possible when |M| ≤ 2. Cantor & Gordon [3] showed that

μ(\{m\}) = \frac{1}{2}, μ(\{m_{1}, m_{2}\}) = \frac{⌊(m_{1} + m_{2})/2⌋}{m_{1} + m_{2}}.

There have, however, been a number of results that give the exact value or bounds for μ(M) in other cases; see [13] for an exhaustive bibliography.

Connections with coloring problems in graph theory have been found useful in solving the Motzkin problem. One such connection, introduced by Hale [10] and shown to be equivalent to the Motzkin problem by Griggs & Liu [9], is the T -coloring problem. Another connection with colorings of graphs involves the fractional chromatic number of distance graphs.

The lower bound for μ(M), denoted by κ(M) in (1), is itself at the heart of a longstanding conjecture. The Lonely Runner Conjecture (LRC) stated independently by Wills [17] in the context of diophantine approximations and by Cusick [7] while studying view obstructions problems in n-dimensional geometry, was actually given this apt name by Bienia et al [1].

Chen [6] characterized 3-sets M for which 1/κ(M) is an integer and also obtained general bounds.

We consider the problem of determining μ(M) for the family M = {a, b, n(a+b)}, n ≥ 1. By a result of Cantor & Gordon [3], we know that μ(kM) = μ(M). Thus, it is no loss of generality to assume that gcd(a, b) = 1, and that a < b. We determine the value of κ(M), which is the lower bound for μ(M) and conjecturally equal to it. This extends a result of Liu & Zhu [[13], Theorem 5.1], wherein they determined μ(M) in the case M = {a, b, a + b}. Rabinowitz & Proulx [16] provided a lower bound for μ(M) in this case and conjectured that their bound was sharp. An extensive list of work related to the Motzkin problem may be found in [13].

2 Main Result

For the set M = {a, b, a + b}, Rabinowitz & Proulx [16] conjectured the exact value of μ(M) in 1985, and Liu & Zhu [13] proved this conjecture in 2004. We determine κ(M) for M = {a, b, n(a + b)} where n is a fixed positive integer. If the conjecture of Haralambis [11] is true, then κ(M) = μ(M) in this case, thus providing a generalization of the result of Liu & Zhu.

Theorem 1. Let M = {a, b, n(a + b)}, where a < b, gcd(a, b) = 1 and n ≥ 1. Then

κ(M) = \begin{cases}\frac{n(a+b−λ)}{2(a+n(a+b))}, & if λ ≡ a + b (mod 2); \\ \frac{n(a+b+λ−1)}{2(b+n(a+b))}, & if λ ≢ a + b (mod 2), \end{cases}

where λ = 1 + ⌊\frac{b−a}{2n+1}⌋.

Proof. We use (2) to compute κ(M). The choice m = a+b trivially yields min {|ax|_{m}, |bx|_{m}, |n(a+ b)x|_{m}} = 0 for each x. There are two choices remaining for m, and we determine κ(M) by comparing the two rational numbers corresponding to these cases. In each of the two cases we need to compute κ(M) with m = a + n(a + b) and m = b + n(a + b), and compare the two. Note that the definition of λ implies

b − a < (2n + 1)λ ≤ b − a + 2n + 1.

Case I: (λ ≡ a + b (mod 2))

Subcase (i): (m = a + n(a + b)) Choose x such that

(a + b)x ≡ \frac{a+b−λ}{2} (mod m).

Then

−ax ≡ n(a + b)x ≡ n\frac{a+b−λ}{2} ≡ \frac{m−(a+nλ)}{2} (mod m),

and

bx = (a + b)x − ax ≡ \frac{m+\{b−(n+1)λ\}}{2} (mod m).

Therefore

min \{|ax|_{m}, |bx|_{m}, |n(a + b)x|_{m}\} = \frac{m−(a+nλ)}{2}  (4)

since b − (n + 1)λ < a + nλ if and only if (2n + 1)λ > b − a.

Write ℓ := a + nλ. We show that

min \{|ay|_{m}, |by|_{m}, |n(a + b)y|_{m}\} ≤ \frac{m−(a+nλ)}{2} = \frac{m}{2} − \frac{ℓ}{2}

for each y, 1 ≤ y ≤ \frac{m}{2}. Let ℐ := (\frac{m}{2} − \frac{ℓ}{2}, \frac{m}{2} + \frac{ℓ}{2}). We show that −ay mod m ∈ ℐ and by mod m ∈ ℐ is simultaneously impossible for 1 ≤ y ≤ \frac{m}{2}. Suppose

(a + b)y ≡ \frac{a+b−λ}{2} + i (mod m),

with 1 ≤ i ≤ m − 1. Then

− ay ≡ n(a + b)y ≡ \frac{m}{2} − \frac{ℓ}{2} + ni (mod m),  (5)
by ≡ (a + b)y − ay ≡ \frac{m}{2} − \frac{ℓ}{2} + \frac{a+b−λ}{2} + (n + 1)i (mod m)

Thus −ay mod m ∈ ℐ if and only if

km + \frac{m}{2} − \frac{ℓ}{2} < \frac{m}{2} − \frac{ℓ}{2} + ni < km + \frac{m}{2} + \frac{ℓ}{2}

for some integer k, with 0 ≤ k ≤ n − 1. This is equivalent to

k \frac{m}{n} < i < k \frac{m}{n} + \frac{ℓ}{n},

so that

k(a + b) + 1 ≤ i ≤ k(a + b) + a + λ − 1.  (6)

For k(a + b) + 1 ≤ i ≤ k(a + b) + a + λ − 1, we show that

km + \frac{m}{2} + \frac{ℓ}{2} < \frac{m}{2} − \frac{ℓ}{2} + \frac{a+b−λ}{2} + (n + 1)\{k(a + b) + 1\}

and

\frac{m}{2} − \frac{ℓ}{2} + \frac{a+b−λ}{2} + (n + 1)\{k(a + b) + a + λ − 1\} < (k + 1)m + \frac{m}{2} − \frac{ℓ}{2}.

This will prove that

km + \frac{m}{2} + \frac{ℓ}{2} < by < (k + 1)m + \frac{m}{2} − \frac{ℓ}{2},

so that by mod m ∉ ℐ, as claimed. Each of the above two inequalities is easy to prove. Using the fact that (n + 1)(a + b) = m + b, each inequality can be shown to hold if (2n + 1)λ < (b − a) + 2(n + 1), which is true by the definition of λ. This completes the subcase when m = a + n(a + b).

Subcase (ii): (m = b + n(a + b)) The argument in this subcase is similar to the one in subcase (i). We omit the calculation and state only the significant parts. Choose x such that

(a + b)x ≡ \frac{a+b+λ}{2} (mod m).

Then

−bx ≡ n(a + b)x ≡ \frac{m−(b−nλ)}{2} (mod m),

and

ax = (a + b)x − bx ≡ −\frac{m−\{a+(n+1)λ\}}{2} (mod m).

Therefore

min \{|ax|_{m}, |bx|_{m}, |n(a + b)x|_{m}\} = \frac{m−\{(a+(n+1)λ\}}{2}  (7)

since b − nλ < a + (n + 1)λ if and only if (2n + 1)λ > b − a. As in subcase (i), we may show that

min \{|ay|_{m}, |by|_{m}, |n(a + b)y|_{m}\} ≤ \frac{m−\{a+(n+1)λ\}}{2}

for each y, 1 ≤ y ≤ \frac{m}{2}. The argument is similar and we omit the proof. This completes subcase (ii). To compute κ(M) in Case I, we need to compare the expressions in (4) and (7). If we let m_{1} = a + n(a + b) and m_{2} = b + n(a + b), then a lengthy but easy computation shows that

\frac{m_{2}−\{(a+(n+1)λ\}}{2m_{2}} = \frac{1}{2} − \frac{1}{2} \frac{a+(n+1)λ}{b+n(a+b)} < \frac{1}{2} − \frac{1}{2} \frac{a+nλ}{a+n(a+b)} = \frac{m_{1}−(a+nλ)}{2m_{1}}

if and only if (2n + 1)λ > b − a. This completes the proof of Case I. Case II: (λ ≢ a + b (mod 2)) Subcase (i): (m = a + n(a + b)) Choose x such that

(a + b)x ≡ \frac{a+b−λ+1}{2} (mod m).

Then

−ax ≡ n(a + b)x ≡ \frac{m−\{a+n(λ−1)\}}{2} (mod m),

and

bx = (a + b)x − ax ≡ \frac{m+\{b−(n+1)(λ−1)\}}{2} (mod m).

Therefore

min \{|ax|_{m}, |bx|_{m}, |n(a + b)x|_{m}\} = \frac{m−\{b−(n+1)(λ−1)\}}{2}  (8)

since a + n(λ − 1) ≤ b − (n + 1)(λ − 1) if and only if (2n + 1)(λ − 1) ≤ b − a. As in subcase (i) of Case I, we may show that

min \{|ay|_{m}, |by|_{m}, |n(a + b)y|_{m}\} ≤ \frac{m−\{b−(n+1)(λ−1)\}}{2}

for each y, 1 ≤ y ≤ \frac{m}{2}. This completes subcase (i). Subcase (ii): (m = b + n(a + b)) Choose x such that

(a + b)x ≡ \frac{a+b+λ−1}{2} (mod m).

Then

−bx ≡ n(a + b)x ≡ \frac{m−\{b−n(λ−1)\}}{2} (mod m),

and

ax = (a + b)x − bx ≡ \frac{m+\{a+(n+1)(λ−1)\}}{2} (mod m).

Therefore

min \{|ax|_{m}, |bx|_{m}, |n(a + b)x|_{m}\} = \frac{m−\{b−n(λ−1)\}}{2}  (9)

since a + (n + 1)(λ − 1) ≤ b − n(λ − 1) if and only if (2n + 1)(λ − 1) ≤ b − a.

As in subcase (i) of Case I, we may show that

min \{|ay|_{m}, |by|_{m}, |n(a + b)y|_{m}\} ≤ \frac{m−\{b−n(λ−1)\}}{2}

for each y, 1 ≤ y ≤ \frac{m}{2}. This completes subcase (ii).

To compute κ(M) in Case II, we need to compare the expressions in (8) and (9). If we let m_{1} = a + n(a + b) and m_{2} = b + n(a + b), then a lengthy but easy computation shows that

\frac{m_{1}−\{b−(n+1)(λ−1)\}}{2m_{1}} = \frac{1}{2} − \frac{1}{2} \frac{b−(n+1)(λ−1)}{a+n(a+b)} ≤ \frac{1}{2} − \frac{1}{2} \frac{b−n(λ−1)}{b+n(a+b)} = \frac{m_{2}−\{b−n(λ−1)\}}{2m_{2}}

if and only if (2n + 1)(λ − 1) ≤ b − a. This completes the proof of Case II, and of the theorem.

Corollary 2. (Liu & Zhu [13])

Let M = {a, b, a + b}, where a < b and gcd(a, b) = 1. Then

κ(M) = \begin{cases}\frac{1}{3}, & if b ≡ a (mod 3); \\ \frac{2a+b−1}{3(2a+b)}, & if b ≡ a + 1 (mod 3); \\ \frac{a+2b−1}{3(a+2b)}, & if b ≡ a + 2 (mod 3). \end{cases}

Proof. This is a direct consequence of Theorem 1. Set b − a = 3k + r, where 0 ≤ r ≤ 2. Then λ = k + 1, so that we are in Case I when b ≡ a + 1 (mod 3) and Case II otherwise. The calculation is routine, and the details are omitted.

Remark 3. Haralambis [11] conjectured that μ(M) = κ(M) when |M| = 3. If this is true, Theorem 1 actually determines μ({a, b, n(a+b)}). Observe that, if a, b are of opposite parity and if n ≥ (b − a)/2, Theorem 1 reduces to

κ(\{a, b, n(a + b)\}) = \frac{a + b − 1}{2(a + b) + (2a/n)},

which is asymptotic to μ({a, b}). This may be an indication that the conjecture of Haralambis may hold, at least for the special case M = {a, b, n(a + b)} when n is large enough, and perhaps even for M = {a, b, c} when c is sufficiently large even if not of the form n(a + b).

3 Acknowledgement

The authors wish to thank the referee for his comments.

References

[1] W. Bienia, L. Goddyn, P. Gvozdjak, A. Sebö, and M. Tarsi, Flows, view obstructions and the lonely runner, J. Combin. Theory Ser. B 72 (1998), 1–9.

[2] J. Barajas and O. Serra, The lonely runner with seven runners, Electron. J. Combin. 15 (2008), Research paper 48, 18 pages.

[3] D. G. Cantor and B. Gordon, Sequences of integers with missing differences, J. Combin. Theory Ser. A 14 (1973), 281–287.

[4] G. J. Chang, L. Huang, and X. Zhu, The circular chromatic numbers and the fractional chromatic numbers of distance graphs, European J. Combin. 19 (1998), 423–431.

[5] G. Chang, D. Liu, and X. Zhu, Distance graphs and T -colorings, J. Combin. Theory Ser. B 75 (1999), 159–169.

[6] Y. G. Chen, On a conjecture about diophantine approximations III, J. Number Theory 37 (1991), 181–198.

[7] T. W. Cusick, View-obstruction problems in n-dimensional geometry, J. Combin. Theory Ser. A 16 (1974), 1–11.

[8] R. B. Eggleton, P. Erdős, and D. K. Skilton, Coloring the real line, J. Combin. Theory Ser. B 39 (1985), 86–100.

[9] J. R. Griggs and D.-D. F. Liu, The channel assignment problem for mutually adjacent sites, J. Combin. Theory Ser. A 68 (1994), 169–183.

[10] W. K. Hale, Frequency assignment: theory and applications, Proceedings of the IEEE 68 (1980), 310–320.

[11] N. M. Haralambis, Sets of integers with missing differences, J. Combin. Theory Ser. A 23 (1977), 22–33.

[12] A. Kemnitz and H. Kolberg, Coloring of integer distance graphs, Discrete Math. 191 (1998), 113–123.

[13] D.-D. F. Liu and X. Zhu, Fractional chromatic number for distance graphs with large clique size, J. Graph Theory 47 (2004), 129–146.

[14] D. D.-F. Liu and X. Zhu, Fractional chromatic number of distance graphs generated by two-interval sets, European J. Combin. 29 (7) (2008), 1733–1742.

[15] T. S. Motzkin, Unpublished problem collection.

[16] J. H. Rabinowitz and V. K. Proulx, An asymptotic approach to the channel assignment problem, SIAM J. Alg. Disc. Methods 6 (1985), 507–518.

[17] J. M. Wills, Zwei Sätze uber inhomogene diophantische Approximation von Irrationalzahlen, Monatsh. Math. 71 (1967), 263–269.

2010 Mathematics Subject Classification: Primary 11B05. Keywords: density, coloring.

Received January 6 2011; revised version received May 18 2011. Published in Journal of Integer Sequences, June 1 2011.

Return to Journal of Integer Sequences home page.