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

В математике целое число, свободное от квадратов (или целое число, свободное от квадратов ), — это целое число , которое не делится ни на какое квадратное число, кроме 1. То есть, его разложение на простые множители имеет ровно один множитель для каждого простого числа, которое в нем появляется. Например, 10 = 2 ⋅ 5 свободно от квадратов, но 18 = 2 ⋅ 3 ⋅ 3 — нет, потому что 18 делится на 9 = 3 ² . Наименьшие положительные свободные от квадратов числа:

Каждое положительное целое число можно разложить на множители уникальным образом, где отличными от единицы являются целые числа без квадратов, которые попарно взаимно просты . Это называется разложением числа n без квадратов .${\displaystyle n}$$${\displaystyle n=\prod _{i=1}^{k}q_{i}^{i},}$$${\displaystyle q_{i}}$

Для построения факторизации без квадратов пусть будет факторизацией числа , где — различные простые числа . Тогда факторы факторизации без квадратов определяются как $${\displaystyle n=\prod _{j=1}^{h}p_{j}^{e_{j}}}$$${\displaystyle n}$${\displaystyle p_{j}}$$${\displaystyle q_{i}=\prod _{j:e_{j}=i}p_{j}.}$$

Целое число является свободным от квадратов тогда и только тогда, когда для всех . Целое число, большее единицы, является -й степенью другого целого числа тогда и только тогда, когда является делителем всех таких, что${\displaystyle q_{i}=1}$${\displaystyle я>1}$${\displaystyle к}$${\displaystyle к}$${\displaystyle я}$${\displaystyle q_{i}\neq 1.}$

Использование факторизации целых чисел без квадратов ограничено тем фактом, что ее вычисление так же сложно, как и вычисление факторизации на простые множители. Точнее, каждый известный алгоритм вычисления факторизации без квадратов вычисляет и факторизацию на простые множители. Это заметное отличие от случая многочленов , для которых можно дать те же определения, но в этом случае факторизация без квадратов не только проще для вычисления, чем полная факторизация, но и является первым шагом всех стандартных алгоритмов факторизации.

Радикал целого числа — это его наибольший свободный от квадратов множитель, то есть с обозначениями предыдущего раздела. Целое число свободно от квадратов тогда и только тогда, когда оно равно своему радикалу.${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}}$

Каждое положительное целое число может быть представлено уникальным способом как произведение мощного числа (то есть целого числа, которое делится на квадрат каждого простого множителя) и свободного от квадратов целого числа, которые являются взаимно простыми . В этой факторизации свободный от квадратов множитель равен , а мощное число равно${\displaystyle n}$${\displaystyle q_{1},}$${\displaystyle \textstyle \prod _ {i = 2} ^ {k} q_ {i} ^ {i}.}$

Бесквадратная часть числа — это наибольший бесквадратный делитель числа, который является взаимно простым с . Бесквадратная часть целого числа может быть меньше наибольшего бесквадратного делителя, который является${\displaystyle n}$${\displaystyle q_{1},}$${\displaystyle к}$${\displaystyle n}$${\displaystyle н/к}$${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}.}$

Любое произвольное положительное целое число можно представить единственным способом как произведение квадрата и целого числа, свободного от квадратов: В этой факторизации — наибольший делитель числа , такой, что является делителем числа .${\displaystyle n}$$${\displaystyle n=m^{2}k}$$${\displaystyle м}$${\displaystyle n}$${\displaystyle м^{2}}$${\displaystyle n}$

Подводя итог, можно сказать, что существует три бесквадратных множителя, которые естественным образом связаны с каждым целым числом: бесквадратная часть, указанный выше множитель и наибольший бесквадратный множитель. Каждый из них является множителем следующего. Все они легко выводятся из разложения на простые множители или бесквадратного разложения: если — разложение на простые множители и бесквадратное разложение , где — различные простые числа, то бесквадратная часть равна Бесквадратный множитель, такой что частное является квадратом, равен и наибольший бесквадратный множитель равен ${\displaystyle к}$$${\displaystyle n=\prod _{i=1}^{h}p_{i}^{e_{i}}=\prod _{i=1}^{k}q_{i}^{i}}$$${\displaystyle n}$${\displaystyle p_{1},\ldots ,p_{h}}$$${\displaystyle \prod _{e_{i}=1}p_{i}=q_{1},}$$$${\displaystyle \prod _{e_{i}{\text{ odd}}}p_{i}=\prod _{i{\text{ odd}}}q_{i},}$$$${\displaystyle \prod _{i=1}^{h}p_{i}=\prod _{i=1}^{k}q_{i}.}$$

