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

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.

Uğur Efem

About the Author

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.

Reklam Alanı

ASAL ÜRETEN FONKSİYONLAR

KAYNAKLAR

Uğur Efem

About the Author

Bir cevap yazın Cevabı iptal et

Reklam Alanı

Sitede ara

Aktif Programlar

Patreon’dayız

Destekçiler

E-POSTA LİSTESİ