I have edited after answering dunrewpp's questions.This could be proved by the following strategy.Assuming M is an integer such that 1/M<d<1/(M-1)denote 1/M by d0We can prove the original problem by replacing d by d0 since d0<d.Let m_0=1, we have S_0=[0,d0] satisfies that if x is in S_0, we can find integer n such that |m_0 x-n|<d0Let m_1=M, we have S_1=.For any x in S_1, we can find integer n such that |m_1 x - n|<d0Note that the S_1 already has S_0 excluded.We can continue this process,For m_k=M^k, we construct set S_k from [0,1]/(S_0 U S_1 U ... U S_{k-1}) such that |m_k x -n|<d0By our construction, [0,1]/(S_0 U S_1 U ... U S_{k-1}) can be represented a union of [i d0^k, (i+1) d0^k) wherei is an integer. Denote the set of integers i as I_k. (Note that, the interval [j d0^{k-1}, (j+1) d0^{k-1}) are divided into M=1/d0 continuous intervals)S_k is defined to be the union [i d0^k, i d0^k +d0^{k+1} ), i in I_kNote that for m_k=M^k=1(d0^k), for any x in [i d0^k, i d0^k +d0^{k+1} ), we have |m_k *x -i|<d_0In our construction, we have seen the area of S_k the d_0 of [0,1]/(S_0 U S_1 U ... U S_{k-1}).We can now compute the area A(S_k) that S_k covers as in the following:A(S_0) = d0A(S_1) = (M-1) d0^2= d0-d0^2 (note that M=1/d0) = (1-A(S_0)) *d0 (this can be inferred directly)...A(S_k) = (1-A(S_{k-1})) * d0=(1-d0)^{k-1}*d0One can see that A(S_0)+A(S_1)+...+A(S_k)+...=1 QuoteOriginally posted by: dunrewppGiven any real number x and any d>0, prove there exist non-zero integers m and n such that |mx-n|<d.You may first assume 0<x<1.If you have any results that are seemingly obvious but whose proofs are not so obvious (a relative term, of course), share them with us. ----------- ----------- ----------- ----------- ----------- -----------Corrected....thanks to kimosabe's observation.

yongge: what's wrong with p=1?

That is only for non-rationals, since denumerator*x - numerator = 0 anyway, hence trivialI do not quite see, what you are going to prove in your 2nd reply (note, that m=n=0as trivial solution is the critic by kimosabe and dunwrepp corrected that)The precise formulation + proof can be found in the Wiki, where it links to PlanetMath(self contained no need to repeat it) or in Schmidt, Diophantine Approximations (whereit is reduced to a Thm of Minkowski on integer points in lattices).

It is overkill for this problem, but Farey sequences give a more detailed picture of how well an irrational number can be approximated.I have added some functions in farey.h and farey.cpp of the utility project here. The implementation given in the Wiki page appears to be incorrect. Hopefully someone with more time than I have will point out how to fix it.