Например, если бесквадратная часть равна 7 , то бесквадратный множитель, при котором частное является квадратом, равен 3 ⋅ 7 = 21 , а наибольший бесквадратный множитель равен 2 ⋅ 3 ⋅ 5 ⋅ 7 = 210 .${\displaystyle n=75600=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7,}$${\displaystyle q_{1}=7,\;q_{2}=5,\;q_{3}=3,\;q_{4}=2.}$

Неизвестен ни один алгоритм для вычисления любого из этих бесквадратных множителей, который был бы быстрее, чем вычисление полной простой факторизации. В частности, неизвестен алгоритм полиномиального времени для вычисления бесквадратной части целого числа или даже для определения того, является ли целое число бесквадратным. ^[1] Напротив, известны алгоритмы полиномиального времени для проверки простоты . ^[2] Это основное различие между арифметикой целых чисел и арифметикой одномерных многочленов , поскольку известны алгоритмы полиномиального времени для бесквадратной факторизации многочленов (короче говоря, наибольший бесквадратный множитель многочлена — это его частное на наибольший общий делитель многочлена и его формальную производную ). ^[3]

Положительное целое число является свободным от квадратов тогда и только тогда, когда в разложении на простые множители нет простого множителя с показателем больше единицы. Другой способ сформулировать то же самое заключается в том, что для каждого простого множителя простое число не делится нацело  . Также является свободным от квадратов тогда и только тогда, когда в каждом разложении на простые множители и являются взаимно простыми . Непосредственным результатом этого определения является то, что все простые числа являются свободными от квадратов.${\displaystyle n}$${\displaystyle n}$ ${\displaystyle p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle н/п}$${\displaystyle n}$${\displaystyle n=ab}$${\displaystyle а}$${\displaystyle б}$

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

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

Для каждого положительного целого числа множество всех положительных делителей становится частично упорядоченным множеством , если мы используем делимость как отношение порядка. Это частично упорядоченное множество всегда является дистрибутивной решеткой . Это булевская алгебра тогда и только тогда, когда является бесквадратной.${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

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

Абсолютное значение функции Мёбиуса является индикаторной функцией для целых чисел, свободных от квадратов, то есть | μ ( n ) | равно 1, если n свободно от квадратов, и 0, если нет. Ряд Дирихле этой индикаторной функции равен

${\displaystyle \sum _{n=1}^{\infty }{\frac {|\mu (n)|}{n^{s}}} = {\frac {\zeta (s)}{\zeta (2с)}},}$

где ζ ( s ) — дзета-функция Римана . Это следует из произведения Эйлера

${\displaystyle {\frac {\zeta (s)}{\zeta (2s)}}=\prod _{p}{\frac {(1-p^{-2s})}{(1-p^{-s})}}=\prod _{p}(1+p^{-s}),}$

где произведения берутся по простым числам.

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

${\displaystyle {\begin{aligned}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}}}\\&=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)}}={\frac {6x}{\pi ^{2}}}.\end{aligned}}}$

Этот аргумент можно сделать строгим для получения оценки (используя нотацию «большое О» )

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

Набросок доказательства: приведенная выше характеристика дает

${\displaystyle Q(x)=\sum _{n\leq x}\sum _{d^{2}\mid n}\mu (d)=\sum _{d\leq x}\mu (d)\sum _{n\leq x,d^{2}\mid n}1=\sum _{d\leq x}\mu (d)\left\lfloor {\frac {x}{d^{2}}}\right\rfloor ;}$

заметив, что последнее слагаемое равно нулю для , получаем, что${\displaystyle d>{\sqrt {x}}}$

