Диксон леммасы және сандар теориясының кейбір мәселелері
Dickson's lemma
Диксон леммасы: Натурал сандар жиынында минималды элементтер саны шектеулі. Комбинаторика, сандар теориясы, алгебрада қолданылады. Математикалық тұжырым.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикада Диксон леммасы, табиғи сандар жұптарының кез келген жиынында шектеулі мөлшерде ең кіші элементтер болатынын мәлімдейді. Комбинаторикадан алынған бұл қарапайым факт американдық алгебрашы Л. Э. Диксонға жатқызылды, ол оны сандар теориясындағы толық сандар туралы нәтижені дәлелдеу үшін пайдаланды.
In mathematics, Dickson's lemma states that every set of tuples of natural numbers has finitely many minimal elements. This simple fact from combinatorics has become attributed to the American algebraist L. E. Dickson, who used it to prove a result in number theory about perfect numbers.
Мысал
Белгілі бір табиғи сан болсын, және оң нақты сандар бойынша анықталғанда, көбейтіндісі кем дегенде болатын сандар жұптарының жиыны болсын. Бұл жиын, оң сандар бойынша қарастырылғанда, формасының шексіз көп минималды элементтеріне ие, әрбір оң сан үшін біреуінен; бұл нүктелер жиыны гиперболаның бір тармағын құрайды. Бұл гиперболадағы жұптар минималды, себебі жиынға жататын екінші жұптың екі координатасы да бірдей немесе кіші болуы мүмкін емес. Алайда, Диксон леммасы тек табиғи сандардың топтамаларына қатысты, ал табиғи сандар бойынша тек шекті санда ғана минималды жұптар бар. Кез келген минималды табиғи сандар жұбы үшін және , егер x K-дан үлкен болса, онда (x - 1, y) де S жиынына жатады, бұл (x, y) жұбының минималдығына қайшы келеді, ал y K-дан үлкен болса, онда (x, y - 1) де S жиынына жатады. Сондықтан, табиғи сандар бойынша S жиынында ең көп дегенде минималды элементтер, яғни шекті санда бар.
Let be a fixed natural number, and let be the set of pairs of numbers whose product is at least When defined over the positive real numbers, has infinitely many minimal elements of the form , one for each positive number ; this set of points forms one of the branches of a hyperbola. The pairs on this hyperbola are minimal, because it is not possible for a different pair that belongs to to be less than or equal to in both of its coordinates. However, Dickson's lemma concerns only tuples of natural numbers, and over the natural numbers there are only finitely many minimal pairs. Every minimal pair of natural numbers has and , for if x were greater than K then (x − 1, y) would also belong to S, contradicting the minimality of (x, y), and symmetrically if y were greater than K then (x, y − 1) would also belong to S. Therefore, over the natural numbers, has at most minimal elements, a finite number.
Жалпылау және қолдану
Диксон өзінің леммасын кез келген берілген сан үшін, ең көпі шешімді саны бар тақ толық сандар ғана болуы мүмкін екенін дәлелдеу үшін пайдаланды. Дегенмен, ең болмағанда бір тақ толық сан бар ма деген сұрақ әлі де ашық күйде. P-тегіс сандарының арасындағы бөлінгіштік қатынасы, яғни жай факторлары P шекті жиынына жататын натурал сандар, осы сандарға P-ге изоморфты жартылай реттелген жиын құрылымын береді. Сондықтан, P-тегіс сандарының кез келген S жиыны үшін, S жиынының әрбір елемі осы жиынның бір санына бөлінетін S жиынының шекті ішкі жиыны бар. Мысалы, бұл факт Sylver монетасы ойынының бастапқы позициясынан жеңіске және жеңіліске апаратын қадамдарды жіктеуге арналған алгоритмнің бар екенін көрсету үшін қолданылды, тіпті алгоритмнің өзі белгісіз болса да. Бұл сәйкестік бойынша Диксон леммасын Хилберттің негіз теоремасының, яғни әрбір полиномдық идеалдың мономиялармен жасалған идеалдар үшін шекті негізі бар екенін айтатын теореманың ерекше жағдайы ретінде қарастыруға болады. Шындығында, Пол Гордан 1899 жылы Диксон леммасының осы қайта формулировкасын Хилберттің негіз теоремасын дәлелдеудің бір бөлігі ретінде пайдаланды.
Dickson used his lemma to prove that, for any given number , there can exist only a finite number of odd perfect numbers that have at most prime factors. However, it remains open whether there exist any odd perfect numbers at all. The divisibility relation among the P smooth numbers, natural numbers whose prime factors all belong to the finite set P, gives these numbers the structure of a partially ordered set isomorphic to Thus, for any set S of P smooth numbers, there is a finite subset of S such that every element of S is divisible by one of the numbers in this subset. This fact has been used, for instance, to show that there exists an algorithm for classifying the winning and losing moves from the initial position in the game of Sylver coinage, even though the algorithm itself remains unknown. The tuples in correspond one for one with the monomials over a set of variables Under this correspondence, Dickson's lemma may be seen as a special case of Hilbert's basis theorem stating that every polynomial ideal has a finite basis, for the ideals generated by monomials. Indeed, Paul Gordan used this restatement of Dickson's lemma in 1899 as part of a proof of Hilbert's basis theorem.