открытая проблема: разделители обратных величин и ряда Фарея

[maxal]

Задача из рассылки SeqFan.

Пусть A и B - подмножества множества действительных чисел. Будем говорить, что A разделяет B, если для любых двух элементов $b_1<b_2$ множества B найдется элемент $a\in A$ такой, что $b_1<a<b_2.$

Определим множества:

$$Q_n = \left\{ \frac{k}{n} : k\in\mathbb{Z} \right\}$$

$$R_n = \left\{ \frac{1}{m} : m=1,2,\dots,n \right\}$$

$$F_n = \left\{ \frac{k}{m} : m=1,2,\dots,n,\ k=0,1,\dots,m \right\}$$

- ряд Фарея порядка n.

Пусть $f(n)$ равно минимальному целому $m$ такому, что $Q_m$ разделяет $R_n$.
Пусть $g(n)$ равно минимальному целому $m$ такому, что $Q_m$ разделяет $F_n$.

Две задачи:

1) Найти явную формулу для f(n).

2) (открытая проблема) Доказать или опровергнуть, что $f(n)=g(n)$ для всех $n>1$.

[Руст]

Записывая неравенство:
$\frac 1n <\frac{s_n}{f(n)}<\frac{1}{n-1}<\frac{s_{n-1}}{f(n)}<...$
и рассматривая разность через l членов получаем необходимое неравенство:
$f(n)\ge n^2-1-n(\frac{n-2}{l}+l-1), l=[0.5+\sqrt{n-2}], f(1)=2,f(2)=3.$
Сверху оценка получается f(n)<=g(n)<=n(n-1)+1.

[maxal]

Руст писал(а):

получаем необходимое неравенство:

В каком смысле "необходимое"? Как из него получить формулу для f(n)?

Руст писал(а):

$f(n)\ge n^2-1-n(\frac{n-2}{l}+l-1), l=[0.5+\sqrt{n-2}], f(1)=2,f(2)=3.$

Дык это нижняя оценка, а требуется найти формулу.

[Руст]

Да я поленился дать точное значение.
Лемма 1. Если m>LCM(m1,m2), то Q(m) разделяет любые дроби со знаменателями m1 и m2.
Доказательство.
Найдём s, такой, что $\frac{k_1}{m_1}<\frac{s}{m}<\frac{k_2}{m_2}.$
Пусть $s=[\frac{mk_2-1}{m_2}], \ \ \frac{s}{m}<\frac{k_2}{m_2}$, остается проверить левое неравенство:
$s=[\frac{mk_2-1}{m_1}]=\frac{LCM(m_1,m_2)}{m_2}k_2+[\frac{k_2(m-LCM(m_1,m_2))-1}{m_2}]\ge \frac{mk_1}{m_1}+1.$

Следствие. $f(n)\le g(n)\le n(n-1)+1.$

Пусть Q(m) разделяет R(n). Тогда существует строго убывающая последовательность натуральных чисел:
$\frac{m}{n}<s_{n-1}<\frac{m}{n-1}<s_{n-2}<...,<s_1<m.$
Это условие есть запись условия разделения.
Отсюда получается $\frac{m}{n-k}>s_{n-k+1}\ge s_n+k=k=[\frac mn ].$
Учитывая пределы изменения остатков r(i) при делении m на i, получаем:
$m\ge n(n-k)+r_n +n\frac{r_{n-k}-r_n}{k}.$
Так как последнее слагаемое целое, то максимальная нижняя оценка получается, когда $k=[\sqrt{n-2}],$ или $r_n-r_{n-k}=k(k+1)$
т.е. $m\ge n^2-an+[\frac{a^2+4}{4}], a=[\sqrt{4n-7}].$
Остаётся проверить, что эта оценка точная, т.е. $f(n)=n^2-an+[\frac{a^2+4}{4}], a=[\sqrt{4n-7}].$
Из вышесказанной леммы следует, что при таком m Q(m) разделяет числа 1/(n-l) и 1/(n-l-1) при l>=k=[a/2]. То, что оно разделяет такие числа при l<k следует из построения. Всё это при n>2. Для малых n а(1)=п(1)=2, f(2)=g(2)=3.
В соответствии с леммой, f(n) разделяет все числа, для которых LCM меньше его. Остается проверять только числа с взаимно простыми знаменателями, произведение которых не меньше f(n). Вроде несложно проверить, что Q(m), m=f(n) разделяет и такие числа, так что
g(n)=f(n). Поэтому вопрос, с чего вы считаете, что это открытый вопрос?

