Свободное от квадратов число

 В математике свободным от квадратов, илибесквадратным, называется число, которое не делится ни на одинквадрат, кроме 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, \ldots
 Теория колец обобщает понятие бесквадратности следующим образом:

 Элемент r факториального кольца R называетсясвободным от квадратов, если он не делится на нетривиальныйквадрат.
 Свободные от квадратов элементы также могут быть охарактеризованы исходяиз их разложения на простые сомножители: любой ненулевой элементr может быть представлен в виде произведения простых элементов

r=εp1p2pn,
 причем все простые сомножители pi различны, аε — некоторая единица (обратимый элемент) кольца.

Эквивалентная характеристика чисел, свободных отквадратов


 Положительное число n свободно от квадратов тогда и только тогда,когда в разложении этого числа на простые множители ни одно простоечисло не встречается больше одного раза. По-другому это можно выразитьтак: для любого простого делителя p числа n, числоp не делит n / p. Или, число n свободно отквадратов тогда и только тогда, когда для любого его разложения намножители n = ab, множители a и b взаимнопросты.
 Положительное число n свободно от квадратов тогда и только тогда,когда μ(n)0, где μ(n) обозначает функцию Мёбиуса.
 Ряд Дирихле, порождающий свободные от квадратов числа:

ζ(s)ζ(2s)=n=1|μ(n)|nsгде ζ(s) — дзета-функция Римана.
 Это сразу видно из произведения Эйлера:

ζ(s)ζ(2s)=p(1p2s)(1ps)=p(1+ps).
 Положительное число n свободно от квадратов тогда и только тогда,когда все абелевы группы порядка n изоморфны друг другу, чтоверно в том и только в том случае, когда они все — циклические. Этоследует из классификации конечнопорождённых абелевых групп.
 Положительное число n свободно от квадратов тогда и только тогда,когда факторкольцо Z/nZ (см. сравнение по модулю)есть произведение полей. Это следует из китайской теоремы об остатках итого факта, что кольцо Z/kZ — поле тогда и толькотогда, когда k — простое число.
 Для любого положительного числа n множество всех положительныхего делителей представляет собой частично упорядоченное множество, еслимы положим в качестве порядка отношение «делимости». Это частичноупорядоченное множество — всегда дистрибутивная решётка. Оно —Булева алгебра в том и только в том случае, когда n свободно отквадратов.
 Радикал целого числа всегда свободен от квадратов.

Плотность свободных от квадратовчисел


 Пусть Q(x) задаёт число свободных от квадратов чисел в промежутке от 1до x. Для большого n, 3/4 положительных чисел, меньшихn не делятся на 4, 8/9 этих чисел не делятся на 9 и т. д.. Таккак эти события независимы, получаем формулу:

Q(x)xp prime(11p2)=xp prime1(11p2)1


Q(x)xp prime11+1p2+1p4+=xk=11k2=xζ(2)
 Можно получить формулу без дзета-функции:

Q(x)=xζ(2)+O(x)=6xπ2+O(x)
 (см. pi и «O» большое и «o» малое). Согласно гипотезе Римана, оценкаможет быть улучшена:

Q(x)=xζ(2)+O(x17/54+ε)=6xπ2+O(x17/54+ε).
 Вот как ведёт себя разность числа свободных от квадратов чисел доn и [nζ(2)] на сайте OEIS:A158819 —(Number of square-free numbers ≤ n) minus round(\emphn/ζ(2)).
 Таким образом асимптотическая плотность свободных от квадратов чиселвыглядит так:

limxQ(x)x=6π2=1ζ(2)
 Где ζ — дзета-функция Римана а 1/ζ(2)0.6079 (тоесть, примерно 3/5 всех чисел свободны от квадратов).
 Аналогично, если Q(x,n) означает число n-свободных чисел (тоесть 3-свободные числа не содержат кубов) между 1 и x, то:

Q(x,n)=xk=11kn+O(xn)=xζ(n)+O(xn).

Кодирование двоичнымичислами


 Если представить свободное от квадратов число в качестве бесконечногопроизведения вида

n=0pn+1an,
 где an{0,1},, а pn — n-е простое число, то мы можемвыбирать эти коэффициенты an и использовать их в качестве битов вбинарной кодировке:

n=0an2n
 К примеру, свободное от квадратов число 42 раскладывается как 2 × 3 × 7,или как бесконечное произведение: 21 ·31 · 50 · 71 ·110 · 130 · \ldots; Таким образом,число 42 кодируется последовательностью \texttt...001011 или 11 вдесятичной системе. (в бинарной кодировке биты пишутся наоборот.) А таккак разложение на простые множители каждого числа — уникально, тоуникален и бинарный код каждого свободного от квадратов числа.
 Обратное так же верно: так как у каждого положительного числа —уникальный бинарный код, его можно декодировать, получая уникальныечисла, свободные от квадратов.
 Возьмём опять для примера число 42 — на этот раз просто в качествеположительного числа. Тогда мы получаем бинарный код \texttt101010 —это означает: 20 · 31 ·50 · 71 · 110 ·131 = 3 × 7 × 13 = 273.
 С точки зрения мощностей, это означает, что мощность множества чисел,свободных от квадратов, совпадает с мощностью множества всех натуральныхчисел. Что в свою очередь означает, что кодирования свободных отквадратов чисел по порядку — в точности перестановка множестванатуральных чисел.
 См. последовательности A048672 и A064273 на сайте OEIS.

ГипотезаЭрдёша


 Центральный биномиальный коэффициент (2nn) не может бытьсвободен от квадратов для n \textgreater 4.
 Это предположение Эрдёша о бесквадратности было доказано в 1996 годуматематиками Оливьером Рамарэ и Эндрю Грэвиллом.