Открытые проблемы форумчан.

[Батороев]

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

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

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

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

[Руст]

Не вижу причин, почему эта гипотеза может быть верна. Здесь сильным ограничением является только то, что оба числа составные. Соответственно приходится выбрать так, чтобы они имели много множителей. Само условие (вместе) эквивалентны одному

$$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. По видимому минимальное решение довольно большое и трудно найти его эффективным алгоритмом.

[Батороев]

(Оффтоп)

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

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

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

[Руст]

Батороев в сообщении #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\#})$ слишком сложно и нужно ли.

[Батороев]

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

$\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$) степени двоек.

[Руст]

Батороев в сообщении #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$ слева не целое число.

[Батороев]

Руст в сообщении #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}$

[Руст]

Батороев в сообщении #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.

[Батороев]

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

В случае в таких интервалах длины 144,375 должно быть 30 вычетов. Уже в первом таком интервале это 1 и простые числа их только 29.

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

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

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

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

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

[Руст]

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

[Батороев]

Готов принять любой Ваш приговор итог.

[Руст]

Ваша гипотеза верна.
Доказательство: Каждому вычету х сопоставим координаты $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)$.

[Батороев]

Руст

Ну, разве так по человечьи?! У некоторых, вон - гипотезы по 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)$.

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

[Руст]

Батороев в сообщении #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).

[Батороев]

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

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