Liczby bezkwadratowe

10 jest podzielne przez 2, 5 i 10, żadna z nich nie jest kwadratem liczby całkowitej (pierwszych kilka kwadratów liczby całkowitej to 1, 4, 9 i 16)

Liczba bezkwadratowa – taka liczba całkowita, która nie jest podzielna przez żaden kwadrat liczby całkowitej z wyjątkiem 1. Na przykład 10 jest liczbą bezkwadratową, ale 18 nie jest, bo 18 jest podzielne przez 9 = 3². Najmniejsze dodatnie liczby bezkwadratowe toSzablon:Odn:

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, ... (Szablon:Cytuj stronę).

Bezkwadratowe czynniki liczb całkowitych

Radykał dodatniej liczby całkowitej to iloczyn różnych liczb pierwszych ją dzielących. Wprost z definicji wynika, że jest bezkwadratowy, a ponadto jest największym czynnikiem bezkwadratowym danej liczby. Liczba całkowita jest bezkwadratowa wtedy i tylko wtedy, gdy jest równa swemu radykałowi.

Dodatnia liczba całkowita $n$ może zostać przedstawiona w jednoznaczny sposób jako iloczyn potęgi liczby całkowitej i liczby bezkwadratowej, które są względnie pierwsze. Czynnik bezkwadratowy jest największym bezkwadratowym dzielnikiem $k$ liczby $n,$ który jest względnie pierwszy z $n/k.$

Dowolna dodatnia liczba całkowita $n$ może zostać przedstawiona w jednoznaczny sposób jako iloczyn drugiej potęgi liczby całkowitej i liczby bezkwadratowej:

$n=m^{2}k.$

W tym rozkładzie $m$ jest największym dzielnikiem liczby $n$ takim, że $m^2$ jest dzielnikiem $n.$

Równoważne charakterystyki

Dodatnia liczba całkowita $n$ jest bezkwadratowa wtedy i tylko wtedy, gdy w rozkładzie na czynniki pierwsze liczby $n$ żadna liczba pierwsza nie występuje więcej niż razSzablon:Odn. Można to samo wyrazić w inny sposób: dla każdego dzielnika $p$ liczby $n,$ będącego liczbą pierwszą, $p$ nie dzieli jeszcze $n/p.$ Inne sformułowanie jest następujące: $n$ jest bezkwadratowe wtedy i tylko wtedy, gdy w każdym rozkładzie $n=ab$ czynniki $a$ i $b$ są względnie pierwsze. Bezpośrednim wnioskiem z tej definicji jest to, że wszystkie liczby pierwsze są bezkwadratowe.

Dodatnia liczba całkowita $n$ jest bezkwadratowa wtedy i tylko wtedy, gdy $\mu (n)\ne 0,$ gdzie $\mu$ oznacza funkcję Möbiusa.

Dodatnia liczba całkowita $n$ jest bezkwadratowa wtedy i tylko wtedy, gdy wszystkie grupy abelowe rzędu $n$ są izomorficzne, co ma miejsce wtedy i tylko wtedy, gdy dowolna z nich jest cykliczna. Wynika to z klasyfikacji skończenie generowanych grup abelowych.

Liczba całkowita $n$ jest bezkwadratowa wtedy i tylko wtedy, gdy pierścień ilorazowy $\mathbb{Z}/n\mathbb{Z}$ jest produktem ciał. Wynika to z chińskiego twierdzenia o resztach oraz faktu, że pierścień postaci $\mathbb{Z}/k\mathbb{Z}$ jest ciałem wtedy i tylko wtedy, gdy $k$ jest liczbą pierwszą.

Dla każdej dodatniej liczby całkowitej $n$ zbiór wszystkich dodatnich dzielników $n$ staje się zbiorem częściowo uporządkowanym, jeśli użyjemy podzielności jako relacji porządku. Taki częściowo uporządkowany zbiór jest zawsze kratą rozdzielną. Jest algebrą Boole’a wtedy i tylko wtedy, gdy $n$ jest bezkwadratowe.

Funkcja tworząca Dirichleta

Funkcja tworząca Dirichleta dla liczb bezkwadratowych jest następująca

