Sõelateooria

Allikas: Vikipeedia

Sõelateooria (inglise keeles sieve theory) kujutab enesest hulka arvuteooria üldisi meetodeid, mille eesmärk on loendada või realistlikumalt hinnata täisarvude sõelutud hulkade elementide arvu (võimsust). Sõelutud hulga prototüübiks on mingist arvust X väiksemate algarvude hulk. Sõela prototüübiks on Eratosthenese sõel või üldisemalt Legendre'i sõel. Algarvude uurimine nende meetoditega jõuab kiiresti näiliselt ületamatute raskusteni, mis tulenevad vealiikmete kuhjumisest. 20. sajandi arvuteoorias on õnnestunud leida viise mõningate raskuste vältimiseks.

Üks edukas lähenemine on lähendada mingit sõelutud arvuhulka (näiteks algarvude hulka) teise, lihtsama hulgaga, näiteks peaaegu algarvude (almost prime) hulgaga, mis on algsest hulgast tavaliselt mõnevõrra suurem ja hõlpsamini analüüsitav. Keerukamad sõelad ei tegele otseselt hulkadega, vaid loendavad neid hulki hoolikalt valitud kaalufunktsioonidega, mis annavad hulkade ühtedele elementidele rohkem "kaalu" kui teistele.

Tänapäeval kasutatavate sõelade seas on Bruni sõel, Selbergi sõel ja suur sõel. Üks sõelateooria algseid eesmärke oli püüda tõestada arvuteooria hüpoteese (näiteks kaksikalgarvude hüpotees). Kuigi sõelateooria algsed eesmärgid on suuremalt jaolt saavutamata, on tehtud osalisi edusamme, eriti koos teiste arvuteooria meetoditega. Suuremate saavutuste seas on:

Sõelateooria meetodid võivad olla päris võimsad, kuid nähtavasti on neile takistuseks nn paarsusprobleem (parity problem), mis seisneb selles, et sõelateooria meetoditega on äärmiselt raske teha vahet paaritu arvu algteguritega arvudel ja paarisarvu algteguritega arvudel.

Võrreldes teiste arvuteooria meetoditega on sõelateooria võrdlemisi elementaarne, sest ta ei vaja tingimata keerulisi mõisteid algebralisest arvuteooriast või analüütilisest arvuteooriast. Siiski võib keerulisemate sõelte kasutamine olla vägagi komplitseeritud, eriti juhul, kui kasutatakse ka arvuteooria teisi sügavaid meetodeid.

Sõelateoorial on teatav seos sõelaalgoritmidega (näiteks üldine arvukorpusesõel (general number field sieve)), mida kasutatakse suurte arvude algteguriteks lahutamisel.

Kirjandus[muuda | muuda lähteteksti]

  • H. Halberstam and H. E. Richert. Sieve Methods. London: Academic Press, 1974. ISBN 0-12-318250-6
  • Cojocaru, Alina Carmen & Murty, M. Ram. An introduction to sieve methods and their applications, vol. 66, London Mathematical Society Student Texts, Cambridge University Press, 2006, ISBN 0521848164