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

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

В математике, целое число без квадратов (или целое число без квадратов ) является целым числом, которое не делится ни на какой полный квадрат, кроме 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 )

• 1 Факторизация без квадратов
• 2 Факторы без квадратов целых чисел
• 3 Эквивалентные характеристики
• 4 Серия Дирихле
• 5 Распределение
  • 5.1 Таблица $Q\; (x),\; 6\; \pi \; 2\; x\; \{\backslash \; displaystyle\; Q\; (x),\; \{\backslash \; frac\; \{6\}\; \{\backslash \; pi\; ^\; \{2\}\}\}\; x\}$и $R\; (x)\; \{\backslash \; displaystyle\; R\; (x)\}$
• 6 Кодирование двоичными числами
• 7 Гипотеза Эрдеша без квадратов
• 8 Бесквадратное ядро ​​
• 9 Примечания
• 10 Ссылки

Каждое положительное целое число n может быть разложено на множители уникальным образом:

$n\; =\; \prod \; i\; =\; 1\; kqii,\; \{\backslash \; displaystyle\; n\; =\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{\; k\}\; q\_\; \{i\}\; ^\; \{i\},\}$

где $qi\; \{\backslash \; displaystyle\; q\_\; \{i\}\}$, отличный от единицы, являются целыми числами без квадратов, которые равны pairwi se coprime.

Это называется факторизацией числа n без квадратов.

Пусть

$n\; =\; \prod \; j\; =\; 1\; hpjej\; \{\backslash \; displaystyle\; n\; =\; \backslash \; prod\; \_\; \{j\; =\; 1\}\; ^\; \{h\}\; p\_\; \{j\}\; ^\; \{e\_\; \{j\}\}\}$

будет разложение на простые множители числа n, где p j - различные простые числа. Тогда коэффициенты факторизации без квадратов определяются как

$q\; i\; =\; \prod \; j:\; e\; j\; =\; i\; p\; j.\; \{\backslash \; displaystyle\; q\_\; \{i\}\; =\; \backslash \; prod\; \_\; \{j:\; e\_\; \{j\}\; =\; i\}\; p\_\; \{j\}.\}$

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

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

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

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

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

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

$n\; =\; m\; 2\; k\; \{\backslash \; displaystyle\; n\; =\; m\; ^\; \{2\}\; k\}$

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

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

$n\; =\; \prod \; i\; =\; 1\; hpiei\; =\; \prod \; i\; =\; 1\; kqii\; \{\backslash \; displaystyle\; n\; =\; \backslash \; prod\; \_\; \{i\; =\; 1\; \}\; ^\; \{h\}\; p\_\; \{i\}\; ^\; \{e\_\; \{i\}\}\; =\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{k\}\; q\_\; \{i\}\; ^\; \{i\}\}$

- разложение на простые множители и бесквадратное факторизация n, где $p\; 1,\dots ,\; ph\; \{\backslash \; displaystyle\; p\_\; \{1\},\; \backslash \; ldots,\; p\_\; \{h\}\}$- различные простые числа, тогда часть без квадратов

$\prod \; ei\; =\; 1\; pi\; =\; q\; 1,\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{e\_\; \{i\}\; =\; 1\}\; p\_\; \{i\}\; =\; q\_\; \{1\},\}$

Фактор без квадратов, такой как квадрат, равен

$\prod \; ei\; odd\; pi\; =\; \prod \; i\; odd\; qi,\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{e\_\; \{i\}\; \{\backslash \; text\; \{odd\}\}\}\; p\_\; \{i\}\; =\; \backslash \; prod\; \_\; \{i\; \{\backslash \; text\; \{odd\}\}\}\; q\_\; \{i\},\}$

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

$\prod \; i\; =\; 1\; hpi\; =\; \prod \; i\; =\; 1\; kqi.\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{h\}\; p\_\; \{i\}\; =\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{k\}\; q\_\; \{i\}.\}$

