MAKALE

Yayın Tarihi: 5 Kas 2014 | Uğur Efem

0

ASAL ÜRETEN FONKSİYONLAR

Sayılar teorisinde sadece asal sayılara özgü önermeler bulmak genellikle oldukça zordur. Bu anlamda asal sayılar oldukça kaprislidir. Bütün asal sayıları üreten bir fonksiyon bulmak, ya da “asal sayıları veren bir formül” bulmak sanırım bütün matematikçiler için bir çeşit çocukluk düşüdür. Hepimiz en az bir kez bunu denemişizdir.

Elbette böyle bir fonksiyonun kullanışlı olması için bazı beklentilerimizi karşılaması lazım. Örneğin hesaplanması kolay olmalı; en azından bir bilgisayar yardımıyla. Yani hesaplanması çok süre almamalı. Daha da önemlisi $n$’inci asalı hesaplamak için bu asalın ne olduğunu bilmeyi gerektirmemesi! Mesela, bütün asaları p_1,p_2,p_3,\ldots olarak listeleyleim ve n sayısını n‘inci asala götüren fonksiyonu düşünelim. Bu elbette bütün asal sayıları veren bir fonksiyon, ama asal sayı “üreten” bir fonksiyon demek pek doğru olmaz. Çünkü n‘inci asalı üretmesi için zaten bu sayıyı biliyor olmamız gerekli!

Demek ki asal sayı üretmekten ne anlamamız gerektiği üzerinde biraz durmamız gerekli. İdeal olarak asal sayı üreten bir fonksiyon bütün asal sayıları üretmeli, daha da iyisi bu işi sırasıyla yapmalı. Yani her n doğal sayısı için f(n)=p_n olmalı. İlk bakışta bu isteğimiz oldukça aç gözlü görünüyor. Bu ideal isteğimizi karşılayan bir fonksiyon örneği vereceğim ama önce biraz

Hero ve Leandros, J. M. W. Turner, 1837

Hero ve Leandros, J. M. W. Turner, 1837

hazırlık gerekli.

Asal sayıların dağılımını anlamak için kullanılan en temel fonksiyonlardan biri herhangi bir n doğal sayısını n‘den küçük asal sayıların sayısına götüren \pi fonksiyonudur. Başka bir deyişle \pi(n), n‘den küçük (yada eşit) asal sayıların sayısı olarak tanımlanır. Vereceğim örnek temel olarak \pi fonksiyonuna dayanıyor.

Örnek: ([6])
Herhangi bir n ve i\in\{1,2,\ldots n-1\} doğal sayıları için \frac{n}{i} rasyonel sayınısa bakalım,
\left\lfloor\frac{n}{i}\right\rfloor, bu rasyonel sayının tam kısmı olsun. Öyleyse \frac{\left\lfloor\frac{n}{i}\right\rfloor}{\frac{n}{i}} sayısı 0 ve 1 arasında olmak zorunda.
Şimdi \left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{\frac{n}{i}}\right\rfloor sayısına bakarsak, kolayca bu sayının 0 ya da 1 olduğunu görebiliriz. Hatta kolaylıkla bu sayının sadece i sayısı n‘yi böldüğünde (yani \frac{n}{i} doğal sayı olduğunda) 1’e eşit olduğunu da görebiliriz.

Bu gözlemlerden yola çıkarak

g(n) =\displaystyle\sum_{i=1}^{n-1}\left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{\frac{n}{i}}\right\rfloor

fonksiyonunu inceleyelim. Özellikle g fonksiyonu hangi n değerlerinde 1 oluyor bunu hesaplayalım. Bütün n doğal sayıları 1’e bölündüğü için g(n) = 1 ancak ve ancak \{1,\ldots, n-1\} sayıları arasında n‘yi sadece 1 bölüyorsa; yani n asalsa. Öyleyse g fonksiyonu asal sayılarda 1 değerini alıyor, bileşik sayılarda ise 1’den büyük oluyor.

Asal sayılarda 1, bileşik sayılarda 0 değerlerini alan bir fonksiyon elde etmek için f fonksiyonunu f(n) = \left\lfloor\frac{1}{g(n)}\right\rfloor olarak tanımlayalım. Öyleyse n asalken f(n)\pi(n) = \pi(n) yani n‘den küçük ya da eşit asalların sayısı; n bileşik ise f(n)\pi(n) = 0.

Herhangi bir k doğal sayısı için

