Гипотеза Кармайкла о полной функции

В математике гипотеза о тотент-функции Кармайкла касается множественности значений тотент-функции Эйлера φ ( n ), которая подсчитывает количество целых чисел, меньших и взаимно простых с n . В нем говорится, что для каждого n существует хотя бы еще одно целое число m ≠ n такое, что φ ( m ) = φ ( n ). Роберт Кармайкл впервые высказал эту гипотезу в 1907 году, но скорее как теорему, чем как гипотезу. Однако его доказательство было ошибочным, и в 1922 году он отказался от своего утверждения и заявил, что гипотеза является открытой проблемой .

Примеры

Функция тотента φ ( n ) равна 2, когда n является одним из трех значений 3, 4 и 6. Таким образом, если мы возьмем любое из этих трех значений в качестве n , то можно использовать любое из двух других значений. как m, для которого φ ( m ) = φ ( n ).

Точно так же тотент равен 4, когда n является одним из четырех значений 5, 8, 10 и 12, и равен 6, когда n является одним из четырех значений 7, 9, 14 и 18. В каждом В этом случае существует более одного значения n, имеющего одно и то же значение φ ( n ).

Гипотеза утверждает, что это явление повторяющихся значений справедливо для каждого n .

к	числа n такие, что φ ( n ) = k (последовательность A032447 в OEIS )	количество таких n (последовательность A014197 в OEIS )
1	1, 2	2
2	3, 4, 6	3
4	5, 8, 10, 12	4
6	7, 9, 14, 18	4
8	15, 16, 20, 24, 30	5
10	11, 22	2
12	13, 21, 26, 28, 36, 42	6
16	17, 32, 34, 40, 48, 60	6
18	19, 27, 38, 54	4
20	25, 33, 44, 50, 66	5
22	23, 46	2
24	35, 39, 45, 52, 56, 70, 72, 78, 84, 90	10
28	29, 58	2
30	31, 62	2
32	51, 64, 68, 80, 96, 102, 120	7
36	37, 57, 63, 74, 76, 108, 114, 126	8
40	41, 55, 75, 82, 88, 100, 110, 132, 150	9
42	43, 49, 86, 98	4
44	69, 92, 138	3
46	47, 94	2
48	65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210	11
52	53, 106	2
54	81, 162	2
56	87, 116, 174	3
58	59, 118	2
60	61, 77, 93, 99, 122, 124, 154, 186, 198	9
64	85, 128, 136, 160, 170, 192, 204, 240	8
66	67, 134	2
70	71, 142	2
72	73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270	17

Нижние границы

очень высокие нижние оценки У гипотезы Кармайкла , которые относительно легко определить. Сам Кармайкл доказал, что любой контрпример к его гипотезе (то есть значение n такое, что φ( n ) отличается от долей всех других чисел) должен быть не менее 10 ³⁷ , а Виктор Клее расширил этот результат до 10 ⁴⁰⁰ . Нижняя граница $10^{10^{7}}$было дано Шлафли и Вагоном, а нижняя граница $10^{10^{10}}$ был определен Кевином Фордом в 1998 году.

Вычислительная техника, лежащая в основе этих нижних оценок, зависит от некоторых ключевых результатов Кли, которые позволяют показать, что наименьший контрпример должен делиться на квадраты простых чисел, делящих его общее значение. Из результатов Клее следует, что 8 и простые числа Ферма (простые числа вида 2 ^к + 1) исключая 3, не делите наименьший контрпример. Следовательно, доказательство гипотезы эквивалентно доказательству того, что гипотеза верна для всех целых чисел, соответствующих 4 (по модулю 8).

Другие результаты

Форд также доказал, что если существует контрпример к гипотезе, то положительная пропорция (в смысле асимптотической плотности) целых чисел также является контрпримером.

Хотя эта гипотеза широко распространена, Карл Померанс дал достаточное условие для того, чтобы целое число n было контрпримером к гипотезе ( Pomerance 1974 ). Согласно этому условию, n является контрпримером, если для каждого простого числа p такого, что p − 1 делит φ ( n ), p ² делит n . Однако Померанс показал, что существование такого целого числа крайне маловероятно. По сути, можно показать, что если все первые k простых чисел p, конгруэнтных 1 (mod q ) (где q — простое число), меньше q ^{к +1} , то такое целое число будет делиться на все простые числа и, следовательно, не может существовать. В любом случае доказательство того, что контрпример Померанса не существует, далеко от доказательства гипотезы Кармайкла. Однако если он существует, то, как утверждает Форд, существует бесконечно много контрпримеров.

Другой способ сформулировать гипотезу Кармайкла состоит в том, что если A ( f ) обозначает количество натуральных чисел n, для которых φ ( n ) = f , тогда A ( f ) никогда не может равняться 1. Соответственно, Вацлав Серпинский предположил, что каждое положительное целое число, отличное от 1, встречается как значение A ( f ), гипотеза, доказанная в 1999 году Кевином Фордом.

Ссылки

• Кармайкл, Р.Д. -функции Эйлера (1907), «О φ », Бюллетень Американского математического общества , 13 (5): 241–243, doi : 10.1090/S0002-9904-1907-01453-2 , MR   1558451 .
• Кармайкл, Р.Д. -функции Эйлера (1922), «Заметка о φ », Бюллетень Американского математического общества , 28 (3): 109–110, doi : 10.1090/S0002-9904-1922-03504-5 , MR   1560520 .
• Форд, К. (1999), «Число решений φ ( x ) = m », Annals of Mathematics , 150 (1): 283–311, doi : 10.2307/121103 , JSTOR   121103 , MR   1715326 , Zbl   0978.11053 .
• Гай, Ричард К. (2004), Нерешенные проблемы теории чисел (3-е изд.), Springer-Verlag , B39, ISBN  978-0-387-20860-2 , Збл   1058.11001 .
• Клее, В.Л. младший (1947), «О гипотезе Кармайкла», Бюллетень Американского математического общества , 53 (12): 1183–1186, doi : 10.1090/S0002-9904-1947-08940-0 , MR   0022855 , Збл   0035.02601 .
• Померанс, Карл (1974), «О гипотезе Кармайкла» (PDF) , Proceedings of the American Mathematical Society , 43 (2): 297–298, doi : 10.2307/2038881 , JSTOR   2038881 , Zbl   0254.10009 .
• Шандор, Йожеф; Крстичи, Борислав (2004), Справочник по теории чисел II , Дордрехт: Kluwer Academic, стр. 228–229, ISBN  978-1-4020-2546-4 , Збл   1079.11001 .
• Шлафли, А.; Вагон, С. (1994), «Гипотеза Кармайкла о функции Эйлера справедлива ниже 10 ^10,000,000 ", Математика вычислений , 63 (207): 415–419, doi : 10.2307/2153585 , JSTOR   2153585 , MR   1226815 , Zbl   0801.11001 .

Внешние ссылки

• Вайсштейн, Эрик В. , «Гипотеза Кармайкла о полной функции» , MathWorld