Например, если $n\; =\; 75600\; =\; 2\; 4\; \cdot \; 3\; 3\; \cdot \; 5\; 2\; \cdot \; 7,\; \{\backslash \; displaystyle\; n\; =\; 75600\; =\; 2\; ^\; \{4\}\; \backslash \; cdot\; 3\; ^\; \{3\}\; \backslash \; cdot\; 5\; ^\; \{2\}\; \backslash \; cdot\; 7,\}$один имеет $q\; 1\; =\; 7,\; q\; 2\; =\; 5,\; q\; 3\; =\; 3,\; q\; 4\; =\; 2.\; \{\backslash \; displaystyle\; q\_\; \{1\}\; =\; 7,\; \backslash ;\; q\_\; \{2\}\; =\; 5,\; \backslash ;\; q\_\; \{3\}\; =\; 3,\; \backslash ;\; 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 ar e изоморфна, что имеет место тогда и только тогда, когда любая такая группа является циклической. Это следует из классификации конечно порожденных абелевых групп.

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

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

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

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

$\sum \; n\; =\; 1\; \infty \; |\; \mu \; (n)\; |\; ns\; знак\; равно\; \zeta \; (s)\; \zeta \; (2\; s),\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 1\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{|\; \backslash \; mu\; (n)\; |\}\; \{n\; ^\; \{s\}\}\}\; =\; \{\; \backslash \; frac\; \{\backslash \; zeta\; (s)\}\; \{\backslash \; zeta\; (2s)\}\},\}$

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

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

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

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

$Q\; (x)\; \approx \; x\; \prod \; p\; prime\; (1\; -\; 1\; p\; 2)\; =\; x\; \prod \; p\; простое\; 1\; (1\; -\; 1\; p\; 2)\; -\; 1\; \approx \; x\; \prod \; p\; простое\; 1\; 1\; +\; 1\; p\; 2\; +\; 1\; p\; 4\; +\; \cdots \; =\; x\; \sum \; k\; =\; 1\; \infty \; 1\; k\; 2\; =\; x\; \zeta \; (2)\; =\; 6\; х\; \pi \; 2.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; Q\; (x)\; \backslash \; приблизительно\; x\; \backslash \; prod\; \_\; \{p\; \backslash \; \{\backslash \; text\; \{prime\}\}\}\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{1\}\; \{p\; ^\; \{2\}\}\}\; \backslash \; right)\; =\; x\; \backslash \; prod\; \_\; \{p\; \backslash \; \{\backslash \; text\; \{prime\}\}\}\; \{\backslash \; frac\; \{1\}\; \{(1\; -\; \{\backslash \; frac\; \{1\}\; \{p\; ^\; \{2\}\}\})\; ^\; \{-\; 1\}\}\; \}\; \backslash \backslash \; \backslash \; приблизительно\; x\; \backslash \; prod\; \_\; \{p\; \backslash \; \{\backslash \; text\; \{prime\}\}\}\; \{\backslash \; frac\; \{1\}\; \{1\; +\; \{\backslash \; frac\; \{1\}\; \{p\; ^\; \{2\}\}\}\; +\; \{\backslash \; frac\; \{1\; \}\; \{p\; ^\; \{4\}\}\}\; +\; \backslash \; cdots\}\}\; =\; \{\backslash \; frac\; \{x\}\; \{\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{1\}\; \{k\; ^\; \{2\}\}\}\}\; \}\; =\; \{\backslash \; frac\; \{x\}\; \{\backslash \; zeta\; (2)\}\}\; =\; \{\backslash \; frac\; \{6x\}\; \{\backslash \; pi\; ^\; \{2\}\}\}.\; \backslash \; end\; \{align\}\}\}$

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

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

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

$Q\; (x)\; =\; \sum \; n\; \le \; x\; \sum \; d\; 2\; \mid \; n\; \mu \; (\; г)\; знак\; равно\; \sum \; d\; \le \; Икс\; \mu \; (d)\; \sum \; N\; \le \; Икс,\; d\; 2\; \mid \; N\; 1\; =\; \sum \; d\; \le \; Икс\; \mu \; (d)\; \lfloor \; xd\; 2\; \rfloor ;\; \{\backslash \; Displaystyle\; Q\; (x)\; =\; \backslash \; sum\; \_\; \{n\; \backslash \; Leq\; x\}\; \backslash \; sum\; \_\; \{d\; ^\; \{2\}\; \backslash \; mid\; n\}\; \backslash \; mu\; (d)\; =\; \backslash \; sum\; \_\; \{d\; \backslash \; leq\; x\}\; \backslash \; mu\; (d)\; \backslash \; sum\; \_\; \{n\; \backslash \; leq\; x,\; d\; ^\; \{2\}\; \backslash \; mid\; n\}\; 1\; =\; \backslash \; sum\; \_\; \{d\; \backslash \; leq\; x\}\; \backslash \; mu\; (d)\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{x\}\; \{d\; ^\; \{2\}\}\}\; \backslash \; right\; \backslash \; rfloor;\}$

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

