Метод решета

Ме́тод решета́, один из общих методов теории чисел, обобщающий принцип высеивания составных чисел из натурального ряда (см. в статье Решето Эратосфена). Проблема метода решета состоит в оценке для конечного множества ${\displaystyle A}$ целых чисел количества тех элементов, которые не делятся ни на какое простое число ${\displaystyle p}$ из некоторого множества ${\displaystyle P}$ простых чисел. Оценивается «просеивающая» функция ${\displaystyle S(A;P,z)}$, обозначающая количество указанных элементов из ${\displaystyle A}$ при дополнительном условии: ${\displaystyle p<z}$. Для получения оценок просеивающей функции часто используется информация о числе ${\displaystyle N\left(A_{q}\right)}$ элементов множества ${\displaystyle A_{q}}$, состоящего из элементов ${\displaystyle A}$, которые делятся на свободное от квадратов число ${\displaystyle q}$. При ${\displaystyle q=1}$ множество ${\displaystyle A_{q}=A}$. Поэтому обычно оценивается более общая просеивающая функция ${\displaystyle S\left(A_{q};P,z\right)}$.</z<></math>

При выборе ожидаемого значения для ${\displaystyle N\left(A_{q}\right)}$ в форме ${\displaystyle (\omega (q)/q)X}$, где ${\displaystyle X}$ – ожидаемое значение для ${\displaystyle N(A)}$ и ${\displaystyle \omega (q)}$ – мультипликативная функция, руководствуются тем, чтобы погрешность

${\displaystyle R(X,q)=N\left(A_{q}\right)-(\omega (q)/q)X}$

была относительно мала. Если при этом ${\displaystyle \omega (p)=k}$ (по крайней мере «в среднем»), то ${\displaystyle k}$ называется размерностью решета.

Общая теория метода решета с её приложениями продвинулась наиболее далеко в случае линейного решета (при ${\displaystyle k=1}$). Существуют различные специализации метода решета, наиболее важные из которых принадлежат B. Бруну (см. в статье Решето Бруна) и А. Сельбергу (см. в статье Решето Cельберга).

В приложениях метода решета к аддитивным задачам (см. в статье Аддитивная теория чисел), кроме оценок просеивающей функции сверху, необходимы оценки этой функции снизу. Получение оценок снизу может быть основано на логическом комбинаторном тождестве

{{center|${\displaystyle S\left(A_{q};P,z\right)=N\left(A_{q}\right)-\sum _{p<z,\ p\in P}S\left(A_{q,p};P,p\right)}$ представимо в виде ${\displaystyle N=p+P_{2}}$, где ${\displaystyle p}$ – простое число, ${\displaystyle P_{2}}$ содержит не более двух простых множителей.</z,></math>