Сито большего размера

Сито, изобретенное Патриком Икс. Галлахером

В теории чисел большее решето — это решето, изобретенное Патриком X. Галлахером . Название обозначает усиление большого решета . Комбинаторные решета, такие как решето Сельберга, являются наиболее сильными, когда удаляются только несколько классов остатков, в то время как термин большое решето означает, что это решето может воспользоваться удалением большого числа, вплоть до половины всех классов остатков. Большее решето может использовать удаление произвольного числа классов.

Заявление

Предположим, что — набор степеней простых чисел, N — целое число, набор целых чисел в интервале [1,  N ], такой, что для существует не более классов вычетов по модулю , которые содержат элементы . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle q\in {\mathcal {S}}}$ ${\displaystyle g(q)}$ ${\displaystyle q}$ ${\displaystyle {\mathcal {A}}}$

Тогда у нас есть

${\displaystyle |{\mathcal {A}}|\leq {\frac {\sum _{q\in {\mathcal {S}}}\Lambda (q)-\log N}{\sum _{q\in {\mathcal {S}}}{\frac {\Lambda (q)}{g(q)}}-\log N}},}$

при условии, что знаменатель справа положительный. ^[1]

Приложения

Типичным применением является следующий результат, для которого большое сито не работает (особенно для ), по Галлахеру: ^[2] ${\displaystyle \theta >{\frac {1}{2}}}$

Число целых чисел , таких что порядок модуля для всех простых чисел равен . ${\displaystyle n\leq N}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle \leq N^{\theta }}$ ${\displaystyle p\leq N^{\theta +\epsilon }}$ ${\displaystyle {\mathcal {O}}(N^{\theta })}$

Если число исключенных классов остатков по модулю меняется с , то большее решето часто комбинируется с большим решетом. Большее решето применяется с набором, определенным выше как набор простых чисел, для которых удаляются многие классы остатков, в то время как большое решето используется для получения информации с использованием простых чисел за пределами . ^[3] ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {S}}}$

Примечания

1. Галлахер 1971, Теорема 1
2. Галлахер, 1971, Теорема 2
3. Крут, Элсхольц, 2004

Ссылки

• Галлахер, Патрик (1971). «Большое сито». Акта Арифметика . 18 : 77–81. дои : 10.4064/aa-18-1-77-81 .
• Крут, Эрни ; Эльшольц, Кристиан (2004). «О вариантах большего сита». Acta Mathematica Hungarica . 103 (3): 243–254. дои : 10.1023/B:AMHU.0000028411.04500.e2 .