Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
2  
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. –  Frank Science Jan 30 '12 at 9:29
3  
@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. –  Frank Science Jan 30 '12 at 14:31
2  
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
show 3 more comments

3 Answers 3

up vote 11 down vote accepted
+50

Look at the following figure of the checkered $(x,y)$-plane with gridlines at integer $x$'s and $y$'s:

kronecker

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.

share|improve this answer
    
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? –  Frank Science 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. –  Frank Science Feb 2 '12 at 4:39
    
The algebraic constructor proof might not exist. –  Frank Science Feb 2 '12 at 4:45
    
@Frank Science: Concerning your first comment: Yes. –  Christian Blatter Feb 2 '12 at 9:11
add comment

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

share|improve this answer
    
Why -1? The voter might as well point out the mistake. Thanks. –  Frank Science Feb 2 '12 at 3:28
add comment

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.

share|improve this answer
    
I cannot understand accurately when the bit happens $1 + 1 = 10$ for $n \cdot a$ or $n \cdot b$. –  Frank Science Feb 1 '12 at 13:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.