2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Открытые проблемы форумчан.
Сообщение24.09.2012, 21:32 


23/01/07
3415
Новосибирск
В данной теме предлагается озвучить гипотезы, которые форумчане выдвинули самостоятельно в разные годы. Может быть, со временем возникнет собственный список открытых проблем форума DXDY. Попытка-не пытка.

Для затравки озвучу собственную мысль, которой уже лет семь:

"Двух составных взаимнопсевдопростых чисел $6n\pm 1$ не существует".

Другими словами, не существует двух составных чисел $6n\pm 1$ таких, что:
$(6n-1)^{6n}\equiv 1\pmod {(6n+1)}$
$(6n+1)^{6n-2}\equiv 1\pmod {(6n-1)}$

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение24.09.2012, 22:30 
Заслуженный участник


09/02/06
4382
Москва
Не вижу причин, почему эта гипотеза может быть верна. Здесь сильным ограничением является только то, что оба числа составные. Соответственно приходится выбрать так, чтобы они имели много множителей. Само условие (вместе) эквивалентны одному $$2^{6n+1}=4(6n+1)-(6n-1)\mod (36n^2-1)$$
или двум $ord_{6n+1}(2)|6n, ord_{6n-1}(2)|6n-2$. Отсюда следует, что $6n\pm 1$ свободны от квадратов за исключением простых вида $2^{p-1}=1\mod p^2$ (только такие простые могут войти в эти числа в квадрате, а их очень мало).
Вычисляя предварительно по всем простым $p<10^{10}$ числа $ord_p(2)$ можно эффективно исключать не подходящие n. По видимому минимальное решение довольно большое и трудно найти его эффективным алгоритмом.

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение30.09.2012, 08:47 


23/01/07
3415
Новосибирск

(Оффтоп)

Руст
Спасибо ответ! Сейчас пытаюсь, не спеша, разобраться в Ваших рассуждениях.


Другое мое предположение заключается в том, что:

"Если примориал $p_i\#$ поделить на $ 2^{i-1}$ равных интервала, то в каждом из интервалов будет равное (или примерно равное с некоторой небольшой погрешностью) количество чисел, взаимнопростых этому примориалу".

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение30.09.2012, 09:29 
Заслуженный участник


09/02/06
4382
Москва
Батороев в сообщении #625023 писал(а):
Другое мое предположение заключается в том, что:

"Если примориал $p_i\#$ поделить на $ 2^{i-1}$ равных интервала, то в каждом из интервалов будет равное (или примерно равное с некоторой небольшой погрешностью) количество чисел, взаимнопростых этому примориалу".

По сути вы хотите сказать, что вычеты распределены равномерно независимо от положения. Когда делим на 2 первый раз получаем точное равенство вычетов в нижней и верхней половинах. Дальше уже не будет точного равенства. Можно доказать только слабую равномерность. При любом $0<x<1$ в интервале длины $xp\#$ количество вычетов из интервала оценивается формулой:
$$\pi(A,B)=xN+o(N), B-A=xp\#, N=\prod_{q\le p, q\in P} (q-1).$$
Более точно оценить погрешность (как квадратный корень) и возможность такой оценки, когда x стремится к нулю, например как $xp\#=O(\sqrt{p\#})$ слишком сложно и нужно ли.

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение30.09.2012, 10:11 


23/01/07
3415
Новосибирск
Я исходил из того, что если функция Эйлера мультипликативна:

$\varphi (p_1\cdot p_2\cdot ...\cdot p_i)=\varphi(p_1)\cdot\varphi(p_2)\cdot...\cdot \varphi(p_i)$,

то почему бы не быть справедливой и формуле:

$\varphi (\dfrac {p_1\cdot p_2\cdot ...\cdot p_i}{2^{i-1}})=\varphi (p_1)\cdot \dfrac{\varphi (p_2)}{2}\cdot ...\cdot \dfrac{\varphi (p_i)}{2}$

-- 30 сен 2012 14:18 --

