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

В математике бесквадратным называется число, которое не делится ни на один квадрат, кроме 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, … последовательность A005117 в OEIS

Теория колец обобщает понятие бесквадратности.

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

Положительное число n бесквадратно тогда и только тогда, когда в разложении этого числа на простые множители ни одно простое число не встречается больше одного раза. По-другому это можно выразить так: для любого простого делителя p числа n, число p не делит n / p. Или, число n бесквадратно тогда и только тогда, когда для любого его разложения на множители n = ab, множители a и b взаимно просты.

Положительное число n бесквадратно тогда и только тогда, когда $\mu(n)\neq 0$, где $\mu(n)$ обозначает функцию Мёбиуса.

Ряд Дирихле, порождающий бесквадратные числа:

$\frac{\zeta(s)}{\zeta(2s) } = \sum_{n=1}^{\infty}\frac{ |\mu(n)|}{n^{s}}$ где $\zeta(s)$ — дзета-функция Римана.

Это сразу видно из произведения Эйлера:

$\frac{\zeta(s)}{\zeta(2s)} =\prod_p \frac{(1-p^{-2s})}{(1-p^{-s})}=\prod_p (1+p^{-s}).$

Положительное число n бесквадратно тогда и только тогда, когда все абелевы группы порядка изоморфны друг другу, что верно в том и только в том случае, когда они все — циклические. Это следует из классификации конечнопорождённых абелевых групп.

Положительное число n бесквадратно тогда и только тогда, когда факторкольцо $\mathbb{Z}/n\mathbb{Z}$ (см. сравнение по модулю) есть произведение полей. Это следует из китайской теоремы об остатках и того факта, что кольцо $\mathbb{Z}/k\mathbb{Z}$ — поле тогда и только тогда, когда k — простое число.

Для любого положительного числа n множество всех положительных его делителей представляет собой частично упорядоченное множество, если мы положим в качестве порядка отношение «делимости». Это частично упорядоченное множество — всегда дистрибутивная решётка. Оно — Булева алгебра в том и только в том случае, когда n бесквадратно.

Радикал целого числа всегда бесквадратен.

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

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

$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}}$

$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)}$

Можно получить формулу без дзета-функции:

$Q(x) = \frac{x}{\zeta(2)} + O\left(\sqrt{x}\right) = \frac{6x}{\pi^2} + O\left(\sqrt{x}\right)$

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

$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 и $\left[\frac{n}{\zeta(2)}\right]$ на сайте OEIS: A158819 — (Number of square-free numbers ≤ n) minus round(n/ζ(2)).

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

$\lim_{x\to\infty} \frac{Q(x)}{x} = \frac{6}{\pi^2} = \frac{1}{\zeta(2)}$

Где $\zeta~$ — дзета-функция Римана а $1/\zeta(2)\approx 0.6079$ (то есть, примерно 3/5 всех чисел бесквадратны).

Аналогично, если $Q(x,n)$ означает число n-свободных чисел (то есть 3-свободные числа не содержат кубов) между 1 и x, то:

$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).$

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

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

$\prod_{n=0}^\infty {p_{n+1}}^{a_n},$

где $a_n\in\{0,1\},$, а $p_n$ - n-е простое число, то мы можем выбирать эти коэффициенты $a_n$ и использовать их в качестве битов в бинарной кодировке:

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

Предположение Эрдёша о бесквадратности

Центральный биномиальный коэффициент ${2n \choose n}$ не может быть бесквадратен для n > 4. Это было доказано в 1996 году математиками Оливьером Рамарэ и Эндрю Грэвиллом.