Теорема Ламбека–Мозера
О целочисленных разбиениях из монотонных функций

Теорема Ламбека–Мозера — это математическое описание разбиений натуральных чисел на два дополнительных множества . Например, она применяется к разбиению чисел на четные и нечетные или на простые и не простые (единица и составные числа ). Теорема Ламбека–Мозера состоит из двух частей. Одна часть утверждает, что любые две неубывающие целые функции, которые являются обратными в определенном смысле, могут быть использованы для разбиения натуральных чисел на два дополнительных подмножества, а другая часть утверждает, что каждое дополнительное разбиение может быть построено таким образом. Когда известна формула для -го натурального числа в множестве, теорему Ламбека–Мозера можно использовать для получения формулы для -го числа, не входящего в множество. н {\displaystyle n} н {\displaystyle n}

Теорема Ламбека–Мозера относится к комбинаторной теории чисел . Она названа в честь Иоахима Ламбека и Лео Мозера , которые опубликовали ее в 1954 году, [1] и ее следует отличать от несвязанной теоремы Ламбека и Мозера, позднее усиленной Уайлдом, о числе примитивных пифагорейских троек . [2] Она расширяет теорему Рэлея, которая описывает дополнительные пары последовательностей Битти , последовательности округленных кратных иррациональных чисел.

От функций к разделам

Четыре функции , , , и для двух последовательностей Битти 1, 3, 4, 6, ... и 2, 5, 7, 10, ... . Эти последовательности округляют вниз целые кратные и , где — золотое сечение . ф {\displaystyle f} ф ∗ {\displaystyle f^{*}} Ф {\displaystyle F} Ф ∗ {\displaystyle F^{*}} φ {\displaystyle \varphi} φ + 1 {\displaystyle \varphi +1} φ {\displaystyle \varphi}

Пусть будет любой функцией от положительных целых чисел до неотрицательных целых чисел, которая является как неубывающей (каждое значение в последовательности по крайней мере так же велико, как и любое предыдущее значение), так и неограниченной (она в конечном итоге увеличивается после любого фиксированного значения). Последовательность ее значений может пропускать некоторые числа, поэтому она может не иметь обратной функции с теми же свойствами. Вместо этого определите неубывающую и неограниченную целочисленную функцию , которая максимально близка к обратной в том смысле, что для всех положительных целых чисел , Эквивалентно, может быть определена как количество значений, для которых . Из любого из этих определений следует, что . [3] Если две функции и изображены в виде гистограмм , они образуют зеркальные отображения друг друга по диагональной линии . [4] ф {\displaystyle f} ф ( 1 ) , ф ( 2 ) , ф ( 3 ) , … {\displaystyle f(1),f(2),f(3),\точки} ф ∗ {\displaystyle f^{*}} н {\displaystyle n} ф ( ф ∗ ( н ) ) < н ≤ ф ( ф ∗ ( н ) + 1 ) . {\displaystyle f{\bigl (}f^{*}(n){\bigr )}<n\leq f{\bigl (}f^{*}(n)+1{\bigr )}.} ф ∗ ( н ) {\displaystyle f^{*}(н)} х {\displaystyle x} ф ( х ) < н {\displaystyle f(x)<n} ф ∗ ∗ = ф {\displaystyle f^{*}{}^{*}=f} ф {\displaystyle f} ф ∗ {\displaystyle f^{*}} х = у {\displaystyle x=y}

Из этих двух функций и , определяем еще две функции и , от положительных целых чисел до положительных целых чисел, по Тогда первая часть теоремы Ламбека–Мозера утверждает, что каждое положительное целое число встречается ровно один раз среди значений либо , либо . То есть значения, полученные из и значения, полученные из, образуют два дополнительных набора положительных целых чисел. Более того, каждая из этих двух функций отображает свой аргумент в -й член своего набора в разбиении. [3] ф {\displaystyle f} ф ∗ {\displaystyle f^{*}} Ф {\displaystyle F} Ф ∗ {\displaystyle F^{*}} Ф ( н ) = ф ( н ) + н Ф ∗ ( н ) = ф ∗ ( н ) + н {\displaystyle {\begin{align}F(n)&=f(n)+n\\F^{*}(n)&=f^{*}(n)+n\\\end{align}}} Ф {\displaystyle F} Ф ∗ {\displaystyle F^{*}} Ф {\displaystyle F} Ф ∗ {\displaystyle F^{*}} н {\displaystyle n} н {\displaystyle n}