$Q\; (x)\; =\; \sum \; d\; \le \; x\; \mu \; (d)\; \lfloor \; xd\; 2\; \rfloor \; =\; \sum \; d\; \le \; xx\; \mu \; (d)\; d\; 2\; +\; O\; (\sum \; d\; \le \; x\; 1)\; =\; x\; \sum \; d\; \le \; x\; \mu \; (d)\; d\; 2\; +\; O\; (x)\; =\; x\; \sum \; d\; \mu \; (d)\; d\; 2\; +\; O\; (x\; \sum \; d>x\; 1\; d\; 2\; +\; x).)\; =\; x\; \zeta \; (2)\; +\; O\; (x).\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; Q\; (x)\; =\; \backslash \; sum\; \_\; \{d\; \backslash \; leq\; \{\backslash \; sqrt\; \{x\}\}\}\; \backslash \; mu\; (d)\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{x\}\; \{d\; ^\; \{2\; \}\}\}\; \backslash \; right\; \backslash \; rfloor\; =\; \backslash \; sum\; \_\; \{d\; \backslash \; leq\; \{\backslash \; sqrt\; \{x\}\}\}\; \{\backslash \; frac\; \{x\; \backslash \; mu\; (d)\}\; \{d\; ^\; \{2\}\}\}\; +\; O\; (\backslash \; sum\; \_\; \{d\; \backslash \; leq\; \{\backslash \; sqrt\; \{x\}\}\}\; 1)\; =\; x\; \backslash \; sum\; \_\; \{d\; \backslash \; leq\; \{\backslash \; sqrt\; \{x\}\}\}\; \{\backslash \; frac\; \{\backslash \; mu\; (d)\}\; \{d\; ^\; \{2\}\}\}\; +\; O\; (\; \{\backslash \; sqrt\; \{x\}\})\; \backslash \backslash \; =\; x\; \backslash \; sum\; \_\; \{d\}\; \{\backslash \; frac\; \{\backslash \; mu\; (d)\}\; \{d\; ^\; \{2\}\}\}\; +\; O\; \backslash \; left\; (x\; \backslash \; sum\; \_\; \{d>\{\; \backslash \; sqrt\; \{x\}\}\}\; \{\backslash \; frac\; \{1\}\; \{d\; ^\; \{2\}\}\}\; +\; \{\backslash \; sqrt\; \{x\}\}\; \backslash \; right)\; =\; \{\backslash \; frac\; \{x\}\; \{\backslash \; zeta\; (2)\}\}\; +\; O\; (\; \{\backslash \; sqrt\; \{x\}\}).\; \backslash \; end\; \{align\}\}\}$

За счет использования самой большой известной области без нулей функции Арнольд Вальфис улучшил приближение до

$Q\; (x)\; =\; 6\; x\; \pi \; 2\; +\; O\; (x\; 1/2\; exp\; \; (-\; c\; (log\; \; x)\; 3/5\; (log\; \; log\; \; x)\; 1\; /\; 5)),\; \{\backslash \; displaystyle\; Q\; (x)\; =\; \{\backslash \; frac\; \{6x\}\; \{\backslash \; pi\; ^\; \{2\}\}\}\; +\; O\; \backslash \; left\; (x\; ^\; \{1/2\}\; \backslash \; exp\; \backslash \; left\; (-c\; \{\backslash \; frac\; \{\; (\backslash \; журнал\; х)\; ^\; \{\; 3/5\}\}\; \{(\backslash \; log\; \backslash \; log\; x)\; ^\; \{1/5\}\}\}\; \backslash \; right)\; \backslash \; right),\}$

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

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

$Q\; (x)\; =\; x\; \zeta \; (2)\; +\; O\; (x\; 17/54\; +\; \epsilon )\; =\; 6\; \pi \; 2\; х\; +\; О\; (х\; 17/54\; +\; е).\; \{\backslash \; Displaystyle\; Q\; (x)\; =\; \{\backslash \; frac\; \{x\}\; \{\backslash \; zeta\; (2)\}\}\; +\; O\; \backslash \; left\; (x\; ^\; \{17/54\; +\; \backslash \; varepsilon\}\; \backslash \; right)\; =\; \{\backslash \; frac\; \{6\}\; \{\backslash \; pi\; ^\; \{2\}\}\}\; x\; +\; O\; \backslash \; left\; (x\; ^\; \{17/54\; +\; \backslash \; varepsilon\}\; \backslash \; right).\}$

