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

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

Число 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 }$

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

Абсолютное значение функции Мёбиуса является индикаторной функцией для целых чисел без квадратов, то есть | μ ( п ) | равно 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}}}$

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

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

для различных простых чисел каждое ^из них делится на pi ₂ . ^[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 -свободным» целое положительное число, делители которого не имеют t -й степени. В частности, целые числа без 2 — это целые числа без квадратов.

Мультипликативная функция отображает каждое положительное целое число 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. Адлеман, Леонард М.; МакКерли, Кевин С. (1994). «Открытые задачи теоретико-числовой сложности, II». В Адлемане, Леонард М.; Хуанг, Мин-Де А. (ред.). Алгоритмическая теория чисел, Первый международный симпозиум, ANTS-I, Итака, Нью-Йорк, США, 6–9 мая 1994 г., Труды . Конспекты лекций по информатике. Том. 877. Спрингер. стр. 291–322. дои : 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. Лю, H.-Q. (2016). «О распределении бесквадратных чисел». Журнал теории чисел . 159 : 202–222. дои : 10.1016/j.jnt.2015.07.013 .
7. Линфут, Э.Г .; Эвелин, CJA (1929). «Об одной задаче аддитивной теории чисел». Mathematische Zeitschrift . 30 : 443–448. дои : 10.1007/BF01187781. S2CID  120604049.
8. Родитель, DP (1984). Упражнения по теории чисел. Задачи по математике. Спрингер-Верлаг Нью-Йорк. дои : 10.1007/978-1-4757-5194-9. ISBN 978-1-4757-5194-9.
9. Филасета, Майкл; Трифонов, Огнян (1992). «О промежутках между бесквадратными числами. II». Журнал Лондонского математического общества . Вторая серия. 45 (2): 215–221. дои : 10.1112/jlms/s2-45.2.215. МР  1171549.
10. Эндрю, Гранвиль (1998). «ABC позволяет нам считать квадраты». Межд. Математика. Рез. Нет . 1998 (19): 991–1009. дои : 10.1155/S1073792898000592 .
11. Минору, Танака (1979). «Опыты по распределению бесквадратных чисел». Труды Японской академии, серия A, Математические науки . 55 (3). дои : 10.3792/pjaa.55.101 . S2CID  121862978.
12. Саркози, А. (1985). «О делителях биномиальных коэффициентов. I». Журнал теории чисел . 20 (1): 70–80. дои : 10.1016/0022-314X(85)90017-4 . МР  0777971.
13. Рамаре, Оливье; Гранвилл, Эндрю (1996). «Явные границы экспоненциальных сумм и нехватка бесквадратных биномиальных коэффициентов». Математика . 43 (1): 73–107. дои : 10.1112/S0025579300011608.

Рекомендации

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