Thanks for your novel approach. But there are problems with your proof, some trivial, some maybe serious. First the trivial problems: There is a typo in one line, quoted here:"Let m_0=M, we have S_1=."I think "m_0" is incorrect and you meant to say: "Let m_1=M". Am I right?Now, on to some not so trivial matters: Consider the following quoted line:"Let m_0=1, we have S_0=[0,d0] satisfies that if x is in S_0, we can find integer n such that |m_0 x-n|<d0".Given that m_0=1, we have |m_0 x-n|=|1*x-n|=|x-n|<d0. So, what is n here? It's obvious that the only n you can be sure of to fit the inequality is that n=0. (For example: for d0=0.00002, n has to be 0). But the statement of the problem claims that m and n are non-zero integers.Here's another problem:It is absolutely not clear what the set S_k is. In fact you are making a logical error. You cannot 'legislate' a definition by endowing the thing you are defining with certain properties. Let me first quote what you wrote:"For m_k=M^k, we define S_k is that set [0,1]/(S_0 U S_1 U ... U S_{k-1}) such that |m_k x -n|<d0".You want S_k to have the property "|m_k x -n|<d0". But that's exactly what you are supposed to prove and you cannot by fiat define things like that. You have to be constructive in your definition of S_k, like exactly the very clear way you did with S_1. Notwithstanding the preceding, I like your approach and I hope you do succeed in coming up with a complete proof.One question: Did you read my (partial) proof from the beginning to end? Did you understand it? Did you find anything lacking?QuoteOriginally posted by: yonggeThis could be proved by the following strategy.Assuming M is an integer such that 1/M<d<1/(M-1)denote 1/M by d0We can prove the original problem by replacing d by d0 since d0<d.Let m_0=1, we have S_0=[0,d0] satisfies that if x is in S_0, we can find integer n such that |m_0 x-n|<d0Let m_0=M, we have S_1=.For any x in S_1, we can find integer n such that |m_1 x - n|<d0Note that the S_1 already has S_0 excluded.We can continue this process,For m_k=M^k, we define S_k is that set [0,1]/(S_0 U S_1 U ... U S_{k-1}) such that |m_k x -n|<d0We can also compute the area A(S_k) that S_k covers as in the following:A(S_0) = d0A(S_1) = (M-1) d0^2= d0-d0^2 (note that M=1/d0) = (1-A(S_0)) *d0 (this can be inferred directly)...A(S_k) = (1-A(S_{k-1})) * d0=(1-d0)^{k-1}*d0One can see that A(S_0)+A(S_1)+...+A(S_k)+...=1 QuoteOriginally posted by: dunrewppGiven any real number x and any d>0, prove there exist non-zero integers m and n such that |mx-n|<d.You may first assume 0<x<1.If you have any results that are seemingly obvious but whose proofs are not so obvious (a relative term, of course), share them with us. ----------- ----------- ----------- ----------- ----------- -----------Corrected....thanks to kimosabe's observation.

I agree with paulptli.QuoteOriginally posted by: paulptliyongge: what's wrong with p=1?QuoteOriginally posted by: yonggeThe wiki entry is not correct.I copied the wiki entry below:for any real number α and any positive integer N, there exists integers p and q such that 1 ≤ q ≤ N and counter example: For N=1, it says that , which can not be true when QuoteOriginally posted by: AVtThis follows from http://en.wikipedia.org/wiki/Dirichlet% ... on_theorem, 1 / (floor(Q) +1) < 1 / Q = d, Q := d

The wiki entry does not make the same assertion as my post. Wiki says:for any real number a and any positive integer N, there exist integers p and q such that 1 <=q <=N and |qa-p|<1/(N+1).Notice that p and q can be any integers, including zero. So, for a=0.00000001 and N=1, q has to be 1 and p has to be zero. In my statement, m and n (which correspond to p and q) are both non-zero. QuoteOriginally posted by: AVtThis follows from http://en.wikipedia.org/wiki/Dirichlet% ... on_theorem, 1 / (floor(Q) +1) < 1 / Q = d, Q := d

What could the phrase "The precise formulation + proof" possibly mean? There is no such thing as "The precise formulation" as if my formulation (as posted) is not precise or my proof is not 'really' good. For any valid claim there are possibly an infinite number of proofs and equivalent formulations. It seems hardly anyone has bothered to go through my proof and has quickly given up reading it by the third line. So be it ...QuoteOriginally posted by: AVtThat is only for non-rationals, since denumerator*x - numerator = 0 anyway, hence trivialI do not quite see, what you are going to prove in your 2nd reply (note, that m=n=0as trivial solution is the critic by kimosabe and dunwrepp corrected that)The precise formulation + proof can be found in the Wiki, where it links to PlanetMath(self contained no need to repeat it) or in Schmidt, Diophantine Approximations (whereit is reduced to a Thm of Minkowski on integer points in lattices).

Nice catch, I was only considering one direction. Still for alpha=1/2, it still needs modifications.QuoteOriginally posted by: paulptliyongge: what's wrong with p=1?