В качестве примера построения разбиения из функции, пусть , функция, которая возводит свой аргумент в квадрат . Тогда ее обратная функция — это функция квадратного корня , ближайшим целочисленным приближением которой (в смысле, используемом для теоремы Ламбека–Мозера) является . Эти две функции дают и Для значений — пронические числа ф ( н ) = н 2 {\displaystyle f(n)=n^{2}} ф ∗ ( н ) = ⌊ н − 1 ⌋ {\displaystyle f^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor } Ф ( н ) = н 2 + н {\displaystyle F(n)=n^{2}+n} Ф ∗ ( н ) = ⌊ н − 1 ⌋ + н . {\displaystyle F^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor +n.} н = 1 , 2 , 3 , … {\displaystyle n=1,2,3,\точки} Ф {\displaystyle F}

2, 6, 12, 20, 30, 42, 56, 72, 90, 110,...

в то время как значения являются Ф ∗ {\displaystyle F^{*}}

1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, ....

Эти две последовательности являются дополнительными: каждое положительное целое число принадлежит ровно одной из них. [4] Теорема Ламбека–Мозера утверждает, что это явление не является специфическим для пронических чисел, а скорее возникает для любого выбора с соответствующими свойствами. [3] ф {\displaystyle f}

От разделов к функциям

Две функции (правые синие стрелки) и (левые красные стрелки), возникающие из разбиения положительных целых чисел на простые (2, 3, 5, 7, ...) и не простые (1, 4, 6, 8, ...). Визуализация на основе метода Энджела. [5] ф {\displaystyle f} ф ∗ {\displaystyle f^{*}}

Вторая часть теоремы Ламбека–Мозера утверждает, что эта конструкция разбиений из обратных функций универсальна, в том смысле, что она может объяснить любое разбиение положительных целых чисел на две бесконечные части. Если и являются любыми двумя дополнительными возрастающими последовательностями целых чисел, можно построить пару функций и , из которых это разбиение может быть получено с помощью теоремы Ламбека–Мозера. Для этого определим и . [3] С = с 1 , с 2 , … {\displaystyle S=s_{1},s_{2},\точки } С ∗ = с 1 ∗ , с 2 ∗ , … {\displaystyle S^{*}=s_{1}^{*},s_{2}^{*},\точки } ф {\displaystyle f} ф ∗ {\displaystyle f^{*}} ф ( н ) = с н − н {\displaystyle f(n)=s_{n}-n} ф ∗ ( н ) = с н ∗ − н {\displaystyle f^{*}(n)=s_{n}^{*}-n}

Одним из простейших примеров, к которым это может быть применено, является разбиение положительных целых чисел на четные и нечетные числа . Функции и должны давать четное или нечетное число, соответственно, поэтому и . Из них выводятся две функции и . Они образуют обратную пару, и разбиение, полученное с помощью теоремы Ламбека–Мозера из этой пары, является просто разбиением положительных целых чисел на четные и нечетные числа. Другое целочисленное разбиение, на злые числа и одиозные числа (по четности двоичного представления ), использует почти те же функции, скорректированные по значениям последовательности Туэ–Морса . [6] Ф ( н ) {\displaystyle F(n)} Ф ∗ ( н ) {\displaystyle F^{*}(н)} н {\displaystyle n} Ф ( н ) = 2 н {\displaystyle F(n)=2n} Ф ∗ ( н ) = 2 н − 1 {\displaystyle F^{*}(n)=2n-1} ф ( н ) = Ф ( н ) − н = н {\displaystyle f(n)=F(n)-n=n} ф ∗ ( н ) = Ф ∗ ( н ) − н = н − 1 {\displaystyle f^{*}(n)=F^{*}(n)-n=n-1}