eğer n=p_k ise \left\lfloor\frac{1}{1+|k-f(n)\pi(n)|}\right\rfloor \cdot n = n

eğer değilse \left\lfloor\frac{1}{1+|k-f(n)\pi(n)|}\right\rfloor \cdot n = 0.

Yukarıdaki ifadenin tam olarak ne zaman n‘ye eşit olduğuna yakından bakalım. Bu ifadenin n‘ye eşit olması için k=f(n)\pi(n) olmalı, aksi halde sıfıra eşit olur. Fakat k=f(n)\pi(n) ifadesi n bir asal sayıysa ve kendisinden küçük veya eşit k tane asal sayı varsa doğru. Bu da n=p_k anlamına gelir!

Nerdeyse aradığımız fonksiyona ulaştık sayılır, fonksiyonu bulabilmek için sayılar teorisinin güçlü teoremlerinde birine ihityacımız var.

Teorem 1. Birden büyük herhangi bir n doğal sayısıyla 2n arasında herzaman bir asal sayı vardır.
Sayılar teorisinde bu sonuç Bertrand postülası olarak bilinir. Sıklıkla olduğu gibi, basit gibi görünen bu teoremin kanıtı kolay değildir. Dileyen okur şık bir kanıtı [2]’de bulabilir.
Bertrand postülasının bizim için kullanışı olan bir sonucu:

Teorem 2. Her k doğal sayısı için p_k\leq 2^k

Kanıt.
k üzerine tümvarımla kanıtlayalım, k=1 ise p_1=2\leq2^1. Şimdi önermemizin k için doğru olduğunu varsayalım ve k+1 için doğru olduğunu kanıtlayalım.
Teorem 1’den dolayı p_k<p_{k+1}\leq 2p_k. Tümevarım hipotezinden dolayı p_k\leq 2^k. Öyleyse, p_{k+1}<2p_k\leq2\cdot 2^k=2^{k+1}. ♦

Son olarak

P(k) = \displaystyle\sum_{n=1}^{2^k}\left\lfloor\frac{1}{1+|k-f(n)\pi(n)|}\right\rfloor \cdot n

fonksiyonuna bakalım. Toplamı 1’den 2^k ‘ya kadar aldığımız için, Teorem~\ref{bert-sonuc}’den dolayı \left\lfloor\frac{1}{1+|k-f(p_k)\pi(p_k)|}\right\rfloor\cdot p_k terimi mutlaka bu toplamda belirecek. Hata bu terim söz konusu toplamda sıfır olmayan tek terim olduğundan, P fonksiyonu k sayısını k‘inci asala götürüyor. Yani P(k) = p_k.

İlk bakışta hedefimize ulaşmışız gibi görünüyor. Fakat oldukça güçlü bir teorem kullandık (Bertrand postülası). Üstelik bulduğumuz fonksiyonun hesap yükü de fazla. k‘inci asalı, yani p_k sayısını hesaplamak 2^k tane terimin toplamını almamız gerekiyor, yani üretmemiz gereken terim sayısı üstel olarak büyüyor. Örneğin p_{20} sayısını hesaplayabilmek için 2^{20} = 1048576 tane terim üretip bunların toplamını almamız lazım. Görüldüğü gibi ilk bir kaç asalı bulabilmek için bile üretmemiz gereken terim sayısı bir milyonun üzerinde. Daha büyük asalları üretmeye kalkarsak üretmemiz gereken terim sayısı daha hızlı aratacak. Daha da trajiği p_k asalını hesaplayabilmemiz için p_k asalını bilmemiz gerekiyor! Çünkü bize bu sayıyı vermesi gereken toplam p_k sayınısını içeren terime kadar ulaşamazsa sonuç sıfır. Demek ki yine p_k asalını ürettik diyemeyiz!

Bütün asalları -hem de sırasıyla- üreten bir fonksiyon bulma girişimimiz biraz hayal kırıklığı ile sonuçlandı. Benzer örnekleri kolayca da çoğaltabiliriz (benzer bir başka örnek için bkz. [7]). Bütün asalları gerçekten üreten, ve kullanışlı bir fonksiyon bulmak koaly görünmüyor. Bekletilerimizi düşürüp yeniden deneyelim.