${\displaystyle {\begin{aligned}Q(x)&=\sum _{d\leq {\sqrt {x}}}\mu (d)\left\lfloor {\frac {x}{d^{2}}}\right\rfloor =\sum _{d\leq {\sqrt {x}}}{\frac {x\mu (d)}{d^{2}}}+O\left(\sum _{d\leq {\sqrt {x}}}1\right)=x\sum _{d\leq {\sqrt {x}}}{\frac {\mu (d)}{d^{2}}}+O({\sqrt {x}})\\&=x\sum _{d}{\frac {\mu (d)}{d^{2}}}+O\left(x\sum _{d>{\sqrt {x}}}{\frac {1}{d^{2}}}+{\sqrt {x}}\right)={\frac {x}{\zeta (2)}}+O({\sqrt {x}}).\end{aligned}}}$

Используя наибольшую известную свободную от нулей область дзета-функции Римана, Арнольд Вальфис улучшил приближение к ^[4]

${\displaystyle Q(x)={\frac {6x}{\pi ^{2}}}+O\left(x^{1/2}\exp \left(-c{\frac {(\log x)^{3/5}}{(\log \log x)^{1/5}}}\right)\right),}$

для некоторой положительной константы c .

Согласно гипотезе Римана , ошибка может быть уменьшена до ^[5]

${\displaystyle Q(x)={\frac {x}{\zeta (2)}}+O\left(x^{17/54+\varepsilon }\right)={\frac {6}{\pi ^{2}}}x+O\left(x^{17/54+\varepsilon }\right).}$

В 2015 году ошибка была дополнительно уменьшена (предполагая также гипотезу Римана) до ^[6]

${\displaystyle Q(x)={\frac {6}{\pi ^{2}}}x+O\left(x^{11/35+\varepsilon }\right).}$

Асимптотическая/ естественная плотность чисел, свободных от квадратов, таким образом, равна

${\displaystyle \lim _{x\to \infty }{\frac {Q(x)}{x}}={\frac {6}{\pi ^{2}}}\approx 0.6079}$

Следовательно, более 3/5 целых чисел не содержат квадратов.

Аналогично, если Q ( x , n ) обозначает число целых чисел, свободных от n (например, целые числа, свободные от 3, являются целыми числами, свободными от кубов) между 1 и x , можно показать ^[7]

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

Поскольку кратное 4 должно иметь квадратный множитель 4=2 ² , не может случиться так, что четыре последовательных целых числа все являются свободными от квадратов. С другой стороны, существует бесконечно много целых чисел n, для которых 4 n +1, 4 n +2, 4 n +3 все являются свободными от квадратов. В противном случае, заметив, что 4 n и по крайней мере одно из 4 n +1, 4 n +2, 4 n +3 среди четырех может быть не свободным от квадратов для достаточно большого n , половина всех положительных целых чисел за вычетом конечного числа должна быть не свободным от квадратов и, следовательно,

${\displaystyle Q(x)\leq {\frac {x}{2}}+C}$для некоторой константы C ,

вопреки приведенной выше асимптотической оценке для .${\displaystyle Q(x)}$

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

${\displaystyle n\equiv -i{\pmod {p_{i}^{2}}}\qquad (i=1,2,\ldots ,l)}$

для различных простых чисел , то каждое делится на p _i ² . ^[8] С другой стороны, вышеупомянутая оценка подразумевает, что для некоторой константы c всегда существует свободное от квадратов целое число между x и для положительных x . Более того, элементарный аргумент позволяет нам заменить на ^[9] Гипотеза ABC допускает . ^[10]${\displaystyle p_{1},p_{2},\ldots ,p_{l}}$${\displaystyle n+i}$${\displaystyle Q(x)=6x/\pi ^{2}+O\left({\sqrt {x}}\right)}$${\displaystyle x+c{\sqrt {x}}}$${\displaystyle x+c{\sqrt {x}}}$${\displaystyle x+cx^{1/5}\log x.}$${\displaystyle x+x^{o(1)}}$

В таблице показано, как и (последнее округлено до одного знака после запятой) сравниваются в степенях 10.${\displaystyle Q(x)}$${\displaystyle {\frac {6}{\pi ^{2}}}x}$

