Liczby bezkwadratowe

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 to^[1]:

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, ... (OEIS: A005117.).

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 ${\displaystyle 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 ${\displaystyle k}$ liczby ${\displaystyle n,}$ który jest względnie pierwszy z ${\displaystyle n/k.}$

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

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

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

Równoważne charakterystyki

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

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

Dodatnia liczba całkowita ${\displaystyle n}$ jest bezkwadratowa wtedy i tylko wtedy, gdy wszystkie grupy abelowe rzędu ${\displaystyle 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 ${\displaystyle n}$ jest bezkwadratowa wtedy i tylko wtedy, gdy pierścień ilorazowy ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ jest produktem ciał. Wynika to z chińskiego twierdzenia o resztach oraz faktu, że pierścień postaci ${\displaystyle \mathbb {Z} /k\mathbb {Z} }$ jest ciałem wtedy i tylko wtedy, gdy ${\displaystyle k}$ jest liczbą pierwszą.

Dla każdej dodatniej liczby całkowitej ${\displaystyle n}$ zbiór wszystkich dodatnich dzielników ${\displaystyle 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 ${\displaystyle n}$ jest bezkwadratowe.

Funkcja tworząca Dirichleta

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

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

Można to łatwo zobaczyć w produkcie Eulera

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

Dystrybucja

Niech ${\displaystyle Q(x)}$ oznacza liczbę liczb bezkwadratowych między 1 i ${\displaystyle x.}$ Wtedy ${\displaystyle Q(10)=6,}$ ${\displaystyle Q(100)=61,}$ ${\displaystyle Q(1000)=608,}$ ${\displaystyle Q(10\ 000)=6083,}$ ${\displaystyle Q(100\ 000)=60\ 794,}$ ${\displaystyle Q(1\ 000\ 000)=607\ 926}$^[1]. Dla dużych ${\displaystyle n,}$ 3/4 dodatnich liczb mniejszych niż ${\displaystyle 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

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

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

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

${\displaystyle 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 ${\displaystyle \mathrm {O} }$), ponieważ używamy powyższej charakterystyki do uzyskania

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

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

${\displaystyle Q(x)=\sum _{d\leqslant {\sqrt {x}}}\mu (d)\left\lfloor {\frac {x}{d^{2}}}\right\rfloor =\sum _{d\leqslant {\sqrt {x}}}{\frac {x\mu (d)}{d^{2}}}+O(\sum _{d\leqslant {\sqrt {x}}}1)=x\sum _{d\leqslant {\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}}\right)={\frac {x}{\zeta (2)}}+O({\sqrt {x}}).}$

Wykorzystanie przez Arnolda Walfisza^[2]  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

${\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}}}\right)\right)}$

dla pewnej dodatniej stałej ${\displaystyle c.}$ Na podstawie hipotezy Riemanna błąd można dalej redukować^[3][4] [5], by otrzymać

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

Dlatego asymptotyczna gęstość liczb bezkwadratowych jest

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

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

Podobnie, jeśli ${\displaystyle Q(x,n)}$ oznacza liczbę ${\displaystyle 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 ${\displaystyle x,}$ można pokazać, że

${\displaystyle Q(x,n)={\frac {x}{\sum _{k=1}^{\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

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

wtedy możemy wziąć te ${\displaystyle a_{n}}$ i użyć ich jako bitów w liczbie binarnej z kodowaniem

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

Liczba bezkwadratowa 42 ma rozkład ${\displaystyle 2\times 3\times 7}$ lub jest nieskończonym produktem ${\displaystyle 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 ${\displaystyle 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: A019565., A048672. i A064273.

Twierdzenie bezkwadratowe Erdősa

Środkowy współczynnik dwumianowy ${\displaystyle 2n \choose n}$ nigdy nie jest bezkwadratowy dla ${\displaystyle n>4.}$ Zostało to udowodnione w 1985 przez Andrása Sárközy’ego dla wszystkich wystarczająco dużych liczb całkowitych^[6], a dla wszystkich liczb całkowitych ${\displaystyle >4}$ w 1996 przez Oliviera Ramaré’a i Andrew Granville’a^[7].

Rdzeń bezkwadratowy

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

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

Zbiorem wartości ${\displaystyle \mathrm {core} _{2}}$ są w szczególności liczby bezkwadratowe. Ich funkcje tworzące Dirichleta są następujące

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

Odpowiedniki OEIS to: A007913. ${\displaystyle (t=2),}$ A050985. ${\displaystyle (t=3)}$ i A053165. ${\displaystyle (t=4).}$

Zobacz też

• liczby kwadratowe

Przypisy

Bibliografia

• Richard K. Guy: Unsolved problems in number theory. Nowy Jork: Springer-Verlag, 2004. ISBN 0-387-20860-7. (ang.).brak strony w książce
• Chao-Hua Jia. The distribution of square-free numbers. „Science in China Series A: Mathematics”. 36 (2), 1993. DOI: 10.1360/ya1993-36-2-154. ISSN 1862-2763. (ang.). 
• Andrzej Nowicki: Podróże po Imperium Liczb. Wyd. 2. Cz. 3: Liczby Kwadratowe. Olsztyn, Toruń: Olsztyńska Wyższa Szkoła Informatyki i Zarządzania im. prof. T. Kotarbińskiego, 2012, s. 41–43. ISBN 978-83-88629-69-3.
• Francesco Pappalardi: A Survey on k-freeness. 2003. [dostęp 2016-06-27]. (ang.).
• Olivier Ramaré, Andrew Granville. Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients. „Mathematika”. 43 (1), 1996. Londyn: University College London. DOI: 10.1112/S0025579300011608. ISSN 0025-5793. (ang.). 
• András Sárközy. On divisors of binomial coefficients. „Journal of Number Theory”. 20 (1), 1985. Elsevier. DOI: 10.1016/0022-314X(85)90017-4. ISSN 0022-314X. (ang.). 
• Kaneenika Sinha. Average orders of certain arithmetical functions. „Journal of the Ramanujan Mathematical Society”. 21 (3), 2006. ISSN 0970-1249. (ang.). 
• Arnold Walfisz. Weylsche Exponentialsummen in der neueren Zahlentheorie. „Zeitschrift für Angewandte Mathematik und Mechanik”, 1963. Berlin: VEB Deutscher Verlag der Wissenschaften. DOI: 10.1002/zamm.19640441217. ISSN 0044-2267. (niem.).