Целые точки в окрестностях

[Nartu]

Предисловие
Неопределился с разделом. Потом определим.

Некоторые замечания
Это не домашнее задание, а просто задача собственного(почти) производства, на которую у меня нет решения, а могло подойти разделу для ребусов, что ли...

Собственно, вот общий случай

$$\left\lvert c_0+\sum\limits_{i=1}^{k}{c_ix_i}\right\rvert \leqslant\varepsilon$$

Где $x_i$ - целые, $c_i \in\mathbb{R}\backslash\mathbb{Q}$, $c_0\in(\mathbb{R}\backslash\mathbb{Q})\cup\{0\}$, $k$ - конечное (задано),$\varepsilon\in\mathbb{R}$ (задано).
Мой (частный) случай

$$\left\lvert c_0+c_1x+c_2y\right\rvert\leqslant\varepsilon$$

Это можно преобразить в

$$y=\lambda x+\mu+\xi,\quad\xi\in\ [-\varepsilon,\varepsilon]$$

$$\lambda=\frac{c_1}{c_2},\quad \mu=\frac{c_0}{c_2} $$

То есть это окресность $\mathrm{U}(y, \varepsilon)\subset\mathbb{R}^2$ . Задача - найти целые точки, что попадают внутрь.
Мой главный вопрос: "Можно ли обойтись без компьютера?" (Ну, кроме вычисления цепных дробей.) Это вопрос не так на решение, как на интуицию специалистов. Голосования я не хочу!

Когда $\mu=0$ решение таково:
1) Найти рациональные приближения $\frac{p}{q}$ для \lambda
2) Построить прямые $y=\frac{p}{q}x$
3) Найти (разные)целые точки на их кусках из \matrm{U}(y, \varepsilon).
4)Это и будут искомые точки. Их вид: $(qn, pn),\;n\in \left[\left\lfloor\frac{-\varepsilon}{q(\lambda-\frac{p}{q}) }\right\rfloor, \left\lfloor\frac{\varepsilon}{q(\lambda-\frac{p}{q}) }\right\rfloor\right]\supset \mathbb{Z} $

Затруднения у меня в случае $\mu\ne0$

[demolishka]

Будем рассматривать (задачу неоднородного линейного приближения)

Nartu в сообщении #1414618 писал(а):

$$\left\lvert c_0+c_1x+c_2y\right\rvert\leqslant\varepsilon$$

Поделим все на $c_{2}$. Обозначим $\alpha:=\frac{c_{1}}{c_{2}}$, $\beta:=-\frac{c_{0}}{c_{2}}$. Рассмотрим

$$|\alpha x + y - \beta| \leq \frac{1}{n}.$$

Если хочется решать задачу для любых $\beta$ и $n$, то существенно потребовать иррациональности $\alpha$ (т. е. несоизмеримости $c_{1}$ и $c_{2}$). В случае $\beta \not= 0$ цепные дроби для поиска решений мало помогут. Не знаю можно ли в общем случае предложить что-то кроме перебора (см. ниже). Конечно достаточно дробной частью $\alpha x$ приблизить дробную часть $\beta$ и тогда $y$ определяется однозначно. Это приводит к задаче на окружности: сделать величину $|\alpha x - \beta|_{1}$ малой в смысле метрики $|\cdot|_{1}$ на окружности $\mathbb{T}^{1} = \mathbb{R}/\mathbb{Z}$.

Например, можно действовать как при доказательстве плотности иррационального поворота окружности: разбить окружность (длины 1) на $n$ полудуг длины $1/n$; тогда по принципу Дирихле точка $\alpha x$ при целых $0 \leq x \leq n$ хотя бы дважды попадет в одну из этих полудуг (пусть это происходит при $x=x_{1}$ и $x=x_{2}$). А дальше уже можно идти с шагом $\alpha (x_{1}-x_{2})$ (строго меньше $1/n$), пока не придем в полудугу, содержащую $\beta$. Будем считать, что $h = \{ \alpha (x_{1}-x_{2}) \} > 0$ и $\beta \in [0,1]$. Осталось найти $m$ так, что $m h \leq \beta < m (h+1)$. Ответ: $x = m(x_{1}-x_{2})$. Формально мы справились за $n$ итераций (на деле же все упирается в точность вычислений). Это лучше тупого перебора $x$ от 0 до упора и вот почему.

