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

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

Заявление

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

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

|{\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]

Приложения

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

The number of integers  $n\leq N$ , such that the order of  $n$  modulo  $p$  is  $\leq N^{\theta }$  for all primes  $p\leq N^{\theta +\epsilon }$  is  ${\mathcal {O}}(N^{\theta })$ .

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

Примечания

^ Галлахер 1971, Теорема 1
^ Галлахер, 1971, Теорема 2.
^ Крут, Эльшольц, 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 .

[1] Галлахер 1971, Теорема 1

[2] Галлахер, 1971, Теорема 2.

[3] Крут, Эльшольц, 2004 г.

[1]

[2]

[3]