Целое число без квадратов - Square-free integer

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 )

Факторизация без квадратов

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

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

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

Это называется бесквадратная факторизация из $п$ .

Позволять

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

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

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

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

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

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

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

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

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

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

{displaystyle n = m ^ {2} k}

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

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

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

разложение на простые множители и разложение без квадратов $п$ , куда ${displaystyle p_ {1}, ldots, p_ {h}}$ - различные простые числа, то бесквадратная часть равна

{displaystyle prod _ {e_ {i} = 1} p_ {i} = q_ {1},}

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

{displaystyle prod _ {e_ {i} {ext {odd}}} p_ {i} = prod _ {i {ext {odd}}} q_ {i},}

а наибольший бесквадратный множитель равен

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

Например, если ${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.}$ Часть без квадратов $7$ , бесквадратный множитель такой, что фактор является квадратом, равен $3 \cdot 7 = 21$ , а наибольший бесквадратный множитель равен $2 \cdot 3 \cdot 5 \cdot 7 = 210$ .

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

Эквивалентные характеристики

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

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

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

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

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

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

Абсолютное значение функции Мёбиуса - это индикаторная функция для целых чисел, свободных от квадратов, то есть $| μ (п) |$ равно 1, если $п$ без квадратов, и 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(Икс) обозначают количество целых чисел без квадратов от 1 до Икс (OEIS: A013928 индекс сдвига на 1). Для больших п, 3/4 натуральных чисел меньше п не делятся на 4, 8/9 из этих чисел не делятся на 9 и так далее. Поскольку эти отношения удовлетворяют мультипликативное свойство (это следует из Китайская теорема об остатках ), получаем приближение:

{displaystyle {egin {выравнивается} Q (x) & приблизительно xprod _ {p {ext {prime}}} left (1- {frac {1} {p ^ {2}}} ight) = xprod _ {p {ext { prime}}} {frac {1} {(1- {frac {1} {p ^ {2}}}) ^ {- 1}}} & приблизительно xprod _ {p {ext {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 {выровнено }}}

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

{displaystyle Q (x) = {frac {6x} {pi ^ {2}}} + Oleft ({sqrt {x}} ight).}

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

{displaystyle Q (x) = sum _ {nleq x} sum _ {d ^ {2} mid n} mu (d) = sum _ {dleq x} mu (d) sum _ {nleq x, d ^ {2} mid n} 1 = сумма _ {dleq x} mu (d) leftlfloor {frac {x} {d ^ {2}}} ightfloor;}

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

{displaystyle {egin {align} Q (x) & = sum _ {dleq {sqrt {x}}} mu (d) leftlfloor {frac {x} {d ^ {2}}} ightfloor = sum _ {dleq {sqrt {x}}} {frac {xmu (d)} {d ^ {2}}} + O (сумма _ {dleq {sqrt {x}}} 1) = xsum _ {dleq {sqrt {x}}} { frac {mu (d)} {d ^ {2}}} + O ({sqrt {x}}) & = xsum _ {d} {frac {mu (d)} {d ^ {2}}} + Oleft (xsum _ {d> {sqrt {x}}} {frac {1} {d ^ {2}}} + {sqrt {x}} ight) = {frac {x} {zeta (2)}} + O ({sqrt {x}}). Конец {выровнено}}}

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

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

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

Под Гипотеза Римана, член ошибки можно свести к^[5]

{displaystyle Q (x) = {frac {x} {zeta (2)}} + Oleft (x ^ {17/54 + varepsilon} ight) = {frac {6} {pi ^ {2}}} x + Oleft (x ^ {17/54 + varepsilon} ight).}

Недавно (2015 г.) член ошибки был сокращен до^[6]

{displaystyle Q (x) = {frac {6} {pi ^ {2}}} x + Oleft (x ^ {11/35 + varepsilon} ight).}

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

{displaystyle lim _ {x o infty} {frac {Q (x)} {x}} = {frac {6} {pi ^ {2}}} примерно 0.6079}

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

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

{displaystyle Q (x, n) = {frac {x} {sum _ {k = 1} ^ {infty} {frac {1} {k ^ {n}}}}}} + Oleft ({sqrt [{n} ] {x}} ight) = {frac {x} {zeta (n)}} + Oleft ({sqrt [{n}] {x}} ight).}

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

{displaystyle Q (x) leq {frac {x} {2}} + C}

для некоторой постоянной C,

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

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

{displaystyle nequiv -i {pmod {p_ {i} ^ {2}}} qquad (i = 1,2, ldots, l)}

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

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

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

${displaystyle R (x) = Q (x) - {гидроразрыв {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²	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	420.0
10¹³	6,079,271,018,294	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	607,927,101,854,027.0	76.0

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

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

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

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

{displaystyle prod _ {n = 0} ^ {infty} (p_ {n + 1}) ^ {a_ {n}}, a_ {n} in lbrace 0,1brace, {ext {and}} p_ {n} { ext {это}} n {ext {простое число}},}

тогда мы можем взять эти ${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 выберите n}}

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

Ядро без квадратов

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

{displaystyle mathrm {core} _ {t} (p ^ {e}) = p ^ {e {mod {t}}}.}

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

{displaystyle sum _ {ngeq 1} {frac {mathrm {core} _ {t} (n)} {n ^ {s}}} = {frac {zeta (ts) zeta (s-1)} {zeta (ts -t)}}}

.

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

Примечания

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

Наборы целых чисел на основе делимости
Обзор	Целочисленная факторизация Делитель Унитарный делитель Функция делителя главный фактор Основная теорема арифметики
Формы факторизации	основной Композитный Полупростой Пронический Сфенический Без квадратов Мощный Идеальная мощность Ахиллес Гладкий Обычный Грубый Необычный
Суммы ограниченных делителей	Идеально Практически идеально Квазидеальный Умножить идеально Полусовершенный Гиперсовершенство Суперсовершенный Унитарное совершенное Би-унитарное умножение совершенное Полусовершенный Практичный Эрдеш – Николас
Со многими делителями	Обильный Первобытный изобилие Очень много Сверхизбыток Колоссально обильный Сильно композитный Превосходный высококомпозитный Странный
Последовательность аликвот -связанные с	Неприкасаемый Дружный Общительный Обрученный
Основание -зависимый	Равноцилиндровый Экстравагантный Экономный Харшад Полиделимый Смит
Другие наборы	Арифметика Недостаточный Дружелюбный Одиночный Возвышенный Гармонический дивизор Декарт Возможность рефакторинга Суперсовершенный

Целое число без квадратов - Square-free integer

Содержание

Факторизация без квадратов

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

Эквивалентные характеристики

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

Распределение

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

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

Гипотеза эрдёша о бесквадратности

Ядро без квадратов

Примечания

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

Целое число без квадратов - Square-free integer

Факторизация без квадратов

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

Эквивалентные характеристики

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

Распределение

Таблица Q ( Икс ) , 6 π 2 Икс {displaystyle Q (x), {frac {6} {pi ^ {2}}} x} и р ( Икс ) {displaystyle R (x)}

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

Гипотеза эрдёша о бесквадратности

Ядро без квадратов

Примечания

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

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