%------------------------------------------------------------------------------ % Beginning of journal.tex %------------------------------------------------------------------------------ % % AMS-LaTeX 1.2 sample file for journals, based on amsart.cls. % % Replace amsart by the documentclass for the target journal, e.g. tran-l. % \documentclass[12pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{lscape} \usepackage{latexsym} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{xca}[theorem]{Exercise} \newtheorem{remark}[theorem]{Remark} % Absolute value notation \newcommand{\abs}[1]{\lvert#1\rvert} % Blank box placeholder for figures (to avoid requiring any % particular graphics capabilities for printing this document). \newcommand{\blankbox}[2]{% \parbox{\columnwidth}{\centering % Set fboxsep to 0 so that the actual size of the box will match the % given measurements more closely. \setlength{\fboxsep}{0pt}% \fbox{\raisebox{0pt}[#2]{\hspace{#1}}}% }% } \begin{document} \vspace*{-60pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4 (2004), \#A12} \vskip 50pt \begin{center} {\bf DISJOINT BEATTY SEQUENCES} \vskip 20pt {\bf Jamie Simpson}\\ {\smallit Department of Mathematics and Statistics, Curtin University of Technology,\\ GPO Box U1987, Perth WA 6001, Australia}\\ {\tt simpson@maths.curtin.edu.au}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 2/6/04, Revised: 9/28/04, Accepted: 9/29/04, Published: 9/30/04 } \vskip 30pt \centerline{\bf Abstract} \noindent Consider two rational Beatty sequences $\{\lfloor p_1/q_1 + \beta_1 \rfloor:n \in \mathbf{Z} \}$ and $\{\lfloor p_2/q_2 + \beta_2 \rfloor:n \in \mathbf{Z} \}$ where $p_1,p_2,q_1,q_2$ are integers. We set $p=\gcd(p_1,p_2)$, $q=\gcd(q_1,q_2)$, $u_1=q_1/q$, $u_2=q_2/q$. In 1985 Morikawa showed that the sequences are disjoint for some $\beta_1$ and $ \beta_2$ if and only if there exist positive integers $x$ and $y$ such that $$xu_1+yu_2=p-2u_1u_2(q-1).$$ We give a new proof of this theorem. We also use intermediate results to obtain a generating function for a Beatty sequence and relate this to Fraenkel's conjecture about disjoint covering systems of rational Beatty sequences. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4 (2004), \#A12\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt We define a \textbf{rational Beatty sequence} to be a sequence \begin{equation}\label{1} S(p/q,\beta)=\{\lfloor pn/q+\beta \rfloor : n \in \mathbf{Z} \}, \end{equation} \noindent where $p$ and $q$ are positive integers, $\gcd(p,q)=1$ and $\beta$ is real. We say $p/q$ is the \textbf{modulus} of the sequence. Such sequences have an extensive literature (see \cite{F}, \cite{Porub}, \cite{St}) and are the subject of a famous conjecture, postulated by Fraenkel (\cite{F}, \cite{Porub}, \cite{GLL}, \cite{S}, \cite{T}). A \textbf{disjoint covering system of rational Beatty sequences} is a set of Beatty sequences $\{S(p_i/q_i,b_i) : i=1, \dots, n\}$ which partitions the integers. Fraenkel's conjecture is: \noindent \textbf{Conjecture} If the rational Beatty sequences $\{S(p_i/q_i,b_i) : i=1, \dots, n\}$ form a disjoint covering system, with $n>2$ and $p_1/q_11.$ The situation is considerably more complicated when we deal with rational Beatty sequences with non-integral moduli. Ryozu Morikawa \cite{M} has found necessary and sufficient conditions for the existence of $\beta_1, \: \beta_2,$ such that $S(p_1/q_1,\beta_1)$ and $S(p_2/q_2,\beta_2)$ are disjoint. This is the ``Japanese Remainder Theorem". Morikawa's proof is difficult and because it was published in a little known journal is not as well known as it should be. In this paper we present a simpler proof. Thus we are interested in whether or not the Beatty sequences $S(p_1/q_1,\beta_1)$ and $S(p_2/q_2,\beta_2)$ intersect. We begin with some results that simplify the question. \begin{lemma}\label{T1} Given a rational Beatty sequence $S(p/q,\beta)$ there exist integers $b_1$ and $b_2$ such that \begin{eqnarray*} S(p/q,\beta) & =& S(p/q,b_1)\\ & = & S(p/q,b_2/q)). \end{eqnarray*} \end{lemma} \noindent For a proof see Lemma 1 of \cite{S}, where a slightly more general result is given. \noindent \textbf{Remark 1} Since $\lfloor p(n+q)/q + \beta \rfloor = \lfloor pn/q + \beta \rfloor +p$ the sequence $S(p/q,\beta) $ coincides with a set of residue classes modulo $p$. It follows that: \begin{eqnarray*} S(p/q, b'_1) &=&S(p/q,b_1),\\ S(p/q,b'_2/q)&=&S(p/q,b_2/q) \end{eqnarray*} if and only if $b'_1 \equiv b_1 \bmod p$ and $b'_2 \equiv b_2 \bmod p$. If $b_1$ and $b_2$ are as in Lemma \ref{T1} we have $$S(p/q,b_1q/q)=S(p/q,b_2/q)$$ from which \begin{equation}\label{2} b_1q \equiv b_2 \pmod{p}. \end{equation} \begin{theorem} \label{T2} Let $p=\gcd(p_1,p_2)$. Then $$S(p_1/q_1,b_1) \cap S(p_2/q_2,b_2) = \emptyset$$ if and only if $$S(p/q_1,b_1) \cap S(p/q_2,b_2) = \emptyset.$$ \end{theorem} \noindent \textit{Proof.} The ``if" part is immediate since $S(p_i/q_i,b_i) \subseteq S(p/q_i,b_i)$ for $i=1,2.$ In the other direction let $$p_1=R_1p, \: p_2=R_2p$$ so that $\gcd(R_1,R_2)=1.$ By Lemma \ref{T1} we may assume that $b_1$ and $b_2$ are integers. Suppose there exist integers $n_1$ and $n_2$ such that $$\lfloor n_1p/q_1 \rfloor +b_1=\lfloor n_2p/q_2 \rfloor + b_2. $$ Then for any integer $m$, \begin{equation}\label{3} \lfloor (n_1+mq_1)p/q_1 \rfloor +b_1=\lfloor (n_2+mq_2)p/q_2 \rfloor + b_2. \end{equation} It is now sufficient to show that there exists $m$ such that \begin{equation} \label{4} R_1 | (n_1+mq_1), \: \: R_2 | (n_2+mq_2)\end{equation} for then the left and right sides of (\ref{3}) are members, respectively, of $S(p_1/q_1,b_1)$ and $S(p_2/q_2,b_2)$. Since $\gcd (q_1,R_1) =1.$ there exists $m_0$ such that $R_1$ divides $n_1+m_0q_1$. So for any integer $k$, $$R_1 | n_1+(m_0+kR_1)q_1.$$ Now consider the sequence $$\{n_2+(m_0+kR_1)q_2:k \in \mathbf{Z}\}.$$ Since $\gcd (R_1,R_2)=1$ and $\gcd (R_2,q_2)=1$ there exists $k_0$ such that $$R_2|n_2+m_0q_2+k_0R_1q_2,$$ so that (\ref{4}) holds with $m=m_0+k_0R_1.$ \hfill$\Box$ This theorem means that when considering conditions for the disjointness of pairs of Beatty sequences we may assume that the numerators of their moduli are equal. We shall henceforth fix $p$ to be this numerator. For this $p$ and any integer $q$ for which $\gcd (p,q) =1$ we let $\overline{q}$ be the least non-negative residue modulo $p$ satisfying $$q\overline{q} \equiv -1 \bmod p.$$ \begin{theorem} \label{T3} The sequence $S(p/q,b)$, where $b$ is an integer, coincides with the set of residues $$\{\overline{q}m+b : m=0, \dots , q-1\} \bmod p.$$ \end{theorem} \noindent \textit{Proof.} For any $n$, \begin{eqnarray*} \lfloor pn/q + b \rfloor &\equiv& (pn-q\lfloor pn/q \rfloor )\overline{q} + b \pmod{p}. \end{eqnarray*} The term in parentheses can take any value in the interval $[0,q-1]$. Thus for any $n$ there exists $m \in [0,q-1]$ such that $$\lfloor pn/q+b \rfloor \equiv m\overline{q} + b \pmod{p}.$$ Similarly, for any $m \in [0,q-1]$ there exists an $n$ satisfying this relation. $\Box$ The next theorem concerns the disjointness of two Beatty sequences in which the denominator of the modulus of one divides the denominator of the modulus of the other. This will be used as a lemma for the main theorem. \begin{theorem} \label{T4} Let $u$ be a positive integer. Then the Beatty sequences $S(p/q, b_1/q)$ and $S(p/uq, b_2/uq)$ have non-empty intersection if and only if $b_2$ is congruent modulo p to some integer $n$ in the interval $[(b_1-q+1)u,(b_1+q)u-1].$ \end{theorem} \noindent \textit{Proof.} Using equation (\ref{2}) in Remark 1, the two Beatty sequences are $S(p/q,-b_1\overline{q})$ and $S(p/uq,-b_2\overline{uq}).$ By Theorem \ref{T3} these intersect if and only if there exist integers $i$ and $j$ with $0 \le i \le q-1,$ $0 \le j \le uq-1$ such that, \begin{equation} \label{5} i\overline{q}-b_1\overline{q} \equiv j\overline{uq}-b_2\overline{uq} \pmod{p}. \end{equation} Multiplying by $uq$ and rearranging gives $$b_2 \equiv j+b_1u-iu \pmod{p}.$$ That is, \begin{eqnarray*} b_2 &\in & \bigcup_{i=0}^{q-1} \bigcup_{_j=0}^{uq-1} \{j+b_1u-iu\}\\ &\equiv & \bigcup_{i=0}^{q-1} [(b_1-i)u,(b_1+q-i)u-1] \pmod{p}. \end{eqnarray*} This is the union of $q$ blocks of $uq$ consecutive residues modulo $p$, with starting points of consecutive blocks differing by $u$. Thus it is the interval $$[(b_1-q+1)u,(b_1+q)u-1]\pmod{p}.$$ \hfill $\Box$ \begin{corollary} There exist $b_1$, $b_2$ such that the Beatty sequences in Theorem \ref{T4} are disjoint if and only if $p > (2q-1)u.$ \end{corollary} \noindent \textit{Proof.} The interval $[(b_1-q+1)u,(b_1+q)u-1]$ contains $(2q-1)u$ integers. By the theorem, the Beatty sequences can be made disjoint if and only if we can find $b_2$ which is not congruent modulo $p$ to any integer in the interval. This occurs if and only if $p>(2q-1)u$. \hfill $\Box$ We now consider the general case of two Beatty sequences $S(p/q_1,\beta_1)$ and $S(p/q_2,\beta_2).$ From Remark 1 we may assume that $\beta_1=0,$ $\beta_2=b/q_2.$ The next theorem allows us to apply Theorem \ref{T4} to this case. We let \begin{equation}\label{5A} q=\gcd (q_1,q_2), \: \: q_1=u_1q, \: \: q_2=u_2q. \end{equation} \begin{theorem} \label{T5} $$S(p/q_1,0)=\bigcup_{i=0}^{u_1-1}S(p/q,i\overline{u}_1/q).$$ \end{theorem} \noindent \textit{Proof.} Treating $S(p/q_1,0)$ as a set of residues modulo $p$, we have, by Theorem \ref{T3}, $$S(p/q_1,0)=\bigcup_{m=0}^{q_1-1}\{m\overline{q}_1\} \pmod{p}.$$ By (\ref{5A}) the right hand side is $$\bigcup_{m=0}^{u_1q-1}\{m\overline{u_1q}\} \equiv \bigcup_{i=0}^{u_1-1} \bigcup_{j=0}^{q-1}\{u_1j+i\}\overline{u_1q} \pmod{p}.$$ It is easily checked that $$\overline{u_1q} \equiv -\overline{u}_1 \overline{q} \pmod{p}$$ so that, using Theorem \ref{T3}, \begin{eqnarray*} S(p/q,0) & \equiv & \bigcup_{i=0}^{u_1-1}\bigcup_{j=0}^{q-1}\{-\overline{u}_1 \overline{q}u_1j+i\overline{u_1q}\} \\ &\equiv & \bigcup_{i=0}^{u_1-1}\bigcup_{j=0}^{q-1}\{j \overline{q} +i\overline{u_1q}\}\\ &\equiv & \bigcup_{i=0}^{u_1-1}S(p/q,i\overline{u_1q}) \\ &\equiv & \bigcup_{i=0}^{u_1-1}S(p/q,-i\overline{u}_1\overline{q}q/q) \\ &\equiv & \bigcup_{i=0}^{u_1-1}S(p/q,i\overline{u}_1/q) \pmod{p} \end{eqnarray*} as required. \hfill $\Box$ For $i=0$ to $u_1-1$ we let $V_i$ be the set of residues modulo $p$ such that $b \in V_i$ implies $$S(p/q_2,b/q_2) \cap S(p/q,i\overline{u}_1/q) \not= \emptyset.$$ \noindent \textbf{Remark 2} It follows from Theorem \ref{T5} that there exists $b$ such that $S(p/q_1,0)$ and $S(p/q_2,b/q_2)$ are disjoint if and only if $\cup_{i=0}^{u_1-1}V_i$ is not a complete residue system modulo $p$. If we apply Theorem \ref{T4} with $u_2$ in the role of $u$, $b$ in the role of $b_2$ and $i\overline{u}_1$ in the role of $b_1$ we obtain \begin{eqnarray*} V_i &=& [(i\overline{u}_1-q+1)u_2,(i\overline{u}_1+q)u_2-1]\\ &=&[(-q+1)u_2,qu_2-1]+i\overline{u}_1u_2, \end{eqnarray*} using an obvious notation. Our problem now is to decide whether the union of these intervals is a complete residue system modulo $p$. To proceed we need some more notation. Let $x$ and $y$ be integers such that \begin{equation} \label{6} xu_1+yu_2=p-2u_1u_2(q-1) \end{equation} with \begin{equation} \label{7} 1\le y\le u_1. \end{equation} Since $u_1$ and $u_2$ are relatively prime by definition, (\ref{6}) can always be satisfied, and (\ref{7}) ensures that $x$ and $y$ are uniquely defined. Now let \begin{equation} \label{8} z=u_1-y. \end{equation} Recall that $\gcd (q_1,p)=1,$ hence $\gcd(u_1,p)=1,$ hence by (\ref{6}) $\gcd (y,u_1)=1$ and by (\ref{8}) $\gcd (z,u_1)=1.$ Thus for each $i \in [0,u_1-1]$ there exists a unique integer $r(i)$ satisfying $r(i) \in [0,u_1-1]$ and $i \equiv r(i)z \bmod u_1.$ For $r=0, \dots ,u_1$ let $$M(r)=r(x+(2q-1)u_2)-\lfloor zr/u_1 \rfloor u_2.$$ We will use the functions $r(i)$ and $M(r)$ to obtain a reordering of the intervals $V_i$. \begin{lemma} \label{L1} For $i \in [0,u_1-1],$ $$M(r(i)) \equiv -i\overline{u}_1u_2 \pmod{p}.$$ \end{lemma} \noindent \textit{Proof.} Fix $i$ and consider $u_1(M(r(i))+i\overline{u_1}u_2)$. Writing $r$ for $r(i)$ and using (\ref{6}) this equals \begin{eqnarray*} & & u_1r(x+(2q-1)u_2)-u_1\lfloor zr/u_1 \rfloor u_2 +u_1i\overline{u_1}u_2\\ & \equiv & r(xu_1+2u_1u_2(q-1)+u_1u_2)-u_1u_2\lfloor zr/u_1 \rfloor -iu_2 \\ & \equiv & r(-yu_2+u_1u_2)-u_1u_2\lfloor zr/u_1 \rfloor -iu_2 \\ & \equiv & u_2((u_1-y)r-u_1\lfloor zr/u_1 \rfloor -i) \\ & \equiv & u_2(zr-u_1 \lfloor zr/u_1 \rfloor -i) \pmod{p}.\\ \end{eqnarray*} Since $zr \equiv i \bmod u_1$ and $0 \le i 0.$ By Remark 2 the Beatty sequences can be disjoint if and only if the union of the intervals $V_i$ is not a complete residue system modulo $p$. By Lemma \ref{L1} and the observation that as $i$ takes values from 0 to $u_1-1$ so, in a different order, does $r(i),$ this union is, $$ \bigcup_{i=0}^{u_1-1}\{[(-q+1)u_2,qu_2-1]+i\overline{u}_1u_2 \}\\ = \bigcup_{r=0}^{u_1-1}\{[(-q+1)u_2,qu_2-1]-M(r) \}. $$ This is the union of $u_1$ blocks each containing $(2q-1)u_2$ consecutive residues modulo $p$. The first member of the $r$th block is $(-q+1)u_2-M(r).$ Now $$M(r+1)-M(r)=x+(2q-1)u_2-u_2(\lfloor z(r+1)/u_1 \rfloor -\lfloor zr/u_1 \rfloor). $$ The term in parentheses takes the value 0 or 1, and as $r$ increases from 0 to $u_1$, $\lfloor zr/u_1 \rfloor$ increases from 0 to $z$. Thus this term will equal 1 for $z$ values of $r$ and 0 for $u_1-z=y$ values. Now $y$ is positive by assumption so the maximum value of $M(r+1)-M(r)$ is $x+(2q-1)u_2.$ The question of whether the union of the intervals $V_i$ is a complete residue system modulo $p$ is then equivalent to asking whether the block size is as big as $M(r+1)-M(r).$ That is, is $(2q-1)u_2 \ge x+(2q-1)u_2?$ This is so if and only if $x \le 0$. Thus it is possible to find $\beta_1,$ $\beta_2$ such that the Beatty sequences are disjoint if and only if $x$ is strictly positive, which implies the statement of the theorem. \hfill $\Box$ We have presented an analogue of part of the Chinese Remainder Theorem. That theorem also describes the shape of the intersection $S(p_1,b_1) \cap S(p_2,b_2)$ when it is non-empty: it is an arithmetic progression with common difference equaling the lowest common multiple of $p_1$ and $p_2.$ In the general case the situation is again more complicated. Fraenkel and Holzman \cite{FH} have shown that the intersection of $S(p_1/q_1,b_1)$ and $S(p_2/q_2,b_2)$ can have as many as $\min \{q_1,q_2\}+3$ distinct differences between consecutive members. We now return to Fraenkel's conjecture Although this concerns sets of pairwise disjoint Beatty sequences, Theorem \ref{JRT} does not seem to help a great deal. However, we can use some of the earlier results to produce a generating function for the set of non-negative members of a Beatty sequence. We remark that O'Bryant \cite{O} has recently developed a different technique for producing generating functions for Beatty sequences. \begin{theorem} \label{gf} The Beatty sequence $S(p/q,b),$ where $b$ is a non-negative integer, has generating function $$f(x)=g(x)+\frac{x^b}{1-x^p} \frac{1-x^{\overline{q}q}}{1-x^{\overline{q}}},$$ where $g(x)$ is a polynomial with all coefficients equalling 1. \end{theorem} \noindent \textit{Proof.} By Theorem \ref{T3} and Remark 1 we see that the non-negative members of the Beatty sequence $S(p/q,b)$ form the set $$\{\overline{q}m+b+np : 0\le m p_{n-1}$ and let $\zeta$ be a primitive $p_n$th root of unity. Now let $x$ approach $\zeta$ in equation (\ref{sum}). The absolute value of the term $\frac{x^{b_n}}{1-x^{p_n}} \frac{1-x^{\overline{q}_nq_n}}{1-x^{\overline{q}_n}}$ goes to infinity, but all other terms remain finite. This contradiction proves the result. \hfill $\Box$ \begin{thebibliography}{9} \footnotesize \bibitem{BFF} Berger, M.A., Felzenbaum, A., Fraenkel, A.S., Disjoint covering systems of rational Beatty sequences, J.Comb. Th.(A) 42(1986), 150-153. \bibitem{BFF2} Berger, M.A., Felzenbaum, A., Fraenkel, A.S., A non-analytic proof of the Newman-Z\'{n}am result for disjoint covering systems, Combinatorica, 6(1986), 235-243. \bibitem{E} Erd\"{o}s, P., On a problem concerning covering systems (Hungarian, English summary), Mat. Lapok, 3(1950), 122-128. \bibitem{F} Fraenkel, A.S., Complementing and exactly covering sequences, J. Comb. Th.(1973), 8-20. \bibitem{FH} Fraenkel, Aviezri S., Holzman, Ron, Gap problems for integer part and fractional part sequences. J. Number Theory 50 (1995), 66--86. \bibitem{GLL} Graham, R.L., Shen Lin, Chio-Shis Lin, Spectra of numbers, Math. Mag., 51(1978), 174-176. \bibitem{L} Lewis, E., Infinite covering systems of congruences which don't exist, Proc. Amer. Math. Soc., 124(1996), 355-360. \bibitem{M} Morikawa, R., Disjoint sequences generated by the bracket function, Bull. Lib. Arts, Nagasaki University, 26(1985), 1-13. \bibitem{O} O'Bryant, K., A generating function technique for Beatty sequences and other step functions, J. Number Theory 94 (2002), 299-319 \bibitem{Porub} Porubsk\'{y}, \v{S}. and Sch\"{o}nheim, J., Covering Systems of Paul Erd\H{o}s Past, Present and Future, Bolyai Soc. Math. Studies 11, Paul Erd\H{o}s and his Mathematics, I, Budapest 2002, 581-627. \bibitem{S1} Simpson, R.J., Exact coverings of the integers by arithmetic progressions, Discrete Math. 59(1986), 181-190. \bibitem{S} Simpson, R.J., Disjoint covering systems of rational Beatty sequences, Discrete Math. 92(1991), 361--369. \bibitem{St} Stolarsky, K.B., Beatty sequences, continued fractions and certain shift operators, Can. Math. Bull. 19(1976), 473-482. \bibitem{T} Tijdeman, R., Fraenkel's conjecture for six sequences, Disc. Math. 222(2000), 223--234. \bibitem{Z} Zeilberger,D., How Berger, Felzenbaum and Fraenkel Revolutionized Covering Systems the Same Way that George Boole Revolutionized Logic, Elect. J. Comb., A1, 8(2), (2002), 10 pages. \end{thebibliography} \end{document} %------------------------------------------------------------------------------ % End of journal.tex %------------------------------------------------------------------------------