\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{mathrsfs} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \def\ul{\underline} \def\imp{\rightarrow} \def\ds{\displaystyle} \def\ts{\textstyle} \def\pr{\prime} \def\lf{\lfloor} \def\rf{\rfloor} \def\lc{\lceil} \def\rc{\rceil} \def\sm{\setminus} \def\A{\mathscr A} \def\I{\mathscr I} \def\N{\mathbb N} \def\R{\mathbb R} \def\S{\mathcal S} \def\Z{\mathbb Z} \def\a{\alpha} \def\d{\delta} \def\k{\kappa} \def\l{\lambda} \def\o{\overline} \def\s{\sigma} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A Note on a Problem of Motzkin Regarding \\ \vskip .03in Density of Integral Sets with Missing \\ \vskip .1in Differences } \vskip 1cm \large Ram Krishna Pandey\thanks{This work was done when at Department of Mathematics, Indian Institute of Technology, Delhi} \\ Department of Mathematics \\ Indian Institute of Technology \\ Patliputra Colony, Patna -- 800013 \\ India\\ \href{mailto:ram@iitp.ac.in}{\tt ram@iitp.ac.in}\\ \ \\ Amitabha Tripathi\thanks{\em Corresponding author} \\ Department of Mathematics \\ Indian Institute of Technology \\ Hauz Khas, New Delhi -- 110016 \\ India \\ \href{mailto:atripath@maths.iitd.ac.in}{\tt atripath@maths.iitd.ac.in} \end{center} \vskip .2 in \begin{abstract} For a given set $M$ of positive integers, a problem of Motzkin asks to determine the maximal density ${\mu}(M)$ among sets of nonnegative integers in which no two elements differ by an element of $M$. The problem is completely settled when $|M| \le 2$, and some partial results are known for several families of $M$ when $|M| \ge 3$. In 1985 Rabinowitz \& Proulx provided a lower bound for ${\mu}(\{a,b,a+b\})$ and conjectured that their bound was sharp. Liu \& Zhu proved this conjecture in 2004. For each $n \ge 1$, we determine ${\k}(\{a,b,n(a+b)\})$, which is a lower bound for $\mu(\{a,b,n(a+b)\})$, and conjecture this to be the exact value of ${\mu}(\{a,b,n(a+b)\})$. \end{abstract} \section{Introduction} For $x \in {\R}$ and a set $S$ of nonnegative integers, let $S(x)$ denote the number of elements $n \in S$ such that $n \le x$. The upper and lower densities of $S$, denoted by $\o{\d}(S)$ and $\ul{\d}(S)$ respectively, are given by \[ \o{\d}(S):= \limsup_{x \imp \infty} \frac{S(x)}{x}, \quad \ul{\d}(S):= \liminf_{x \imp \infty} \frac{S(x)}{x}. \] If $\o{\d}(S)=\ul{\d}(S)$, we denote the common value by $\d(S)$, and say that $S$ has density $\d(S)$. Given a set of positive integers $M$, $S$ is said to be an $M$-set if $a \in S$, $b \in S$ imply $a-b \notin M$. Motzkin \cite{Mot} asked to determine $\mu(M)$ given by \[ \mu(M):= \sup_S \o{\d}(S) \] where $S$ varies over all $M$-sets. Cantor \& Gordon \cite{CG73} showed the existence of $\mu(M)$ for any $M$, determined ${\mu}(M)$ when $|M| \le 2$, and gave the following lower bound for $\mu(M)$: \begin{equation}\label{1} \mu(M) \ge {\k}(M):= \sup_{\gcd(c,m)=1} \frac{1}{m} \min_i |cm_i|_m, \end{equation} 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 ${\mu}(M)$, due to Haralambis \cite{Har77}: \begin{equation}\label{2} {\k}(M) = \max_{\stackrel{\tiny m=m_i+m_j}{\tiny 1 \le k \le \frac{m}{2}}} \frac{1}{m} \min_{m_i \in M} |km_i|_m, \end{equation} where $m_i,m_j$ represent distinct elements of $M$. The following useful upper bound for ${\mu}(M)$ is due to Haralambis \cite{Har77}: \begin{equation}\label{3} {\mu}(M) \le \a \end{equation} provided there exists a positive integer $k$ such that $S(k) \le (k+1)\a$ for every $M$-set $S$ with $0 \in S$ and for some $\a \in [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 ${\mu}(M)$ have been few, and computation of ${\mu}(M)$ has only been completely possible when $|M| \le 2$. Cantor \& Gordon \cite{CG73} showed that \[ {\mu}(\{m\}) = \frac{1}{2}, \quad {\mu}(\{m_1,m_2\}) = \frac{\lf (m_1+m_2)/2 \rf}{m_1+m_2}. \] There have, however, been a number of results that give the exact value or bounds for ${\mu}(M)$ in other cases; see \cite{LZ04} 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 \cite{Hal80} and shown to be equivalent to the Motzkin problem by Griggs \& Liu \cite{GL94}, is the {\it $T$-coloring problem}. Another connection with colorings of graphs involves the {\it fractional chromatic number} of {\it distance graphs}. The lower bound for ${\mu}(M)$, denoted by ${\k}(M)$ in \eqref{1}, is itself at the heart of a longstanding conjecture. The {\it Lonely Runner Conjecture} (LRC) stated independently by Wills \cite{Wil67} in the context of diophantine approximations and by Cusick \cite{Cus74} while studying view obstructions problems in $n$-dimensional geometry, was actually given this apt name by Bienia {\it et al} \cite{BGGST98}. Chen \cite{Che91} characterized $3$-sets $M$ for which $1/{\k}(M)$ is an integer and also obtained general bounds. We consider the problem of determining ${\mu}(M)$ for the family $M=\{a,b,n(a+b)\}$, $n \ge 1$. By a result of Cantor \& Gordon \cite{CG73}, we know that ${\mu}(kM)={\mu}(M)$. Thus, it is no loss of generality to assume that $\gcd(a,b)=1$, and that $ab-a$. \\[10pt] Write $\ell:=a+n\l$. We show that \[ \min \big\{|ay|_m, |by|_m, |n(a+b)y|_m\big\} \le \ts\frac{m-(a+n\l)}{2} = \ts\frac{m}{2}-\frac{\ell}{2} \] for each $y$, $1 \le y \le \frac{m}{2}$. Let ${\I}:=\left(\frac{m}{2}-\frac{\ell}{2},\frac{m}{2}+\frac{\ell}{2}\right)$. We show that $-ay\bmod{m} \in \I$ and $by\bmod{m} \in \I$ is simultaneously impossible for $1 \le y \le \frac{m}{2}$. Suppose \[ (a+b)y \equiv \ts\frac{a+b-\l}{2}+i\pmod{m}, \] with $1 \le i \le m-1$. Then \begin{eqnarray}\label{5} -ay \equiv n(a+b)y \equiv \ts\frac{m}{2}-\ts\frac{\ell}{2}+ni\pmod{m}, \\ \nonumber by \equiv (a+b)y-ay \equiv \ts\frac{m}{2}-\ts\frac{\ell}{2}+\ts\frac{a+b-\l}{2}+(n+1)i\pmod{m} \end{eqnarray} Thus $-ay\bmod{m} \in \I$ if and only if \[ km+\ts\frac{m}{2}-\ts\frac{\ell}{2} < \ts\frac{m}{2}-\ts\frac{\ell}{2}+ni < km+\ts\frac{m}{2}+\ts\frac{\ell}{2} \] for some integer $k$, with $0 \le k \le n-1$. This is equivalent to \[ k\ts\frac{m}{n} < i < k\ts\frac{m}{n}+\ts\frac{\ell}{n}, \] so that \begin{equation}\label{6} k(a+b)+1 \le i \le k(a+b)+a+\l-1. \end{equation} For $k(a+b)+1 \le i \le k(a+b)+a+\l-1$, we show that \begin{eqnarray*} km+\ts\frac{m}{2}+\ts\frac{\ell}{2} < \ts\frac{m}{2}-\ts\frac{\ell}{2}+\ts\frac{a+b-\l}{2}+(n+1)\big\{k(a+b)+1\big\} \end{eqnarray*} and \begin{eqnarray*} \ts\frac{m}{2}-\ts\frac{\ell}{2}+\ts\frac{a+b-\l}{2}+(n+1)\big\{k(a+b)+a+\l-1\big\} < (k+1)m+\ts\frac{m}{2}-\ts\frac{\ell}{2}. \end{eqnarray*} This will prove that \[ km+\ts\frac{m}{2}+\ts\frac{\ell}{2} < by < (k+1)m+\ts\frac{m}{2}-\ts\frac{\ell}{2}, \] so that $by\bmod{m} \notin \I$, 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)\l<(b-a)+2(n+1)$, which is true by the definition of $\l$. This completes the subcase when $m=a+n(a+b)$. \\[10pt] {\bf \em 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 \equiv \ts\frac{a+b+\l}{2}\pmod{m}. \] Then \[ -bx \equiv n(a+b)x \equiv \ts\frac{m-(b-n\l)}{2}\pmod{m}, \] and \[ ax = (a+b)x-bx \equiv -\ts\frac{m-\{a+(n+1)\l\}}{2}\pmod{m}. \] Therefore \begin{equation}\label{7} \min \big\{|ax|_m, |bx|_m, |n(a+b)x|_m\big\} = \ts\frac{m-\{(a+(n+1)\l\}}{2} \end{equation} since $b-n\lb-a$. \\[10pt] \noindent As in subcase (i), we may show that \[ \min \big\{|ay|_m, |by|_m, |n(a+b)y|_m\big\} \le \ts\frac{m-\{a+(n+1)\l\}}{2} \] for each $y$, $1 \le y \le \frac{m}{2}$. The argument is similar and we omit the proof. This completes subcase (ii). \\[5pt] To compute ${\k}(M)$ in Case I, we need to compare the expressions in \eqref{4} and \eqref{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 \[ \ts\frac{m_2-\{(a+(n+1)\l\}}{2m_2} = \ts\frac{1}{2}-\ts\frac{1}{2}\ts\frac{a+(n+1)\l}{b+n(a+b)} < \ts\frac{1}{2}-\ts\frac{1}{2}\ts\frac{a+n\l}{a+n(a+b)} = \ts\frac{m_1-(a+n\l)}{2m_1} \] if and only if $(2n+1)\l>b-a$. This completes the proof of Case I. \\[10pt] {\sc Case II:} {\bf \big(${\l} \not\equiv a+b$ (mod $2$)\big)} \\[10pt] {\bf \em Subcase\/} (i): ($m=a+n(a+b)$) Choose $x$ such that \[ (a+b)x \equiv \ts\frac{a+b-\l+1}{2}\pmod{m}. \] Then \[ -ax \equiv n(a+b)x \equiv \ts\frac{m-\{a+n(\l-1)\}}{2}\pmod{m}, \] and \[ bx = (a+b)x-ax \equiv \ts\frac{m+\{b-(n+1)(\l-1)\}}{2}\pmod{m}. \] Therefore \begin{equation}\label{8} \min \big\{|ax|_m, |bx|_m, |n(a+b)x|_m\big\} = \ts\frac{m-\{b-(n+1)(\l-1)\}}{2} \end{equation} since $a+n(\l-1) \le b-(n+1)(\l-1)$ if and only if $(2n+1)(\l-1) \le b-a$. \\[10pt] As in subcase (i) of Case I, we may show that \[ \min \big\{|ay|_m, |by|_m, |n(a+b)y|_m\big\} \le \ts\frac{m-\{b-(n+1)(\l-1)\}}{2} \] for each $y$, $1 \le y \le \frac{m}{2}$. This completes subcase (i). \\[5pt] {\bf \em Subcase\/} (ii): ($m=b+n(a+b)$) Choose $x$ such that \[ (a+b)x \equiv \ts\frac{a+b+\l-1}{2}\pmod{m}. \] Then \[ -bx \equiv n(a+b)x \equiv \ts\frac{m-\{b-n(\l-1)\}}{2}\pmod{m}, \] and \[ ax = (a+b)x-bx \equiv \ts\frac{m+\{a+(n+1)(\l-1)\}}{2}\pmod{m}. \] Therefore \begin{equation}\label{9} \min \big\{|ax|_m, |bx|_m, |n(a+b)x|_m\big\} = \ts\frac{m-\{b-n(\l-1)\}}{2} \end{equation} since $a+(n+1)(\l-1) \le b-n(\l-1)$ if and only if $(2n+1)(\l-1) \le b-a$. \\[10pt] As in subcase (i) of Case I, we may show that \[ \min \big\{|ay|_m, |by|_m, |n(a+b)y|_m\big\} \le \ts\frac{m-\{b-n(\l-1)\}}{2} \] for each $y$, $1 \le y \le \frac{m}{2}$. This completes subcase (ii). \\[5pt] To compute ${\k}(M)$ in Case II, we need to compare the expressions in \eqref{8} and \eqref{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 \[ \ts\frac{m_1-\{b-(n+1)(\l-1)\}}{2m_1} = \ts\frac{1}{2}-\ts\frac{1}{2}\ts\frac{b-(n+1)(\l-1)}{a+n(a+b)} \le \ts\frac{1}{2}-\ts\frac{1}{2}\ts\frac{b-n(\l-1)}{b+n(a+b)} = \ts\frac{m_2-\{b-n(\l-1)\}}{2m_2} \] if and only if $(2n+1)(\l-1) \le b-a$. This completes the proof of Case II, and of the theorem. \end{proof} \begin{corollary}\label{C} {\bf (Liu \& Zhu \cite{LZ04})} \\[5pt] Let $M=\{a,b,a+b\}$, where $a