В математике целое число без квадратов (или целое число без квадратов ) — это целое число , которое не делится ни на одно квадратное число, кроме 1. То есть его простая факторизация имеет ровно один множитель для каждого простого числа, которое в нем встречается. Например, 10 = 2 ⋅ 5 не содержит квадратов, а 18 = 2 ⋅ 3 ⋅ 3 — нет, поскольку 18 делится на 9 = 3 2 . Наименьшие положительные числа без квадратов – это
Каждое положительное целое число может быть факторизовано уникальным способом, поскольку отличными от одного являются целые числа без квадратов, которые попарно взаимно просты . Это называется бесквадратной факторизацией n .
Чтобы построить факторизацию без квадратов, пусть будет факторизация простых чисел , где - различные простые числа . Тогда факторы бесквадратной факторизации определяются как
Целое число является свободным от квадратов тогда и только тогда, когда для всех . Целое число больше единицы является четвертой степенью другого целого числа тогда и только тогда, когда оно является делителем всех таких, что
Использование бесквадратной факторизации целых чисел ограничено тем фактом, что ее вычисление столь же сложно, как и вычисление простой факторизации. Точнее, каждый известный алгоритм вычисления факторизации без квадратов вычисляет также и простую факторизацию. Это заметное отличие от случая многочленов , для которых можно дать те же определения, но в этом случае факторизацию без квадратов не только легче вычислить, чем полную факторизацию, но это первый шаг всех стандартных методов. алгоритмы факторизации.
Радикал целого числа — это его наибольший безквадратный множитель, то есть в обозначениях предыдущего раздела. Целое число является свободным тогда и только тогда, когда оно равно своему радикалу.
Каждое положительное целое число может быть представлено уникальным образом как произведение мощного числа (то есть целого числа, которое делится на квадрат каждого простого множителя) и целого числа без квадратов, которые являются взаимно простыми . В этой факторизации бесквадратный фактор равен, а мощное число равно
Часть , свободная от квадратов, является наибольшим делителем, свободным от квадратов , который взаимно прост с . Часть целого числа без квадратов может быть меньше наибольшего делителя без квадратов, который равен
Любое произвольное положительное целое число может быть представлено уникальным образом как произведение квадрата и целого числа без квадратов: в этой факторизации является наибольшим делителем такого числа, которое является делителем .
Таким образом, есть три множителя без квадратов, которые естественным образом связаны с каждым целым числом: часть без квадратов, указанный выше множитель и наибольший множитель без квадратов. Каждый из них является фактором следующего. Все они легко выводятся из простой факторизации или факторизации без квадратов: если - факторизация простых чисел и факторизация без квадратов , где - различные простые числа, то часть без квадратов равна Фактору без квадратов, такому как частное квадрат равен , а наибольший безквадратный фактор равен
Например, если у вас есть Часть без квадратов равна 7 , коэффициент без квадратов, такой что частное является квадратом, равен 3 ⋅ 7 = 21 , а наибольший множитель без квадратов равен 2 ⋅ 3 ⋅ 5 ⋅ 7 = 210. .
Неизвестен алгоритм для вычисления любого из этих безквадратных факторов, который был бы быстрее, чем вычисление полной факторизации простых чисел. В частности, не существует известного алгоритма с полиномиальным временем для вычисления части целого числа, свободной от квадратов, или даже для определения того, является ли целое число свободным от квадратов. [1] Напротив, для проверки простоты известны алгоритмы с полиномиальным временем . [2] Это основное различие между арифметикой целых чисел и арифметикой одномерных многочленов , поскольку известны алгоритмы с полиномиальным временем для безквадратной факторизации многочленов (короче говоря, наибольший безквадратный множитель полинома есть его частное по наибольшему общему делителю многочлена и его формальной производной ). [3]
Положительное целое число является свободным от квадратов тогда и только тогда, когда при разложении на простые множители ни один простой множитель не встречается с показателем степени больше единицы. Другой способ сказать то же самое состоит в том, что для каждого простого делителя простое число не делится поровну . Также является свободным от квадратов тогда и только тогда, когда в каждой факторизации факторы и взаимно просты . Непосредственным результатом этого определения является то, что все простые числа не содержат квадратов.
Положительное целое число является свободным от квадратов тогда и только тогда, когда все абелевы группы порядка изоморфны , что имеет место тогда и только тогда, когда любая такая группа является циклической . Это следует из классификации конечно порожденных абелевых групп .
Целое число является свободным от квадратов тогда и только тогда, когда фактор -кольцо (см. модульную арифметику ) является произведением полей . Это следует из китайской теоремы об остатках и того факта, что кольцо вида является полем тогда и только тогда, когда оно простое.
Для каждого положительного целого числа набор всех положительных делителей становится частично упорядоченным набором, если мы используем делимость в качестве отношения порядка. Это частично упорядоченное множество всегда является дистрибутивной решеткой . Это булева алгебра тогда и только тогда, когда она свободна от квадратов.
Целое положительное число является свободным от квадратов тогда и только тогда , когда , где обозначает функцию Мёбиуса .
Абсолютное значение функции Мёбиуса является индикаторной функцией для целых чисел без квадратов, то есть | μ ( п ) | равно 1, если n не содержит квадратов, и 0, если нет. Ряд Дирихле этой индикаторной функции равен
где ζ ( s ) – дзета-функция Римана . Это следует из произведения Эйлера
где произведения берутся по простым числам.
Пусть Q ( x ) обозначает количество целых чисел без квадратов между 1 и x ( OEIS : A013928 индекс сдвига на 1). При больших n 3/4 натуральных чисел меньше n не делятся на 4, 8/9 этих чисел не делятся на 9 и так далее. Поскольку эти отношения удовлетворяют мультипликативному свойству (это следует из китайской теоремы об остатках ), мы получаем приближение:
Этот аргумент можно сделать строгим для получения оценки (используя обозначение big O )
Набросок доказательства: приведенная выше характеристика дает
учитывая, что последнее слагаемое равно нулю для , получаем, что
Используя самую большую известную область дзета-функции Римана без нуля, Арнольд Уолфис улучшил аппроксимацию до [4]
для некоторой положительной константы c .
Согласно гипотезе Римана , член ошибки может быть уменьшен до [5]
В 2015 году член ошибки был дополнительно уменьшен (с учетом гипотезы Римана) до [6]
Следовательно, асимптотическая/ естественная плотность чисел без квадратов равна
Следовательно, более 3/5 целых чисел не содержат квадратов.
Аналогично, если Q ( x , n ) обозначает количество n -свободных целых чисел (например, целые числа без 3 - целые числа без кубов) между 1 и x , можно показать [7]
Поскольку число, кратное 4, должно иметь квадратичный коэффициент 4=2 2 , не может случиться так, что четыре последовательных целых числа не будут содержать квадратов. С другой стороны, существует бесконечно много целых чисел n , для которых 4 n +1, 4 n +2, 4 n +3 свободны от квадратов. В противном случае, учитывая, что 4 n и по крайней мере одно из 4 n +1, 4 n +2, 4 n +3 из четырех могут быть несвободными от квадратов для достаточно больших n , половина всех натуральных чисел минус конечное число не должна быть несвободной. -свободный от квадратов и, следовательно,
вопреки приведенной выше асимптотической оценке для .
Существуют последовательности последовательных целых чисел, не свободных от квадратов, произвольной длины. Действительно, если n удовлетворяет одновременному сравнению
для различных простых чисел каждое из них делится на pi 2 . [8] С другой стороны, из вышеупомянутой оценки следует, что для некоторой константы c всегда существует целое число без квадратов между x и для положительного x . Более того, элементарный аргумент позволяет нам заменить на [9] Гипотеза ABC позволила бы . [10]
В таблице показано, как и (с округлением до одного десятичного знака) сравниваются при степени 10.
, также обозначается как .
меняет знак бесконечно часто, стремясь к бесконечности. [11]
Абсолютное значение удивительно мало по сравнению с .
Если мы представим число без квадратов как бесконечное произведение
тогда мы можем взять их и использовать как биты двоичного числа с кодировкой
Бесквадратное число 42 имеет факторизацию 2 × 3 × 7 или представляет собой бесконечное произведение 2 1 · 3 1 · 5 0 · 7 1 · 11 0 · 13 0 ··· Таким образом, число 42 можно закодировать как двоичную последовательность ...001011
или 11 десятичных чисел. (Двоичные цифры перевернуты по сравнению с порядком в бесконечном произведении.)
Поскольку простая факторизация каждого числа уникальна, то же самое происходит и с каждым двоичным кодированием целых чисел без квадратов.
Обратное также верно. Поскольку каждое положительное целое число имеет уникальное двоичное представление, можно обратить это кодирование вспять, чтобы их можно было декодировать в уникальное целое число без квадратов.
Опять же, например, если мы начнем с числа 42, на этот раз как просто положительное целое число, мы получим его двоичное представление 101010
. Это декодирует как 2 0 · 3 1 · 5 0 · 7 1 · 11 0 · 13 1 = 3 × 7 × 13 = 273.
Таким образом, двоичное кодирование чисел без квадратов описывает биекцию между неотрицательными целыми числами и набором положительных целых чисел без квадратов.
(См. последовательности A019565, A048672 и A064273 в OEIS .)
Центральный биномиальный коэффициент
никогда не является свободным от квадратов при n > 4. Это было доказано в 1985 году для всех достаточно больших целых чисел Андрашем Саркози [12] и для всех целых чисел > 4 в 1996 году Оливье Рамаре и Эндрю Гранвиллем . [13]
Назовем « t -свободным» целое положительное число, делители которого не имеют t -й степени. В частности, целые числа без 2 — это целые числа без квадратов.
Мультипликативная функция отображает каждое положительное целое число n в частное числа n по его наибольшему делителю, который является t -й степенью. То есть,
Целое число является t -свободным, и каждое t -свободное целое число отображается в себя с помощью функции
Производящая функция Дирихле последовательности :
См. также OEIS : A007913 ( t =2), OEIS : A050985 ( t =3) и OEIS : A053165 ( t =4).