Битти-последовательность

В математике последовательность Битти (или однородная последовательность Битти ) — это последовательность целых чисел , найденная путем взятия нижнего числа положительных кратных положительного иррационального числа . Последовательности Битти названы в честь Сэмюэля Битти , написавшего о них в 1926 году.

Теорема Рэлея , названная в честь лорда Рэлея , утверждает, что дополнение последовательности Битти, состоящее из положительных целых чисел, не входящих в последовательность, само по себе является последовательностью Битти, порожденной другим иррациональным числом.

Последовательности Битти также можно использовать для создания слов Штурма .

Определение

Любое иррациональное число $r$ которое больше единицы, генерирует последовательность Битти $${\mathcal {B}}_{r}={\bigl \{}\lfloor r\rfloor ,\lfloor 2r\rfloor ,\lfloor 3r\rfloor ,\ldots {\bigr \}}$$Два иррациональных числа $r$ и $s=r/(r-1)$ естественно удовлетворяет уравнению $1/r+1/s=1$.Две сцены Битти ${\mathcal {B}}_{r}$ и ${\mathcal {B}}_{s}$ которые они генерируют, образуют пару дополнительных последовательностей Битти . Здесь «дополнительный» означает, что каждое положительное целое число принадлежит ровно одной из этих двух последовательностей.

Примеры

Когда $r$ это золотое сечение $r=(1+{\sqrt {5}})/2\approx 1.618$, дополнительная последовательность Битти генерируется $s=r+1=(3+{\sqrt {5}})/2\approx 2.618$. В этом случае последовательность $(\lfloor nr\rfloor )$, известная как нижняя последовательность Витгофа , представляет собой

1 , 3 , 4 , 6 , 8 , 9 , 11 , 12 , 14 , 16 , 17 , 19 , 21 , 22 , 24 , 25 , 27 , 29 , ... (последовательность A000201 в OEIS ),

и дополнительная последовательность $(\lfloor ns\rfloor )$, верхняя последовательность Витгофа , есть

2 , 5 , 7 , 10 , 13 , 15 , 18 , 20 , 23 , 26 , 28 , 31 , 34 , 36 , 39 , 41 , 44 , 47 , ... (последовательность A001950 в OEIS ).

Эти последовательности определяют оптимальную стратегию игры Витхоффа и используются при определении массива Витгоффа .

Другой пример: квадратный корень из 2 : $r={\sqrt {2}}\approx 1.414$, $s=2+{\sqrt {2}}\approx 3.414$. В этом случае последовательности

1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, ... (последовательность A001951 в OEIS ), и

3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... (последовательность A001952 в OEIS ).

Для $r=\pi \approx 3.142$ и $s=\pi /(\pi -1)\approx 1.467$, последовательности

3, 6, 9, 12, 15, 18, 21, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53, ... (последовательность A022844 в OEIS ), и

1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, ... (последовательность A054386 в OEIS ).

Любое число в первой последовательности отсутствует во второй, и наоборот.

История

Последовательности Битти получили свое название от задачи, поставленной Сэмюэлем Битти в математическом ежемесячном журнале» « Американском в 1926 году. Вероятно, это одна из наиболее часто упоминаемых проблем, когда-либо поднимавшихся в Monthly . Однако еще раньше, в 1894 году, подобные последовательности были кратко упомянуты лордом Рэлеем во втором издании его книги «Теория звука» .

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

Теорема Рэлея (также известная как теорема Битти ) утверждает, что при наличии иррационального числа $r>1\,,$ существует $s>1$ так что последовательности Битти ${\mathcal {B}}_{r}$ и ${\mathcal {B}}_{s}$ разделите набор положительных целых чисел: каждое положительное целое число принадлежит ровно одной из двух последовательностей.

Первое доказательство

Данный $r>1\,,$ позволять $s=r/(r-1)$. Мы должны показать, что каждое положительное целое число принадлежит одной и только одной из двух последовательностей. ${\mathcal {B}}_{r}$ и ${\mathcal {B}}_{s}$. Мы сделаем это, рассмотрев порядковые позиции, занимаемые всеми дробями. $j/r$ и $k/s$ когда они вместе перечислены в порядке неубывания для натуральных чисел j и k .

Чтобы увидеть, что никакие два числа не могут занимать одну и ту же позицию (как одно число), предположим противное, что $j/r=k/s$ для некоторых j и k . Затем $r/s$ = $j/k$, рациональное число , но также, $r/s=r(1-1/r)=r-1,$ не рациональное число. Следовательно, никакие два числа не занимают одну и ту же позицию.

Для любого $j/r$, есть $j$ положительные целые числа $i$ такой, что $i/r\leq j/r$ и $\lfloor js/r\rfloor$ положительные целые числа $k$ такой, что $k/s\leq j/r$, так что положение $j/r$ в списке есть $j+\lfloor js/r\rfloor$. Уравнение $1/r+1/s=1$ подразумевает $$j+\lfloor js/r\rfloor =j+\lfloor j(s-1)\rfloor =\lfloor js\rfloor .$$

Аналогично, позиция $k/s$ в списке есть $\lfloor kr\rfloor$.

Вывод: каждое целое положительное число (то есть каждая позиция в списке) имеет вид $\lfloor nr\rfloor$ или формы $\lfloor ns\rfloor$, но не то и другое. Верно и обратное утверждение: если p и q — два действительных числа такие, что каждое положительное целое число встречается в приведенном выше списке ровно один раз, то p и q иррациональны, а сумма их обратных чисел равна 1.

Второе доказательство

Столкновения . Предположим, что вопреки теореме существуют целые числа j > 0, k и m такие, что $$j=\left\lfloor {k\cdot r}\right\rfloor =\left\lfloor {m\cdot s}\right\rfloor \,.$$Это эквивалентно неравенствам $$j\leq k\cdot r<j+1{\text{ and }}j\leq m\cdot s<j+1.$$

