Kare içermeyen tamsayı - Square-free integer

10 karesizdir, çünkü 1'den büyük bölenleri 2, 5 ve 10'dur ve hiçbiri tam kare değildir (ilk birkaç tam kare 1, 4, 9 ve 16'dır)

In matematik , bir squarefree tamsayı (ya squarefree tamsayı ) bir olan tamsayı olan bölünebilir hiçbir tarafından mükemmel kare diğeri Yani 1. den, onun asal çarpanlara her asal için tam bir faktörüne sahip İçinde göründüğünü söyledi. Örneğin, 10 = 2 ⋅ 5 karesizdir , ancak 18 = 2 ⋅ 3 ⋅ 3 karesizdir , çünkü 18, 9 = 3 ² ile bölünebilir . En küçük pozitif kare içermeyen sayılar

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, ... (sekans A005117 içinde OEIS )

Kare içermeyen çarpanlara ayırma

Her pozitif tamsayı n benzersiz bir şekilde çarpanlara ayrılabilir:

${\displaystyle n=\prod _{i=1}^{k}q_{i}^{i},}$

nerede birinden farklıdır kare içermeyen tam sayılardır İkili aralarında asal . ${\displaystyle q_{i}}$

Bu denir kare içermeyen çarpanlarına ait n .

İzin vermek

${\displaystyle n=\prod _{j=1}^{h}p_{j}^{e_{j}}}$

olmak asal çarpanlara arasında n , s _j farklı olan asal sayılar . Daha sonra karesiz çarpanlara ayırmanın faktörleri şu şekilde tanımlanır:

${\displaystyle q_{i}=\prod _{j:e_{j}=i}p_{j}.}$

Bir tamsayı, ancak ve ancak tümü için i > 1 ise karesizdir . Biri büyük bir tam sayı k başka tamsayı inci güç ancak ve ancak k tüm bir bölen bir i şekilde${\displaystyle q_{i}=1}$${\displaystyle q_{i}\neq 1.}$

Tam sayıların karesiz çarpanlara ayrılmasının kullanımı, hesaplanmasının asal çarpanlara ayırmanın hesaplanması kadar zor olması gerçeğiyle sınırlıdır. Daha kesin olarak , kare içermeyen bir çarpanlara ayırmayı hesaplamak için bilinen her algoritma aynı zamanda asal çarpanlara ayırmayı da hesaplar. Bu, aynı tanımların verilebildiği polinomlar durumunda dikkate değer bir farktır , ancak bu durumda, karesiz çarpanlara ayırmanın hesaplanması yalnızca tam çarpanlara ayırmadan daha kolay olmakla kalmaz, aynı zamanda tüm standartların ilk adımıdır. çarpanlara ayırma algoritmaları.

Tam sayıların kare içermeyen çarpanları

Bir tamsayı radikali olan, en büyük kare içermeyen faktör olduğu, önceki bölümde notasyonu ile. Bir tamsayı, ancak ve ancak köküne eşitse karesizdir. ${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}}$

Her pozitif tamsayı n , güçlü bir sayının (yani, her asal çarpanın karesine bölünebilen bir tam sayıdır) ve asal olan karesiz bir tamsayının ürünü olarak benzersiz bir şekilde temsil edilebilir . Bu çarpanlara ayırmada, karesiz çarpan ve güçlü sayı ise${\görüntüleme stili q_{1},}$${\displaystyle \textstyle \prod _{i=2}^{k}q_{i}^{i}.}$

Kare içermeyen kısım ait n olan büyük kare içermeyen bölen hangi k bir n ile aralarında asal olan n / k . Bir tamsayının karesiz kısmı en büyük karesiz bölenden daha küçük olabilir.${\görüntüleme stili q_{1},}$${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}.}$

Herhangi bir rasgele pozitif tamsayı n , bir kare ve kare içermeyen bir tamsayının ürünü olarak benzersiz bir şekilde temsil edilebilir :

${\displaystyle n=m^{2}k}$

Bu çarpanlara olarak, m, en bölen bir N böyle m ² bir bölen bir n .

Özetle, her tamsayı ile doğal olarak ilişkilendirilen üç karesiz faktör vardır: karesiz kısım, yukarıdaki faktör k ve en büyük karesiz faktör. Her biri bir sonrakinin bir faktörüdür. Tümü, asal çarpanlara ayırmadan veya karesiz çarpanlara ayırmadan kolayca çıkarılabilir : eğer