Bu sefer bütün asallar yerine sonsuz sayıda asal üreten ve elbette kullanışlı olabilecek bir fonksiyon bulmaya çalışalım. Yani bu sefer öyle bir P fonksiyonu bulmalıyız ki her n doğal sayısı için P(n) asal olsun ve n\neq m ise P(n)\neq P(m) sağlansın. Bu koşulu sağlayan fonksiyonlar bulmamız da mümkün, ancak bulduktan sonra durumun yukrıdakinden pek de farklı olmadığını göreceğiz.

Herhangi bir $\mu$ reel sayısı için 2^\mu ifadesini \exp_2(\mu) olarak gösterelim. Bu durumda 2^{2^\mu} = \exp_2(2^\mu)=\exp_2(\exp_2(\mu)) = \exp_2^2(\mu). Bu işlemi herhangi bir n doğal sayısı için n defa tekrar ederek bulduğumuz genel ifadeyi de \exp_2^n(\mu) olarak yazabiliriz.

Burada tanımladığımız ikilik üstel fonksiyon, dolayısıyla ters fonksiyonu da ikilik tabanda logaritma fonksiyonu \log_2. Genel ifade için verdiğimiz fonksiyonun tersi de \log_2^n olarak yazılabilir, yani 2 tabanında logaritma fonksiyonun peş peşe n defa uygulanması ile edilen fonksiyon.

Teorem 3. (Wright, 1951 [8]) Öyle bir \mu reel sayısı vardır ki her n doğal sayısı için \left\lfloor \exp_2^n(\mu)\right\rfloor asaldır.

Yani öyle bir \mu reel sayısı vardır ki, \left\lfloor2^\mu\right\rfloor, \left\lfloor2^{2^\mu}\right\rfloor, \left\lfloor2^{2^{2^\mu}}\right\rfloor,\ldots hep asaldır. Dolayısıyla bu teoremden yola çıkarak  P(1)=\left\lfloor 2^\mu \right\rfloor, P(2)=\left\lfloor 2^{2^\mu}\right\rfloor, P(3)=\left\lfloor 2^{2^{2^\mu}} \right\rfloor,\ldots olarak tanılayabileceğimiz fonksiyon her doğal sayı için bir asal üretir.

Kanıt. Bertrand postülasının (Teorem 1) bir sonucu olarak asal sayılardan oluşan öyle bir (q_n)_{n\in\mathbb N} dizisi vardır ki 2^{q_n}<q_{n+1}<2^{q_{n+1}} - 1 eşitsizliği her n doğal sayısı için doğru olsun.

Bu eşitsizliğin sonucu olarak

\log_2(q_1)<\log_2^2(q_2)<\log_3^3(q_3)<\ldots <\log_2^{n+1}(q_{n+1})<\ldots <\log_2^{n+1}(q_{n+1}+1)<\log_2^n(q_n+1)<\ldots <\log_2(q_1+1)

eşitisizliğini elde edebiliriz. Doalyısıyla (\log_2^n(q_n))_{n\in\mathbb N} dizisi artan ve üstten sınırlı bir dizi, doalyısıyla yakınsak. Bu dizinin limitine \mu diyelim.

Bu durumda, yukarıdaki eşitsizlikten dolayı, her n için \log_2^n(q_n)<\mu<\log_2^n(q_n+1). Bu eşitsizlikte her tarafa \exp_2^n fonksiyonu uygulayarak
q_n<\exp_2^n(\mu)<q_n+1 eşitsizliğine ulaşırız. Dolayısıyla \left\lfloor \exp_2^n(\mu)\right\rfloor doğal sayısı q_n ve q_{n+1} arasında olmalı. Yani
\left\lfloor \exp_2^n(\mu)\right\rfloor = q_n olmak zorunda. ♦

Yine ilk bakışta işimize yarar bir fonksiyon bulmuşuz gibi duruyor ama yine ilk durumdakine benzer problemler var. Birincisi yine Bertrand postülasını kullandık. İkincisi bulduğumuz fonksiyon üstel bir fonksiyon. Yani çok hızlı büyüyor, istediğimiz gibi hesaplaması kolay değil. En önemlisi bu yöntemle asal üretebilmek için \mu sayısının tam olarak ne olduğunu bilmemiz lazım ama kanıtta \mu sayısının sadece varlığını gösterdik. Bu sayının nasıl hesaplanacağına dair herhangi bir yöntem kanıtımızda yok! Elbette bu \mu sayısını yaklaşık olarak hesaplamız mümkün. Fakat tam olarak bilmediğimiz için hesaplarımızda hata payı olacaktır. Bu hata payını iyi kontrol edemezsek ürettiğimiz sayı asal olmaktan uzaklaşır!