$\frac{\zeta (s)}{\zeta (2s)}=\sum _{n=1}^{\mathrm{\infty }}\frac{|\mu (n)|}{n^s},$ gdzie $\zeta (s)$ jest funkcją dzeta Riemanna.

Można to łatwo zobaczyć w produkcie Eulera

$\frac{\zeta (s)}{\zeta (2s)}=\prod _p\frac{(1-p^{-2s})}{(1-p^{-s})}=\prod _p(1+p^{-s}).$

Dystrybucja

Niech $Q(x)$ oznacza liczbę liczb bezkwadratowych między 1 i $x.$ Wtedy $Q(10)=6,$ $Q(100)=61,$ $Q(1000)=608,$ $Q(10000)=6083,$ $Q(100000)=60794,$ $Q(1000000)=607926$Szablon:Odn. Dla dużych $n,$ 3/4 dodatnich liczb mniejszych niż $n$ nie dzieli się przez 4, 8/9 z tych liczb nie dzieli się przez 9 i tak dalej. Ponieważ te zdarzenia są niezależne otrzymujemy przybliżenie

$Q(x)\approx x\prod _{p\text{prime}}(1-\frac{1}{p^2})=x\prod _{p\text{prime}}\frac{1}{(1-\frac{1}{p^2}{)}^{-1}},$

$Q(x)\approx x\prod _{p\text{prime}}\frac{1}{1+\frac{1}{p^2}+\frac{1}{p^4}+\dots }=\frac{x}{\sum _{k=1}^{\mathrm{\infty }}\frac{1}{k^2}}=\frac{x}{\zeta (2)}.$

Powyższą tezę można uściślić, a całkowicie elementarne oszacowanie daje

$Q(x)=\frac{x}{\zeta (2)}+O\left(\sqrt{x}\right)=\frac{6x}{{\pi }^2}+O\left(\sqrt{x}\right)$

(zobacz pi i notacja dużego $O$), ponieważ używamy powyższej charakterystyki do uzyskania

$Q(x)=\sum _{n⩽x}\sum _{d^2\mid n}\mu (d)=\sum _{d⩽x}\mu (d)\sum _{n⩽x,d^2\mid n}1=\sum _{d⩽x}\mu (d)\lfloor \frac{x}{d^2}\rfloor ,$

a zauważywszy, że ostatni składnik sumy jest równy zero dla $d>\sqrt{x},$ mamy

$Q(x)=\sum _{d⩽\sqrt{x}}\mu (d)\lfloor \frac{x}{d^2}\rfloor =\sum _{d⩽\sqrt{x}}\frac{x\mu (d)}{d^2}+O(\sum _{d⩽\sqrt{x}}1)=x\sum _{d⩽\sqrt{x}}\frac{\mu (d)}{d^2}+O(\sqrt{x})=x\sum _d\frac{\mu (d)}{d^2}+O(x\sum _{d>\sqrt{x}}\frac{1}{d^2}+\sqrt{x})=\frac{x}{\zeta (2)}+O(\sqrt{x}).$

Wykorzystanie przez Arnolda WalfiszaSzablon:Odn największego znanego obszaru bez zer funkcji dzeta Riemanna, który odkryli Winogradow, Korobow i Richert, umożliwiło zredukowanie maksymalnego rozmiaru błędu i mamy

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

dla pewnej dodatniej stałej $c.$ Na podstawie hipotezy Riemanna błąd można dalej redukowaćSzablon:OdnSzablon:OdnSzablon:Odn, by otrzymać

$Q(x)=\frac{x}{\zeta (2)}+O\left(x^{17/54+\epsilon }\right)=\frac{6x}{{\pi }^2}+O\left(x^{17/54+\epsilon }\right).$

Dlatego asymptotyczna gęstość liczb bezkwadratowych jest

$\underset{x\to \mathrm{\infty }}{\lim }\frac{Q(x)}{x}=\frac{6}{{\pi }^2}=\frac{1}{\zeta (2)},$

gdzie $\zeta$ jest funkcją dzeta Riemanna, a $\frac{1}{\zeta (2)}$ jest w przybliżeniu 0,6079. Dlatego ponad 3/5 liczb całkowitych jest bezkwadratowa.