Thanks for this, here are my answers.yes m_1=M. I will also update the my original post.Your question: Given that m_0=1, we have |m_0 x-n|=|1*x-n|=|x-n|<d0. So, what is n here? It's obvious that the only n you can be sure of to fit the inequality is that n=0. My answer: I only consider x in [0,1). if x=1, you can take m=n=1, which result in |1*x-n|=0<d0Your question:You want S_k to have the property "|m_k x -n|<d0". But that's exactly what you are supposed to prove and you cannot by fiat define things like that. You have to be constructive in your definition of S_k, like exactly the very clear way you did with S_1. It will be difficult to write the explicit formula of S_k as the way in defining S_1. It is usually OK to write the definition of a set using property. Here is another try.by our construction, [0,1]/(S_0 U S_1 U ... U S_{k-1}) can be represented a union of [i d0^k, (i+1) d0^k) wherei is an integer. Denote the set of integers i as I_k. (Note that, the interval [j d0^{k-1}, (j+1) d0^{k-1}) are divided into M=1/d0 continuous intervals) S_k is defined to be the union [i d0^k, i d0^k +d0^{k+1} ), i in I_kNote that for m_k=M^k=1/d0^k, for any x in [i d0^k, i d0^k +d0^{k+1} ), we have |m_k *x -i|<d_0In our construction, we have seen the area of S_k the d_0 of [0,1]/(S_0 U S_1 U ... U S_{k-1}).your question:One question: Did you read my (partial) proof from the beginning to end? Did you understand it? Did you find anything lacking?My answer, I haven't read your proof. I will read it now.QuoteOriginally posted by: dunrewppThanks for your novel approach. But there are problems with your proof, some trivial, some maybe serious. First the trivial problems: There is a typo in one line, quoted here:"Let m_0=M, we have S_1=."I think "m_0" is incorrect and you meant to say: "Let m_1=M". Am I right?Now, on to some not so trivial matters: Consider the following quoted line:"Let m_0=1, we have S_0=[0,d0] satisfies that if x is in S_0, we can find integer n such that |m_0 x-n|<d0".Given that m_0=1, we have |m_0 x-n|=|1*x-n|=|x-n|<d0. So, what is n here? It's obvious that the only n you can be sure of to fit the inequality is that n=0. (For example: for d0=0.00002, n has to be 0). But the statement of the problem claims that m and n are non-zero integers.Here's another problem:It is absolutely not clear what the set S_k is. In fact you are making a logical error. You cannot 'legislate' a definition by endowing the thing you are defining with certain properties. Let me first quote what you wrote:"For m_k=M^k, we define S_k is that set [0,1]/(S_0 U S_1 U ... U S_{k-1}) such that |m_k x -n|<d0".You want S_k to have the property "|m_k x -n|<d0". But that's exactly what you are supposed to prove and you cannot by fiat define things like that. You have to be constructive in your definition of S_k, like exactly the very clear way you did with S_1. Notwithstanding the preceding, I like your approach and I hope you do succeed in coming up with a complete proof.One question: Did you read my (partial) proof from the beginning to end? Did you understand it? Did you find anything lacking?QuoteOriginally posted by: yonggeThis could be proved by the following strategy.Assuming M is an integer such that 1/M<d<1/(M-1)denote 1/M by d0We can prove the original problem by replacing d by d0 since d0<d.Let m_0=1, we have S_0=[0,d0] satisfies that if x is in S_0, we can find integer n such that |m_0 x-n|<d0Let m_0=M, we have S_1=.For any x in S_1, we can find integer n such that |m_1 x - n|<d0Note that the S_1 already has S_0 excluded.We can continue this process,For m_k=M^k, we define S_k is that set [0,1]/(S_0 U S_1 U ... U S_{k-1}) such that |m_k x -n|<d0We can also compute the area A(S_k) that S_k covers as in the following:A(S_0) = d0A(S_1) = (M-1) d0^2= d0-d0^2 (note that M=1/d0) = (1-A(S_0)) *d0 (this can be inferred directly)...A(S_k) = (1-A(S_{k-1})) * d0=(1-d0)^{k-1}*d0One can see that A(S_0)+A(S_1)+...+A(S_k)+...=1 QuoteOriginally posted by: dunrewppGiven any real number x and any d>0, prove there exist non-zero integers m and n such that |mx-n|<d.You may first assume 0<x<1.If you have any results that are seemingly obvious but whose proofs are not so obvious (a relative term, of course), share them with us. ----------- ----------- ----------- ----------- ----------- -----------Corrected....thanks to kimosabe's observation.