[maxal]

Руст писал(а):

т.е. $f(n)=n^2-an+[\frac{a^2+3}{4}], a=[\sqrt{4n-7}].$

Увы, но эта формула начинает врать с некоторого n. Например, для $n=11$ она дает $64$, в то время как $f(11)=65$.

Руст писал(а):

Вроде несложно проверить, что Q(m), m=f(n) разделяет и такие числа, так что
g(n)=f(n).

Так вроде или несложно? Если несложно, то продемонстрируйте, пожалуйста.

Руст писал(а):

Поэтому вопрос, с чего вы считаете, что это открытый вопрос?

Вопрос назван открытым потому как он назван таковым как минимум в паре мест в интернете. Например, он уже несколько лет высказан как гипотеза в OEIS и оставлен пока без ответа.

[Руст]

maxal писал(а):

Руст писал(а):

т.е. $f(n)=n^2-an+[\frac{a^2+3}{4}], a=[\sqrt{4n-7}].$

На самом деле из вычисления следовала f(n)=(n-k)(n-k)+1, если a=2k - чётное и f(n)=(n-k)(n-k-1)+1, если a=2k+1 нечётное. Ошибку допустил на 1/4 при единой записи.

Руст писал(а):

Вроде несложно проверить, что Q(m), m=f(n) разделяет и такие числа, так что
g(n)=f(n).

Так вроде или несложно? Если несложно, то продемонстрируйте, пожалуйста.

Руст писал(а):

Поэтому вопрос, с чего вы считаете, что это открытый вопрос?

Я проверил кондовым образом это для случая, когда а чётное, аналогична проверка и для нечётного случая. Вчера, когда уже лёг, у меня промелькнуло более оригинальное доказательство даже более общего утверждения, а именно:
Q(m) разделяет F(n) тогда и только тогда, когда он разделяет R(n).
При этом, из этих множеств можно даже исключить 0 и 1, они ничего не меняют.

[Руст]

Руст писал(а):

maxal писал(а):

Руст писал(а):

т.е. $f(n)=n^2-an+[\frac{a^2+3}{4}], a=[\sqrt{4n-7}].$

На самом деле из вычисления следовала f(n)=(n-k)(n-k)+1, если a=2k - чётное и f(n)=(n-k)(n-k-1)+1, если a=2k+1 нечётное. Ошибку допустил на 1/4 при единой записи.

Руст писал(а):

Вроде несложно проверить, что Q(m), m=f(n) разделяет и такие числа, так что
g(n)=f(n).

Так вроде или несложно? Если несложно, то продемонстрируйте, пожалуйста.

Руст писал(а):

Поэтому вопрос, с чего вы считаете, что это открытый вопрос?

Я проверил кондовым образом это для случая, когда а чётное, аналогична проверка и для нечётного случая. Вчера, когда уже лёг, у меня промелькнуло более оригинальное доказательство даже более общего утверждения, а именно:
Q(m) разделяет F(n) тогда и только тогда, когда он разделяет R(n).
В принципе и это можно доказать кондовым способом (громоздко и нудно) предварительно выяснив, что при m>=f(n) Q(m) разделяет R(n) за исключением только случаев, когда m является произведением двух взаимно простых чисел, не превосходящих n.
Оригинальную идею доказателства уже успел забыть к утру.
При этом, из этих множеств можно даже исключить 0 и 1, они ничего не меняют.

[maxal]

Руст писал(а):

maxal писал(а):