Формула предела

В той же работе, в которой они доказали теорему Ламбека–Мозера, Ламбек и Мозер предложили метод прямого перехода от , Ф {\displaystyle F} функции, дающей й член множества положительных целых чисел, к , функции, дающей й нечлен , минуя и . Пусть обозначает число значений для , для которых ; это приближение к обратной функции , но (поскольку она использует вместо ) смещено на единицу от типа обратной функции, используемой для определения из . Тогда для любого , является пределом последовательности, что означает, что эта последовательность в конечном итоге становится постоянной, а значение, которое она принимает, когда это происходит, равно . [ 7] н {\displaystyle n} Ф ∗ {\displaystyle F^{*}} н {\displaystyle n} ф {\displaystyle f} ф ∗ {\displaystyle f^{*}} Ф # ( н ) {\displaystyle F^{\#}(н)} х {\displaystyle x} Ф ( х ) ≤ н {\displaystyle F(x)\leq n} Ф {\displaystyle F} ≤ {\displaystyle \leq} < {\стиль_отображения <} ф ∗ {\displaystyle f^{*}} ф {\displaystyle f} н {\displaystyle n} Ф ∗ ( н ) {\displaystyle F^{*}(н)} н , н + Ф # ( н ) , н + Ф # ( н + Ф # ( н ) ) , … , {\displaystyle n,n+F^{\#}(n),n+F^{\#}{\bigl (}n+F^{\#}(n){\bigr )},\dots ,} Ф ∗ ( н ) {\displaystyle F^{*}(н)}

Ламбек и Мозер использовали простые числа в качестве примера, следуя более ранней работе Вигго Бруна и Д. Х. Лемера . [8] Если — функция подсчета простых чисел (количество простых чисел, меньших или равных ) , то -е не простое число (1 или составное число ) задается пределом последовательности [7] π ( н ) {\displaystyle \пи (n)} н {\displaystyle n} н {\displaystyle n} н , н + π ( н ) , н + π ( н + π ( н ) ) , … {\displaystyle n,n+\pi (n),n+\pi {\bigl (}n+\pi (n){\bigr)},\dots }

Для некоторых других последовательностей целых чисел соответствующий предел сходится за фиксированное число шагов, и возможна прямая формула для дополнительной последовательности. В частности, положительное целое число th , которое не является степенью th, может быть получено из предельной формулы как [9] н {\displaystyle n} к {\displaystyle к} н + ⌊ н + ⌊ н к ⌋ к ⌋ . {\displaystyle n+\left\lfloor {\sqrt[{k}]{n+\lfloor {\sqrt[{k}]{n}}\rfloor }}\right\rfloor .}

История и доказательства

Теорема была открыта Лео Мозером и Иоахимом Ламбеком , которые опубликовали ее в 1954 году. Мозер и Ламбек ссылаются на предыдущую работу Сэмюэля Битти о последовательностях Битти как на свое вдохновение, а также ссылаются на работу Вигго Бруна и Д. Х. Лемера начала 1930-х годов о методах, связанных с их предельной формулой для . [1] Эдсгер В. Дейкстра предоставил визуальное доказательство результата, [10] а позже еще одно доказательство, основанное на алгоритмических рассуждениях. [11] Юваль Гиносар предоставил интуитивное доказательство, основанное на аналогии двух спортсменов, бегущих в противоположных направлениях по круговой гоночной трассе. [12] Ф ∗ {\displaystyle F^{*}}

Для неотрицательных целых чисел