${\displaystyle n=\prod _{i=1}^{h}p_{i}^{e_{i}}=\prod _{i=1}^{k}q_{i}^{i}}$

n'nin asal çarpanlara ayırma ve karesiz çarpanlarına ayırma , burada farklı asal sayılar, o zaman karesiz kısım ${\displaystyle p_{1},\ldots ,p_{h}}$

${\displaystyle \prod _{e_{i}=1}p_{i}=q_{1},}$

Bölümün kare olması gibi kare içermeyen faktör

${\displaystyle \prod _{e_{i}{\text{ tek}}}p_{i}=\prod _{i{\text{ tek}}}q_{i},}$

ve kare içermeyen en büyük faktör

${\displaystyle \prod _{i=1}^{h}p_{i}=\prod _{i=1}^{k}q_{i}.}$

Örneğin, bir sahiptir kare içermeyen bir parçasıdır 7 , bölüm kare şekilde kare içermeyen bir faktördür 3 ⋅ 7 = 21 , ve en büyük kare içermeyen bir faktördür 2 ⋅ 3 ⋅ 5 ⋅ 7 = 210 . ${\displaystyle n=75600=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7,}$${\displaystyle q_{1}=7,\;q_{2}=5,\;q_{3}=3,\;q_{4}=2.}$

Tam asal çarpanlara ayırmayı hesaplamaktan daha hızlı olan bu kare içermeyen faktörlerin herhangi birini hesaplamak için hiçbir algoritma bilinmemektedir. Özellikle, bir tamsayının karesiz kısmını hesaplamak ve hatta bir tamsayının karesiz olup olmadığını belirlemek için bilinen bir polinom-zaman algoritması yoktur . Buna karşılık, polinom zamanlı algoritmalar, asallık testi için bilinir . Bu, tam sayıların aritmetiği ile tek değişkenli polinomların aritmetiği arasındaki büyük bir farktır , çünkü polinom-zaman algoritmaları, polinomların karesiz çarpanlara ayrılması için bilinir (kısaca, bir polinomun kare içermeyen en büyük faktörü onun bölümüdür). tarafından büyük ortak bölen polinom ve bir biçimsel türevi ).

eşdeğer karakterizasyonlar

Pozitif bir n tamsayısının karesiz olması ancak ve ancak n'nin asal çarpanlarına ayrılmasında , üs birden büyük olan hiçbir asal çarpan oluşmazsa. Aynı şeyi belirtmenin bir başka yolu da , n'nin her p asal çarpanı için , p asalının n  /  p'yi eşit olarak bölmemesidir  . Ayrıca , n ancak ve ancak her çarpanlara içinde eğer kare serbesttir n  =  ab , faktörler bir ve b vardır aralarında asal . Bu tanımın hemen bir sonucu, tüm asal sayıların karesiz olmasıdır.

Pozitif bir tam sayı , n -kare serbest ise ve sadece değişmeli gruplar arasında sırayla N olan izomorfik durumda olan, ancak ve herhangi bir grup olduğu takdirde halkalı . Bu, sonlu olarak oluşturulmuş değişmeli grupların sınıflandırılmasından kaynaklanmaktadır .

Bir n tamsayısı , yalnızca ve yalnızca Z  /  n Z faktör halkasının (bkz. modüler aritmetik ) alanların bir ürünü olması durumunda karesizdir . Bu, Çin kalan teoreminden ve Z  /  k Z biçimindeki bir halkanın, ancak ve ancak k bir asal ise bir alan olduğu gerçeğinden kaynaklanır .

Her pozitif tamsayı için n , tüm pozitif bölenler kümesi n bir hale kısmen sıralı küme kullandığımız takdirde Bölünebilme sipariş ilişkisi olarak. Bu kısmen sıralı küme her zaman bir dağıtımlı kafestir . Bu bir Boole cebridir, ancak ve ancak n karesiz ise .

Pozitif bir tamsayı n , ancak ve ancak μ ( n ) ≠ 0 ise karesizdir , burada μ Möbius fonksiyonunu gösterir .

Dirichlet serisi

Möbius fonksiyonunun mutlak değeri , kare içermeyen tamsayılar için gösterge fonksiyonudur – yani, | μ ( n ) | n karesiz ise 1'e, karesiz ise 0'a eşittir. Dirichlet serisi bu gösterge fonksiyonu olduğunu

${\displaystyle \sum _{n=1}^{\infty }{\frac {|\mu (n)|}{n^{s}}}={\frac {\zeta(lar)}{\zeta (2s)}},}$

