В математике , бесквадратное целое (или бесквадратное целое ) является целым числом , которое является делимым на не идеальном квадрате , кроме 1. То есть, его простые множители имеют ровно один фактор для каждого простого , который появляется в нем. Например, 10 = 2 5 бесквадратное, а 18 = 2 ⋅ 3 ⋅ 3 - нет, потому что 18 делится на 9 = 3 2 . Наименьшие положительные числа без квадратов:
Факторизация без квадратов
Каждое положительное целое число n может быть уникальным образом разложено на множители как
где отличными от единицы являются целые числа без квадратов, которые попарно взаимно просты .
Это называется факторизацией числа n без квадратов .
Позволять
- разложение числа n на простые множители , где p j - различные простые числа . Тогда факторы бесквадратной факторизации определяются как
Целое число бесквадратично тогда и только тогда, когда для всех i > 1 . Целое число больше единицы является k- й степенью другого целого числа тогда и только тогда, когда k является делителем всех i таких, что
Использование факторизации целых чисел без квадратов ограничено тем фактом, что ее вычисление так же сложно, как вычисление факторизации простых чисел. Точнее, каждый известный алгоритм вычисления факторизации без квадратов вычисляет также разложение на простые множители. Это заметное отличие от случая многочленов, для которых могут быть даны те же определения, но в этом случае факторизацию без квадратов не только легче вычислить, чем полную факторизацию, но и это первый шаг всех стандартных алгоритмы факторизации.
Бесквадратные множители целых чисел
Радикал целого числа является его большим площадью свободным от фактора, то естьс обозначениями предыдущего раздела. Целое число свободно от квадратов тогда и только тогда, когда оно равно своему радикалу.
Каждое положительное целое число n может быть представлено уникальным образом как произведение мощного числа (то есть такого целого числа, которое делится на квадрат каждого простого множителя) и целого числа без квадратов, которые взаимно просты . В этой факторизации бесквадратный множитель равен и сильное число
Бесквадратно часть из п являетсякоторый является наибольшим бесквадратным делителем k числа n , взаимно простым с n / k . Часть целого числа без квадратов может быть меньше наибольшего делителя без квадратов, который равен
Любое произвольное положительное целое число n можно уникальным образом представить как произведение квадрата и целого числа без квадратов:
В этой факторизации m - наибольший делитель n, такой что m 2 является делителем n .
Таким образом, есть три бесквадратных фактора, которые естественным образом связаны с каждым целым числом: бесквадратная часть, указанный выше коэффициент k и наибольший бесквадратный фактор. Каждый является фактором следующего. Все легко выводятся из разложения на простые множители или разложения без квадратов: если
- разложение на простые множители и разложение числа n без квадратов , где - различные простые числа, то бесквадратная часть равна
Фактор без квадратов, такой как квадрат, равен
а наибольший бесквадратный множитель равен
Например, если надо Часть без квадратов равна 7 , коэффициент без квадратов, при котором частное является квадратом, составляет 3 ⋅ 7 = 21 , а наибольший коэффициент без квадратов равен 2 ⋅ 3 ⋅ 5 7 = 210 .
Неизвестно ни одного алгоритма для вычисления любого из этих бесквадратных множителей, который был бы быстрее, чем вычисление полного разложения на простые множители. В частности, не существует известного алгоритма с полиномиальным временем для вычисления части целого числа без квадратов или даже для определения того, является ли целое число бесквадратным. [1] Напротив, для проверки простоты известны алгоритмы с полиномиальным временем . [2] Это главное различие между арифметикой целых чисел и арифметикой одномерных многочленов , поскольку алгоритмы с полиномиальным временем известны для факторизации многочленов без квадратов (короче говоря, наибольший бесквадратный множитель многочлена является его частным по наибольшему общему делителю многочлена и его формальной производной ). [3]
Эквивалентные характеристики
Положительное целое число п бесквадратно тогда и только тогда , когда в простые множители из п , не простой множитель не происходит с показателем больше единицы. Другой способ заявить то же самое состоит в том, что для любого простого множителя p числа n простое число p не делит n / p равномерно . Кроме того, п бесквадратно тогда и только тогда , когда в каждом разложении п = аб , коэффициенты а и б являются взаимно простыми . Непосредственным результатом этого определения является то, что все простые числа свободны от квадратов.
Положительное целое число п бесквадратно тогда и только тогда , когда все абелевы группы из порядка п являются изоморфными , что имеет место тогда и только тогда , когда любая такая группа является циклической . Это следует из классификации конечно порожденных абелевых групп .
Целое число п бесквадратно тогда и только тогда , когда фактор - кольцо Z / п Z (см модульной арифметики ) представляет собой продукт из полей . Это следует из китайской теоремы об остатках и того факта, что кольцо вида Z / k Z является полем тогда и только тогда, когда k простое число.
Для каждого положительного целого числа n множество всех положительных делителей n становится частично упорядоченным множеством, если мы используем делимость как отношение порядка. Этот частично упорядоченный набор всегда представляет собой распределительную решетку . Это булева алгебра тогда и только тогда, когда n бесквадратично.
Положительное целое число n свободно от квадратов тогда и только тогда, когда μ ( n ) ≠ 0, где μ обозначает функцию Мёбиуса .
Серия Дирихле
Абсолютное значение функции Мёбиуса - это индикаторная функция для целых чисел без квадратов, то есть | μ ( n ) | равно 1, если n бесквадратное, и 0, если это не так. Ряд Дирихле этой функции индикаторного
где ζ ( s ) - дзета-функция Римана . Это следует из произведения Эйлера
где произведения берутся по простым числам.
Распределение
Пусть Q ( x ) обозначает количество целых чисел без квадратов от 1 до x ( OEIS : A013928 смещение индекса на 1). Для больших n 3/4 натуральных чисел меньше n не делятся на 4, 8/9 этих чисел не делятся на 9 и так далее. Поскольку эти отношения удовлетворяют мультипликативному свойству (это следует из китайской теоремы об остатках ), мы получаем приближение:
Этот аргумент можно сделать строгим для получения оценки (используя большую нотацию 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 , половина всех положительных целых чисел минус конечное число должны быть неквадратными. -бесквадратный и, следовательно,
- для некоторой постоянной C ,
вопреки приведенной выше асимптотической оценке для .
Существуют последовательности последовательных целых чисел произвольной длины, не свободных от квадратов. В самом деле, если n удовлетворяет одновременному сравнению
для различных простых чисел , то каждый делится на p i 2 . [8] С другой стороны, указанная выше оценкаозначает, что для некоторой константы c всегда существует целое число без квадратов между x идля положительного x . Более того, элементарный аргумент позволяет заменить от [9] Гипотеза ABC позволила бы. [10]
Таблица а также
В таблице показано, как а также сравните в степени 10.
, также обозначается как .
10 7 6.1 0,9 10 2 61 60,8 0,2 10 3 608 607,9 0,1 10 4 6 083 6 079,3 3,7 10 5 60 794 60 792,7 1.3 10 6 607 926 607 927,1 - 1,3 10 7 6 079 291 6 079 271,0 20,0 10 8 60 792 694 60 792 710,2 - 16,2 10 9 607 927 124 607 927 101,9 22,1 10 10 6 079 270 942 6 079 271 018,5 - 76,5 10 11 60 792 710 280 60 792 710 185,4 94,6 10 12 607 927 102 274 607 927 101 854,0 420,0 10 13 6 079 271 018 294 6 079 271 018 540,3 - 246,3 10 14 60 792 710 185 947 60 792 710 185 402,7 544,3 10 15 607 927 101 854 103 607 927 101 854 027,0 76,0
меняет знак бесконечно часто, как стремится к бесконечности. [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 .)
Гипотеза Эрдёша о бесквадратности
Центральный биномиальный коэффициент
никогда не бесквадратно для п > 4. Это было доказано в 1985 для всех достаточно больших целых чисел Андрасом Саркози , [12] и для всех целых чисел> 4 в 1996 году Оливье Рамар и Эндрю Гранвиль . [13]
Ядро без квадратов
Мультипликативная функция определен для отображения положительных целых чисел n в t -свободные числа путем уменьшения показателей степени в представлении простой степени по модулю t :
Набор значений , в частности, целые числа без квадратов. Их производящие функции Дирихле :
- .
Представителями OEIS являются OEIS : A007913 ( t = 2), OEIS : A050985 ( t = 3) и OEIS : A053165 ( t = 4).
Заметки
- ^ Адлеман, Леонард М .; Маккарли, Кевин С. "Открытые проблемы теоретико-числовой сложности, II". Конспект лекций по информатике : 9. CiteSeerX 10.1.1.48.4877 .
- ^ Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (1 сентября 2004 г.). "ПРИМЕР в П" (PDF) . Анналы математики . 160 (2): 781–793. DOI : 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 .
- ^ Цзя, Чао Хуа. «Распределение бесквадратных чисел», Science in China Series A: Mathematics 36 : 2 (1993), pp. 154–169. Цитируется в Pappalardi 2003, A Survey on k -freeness ; также см. Каниника Синха, « Средние порядки некоторых арифметических функций », Журнал Математического общества Рамануджана, 21 : 3 (2006), стр. 267–277.
- ^ Лю, H.-Q. (2016). «О распределении бесквадратных чисел» . Журнал теории чисел . 159 : 202–222. DOI : 10.1016 / j.jnt.2015.07.013 .
- ^ Linfoot, EH ; Эвелин, CJA (1929). «Об одной проблеме аддитивной теории чисел» . Mathematische Zeitschrift . 30 : 443–448.
- ^ Родитель, Д.П. (1984). Упражнения по теории чисел . Проблемные книги по математике. Springer-Verlag New York. DOI : 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. DOI : 10.1155 / S1073792898000592 .
- ^ Минору, Танака. «Эксперименты по распределению бесквадратных чисел» .
- ^ Андраш Шаркози. О делителях биномиальных коэффициентов, IJ Number Theory 20 (1985), no. 1, 70–80.
- ^ Оливье Рамаре и Эндрю Гранвиль. Явные оценки экспоненциальных сумм и редкости бесквадратных биномиальных коэффициентов. Математика 43 (1996), нет. 1, 73–107
Рекомендации
- Шапиро, Гарольд Н. (1983). Введение в теорию чисел . Издательство Оксфордского университета в Дувре. ISBN 978-0-486-46669-9.
- Гранвиль, Эндрю; Рамаре, Оливье (1996). «Явные оценки экспоненциальных сумм и редкости бесквадратных биномиальных коэффициентов». Математика . 43 : 73–107. CiteSeerX 10.1.1.55.8 . DOI : 10.1112 / S0025579300011608 . Руководство по ремонту 1401709 . Zbl 0868.11009 .
- Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag . ISBN 978-0-387-20860-2. Zbl 1058.11001 .