сито Лежандра

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

Личность Лежандра

Центральная идея метода выражается следующим тождеством, иногда называемым тождеством Лежандра :

$S(A,P)=\sum _{a\in A}\sum _{d\mid a;\,d\mid P}\mu (d)=\sum _{d\mid P}\mu (d)|A_{d}|,$

где A — набор целых чисел, P — произведение различных простых чисел, $\mu$ — функция Мёбиуса , а $A_{d}$ — это набор целых чисел в A, делящихся на d , а S(A, P) определяется как:

$S(A,P)=|\{n:n\in A,\gcd(n,P)=1\}|$

т.е. S ( A , P ) — это количество чисел в A без общих с P множителей .

Обратите внимание, что в наиболее типичном случае A — это все целые числа, меньшие или равные некоторому действительному числу X , P — произведение всех простых чисел, меньших или равных некоторому целому числу z < X , и тогда тождество Лежандра принимает вид:

${\begin{aligned}S(A,P)={}&\sum _{d\mid P}\mu (d)\left\lfloor {\frac {X}{d}}\right\rfloor \\[6pt]={}&\lfloor X\rfloor -\sum _{p_{1}\leq z}\left\lfloor {\frac {X}{p_{1}}}\right\rfloor +\sum _{p_{1}<p_{2}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}}}\right\rfloor \\[4pt]&{}-\sum _{p_{1}<p_{2}<p_{3}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots +\mu (P)\left\lfloor {\frac {X}{P}}\right\rfloor \end{aligned}}$

(где $\lfloor X\rfloor$ обозначает функцию пола ). В этом примере очевиден тот факт, что тождество Лежандра выведено из Решета Эратосфена: первый член — это количество целых чисел ниже X , второй член удаляет кратные всем простым числам, третий член возвращает кратные двум простым числам. (которые были неправильно подсчитаны из-за того, что их «вычеркнули дважды»), но также добавляет обратно числа, кратные трем простым числам, слишком много, и так далее, пока все $2^{\pi (z)}$ (где $\pi (z)$ обозначает количество простых чисел ниже z ) были рассмотрены комбинации простых чисел.

Как только S ( A , P ) рассчитано для этого особого случая, его можно использовать для оценки $\pi (X)$ используя выражение

$S(A,P)\geq \pi (X)-\pi (z)+1,\,$

что непосредственно следует из определения S ( A , P ).

Ограничения

Решето Лежандра имеет проблему с дробными частями членов, которые накапливаются в большую ошибку, что означает, что в большинстве случаев сито дает только очень слабые оценки. По этой причине он почти никогда не используется на практике, поскольку его вытесняют другие методы, такие как сито Бруна и сито Сельберга . Однако, поскольку эти более мощные сита являются развитием основных идей сита Лежандра, полезно сначала понять, как это сито работает.