Вільне від квадратів число

Додатне число n вільне від квадратів тоді і тільки тоді, коли в розкладі цього числа на прості множники жодне просте число не зустрічається більше, ніж один раз. По-іншому це можна висловити так: для будь-якого простого дільника p числа n, число p не є дільником n/p. Або, число n вільне від квадратів тоді і тільки тоді, коли для будь-якого його розкладу на множники n = ab, множники a і b взаємно прості.

Додатне число n вільне від квадратів тоді і тільки тоді, коли ${\displaystyle \mu (n)\neq 0}$, де ${\displaystyle \mu (n)}$ позначає функцію Мебіуса.

Ряд Діріхле, який породжує вільні від квадратів числа:

${\displaystyle {\frac {\zeta (s)}{\zeta (2s)}}=\sum _{n=1}^{\infty }{\frac {|\mu (n)|}{n^{s}}}}$ де ${\displaystyle \zeta (s)}$ — дзета-функція Рімана.

Це зразу видно з добутку Ейлера :

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

Додатне число n вільне від квадратів тоді і тільки тоді, коли всі абелеві групи порядку n ізоморфні одна одній, що виконується в тому і тільки в тому випадку, коли вони всі — циклічні. Це випливає з класифікації скінченнопороджених абелевих груп.

Додатне число n вільне від квадратів тоді і тільки тоді, коли фактор-кільце ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ (див. порівняння за модулем) є добутком полів. Це випливає з китайської теореми про остачі і того факту, що кільце ${\displaystyle \mathbb {Z} /k\mathbb {Z} }$ — поле тоді і тільки тоді, коли k — просте число.

Для будь-якого додатного числа n множина всіх додатних його дільників є частково впорядкованою, якщо ми порядком вважатимемо відношення «подільності». Ця частково впорядкована множина — завжди дистрибутивна ґратка. Вона — булева алгебра в тому і тільки в тому випадку, коли n вільне від квадратів.

Радикал цілого числа завжди вільний від квадратів.

Нехай ${\displaystyle Q(x)}$ задає число вільних від квадратів чисел на проміжку від 1 до x. Для великого n, 3/4 додатних чисел, менших від n, не діляться на 4, 8/9 цих чисел не діляться на 9 і т. д. Оскільки ці події незалежні, отримуємо формулу:

${\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}}}+\cdots }}={\frac {x}{\sum _{k=1}^{\infty }{\frac {1}{k^{2}}}}}={\frac {x}{\zeta (2)}}}$

Можна отримати формулу без дзета-функції:

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

(див. pi і «O» велике і «o» мале). Згідно з гіпотезою Рімана, оцінку можна поліпшити:

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

Ось як поводиться різниця числа вільних від квадратів чисел до n і ${\displaystyle \left[{\frac {n}{\zeta (2)}}\right]}$ на сайті OEIS: A158819 — (Number of square-free numbers ≤ n) minus round (n / ζ (2)).

Таким чином асимптотична щільність вільних від квадратів чисел виглядає так:

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

де ${\displaystyle \zeta }$ — дзета-функція Рімана а ${\displaystyle 1/\zeta (2)\approx 0.6079}$ (тобто, приблизно 3/5 всіх чисел вільні від квадратів).

Аналогічно, якщо ${\displaystyle Q(x,n)}$ означає число n-вільних чисел (тобто 3-вільні числа не містять кубів) між 1 і x, то:

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

Якщо подати вільне від квадратів число як нескінченний добуток виду

${\displaystyle \prod _{n=0}^{\infty }{p_{n+1}}^{a_{n}},}$

де ${\displaystyle a_{n}\in \{0,1\},}$, а ${\displaystyle p_{n}}$ — n-е просте число, то ми можемо вибирати ці коефіцієнти ${\displaystyle a_{n}}$ і використовувати їх як біти в бінарному кодуванні:

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

Наприклад, вільне від квадратів число 42 розкладається як 2 · 3 · 7, або як нескінченний добуток:

2¹ · 3¹ · 5⁰ · 7¹ · 11⁰ · 13⁰ · …;

Таким чином, число 42 кодується послідовністю ... 001011 або 11 в десятковій системі (в бінарному кодуванні біти пишуться навпаки). А оскільки розклад на прості множники кожного числа — унікальний, то унікальним є й бінарний код кожного вільного від квадратів числа.

Зворотне також істинне: оскільки у кожного додатного числа є унікальний бінарний код, його можна декодувати, отримуючи унікальні числа, вільні від квадратів.

Візьмемо знову для прикладу число 42 — на цей раз просто як додатне число. Тоді ми отримуємо бінарний код 101010 — це означає: 2⁰ · 3¹ · 5⁰ · 7¹ · 11⁰ · 13¹ = 3 · 7 · 13 = 273.

З точки зору потужностей, це означає, що потужність множини чисел, вільних від квадратів, збігається з потужністю множини всіх натуральних чисел. Що в свою чергу означає, що кодування вільних від квадратів чисел по порядку — точно є перестановкою множини натуральних чисел.

Див. послідовності A048672 і A064273 на сайті OEIS .

Центральний біноміальний коефіцієнт ${\displaystyle {2n \choose n}}$ не може бути вільним від квадратів для n>4.

Це припущення Ердеша про безквадратність довели в 1996 році математики Олів'єр Рамаре і Ендрю Гревілл.

• Функція Мебіуса

• Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. — 385 с.