Вільне від квадратів число
У математиці вільним від квадратів, або безквадратним, називається число, яке не ділиться на жоден квадрат, крім 1. Наприклад, 10 — вільне від квадратів, а 18 — ні, оскільки 18 ділиться на 9 = 32. Початок послідовності вільних від квадратів чисел такий:
- 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 може бути поданий у вигляді добутку простих елементів
- ,
причому всі прості множники p i різні, а — деяка одиниця (оборотний елемент) кільця.
Еквівалентна характеристика чисел, вільних від квадратів
Додатне число n вільне від квадратів тоді і тільки тоді, коли в розкладі цього числа на прості множники жодне просте число не зустрічається більше, ніж один раз. По-іншому це можна висловити так: для будь-якого простого дільника p числа n, число p не є дільником n/p. Або, число n вільне від квадратів тоді і тільки тоді, коли для будь-якого його розкладу на множники n = ab, множники a і b взаємно прості.
Додатне число n вільне від квадратів тоді і тільки тоді, коли , де позначає функцію Мебіуса.
Ряд Діріхле, який породжує вільні від квадратів числа:
- де — дзета-функція Рімана.
Це зразу видно з добутку Ейлера :
Додатне число n вільне від квадратів тоді і тільки тоді, коли всі абелеві групи порядку n ізоморфні одна одній, що виконується в тому і тільки в тому випадку, коли вони всі — циклічні. Це випливає з класифікації скінченнопороджених абелевих груп.
Додатне число n вільне від квадратів тоді і тільки тоді, коли фактор-кільце (див. порівняння за модулем) є добутком полів. Це випливає з китайської теореми про остачі і того факту, що кільце — поле тоді і тільки тоді, коли k — просте число.
Для будь-якого додатного числа n множина всіх додатних його дільників є частково впорядкованою, якщо ми порядком вважатимемо відношення «подільності». Ця частково впорядкована множина — завжди дистрибутивна ґратка. Вона — булева алгебра в тому і тільки в тому випадку, коли n вільне від квадратів.
Радикал цілого числа завжди вільний від квадратів.
Щільність вільних від квадратів чисел
Нехай задає число вільних від квадратів чисел на проміжку від 1 до x. Для великого n, 3/4 додатних чисел, менших від n, не діляться на 4, 8/9 цих чисел не діляться на 9 і т. д. Оскільки ці події незалежні, отримуємо формулу:
Можна отримати формулу без дзета-функції:
(див. pi і «O» велике і «o» мале). Згідно з гіпотезою Рімана, оцінку можна поліпшити:
Ось як поводиться різниця числа вільних від квадратів чисел до n і на сайті OEIS: A158819 — (Number of square-free numbers ≤ n) minus round (n / ζ (2)).
Таким чином асимптотична щільність вільних від квадратів чисел виглядає так:
де — дзета-функція Рімана а (тобто, приблизно 3/5 всіх чисел вільні від квадратів).
Аналогічно, якщо означає число n-вільних чисел (тобто 3-вільні числа не містять кубів) між 1 і x, то:
Кодування двійковими числами
Якщо подати вільне від квадратів число як нескінченний добуток виду
де , а — n-е просте число, то ми можемо вибирати ці коефіцієнти і використовувати їх як біти в бінарному кодуванні:
Наприклад, вільне від квадратів число 42 розкладається як 2 · 3 · 7, або як нескінченний добуток:
21 · 31 · 50 · 71 · 110 · 130 · …;
Таким чином, число 42 кодується послідовністю ... 001011 або 11 в десятковій системі (в бінарному кодуванні біти пишуться навпаки). А оскільки розклад на прості множники кожного числа — унікальний, то унікальним є й бінарний код кожного вільного від квадратів числа.
Зворотне також істинне: оскільки у кожного додатного числа є унікальний бінарний код, його можна декодувати, отримуючи унікальні числа, вільні від квадратів.
Візьмемо знову для прикладу число 42 — на цей раз просто як додатне число. Тоді ми отримуємо бінарний код 101010 — це означає: 20 · 31 · 50 · 71 · 110 · 131 = 3 · 7 · 13 = 273.
З точки зору потужностей, це означає, що потужність множини чисел, вільних від квадратів, збігається з потужністю множини всіх натуральних чисел. Що в свою чергу означає, що кодування вільних від квадратів чисел по порядку — точно є перестановкою множини натуральних чисел.
Див. послідовності A048672 і A064273 на сайті OEIS .
Гіпотеза Ердеша
Центральний біноміальний коефіцієнт не може бути вільним від квадратів для n>4.
Це припущення Ердеша про безквадратність довели в 1996 році математики Олів'єр Рамаре і Ендрю Гревілл.
Див. також
Література
- Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. — 385 с.
Примітки
|