Можно показать, что если $\alpha$ диофантово с показателем $\nu>0$, т. е. для некоторого $C>0$ и всех целых $p$ и натуральных $q$ выполнено

$$|\alpha q - p| \geq \frac{C}{q^{1+\nu}},$$

то у неоднородной задачи существует решение $0 \leq x \leq \widetilde{C} n^{1+\nu}$ (на самом деле решение будет существовать в любом интервале длины $\widetilde{C} n^{1+\nu}$). Для случая $\nu = 0$ это есть у Хинчина в "Цепные дроби" (теорема 26). Множество диофантовых с показателем $\nu > 0$ чисел имеет полную меру Лебега. Для не диофантовых (=лиувиллевых чисел, составляющих множество меры нуль) актуальная граница может быть выше любой степени $n$.

[Nartu]

Что ж спасибо, а мне надо углублятся в эту книгу: "Цепные дроби" Хинчина, что бы находить $\nu$ ?
Ведь действительно исходная задача такова

$$3^{x}5^{y}\overset{\varepsilon}{\approx}c$$

Это, конечно, можно переписать так:

$$y\overset{(\varepsilon)}{\approx}-\log_5(3)\cdot x+c\cdot \log_5(2)(+\log_5(1+\xi))$$

$x$ и $y$ - целые, $\varepsilon$ - ошибка(задано), ( $\xi\in[-\varepsilon,\varepsilon]$ )
Как видите, $\alpha$ - логарифм.

[demolishka]

В Вашем случае $\alpha$ иррационально. Поэтому решения существуют, что уже хорошо

Nartu в сообщении #1414652 писал(а):

а мне надо углублятся в эту книгу: "Цепные дроби" Хинчина, что бы находить $\nu$ ?

Нет и более того в общем случае это нетривиальная задача. Для определения $\nu$ нужно для знаменателей подходящих дробей проверить, что $q_{k+1}=O(q^{1+\nu}_{k})$. Для Вашего логарифма вольфрам не выдает красивой закономерности. Да и зачем Вам эта верхняя граница на решения?

Я так понимаю, что Вам нужно найти хоть какие-то решения при различных $c$ и, возможно, варьируемом $\varepsilon$? Ну тогда можно вычислять логарифм с нужной точностью и следовать тому алгоритму, который я предложил.

[Nartu]

demolishka в сообщении #1414660 писал(а):

Да и зачем Вам эта верхняя граница на решения?

Вы меня спрашиваете или это касалось
$q_{k+1}=O(q_k^{1+\nu})$ ?
Ведь я бы мог рассказать... Это немножко касается музыки... только это уже малость оффтопик будет, нехорошо.

demolishka в сообщении #1414660 писал(а):

Нет и более того в общем случае это нетривиальная задача.

А что, небыло попыток искать, на пример, алгебраические методы? Для корней полиномов (над полем) это, в принципе, бессмысленно, - можно и компом посчитать. Но я бы начинал с них...

demolishka в сообщении #1414660 писал(а):

Я так понимаю, что Вам нужно найти хоть какие-то решения при различных $c$ и, возможно, варьируемом $\varepsilon$?

Да, $c=2^\frac{n}{12},\;n\n\in\mathbb{Z}$,
$\frac{2}{1200}\leqslant\varepsilon\leqslant\frac{25}{1200}$, в принципе он неподвижен. а если да, то чуть-чуть. Распределён неоднородно относительно $c$

[demolishka]

Nartu в сообщении #1414762 писал(а):

Ведь я бы мог рассказать...

Расскажите мне в ЛС. Интересно

Nartu в сообщении #1414762 писал(а):

А что, небыло попыток искать, на пример, алгебраические методы? Для корней полиномов (над полем) это, в принципе, бессмысленно, - можно и компом посчитать. Но я бы начинал с них...

Все алгебраические числа диофантовы с любым показателем $\nu > 0$. Это теорема Рота, известная в алгебраической теории чисел. Для некоторых не алгебраических чисел известны оценки или точные значения нижней грани $\nu$. Например для $e$ она равна нулю (как для алгебраических), для $\pi$ есть только оценка сверху $\leq 5.6063$. Как это все доказывается мне не известно. По виду первых членов разложения Вашего логарифма в цепную дробь он по гадкости больше похож на $\pi$, нежели на $e$.