Руст писал(а):

т.е. $f(n)=n^2-an+[\frac{a^2+3}{4}], a=[\sqrt{4n-7}].$

На самом деле из вычисления следовала f(n)=(n-k)(n-k)+1, если a=2k - чётное и f(n)=(n-k)(n-k-1)+1, если a=2k+1 нечётное. Ошибку допустил на 1/4 при единой записи.

Ага, теперь вроде все верно.

Руст писал(а):

Вчера, когда уже лёг, у меня промелькнуло более оригинальное доказательство даже более общего утверждения, а именно:
Q(m) разделяет F(n) тогда и только тогда, когда он разделяет R(n).

И чем оно "более обще"? В одну сторону это тривиальное утверждение, а в другую - в чистом виде задача 2 как она была представлена в исходном сообщении по данной теме.
А вот "более оригинальное доказательство" с удовольствием выслушаю.

[Руст]

maxal писал(а):

И чем оно "более обще"? В одну сторону это тривиальное утверждение, а в другую - в чистом виде задача 2 как она была представлена в исходном сообщении по данной теме.
А вот "более оригинальное доказательство" с удовольствием выслушаю.[/quote]
Оно более обще чем g(n)=f(n), так как доказывает, что Q(m) разделяет F(n) при разделении R(n) не только для случая m=f(n), а вообще для всех m, разделяющих R(n). Как я уже сказал, его можно доказать и кондовым образом, выяснив случаи, m>=f(n), когда Q(m) не разделяет R(n) и проверив для всех дробей с взаимно простыми знаменателями m1,m2 произведение которых не меньше m, что между ними всегда найдётся дробь со знаменателем m.

[Руст]

Пусть $Q(n)=\{\frac kn \ |1\le k<n\}, \ R(n)=\{\frac 1k \ |2\le k\le n \}, \ F(n)=\{\frac{a}{b} \ |1\le a<b\le n \}.$
Здесь при n=1 получаются пустые множества.
Очевидны следующие леммы:
Лемма 1. Если m>LCM(m1,m2), то Q(m) разделяет два числа со знаменателями m1 и m2.
Доказательство приведено выше. Верно и наоборот, если Q(m) разделяет любые два (не равных естественно) числа со знаменателями m1 и m2, то m>LCM(m1,m2).
Лемма 2. Q(m) разделяет R(n) тогда и только тогда, когда существует такая строго убывающая последовательность натуральных чисел: $s_1>s_2>...>s_n\ge 0$, что $s_n<\frac mn <s_{n-1}<\frac{m}{n-1}<...<\frac m2 <s_1.$
Это фактически перезапись с умножением на m определения того, что Q(m) разделяет R(n).
Лемма 3. Если m=m1*m2, n>=m1>=m2<n, то Q(m) не разделяет R(n).
Доказательство. Если m1=m2=k, то k<n и должно быть $\frac{k^2}{k+1}<s_k<k$, что невозможно, так как $\frac{k^2}{k+1}>k-1.$ Пусть m1>m2.
Рассмотрим часть неравенств из леммы 2:
$\frac{m}{m_1}=m_2<s_{m_1-1}<...<s_{m_2}<m1.$
В интервале (m2,m1) имеется всего m1-m2-1 натуральных чисел, а согласно требованию о разделимости должно быть как минимум m1-m2. Это означает, что Q(m) не разделяет R(n).
Определим теперь множество тех m, которые разделяют R(n) через QR(n), аналогично QF(n).
Очевидно, что QF(n) подмножество QR(n) (здесь отношение "разделяет" есть соответствие Галуа). Оригинальное доказательство совпадения этих множеств я уже забыл. Поэтому, приведу кондовое доказательство, вычисляя непосредственно эти множества. Так как из леммы 1 следует, что при QF(n) содержит любое число m>n(n-1), а из леммы 3 следует, что любое число <=n не принадлежит QF(n), то в определении этих множеств достаточно ограничиться только натуральными числами из интервала (n,n(n-1)). При n<=2 этот интервал пуст. Поэтому в дальнейшем ограничимся случаем n>2 и опишем множество QR(n) чисел m из этого интервала, разделяющих R(n).
Определим число b(m) и k(m): $b(m)=[\sqrt{4m+1}], k(m)=n-[\frac{b(m)+1}{2}]$
Если m принадлежит QR(n) и число b(m) чётное, то (n-k(m))^2<m<(n-k(m))(n-k(m)+1), если b(m) нечётное, то (n-k(m)-1)(n-k(m))<m<(n-k(m))^2.
Рассмотрим неравенство из леммы 2:
$s_n<\frac{m}{n}<s_{n-1}<...<\frac{m}{n-k(m)}<s_{n-k(m)-1}.$
Отсюда следует, что [m/n]<=[m/(n-k(m))]-k[m]. А это возможно только в случае, когда
$[\frac mn ]+k(m)=[\frac{m}{n-k(m)}]$.
Пусть r(m) определяется по формуле: $r(m)=m-[(n-\frac{b(m)}{2})^2].$ Тогда наше условие эквивалентно тому, что
(1) $r(m) \ge 1, \ \ r(m)+[\frac{b(m)^2}{4}]\le n-1.$
Легко проверить, что при этом условии Q(m) разделяет R(n), так как это условие обеспечивает разделимость до дроби 1/(n-k(m))), а дальше очевидно согласно лемме 1.
Отсюда получается, что $b(m)\le a=[\sqrt{4n-7}]$ а минимальный элемент этого множества f(n) есть $f(n)=[(n-\frac a2 )^2]+1.$
Множество QR(n) имеет всего