burada ζ ( ler ) olan Riemann zeta fonksiyonu . Bu, Euler ürününden gelir

${\displaystyle {\frac {\zeta(lar)}{\zeta (2s)}}=\prod _{p}{\frac {(1-p^{-2s})}{(1-p^{ -s})}}=\prod _{p}(1+p^{-s}),}$

ürünlerin asal sayılar üzerinden alındığı yer.

Dağıtım

Let S ( x ) 1 arasında kare içermeyen tamsayı sayısını göstermek x ( OEIS :  A013928 1 ile indeksi kaydırır). Büyük için n az, pozitif tamsayılar 3/4 n bu numaralardan 9/8 9 ile bölünebilir değildir ve benzerleri, 4 ile bölünebilir değildir. Bu oranlar çarpımsal özelliği sağladığından (bu, Çin kalan teoreminden gelir ), yaklaşıklığı elde ederiz:

${\displaystyle {\begin{hizalanmış}Q(x)&\yaklaşık x\prod _{p\ {\text{asal}}}\left(1-{\frac {1}{p^{2}}} \right)=x\prod _{p\ {\text{prime}}}{\frac {1}{(1-{\frac {1}{p^{2}}})^{-1}} }\\&\yaklaşık x\prod _{p\ {\text{prime}}}{\frac {1}{1+{\frac {1}{p^{2}}}+{\frac {1 }{p^{4}}}+\cdots }}={\frac {x}{\sum _{k=1}^{\infty }{\frac {1}{k^{2}}}} }={\frac {x}{\zeta (2)}}={\frac {6x}{\pi ^{2}}}.\end{hizalı}}}$

Bu argüman, tahmini elde etmek için titiz hale getirilebilir ( büyük O notasyonu kullanılarak )

${\displaystyle Q(x)={\frac {6x}{\pi ^{2}}}+O\sol({\sqrt {x}}\sağ).}$

Bir ispatın taslağı: yukarıdaki karakterizasyon

${\displaystyle Q(x)=\sum _{n\leq x}\sum _{d^{2}\mid n}\mu (d)=\sum _{d\leq x}\mu (d) \sum _{n\leq x,d^{2}\mid n}1=\sum _{d\leq x}\mu (d)\left\lfloor {\frac {x}{d^{2} }}\sağ\rzemin ;}$

Geçen summand sıfır olduğunu gözlemleyerek , bu sonuçları ${\displaystyle d>{\sqrt {x}}}$

${\displaystyle {\begin{aligned}Q(x)&=\sum _{d\leq {\sqrt {x}}}\mu (d)\left\lfloor {\frac {x}{d^{2 }}}\right\rfloor =\sum _{d\leq {\sqrt {x}}}{\frac {x\mu (d)}{d^{2}}}+O\left(\sum _ {d\leq {\sqrt {x}}}1\sağ)=x\sum _{d\leq {\sqrt {x}}}{\frac {\mu (d)}{d^{2}} }+O({\sqrt {x}})\\&=x\sum _{d}{\frac {\mu (d)}{d^{2}}}+O\left(x\sum _ {d>{\sqrt {x}}}{\frac {1}{d^{2}}}+{\sqrt {x}}\sağ)={\frac {x}{\zeta (2)} }+O({\sqrt {x}}).\end{hizalı}}}$

Arnold Walfisz , Riemann zeta fonksiyonunun bilinen en büyük sıfırdan arındırılmış bölgesinden yararlanarak,

${\displaystyle Q(x)={\frac {6x}{\pi ^{2}}}+O\left(x^{1/2}\exp \left(-c{\frac {(\log x) )^{3/5}}{(\log \log x)^{1/5}}}\sağ)\sağ),}$

bazı pozitif sabitler için c .

Riemann hipotezi altında, hata terimi şuna indirgenebilir:

${\displaystyle Q(x)={\frac {x}{\zeta (2)}}+O\left(x^{17/54+\varepsilon }\sağ)={\frac {6}{\pi ^{2}}}x+O\sol(x^{17/54+\varepsilon }\sağ).}$

Son zamanlarda (2015) hata terimi daha da azaltıldı

${\displaystyle Q(x)={\frac {6}{\pi ^{2}}}x+O\sol(x^{11/35+\varepsilon }\sağ).}$

Karesiz sayıların asimptotik/ doğal yoğunluğu bu nedenle

