Кіріспе
Бүкіл сандардың іріктелген жиындарының мөлшерін бағалау тәсілдері. Іріктеу теориясы – сан теориясындағы жалпы әдістердің жиынтығы, іріктелген бүтін сандар жиындарының мөлшерін есептеу немесе, дәлірек айтқанда, бағалау үшін жасалған. Іріктелген жиынның классикалық мысалы – белгілі бір X шегіне дейінгі жай сандар жиыны. Сәйкесінше, іріктеудің классикалық мысалы – Эратоспеннің іріктегіші немесе жалпырақ Лежандрдің іріктегіші. Осы әдістерді қолданып, жай сандарға тікелей шабуыл жасау көп ұзамай қателік мүшелерінің жиналуынан туындайтын көріне бұрынғысы жоқ кедергілерге жетеді. ХХ ғасырдағы сан теориясының маңызды бағыттарының бірінде, іріктеудің қандай болуы керек деген қарапайым түсінікпен, тікелей шабуылдың кейбір қиындықтарынан қашудың жолдары табылды. Сәтті тәсілдердің бірі – нақты іріктелген сандар жиынын (мысалы, жай сандар жиынын) басқа, қарапайым жиынмен (мысалы, дерлік жай сандар жиынымен) жуықтау, ол әдетте бастапқы жиыннан сәл үлкен және талдауға оңай. Күрделірек іріктегіштер де жиындармен тікелей жұмыс істемейді, керісінше, оларды осы жиындардағы мұқият таңдалған салмақтық функциялар бойынша санайды (кейбір элементтерге басқаларына қарағанда көбірек "салмақ" беру мүмкіндігі). Сонымен қатар, кейбір қазіргі қолданыстарда іріктегіштер іріктелген жиынның мөлшерін бағалау үшін емес, жиынның ішінде үлкен және одан тыс жерде көбінесе кішкентай болатын функцияны жасау үшін қолданылады, бұл жиынның сипаттамалық функциясына қарағанда талдауға оңай. "Іріктегіш" терминін алғаш рет 1915 жылы норвегиялық математик Вигго Брун қолданған. Алайда Брунның жұмысы Бірінші дүниежүзілік соғыста қаза тапқан француз математигі Жан Мерлиннің еңбектерінен шабыттанды, және оның қолжазбаларының тек екі ғана данасы сақталған.
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be. One successful approach is to approximate a specific sifted set of numbers (e. g. the set of prime numbers) by another, simpler set (e. g. the set of almost prime numbers), which is typically somewhat larger than the original set, and easier to analyze. More sophisticated sieves also do not work directly with sets per se, but instead count them according to carefully chosen weight functions on these sets (options for giving some elements of these sets more "weight" than others). Furthermore, in some modern applications, sieves are used not to estimate the size of a sifted
set, but to produce a function that is large on the set and mostly small outside it, while being easier to analyze than the characteristic function of the set. The term sieve was first used by the norwegian mathematician Viggo Brun in 1915. However Brun's work was inspired by the works of the french mathematician Jean Merlin who died in the World War I and only two of his manuscripts survived.
Мысал
Let және жай санның әрқайсысы үшін Мёбиус функциясы теріс болады, сондықтан біз аламыз.
Сілте теориясының әдістері
Сита теориясының әдістері өте қуатты болуы мүмкін, бірақ олар «паритет проблемасы» деп аталатын кедергімен шектеледі. Бұл проблема, шамамен айтқанда, сита теориясының әдістеріне жай сандардың тақ санына ие сандар мен жұп санына ие сандарды ажыратуда үлкен қиындық тудырады. Бұл паритет проблемасы әлі толыққанды түсініксіз. Сандар теориясының басқа әдістерімен салыстырғанда, сита теориясы салыстырмалы түрде қарапайым, себебі ол алгебралық сандар теориясы немесе аналитикалық сандар теориясынан күрделі түсініктерді міндетті түрде талап етпейді. Дегенмен, жетілдірілген ситалар өте күрделі және нәзік болуы мүмкін (әсіресе сан теориясының басқа терең әдістерімен біріктірілгенде), сондықтан сан теориясының осы тармағына арналған толық оқулықтар жазылған; классикалық анықтама – және заманауи мәтін – . Бұл мақалада талқыланған сита әдістері, квадраттық сита және жалпы сан өрісі ситасы сияқты бүтін сандарды жіктеуге арналған сита әдістерімен тікелей байланысты емес. Бұл жіктеу әдістері Эратоспеннің ситасының идеясын пайдаланады, сандар тізімінен кішігірім жай сандарға толық жіктелетін сандарды тиімді анықтау үшін.
The sieve methods discussed in this article are not closely related to the integer factorization sieve methods such as the quadratic sieve and the general number field sieve. Those factorization methods use the idea of the sieve of Eratosthenes to determine efficiently which members of a list of numbers can be completely factored into small primes.