2014 dxdy logo

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

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




 
 Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение10.03.2010, 07:17 
Вот это тоже не знаю как найти.
$$\frac{1}{N} \sum\limits_{p: p=4t+1} [a(p) < \frac{p}{3}]$$
Здесь $a(p):a(p)^2 \equiv -1 \pmod p, a(p) < \frac{p}{2}$, $N$ - число слагаемых в сумме. Выражения типа $[P(n)]$ - нотация Айверсона, т.е. $[P(n)]=1 \Leftrightarrow P(n)$ истинно и $[P(n)]=0 \Leftrightarrow P(n)$ ложно.
Ответ навеивают только вероятностные соображения ($\frac{2}{3}$), но их нельзя использовать.

 
 
 
 Re: Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение10.03.2010, 18:12 
Аватара пользователя
Непонятно, по какому множеству простых(?) берётся сумма.
А вообще для каждого фиксированного значения $a(p)=k$ попробуйте подсчитать количество подходящих $p$.

 
 
 
 Re: Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение10.03.2010, 20:04 
Аватара пользователя
Как я понимаю, интересует "условная вероятность" того, что решение уравнения $a^2=-1\pmod p$ из отрезка $(0,p/2)$, попадает в $(0,p/3)$, при условии, что уравнение разрешимо. Так?

 
 
 
 Re: Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение11.03.2010, 06:34 
maxal писал(а):
Непонятно, по какому множеству простых(?) берётся сумма.

По всем простым вида $4t+1$ не превосходящих $N$.
maxal писал(а):
А вообще для каждого фиксированного значения $a(p)=k$ попробуйте подсчитать количество подходящих $p$.

Эх, попробую - сообщу.
Хорхе писал(а):
Как я понимаю, интересует "условная вероятность" того, что решение уравнения $a^2 = -1  \pmod p$ из отрезка $(0;p/2)$, попадает в $(0;p/3)$, при условии, что уравнение разрешимо. Так?

Да. Только я не знаю, насколько правомерно тут о вероятностях говорить.

 
 
 
 Re: Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение11.03.2010, 06:49 
Аватара пользователя
Sonic86 в сообщении #296262 писал(а):
$N$ - число слагаемых в сумме

Sonic86 в сообщении #296512 писал(а):
По всем простым вида $4t+1$ не превосходящих $N$.

Противоречие наблюдается.

 
 
 
 Re: Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение11.03.2010, 10:42 
maxal писал(а):
Sonic86 в сообщении #296262 писал(а):
$N$ - число слагаемых в сумме

Sonic86 в сообщении #296512 писал(а):
По всем простым вида $4t+1$ не превосходящих $N$.

Противоречие наблюдается.

:D А, блин, значит сумма по первым $N$ простым числам вида $4t+1$.

 
 
 
 Re: Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение15.03.2010, 23:25 
Аватара пользователя
В этой статье этот вопрос обсуждается.

 
 
 
 Re: Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение16.03.2010, 15:02 
RIP писал(а):
В этой статье этот вопрос обсуждается.

Если я правильно понял, мне туда не попасть :-(

Опытным путем пришел к предположению, что величина $\frac{2 a(p)}{p}$ распределена равномерно на $(0;1)$.
Еще получилось оценить сумму $\sum\limits_{p} [a(p) < n]$ как $O(n)$. Больше ничего :-(

maxal писал(а):
А вообще для каждого фиксированного значения $a(p)=k$ попробуйте подсчитать количество подходящих $p$.


Не вышло :-( Может я не понял что-то. Это мне надо знать оценку для числа делителей вида $n^2+1$. Я нашел только среднюю оценку для всех чисел от 1 до $n$ - $n \ln \ln n + B + O(\frac{1}{\ln n})$. По-моему для подпоследовательностей чисел даже с таким же ростом ее нельзя использовать.

 
 
 
 Re: Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение16.03.2010, 22:29 
Аватара пользователя
Sonic86 в сообщении #298283 писал(а):
Если я правильно понял, мне туда не попасть :-(
К сожалению, мне туда тоже не попасть. Попросите помощи в Lost & found: вам наверняка помогут (но сначала лучше дочитайте моё сообщение до конца).

Sonic86 в сообщении #298283 писал(а):
Опытным путем пришел к предположению, что величина $\frac{2 a(p)}{p}$ распределена равномерно на $(0;1)$.
Это правда. Сам я статью не смотрел, но насколько я понял (из других источников, но название работы это подтверждает), в статье это и доказывается. Причём доказательство весьма суровое и забирается глубоко в дебри аналитической теории чисел (например, используется спектральная теория автоморфных форм)

 
 
 
 Re: Среднее выражения [a<p/3], где a^2+1 = 0 mod p
Сообщение17.03.2010, 07:19 

(Оффтоп)

RIP писал(а):
Причём доказательство весьма суровое и забирается глубоко в дебри аналитической теории чисел (например, используется спектральная теория автоморфных форм)

Кошмар! :shock: А я совсем не знаю, что это такое!

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group