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

У математиці вільним від квадратів, або безквадратним, називається число, яке не ділиться на жоден квадрат, крім 1. Наприклад, 10 — вільне від квадратів, а 18 — ні, оскільки 18 ділиться на 9 = 3^2. Початок послідовності вільних від квадратів чисел такий:

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, … послідовність A005117 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

Теорія кілець узагальнює поняття безквадратності таким чином:

Елемент r факторіального кільця R називається вільним від квадратів, якщо він не ділиться на нетривіальний квадрат.

Вільні від квадратів елементи також можуть бути схарактеризовані виходячи з їх розкладання на прості множники: будь-який ненульовий елемент r може бути поданий у вигляді добутку простих елементів

${\displaystyle r=\varepsilon p_{1}p_{2}\cdots p_{n}}$ ,

причому всі прості множники p _i різні, а ${\displaystyle \varepsilon }$ — деяка одиниця (оборотний елемент) кільця.

Еквівалентна характеристика чисел, вільних від квадратів

Додатне число 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)). [Архівовано 22 грудня 2019 у Wayback Machine.]

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

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

Примітки