Chestnut

[Max Alekseyev]

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<m_2, according to Lemma 2, there should exist integers s_i such that
such that m_1=m/m_2 < s_{m_2-1} < ... < s_{m_1} < m/m_1=m_2, i.e.,
strictly in between of m_1 and m_2 there should be m_2-m_1 integers
that is impossible.
QED

Now, let us explicitly compute the set D(R(n)).

It follows from Lemma 1 that every integer greater than n(n-1) belongs
to both D(R(n)) and D(F(n)).
Let m be an element of D(R(n)) such that m<=n(n-1).

Let k be the largest number such that m>(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<r<n and neither of m and 4m+1 is a square.
Proof.
Since for every t=n-k,n-k+1,...,n,
m/t - m/(t+1) = m/(t(t+1)) <= m/((n-k)(n-k+1)) < 1
(i.e., m/t and m/(t+1) may have at most one integer in between),
it follows that Q(m) is a divider of R(n) if and only if neither of
m/(n-k) and m/n is integer and [m/(n-k)] = [m/n] + k. Indeed, this
condition implies that there is an integer strictly in between of any
two consecutive elements of m/n, m/(n-1), ..., m/(n-k) while Lemma 1
implies the same for any two consecutive elements of m/(n-k),
m/(n-k-1), ..., m/1.
Let r=m-n(b-n). Then m=n(b-n)+r and [m/n]=b-n+[r/n].
If b is even then (n-k)^2<m<(n-k)(n-k+1) and thus [m/(n-k)]=n-k=b-n+k.
If b is odd then (n-k)(n-k-1)<m<(n-k)^2 and thus [m/(n-k)]=n-k-1=b-n+k.
Therefore, the equality [m/(n-k)]=[m/n]+k holds if and only if 0<=r<n.
To make m/n non-integer, r must be greater than 0. On the other hand,
it is easy to verify that m/(n-k) is integer iff m or 4m+1 is a
square.
QED

Lemma 5. If m belongs to D(R(n)) and q is such that b-n<q<=n then [m/q]=b-q.
Proof.
Note that q>=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<r<n, then r >
((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 0<a<2b (values
a=0 and a=2b are forbidden since they turn m or 4m+1 into a perfect
square). Theorem 1 implies that m=n(b-n)+r where 0<r<n. Then
4m=4n(b-n)+4r and
b^2 - 4nb + 4n^2 - 4r + a = 0.
This quadratic equation (with respect to b) has the following solution:
b = 2n +- sqrt(4r - a)
The minimum value of m corresponds to the minimum value of b, which is
2n-t where
t^2 = 4r-a <= 4(n-1)-1 = 4n-5
To minimize b, let t=[sqrt(4n-5)] (note that
[sqrt(4n-5)]=[sqrt(4n-6)]=[sqrt(4n-7)] for any n, since neither of
4n-5 or 4n-6 can be a perfect square). As soon as b is fixed, the
minimum value of m corresponds to the minimum value of a, which is a=4
if t is even and a=3 if t is odd. Then b=2n-t, r=(t^2+a)/4=[t^2/4]+1,
and m=n*(n-t) + [t^2/4] + 1.

Theorem 3. For any integer n>1, 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<q2.

The equality [m*p1/q1]=[m*p2/q2] is equivalent to
(m*p1-(m*p1 mod q1))*q2 = (m*p2-(m*p2 mod q2))*q1
or
m*p1*q2 - (m*p1 mod q1)*q2 = m*p2*q1 - (m*p2 mod q2)*q1
or
m + (m*p2 mod q2)*q1 = (m*p1 mod q1)*q2.
Let s = m*p2 mod q2. Then
m + s*q1 = (m*p1 mod q1)*q2 < q1*q2.   (**)

Since q1*q2>=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

On 10/21/06, David Wilson <davidwwilson at comcast.net> wrote:
>
>
>
>
> This is a chestnut that I am convinced it is true, but I cannot prove it. I
> have posed it on math-fun occasionally, and never got an answer. I would
> like to see it posed to some better minds that some of you might know, e.g,
> JHC or other number theorist.
>
> 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 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 real set 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?
>
> The apparently common sequences a(n) = f(Recip(n)) =? f(Farey(n)) is in the
> OEIS, I cannot find it in the short time I have.



Dear Seqfans, I will be away from email until about mid-September.
I probably will not be able to process all the Comments
that are waiting before I leave.
Neil