В математике свободным от квадратов , или бесквадратным , называется число , которое не делится ни на один квадрат , кроме 1. К примеру, 10 — свободное от квадратов, а 18 — нет, так как 18 делится на 9 = 3 ² . Начало последовательности свободных от квадратов чисел таково:

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, … последовательность в 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:

Таким образом асимптотическая плотность свободных от квадратов чисел выглядит так:

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

С точки зрения мощностей, это означает, что мощность множества чисел, свободных от квадратов, совпадает с мощностью множества всех натуральных чисел. Что в свою очередь означает, что кодирования свободных от квадратов чисел по порядку — в точности перестановка множества натуральных чисел.

См. последовательности и на сайте OEIS .

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

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

Это предположение Эрдёша о бесквадратности было доказано в 1996 году математиками Оливьером Рамарэ и Эндрю Грэвиллом.

См. также

• Функция Мёбиуса

Литература

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

Примечания