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

Число без повторяющихся простых множителей

Число 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 без квадратов . ${\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 i>1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\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 k}$ ${\displaystyle n}$ ${\displaystyle n/k}$ ${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}.}$

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

Подводя итог, можно сказать, что существует три бесквадратных множителя, которые естественным образом связаны с каждым целым числом: бесквадратная часть, указанный выше множитель и наибольший бесквадратный множитель. Каждый из них является множителем следующего. Все они легко выводятся из разложения на простые множители или бесквадратного разложения: если — разложение на простые множители и бесквадратное разложение , где — различные простые числа, то бесквадратная часть равна Бесквадратный множитель, такой что частное является квадратом, равен и наибольший бесквадратный множитель равен ${\displaystyle k}$ $${\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 n/p}$ ${\displaystyle n}$ ${\displaystyle n=ab}$ ${\displaystyle a}$ ${\displaystyle b}$

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

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

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

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

ряд Дирихле

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

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

где ζ ( 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)}}$

ТаблицаВ(х),.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠6/π 2⁠х, иР(х)

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

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

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

Примечания

1. Adleman, Leonard M.; McCurley, Kevin S. (1994). "Открытые проблемы в числовой теоретической сложности, II". В Adleman, Leonard M.; Huang, Ming-Deh A. (ред.). Алгоритмическая теория чисел, Первый международный симпозиум, ANTS-I, Итака, Нью-Йорк, США, 6–9 мая 1994 г., Труды . Заметки лекций по информатике. Том 877. Springer. стр. 291–322. doi :10.1007/3-540-58691-1_70. ISBN 978-3-540-58691-3.
2. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (1 сентября 2004 г.). «ПРАЙМС находится в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 . ISSN  0003-486X. МР  2123939. Збл  1071.11070.
3. Ричардс, Челси (2009). Алгоритмы факторизации бесквадратных многочленов над конечными полями (PDF) (магистерская диссертация). Канада: Университет Саймона Фрейзера.
4. Вальфиш, А. (1963). Экспоненциальные суммы Вейля в neueren Zahlentheorie . Берлин: VEB Deutscher Verlag der Wissenschaften .
5. Цзя, Чао Хуа. «Распределение чисел, свободных от квадратов», Science in China Series A: Mathematics 36 :2 (1993), стр. 154–169. Цитируется в Паппаларди, 2003 г., «Обзор k-свободы»; см. также Каниника Синха, «Средние порядки некоторых арифметических функций», Журнал Рамануджанского математического общества 21 :3 (2006), стр. 267–277.
6. Лю, Х.-К. (2016). «О распределении чисел, свободных от квадратов». Журнал теории чисел . 159 : 202–222. doi : 10.1016/j.jnt.2015.07.013 .
7. Линфут, Э.Г .; Эвелин, CJA (1929). «Об одной задаче аддитивной теории чисел». Mathematische Zeitschrift . 30 : 443–448. дои : 10.1007/BF01187781. S2CID  120604049.
8. Parent, DP (1984). Упражнения по теории чисел. Задачники по математике. Springer-Verlag New York. doi :10.1007/978-1-4757-5194-9. ISBN 978-1-4757-5194-9.
9. Филасета, Майкл; Трифонов, Огнян (1992). «О пробелах между числами, свободными от квадратов. II». Журнал Лондонского математического общества . Вторая серия. 45 (2): 215–221. doi :10.1112/jlms/s2-45.2.215. MR  1171549.
10. Эндрю, Гранвиль (1998). «ABC позволяет нам считать бесквадратные элементы». Int. Math. Res. Not . 1998 (19): 991–1009. doi : 10.1155/S1073792898000592 .
11. Минору, Танака (1979). «Эксперименты, касающиеся распределения чисел, свободных от квадратов». Труды Японской академии, Серия A, Математические науки . 55 (3). doi : 10.3792/pjaa.55.101 . S2CID  121862978.
12. Саркози, А. (1985). «О делителях биномиальных коэффициентов. I». Журнал теории чисел . 20 (1): 70–80. doi : 10.1016/0022-314X(85)90017-4 . MR  0777971.
13. Рамаре, Оливье; Гранвиль, Эндрю (1996). «Явные границы экспоненциальных сумм и дефицитность бесквадратных биномиальных коэффициентов». Mathematika . 43 (1): 73–107. doi :10.1112/S0025579300011608.

Ссылки

• Шапиро, Гарольд Н. (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 г. .