$$(a-1)(n-1)-\sum_{k=2}^a [\frac{k^2}{4}]=(a-1)(n-1)+[(a-1)/2]/4-\frac{a(a+1)(2a+1)-6}{24}.$$

В продолжении покажу, что QF(n) то же множество, что и QR(n).

[Руст]

Закроем эту тему. Ранее доказали, что Q(m) при m<n(n-1) разделяет R(n) тогда и только тогда, когда m=n(n-b)+r и $\frac{b^2}{4}<r\le n-1.$
Пусть при этом Q(m) не разделяет числа $\frac{k_1}{m_1}>\frac{k_2}{m_2}, m_1=n-a_1,m_2=n-a_2.$
Тогда есттественно
(2) $m_1m_2>m, k_1m_2-k_2m_1=1$ и должно быть
(3)$[\frac{mk_1}{m_1}]=[\frac{mk_2}{m_2}].$
Докажем, что эти условия не выполнимы.
Легко вычисляются остатки при делении m на знаменатели: $r_i=r-a_i(b-a_i),i=1,2$ (здесь используется, что целая часть [m/mi]=2n-b-mi ). Условие (3) с учётом (2) приводится к виду sm1+m<m1m2 или
(4) $a_1+a_2+s<b, \ s=r_2k_2-m_2[\frac{r_2k_2}{m_2}],$
т.е. s - остаток при делении k2m на m2.
Переписывая (2) в виде $k_2(a_1-a_2)=1+(k_2-k_1)m_2=1(mod \ m_2)$ и умножая (4) на |a1-a2| получаем:
$s_2|a_1-a_2|<|b(a_1-a_2)-a_^2+a_2^|.$
Если a1>a2 это приводит к неравенству r2<b(a_1-a2)-a1^2+a2^2 или
$r<b(a_1-a_2)-a_1^2+a_2^2+a_2(b-a_2)=a_1(b-a_1)$, что противоречит другим условиям a1+a2<b, r>b^2/4. Аналогично (чуть сложнее) проверяется случай a1<a_2. На самом деле этот случай можно не рассматривать, переходя к дополнениям к 1, т.е. числам: $\frac{k_1}{m_1}>\frac{t}{m}>\frac{k_2}{m_2}$ из последнего случая сопоставляется $\frac{m_1-k_1}{m_1}<\frac{m-t}{m}<\frac{k_2}{m_2}$ из первого случая, так как роль k2/m2 играет (m1-k1)/m1, соответственно a1<a2 интерпретируется (после смены ролей), как a1>a2.
Это противоречие доказывает, что MR(n)=MF(n) (т.е. Q(m) разделяет F(n) тогда и только тогда, когда он разделяет R(n)), тем более равны их минимальные элементы f(n)=g(n).

