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

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

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

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

${\displaystyle 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 — произведение различных простых чисел, — функция Мёбиуса и множество целых чисел из A , делящихся на d , а S(A, P) определяется как: ${\displaystyle \mu }$ ${\displaystyle A_{d}}$

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

Ограничения

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

Рекомендации

1. Иванец, Хенрик. Решето Эратосфена-Лежандра. Annali della Scuola Normale Superiore di Pisa – Classe di Scienze, Sér. 4, 4 нет. 2 (1977), стр. 257–268 MR 453676.