В случае, если вышеуказанное справедливо, то можно было бы и продолжить далее, выявляя из всех $\varphi(p_j)$ (где $j=1,2...,i$) степени двоек.

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение30.09.2012, 13:52 
Заслуженный участник


09/02/06
4382
Москва
Батороев в сообщении #625057 писал(а):
то почему бы не быть справедливой и формуле:

$\varphi (\dfrac {p_1\cdot p_2\cdot ...\cdot p_i}{2^{i-1}})=\varphi (p_1)\cdot \dfrac{\varphi (p_2)}{2}\cdot ...\cdot \dfrac{\varphi (p_i)}{2}$

При $i>2$ аргумент $\phi$ слева не целое число.

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение30.09.2012, 17:49 


23/01/07
3415
Новосибирск
Руст в сообщении #625163 писал(а):
При $i>2$ аргумент $\phi$ слева не целое число.

Да, действительно, некорректно записал.
Пусть $\phi  (k,m)$ - количество взаимнопростых числу $k$ на интервале, равном $m$.
Тогда свое выражение перепишу в виде:

$\phi ((p_i\#),(\dfrac {p_i\#}{2^{i-1}}))=\varphi (p_1)\cdot \dfrac{\varphi (p_2)}{2}\cdot ...\cdot \dfrac{\varphi (p_i)}{2}$

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение30.09.2012, 19:08 
Заслуженный участник


09/02/06
4382
Москва
Батороев в сообщении #625309 писал(а):
Пусть $\phi  (k,m)$ - количество взаимнопростых числу $k$ на интервале, равном $m$.
Тогда свое выражение перепишу в виде:

$\phi ((p_i\#),(\dfrac {p_i\#}{2^{i-1}}))=\varphi (p_1)\cdot \dfrac{\varphi (p_2)}{2}\cdot ...\cdot \dfrac{\varphi (p_i)}{2}$

Во первых в разных таких интервалах разное количество, поэтому необходимо писать $\phi(k,A,B)=(B-A)\prod_{j\le i}(1-\frac{1}{p_j})+R$ и дать оценку для погрешности $R$ Для вашего случая $B-A=\frac{p_i\#}{2^{i-1}}$. Она не равна нулю уже в случае $i=3$, если интервалы брать смещенными от точек $l\frac{p_i\#}{2^{i-1}}$. В случае $i=5$ в таких интервалах длины 144,375 должно быть 30 вычетов. Уже в первом таком интервале это 1 и простые числа $11<p<144$ их только 29.

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение01.10.2012, 10:22 


23/01/07
3415
Новосибирск
Руст в сообщении #625346 писал(а):
В случае в таких интервалах длины 144,375 должно быть 30 вычетов. Уже в первом таком интервале это 1 и простые числа их только 29.

Ну, так с числом $1$ тридцать взаимно простых и получается.

-- 01 окт 2012 14:25 --

Если по какой-то причине $1$ не считается взаимно простым (по примеру с простыми), то предлагаю в пределах данного обсуждения временно включить.

-- 01 окт 2012 14:34 --

Да вроде, и без моего предложения учитывается - по функции Эйлера.

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение01.10.2012, 11:50 
Заслуженный участник


09/02/06
4382
Москва
1 всегда считается взаимно простым с другими целыми, включая даже нуля.
Возможно я ошибся при ручном подсчете. Тогда надо рассмотреть другие интервалы. При большом $i$ согласно моей интуиции не должно быть точное равенство.

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение01.10.2012, 17:12 


23/01/07
3415
Новосибирск
Готов принять любой Ваш приговор итог.

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение01.10.2012, 18:34 
Заслуженный участник


09/02/06
4382
Москва
Ваша гипотеза верна.
Доказательство: Каждому вычету х сопоставим координаты $x=\sum_{j\le i}x_jN_j\mod N$, где $N=\prod_{j\le i}p_j=p_i\#, N_j=\frac{N}{p_j}$. Любые ненулевые координаты $1\le x_j<p_j$ определяет один вычет $x$, взаимно простой с $N$.
При этом если зафиксируем одну из координат, то получаем вычеты по модулю $N_j$. По индукции вычеты по модулю $N_j$ удовлетворяют этому свойству при любом $j$, т.е. каждый из $2^{i-2}$ интервалов длины $L_j$ имеет ровно $M_j=2^{2-i}\prod_{k\not =j}(p_k-1)$ вычетов и докажем это свойство по модулю $N$. Длина рассматриваемых интервалов по модулю $N_j$ есть $L_j=\frac{N_j}{2^{i-2}}$, а по модулю $N$ есть $L=\frac{N}{2^{i-1}}=L_j\frac{p_j}{2}.$
Учитывая симметрию $x_j\to p_j-x_j$ получаем, что объединенные $p_j$ интервалов длины $L_j$ обладают симметрией и поэтому каждый из интервалов длины $L$ имеет ровно $\frac{p_j-1}{2}M_j=2^{1-i}\prod_{k\le i}(p_k-1)$ вычетов.

Отсюда получается почти равномерность ПСВ, т.е. в интервале $(A,B), B-A>N^{ln2 +\epsilon}$ содержится вычетов $\pi(A,B)=(B-A)\prod_j(1-\frac{1}{p_j})+O(N^{\ln 2+\epsilon})$ (для хорошей равномерности не хватает то, что $\ln 2>0.5)$.

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение01.10.2012, 19:07 


23/01/07
3415
Новосибирск
Руст

Ну, разве так по человечьи?! У некоторых, вон - гипотезы по 350 лет живут, а Вы мою - за два дня свели на нетда. Теперь новую думать! :-)

Теперь серъезно.
Руст в сообщении #625700 писал(а):
Учитывая симметрию $x_j\to p_j-x_j$ получаем, что объединенные $p_j$ интервалов длины $L_j$ обладают симметрией и поэтому каждый из интервалов длины $L$ имеет ровно $\frac{p_j-1}{2}M_j=2^{1-i}\prod_{k\le i}(p_k-1)$ вычетов.

Отсюда получается почти равномерность ПСВ, т.е. в интервале $(A,B), B-A>N^{ln2 +\epsilon}$ содержится вычетов $\pi(A,B)=(B-A)\prod_j(1-\frac{1}{p_j})+O(N^{\ln 2+\epsilon})$ (для хорошей равномерности не хватает то, что $\ln 2>0.5)$.

Я немного не понял из Вашего сообщения, есть все таки погрешность в интервалах или нет?

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение01.10.2012, 19:19 
Заслуженный участник


09/02/06
4382
Москва
Батороев в сообщении #625718 писал(а):
Руст

Отсюда получается почти равномерность ПСВ, т.е. в интервале $(A,B), B-A>N^{ln2 +\epsilon}$ содержится вычетов $\pi(A,B)=(B-A)\prod_j(1-\frac{1}{p_j})+O(N^{\ln 2+\epsilon})$ (для хорошей равномерности не хватает то, что $\ln 2>0.5)$.
Я немного не понял из Вашего сообщения, есть все таки погрешность в интервалах или нет?

В интервалах длины $L=\frac{p_i\#}{2^{i-1}}$ погрешности нет, когда они взяты в точках $(\frac{j\p_i\#}{2^{i-1}},\frac{(j+1)p_i\#}{2^{i-1}}).$. Для общего вида интервалов (например при смещениях) появляются погрешности. На самом деле для модуля из произведения любых i нечетных простых чисел, знаменатель можно взять $2^i$. Включая в модуль простое число 2 приходится довольствоваться $2^{i-1}$ (как будто не учитываем 2).

 Профиль  
                  
 
 Re: Открытые проблемы форумчан.
Сообщение01.10.2012, 19:43 


23/01/07
3415
Новосибирск
Наверное, нет ничего страшного и в том, чтобы рассматривать дробные интервалы. На мой взгляд, при рассмотрении равномерности это допустимо.

На счет $2$, то по-видимому, дальнейшее увеличение ее степени может вести к появлению погрешности. Хорошо, если бы эта погрешность не превышала 1 число/на 1 степень.

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

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



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

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


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

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