Для ненулевого j иррациональность r и s несовместима с равенством, поэтому $$j<k\cdot r<j+1{\text{ and }}j<m\cdot s<j+1,$$что приводит к $${j \over r}<k<{j+1 \over r}{\text{ and }}{j \over s}<m<{j+1 \over s}.$$

Сложив их вместе и используя гипотезу, мы получаем $$j<k+m<j+1$$что невозможно (нельзя иметь целое число между двумя соседними целыми числами). Таким образом, предположение должно быть ложным.

Антиколлизии : предположим, что вопреки теореме существуют целые числа j > 0, k и m такие, что $$k\cdot r<j{\text{ and }}j+1\leq (k+1)\cdot r{\text{ and }}m\cdot s<j{\text{ and }}j+1\leq (m+1)\cdot s\,.$$

Поскольку j + 1 не равно нулю, а r и s иррациональны, мы можем исключить равенство, поэтому $$k\cdot r<j{\text{ and }}j+1<(k+1)\cdot r{\text{ and }}m\cdot s<j{\text{ and }}j+1<(m+1)\cdot s.$$

Тогда мы получим $$k<{j \over r}{\text{ and }}{j+1 \over r}<k+1{\text{ and }}m<{j \over s}{\text{ and }}{j+1 \over s}<m+1$$

Сложив соответствующие неравенства, получим $$k+m<j{\text{ and }}j+1<k+m+2$$$$k+m<j<k+m+1$$

что тоже невозможно. Таким образом, предположение неверно.

Характеристики

Число $m$ принадлежит к последовательности Битти ${\mathcal {B}}_{r}$ тогда и только тогда, когда $$1-{\frac {1}{r}}<\left[{\frac {m}{r}}\right]_{1}$$где $[x]_{1}$ обозначает дробную часть $x$ то есть, $[x]_{1}=x-\lfloor x\rfloor$.

Доказательство: $m\in B_{r}$$\Leftrightarrow \exists n,m=\lfloor nr\rfloor$$\Leftrightarrow m<nr<m+1$$\Leftrightarrow {\frac {m}{r}}<n<{\frac {m}{r}}+{\frac {1}{r}}$$\Leftrightarrow n-{\frac {1}{r}}<{\frac {m}{r}}<n$$\Leftrightarrow 1-{\frac {1}{r}}<\left[{\frac {m}{r}}\right]_{1}$

Более того, $m=\left\lfloor \left(\left\lfloor {\frac {m}{r}}\right\rfloor +1\right)r\right\rfloor$.

Доказательство: $m=\left\lfloor \left(\left\lfloor {\frac {m}{r}}\right\rfloor +1\right)r\right\rfloor$$\Leftrightarrow m<\left(\left\lfloor {\frac {m}{r}}\right\rfloor +1\right)r<m+1$$\Leftrightarrow {\frac {m}{r}}<\left\lfloor {\frac {m}{r}}\right\rfloor +1<{\frac {m+1}{r}}$$\Leftrightarrow \left\lfloor {\frac {m}{r}}\right\rfloor +1-{\frac {1}{r}}<{\frac {m}{r}}<\left\lfloor {\frac {m}{r}}\right\rfloor +1$$\Leftrightarrow 1-{\frac {1}{r}}<{\frac {m}{r}}-\left\lfloor {\frac {m}{r}}\right\rfloor =\left[{\frac {m}{r}}\right]_{1}$

Связь с последовательностями Штурма

Первое отличие $$\lfloor (n+1)r\rfloor -\lfloor nr\rfloor$$последовательности Битти, связанной с иррациональным числом $r$ - характерное слово Штурма в алфавите $\{\lfloor r\rfloor ,\lfloor r\rfloor +1\}$.

Обобщения

Если немного изменить, теорему Рэлея можно обобщить на положительные действительные числа (не обязательно иррациональные), а также на отрицательные целые числа: если положительные действительные числа $r$ и $s$ удовлетворить $1/r+1/s=1$, последовательности $(\lfloor mr\rfloor )_{m\in \mathbb {Z} }$ и $(\lceil ns\rceil -1)_{n\in \mathbb {Z} }$ образуют разбиение целых чисел. Например, белые и черные клавиши клавиатуры фортепиано распределены в виде таких последовательностей для $r=12/7$ и $s=12/5$.

Теорема Ламбека-Мозера обобщает теорему Рэлея и показывает, что более общие пары последовательностей, определенные из целочисленной функции и ее обратной, обладают одинаковым свойством разделения целых чисел.

Теорема Успенского утверждает, что если $\alpha _{1},\ldots ,\alpha _{n}$ положительные действительные числа такие, что $(\lfloor k\alpha _{i}\rfloor )_{k,i\geq 1}$ содержит все положительные целые числа ровно один раз, то $n\leq 2.$ То есть не существует эквивалента теоремы Рэлея для трех и более последовательностей Битти.

Дальнейшее чтение

• Холсхаузер, Артур; Райтер, Гарольд (2001). «Обобщение теоремы Битти» . Юго-западный журнал чистой и прикладной математики . 2 : 24–29. Архивировано из оригинала 19 апреля 2014 г.
• Столарский, Кеннет (1976). «Последовательности Битти, цепные дроби и некоторые операторы сдвига» . Канадский математический бюллетень . 19 (4): 473–482. дои : 10.4153/CMB-1976-071-6 . МР   0444558 . Содержит множество ссылок.

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

• Вайсштейн, Эрик В. «Последовательность Битти» . Математический мир .
• Александр Богомольный , Beatty Sequences , Cut-the-knot