Nartu в сообщении #1414762 писал(а):

Да, $c=2^\frac{n}{12},\;n\n\in\mathbb{Z}$,
$\frac{2}{1200}\leqslant\varepsilon\leqslant\frac{25}{1200}$, в принципе он неподвижен. а если да, то чуть-чуть. Распределён неоднородно относительно $c$

Ну точность небольшая, так что задача посильная.

[Nartu]

demolishka в сообщении #1414774 писал(а):

Все алгебраические числа диофантовы с любым показателем $\nu > 0$. Это теорема Рота
, известная в алгебраической теории чисел. Для некоторых не алгебраических чисел известны оценки или точные значения нижней грани $\nu$. Например для $e$ она равна нулю (как для алгебраических), для $\pi$ есть только оценка сверху $\leq 5.6063$. Как это все доказывается мне не известно. По виду первых членов разложения Вашего логарифма в цепную дробь он по гадкости больше похож на $\pi$, нежели на $e$.

Ааа!.. Так $\nu$ есть мера иррациональности!?

На счёт лс...мне надо картинки вставлять или кодить комут.диаграммы(их на смартфоне как-то не очень удобно... К ноутбуку доступ будет завтра, но и без него есть что сказать)

[demolishka]

Nartu в сообщении #1414790 писал(а):

Так $\nu$ есть мера иррациональности!?

Нижняя грань $\nu > 0$ таких, что $\alpha$ диофантово с показателем $\nu$ плюс двойка есть мера иррациональности.

[Nartu]

demolishka в сообщении #1414642 писал(а):

Если хочется решать задачу для любых $\beta$ и $n$, то существенно потребовать иррациональности $\alpha$ (т. е. несоизмеримости $c_{1}$ и $c_{2}$). В случае $\beta \not= 0$ цепные дроби для поиска решений мало помогут. Не знаю можно ли в общем случае предложить что-то кроме перебора (см. ниже). Конечно достаточно дробной частью $\alpha x$ приблизить дробную часть $\beta$ и тогда $y$ определяется однозначно. Это приводит к задаче на окружности: сделать величину $|\alpha x - \beta|_{1}$ малой в смысле метрики $|\cdot|_{1}$ на окружности $\mathbb{T}^{1} = \mathbb{R}/\mathbb{Z}$.

Например, можно действовать как при доказательстве плотности иррационального поворота окружности: разбить окружность (длины 1) на $n$ полудуг длины $1/n$; тогда по принципу Дирихле точка $\alpha x$ при целых $0 \leq x \leq n$ хотя бы дважды попадет в одну из этих полудуг (пусть это происходит при $x=x_{1}$ и $x=x_{2}$). А дальше уже можно идти с шагом $\alpha (x_{1}-x_{2})$ (строго меньше $1/n$), пока не придем в полудугу, содержащую $\beta$. Будем считать, что $h = \{ \alpha (x_{1}-x_{2}) \} > 0$ и $\beta \in [0,1]$. Осталось найти $m$ так, что $m h \leq \beta < m (h+1)$. Ответ: $x = m(x_{1}-x_{2})$. Формально мы справились за $n$ итераций (на деле же все упирается в точность вычислений).

А можно этот трюк распространить на более многомерный случай? Вот:

$$\left\lvert c_0+c_1x+c_2y+c_3z\right\rvert\leqslant\varepsilon$$

Я просто затупил , там есть ещё 2 в степени(это не столь критично):

$$3^{x}5^{y}2^{z}\overset{\varepsilon}{\approx}c$$

[demolishka]

Nartu в сообщении #1415149 писал(а):

А можно этот трюк распространить на более многомерный случай?

Ну при $z=0$ подходят старые решения $x$ и $y$.

Чтобы описать все решения, нужно на окружности решить неравенство $|\log_{2}(3) x + \log_{2}(5) y - \beta |_{1} \leq \varepsilon$, где $\beta = \log_{2}c$. Ну тут для любого $y$ можно (вышеуказанным способом) найти $x$ такой, что оно выполнено.