Улучшаема ли оценка сверху у функции?

[Sonic86]

$f(x)= \{ \frac{x}{a}\} + \{ \frac{x}{b}\} - \{ \frac{x}{ab}\}$, где $a,b>1$ - натуральные взаимно простые числа, $\{ t \}$ - дробная часть $t$. $f(x)$ оценивается сверху как $f(x) \leqslant 2$. Улучшаема ли эта оценка сверху? Как это доказать?

(Оффтоп)

теги: максимум функции, наибольшее значение

[Руст]

Когда $a,b$ неограниченные, то неулучшаемо. Например $x=a-1,b=a+1$.

[Sonic86]

Руст в сообщении #469946 писал(а):

Когда $a,b$ неограниченные, то неулучшаемо. Например $x=a-1,b=a+1$.

Проверил. Действительно так, спасибо. Разница $d(a,b)$ между максимумом и оценкой сверху примерно похожа на $O(a^{-1})$.

А если пытаться функциями от $a,b$ оценивать? (получается, что эти функции будут стремиться к 2 снизу при $a,b \to + \infty$). Может быть даже получится найти сам супремум?
У меня уже получилось:
$d(2,b)=\frac{1}{2}+1-\frac{1}{2b} \leqslant \frac{3}{2}$
$d(3,b) \leqslant \frac{1}{2}+\frac{4}{3}$
$d(4,b) \leqslant \frac{1}{2}+\frac{6}{4}$
$d(5,b) \leqslant \frac{1}{2}+\frac{8}{5}$

[Руст]

$f(x)$ имеет период $ab$. Рассмотрим вначале целые $x=ay+bz$.
Тогда $f(x)=\{\frac{bz}{a}\}+\{\frac{ay}{b}\}-\{\frac{ay+bz}{ab}\}}$.
Меняем $z$ от 0 до a-1, y от 0 до b-1.
$f(x)=f(y,z), f(y,z+1)=f(y,z)+\frac{b\mod a -1}{a}+0,\pm 1$. Аналогично для y. Поэтому, максимум достигается, когда $f(x)=2-\frac{gcd(b-1,a)}{a}-\frac{gcd(a-1,b)}{b}$. Когда $x$ действительное максимум не достигается, супремум на $\frac{a+b-1}{ab}$ больше максимума по целым х.

[Sonic86]

Руст в сообщении #469987 писал(а):

$f(x)=2-\frac{gcd(b-1,a)}{a}-\frac{gcd(a-1,b)}{b}$

Кажется, общая формула неверна.
Для $f(x)= \{ \frac{x}{3}\} + \{ \frac{x}{5}\} - \{ \frac{x}{15}\}$ ее максимум на целых числах у меня вышел $\frac{14}{15}$ в точке $x=\min \{ 3;5\}-1$, а по формуле получаем $2-\frac{\gcd(5-1,3)}{3}-\frac{\gcd(3-1,5)}{5} = 2-\frac{1}{3}-\frac{1}{5}=1+\frac{7}{15}$.

[Sonic86]

Для простых различных $a,b, b>a$ вышло $f_{\max} \geqslant \left( 2- \frac{1+ b \mod a}{b}\right) \left( 1- \frac{1}{a}\right)$. $x$ - первое подходящее, не превосходящее $b$.

[Sonic86]

Максимум можно вычислить за $O(\ln b), a<b$ операций.
При $f(x)= ab(\{ \frac{x}{a}\} + \{ \frac{x}{b}\} - \{ \frac{x}{ab}\}), x \in \mathbb{N}, 1 \leqslant x \leqslant ab$ ясно, что максимум находится либо среди чисел $x \equiv -1 \pmod a$, либо среди чисел $x \equiv -1 \pmod b$. Будем рассматривать только 1-й случай, 2-й аналогичен.
$x=ak-1$:
$f(ak-1)=b(a-1)+a((ak-1) \mod b)-ak-1=$ $ab-b-1+a(-k+(ak-1) \mod b), 1 \leqslant x \leqslant b$ - достаточно найти максимум скобки.
Положим $a=a_1, b=a_0$, $f_k(x)=-q_kx+e_k (a_kx+c_k) \mod a_{k-1}$, где $q_k \in \mathbb{Q}, e_k = \pm 1, c_k \in \mathbb{Z}, 1 \leqslant x \leqslant a_{k-1}$. Рассмотрим 2-е слагаемое при $x \in \mathbb{R}$ - функция разрывна, распадается на отрезки. Высшими точками $x_h$ функции $e(ax+c) \mod m$ назовем наибольшие значения функции на каждом из этих отрезков. Тогда ясно, что функция $f_k(x)$ имеет точку максимума среди высших точек. Легко найти формулу для высших точек:
1. $e=1 \Rightarrow x_h(t)= \left[ \frac{tm-c-1}{a} \right]$
2. $e=-1 \Rightarrow x_h(t)= \left[ \frac{tm-c-1}{a} \right]+1$
Будем рассматривать случай $e=1$ (2-й случай аналогичен). Для $f_k(x)$ получаем $x_h(t)=\left[ \frac{ta_{k-1}-c_k-1}{a_k} \right]$, причем $1 \leqslant t \leqslant a_k<a_{k-1}$ - интервал уменьшается. Обозначим $a_{k+1}=a_k \mod a_{k-1}$. Подставляем
$f_k(\left[ \frac{ta_{k-1}-c_k-1}{a_k} \right])=-q_k \left[ \frac{ta_{k-1}-c_k-1}{a_k} \right]+e_k (a_k\left[ \frac{ta_{k-1}-c_k-1}{a_k} \right]+c_k) \mod a_{k-1}$
$=-q_k \frac{ta_{k-1}-c_k-1}{a_k} - \frac{(ta_{k-1}-c_k-1) \mod a_k}{a_k}$ $+e_k (ta_{k-1}-c_k-1+c_k-(ta_{k-1}-c_k-1) \mod a_k) \mod a_{k-1}$
$=q_k\frac{c_k+1}{a_k} -q_k\frac{ta_{k-1}}{a_k} - \frac{(ta_{k+1}-c_k-1) \mod a_k}{a_k}$ $+e_k (a_{k-1}-1-(ta_{k+1}-c_k-1) \mod a_k) \mod a_{k-1}$
$=q_k\frac{c_k+1}{a_k} -q_k\frac{ta_{k-1}}{a_k} - \frac{(ta_{k+1}-c_k-1) \mod a_k}{a_k}$ $+e_k(a_{k-1}-1)-e_k(ta_{k+1}-c_k-1) \mod a_k$
$=q_k\frac{c_k+1}{a_k}+e_k(a_{k-1}-1) -q_k\frac{ta_{k-1}}{a_k}$ $-e_k(1+\frac{e_k}{a_k})(ta_{k+1}-c_k-1) \mod a_k$
В полученном выражении отделяем константы, выносим коэффициент перед $X \mod a_k$ - получаем новое выражение $f_{k+1}(t)$ того же вида, для которого нужно найти максимум уже на меньшем отрезке.
Из формулы $a_{k+1}=a_k \mod a_{k-1}$ получаем логарифмическую оценку скорости.

Еще бы смочь выписать явную формулу для максимума - было бы просто прекрасно. Вот только формула страшная будет.