Date: Mon, 27 Aug 2007 22:28:06 -0700 From: "Max Alekseyev" (maxale(AT)gmail.com) On 10/21/06, David Wilson (davidwwilson(AT)comcast.net) wrote: > This is a chestnut that I am convinced is true, but I cannot prove it. > > Let S and T be sets of real numbers. Call T a divider of S if some element > of T lies strictly between any two distinct elements of S. > > For integer n >= 1, let Fence(n) be the set of all rationals with > denominator n, that is, { k/n : k in Z }. > > For a set of reals S, let f(S) be the least n such that Fence(n) is a divider of > S, if such an n exists. > > Let Recip(n) be the set of all integer reciprocals on [0,1] with denominator > <= n, that is, { 1/b : 1 <= b <= n } > > Let Farey(n) be the set of all rationals on [0,1] with denominator <= n, > that is, { a/b : 0 <= a <= b, 1 <= b <= n } > > Is f(Farey(n)) = f(Recip(n)) for every n? > For real set S, let D(S) be a set of all integers n such that Fence(n) is a divider of S. Rustem Aidagulov gave a sketch of the proof (it can be found in Russian at http://lib.mexmat.ru/forum/viewtopic.php?p=37669#37669 ) that for every positive integer n, D(Farey(n)) = D(Recip(n)), implying, in particular, that the minimum elements of D(Farey(n)) and D(Recip(n)) coincide, i.e., f(Farey(n)) = f(Recip(n)). Below I will give a complete proof of this result, filling gaps in Rustem's proof. Let us denote (for short) R(n) = Recip(n) = { 1/b : 1 <= b <= n } Q(n) = Fence(n) = { k/n : k in Z } F(n) = Farey(n) = { a/b : 0 <= a <= b, 1 <= b <= n } Lemma 1. If m>LCM(p,q) then Q(m) is a divider for any two non-equal fractions with denominators p and q respectively. Proof. Let a/p < b/q be two non-equal fractions (where a,b are integer). Let r=LCM(p,q) then the number r*(b/q - a/p) is integer >= 1 and m*(b/q - a/p) > r*(b/q - a/p) >= 1, implying that there is an integer k such that m*a/p < k < m*b/q. Therefore, a/p < k/m < b/q. QED Lemma 2. Q(m) is a divider of R(n) if and only if there exist integers s_1, s_2, ..., s_{n-1} such that m/n < s_{n-1} < m/(n-1) < ... < m/2 < s_1 < m. Proof easily follows from the definition of "divider". Lemma 3. If m=m_1*m_2 where m_1<=m_2<=n then Q(m) is NOT a divider of R(n). Proof. Suppose that Q(m) is a divider of R(n). If m_1=m_2=k then according to Lemma 2, there exists an integer strictly in between of m/(k+1)=k^2/(k+1) and m/k=k. But that is impossible since k-1 < k^2/(k+1) < k. For m_1(n-k)(n-k-1), i.e., (n-k)(n-k-1) < m < (n-k)(n-k+1) (*) Note that Lemma 3 forbids the case of equality m=(n-k)(n-k+1). Solution to this pair of quadratic inequalities (*) is (2n-1-sqrt(4m+1))/2 < k < (2n+1-sqrt(4m+1))/2 The difference between the upper and the lower bounds is 1, thus, there exists integer k satisfying this inequality as soon as 4m+1 is not a perfect square. In this case we can derive k = n - [(sqrt(4m+1)+1)/2] Denote b = [sqrt(4m+1)] = [2*sqrt(m)] (since 4m+1 is not a perfect square). Then k = n - [(b+1)/2] and [sqrt(m)] = [b/2]. Lemma 4. If b is even then b=2(n-k) and [sqrt(m)]=n-k. If b is odd then b=2(n-k)-1 and [sqrt(m)]=n-k-1. Proof. If b is even then b = [2*sqrt(m)] = 2*[sqrt(m)] and k = n - [(b+1)/2] = n - b/2 = n - [sqrt(m)], implying that b = 2(n-k) and [sqrt(m)] = n-k. If b is odd then b = [2*sqrt(m)] = 2*[sqrt(m)]+1 and k = n - [(b+1)/2] = n - (b+1)/2 = n - [sqrt(m)] - 1, implying that b=2(n-k)-1 and [sqrt(m)] = n-k-1. QED Theorem 1. Let m<=n(n-1). Then m belongs to D(R(n)) if and only if m=n*(b-n)+r where 0=b-n+1>=n-k. From the proof of Theorem 1 it follows that [m/q] = [m/(n-(n-q))] = [m/n]+n-q = b-n+n-q = b-q. QED Lemma 6. If m belongs to D(R(n)) and m=n*(b-n)+r with 0 ((b-2n)/2)^2. Proof. >From the definition of b we have b^2 = [2*sqrt(m)]^2 < 4*m = 4*(n(b-n)+r), implying that 4*r > b^2 - 4*b*n + 4*n^2 = (b-2n)^2. QED Theorem 2. For n>1, f(R(n)) = n*(n-t) + [t^2/4] + 1 where t=[sqrt(4*n-5)]=[sqrt(4*n-7)]. Proof. Let m be an element of D(R(n)) and 4m = b^2 + a where 01, D(R(n)) = D(F(n)). Proof. It is clear that D(F(n)) is a subset of D(R(n)). Therefore, to prove the theorem it is enough to show the converse, i.e., that for every m, if Q(m) is a divider of R(n) then Q(m) is a divider of F(n). Assume that there exists such m that Q(m) is a divider of R(n) but not of F(n). Then m=n*(b-n)+r (by Theorem 1) and there exist consecutive elements p1/q1 < p2/q2 of F(n) (hence, q1*p2-q2*p1=1) with no element of Q(m) in between of them. Then q1*q2>=m and [m*p1/q1]=[m*p2/q2]. Switching if necessary to p1'/q1'=(q2-p2)/q2 < (q1-p1)/q1=p2'/q2', we assume that q1=m>n*(b-n), we have q1>n*(b-n)/q2>=b-n and similarly q2>b-n. Then Lemma 5 implies that [m/q1]=b-q1 and [m/q2]=b-q2. Therefore, r2 = m mod q2 = m - q2*(b-q2) = m - q2*b +q2^2 = n*(b-n) - q2*b +q2^2 = r + (n-q2)*(b-n-q2). Dividing (**) by q2, we have b - q1 + s = [m/q1] + s <= m/q1 + s < q2, implying that s < -b + q1 + q2. (***) Note that q2*p1-q1*p2=1 is equivalent to p2*(q2-q1)=1+q2*(p2-p1), implying that m*p2*(q2-q1) = m + m*q2*(p2-p1) and s*(q1-q2) mod q2 = m*p2*(q2-q1) mod q2 = (m + m*q2*(p2-p1)) mod q2 = r2 = m - q2*b +q2^2. Multiplying (***) by q2-q1>0, we have s*(q2-q1) < -b*q2 + b*q1 + q2^2 - q1^2, implying that r2 = s*(q1-q2) mod q2 < s*(q1-q2) < -b*q2 + b*q1 + q2^2 - q1^2. Therefore, r + (n-q2)*(b-n-q2) = r2 < -b*(q1-q2) + q1^2 - q2^2 and r < (n-q1)*(n+q1-b) <= ( ((n-q1) + (n+q1-b))/2 )^2 = ((2n-b)/2)^2, a contradiction to Lemma 6. This contradiction proves that for every m such that Q(m) is a divider of R(n), Q(m) is also a divider of F(n). QED This shows that A001000 and A071111 agree except for the initial term in A001000.