${\displaystyle \lim _{x\to \infty }{\frac {Q(x)}{x}}={\frac {6}{\pi ^{2}}}\yaklaşık 0.6079}$

Bu nedenle, tam sayıların 3/5'inden fazlası karesizdir.

Benzer şekilde, Q, ( x , n ) sayısını temsil eder , n içermeyen tamsayı 1 arasında (küp içermeyen bir tamsayı olmak örneğin 3-serbest tam sayı) x , tek gösterebilir

${\displaystyle Q(x,n)={\frac {x}{\sum _{k=1}^{\infty }{\frac {1}{k^{n}}}}+O\sol ({\sqrt[{n}]{x}}\sağ)={\frac {x}{\zeta (n)}}+O\sol({\sqrt[{n}]{x}}\sağ) ).}$

4'ün katının kare çarpanı 4=2 ² olması gerektiğinden, ardışık dört tamsayının hepsinin karesiz olması mümkün değildir. Öte yandan, 4 n +1, 4 n +2, 4 n + 3'ün tamamı karesiz olan sonsuz sayıda n tamsayısı vardır. Aksi takdirde, 4 n ve 4 n +1, 4 n +2, 4 n +3'ten en az birinin yeterince büyük n için karesiz olabileceği göz önüne alındığında , tüm pozitif tam sayıların yarısı eksi sonlu çok olmayan olmalıdır. -karesiz ve bu nedenle

${\displaystyle Q(x)\leq {\frac {x}{2}}+C}$bazı sabit C için ,

için yukarıdaki asimptotik tahminin aksine . ${\görüntüleme stili Q(x)}$

Ardışık kare olmayan, rastgele uzunlukta ardışık tamsayı dizileri vardır. Gerçekten de, eğer n eşzamanlı bir kongrüansı sağlıyorsa

${\displaystyle n\equiv -i{\pmod {p_{i}^{2}}}\qquad (i=1,2,\ldots ,l)}$

farklı asal sayılar için , her biri p _i ² ile bölünebilir . Öte yandan, yukarıda bahsedilen tahmin , bir c sabiti için , x ile pozitif x arasında her zaman karesiz bir tamsayı olduğunu ima eder . Dahası, bir ilköğretim argüman yerine bize veriyor tarafından ABC varsayım olanak sağlayacak . ${\displaystyle p_{1},p_{2},\ldots ,p_{l}}$${\görüntüleme stili n+i}$${\displaystyle Q(x)=6x/\pi ^{2}+O\sol({\sqrt {x}}\sağ)}$${\displaystyle x+c{\sqrt {x}}}$${\displaystyle x+c{\sqrt {x}}}$${\displaystyle x+cx^{1/5}\log x.}$${\displaystyle x+x^{o(1)}}$

Q Tablosu ( x ), 6/π ²x ve R ( x )

Tablo, 10'un güçlerinde nasıl ve karşılaştırıldığını gösterir . ${\görüntüleme stili Q(x)}$${\displaystyle {\frac {6}{\pi ^{2}}}x}$

${\displaystyle R(x)=Q(x)-{\frac {6}{\pi ^{2}}}x}$, olarak da ifade edilir . ${\görüntüleme stili\Delta (x)}$

${\görüntüleme stili x}$	${\görüntüleme stili Q(x)}$	${\displaystyle {\frac {6}{\pi ^{2}}}x}$	${\görüntüleme stili R(x)}$
10	7	6.1	0.9
10 2	61	60.8	0,2
10 3	608	607.9	0.1
10 4	6.083	6.079.3	3.7
10 5	60.794	60,792.7	1.3
10 6	607.926	607.927.1	- 1.3
10 7	6.079.291	6.079.271.0	20.0
10 8	60.792.694	60.792.710.2	- 16.2
10 9	607.927.124	607.927.101.9	22.1
10 10	6.079.270.942	6.079.271.018,5	- 76,5
10 11	60.792.710.280	60,792,710,185.4	94.6
10 12	607.927.102.274	607,927,101,854,0	420.0
10 13	6.079.271.018.294	6.079.271.018.540.3	- 246.3
10 14	60.792.710.185.947	60.792.710.185.402.7	544.3
10 15	607.927.101.854.103	607.927.101.854.027.0	76.0

${\görüntüleme stili R(x)}$sonsuzluğa meyilli olduğu için işaretini sonsuz sıklıkta değiştirir. ${\görüntüleme stili x}$