Недавно (2015 г.) член ошибки был дополнительно сокращен до

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

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

$lim\; x\; \to \; \infty \; Q\; (x)\; x\; =\; 6\; \pi \; 2\; \approx \; 0,6079\; \{\backslash \; displaystyle\; \backslash \; lim\; \_\; \{x\; \backslash \; to\; \backslash \; infty\}\; \{\backslash \; frac\; \{\; Q\; (x)\}\; \{x\}\}\; =\; \{\backslash \; frac\; \{6\}\; \{\backslash \; pi\; ^\; \{2\}\}\}\; \backslash \; приблизительно\; 0.6079\}$

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

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

$Q\; (x,\; n)\; знак\; равно\; x\; \sum \; k\; =\; 1\; \infty \; 1\; kn\; +\; O\; (xn)\; =\; x\; \zeta \; (n)\; +\; O\; (xn).\; \{\backslash \; displaystyle\; Q\; (x,\; n)\; =\; \{\backslash \; frac\; \{x\}\; \{\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{1\}\; \{k\; ^\; \{n\}\}\}\}\}\; +\; O\; \backslash \; left\; (\{\backslash \; sqrt\; [\{n\}]\; \{x\}\}\; \backslash \; right)\; =\; \{\backslash \; frac\; \{x\}\; \{\backslash \; zeta\; (n)\}\}\; +\; O\; \backslash \; left\; (\{\backslash \; sqrt\; [\{n\}]\; \{x\}\}\; \backslash \; right).\}$

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

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

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

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

$n\; n\; -\; i\; (mod\; pi\; 2)\; (i\; =\; 1,\; 2,\dots ,\; l)\; \{\backslash \; displaystyle\; n\; \backslash \; Equiv\; -i\; \{\backslash \; pmod\; \{p\_\; \{i\}\; ^\; \{2\; \}\}\}\; \backslash \; qquad\; (i\; =\; 1,2,\; \backslash \; ldots,\; l)\}$

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

Таблица $Q\; (x),\; 6\; \pi \; 2\; x\; \{\backslash \; displaystyle\; Q\; (x),\; \{\backslash \; frac\; \{6\}\; \{\backslash \; pi\; ^\; \{2\}\}\}\; x\}$и $R\; (x)\; \{\backslash \; displaystyle\; R\; (x)\}$

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

$R\; (x)\; =\; Q\; (x)\; -\; 6\; \pi \; 2\; Икс\; \{\backslash \; Displaystyle\; R\; (x)\; =\; Q\; (x)\; -\; \{\backslash \; frac\; \{6\}\; \{\backslash \; pi\; ^\; \{2\}\}\}\; x\}$, также обозначается как $\Delta \; (Икс)\; \{\backslash \; Displaystyle\; \backslash \; Дельта\; (х)\}$.

<350,271>620,094,079 270><260,102,727,07,027,027,0270,0260,0270,0270,0270,0270,0270,0270,0270,0260,0270,0270,0270,0270,0270

$Икс\; \{\backslash \; Displaystyle\; х\}$	$Q\; (х)\; \{\backslash \; Displaystyle\; Q\; (х)\}$	$6\; \pi \; 2\; х\; \{\backslash \; Displaystyle\; \{\backslash \; frac\; \{\; 6\}\; \{\backslash \; pi\; ^\; \{2\}\}\}\; x\}$	$R\; (x)\; \{\backslash \; displaystyle\; R\; (x)\}$
10	7	6,1	0,9
10	61	60,8	0,2
10	608	607,9	0,1
10	6,083	6,079,3	3,7
10	60,794	60,792,7	1,3
10	607,926	607,927,1	- 1,3
10	6,079,291	6,079,271,0	20,0
10	60,792,694	60,792,710,2	- 16,2
10	607,927,124	607,927,101,9	22,1
10	6,079,270,942	6,079,271,018,5	- 76,5
10	60,792,710,280	60,792,710,185,4	94,6
10	607,927,102,274	607,927,101,854,0	6,079,271,018,540,3	- 246,3
10	60,792,710,185,947	60,792,710,185,402,7	544,3
10	607,927,101,854,103

