В математике свободным от квадратов, или бесквадратным, называется число, которое не делится ни на один квадрат, кроме 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 может быть представлен в виде произведения простых элементов
,
причем все простые сомножители pi различны, а
— некоторая единица (обратимый элемент) кольца.
Эквивалентная характеристика чисел, свободных от квадратов
Положительное число n свободно от квадратов тогда и только тогда, когда в разложении этого числа на простые множители ни одно простое число не встречается больше одного раза. По-другому это можно выразить так: для любого простого делителя p числа n, число p не делит n / p. Или, число n свободно от квадратов тогда и только тогда, когда для любого его разложения на множители n = ab, множители a и b взаимно просты.
Положительное число n свободно от квадратов тогда и только тогда, когда
, где
обозначает функцию Мёбиуса.
Ряд Дирихле, порождающий свободные от квадратов числа:
где
— дзета-функция Римана.
Это сразу видно из произведения Эйлера:
![{\displaystyle {\frac {\zeta (s)}{\zeta (2s)}}=\prod _{p}{\frac {(1-p^{-2s})}{(1-p^{-s})}}=\prod _{p}(1+p^{-s}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dbf3a8070440d94ba04bb8e9f874841aa10e297)
Положительное число n свободно от квадратов тогда и только тогда, когда все абелевы группы порядка n изоморфны друг другу, что верно в том и только в том случае, когда они все — циклические. Это следует из классификации конечнопорождённых абелевых групп.
Положительное число n свободно от квадратов тогда и только тогда, когда факторкольцо
(см. сравнение по модулю) есть произведение полей. Это следует из китайской теоремы об остатках и того факта, что кольцо
— поле тогда и только тогда, когда k — простое число.
Для любого положительного числа n множество всех положительных его делителей представляет собой частично упорядоченное множество, если мы положим в качестве порядка отношение «делимости». Это частично упорядоченное множество — всегда дистрибутивная решётка. Оно — Булева алгебра в том и только в том случае, когда n свободно от квадратов.
Радикал целого числа всегда свободен от квадратов.
Плотность свободных от квадратов чисел
Пусть
задаёт число свободных от квадратов чисел в промежутке от 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}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac40b99420b8a5320c65282f338edf2c0f7eb7b2)
![{\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)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5db8cbe23c97ad2089af5b8f182771db01e06caa)
Можно получить формулу без дзета-функции:
![{\displaystyle Q(x)={\frac {x}{\zeta (2)}}+O\left({\sqrt {x}}\right)={\frac {6x}{\pi ^{2}}}+O\left({\sqrt {x}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3006be52a89cabb50fce07861399f902248e365c)
(см. pi и «O» большое и «o» малое). Согласно гипотезе Римана, оценка может быть улучшена:[1]
![{\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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84b624e3f8dfc1baf287248f119d927c3b6ef2c5)
Вот как ведёт себя разность числа свободных от квадратов чисел до n и
на сайте 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)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9faa8937914b7f67359a992960b87d7bed62ec2b)
Где
— дзета-функция Римана а
(то есть, примерно 3/5 всех чисел свободны от квадратов).
Аналогично, если
означает число 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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ee1f41bd7855734c706b7b8b71544e094e7a5da)
Кодирование двоичными числами
Если представить свободное от квадратов число в качестве бесконечного произведения вида
![{\displaystyle \prod _{n=0}^{\infty }{p_{n+1}}^{a_{n}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e169c4f83c9165b0ef57f60e58191a50b86e04a)
где
, а
— n-е простое число, то мы можем выбирать эти коэффициенты
и использовать их в качестве битов в бинарной кодировке:
![{\displaystyle \sum _{n=0}^{\infty }{a_{n}}\cdot 2^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93fe2d1885e71070cf499a943afb4aa0aa9846b4)
К примеру, свободное от квадратов число 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 с.
Примечания