I read your proof, dunrewpp. I think it is good and I like it.One thing I note that in your proof, how can you guarantee that N=1-b(n,0)+b(n,1)-b(n,2)+-?.+{(-1)^(n)}*b(n,n-1) is nonzero because of so many terms, which might be canceled out.The http://en.wikipedia.org/wiki/Dirichlet% ... on_theorem does not solve the problem that n might be zero (or q in their notation). I think the requirement of n being non-zero is insignificant and meaningless. I can revise my original proof to handle the situation if we really want n to be non-zero as well.here is the sketch.Let m_0=1, we have S_0=[1-d0,1] such that |m_0 *x -1|<d_0 for x in S_0Let m_1=M, S1=, we can find n>0 such that |m_1 *x - n|<d_0 for x in S_1By our construction, [0,1]/(S_0 U S_1 U ... U S_{k-1}) can be represented as a union of [i d0^k, (i+1) d0^k) wherei is an integer. Denote the set of integers i as I_k. (Note that, the interval [j d0^{k-1}, (j+1) d0^{k-1}) are divided into M=1/d0 continuous intervals)S_k is defined to be the union [i d0^k-d0^{k+1}, i d0^k], i in I_kNote that for m_k=M^k=1(d0^k), for any x in [i d0^k - d0^{k+1}, i d0^k ), we have |m_k *x -(i+1)|<d_0By noting that i>=0, we have n=(i+1)>0.This construction is similar as the one I gave before except the intervals are searched from the right side rather than rom the left side.QuoteOriginally posted by: dunrewppQuoteOriginally posted by: dunrewppGiven any real number x and any d>0, prove there exist non-zero integers m and n such that |mx-n|<d.You may first assume 0<x<1.If you have any results that are seemingly obvious but whose proofs are not so obvious (a relative term, of course), share them with us. ----------- ----------- ----------- ----------- ----------- -----------Corrected....thanks to kimosabe's observation.Here?s a (partial) direct proof, using the observation that a remainder is always less than the divisor.Let x(0)=x where 0<x<1. Definition: For any positive integer n, let x(n+1) = 1 - [1/x(n)]*x(n) if x(n)>0, and Let x(n+1)=0 if x(n)=0. Here [.] denotes the greatest integer value function.It can be shown that limit of x(n) is 0 as n approaches infinity. Note that {x(n)} is a decreasing (i.e., non-increasing) sequence of non-negative numbers. So, it must converge. It?s not too difficult to show that it must converge to 0. We will assume this result. Partial Proof:For any n, let a(n)=[1/x(n)], and let b(n,k)=a(n)*a(n-1)*?*a(n-k). Clearly both a(n) and b(n) are positive integers.It easy to see that x(n+1)=1-b(n,0)+b(n,1)-b(n,2)+-?.+{(-1)^(k)}*b(n,k-1)+{(-1)^(k+1)}*b(n,k)*x(n-k).Sox(n+1)=1-b(n,0)+b(n,1)-b(n,2)+-?.+{(-1)^(n)}*b(n,n-1)+{(-1)^(n+1)}*b(n,n)*x(0).Replacing x(0) with x, we havex(n+1)=1-b(n,0)+b(n,1)-b(n,2)+-?.+{(-1)^(n)}*b(n,n-1)+{(-1)^(n+1)}*b(n,n)*x.Let d be any positive number. Since {x(n)} converges to 0, then there exists an integer n such that x(n+1)<d. For this n, let M=(-1)^(n+1)}*b(n,n) and let N=1-b(n,0)+b(n,1)-b(n,2)+-?.+{(-1)^(n)}*b(n,n-1). Then 0<=Mx+N<d.

