# A problem about floor function

Here's the problem

Suppose that $$a, b \in \mathbb {R^+},\qquad 0 < a + b < 1$$ Prove or disprove that $$\exists n \in \mathbb{Z^+}: \left\{na\right\} + \left\{nb\right\} \ge 1$$ where $\{x\} = x - \lfloor x \rfloor$ and $\lfloor x \rfloor = \max\left\{ n | n \in \mathbb{Z}, n \le x \right\}$.

Postscripts:

1. The original problem in magazine ( ISSN 1005-6416 ) might be (For a long time, I can't remember clearly):

$a, b$ are irrationals, subjects to $\forall n \in \mathbb{Z^+}: \left\{ na \right\} + \left\{ nb \right\} \le 1$, prove that $a + b \in \mathbb{Z}$.

Because I've found that $a, b$ needn't have been irrationals, I insist that there be a general proof (I think it's algebrian). I think the steps are like this:

• Divides $\left\{ (x, y) | x, y \in \mathbb{R^+}, x + y < 1 \right\}$ into many (infinity) pieces.
• For each piece, we obtain a $n$.
2. It may be easy when $a, b \in \mathbb{Q}$. Here's the proof:

Let $f(n) = \left\{na\right\} + \left\{nb\right\}$. For each $x \not \in \mathbb{Z}$, we have $\left\{x\right\} + \left\{-x\right\} = 1$

So if $a, b \in \mathbb{Q}$, we have $f(1) + f(-1) = 2$

Note that: $\exists T \in \mathbb{Z^+}$ subjects to $\forall n \in \mathbb{Z}: f(n + T) = f(n)$

So $2 = f(1) + f(-1) = f(1) + f(2T-1) \le 2 \max\left(f(1), f(2T-1)\right)$

We've done.

3. I'd like a proof with algebraic construction.

Thanks

• This is certainly true for rationals when $a = b = \frac{k}{m}$ (suppose $\frac{k}{m}$ is in lowest terms) since this forces $\frac{k}{m} < \frac{1}{2}$. Thus, the fractional part $\{n \cdot \frac{k}{m}\} \in \left\{0, \frac{1}{m}, \frac{2}{m}, \dots , \frac{m-1}{m} \right\}$. Note that the condition $a + b < 1$ implies that $m > 2$ and hence $\frac{m-1}{m} > \frac{1}{2}$. – JavaMan Jan 30 '12 at 8:42
• The fractional parts of multiples of irrationals are dense and equidistributed in $[0,1]$ ( mathworld.wolfram.com/FractionalPart.html ). This might be helpful for the irrational case. – Listing Jan 30 '12 at 9:09
• @Listing I know that there's a proof by the theorems of multiples of irrationals (although I don't know how). But I'd prefer a algebra proof without discussing whether $a, b$ are rationals or not. That's what I meant. – Yai0Phah Jan 30 '12 at 9:29
• @JavaMan Thanks. 1. It's from a mock test of math competition from a magazine made up of mock tests, so I think the context might be useless. 2. I'm not a native speaker. As you see in the post, I try to replace the English words with the mathematical symbols. – Yai0Phah Jan 30 '12 at 14:31
• The "easy" case is that when the set $\{a,b,1\}$ is linearly independent over $\mathbf{Q}$, then the set of points $$\{(\{na\},\{nb\})\mid n\in\mathbf{N}\}$$ is dense on the square $[0,1]\times[0,1]$ meaning that the sum attains values arbitrarily close to two. This the 2-dimensional version of Kronecker's density theorem (see e.g. Joe Roberts': "Elementary Number Theory - a problem oriented approach", or Tom Apostol's "Modular Functions and Dirichlet Series in Number Theory") – Jyrki Lahtonen Feb 1 '12 at 8:58

Look at the following figure of the checkered $(x,y)$-plane with gridlines at integer $x$'s and $y$'s: The points $z_n:=(n\ a,n\ b)$ $\ (n\in{\mathbb Z})$ are marked. We will show that at least one $z_n$ with $n>0$ falls in the interior of a grey triangle, which means $\{n a\}+\{n b\}>1$.

We distinguish the following two cases:

(i) $b/a$ is rational. $-$ In this case there are $p$, $q\in{\rm N}_{\geq1}$ with ${\rm gcd}(p,q)=1$ and a $\lambda>0$ with $a=p\lambda$, $b=q\lambda$. All points $z_n$ are lying on the line $$\ell:\quad t\mapsto z(t)=(pt, qt)\qquad(-\infty<t<\infty)\ ;$$ in fact $z_n=z(n\lambda)$. This line passes through the points $(j p, j q)$ $\ (j\in{\mathbb Z})$ and actually is a closed curve $\gamma$ on the torus $T$ obtained by identifying points $(x,y)$ and $(x',y')$ with $x\equiv x'$ $\ ({\rm mod}\ p)$ and $y\equiv y'$ $\ ({\rm mod}\ q)$. Let $\pi: \ {\mathbb R}^2\to T$ denote the corresponding projection. There is a finite set of segments $\sigma_k\subset\gamma=\pi(\ell)$ colored in grey, which makes up for half of the length of $\gamma$.

(i.i) If $\lambda$ is rational then the $z_n$ project onto only finitely many equally spaced points on $\gamma$, and some $z_n$ with $n>0$ will project onto the same point as $z_{-1}$ and therefore will lie in the interior of a grey triangle. (This case has already been dealt with by the OP.)

(i.ii) If $\lambda$ is irrational then the points $\pi(z_n)$ are dense on $\gamma$, and some of them will lie in the interior of one of the grey intervals of $\gamma$. It follows that the corresponding $z_n$ are lying in a grey triangle.

(ii) $b/a=:m$ is irrational. $-$ Put $\delta:=1-a-b$ and consider again the line $$\ell: \quad t \mapsto z(t):=(t, m t)\qquad(-\infty<t<\infty)$$ (now with a different parametrization). The $z_n$ are equally spaced on $\ell$ with distance $d:=\sqrt{a^2+b^2}$. The line $\ell$ intersects the vertical gridlines $x=k\in{\mathbb Z}$ in the points $(k, m k)$ whose ordinates $y_k:=m k$ are irrational for $k\ne0$. Therefore the $y_k$ are dense ${\rm mod}\ 1$. There is a $k_0>0$ such that $1-\{y_{k_0}\}<\delta$. It is easy to see that the segment $\sigma\subset\ell$ with endpoints $(k_0-a, y_{k_0}-b)$ and $(k_0, y_{k_0})$ is lying completely in the grey triangle to the left of $(k_0, y_{k_0})$. Since $\sigma$ has length $d$ there is at least one $z_n\in\sigma$, and this $z_n$ lies in the interior of a grey triangle.

• In summary, you proved: 1. if $a, b \not \in Q$, $\displaystyle{\frac{a}{b}} \in \mathbb{Q}$, the points on line (in torus) will be density so some point will be in gray triangle. 2. if $\displaystyle{\frac{a}{b}} \not \in \mathbb{Q}$, there will be a "gray segment" which length is larger than $\displaystyle{\sqrt{a^2 + b^2}}$ (exactly could be $\displaystyle{\frac{\sqrt{a^2 + b^2}}{a + b} - \varepsilon}$ foreach $\varepsilon > 0$. Am I right? – Yai0Phah Feb 2 '12 at 4:24
• You might as well need to improve your symbol such as $\bmod n$ and $\pmod n$ with LaTeX command bmod and pmod. – Yai0Phah Feb 2 '12 at 4:39
• The algebraic constructor proof might not exist. – Yai0Phah Feb 2 '12 at 4:45
• @Frank Science: Concerning your first comment: Yes. – Christian Blatter Feb 2 '12 at 9:11

Case 1: $a,b$ rationals.

This case is simple. $a=\frac{m}{n}$ and $b=\frac{r}{p}$ with both fractions irreducible.

WLOG $n \geq p$.

Subcase 1.1 *$n < p$*

Solve $rx \cong -1 \mod p$, which has the solution $x= x_0 +lp$.

Then for all $x$ we have $\{ xb \}=\frac{p-1}{p}$, and because $1 < n < p$ you can easely find such $x$ so that $xa \notin Z$, meaning $\{ xa \} >\frac{1}{n}$.

Since $\frac{p-1}{p}+\frac{1}{n} > \frac{p-1}{p}+\frac{1}{p} =1$ we are done.

Subcase 1.2 *$n = p$*

Same idea.

Solve $rx \cong -1 \mod p$, which has the solution $x= x_0 +lp$.

The only possible issues are if $xm= 0, 1 \mod p$.

But this is not possible.

The first case is not possible since both $x,m$ are invertible, while in the second case you get

$$rx \cong -1 \mod p \Rightarrow r \cong -x^{-1} \mod p$$ $$mx \cong 1 \mod p \Rightarrow m \cong x^{-1} \mod p$$

Thus, $r+m \cong 0 \mod p$ and hence $a+b= \frac{m+r}{p} \in Z$ which is a contradiction.

Case 2 A rational, b irrational. This case follows immediately from Dirichclet theorem.

Indeed, $a=\frac{m}{n}$ irreducible.

The equation $xm \cong -1 \mod p$ has solution $x= x_o+np$, and by Dirichlet theorem, since $b$ is irrational, the set $\{ (x_0+np)b\}$ is dense in $[0,1]$.

Pick some $k$ so that $\{ (x_0+kp)b\} > \frac{1}{n}$ and you are done, $(x_0+kp)$ satisfies your condition.

Case 3: $a,b$ irational. Then $b= \alpha a$.

Subcase 3.1 $\alpha$ irrational. See Jyrki's comment.

Subcase 3.2 $\alpha$ rational. $\alpha=\frac{m}{n}$ irreducible.

Fix some $\epsilon$ so that $(m+n)\epsilon <1$. Then we also have $m-1 < m(1-\epsilon) < m$.

By Dirichlet theorem, the set $\{nka\}$ is dense in $[0,1]$.

Pick some $k$ so that

$$\{ kna \} > 1- \epsilon \,.$$

Then

$$kna = l+ 1- \epsilon$$

for some integer $l$.

Hence

$$knb=kn\frac{m}{n}a=\frac{m(l+1-\epsilon)}{n}$$

Note that by our choise of $\epsilon$,

$$\frac{ml+m-1}{n} < \frac{m(l+1-\epsilon)}{n} < \frac{ml+m}{n} \,.$$

This shows that $[\frac{m(l+1-\epsilon)}{n}] \leq \frac{ml+m-1}{n}$ and hence

$$\{\frac{m(l+1-\epsilon)}{n} \} > \frac{1-m\epsilon}{n}$$

Thus

$$\{ kna \} + \{ knb \} >1- \epsilon+ \frac{1-m\epsilon}{n} \geq 1$$

the last inequality following from $(m+n)\epsilon<1$.

P.S. The proof is extremely technical, there might be a mistake into it. I wrote but I would definitely not enjoy reading it :P

• Why -1? The voter might as well point out the mistake. Thanks. – Yai0Phah Feb 2 '12 at 3:28

The case for rationals was mentioned in Javaman's comment above. Here is one for the irrationals. I'm arguing here a bit informal, I think from this a precise answer can be derived.

Assume a and b in their base-2-expansions at some position behind the decimal separator:
$\qquad \small \begin{array} {rrl} a&:& \ldots 10010100101001 \ldots \\ b&:& \ldots 00001010110000 \ldots \\ & & \ldots .........! \end{array}$

Then
a) if at some position k both strings have simultanously a 1 then it is obvious that $\small n=2^k$ solves the problem.

So to have a counterexample we
b) need a pair of numbers, which have at no position simultanously a 1. But if we have nonterminating bitstrings (because of irrationality), then there will be one position k where in the bitstring of a is a 1 and the distance to the next 1 in the bitstring of b is minimal, say d. But then it suffices to use $\small n=2^{k+d} \cdot (1+2^{-1} + 2^{-2}+ \ldots 2^{-d})$ to make the 1 in the bitstrings of a and b repeating such that the last new 1 in $\small n \cdot a$ matches that in $\small n \cdot b$ at position $\small k+d$ and we have the previous case and that pair of numbers is not a counterexample but a solution.

c) Because to have a nonterminating bitstring means, we have 1 anywhere we can always find a suitable position k and d in each pair a,b of irrational numbers.
A similar argument may be used for the rational numbers and -maybe- the "transfer" of that argument is really simple but I've not given too much thought into this.

• I cannot understand accurately when the bit happens $1 + 1 = 10$ for $n \cdot a$ or $n \cdot b$. – Yai0Phah Feb 1 '12 at 13:34