A problem about floor function

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.