[maxal]

Я аккуратно прошелся по решению и получил следующее:

При $m<n(n-1)$ множество $Q(m)$ разделяет $R(n)$ тогда и только тогда, когда $m=n(b-n)+r,$ где $0<r<n,$ и ни одно из чисел $m,\ 4m+1$ не является полным квадратом.

Обращаю внимание на то, что в скобках стоит именно $(b-n),$ а не $(n-b).$ Формула $m=n(n-b)+r$ не может быть верной даже для минимального элемента $m=f(n),$ так как значение $b$ получается большим чем $n$, и левая правая часть формулы становится отрицательной.

Далее, "остатки" $r_i$ получаются такими: $r_i = r + a_i (b-a_i)$ (опять обращаю внимание на знаки). Собственно, "остатками" их называть нельзя потому, что возможен вариант когда $r_i > m_i.$ С учетом этих поправок предствленное доказательство равенства QF(n)=QR(n) разваливается.

[Руст]

Руст писал(а):

Определим число b(m) и k(m): $b(m)=[\sqrt{4m+1}], k(m)=n-[\frac{b(m)+1}{2}]$
Если m принадлежит QR(n) и число b(m) чётное, то (n-k(m))^2<m<(n-k(m))(n-k(m)+1), если b(m) нечётное, то (n-k(m)-1)(n-k(m))<m<(n-k(m))^2.
Рассмотрим неравенство из леммы 2:
$s_n<\frac{m}{n}<s_{n-1}<...<\frac{m}{n-k(m)}<s_{n-k(m)-1}.$
Отсюда следует, что [m/n]<=[m/(n-k(m))]-k[m]. А это возможно только в случае, когда
$[\frac mn ]+k(m)=[\frac{m}{n-k(m)}]$.

Такое определение, точнее надо было $b(m)=2n-[\sqrt{4m+1}]$ я давал, как более удобную при вычислении минимального элемента разделяющего R(n). Во второй части я даже забыл о таком определении и пользовался следующем: $b=b(m,n)=n-[\frac mn], r=r(m,n)=m-n(n-b)=m-n[\frac mn ]$. При выполнении необходимых условий разделения эти определения должны совпасть. Тем не менее, даю новое доказательство для последнего определения.
Пусть m<n^2 и n>2. Определим b(m)=n-[m/n], k(m)=[(b(m)+1)/2]. Так как при b=n, m<n и нет разделения, то можно считать b<n. Тогда из условия разделения R(n):
$s_n<\frac mn <s_{n-1}<...<\frac{m}{n-k(m)}<s_{n-k-1}$
получаем $s_n<\frac{m}{n}, s_n\le s_{n-k}-k, s_{n-k}<\frac{m}{n-k}.$
Рассматривая отдельно случаи чётности и нечётности b, получаем, что это возможно только в случае, когда $m>(n-\frac b2 )^2, (\frac b2 )^2<r=r(m,n)=m-n[\frac{m}{n}]\le n-1.$
Т.е. это необходимое условие разделимости R(n) через Q(m). В доказательстве второй части, что это условие достаточное для разделимости F(n) я и так пользовался с таким определением b(m,n) и поэтому не требуется ничего менять.

[maxal]

maxal в сообщении #37280 писал(а):

1) Найти явную формулу для f(n).

Кстати, эта задача под номером 2272 предлагалась в журнале Crux Mathematicorum with Mathematical Mayhem в октябре 1997 года. Её решение было опубликовано в ноябрьском номере 1998 года:
https://cms.math.ca/crux/v24/n7/page427-448.pdf
Её решили лишь два студента.