$R\; (x)\; \{\backslash \; displaystyle\; R\; (x)\}$меняет знак бесконечно часто, поскольку $x\; \{\backslash \; displaystyle\; x\}$стремится к бесконечности.

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

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

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

$\prod \; n\; =\; 0\; \infty \; (pn\; +\; 1)\; an,\; an\; \in \; \{0,\; 1\},\; и\; pn\; является\; n-м\; простым\; числом,\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{\; n\; =\; 0\}\; ^\; \{\backslash \; infty\}\; (p\_\; \{n\; +\; 1\})\; ^\; \{a\_\; \{n\}\},\; a\_\; \{n\}\; \backslash \; in\; \backslash \; lbrace\; 0,1\; \backslash \; rbrace,\; \{\backslash \; text\; \{и\}\}\; p\_\; \{n\}\; \{\backslash \; text\; \{-\; это\}\}\; n\; \{\backslash \; text\; \{th\; prime\}\},\}$

, тогда мы можем взять эти $an\; \{\backslash \; displaystyle\; a\_\; \{n\}\}$и использовать их как биты в двоичном числе с кодировкой

$\sum \; n\; =\; 0\; \infty \; an\; 2\; n.\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \{a\_\; \{n\}\}\; \backslash \; 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.)

Erdős Гипотеза без квадратов

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

$(2\; nn)\; \{\backslash \; displaystyle\; \{2n\; \backslash \; choose\; n\}\}$

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

Squarefree core

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

$coret\; (pe)\; =\; pe\; mod\; t.\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{core\}\; \_\; \{t\}\; (p\; ^\; \{e\})\; =\; p\; ^\; \{e\; \{\backslash \; bmod\; \{t\}\}\}.\}$

Набор значений $core\; 2\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{core\}\; \_\; \{2\}\}$, в частности, являются целыми числами без квадратов. Их производящие функции Дирихле равны

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

представителями OEIS являются OEIS : A007913 (t = 2), OEIS : A050985 (t = 3) и OEIS : A053165 (t = 4).

Примечания

1. ^Adleman, Leonard M.; Маккарли, Кевин С. "Открытые проблемы теоретико-числовой сложности, II". Конспект лекций по информатике: 9. CiteSeerX 10.1.1.48.4877.
2. ^Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (1 сентября 2004 г.). «ПРИМЕР находится в P» (PDF). Анналы математики. 160 (2): 781–793. doi : 10.4007 / annals.2004.160.781. ISSN 0003-486X. MR 2123939. Zbl 1071.11070.
3. ^Ричардс, Челси (2009). Алгоритмы факторизации бесквадратных многочленов по конечным полям (PDF) (магистерская диссертация). Канада: Университет Саймона Фрейзера.
4. ^Вальфис, А. (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie. Берлин: VEB Deutscher Verlag der Wissenschaften.
5. ^Цзя, Чао Хуа. «Распределение бесквадратных чисел», Science in China Series A: Mathematics 36 : 2 (1993), pp. 154–169. Цитируется в Pappalardi 2003, Исследование k-свободы ; также см. Каниника Синха, «Средние порядки некоторых арифметических функций », Журнал Математического общества Рамануджана 21 : 3 (2006), стр. 267–277.
6. ^Лю, H.-Q. (2016). «О распределении бесквадратных чисел». Журнал теории чисел. 159 : 202–222. doi : 10.1016 / j.jnt.2015.07.013.
7. ^Родитель, Д. П. (1984). Упражнения по теории чисел. Проблемные книги по математике. Springer-Verlag Нью-Йорк. DOI : 10.1007 / 978-1-4757-5194-9. ISBN 978-1-4757-5194-9.
8. ^Майкл, Филасета; Огнян, Трифонов (1992). «О промежутках между бесквадратными числами II». J. London Math. Soc. (2) 45: 215–221.
9. ^Эндрю, Гранвиль (1998). «ABC позволяет нам считать без квадрата». Int. Математика. Res. Уведомления. 1998 (19): 991–1009. дои : 10.1155 / S1073792898000592.
10. ^Минору, Танака. «Эксперименты по распределению бесквадратных чисел».
11. ^Андраш Шаркози. О делителях биномиальных коэффициентов, I. J. Теория чисел 20 (1985), вып. 1, 70–80.
12. ^Оливье Рамаре и Эндрю Гранвиль. Явные оценки экспоненциальных сумм и редкости бесквадратных биномиальных коэффициентов. Математика 43 (1996), нет. 1, 73–107

Ссылки

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