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

В математике , бесквадратное целое (или бесквадратное целое ) является целым числом , которое является делимым на не идеальном квадрате , кроме 1. То есть, его простые множители имеют ровно один фактор для каждого простого , который появляется в нем. Например, 10 = 2 5 бесквадратное, а 18 = 2 ⋅ 3 ⋅ 3 - нет, потому что 18 делится на 9 = 3 2 . Наименьшие положительные числа без квадратов:

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 может быть уникальным образом разложено на множители как

где отличные от единицы целые числа без квадратов, попарно взаимно просты .

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

Позволять

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

Целое число свободно от квадратов тогда и только тогда, когда для всех i > 1 . Целое число больше единицы является k- й степенью другого целого числа тогда и только тогда, когда k является делителем всех i таких, что

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

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

Радикал целого числа является его большим площадью свободной от фактора, то есть с обозначениями предыдущего параграфа. Целое число свободно от квадратов тогда и только тогда, когда оно равно своему радикалу.

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

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

Любое произвольное положительное целое число 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 , можно показать

Поскольку кратное 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 . [7] С другой стороны, вышеупомянутая оценка означает, что для некоторой константы c всегда существует целое число без квадратов между x и положительным x . Более того, элементарное рассуждение позволяет нам заменить на [8] . Гипотеза ABC позволила бы . [9]

Таблица и [ править ]

В таблице показано, как и сравнить при степенях 10.

, также обозначается как .

меняет знак бесконечно часто, поскольку стремится к бесконечности. [10]

Абсолютная величина удивительно мала по сравнению с .

Кодирование в виде двоичных чисел [ править ]

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

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

Число 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 для всех достаточно больших целых чисел Андрасом Саркози , [11] и для всех целых чисел> 4 в 1996 году Оливье Рамар и Эндрю Гранвиль . [12]

Ядро Squarefree [ править ]

Мультипликативная функция определена для отображения положительных целых чисел п к т -Free чисел пути уменьшения экспоненты в простом представлении мощности по модулю т :

Набор значений , в частности, представляет собой целые числа без квадратов. Их производящие функции Дирихле :

.

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

Заметки [ править ]

  1. ^ Адлеман, Леонард М .; Маккарли, Кевин С. "Открытые проблемы теоретико-числовой сложности, II". Конспект лекций по информатике : 9. CiteSeerX  10.1.1.48.4877 .
  2. ^ Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (1 сентября 2004 г.). "ПРИМЕР в П" (PDF) . Анналы математики . 160 (2): 781–793. DOI : 10.4007 / анналы.2004.160.781 . ISSN 0003-486X . Руководство по ремонту 2123939 . Zbl 1071.11070 .    
  3. Перейти ↑ Richards, Chelsea (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, A Survey on k -freeness ; также см. Каниника Синха, « Средние порядки некоторых арифметических функций », Журнал Математического общества Рамануджана, 21 : 3 (2006), стр. 267–277.
  6. ^ Лю, H.-Q. (2016). «О распределении бесквадратных чисел» . Журнал теории чисел . 159 : 202–222. DOI : 10.1016 / j.jnt.2015.07.013 .
  7. ^ Родитель, DP (1984). Упражнения по теории чисел . Проблемные книги по математике. Springer-Verlag New York. 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. DOI : 10.1155 / S1073792898000592 .
  10. Минору, Танака. «Эксперименты по распределению бесквадратных чисел» .
  11. ^ Андраш Шаркози. О делителях биномиальных коэффициентов, IJ Number Theory 20 (1985), no. 1, 70–80.
  12. ^ Оливье Рамаре и Эндрю Гранвиль. Явные оценки экспоненциальных сумм и редкости бесквадратных биномиальных коэффициентов. Математика 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 .