In my proof I've sort of tacitly assumed x is irrational, since the rational case is too trivial. If N=0 for some n, then x(n+1), being always positive, would have to be bigger than x(n) -- a contradiction since the sequence {x(n)} is strictly decreasing in the case of x being irrational.You said: "... the requirement of n being non-zero is insignificant and meaningless."Well, the requirement is neither insignificant nor meaningless. Certainly, it means something to say that a number is not zero. You've admitted that it is a "requirement", and as requirements go, they are meaningful. It's also significant in the following sense.Consider a straight line y=mx in the xy rectangular coordinate plane. If m is irrational, then the line gets arbitrarily close to some non-orgin lattice point. That is, given any distance d>0, there exists a lattice point (a,b) different from (0,0) such that the distance between the line and the point (a,b) is less than d. The above assertion is equivalent to my original post. A moment's thought will convince you that the requirement that n be different from zero is crucial in this problem.QuoteOriginally posted by: yonggeI read your proof, dunrewpp. I think it is good and I like it.One thing I note that in your proof, how can you guarantee that N=1-b(n,0)+b(n,1)-b(n,2)+-?.+{(-1)^(n)}*b(n,n-1) is nonzero because of so many terms, which might be canceled out.The http://en.wikipedia.org/wiki/Dirichlet% ... on_theorem does not solve the problem that n might be zero (or q in their notation). I think the requirement of n being non-zero is insignificant and meaningless.

