2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Свойства комбинаторного разложения
Сообщение14.03.2011, 08:31 
Заслуженный участник


09/02/06
4382
Москва
Функция Эйлера тут совсем не причем. Оптимальный алгоритм нахождения алгоритм Евклида.
По сути сразу можно писать $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+...}}},$$
но вычисление все равно сводит к алгоритму Евклида.

 Профиль  
                  
 
 
Сообщение14.03.2011, 14:06 
Заблокирован
Аватара пользователя


17/06/09

2213
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$

 Профиль  
                  
 
 
Сообщение14.03.2011, 16:27 
Заблокирован
Аватара пользователя


17/06/09

2213
Попробуем вернуться к функциям Эйлера:
Пусть $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$

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

 Профиль  
                  
 
 
Сообщение15.03.2011, 23:39 
Заблокирован
Аватара пользователя


17/06/09

2213
Немного поразмыслил.
Рассмотрим исследуемую форму с простыми числами, для которых функция Эйлера принимает значение самого числа, уменьшенного на 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$

 Профиль  
                  
 
 
Сообщение16.03.2011, 00:53 
Заблокирован
Аватара пользователя


17/06/09

2213
Здесь необходимо использовать тот факт, что при представлении каждого конкретного $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$, которое не может быть представлено классом функций с более узкой областью значений.

 Профиль  
                  
 
 
Сообщение16.03.2011, 13:36 
Заблокирован
Аватара пользователя


17/06/09

2213
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$, которое также не может быть представлено другим классом функций, но с более узкой областью значений.

 Профиль  
                  
 
 
Сообщение16.03.2011, 14:03 
Заслуженный участник


08/04/08
8556

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

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

 Профиль  
                  
 
 
Сообщение16.03.2011, 14:07 
Заблокирован
Аватара пользователя


17/06/09

2213
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$. :?

 Профиль  
                  
 
 
Сообщение17.03.2011, 12:45 
Заблокирован
Аватара пользователя


17/06/09

2213
А вот неожиданно в голову пришла интересная идея :?
А что если $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$. И оно действительно может повлиять на количество таких представлений. Поэтому вопрос по-прежнему остаётся открытым.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group