Разновидность теоремы применима к разбиениям неотрицательных целых чисел, а не к разбиениям положительных целых чисел. Для этой разновидности каждое разбиение соответствует соединению Галуа упорядоченных неотрицательных целых чисел с самими собой. Это пара неубывающих функций со свойством, что для всех и , тогда и только тогда, когда . Соответствующие функции и определяются немного менее симметрично с помощью и . Для функций, определенных таким образом, значения и (для неотрицательных аргументов, а не положительных аргументов) образуют разбиение неотрицательных целых чисел, и каждое разбиение может быть построено таким образом. [13] ( ф , ф ∗ ) {\displaystyle (ж,ж^{*})} х {\displaystyle x} у {\displaystyle у} ф ( х ) ≤ у {\displaystyle f(x)\leq y} х ≤ ф ( у ) {\displaystyle x\leq f(y)} Ф {\displaystyle F} Ф ∗ {\displaystyle F^{*}} Ф ( н ) = ф ( н ) + н {\displaystyle F(n)=f(n)+n} Ф ∗ ( н ) = ф ∗ ( н ) + н + 1 {\displaystyle F^{*}(n)=f^{*}(n)+n+1} Ф {\displaystyle F} Ф ∗ {\displaystyle F^{*}}

Теорема Рэлея

Теорема Рэлея утверждает, что для двух положительных иррациональных чисел и , оба больше единицы, при этом две последовательности и для , полученные округлением до целого числа кратных и , являются дополнительными. Это можно рассматривать как пример теоремы Ламбека–Мозера с и . Условие того, что и больше единицы, подразумевает, что эти две функции неубывают; производные функции равны и Последовательности значений и , образующие производное разбиение, известны как последовательности Битти , после того как Сэмюэл Битти в 1926 году переоткрыл теорему Рэлея. [14] г {\displaystyle r} с {\displaystyle с} 1 г + 1 с = 1 {\displaystyle {\tfrac {1}{r}}+{\tfrac {1}{s}}=1} ⌊ я ⋅ г ⌋ {\displaystyle \lfloor i\cdot r\rfloor } ⌊ я ⋅ с ⌋ {\displaystyle \lfloor i\cdot s\rfloor } я = 1 , 2 , 3 , … {\displaystyle i=1,2,3,\точки} г {\displaystyle r} с {\displaystyle с} ф ( н ) = ⌊ г н ⌋ − н {\displaystyle f(n)=\lfloor rn\rfloor -n} ф ∗ ( н ) = ⌊ с н ⌋ − н {\displaystyle f^{\ast }(n)=\lfloor sn\rfloor -n} г {\displaystyle r} с {\displaystyle с} Ф ( н ) = ⌊ г н ⌋ {\displaystyle F(n)=\lfloor rn\rfloor } Ф ∗ ( н ) = ⌊ с н ⌋ . {\displaystyle F^{*}(n)=\lfloor sn\rfloor .} Ф {\displaystyle F} Ф ∗ {\displaystyle F^{*}}

Смотрите также

Примечания

  1. ^ Ламбек и Мозер 1954.
  2. ↑ Уайлд 1955.
  3. ^ abcd Ламбек и Мозер 1954; Хонсбергер 1970, стр. 95–96; Френкель 1977.
  4. ^ ab Гарри 1997.
  5. ↑ Энджел 1964.
  6. ^ Аллуш и Деккинг 2019.
  7. ^ Аб Ламбек и Мозер 1954; Робертс 1992.
  8. ↑ Брун 1931; Лемер 1932.
  9. ^ Хонсбергер 1970, стр. 97–100; Дос Рейс и Силбергер, 1990; Робертс 1992.
  10. ^ Дейкстра 1980.
  11. ^ Дейкстра 1982.
  12. ^ Гиносар 2014.
  13. ^ Ламбек 1994.
  14. ^ Рэлей 1894; Битти 1926; Хонсбергер 1970, стр. 93–95; Чемберленд 2017.