Wright’ın teoreminden daha önce, 1947’de Mills bu bu koşulu sağlayan başka bir fonksiyon buldu.

Theorem 4. Öyle bir \Theta reel sayısı vardır ki herhangi bir n doğal sayısı için \left\lfloor\Theta^{3^n}\right\rfloor her zaman bir asal sayı olur.

Mills’in teoreminin kanıtındaki temel fikir Wrigth’ın teoremiyle benzerdir. Yine bir dizi oluşturup \Theta sayısını bu dizinin limiti olarak bulabiliriz. Yine benzer sebeplerle Mills’in fonksiyonu da asal üretmek için kullanışlı değil. Üstelik kanıtı Bertrand postülasından daha güçlü olan Ingham’a ait ([3]) bir sonuca dayanıyor:

Teorem 5. Öyle bir k sabiti vardır ki p_{n+1}-p_n<kp_n^{5/8}.

Mills’in ve Wright’ın sonuçlarını tek bir teoremde toplayan ise Ore’dur (\cite{Ore}).

Teorem 6.  f sürekli ve artan bir fonksiyon olsun. Asallardan oluşan bir (p_n)_{n\in\mathbb N} dizi ve (q_n)_{n\in\mathbb N} onu bir alt dizisi olsun. Sıfırdan büyük \epsilon_n ve \delta_n sayıları için f fonksiyonu f(q_n-\delta_n)<q_{n+1}-\delta_{n+1}\leq q_{n+1}+\epsilon_{n+1} < f(q_n+\epsilon_n)  eşitsizliğini sağlıyosa, öyle bir $\Theta$ reel sayısı vardır ki \left\lfloor f^n(\Theta))\right\rfloor sayısı her n için bir asal sayıdır. Daha da fazlası \left\lfloor f^n(\Theta))\right\rfloor = q_n.

Ore’un teoreminde f(x) = x^3 alırsak Mills’in teoremini, f(x)=2^x alırsak Wright’ın teoremini elde ederiz.

 

KAYNAKLAR

[1] Dudley, U. , “History of a Formula for Primes”, The American Math. Monthly, Vol.76, No. 1 sayfa 23-28, Ocak 1969
[2] Göral, H., Paksoy, B., “Bertrand Postülası ve Asalların Dağılımı”, Matematik Dünyası, 2012-IV, sayfa 82-90.
[3] Ingham, A. E., “On the Difference Between Consecutive Primes”, Quart. J. Math., Oxford, Ser.(2) 8, sayfa 255-266, 1937.
[4] Matiyasevich, Yu., “Formula for Prime Numbers”, Tabachnikov, S., Kvant Selecta: Algebra and Analysis, II, American Math. Society, sayfa 13–24
[5] Ore, \O., “On the Seleciton of Subsequneces”, Proc. Amer. Math. Soc., 53, 1952.
[6] Regimbal, S., “An Explicit Formula for kth Prime”, Mathematics Magazine, Vol. 48, No. 4, sayfa 230-232, Eylül 1975.
[7] Ribenboim, P., “Are There Functions That Generate Prime Numbers”, The College Math. Journal, Vol. 28, No. 5 , sayfa 352-359, Kasım 1997.
[8] Wright, E. M., “A Prime Representing Function”, The American Math. Monthly, Vol. 58, sayfa 616-618, 1951.

Etiketler: , , ,


Yazar

Lisans eğitimini İstanbul Bilgi Üniversitesi Matematik Bölümü’nde, Yüksek Lisans eğitimini Sabancı Üniversitesi’nde yine Matematik Bölümü’nde tamamladı. 2011 Eylül ayından beri Oxford Üniversitesi Matematik Enstitüsü’nde doktora öğrencisi.






Yorum yapın (Facebook, Twitter gibi hesaplarınız geçerlidir.)

Back to Top ↑
  • Patreon’dayız

  • Bizi Takip Edin

  • iTunes Bağlantısı

  • Reklam Alanı

  • Destekçiler

  • E-POSTA LİSTESİ

    Yeni bir yayınımız yayımlandığında e-posta yoluyla haberdar olmak için adresinizi bu alana girin.

    Diğer 99.731 aboneye katılın

  • Hızlı Takvim

    Kasım 2014
    P S Ç P C C P
    « Eki   Ara »
     12
    3456789
    10111213141516
    17181920212223
    24252627282930