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

Число 10 не содержит квадратов, так как его делители больше 1 равны 2, 5 и 10, ни один из которых не является квадратным (первые несколько квадратов равны 1, 4, 9 и 16).

Целые числа до 120 без квадратов остаются после исключения кратных квадратов простых чисел до √120.

В математике целое число без квадратов (или целое число без квадратов ) — это целое число , которое не делится ни на одно квадратное число, кроме 1. То есть его простая факторизация имеет ровно один множитель для каждого простого числа, которое в нем встречается. Например, 10 = 2 ⋅ 5 не содержит квадратов, а 18 = 2 ⋅ 3 ⋅ 3 — нет, поскольку 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$ могут быть учтены уникальным образом, как

$$n=\prod _{i=1}^{k}q_{i}^{i},$$

где $q_{i}$Отличаются от единицы целые числа без квадратов, которые попарно взаимно просты . называется бесквадратной факторизацией n Это .

Чтобы построить бесквадратную факторизацию, пусть

$$n=\prod _{j=1}^{h}p_{j}^{e_{j}}$$

быть факторизацией простой $n$, где $p_{j}$являются различными простыми числами . Тогда факторы бесквадратной факторизации определяются как

$$q_{i}=\prod _{j:e_{j}=i}p_{j}.$$

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

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

Безквадратные множители целых чисел

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

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

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

Любое произвольное положительное целое число $n$ может быть представлено уникальным образом как произведение квадрата и целого числа без квадратов:

$$n=m^{2}k$$

В этой факторизации $m$ является наибольшим делителем $n$ такой, что $m^{2}$ является делителем $n$.

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

$$n=\prod _{i=1}^{h}p_{i}^{e_{i}}=\prod _{i=1}^{k}q_{i}^{i}$$

- это простая факторизация и бесквадратная факторизация $n$, где $p_{1},\ldots ,p_{h}$ являются различными простыми числами, то свободная от квадратов часть равна

$$\prod _{e_{i}=1}p_{i}=q_{1},$$

Безквадратный множитель, такой как частное, является квадратом, равен

$$\prod _{e_{i}{\text{ odd}}}p_{i}=\prod _{i{\text{ odd}}}q_{i},$$

а наибольший безквадратный фактор равен

$$\prod _{i=1}^{h}p_{i}=\prod _{i=1}^{k}q_{i}.$$

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

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

Эквивалентные

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

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

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

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

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

Серия Дирихле

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

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

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

${\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 и так далее. Поскольку эти отношения удовлетворяют мультипликативному свойству (это следует из китайской теоремы об остатках ), мы получаем приближение:

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

Этот аргумент можно сделать строгим для получения оценки (используя обозначение big O )

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

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

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

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

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

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

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

Согласно гипотезе Римана , член ошибки можно свести к

$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 году срок ошибки был дополнительно сокращен до

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

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

$\lim _{x\to \infty }{\frac {Q(x)}{x}}={\frac {6}{\pi ^{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).$

Поскольку число, кратное 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 , половина всех натуральных чисел минус конечное число не должна быть несвободной. -свободный от квадратов и, следовательно,

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

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

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

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

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

Таблица Q ( x ), 6 / п ² х и R ( х )

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

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

$x$	$Q(x)$	${\frac {6}{\pi ^{2}}}x$	$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

$R(x)$ меняет знак бесконечно часто, так как $x$ стремится к бесконечности.

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

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

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

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

тогда мы можем взять их $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.

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

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

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

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

${2n \choose n}$

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

Ядро Squarefree

Назовем « t -свободным» целое положительное число, не имеют t делители которого -й степени. В частности, целые числа без 2 — это целые числа без квадратов.

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

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

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

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

$\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). Введение в теорию чисел . Публикации издательства Оксфордского университета в Дувре. ISBN  978-0-486-46669-9 .
• Гранвилл, Эндрю; Рамаре, Оливье (1996). «Явные границы экспоненциальных сумм и нехватка бесквадратных биномиальных коэффициентов». Математика . 43 : 73–107. CiteSeerX   10.1.1.55.8 . дои : 10.1112/S0025579300011608 . МР   1401709 . Збл   0868.11009 .
• Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Спрингер-Верлаг . ISBN  978-0-387-20860-2 . Збл   1058.11001 .
• «ОЭИС Вики» . Проверено 24 сентября 2021 г.