Ссылки

  • Аллуш, Жан-Поль; Деккинг, Ф. Мишель (2019), «Обобщенные последовательности Битти и дополнительные тройки», Московский журнал комбинаторики и теории чисел , 8 (4): 325–341, arXiv : 1809.03424 , doi : 10.2140/moscow.2019.8.325, MR  4026541, S2CID  119176190
  • Энджел, Майер (1964), «Разделы натуральных чисел», Канадский математический вестник , 7 (2): 219–236, doi : 10.4153/CMB-1964-020-1 , MR  0161826, S2CID  123729929
  • Битти, Сэмюэл (1926), «Проблема 3173», The American Mathematical Monthly , 33 (3): 159, doi :10.2307/2300153, JSTOR  2300153; Решения Битти, А. Островски, Дж. Хислопа и А. К. Эйткена, т. 34 (1927), стр. 159–160, JSTOR  2298716
  • Брун, Вигго (1931), «Rechenregel zur Bildung der -ten Primzahl» [Правила расчета для построения третьего простого числа], Norsk Matematisk Tidsskrift (на норвежском языке), 13 : 73–79, Zbl  0003.14902. н {\displaystyle n} н {\displaystyle n} , как цитируется Ламбеком и Мозером 1954 г.
  • Чемберленд, Марк (2017), «Последовательности Битти», Single Digits: In Praise of Small Numbers , Princeton University Press, стр. 32–33, ISBN 978-0-691-17569-0
  • Дейкстра, Эдсгер В. (1980), О теореме Ламбека и Мозера (PDF) , Отчет EWD753, Техасский университет
  • Дейкстра, Эдсгер В. (1982), «Повторный визит Ламбека и Мозера», в Broy, Manfred; Schmidt, Gunther (ред.), Theoretical Foundations of Programming Methodology: Lecture Notes of an International Summer School, под руководством FL Bauer, EW Dijkstra и CAR Hoare , NATO Advanced Study Institutes Series, Series C – Mathematical and Physical Sciences, vol. 91, D. Reidel Publishing Co., стр. 19–23, doi :10.1007/978-94-009-7893-5_2, ISBN 978-90-277-1462-6, ЗБЛ  0533.40001
  • Dos Reis, AJ; Silberger, DM (1990), «Генерирование нестепенных чисел по формуле», Mathematics Magazine , 63 (1): 53–55, doi :10.1080/0025570X.1990.11977485, JSTOR  2691513, MR  1042938
  • Френкель, Авиезри С. (1977), «Дополнительные системы целых чисел», The American Mathematical Monthly , 84 (2): 114–115, doi :10.2307/2319931, JSTOR  2319931, MR  0429815
  • Гарри, YKK (1997), "Обратные последовательности и дополнительные последовательности" (PDF) , Математический Экскалибур , 3 (4): 2
  • Гиносар, Ювал (2014), «О теореме Ламбека–Мозера», Целые числа , 14 : A09:1–A09:4, arXiv : 1207.5633
  • Хонсбергер, Росс (1970), «Эссе 12: Дополнительные последовательности», Изобретательность в математике , Новая математическая библиотека, т. 23, Нью-Йорк: Random House, Inc., стр. 93–110, ISBN 0-394-70923-3, МР  3155264
  • Ламбек, Иоахим (1994), «Некоторые связи Галуа в элементарной теории чисел», Журнал теории чисел , 47 (3): 371–377, doi : 10.1006/jnth.1994.1043 , MR  1278405
  • Ламбек, Иоахим ; Мозер, Лео (август–сентябрь 1954 г.), «Обратные и дополнительные последовательности натуральных чисел», The American Mathematical Monthly , 61 (7): 454–458, doi :10.1080/00029890.1954.11988496, JSTOR  2308078
  • Лемер, Д. Х. (1932), «Обратный алгоритм», Бюллетень Американского математического общества , 38 (10): 693–694, doi : 10.1090/S0002-9904-1932-05496-9 , MR  1562488
  • Джон Уильям Стратт, барон Рэлей (1894), Теория звука, т. 1 (2-е изд.), Macmillan, стр. 123
  • Робертс, Джо (1992), Приманка целых чисел, MAA Spectrum, Вашингтон, округ Колумбия: Математическая ассоциация Америки, стр. 11, doi : 10.2307/40148160, ISBN 0-88385-502-X, JSTOR  40148160, MR  1189138
  • Уайлд, Рой Э. (1955), «О числе примитивных пифагорейских треугольников с площадью меньше n», Pacific Journal of Mathematics , 5 : 85–91, doi : 10.2140/pjm.1955.5.85 , MR  0067912
Взято с "https://en.wikipedia.org/w/index.php?title=Lambek–Moser_theorem&oldid=1211616079"