one counter example, for x=0, how are you able to find non-zero integers m,n such that |m*0-n|<0.01. I do not think I can find the answer.My revised proof can only cover the region (0,1] after careful thinking as I searched from the right. This is the same reason that my first proof can only cover the region [0,1) since I do the search from the left.You said: That is, given any distance d>0, there exists a lattice point (a,b) different from (0,0) such that the distance between the line and the point (a,b) is less than d. (In order not to confuse people, in the following, I changed your lattice point (a,b) to be (m,n) as in the original problem. And I change the liney=mx to y=x_0*x) However, you only exclude the (0,0) in your consideration. You have not excluded x-axis where n=0 or y-axis where m=0.Using my counter-example, if x_0=0, then y=x_0 x=0 is the x-axis. I do not think I can find a lattice point (m,n) different from x-axis and y-axis such that the distance between the line y=x_0*x and the point (m,n) is less than d.I understand that if x is irrational , the requirement of m and n both being non-zero can be satisfied. My proof covers the whole interval [0,1] except 0, which is rational anyway.For your geometrical representation and your original proof, I still can not understand how you are able to guarantee that n is non-zero (Note, i sort of need a proof that n needs to be nonzero). The requirement of m being non-zero is important is that we can rewrite the approximation to be |x-n/m|<d_0/m, whether n is zero or non-zero is insignificant here.Of course, three proofs (yours, mine, and the http://en.wikipedia.org/wiki/Dirichlet% ... on_theorem) do satisfy the requirement that m is non-zero.QuoteOriginally posted by: dunrewppIn my proof I've sort of tacitly assumed x is irrational, since the rational case is too trivial. If N=0 for some n, then x(n+1), being always positive, would have to be bigger than x(n) -- a contradiction since the sequence {x(n)} is strictly decreasing in the case of x being irrational.You said: "... the requirement of n being non-zero is insignificant and meaningless."Well, the requirement is neither insignificant nor meaningless. Certainly, it means something to say that a number is not zero. You've admitted that it is a "requirement", and as requirements go, they are meaningful. It's also significant in the following sense.Consider a straight line y=mx in the xy rectangular coordinate plane. If m is irrational, then the line gets arbitrarily close to some non-orgin lattice point. That is, given any distance d>0, there exists a lattice point (a,b) different from (0,0) such that the distance between the line and the point (a,b) is less than d. The above assertion is equivalent to my original post. A moment's thought will convince you that the requirement that n be different from zero is crucial in this problem.

dunrewpp, my last reply was not meant as critics towards you.And yes - I admit that I did not study your proof. Sorry so far, since youstate both Natural to be non-zero (for x=a not zero), and that's not coveredby the cited Thm directly.|q*a-p|<1/(N+1) and 1 <= q <=N , so p is allowed to be zero in Dirichlet's Thm.Assume p=0 is the case for all (large) N. Then a is zero:Devide by q, 1 <= q = q(N) to have |a| < 1/(n*q) <= 1/n and n ---> oo(where q(N) = the maximal q in case of formal requirements).Can you agree, that it can be made sound?

Your counterexample cetainly does not counter what my original post says. Recall x>0.As I have said previously, for x rational, the case is too trivial and so I have tacitly assumed x is irrational.It's more confusing to change (a,b) to (m,n). Just leave the line as y=mx, with m irrational. And restate the original problem by using symbols other than "m" and "n".Given that the slope m in the line y=mx is irrational, then there is no need to consider other points on x-axis or y-axis as the line will never hit them at any point other than (0,0).So, your comment quoted below misses the point of what's happening with the line:"However, you only exclude the (0,0) in your consideration. You have not excluded x-axis where n=0 or y-axis where m=0. Using my counter-example, if x_0=0, then y=x_0 x=0 is the x-axis. I do not think I can find a lattice point (m,n) different from x-axis and y-axis such that the distance between the line y=x_0*x and the point (m,n) is less than d."So, to stay focused, I restate and somewhat rephrase the claim about the line y=mx:Consider a straight line y=mx in the xy rectangular coordinate plane. Suppose m is irrational. Then given any distance d>0, there exists a lattice point (a,b) different from (0,0) such that the distance between the line and the point (a,b) is less than d.This calim is equivalent to my original post of this thread.QuoteOriginally posted by: yonggeone counter example, for x=0, how are you able to find non-zero integers m,n such that |m*0-n|<0.01. I do not think I can find the answer.My revised proof can only cover the region (0,1] after careful thinking as I searched from the right. This is the same reason that my first proof can only cover the region [0,1) since I do the search from the left.You said: That is, given any distance d>0, there exists a lattice point (a,b) different from (0,0) such that the distance between the line and the point (a,b) is less than d. (In order not to confuse people, in the following, I changed your lattice point (a,b) to be (m,n) as in the original problem. And I change the liney=mx to y=x_0*x) However, you only exclude the (0,0) in your consideration. You have not excluded x-axis where n=0 or y-axis where m=0.Using my counter-example, if x_0=0, then y=x_0 x=0 is the x-axis. I do not think I can find a lattice point (m,n) different from x-axis and y-axis such that the distance between the line y=x_0*x and the point (m,n) is less than d.I understand that if x is irrational , the requirement of m and n both being non-zero can be satisfied. My proof covers the whole interval [0,1] except 0, which is rational anyway.For your geometrical representation and your original proof, I still can not understand how you are able to guarantee that n is non-zero (Note, i sort of need a proof that n needs to be nonzero). The requirement of m being non-zero is important is that we can rewrite the approximation to be |x-n/m|<d_0/m, whether n is zero or non-zero is insignificant here.Of course, three proofs (yours, mine, and the http://en.wikipedia.org/wiki/Dirichlet% ... on_theorem) do satisfy the requirement that m is non-zero.QuoteOriginally posted by: dunrewppIn my proof I've sort of tacitly assumed x is irrational, since the rational case is too trivial. If N=0 for some n, then x(n+1), being always positive, would have to be bigger than x(n) -- a contradiction since the sequence {x(n)} is strictly decreasing in the case of x being irrational.You said: "... the requirement of n being non-zero is insignificant and meaningless."Well, the requirement is neither insignificant nor meaningless. Certainly, it means something to say that a number is not zero. You've admitted that it is a "requirement", and as requirements go, they are meaningful. It's also significant in the following sense.Consider a straight line y=mx in the xy rectangular coordinate plane. If m is irrational, then the line gets arbitrarily close to some non-orgin lattice point. That is, given any distance d>0, there exists a lattice point (a,b) different from (0,0) such that the distance between the line and the point (a,b) is less than d. The above assertion is equivalent to my original post. A moment's thought will convince you that the requirement that n be different from zero is crucial in this problem.