Mutlak değeri ile karşılaştırıldığında şaşırtıcı derecede küçüktür . ${\görüntüleme stili R(x)}$${\görüntüleme stili x}$

İkili sayılar olarak kodlama

Sonsuz ürün olarak kare içermeyen bir sayıyı temsil edersek

${\displaystyle \prod _{n=0}^{\infty }(p_{n+1})^{a_{n}},a_{n}\in \lbrace 0,1\rbrace ,{\text{ ve }}p_{n}{\text{, }}n{\text{inci asal}},}$

sonra bunları alabilir ve kodlama ile ikili bir sayı içinde bit olarak kullanabiliriz. ${\ Displaystyle a_{n}}$

${\displaystyle \sum _{n=0}^{\infty }{a_{n}}\cdot 2^{n}.}$

Karesiz 42 sayısı 2 × 3 × 7 veya sonsuz bir çarpım olarak 2 ¹  · 3 ¹  · 5 ⁰  · 7 ¹  · 11 ⁰  · 13 ⁰  ··· Böylece 42 sayısı ikili dizi olarak kodlanabilir ...001011 veya 11 ondalık. (İkili basamaklar, sonsuz üründeki sıralamanın tersidir.)

Her sayının asal çarpanlara ayrılması benzersiz olduğundan, karesiz tam sayıların her ikili kodlaması da benzersizdir.

Tersi de doğrudur. Her pozitif tamsayı benzersiz bir ikili gösterime sahip olduğundan, bu kodlamayı tersine çevirmek mümkündür, böylece bunlar benzersiz bir kare içermeyen tamsayıya dönüştürülebilir.

Yine, örneğin, 42 sayısı ile başlarsak, bu sefer sadece pozitif bir tam sayı olarak, onun ikili gösterimi 101010 olur . Bu, 2 ⁰  · 3 ¹  · 5 ⁰  · 7 ¹  · 11 ⁰  · 13 ¹ = 3 × 7 × 13 = 273 olarak çözülür.

Böylece squarefree sayıların ikili kodlama bir anlatır bijection negatif olmayan tamsayılar ve pozitif squarefree tamsayılar kümesi arasında.

(Bkz sekansları A019565 , A048672 ve A064273 içinde OEIS .)

Erdős karesiz varsayımı

Merkezi binom katsayısı

${\ Displaystyle {2n \ n'yi seçin}}$

n > 4 için asla karesiz değildir . Bu, 1985'te András Sárközy tarafından yeterince büyük tüm tamsayılar için ve 1996'da Olivier Ramaré ve Andrew Granville tarafından tüm > 4 tamsayılar için kanıtlanmıştır .

kare içermeyen çekirdek

Çarpımsal fonksiyon pozitif tamsayılar eşleştirmek için tanımlanır n için t asal güç gösterimi modülo Çin'li azaltarak -ücretsiz numaralarını t : ${\displaystyle \mathrm {çekirdek} _{t}(n)}$

${\displaystyle \mathrm {çekirdek} _{t}(p^{e})=p^{e{\bmod {t}}}.}$

Değer kümesi , özellikle, kare içermeyen tam sayılardır. Bunların Dirichlet üreten işlevleri vardır ${\displaystyle \mathrm {çekirdek} _{2}}$

${\displaystyle \sum _{n\geq 1}{\frac {\mathrm {çekirdek} _{t}(n)}{n^{s}}}={\frac {\zeta (ts)\zeta ( s-1)}{\zeta (ts-t)}}}$.

OEIS temsilcileridir OEIS :  A007913 ( t = 2), OEIS :  A050985 ( t = 3) ve OEIS :  A053165 ( t = 4).

Notlar

Referanslar

• Shapiro, Harold N. (1983). Sayılar teorisine giriş . Oxford University Press Dover Yayınları. ISBN'si 978-0-486-46669-9.
• Granville, Andrew; Ramare, Olivier (1996). "Üssel toplamlar ve kare içermeyen binom katsayılarının kıtlığı üzerindeki açık sınırlar". Matematik . 43 : 73-107. CiteSeerX  10.1.1.55.8 . doi : 10.1112/S0025579300011608 . MR  1401709 . Zbl  0868.11009 .
• Adam, Richard K. (2004). Sayı teorisinde çözülmemiş problemler (3. baskı). Springer-Verlag . ISBN'si 978-0-387-20860-2. Zbl  1058.11001 .
• "OEIS Wiki" . Erişim tarihi: 24 Eylül 2021 .