Свойства комбинаторного разложения

[Руст]

Функция Эйлера тут совсем не причем. Оптимальный алгоритм нахождения алгоритм Евклида.
По сути сразу можно писать $x=a^{-1}\mod b, y=-b^{-1}\mod a$.
Более явно можно записать только через непрерывную дробь

$$\frac{a}{b}=\frac{1}{q_1+\frac{1}{q_2+\frac{1}{q_3+...}}},$$

но вычисление все равно сводит к алгоритму Евклида.

[age]

age в сообщении #422775 писал(а):

Функция Эйлера тут совсем не причем.

Проверял на вольфраме, phi-функции Эйлера дают прекрасный результат по любым $a,b$.

-- Пн мар 14, 2011 15:15:11 --

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

По сути сразу можно писать $x=a^{-1}\mod b, y=-b^{-1}\mod a$.

Ну это просто по сути переписать $ax=1\mod by$

[age]

Попробуем вернуться к функциям Эйлера:
Пусть $b$ - фиксированное, тогда и $\varphi(b)-1$ - также фиксированное. Тогда $b\left(a^{\varphi(b)-1} \bmod{b}\right)$ примет вид $b\left(x^m\mod b\right)=f(x)b$. Очевидно, что меняя любые $x$ мы получим любые числа от $b, 2b, 3b,...,b^2-b$
или
$n=k(a^2+b^2)\pm\left[a\left(a-b^{\varphi(a)-1}\bmod{a}\right)\pm f(x)b$.

Но $b^{\varphi(a)-1}\bmod{a}$ при фиксированном $b$ уже не сможет дать любые числа, а лишь 4 значения максимум (т.к. степени цикличны). Т.е. мы получим:

$n=k(x^2+b^2)\pm(c_1,c_2,c_3,c_4)x\pm f(x)b$.

здесь $x, k$ - переменные (чтобы было понятнее), всё остальное константы. Что по своей сути эквивалентно системе 4 уравнений:
$\begin{cases} n=k(x^2+b^2)\pm c_1x\pm f(x)b\\ n=k(x^2+b^2)\pm c_2x\pm f(x)b\\ n=k(x^2+b^2)\pm c_3x\pm f(x)b\\ n=k(x^2+b^2)\pm c_4x\pm f(x)b \end{cases}$

Т.к. они все одинаковы по сути, то возьмём первое из них:
$n=k(x^2+b^2)\pm c_1x\pm f(x)b$.

Далее положим, что $b=2$. Тогда $f(x)=x^m\mod 2$ может принимать лишь 2 значения $(1,0)$, тогда уравнение эквивалентно системе:
$\begin{cases} n=k(x^2+4)\pm c_1x\pm2\\ n=k(x^2+4)\pm c_1x \end{cases}$.

где $k,x$ - произвольные. Как видно, этими уравнениями (в силу степеней свобод) можно представить очень много $n>\varepsilon$

Но общего ответа на вопрос это так и не даёт.

[age]

Немного поразмыслил.
Рассмотрим исследуемую форму с простыми числами, для которых функция Эйлера принимает значение самого числа, уменьшенного на 1. Это сохранит смысл, но сделает рассуждение понятнее. Для простых $a,b$ формула примет вид:

$n=k(a^2+b^2)\pm a^2\pm\left[b\left(a^{b-2}\bmod{b}\right)-a\left(b^{a-2}\bmod{a}\right)\right]$.

Рассмотрим выражение в скобках, дающее частное решение для пары простых $(a,b)$. Очевидно, что для любой пары $(a,b)$ это будет своё уникальное значение (причём это не исключает, что для различных пар такие значения могут совпадать). Суть в том, что ни для какой пары $(a,b)$ таких значений не может быть несколько. А может быть только одно:

$b\left(a^{b-2}\bmod{b}\right)-a\left(b^{a-2}\bmod{a}\right)=f(a,b)$

Но анализировать такую функцию довольно затруднительно, т.к. она имеет весьма сложное и неоднозначное поведение, мало связанное с числами $a$ и $b$. Её даже в каком-то смысле можно принять за случайную составляющую. Поэтому основным "компонентом" представимости числа $n>\varepsilon$ является именно выражение

$n=k(a^2+b^2)\pm a^2$.

Если не всякое $n>\varepsilon$ представимо данным выражением, то анализируемым выражением - и подавно. Оно даёт два семейства квадратичных форм:
$\begin{cases} (k+1)a^2+kb^2\\ (k-1)a^2+kb^2 \end{cases}$

С точностью до перестановки эти семейства аналогичны, поэтому достаточно рассмотреть лишь одно из них $(k+1)a^2+kb^2$. Оно исчерпывает все квадратичные формы, где один коэффициент на 1 больше другого:
$\begin{cases} 2a^2+b^2\\ 3a^2+2b^2\\ 4a^2+3b^2\\ ........ \end{cases}$

Несложно показать, что не все целые числа $n>\varepsilon$ представимы этими формами. Например, число $7$ не представляется ни одной из перечисленных форм ($a\neq b$), аналогично число $10$. Также найдутся числа вида $n_1\cdot n_2\cdot ...\cdot n_k$, где $n_i=(k_i+1)a^2+k_ib^2$, которые также нельзя представить ни одной из рассматриваемых форм в отдельности, т.к. каждая форма охватывает строгое семейство простых чисел и простые числа, не относящиеся к семейству, данной формой не представимы. Можно показать, что можно построить сколько угодно большое такое число $n>\varepsilon$.
Данное рассуждение было сделано для простых чисел, но оно полностью без ограничения общности переносится и на целые числа.

-- Ср мар 16, 2011 00:54:44 --

Остаётся доказать, что если $n>\varepsilon$ не представимо $(k+1)a^2+kb^2$, то невозможно и гораздо более узкое представление:

$n=(k+1)a^2+kb^2\pm f(a,b)$

где $f(a,b)$ принимает строго фиксированное уникальное значение для каждой пары $a,b$ и не может расширить круг представимости чисел $n>\varepsilon$

[age]

Здесь необходимо использовать тот факт, что при представлении каждого конкретного $n$ при фиксированном $k$, $n=(k+1)a^2+kb^2\pm f(a,b)$ даёт меньше представлений, чем $n=(k+1)a^2+kb^2$, т.к. для различных $a,b$, $f(a,b)$ может давать одно и то же значение, т.е. итоговое количество представлений будет сужаться количеством этих повторов. А повторы будут возникать из-за того, что $0<f(a,b)<a^2,b^2$

-- Ср мар 16, 2011 02:05:42 --

Как это сформулировать более грамотно через классы сложности, это пусть спецы решат. я, в общем-то, на бытовом уровне изложил свои соображения.

-- Ср мар 16, 2011 02:11:33 --

Хотя с другой стороны, мне неизвестно, насколько правомерно следующее утверждение: если некоторое число $n>\varepsilon$ не может представлено классом функций, то найдётся другое число $k>\varepsilon$, которое не может быть представлено классом функций с более узкой областью значений.

[age]

age в сообщении #423402 писал(а):

Здесь необходимо использовать тот факт, что при представлении каждого конкретного $n$ при фиксированном $k$, $n=(k+1)a^2+kb^2\pm f(a,b)$ даёт меньше представлений, чем $n=(k+1)a^2+kb^2$, т.к. для различных $a,b$, $f(a,b)$ может давать одно и то же значение, т.е. итоговое количество представлений будет сужаться количеством этих повторов. А повторы будут возникать из-за того, что $0<f(a,b)<a^2,b^2$

Переформулировка:
Здесь необходимо использовать тот факт, что при представлении каждого конкретного $n$ при фиксированном $k$ форма $n=(k+1)a^2+kb^2\pm f(a,b)$ даёт меньше способов представления, чем $n=(k+1)a^2+kb^2$, т.к. для различных пар $a,b$, функция $f(a,b)$ может давать один и тот же фиксированный набор значений, т.е. итоговое количество представлений будет сужаться количеством этих повторов. А повторы будут возникать из-за того, что $0<f(a,b)<a^2,b^2$

-- Ср мар 16, 2011 14:53:53 --

age в сообщении #423402 писал(а):

Хотя с другой стороны, мне неизвестно, насколько правомерно следующее утверждение: если некоторое число $n>\varepsilon$ не может представлено классом функций, то найдётся другое число $k>\varepsilon$, которое не может быть представлено классом функций с более узкой областью значений.

Ещё переформулировка:
Если некоторое число $n>\varepsilon$ не может представлено определённым классом функций, то найдётся другое число $k>\varepsilon$, которое также не может быть представлено другим классом функций, но с более узкой областью значений.

[Sonic86]

(я вот не понимаю...)

Я вот не понимаю, если задача эквивалентна конечности простых вида $n^2+1$, то зачем ее пытаться доказывать - она же скорее всего ложна, число простых $n^2+1$ ведь скорее всего бесконечно...

[age]

Sonic86
Прочтите два последних утверждения:
1) не каждое $n>\epsilon$ может быть представлено суммой квадратов с последовательными коэффициентами $n=(k+1)a^2+kb^2$.
2) область значений $n=(k+1)a^2+kb^2\pm f(a,b)$ - ещё уже, чем у $n=(k+1)a^2+kb^2$.

Вывод: существует $n>\epsilon$, которое не представимо ни одной из форм $n=(k+1)a^2+kb^2\pm f(a,b)$. Существование такого числа означает бесконечность простых $n^2+1$.

[age]

А вот неожиданно в голову пришла интересная идея
А что если $k$ занулить, т.е. абстрагироваться от общих решений и ограничиться лишь частными? Тогда исследуемая форма примет вид:

$n=a^2+b\left(a^{b-2}\bmod{b}\right)-a\left(b^{a-2}\bmod{a}\right)$

где, как уже было выяснено, для каждой пары $(a,b)$ выражение $b\left(a^{b-2}\bmod{b}\right)-a\left(b^{a-2}\bmod{a}\right)$ принимает ровно одно значение. Причём, если варьировать $a$ и $b$ в каких-то заданных пределах, то таких значений может быть сколь угодно много.

Действительно, последнее выражение представляет собой не что иное как форму $bx-ay$. А этой формой как известно, можно представить любое целое $n>\varepsilon$.

Единственное, что затрудняет вычисление, это то, что в исходной форме ещё присутствует $a^2$. И оно действительно может повлиять на количество таких представлений. Поэтому вопрос по-прежнему остаётся открытым.