Podobnie, jeśli $Q(x,n)$ oznacza liczbę $n$-wolnych liczb całkowitych (wtedy na przykład 2-wolne liczby całkowite oznaczają liczby bezkwadratowe, 3-wolne liczby całkowite są bezsześcienne) między 1 i $x,$ można pokazać, że

$Q(x,n)=\frac{x}{\sum _{k=1}^{\mathrm{\infty }}\frac{1}{k^n}}+O\left(\sqrt[n]{x}\right)=\frac{x}{\zeta (n)}+O\left(\sqrt[n]{x}\right).$

Kodowanie jako liczby binarne

Jeśli przedstawimy liczby bezkwadratowe jako nieskończony produkt

$\prod _{n=0}^{\mathrm{\infty }}(p_{n+1}{)}^{a_n},a_n\in \{0,1\},$ i $p_n$ jest $n$-tą liczbą pierwszą,

wtedy możemy wziąć te $a_n$ i użyć ich jako bitów w liczbie binarnej z kodowaniem

$\sum _{n=0}^{\mathrm{\infty }}{a}_n\cdot 2^n.$

Liczba bezkwadratowa 42 ma rozkład $2\times 3\times 7$ lub jest nieskończonym produktem $2^1\cdot 3^1\cdot 5^0\cdot 7^1\cdot 11^0\cdot 13^0\dots$ Dlatego 42 można zakodować jako sekwencję binarną ...001011 lub dziesiętne 11.

Skoro rozkład na liczby pierwsze jest jednoznaczny, to również jednoznaczne jest binarne zakodowanie liczb bezkwadratowych.

Stwierdzenie odwrotne jest również prawdziwe. Ponieważ każda dodatnia liczba całkowita ma jednoznaczną reprezentację binarną, możliwe jest odwrócenie kodowania, więc mogą zostać odkodowane jednoznacznie do liczby bezkwadratowej.

Na przykład jeśli znowu zaczniemy od liczby 42, jako od zwykłej dodatniej liczby całkowitej, to jej binarna reprezentacja 101010 dekoduje się do $2^0\cdot 3^1\cdot 5^0\cdot 7^1\cdot 11^0\cdot 13^1=3\times 7\times 13=273.$

Dlatego kodowania liczb całkowitych bezkwadratowych w prawidłowej kolejności są permutacjami zbioru wszystkich liczb całkowitych.

Zobacz sekwencje OEIS: Szablon:Cytuj stronę, Szablon:Cytuj stronę i Szablon:Cytuj stronę

Twierdzenie bezkwadratowe Erdősa

Środkowy współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{2n}{n})$ nigdy nie jest bezkwadratowy dla $n>4.$ Zostało to udowodnione w 1985 przez Andrása Sárközy’ego dla wszystkich wystarczająco dużych liczb całkowitychSzablon:Odn, a dla wszystkich liczb całkowitych $>4$ w 1996 przez Oliviera Ramaré’a i Andrew Granville’aSzablon:Odn.

Rdzeń bezkwadratowy

Funkcja multiplikatywna ${\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}_t(n)$ jest definiowana do mapowania dodatnich liczb całkowitych $n$ na $t$-wolne liczby przez redukcję wykładników w potęgach liczb pierwszych reprezentacji modulo $t:$

${\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}_t(p^e)=p^{emodt}.$

Zbiorem wartości ${\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}_2$ są w szczególności liczby bezkwadratowe. Ich funkcje tworzące Dirichleta są następujące

$\sum _{n⩾1}\frac{{\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}_t(n)}{n^s}=\frac{\zeta (ts)\zeta (s-1)}{\zeta (ts-t)}.$

Odpowiedniki OEIS to: Szablon:Cytuj stronę $(t=2),$Szablon:Cytuj stronę $(t=3)$ i Szablon:Cytuj stronę $(t=4).$

Zobacz też

• liczby kwadratowe

Bibliografia

• Szablon:Cytuj książkę
• Szablon:Cytuj pismo
• Szablon:Cytuj książkę
• Szablon:Cytuj stronę
• Szablon:Cytuj pismo
• Szablon:Cytuj pismo
• Szablon:Cytuj pismo
• Szablon:Cytuj pismo