${\displaystyle R(x)=Q(x)-{\frac {6}{\pi ^{2}}}x}$, также обозначается как .${\displaystyle \Delta (x)}$

${\displaystyle x}$	${\displaystyle Q(x)}$	${\displaystyle {\frac {6}{\pi ^{2}}}x}$	${\displaystyle R(x)}$
10	7	6.1	0.9
10 2	61	60,8	0.2
10 3	608	607.9	0.1
10 4	6,083	6,079.3	3.7
10 5	60,794	60,792.7	1.3
10 6	607,926	607,927.1	- 1.3
10 7	6,079,291	6,079,271.0	20.0
10 8	60,792,694	60,792,710.2	- 16.2
10 9	607,927,124	607,927,101.9	22.1
10 10	6,079,270,942	6,079,271,018.5	- 76,5
10 11	60,792,710,280	60,792,710,185.4	94,6
10 12	607,927,102,274	607,927,101,854.0	420.0
10 13	6,079,271,018,294	6,079,271,018,540.3	- 246,3
10 14	60,792,710,185,947	60,792,710,185,402.7	544.3
10 15	607,927,101,854,103	607,927,101,854,027.0	76.0

${\displaystyle R(x)}$меняет свой знак бесконечно часто, стремясь к бесконечности. ^[11]${\displaystyle x}$

Абсолютное значение поразительно мало по сравнению с .${\displaystyle R(x)}$${\displaystyle x}$

Если мы представим свободное от квадратов число как бесконечное произведение

${\displaystyle \prod _{n=0}^{\infty }(p_{n+1})^{a_{n}},a_{n}\in \lbrace 0,1\rbrace ,{\text{ and }}p_{n}{\text{ is the }}n{\text{th prime}},}$

то мы можем взять их и использовать как биты в двоичном числе с кодировкой${\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.

Таким образом, двоичное кодирование бесквадратных чисел описывает биекцию между неотрицательными целыми числами и множеством положительных бесквадратных целых чисел.

(См. последовательности A019565, A048672 и A064273 в OEIS .)

Центральный биномиальный коэффициент

${\displaystyle {2n \choose n}}$

никогда не является бесквадратным для n > 4. Это было доказано в 1985 году для всех достаточно больших целых чисел Андрашем Саркози ^[12] и для всех целых чисел > 4 в 1996 году Оливье Рамаре и Эндрю Грэнвиллем ^[13] .

Назовем " t -free" положительное целое число, которое не имеет t -й степени в своих делителях. В частности, 2-free целые числа являются целыми числами, свободными от квадратов.

Мультипликативная функция отображает каждое положительное целое число n в частное от деления n на его наибольший делитель, являющийся степенью t . То есть, ${\displaystyle \mathrm {core} _{t}(n)}$

${\displaystyle \mathrm {core} _{t}(p^{e})=p^{e{\bmod {t}}}.}$

Целое число является t -свободным, и каждое t -свободное целое число отображается само на себя функцией${\displaystyle \mathrm {core} _{t}(n)}$${\displaystyle \mathrm {core} _{t}.}$

Производящая функция Дирихле последовательности равна${\displaystyle \left(\mathrm {core} _{t}(n)\right)_{n\in \mathbb {N} }}$

${\displaystyle \sum _{n\geq 1}{\frac {\mathrm {core} _{t}(n)}{n^{s}}}={\frac {\zeta (ts)\zeta (s-1)}{\zeta (ts-t)}}}$.

См. также OEIS : A007913 ( t =2), OEIS : A050985 ( t =3) и OEIS : A053165 ( t =4).

• Шапиро, Гарольд Н. (1983). Введение в теорию чисел . Oxford University Press Dover Publications. ISBN 978-0-486-46669-9.
• Гранвиль, Эндрю; Рамаре, Оливье (1996). «Явные границы экспоненциальных сумм и дефицитность бесквадратных биномиальных коэффициентов». Mathematika . 43 : 73–107. CiteSeerX  10.1.1.55.8 . doi :10.1112/S0025579300011608. MR  1401709. Zbl  0868.11009.
• Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag . ISBN 978-0-387-20860-2. Збл  1058.11001.
• "OEIS Wiki" . Получено 24 сентября 2021 г. .