Rotational interval exchange transformations
UDC 517.5 We show the equivalence of two possible definitions of a rotational interval exchange transformation: by the first definition, it is the first return map for a circle rotation onto a union of finitely many circle arcs and, by the second definition, it is an interval exchange with a scheme...
Saved in:
| Date: | 2024 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Institute of Mathematics, NAS of Ukraine
2024
|
| Online Access: | https://umj.imath.kiev.ua/index.php/umj/article/view/7779 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Ukrains’kyi Matematychnyi Zhurnal |
| Download file: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1865794120881012736 |
|---|---|
| author | Teplinsky, A. Теплінський, Олексій |
| author_facet | Teplinsky, A. Теплінський, Олексій |
| author_institution_txt_mv | [
{
"author": "Олексій Теплінський",
"institution": "Інститут математики НАН України, Київ"
}
] |
| author_sort | Teplinsky, A. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2024-06-19T00:35:20Z |
| description | UDC 517.5
We show the equivalence of two possible definitions of a rotational interval exchange transformation: by the first definition, it is the first return map for a circle rotation onto a union of finitely many circle arcs and, by the second definition, it is an interval exchange with a scheme (in the sense of interval rearrangement ensembles) whose dual is also an interval exchange scheme. |
| doi_str_mv | 10.3842/umzh.v76i3.7779 |
| first_indexed | 2026-03-24T03:33:47Z |
| format | Article |
| fulltext |
DOI: 10.3842/umzh.v76i3.7779
УДК 517.5
Олексiй Теплiнський1 (Iнститут математики НАН України, Київ)
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ
We show the equivalence of two possible definitions of a rotational interval exchange transformation: by the first definition,
it is the first return map for a circle rotation onto a union of finitely many circle arcs and, by the second definition, it is an
interval exchange with a scheme (in the sense of interval rearrangement ensembles) whose dual is also an interval exchange
scheme.
Показано еквiвалентнiсть двох можливих означень ротацiйного перекладання iнтервалiв: згiдно з одним, це вi-
дображення першого повернення для повороту кола на об’єднання скiнченної кiлькостi його дуг, а згiдно з iншим,
це перекладання iнтервалiв зi схемою (в сенсi перекладального ансамблю iнтервалiв), дуальна до якої схема також
є схемою перекладання iнтервалiв.
1. Вступ. У роботi [1] було запропоновано нову концепцiю перекладальних ансамблiв iнтер-
валiв (ПАI), яка узагальнює класичну для теорiї динамiчних систем конструкцiю перекладання
iнтервалiв [2 – 7]. Нарiжним поняттям нашої концепцiї є iнволюцiя дуальностi на просторi схем
(дискретних компонент) ПАI, яка кожнiй схемi ПАI ставить у вiдповiднiсть дуальну до неї схе-
му ПАI, i ця дуальнiсть обертає в часi iндукцiю типу Розi – Вiча. Схеми перекладань iнтервалiв
є частинним випадком схем ПАI i, як виявилося, дуальнi до них схеми можуть бути, а можуть
i не бути схемами перекладань iнтервалiв. Власне, простiр усiх схем ПАI є поповненням про-
стору всiх схем перекладань iнтервалiв (на багатьох промiжках) щодо операцiї дуальностi. З
iншого боку, серед усiх схем перекладань iнтервалiв можна видiлити пiдпростiр тих, дуальнi
до яких є також схемами перекладань iнтервалiв. Перекладання iнтервалiв зi схемами з цього
пiдпростору ми називаємо ротацiйними, оскiльки такi перекладання пов’язанi з поворотами
кола, а саме, є вiдображеннями першого повернення для поворотiв кола на об’єднання скiн-
ченної кiлькостi його дуг. Фактично йдеться про два пiдходи до означення одного об’єкту, якi
в певному сенсi є еквiвалентними: перший — через дуальнiсть схем ПАI, другий — через вiд-
ображення першого повернення на колi. Мета цiєї роботи полягає в тому, щоб точно описати
зв’язок мiж цими пiдходами. Результати сформульовано у виглядi трьох тверджень теореми 1 i
доведено у вiдповiдних пунктах статтi.
На думку автора, саме дослiдження ротацiйних перекладань iнтервалiв у рамках концепцiї
ПАI торує шлях до нових результатiв стосовно вiдкритих поки що питань теорiї жорсткостi
для дифеоморфiзмiв кола з багатьма особливими точками, вiдповiднi до яких результати для
дифеоморфiзмiв кола з одним зламом були отриманi в роботах [8, 9]. Справа в тому, що най-
бiльш перспективним у дослiдженнi поворотiв кола з особливими точками є ренормалiзацiйний
пiдхiд, коли замiсть вихiдного вiдображення розглядається послiдовнiсть вiдображень першого
повернення на об’єднання малих околiв особливих точок, перенормованих з експоненцiйно
малої довжини на макроскопiчну. У послiдовностi вiдображень першого повернення наступне
вiдображення одержується з попереднього шляхом застосування iндукцiї типу Розi – Вiча, а
1 E-mail: teplinsky.a@gmail.com.
c\bigcirc ОЛЕКСIЙ ТЕПЛIНСЬКИЙ, 2024
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3 447
448 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
отже дуальнiсть, яка дозволяє обертати час у цьому процесi, буде важливим iнструментом у
подальших дослiдженнях.
Якщо особливi точки iррацiонального дифеоморфiзму кола є невиродженими точками зламу
(лiва похiдна не дорiвнює правiй, але обидвi є додатними; вiдношення цих похiдних вважа-
ється розмiром зламу), то ренормалiзованi вiдображення першого повернення зi зменшенням
довжини розглядуваних околiв прямують до певних скiнченновимiрних просторiв. Цi простори
складаються з дробово-лiнiйних функцiй, що вперше показано в роботi [10], а у випадку, коли
добуток усiх розмiрiв зламiв дорiвнює одиницi, — з аффiнних функцiй, що дослiджено, зокрема,
в роботах [11, 12].
Логiчним наступним кроком буде розширення дуальностi з простору схем ПАI на вiдповiднi
простори дробово-лiнiйних функцiй, чому автор планує присвятити майбутнi публiкацiї.
Опишемо коротко структуру статтi. У пунктi 2 наведено базовi поняття теорiї перекладаль-
них ансамблiв iнтервалiв, у пунктi 3 сформульовано основний результат як теорему з трьох
частин, у пунктах 4 – 6 доведено частини 1 – 3 теореми вiдповiдно.
2. Базовi вiдомостi про ПАI та перекладання iнтервалiв. Нагадаємо основнi поняття
теорiї перекладальних ансамблiв iнтервалiв, викладеної в [1].
Нехай \scrA — алфавiт iз d \geq 1 символiв (вони слугуватимуть мiтками для iнтервалiв iз
перекладального ансамблю). Розглянемо подвоєний алфавiт \=\scrA = \scrA \times \{ \mathrm{b}, \mathrm{e}\} (iндекси \mathrm{b} та \mathrm{e} по-
ходять вiд слiв beginning (початковий) та ending (кiнцевий) вiдповiдно) i будь-яку перестановку
\sigma на цьому подвоєному алфавiтi (тобто бiєктивне вiдображення з \=\scrA на \=\scrA ). Цю перестановку
називаємо схемою перекладального ансамблю iнтервалiв, а власне перекладальний ансамбль
iнтервалiв (ПАI) — це пара (\sigma ,\bfx ), у якiй до схеми \sigma доєднано вектор країв (крайнiх точок
iнтервалiв; ми називаємо їх краями, а не кiнцями, щоби уникнути плутанини з початковими та
кiнцевими iнтервалами) \bfx \in \BbbR \=\scrA , координати якого задовольняють рiвностi
x\alpha \mathrm{b} + x\alpha \mathrm{e} - x\sigma (\alpha \mathrm{b}) + x\sigma (\alpha \mathrm{e}) = 0 для всiх \alpha \in \scrA . (1)
Вектори \bfx , якi задовольняють (1), називаємо дозволеними схемою \sigma . Для цього ПАI (\sigma ,\bfx )
вектор довжин \bfv \in \BbbR \scrA означається покоординатно як
v\alpha = x\sigma (\alpha \mathrm{b}) - x\alpha \mathrm{b} = x\alpha \mathrm{e} - x\sigma (\alpha \mathrm{e}), \alpha \in \scrA . (2)
Називаємо два ПАI еквiвалентними з точнiстю до зсуву, якщо у них спiвпадають схеми та
вектори довжин. Довiльний вектор \bfv \in \BbbR \scrA називається дозволеним схемою \sigma вектором дов-
жин, якщо iснує дозволений нею вектор країв, для якого виконуються рiвностi (2). Пару (\sigma ,\bfv )
iз дозволеним схемою \sigma вектором довжин \bfv називаємо плаваючим ПАI на вiдмiну вiд „закрi-
пленого” ПАI (\sigma ,\bfx ). Плаваючий ПАI можна розглядати як клас еквiвалентностi закрiплених
ПАI, еквiвалентних з точнiстю до зсуву.
У цiй статтi ми переважно працюватимемо саме з плаваючими ПАI, регулярно користу-
ючись наступним простим критерiєм щодо дозволеностi вектора довжин для вказаної схеми.
Ключовим фактом є те, що схема \sigma , як будь-яка перестановка, розкладається на N \geq 1 циклiв
вигляду c = c(\=\xi ) = (\=\xi , \sigma (\=\xi ), . . . , \sigma k(\=\xi )), \=\xi \in \=\scrA , де k \geq 0, \sigma k+1(\=\xi ) = \=\xi , \sigma i(\=\xi ) \not = \=\xi для 0 < i \leq k,
c(\=\xi ) i c(\sigma i(\=\xi )) ототожнюються мiж собою.
Твердження 1. Вектор довжин \bfv є дозволеним схемою ПАI \sigma тодi й лише тодi, коли для
кожного її циклу c = c(\=\xi ), \=\xi \in \=\scrA , виконується рiвнiсть
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 449\sum
\alpha : \alpha \mathrm{b}\in c
v\alpha =
\sum
\alpha : \alpha \mathrm{e}\in c
v\alpha . (3)
Доведення. Нехай вектор довжин \bfv є дозволеним схемою \sigma . Тодi iснує вектор країв \bfx , для
якого виконуються рiвностi (2). Згiдно з ними x\sigma (\=\eta ) - x\=\eta = v\alpha для \=\eta = \alpha \mathrm{b} та x\sigma (\=\eta ) - x\=\eta = - v\alpha
для \=\eta = \alpha \mathrm{e}, i рiвностi (3) випливають з тотожностей\sum
\=\eta \in c(\=\xi )
(x\sigma (\=\eta ) - x\=\eta ) = (x\sigma (\=\xi ) - x\=\xi ) + (x\sigma 2(\=\xi ) - x\sigma (\=\xi )) + . . .+ (x\=\xi - x\sigma k(\=\xi )) = 0
уздовж кожного циклу c(\=\xi ).
Нехай тепер для вектора \bfv виконуються рiвностi (3). Для кожного з циклiв c(\=\xi ) у складi
схеми \sigma задамо координату краю x\=\xi довiльним чином, а решту країв визначимо за таким
алгоритмом: якщо значення x\=\eta вже визначено, а x\sigma (\=\eta ) ще нi, то покладаємо x\sigma (\=\eta ) = x\=\eta + v\alpha у
випадку \=\eta = \alpha \mathrm{b} i x\sigma (\=\eta ) = x\=\eta - v\alpha у випадку \=\eta = \alpha \mathrm{e}. В силу рiвностей (3) цi ж спiввiдношення
виконуються i для \=\eta = \sigma k(\=\xi ), а отже вектор країв \bfx є дозволеним, i \bfv задовольняє (2).
Твердження доведено.
Ключову роль у теорiї ПАI вiдiграє поняття дуальностi, яке обертає час при застосуваннi
до схеми ПАI iндукцiї типу Розi – Вiча (у пп. 5.1 наведено означення елементарних крокiв цiєї
iндукцiї). Двi схеми ПАI \sigma i \sigma \ast називаємо дуальними одна до одної, якщо
\sigma \ast (\alpha \mathrm{b}) = \sigma (\alpha \mathrm{e}), \sigma \ast (\alpha \mathrm{e}) = \sigma (\alpha \mathrm{b}) для всiх \alpha \in \scrA . (4)
Саме через дуальнiсть ми означимо ротацiйнi схеми перекладання iнтервалiв у наступному
пунктi.
Схема ПАI називається незвiдною, якщо з рiвностi \sigma ( \=\scrA 0) = \=\scrA 0, де \=\scrA 0 = \scrA 0 \times \{ \mathrm{b}, \mathrm{e}\} , для
пiдмножини алфавiту \scrA 0 \subset \scrA випливає \scrA 0 \in \{ \varnothing ,\scrA \} . З означення дуальностi (4) легко бачити,
що \sigma ( \=\scrA 0) = \sigma \ast ( \=\scrA 0) для будь-якої пiдмножини \scrA 0 \subset \scrA , а отже з незвiдностi \sigma випливає
незвiднiсть \sigma \ast i навпаки. Якщо схема не є незвiдною, то ПАI з такою схемою фактично
розпадається на два чи кiлька ПАI, якi нiяк не пов’язанi мiж собою, тому в дослiдженнi питань
динамiки є сенс обмежитися розглядом ПАI з незвiдними схемами.
З твердження 2 з роботи [1] випливає, що у випадку незвiдної схеми \sigma з-помiж N рiвно-
стей (3) лiнiйно незалежними є в точностi N - 1 (сума всiх рiвностей (3) очевидно є тотожнiстю,
тож будь-якi N - 1 з-помiж них є лiнiйно незалежними).
Називаємо ПАI додатним, якщо його вектор довжин є додатним. Схему ПАI називаємо
додатною, якщо вона дозволяє додатний вектор довжин.
Додатний ПАI слiд уявляти як ансамбль iз 2d iнтервалiв, спарованих у d пар iз мiтками
\alpha \in \scrA ; у кожнiй такiй парi початковий iнтервал I\alpha \mathrm{b} = [x\alpha \mathrm{b}, x\sigma (\alpha \mathrm{b})) та кiнцевий iнтервал
I\alpha \mathrm{e} = [x\sigma (\alpha \mathrm{e}), x\alpha \mathrm{e}) з тiєю ж самою мiткою \alpha мають однакову довжину v\alpha . Вiдповiдно до
циклiв у схемi, всi початковi та кiнцевi iнтервали з вiдповiдними iндексами є зчепленими своїми
краями в N зiмкнених ланцюжкiв, тобто одновимiрних ламаних лiнiй. Можна розглядати таку
зiмкнену ламану як шлях вiд x\=\xi до x\sigma (\=\xi ), потiм вiд x\sigma (\=\xi ) до x\sigma 2(\=\xi ) i так далi до повернення в x\=\xi ,
при цьому кожен початковий iнтервал проходиться злiва направо, а кожен кiнцевий — справа
налiво. Паралельне перенесення кожної з цих N зiмкнених одновимiрних ламаних лiнiй на
певну вiдстань, очевидно, залишає в силi рiвностi (2) i не змiнює довжини iнтервалiв, саме
тому ми назвали пару (\sigma ,\bfv ) плаваючим ПАI, а вiдповiднi закрiпленi ПАI еквiвалентними з
точнiстю до зсуву.
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
450 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
У випадку, коли кожен iз циклiв у схемi \sigma додатного ПАI можна розбити на двi дуги, перша
з яких складається лише з початкових iнтервалiв, а друга — лише з кiнцевих (тобто кожен цикл
має вигляд c = (\alpha 1\mathrm{b}, . . . , \alpha m\mathrm{b}, \beta n\mathrm{e}, . . . , \beta 1\mathrm{e}) для певних мiток \alpha 1, . . . , \alpha m, \beta 1, . . . , \beta n \in \scrA ,
n,m \geq 1), такий ПАI природно назвати перекладанням iнтервалiв i асоцiювати з дискрет-
ною динамiчною системою (вiдображенням) на диз’юнктному об’єднаннi вiдповiдних до цик-
лiв c1, . . . , cN промiжкiв J1, . . . , JN (а саме, наведеному вище циклу c вiдповiдає промiжок
J = [x\alpha 1\mathrm{b}, x\beta n\mathrm{e}) =
\bigcup m
i=1
I\alpha i\mathrm{b} =
\bigcup n
i=1
I\beta i\mathrm{e}), яка зсуває кожний початковий iнтервал на кiнце-
вий iнтервал iз тою ж мiткою з алфавiту \scrA . Твердження 1 у такому випадку стверджує, що
вектор довжин є дозволеним схемою тодi й лише тодi, коли для кожного промiжку J сума
довжин усiх початкових iнтервалiв у його складi дорiвнює сумi довжин усiх кiнцевих. Ми на-
зиватимемо перекладанням iнтервалiв як пару (\sigma ,\bfx ), так i асоцiйоване з нею вiдображення i
породжену ним одновимiрну динамiчну систему. Схему \sigma у такому випадку називаємо схемою
перекладання iнтервалiв. Аналогiчно до загальних ПАI, можна розглядати плаваючi перекла-
дання iнтервалiв (\sigma ,\bfv ), якщо обмежитись увагою лише до довжин iнтервалiв, дозволивши
при цьому промiжкам J1, . . . , JN соватися уздовж осi, тобто профакторизувавши простiр усiх
перекладань за вiдношенням еквiвалентностi з точнiстю до зсуву.
Цикли вказаного вигляду (\alpha 1\mathrm{b}, . . . , \alpha m\mathrm{b}, \beta n\mathrm{e}, . . . , \beta 1\mathrm{e}) зручно записувати у бiльш наочному
„дворядковому запиci” c =
\biggl[
\alpha 1 . . . \alpha m
\beta 1 . . . \beta n
\biggr]
(при цьому цiлу схему перекладання iнтервалiв
можна подавати теж у два рядки як множину всiх її циклiв \sigma = \{ c1, . . . , cN\} , N \geq 1). У
термiнологiї [1] такий „дворядковий” цикл називається циклом iз нульовим покрученням. Якщо
бути точним, то число покручення окремого циклу схеми ПАI \sigma — це кiлькiсть мiсць у цьому
циклi, де за початковим елементом слiдує кiнцевий, тобто \sigma (\alpha \mathrm{b}) = \beta \mathrm{e} для якихось \alpha , \beta \in \scrA ,
мiнус одиниця. Якщо цикл складається лише з початкових чи лише з кiнцевих елементiв, то
його число покручення дорiвнює - 1, але за умови додатностi схеми цей випадок неможливий.
Число покручення T (\sigma ) схеми — це сума чисел покручення усiх її циклiв. Вiдповiдно, у такiй
термiнологiї схема перекладання iнтервалiв — це додатна схема ПАI з нульовим покрученням,
а власне перекладання iнтервалiв — це додатний ПАI з такою схемою.
Наведене вище означення перекладання iнтервалiв збiгається з класичним тодi, коли його
схема складається з єдиного циклу, а лiвий край вiдповiдного промiжку знаходиться в початку
координат. Цi обмеження не видаються нам природними, i тому ми називаємо перекладанням
iнтервалiв саме бiльш загальну конструкцiю на багатьох промiжках. У пунктi 3 роботи [1],
до того як означити ПАI, автор сформулював означення перекладання iнтервалiв на багатьох
промiжках у класичному дусi. Можна порiвняти наскiльки означення перекладання iнтервалiв
в рамках концепцiї ПАI є менш громiздким.
3. Ротацiйнi схеми i основний результат. Коли \sigma є схемою перекладання iнтервалiв,
дуальна до неї схема \sigma \ast не обов’язково, але може також бути схемою перекладання iнтервалiв,
i перекладання iнтервалiв iз такою властивiстю складають важливий спецiальний клас, який
є предметом даної статтi. Отже, назвемо схему перекладання iнтервалiв ротацiйною, якщо
дуальна до неї також є схемою перекладання iнтервалiв. А власне перекладання iнтервалiв з
ротацiйною схемою назвемо ротацiйним перекладанням iнтервалiв.
Повним покрученням схеми ПАI \sigma в [1] названо величину T (\sigma ) + T (\sigma \ast ), тобто суму чисел
покручення схем \sigma i \sigma \ast . У такiй термiнологiї ротацiйна схема — це схема ПАI, яка разом
iз дуальною є додатною i має нульове повне покручення, а власне ротацiйне перекладання
iнтервалiв — це додатний ПАI з такою схемою. Вiдповiдно до п. 10 роботи [1], це саме тi схеми,
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 451
додатним натуральним розширенням яких вiдповiдають трансляцiйнi поверхнi топологiчного
роду g = 1, тобто тори, без особливих точок.
Зрозумiло, що клас усiх ротацiйних схем є замкненим щодо операцiї дуальностi. Але чому
ми назвали такi перекладання iнтервалiв та їхнi схеми саме „ротацiйними”? Тому, що вони
безпосередньо пов’язанi з поворотами кола. Точне твердження про цей зв’язок i є основним
результатом статтi, сформульованим у цьому пунктi.
Поворотом кола довжини L > 0 на вiдстань M називається вiдображення
RL,M : a \mapsto \rightarrow a+M, a \in \BbbR /L\BbbZ , (5)
де фактор-простiр \BbbR /L\BbbZ власне i є колом довжини L. Поворот кола називається iррацiональним,
якщо його число обертання \rho = \{ M/L\} \not \in \BbbQ . Тут \{ \cdot \} позначає дробову частину дiйсного
числа.
Альтернативно, поворотом кола можна вважати його проєкцiю на довiльно обраний напiв-
вiдкритий промiжок [x0, x0 + L), x0 \in \BbbR , тобто кусково-лiнiйне вiдображення
RL,M : x \mapsto \rightarrow x+M -
\biggl[
x+M - x0
L
\biggr]
L, x \in [x0, x0 + L), (6)
яке, як легко переконатись, є ротацiйним перекладанням (двох) iнтервалiв. Тут [ \cdot ] позначає
цiлу частину дiйсного числа.
Називатимемо дугою будь-який напiввiдкритий промiжок на колi. Далi ми розглядатимемо
об’єднання скiнченної кiлькостi дуг i згiдно з альтернативним означенням (6) iнтерпретувати-
мемо кожен такий об’єкт як об’єднання скiнченної кiлькостi напiввiдкритих промiжкiв дiйсної
прямої. Якщо таке об’єднання дуг (для скорочення пропускатимемо слова „скiнченної кiлькос-
тi”, бо розглядатимемо лише такi) не вкриває все коло повнiстю, то природно вибрати за x0
проєкцiю на \BbbR якої-небудь точки кола, що не належить до внутрiшностi жодної з дуг. Також
природно вважати окремими промiжками цього об’єднання максимальнi (тобто якщо двi дуги
перекриваються чи дотикаються краями, то їхнi проєкцiї на \BbbR слiд об’єднати в один промiжок).
У випадку, коли об’єднанням дуг є все коло, край x0 можна взяти будь-де й iнтерпретувати це
об’єднання дуг як цiлий дiйсний промiжок [x0, x0 + L).
Тепер можемо сформулювати основним результат статтi. Варто зазначити, що найбiльш
важливою у цiй теоремi є її третя частина, тодi як першi двi лише доповнюють третю: якiснi
(дискретнi) данi є важливiшими за кiлькiснi (дiйснi), бо простiр дозволених довжин ПАI визна-
чається його схемою, а не навпаки. Але логiка саме такого впорядкування частин теореми поля-
гає в тому, що доведення третьої з них вiдбувається на основi доведень перших двох (а в дечому
третя частина є безпосереднiм наслiдком першої та другої, докладнiше див. у п. 6). Доведення
теореми є конструктивним у тому сенсi, що iснування всiх шуканих об’єктiв доводиться шляхом
їх алгоритмiчної побудови. Зокрема, звертаємо увагу на введений у пп. 5.7 канонiчний вигляд
ротацiйного перекладання iнтервалiв, який пов’язаний iз так званими динамiчними розбиттями
кола (див. [9]) i є найзручнiшим „посередником” мiж загальними ротацiйними перекладаннями
iнтервалiв та поворотами кола.
Теорема 1. 1. Для будь-якого iррацiонального повороту кола вiдображення першого по-
вернення на будь-яку множину, яка є об’єднанням дуг, являє собою незвiдне ротацiйне пере-
кладання iнтервалiв.
2. Для будь-якого незвiдного ротацiйного перекладання iнтервалiв iснує еквiвалентне йому
з точнiстю до зсуву вiдображення першого повернення для повороту кола на об’єднання дуг.
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
452 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
3. Незвiдна схема перекладання iнтервалiв є ротацiйною тодi й лише тодi, коли iснує таке
вiдображення першого повернення для iррацiонального повороту кола на об’єднання дуг, яке
являє собою перекладання iнтервалiв iз цiєю схемою.
Зауваження 1. Теорему сформульовано для незвiдних схем та перекладань, яким у кож-
ному випадку вiдповiдає якийсь поворот кола. Якщо схема перекладання iнтервалiв скла-
дається з кiлькох незвiдних компонент, то динамiчна система розпадається на вiдповiдну
кiлькiсть незалежних одна вiд одної систем, а тому i вiдображення першого повернення
мусить розглядатися для об’єднання вiдповiдної кiлькостi поворотiв кола. Отже, частини 2
i 3 теореми можна переформулювати, пропустивши у них згадку про незвiднiсть перекла-
дань та схем, натомiсть замiнивши поворот кола на об’єднання поворотiв кола (у части-
нi 3 — iррацiональних поворотiв) у кiлькостi, що дорiвнює кiлькостi незвiдних компонент
схеми.
Зауваження 2. Варто спецiально роз’яснити, чому в частинах 1 i 3 вказується на iррацiо-
нальнiсть повороту кола, а в частинi 2 не вказується. Справа в тому, що коли перекладання
iнтервалiв є вiдображенням першого повернення на об’єднання дуг для iррацiонального пово-
роту кола, то мале збурення параметрiв такої системи дає перекладання iнтервалiв з тiєю ж
самою схемою, яке є вiдображенням першого повернення на об’єднання дуг для рацiонального
повороту кола (близького до вихiдного iррацiонального). Вiдповiдно, кожна така схема (i згiдно
з третiм твердженням теореми це правильно для всiх ротацiйних схем) дозволяє як iррацiональ-
нi, так i рацiональнi (у вищевказаному сенсi) перекладання. Але, з iншого боку, iснують схеми
перекладань iнтервалiв, якi дозволяють виключно рацiональнi перекладання, а саме, схеми, що
мiстять ланцюжок циклiв вигляду\Biggl\{ \Biggl[
\alpha 1
\alpha 2
\Biggr]
;
\Biggl[
\alpha 2
\alpha 3
\Biggr]
; . . . ;
\Biggl[
\alpha m
\alpha 1
\Biggr] \Biggr\}
чи просто цикл вигляду
\biggl[
\alpha
\alpha
\biggr]
. Власне такi перiодичнi ланцюжки циклiв у схемi є квiнтесенцiєю
рацiональних перекладань: одна дуга проходить певну траєкторiю по колу, зрештою поверта-
ючись на себе. Дуальна до такої схема ПАI мiстить пару циклiв\Biggl\{ \Biggl[
\alpha m . . . \alpha 1
\varnothing
\Biggr]
;
\Biggl[
\varnothing
\alpha m . . . \alpha 1
\Biggr] \Biggr\}
(тут \varnothing позначає вiдсутнiсть елементiв у рядку) i очевидно не є додатною. Такi схеми перекла-
дань iнтервалiв мають вiд’ємне повне покручення, i їхнi натуральнi розширення не утворюють
жодних трансляцiйних поверхонь. Тому ми не називаємо подiбнi схеми та перекладання iн-
тервалiв iз ними ротацiйними, хоча такi перекладання можуть бути вiдображеннями першого
повернення для поворотiв кола (але лише рацiональних!) на певнi об’єднання дуг.
4. Доведення першої частини теореми. 4.1. Фiнiтнiсть першого повернення. Нагада-
ємо, що собою являє вiдображення першого повернення для динамiчної системи з дискретним
часом на пiдмножину її фазового простору. Нехай таку динамiчну систему задано вiдображен-
ням f : X \rightarrow X, а непорожня пiдмножина \Gamma \subset X має таку властивiсть: для кожної точки
x \in \Gamma iснує натуральне число n таке, що fn(x) \in \Gamma , тобто траєкторiя точки x повертається на
множину \Gamma через певний час n. Позначимо як n(x, f,\Gamma ) час першого повернення точки x пiд
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 453
дiєю f на множину \Gamma , тобто найменше з таких чисел: f i(x) \not \in \Gamma для всiх 1 \leq i < n(x, f,\Gamma ),
а fn(x,f,\Gamma )(x) \in \Gamma . Вiдображення f\Gamma : x \mapsto \rightarrow fn(x,f,\Gamma )(x) i називають вiдображенням першого
повернення для f на \Gamma . Очевидно, що воно задає вже на цiй пiдмножинi нову, iндуковану,
динамiчну систему з дискретним часом f\Gamma : \Gamma \rightarrow \Gamma .
Згiдно з означенням, для заданого числа n \geq 1 усi точки x \in \Gamma , для яких n(x, f,\Gamma ) = n,
складають множину \Gamma n = \Gamma \cap f - n(\Gamma )\setminus f - (n - 1)(\Gamma )\setminus . . . \setminus f - 1(\Gamma ); має мiсце диз’юнктний розклад
\Gamma =
\bigcup +\infty
n=1
\Gamma n, \Gamma n \cap \Gamma m = \varnothing при n \not = m, i спiввiдношення f\Gamma (x) = fn(x) для всiх x \in \Gamma n,
n \geq 1.
Покажемо, що у випадку повороту кола R = RM,L перше повернення на об’єднання скiн-
ченної кiлькостi його дуг \Gamma завжди є фiнiтним, тобто множина часiв першого повернення усiх
точок цього об’єднання \{ n(x, f,\Gamma )| x \in \Gamma \} є обмеженою.
Якщо число обертання є рацiональним, тобто \rho = M/L = p/q, де p i q — взаємно простi
натуральнi числа, то має мiсце тотожнiсть Rq(x) \equiv x, i тому n(x,R,\Gamma ) \leq q для всiх x на
колi, а отже, вiдображення першого повернення для рацiонального повороту кола на будь-яку
пiдмножину (не лише на об’єднання дуг) завжди є визначеним i фiнiтним.
Нехай тепер число обертання \rho є iррацiональним. У цьому випадку траєкторiя кожної точки
x є скрiзь щiльною на колi, а отже для кожного \delta > 0 iснує натуральне число n0, для якого на
колi не залишається жодного промiжку довжини \delta , вiльного вiд точок зi скiнченного вiдрiзка
цiєї траєкторiї (Ri(x))n0
i=1, причому, оскiльки всi траєкторiї повороту кола влаштованi однаково,
це n0 не залежить вiд x. Взявши за \delta довжину найкоротшої дуги з об’єднання \Gamma , отримаємо
обмеження n(x,R,\Gamma ) \leq n0 для всiх x на колi.
Ми показали, що перше повернення для R на \Gamma справдi є фiнiтним: \Gamma =
\bigcup n0
n=1 \Gamma n для
певного скiнченного n0. А оскiльки перетин чи об’єднання двох скiнченних об’єднань дуг
також є скiнченним об’єднанням дуг, то кожна з множин \Gamma n так само є об’єднанням скiнченної
кiлькостi дуг, на кожнiй з яких вiдображення першого повернення R\Gamma є зсувом (на вiдстань
nM ). Iнтерпретуючи дуги на колi як iнтервали на дiйснiй прямiй у межах певного промiжку
[x0, x0 + L), одержуємо таке твердження.
Твердження 2. Для будь-якого повороту кола вiдображення першого повернення на будь-
яке об’єднання скiнченної кiлькостi дуг являє собою перекладання iнтервалiв.
Якщо поворот кола був iррацiональним, то отримане перекладання iнтервалiв завжди є
незвiдним внаслiдок мiнiмальностi такого повороту.
4.2. Ротацiйнiсть першого повернення. Нехай дано iррацiональний поворот кола (5),
(6) i скiнченне об’єднання дуг \Gamma , яке будемо iнтерпретувати як набiр попарно неперетинних
напiввiдкритих промiжкiв на дiйснiй прямiй у межах [x0, x0 + L). Згiдно з твердженням 2,
вiдображення першого повернення R\Gamma : \Gamma \rightarrow \Gamma є перекладанням iнтервалiв. Покажемо, що
схема цього перекладання iнтервалiв, розглянутого як ПАI, є ротацiйною згiдно з означенням,
тобто дуальна до неї схема ПАI також є схемою перекладання iнтервалiв.
Для того щоб записати схему ПАI для перекладання iнтервалiв R\Gamma , позначимо кожний
з iнтервалiв у цьому перекладаннi окремим символом, склавши з них алфавiт \scrA . Множи-
на \Gamma є, з одного боку, об’єднанням усiх попарно неперетинних iнтервалiв I\alpha \mathrm{b}, \alpha \in \scrA , а з
iншого — об’єднанням їхнiх (також попарно неперетинних) образiв I\alpha \mathrm{e} = \Gamma (I\alpha \mathrm{b}), \alpha \in \scrA .
Кожний окремий промiжок у складi \Gamma у свою чергу розбивається, з одного боку, на декiлька
початкових iнтервалiв I\alpha 1\mathrm{b}, . . . , I\alpha m\mathrm{b} (рахуємо злiва направо), а з iншого — на кiлька кiнцевих
iнтервалiв I\beta 1\mathrm{e}, . . . , I\beta n\mathrm{e} (так само злiва направо); у схемi \sigma цьому промiжку вiдповiдає цикл
(\alpha 1\mathrm{b}, . . . , \alpha m\mathrm{b}, \beta n\mathrm{e}, . . . , \beta 1\mathrm{e}), \{ \alpha i\} mi=1, \{ \beta j\} nj=1 \subset \scrA , n,m \geq 1. Загальний масив країв iнтерва-
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
454 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
лiв \bfx \in \BbbR \=\scrA , де x\alpha \mathrm{b} — лiвий край початкового iнтервалу I\alpha \mathrm{b}, а x\beta \mathrm{e} — правий край кiнцевого
iнтервалу I\beta \mathrm{e}, \alpha , \beta \in \scrA , складає дiйсну компоненту ПАI (\sigma ,\bfx ).
Усi краї iнтервалiв заданого перекладання iнтервалiв наочно роздiляються на чотири типи:
тип L (left) — лiвi краї окремих промiжкiв у складi \Gamma , у вищенаведеному прикладi це точка
x\alpha 1\mathrm{b}; тип R (right) — правi краї окремих промiжкiв у складi \Gamma , у вищенаведеному прикладi це
x\beta 1\mathrm{e}; тип MB (middle beginning) — точки, у яких з’єднуються якiсь два початковi iнтервали, у
прикладi вище це x\alpha i\mathrm{b}, i \not = 1; тип ME (middle ending) — точки, у яких з’єднуються якiсь два
кiнцевi iнтервали, у прикладi вище це x\beta j\mathrm{e}, j \not = 1. З точки зору ПАI, перелiченi типи мають
не самi дiйснi числа x\=\xi , а їхнi iндекси: \=\xi \in \=\scrA має тип L, якщо \=\xi = \xi \mathrm{b} i \sigma - 1(\=\xi ) = \eta \mathrm{e}; тип R,
якщо \=\xi = \xi \mathrm{e} i \sigma - 1(\=\xi ) = \eta \mathrm{b}; тип MB, якщо \=\xi = \xi \mathrm{b} i \sigma - 1(\=\xi ) = \eta \mathrm{b}; тип ME, якщо \=\xi = \xi \mathrm{e} i
\sigma - 1(\=\xi ) = \eta \mathrm{e}, для якихось \xi , \eta \in \scrA .
Варто зауважити, що кожен iз окремих промiжкiв у складi \Gamma (яким вiдповiдають окремi
цикли у складi перестановки \sigma ) має рiвно один край типу L i рiвно один край типу R (це
власне його лiвий i правий краї вiдповiдно), тодi як країв iнтервалiв типiв MB i ME на ньому
може бути будь-яка скiнченна кiлькiсть, зокрема нульова.
Розглянемо довiльний край x\xi 1\mathrm{b} типу MB (а отже, \sigma - 1(\xi 1\mathrm{b}) = \eta 1\mathrm{b}, \xi 1, \eta 1 \in \scrA ) i про-
слiдкуємо за динамiчними траєкторiями його лiвого x - \xi 1\mathrm{b} = (x\xi 1\mathrm{b} - \varepsilon , x\xi 1\mathrm{b}), \varepsilon \rightarrow 0, i правого
x+\xi 1\mathrm{b} = (x\xi 1\mathrm{b}, x\xi 1\mathrm{b} + \varepsilon ), \varepsilon \rightarrow 0, iнфiнiтезимальних пiвоколiв. (Очевидно, що для достатньо ма-
лого конкретного \varepsilon > 0 послiдовнi образи таких пiвоколiв пiд дiєю R\Gamma не накривають жодного
з країв протягом достатньо довгого часу, зокрема залишаючись цiлими iнтервалами, а отже,
iнфiнiтезимальний розгляд є коректним.)
Iнтервал I\xi 1\mathrm{b}, лiвим краєм якого є x\xi 1\mathrm{b}, вiдображається R\Gamma на iнтервал I\xi 1\mathrm{e}, вiдповiдно
правий пiвокiл x+\xi 1\mathrm{b} вiдображається на правий пiвокiл лiвого краю I\xi 1\mathrm{e}, тобто на x+\sigma (\xi 1\mathrm{e}). Те-
пер є два варiанти: або цей край має тип ME, тобто \sigma (\xi 1\mathrm{e}) = \eta \ast \mathrm{e}, \eta \ast \in \scrA , або тип L, тобто
\sigma (\xi 1\mathrm{e}) = \xi 2\mathrm{b}, \xi 2 \in \scrA . У першому випадку ми зупиняємося, а в другому продовжуємо слiдку-
вати за траєкторiєю пiвоколу. Аналогiчно до початкового кроку, x+\sigma (\xi 1\mathrm{e}) = x+\xi 2\mathrm{e} вiдображається
на x+\sigma (\xi 2\mathrm{e}), i знову маємо два варiанти: або край x\sigma (\xi 2\mathrm{e}) має тип ME, тобто \sigma (\xi 2\mathrm{e}) = \eta \ast \mathrm{e},
\eta \ast \in \scrA , або тип L, тобто \sigma (\xi 2\mathrm{e}) = \xi 3\mathrm{b}, \xi 3 \in \scrA . У першому випадку зупиняємося, а в дру-
гому продовжуємо слiдкувати. На якомусь кроцi процес зупиниться, тому що країв типу L
скiнченна кiлькiсть, а вiдображення R\Gamma не має перiодичних траєкторiй внаслiдок iррацiональ-
ностi вихiдного повороту кола. Отже, пiсля зупинки ми одержимо послiдовнiсть iндексiв \xi 1\mathrm{b},
\xi 2\mathrm{b} = \sigma (\xi 1\mathrm{b}), . . . , \xi m\mathrm{b} = \sigma (\xi m - 1\mathrm{b}), \eta \ast \mathrm{e} = \sigma (\xi m\mathrm{b}) i вiдповiдну послiдовнiсть пiвоколiв x+\xi 1\mathrm{b},
x+\xi 2\mathrm{b} = R\Gamma (x
+
\xi 1\mathrm{b}
), . . . , x+\xi m\mathrm{b} = R\Gamma (x
+
\xi m - 1\mathrm{b}
), x+\eta \ast \mathrm{e} = R\Gamma (x
+
\xi m\mathrm{b}), де краї x\xi 1\mathrm{b}, x\xi 2\mathrm{b}, . . . , x\xi m\mathrm{b}, x\eta \ast \mathrm{e}
мають типи MB, L, . . . , L, ME вiдповiдно; \xi 1, . . . , \xi m, \eta \ast \in \scrA , m \geq 1.
Розглянемо тепер траєкторiю лiвого пiвокола того ж самого початкового краю типу MB.
Iнтервал I\eta 1\mathrm{b}, правим краєм якого є x\xi 1\mathrm{b}, вiдображається R\Gamma на iнтервал I\eta 1\mathrm{e}, вiдповiдно лiвий
пiвокiл x - \xi 1\mathrm{b} вiдображається на лiвий пiвокiл правого краю I\eta 1\mathrm{e}, тобто власне на x - \eta 1\mathrm{e}. Є два
варiанти: або цей край має тип ME, тобто \eta 1\mathrm{e} = \sigma (\xi \ast \mathrm{e}), \xi \ast \in \scrA , або тип R, тобто \eta 1\mathrm{e} = \sigma (\eta 2\mathrm{b}),
\eta 2 \in \scrA . У першому випадку ми зупиняємося, а в другому продовжуємо слiдкувати за траєк-
торiєю пiвоколу. Аналогiчно до початкового кроку, iнтервал I\eta 2\mathrm{b}, правим краєм якого є x\eta 1\mathrm{e},
вiдображається на iнтервал I\eta 2\mathrm{e}, вiдповiдно x - \eta 1\mathrm{e} вiдображається на x - \eta 2\mathrm{e}. Знову два випадки:
або x\eta 2\mathrm{e} має тип ME, тобто \eta 2\mathrm{e} = \sigma (\xi \ast \mathrm{e}), \xi \ast \in \scrA , або тип R, тобто \eta 2\mathrm{e} = \sigma (\eta 3\mathrm{b}), \eta 3 \in \scrA . У
першому випадку зупиняємося, а в другому продовжуємо слiдкувати. На якомусь кроцi процес
зупиниться, оскiльки R\Gamma не має перiодичних траєкторiй, i ми зрештою одержимо послiдовнiсть
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 455
iндексiв \xi 1\mathrm{b}, \eta 1\mathrm{b} = \sigma - 1(\xi 1\mathrm{b}), \eta 2\mathrm{b} = \sigma - 1(\eta 1\mathrm{e}), . . . , \eta n\mathrm{b} = \sigma - 1(\eta n - 1\mathrm{b}) i послiдовнiсть пiвоколiв
x - \xi 1\mathrm{b}, x - \eta 1\mathrm{e} = R\Gamma (x
-
\xi 1\mathrm{b}
), x - \eta 2\mathrm{e} = R\Gamma (x
-
\eta 1\mathrm{e}) . . . , x
-
\eta n\mathrm{e} = R\Gamma (x
-
\eta n - 1\mathrm{e}), де краї x\xi 1\mathrm{b}, x\eta 1\mathrm{e}, . . . , x\eta n\mathrm{e}
мають типи MB, R, . . . , R, ME вiдповiдно; \eta 1, . . . , \eta n \in \scrA , n \geq 1.
Залишилося зазначити, що з необхiднiстю x\eta n\mathrm{e} = x\eta \ast \mathrm{e}, а отже, \eta \ast = \eta n. Чому це так?
Тому, що R\Gamma є вiдображенням першого повернення для повороту кола на об’єднання дуг \Gamma .
Поворот кола R є неперервним вiдображенням, а отже, пiд його дiєю лiвий i правий пiвоколи
кожної точки нiколи не роздiляються. Тому у момент, коли внутрiшня точка (така як край типу
MB) множини \Gamma вперше повертається у внутрiшню точку (край типу ME) множини \Gamma , її лiвий
та правий пiвоколи зустрiчаються знову, хоча до цього могли кiлька разiв пройти по межi
(краї типу L та R) множини \Gamma . Навiть бiльше, загальний час (у термiнах кiлькостi iтерацiй
R) повернення двох пiвоколiв вiд їх роздiлення в точцi x\xi 1\mathrm{b} до нової зустрiчi в точцi x\eta n\mathrm{e} є
однаковим для лiвого i для правого. Це означає наступне. Згадаємо, що кожний початковий
iнтервал I\alpha \mathrm{b} перекладання R\Gamma є пiдмножиною однiєї з множин \Gamma k точок, якi повертаються
на \Gamma рiвно за k iтерацiй повороту кола R, 1 \leq k \leq k0, i позначимо цей час k\alpha , \alpha \in \scrA .
Вiдповiдно, для дослiдженої вище траєкторiї правого пiвоколу x+\xi 1\mathrm{b} сумарний час до досягнення
ним точки x\eta n\mathrm{e} в термiнах кiлькостi iтерацiй R дорiвнює k\xi 1 + . . .+ k\xi m , а для лiвого пiвоколу
x - \xi 1\mathrm{b} цей час дорiвнює k\eta 1 + . . . + k\eta n . З огляду на зазначене вище, цi часи з необхiднiстю
є рiвними, тобто маємо
\sum m
i=1
k\xi i =
\sum n
j=1
k\eta j для кожного краю типу MB перекладання
iнтервалiв R\Gamma .
Можемо тепер виписати в явнiй формi перекладання iнтервалiв зi схемою ПАI, дуальною
до \sigma . Ця дуальна схема \sigma \ast складається з усiх циклiв (\xi 1\mathrm{b}, . . . , \xi m\mathrm{b}, \eta n\mathrm{e}, . . . , \eta 1\mathrm{e}), побудованих
для всiх країв типу MB у перекладаннi R\Gamma . Жоднi два рiзних iз цих циклiв не мають спiль-
них елементiв, бо перекладання є бiєктивним вiдображенням. З iншого боку, кожен елемент \=\scrA
входить до якогось iз цих циклiв, бо ми врахували всi точки типу MB. Точок типу ME є така
сама кiлькiсть, як i точок типу MB, а пiвокiл кожної з точок типiв L i R за певну кiлькiсть
iтерацiй необхiдно потрапляє в точку типу ME, i тому цi точки також усi враховано. Дуаль-
нiсть \sigma \ast до \sigma легко перевiрити за означенням (4) з огляду на спiввiдношення, одержанi при
дослiдженнi траєкторiй пiвоколiв краю x\xi 1\mathrm{b}. Щоб показати, що схема \sigma \ast є додатною, покла-
демо для кожного виписаного вище циклу y\xi i\mathrm{b} =
\sum i - 1
s=1
k\xi s , 1 \leq i \leq m, i y\eta j\mathrm{e} =
\sum j
t=1
k\eta t ,
1 \leq j \leq n, визначивши тим самим вектор країв \bfy , дозволений схемою \sigma \ast в силу рiвно-
стей
\sum m
i=1
k\xi i =
\sum n
j=1
k\eta j . Вiдповiдний до нього вектор довжин складається з додатних
(i навiть цiлочислових) компонент k\xi , \xi \in \scrA , а отже, ПАI (\sigma \ast ,\bfy ) дiйсно є перекладанням
iнтервалiв.
Частину 1 теореми 1 доведено.
Зауваження 3. Для доведення зазначеного твердження нами було для перекладання iн-
тервалiв, iндукованого на пiдмножинi кола його поворотом, конструктивно побудовано ду-
альну систему перекладання iнтервалiв з використанням вiдрiзкiв часу в ролi просторових
вiдрiзкiв.
5. Доведення другої частини теореми. У цьому пунктi ми доведемо частину 2 теоре-
ми 1, виклавши алгоритм побудови за даним ротацiйним перекладанням iнтервалiв такого
iррацiонального повороту кола i такого об’єднання дуг, що вiдповiдне вiдображення першого
повернення є еквiвалентним до вихiдного перекладання з точнiстю до зсуву.
Отже, нехай дано незвiдне ротацiйне перекладання iнтервалiв (\sigma ,\bfx ). Оскiльки все одно
йдеться про еквiвалентнiсть перекладань з точнiстю до зсуву, то буде достатньо вiд початку
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
456 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
розглядати плаваюче ПАI (\sigma ,\bfv ), тобто обмежитися розглядом довжин iнтервалiв i не зважати
на координати їх країв.
Ми будемо послiдовно застосовувати до нього два типи операцiй: перший — це зворотний
крок iндукцiї (вiн продукуватиме нову динамiчну систему, для якої вихiдна є вiдображенням
першого повернення), другий — це злиття двох сусiднiх iнтервалiв в один (вiн не змiнюватиме
динамiчну систему взагалi, лише зменшуватиме кiлькiсть iнтервалiв у перекладаннi).
5.1. Елементарнi кроки iндукцiї. Нагадаємо, що таке чотири елементарнi iндукцiйнi кроки
\Pi \mathrm{r}\mathrm{b}
\alpha \beta , \Pi
\mathrm{r}\mathrm{e}
\alpha \beta , \Pi
\mathrm{l}\mathrm{b}
\alpha \beta , \Pi
\mathrm{l}\mathrm{e}
\alpha \beta , означенi в [1]. Це є операцiї перетворення, якi можуть бути застосовними
до ПАI (i, зокрема, до перекладання iнтервалiв) або окремо до їх схем i узагальнюють класич-
нi iндукцiйнi кроки Розi – Вiча. За сутнiстю їх дiї ми називаємо цi чотири кроки „обрiзання
початкового iнтервалу справа”, „обрiзання кiнцевого iнтервалу справа”, „обрiзання початкового
iнтервалу злiва” i „обрiзання кiнцевого iнтервалу злiва” вiдповiдно. Загальнi формули для
чотирьох елементарних крокiв iндукцiї наведено в п. 7 роботи [1], також там пояснено, що
кроки \Pi \mathrm{r}\mathrm{b}
\alpha \beta i \Pi \mathrm{r}\mathrm{e}
\alpha \beta є застосовними до схеми ПАI \sigma за умови \sigma (\alpha \mathrm{b}) = \beta \mathrm{e}, а кроки \Pi \mathrm{l}\mathrm{b}
\alpha \beta та \Pi \mathrm{l}\mathrm{e}
\alpha \beta —
за умови \sigma (\beta \mathrm{e}) = \alpha \mathrm{b}. У термiнах циклiв перестановки \sigma цi операцiї дiють таким чином: крок
\Pi \mathrm{r}\mathrm{b}
\alpha \beta (кроки \Pi \mathrm{r}\mathrm{e}
\alpha \beta , \Pi \mathrm{l}\mathrm{b}
\alpha \beta , \Pi \mathrm{l}\mathrm{e}
\alpha \beta ) перемiщує елемент \beta \mathrm{e} (елементи \alpha \mathrm{b}, \beta \mathrm{e}, \alpha \mathrm{b}) з його поточної
позицiї у позицiю просто перед \alpha \mathrm{e} (просто пiсля \beta \mathrm{b}, просто пiсля \alpha \mathrm{e}, просто перед \beta \mathrm{b}).
У векторi довжин \bfv змiнюється одна компонента: кроки \Pi \mathrm{r}\mathrm{b}
\alpha \beta i \Pi \mathrm{l}\mathrm{b}
\alpha \beta вiднiмають величину v\beta
вiд компоненти v\alpha , а кроки \Pi \mathrm{r}\mathrm{e}
\alpha \beta i \Pi \mathrm{l}\mathrm{e}
\alpha \beta — величину v\alpha вiд компоненти v\beta . Зворотнi кроки
(\Pi \mathrm{r}\mathrm{b}
\alpha \beta )
- 1, (\Pi \mathrm{r}\mathrm{e}
\alpha \beta )
- 1, (\Pi \mathrm{l}\mathrm{b}
\alpha \beta )
- 1, (\Pi \mathrm{l}\mathrm{e}
\alpha \beta )
- 1 є застосовними до схеми ПАI \sigma за умов \sigma (\beta \mathrm{e}) = \alpha \mathrm{e},
\sigma (\beta \mathrm{b}) = \alpha \mathrm{b}, \sigma (\alpha \mathrm{e}) = \beta \mathrm{e}, \sigma (\alpha \mathrm{b}) = \beta \mathrm{b} вiдповiдно. На довжинах: зворотнi кроки (\Pi \mathrm{r}\mathrm{b}
\alpha \beta )
- 1 i
(\Pi \mathrm{l}\mathrm{b}
\alpha \beta )
- 1 додають величину v\beta до компоненти v\alpha , а кроки (\Pi \mathrm{r}\mathrm{e}
\alpha \beta )
- 1 i (\Pi \mathrm{l}\mathrm{e}
\alpha \beta )
- 1 — величину v\alpha
до компоненти v\beta .
Пояснимо тепер, як цi кроки працюють щодо (плаваючих) перекладань iнтервалiв, викори-
ставши дворядковий запис для циклiв їхнiх схем. Фактично точно так само працює класична
iндукцiя Розi – Вiча, але вона дiє на одному промiжку i лише з правого його краю, тодi як ми
маємо справу з перекладаннями iнтервалiв на багатьох промiжках i застосовуємо iндукцiйнi
кроки з обох країв.
Для того щоб перекладання iнтервалiв залишилося перекладанням iнтервалiв пiсля засто-
сування кроку iндукцiї чи зворотного кроку iндукцiї, потрiбно додатково до описаних вище
умов забезпечити, щоб усi компоненти вектора довжин залишилися додатними, а також щоб
схема залишилася непокрученою (тобто кожен цикл у нiй мав число покручення нуль — був
„дворядковим”, див. означення у п. 2).
Розглянемо докладно крок \Pi \mathrm{r}\mathrm{b}
\alpha \beta . Умова його застосування \sigma (\alpha \mathrm{b}) = \beta \mathrm{e} означає, що початко-
вий I\alpha \mathrm{b} i кiнцевий I\beta \mathrm{e} iнтервали прилягають до правого кiнця одного й того самого промiжку
J, тобто у дворядковому записi один iз циклiв схеми має вигляд
\biggl[
. . . \alpha
. . . \beta
\biggr]
. Оскiльки \Pi \mathrm{r}\mathrm{b}
\alpha \beta вiд-
нiмає вiд довжини v\alpha довжину v\beta (вiдрiзаючи кiнцевий iнтервал I\beta \mathrm{e} вiд промiжку, при цьому
„обрiзаючи початковий iнтервал I\alpha \mathrm{b} справа” на v\beta ), то для додатностi одержаного вектора
довжин необхiдною i достатньою умовою є нерiвнiсть v\alpha > v\beta , тобто I\alpha \mathrm{b} має бути довшим за
I\beta \mathrm{e}. Якщо ця умова виконується, то iнтервал I\beta \mathrm{e} не може бути єдиним кiнцевим на промiжку
J, бо сума довжин кiнцевих iнтервалiв на промiжку завжди дорiвнює сумi довжин початкових,
i тому злiва до I\beta \mathrm{e} прилягає якийсь iнший кiнцевий iнтервал I\gamma \mathrm{e}, тобто \sigma (\beta \mathrm{e}) = \gamma \mathrm{e} для якогось
\gamma \in \scrA . У дворядковому записi схема перетвоюється таким чином (ми показуємо лише задiянi
у змiнi цикли, усi решта циклiв не змiнюються):
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 457
\Pi \mathrm{r}\mathrm{b}
\alpha \beta :
\Biggl[
. . . \alpha
. . . \gamma \beta
\Biggr]
,
\Biggl[
. . .
. . . \alpha . . .
\Biggr]
\mapsto \rightarrow
\Biggl[
. . . \alpha
. . . \gamma
\Biggr]
,
\Biggl[
. . .
. . . \alpha \beta . . .
\Biggr]
.
(Тут перший цикл вiдповiдає промiжку J, а другий — тому промiжку, на якому лежить кiнцевий
iнтервал I\alpha \mathrm{e}; це може бути той самий промiжок J, у якому випадку маємо
\Pi \mathrm{r}\mathrm{b}
\alpha \beta :
\Biggl[
. . . \alpha
. . . \alpha . . . \gamma \beta
\Biggr]
\mapsto \rightarrow
\Biggl[
. . . \alpha
. . . \alpha \beta . . . \gamma
\Biggr]
.
Якщо \gamma = \alpha , то схема \sigma пiд дiєю \Pi \mathrm{r}\mathrm{b}
\alpha \beta не змiнюється, змiнюється лише довжина v\alpha .) У всiх
випадках за результатом дiї \Pi \mathrm{r}\mathrm{b}
\alpha \beta промiжок J укорочується справа на v\beta — довжину iнтервалу
I\beta \mathrm{e}. Iнтервали I\alpha \mathrm{b} та I\alpha \mathrm{e} також укорочуються справа на v\beta , при цьому iнтервал I\beta \mathrm{e} займає
нове мiсце справа вiд укороченого на його довжину I\alpha \mathrm{e}. Також бачимо, що в усiх випадках усi
цикли залишаються непокрученими, i це правильно для всiх (прямих!) елементарних крокiв
iндукцiї.
Легко бачити, що динамiчна система перекладання iнтервалiв, одержана в результатi опи-
саної дiї \Pi \mathrm{r}\mathrm{b}
\alpha \beta на (\sigma ,\bfv ), є нiчим iншим як вiдображенням першого повернення для вихiдної
динамiчної системи на об’єднання промiжкiв, де промiжок J укорочено справа на v\beta . Справдi,
всi точки цього об’єднання повертаються на нього за час 1, крiм точок iнтервалу I\beta \mathrm{b}, якi повер-
таються за час 2, — вони спочатку потрапляють на вiдрiзаний iнтервал I\beta \mathrm{e} вихiдної динамiчної
системи, а потiм вiдображення перекидає їх на iнтервал I\beta \mathrm{e} одержаної динамiчної системи,
який у вихiднiй був правою частиною iнтервалу I\alpha \mathrm{e}.
Решта три iндукцiйних кроки дiють аналогiчним чином, i так само результатом їх дiї кожно-
го разу є вiдображення першого повернення для вихiдної динамiчної системи на об’єднання
промiжкiв, один iз яких укорочено справа чи злiва. Для наочностi опишемо їх дiю на схемах
так, як це зроблено вище для кроку \Pi \mathrm{r}\mathrm{b}
\alpha \beta , зауваживши, що крок \Pi \mathrm{l}\mathrm{b}
\alpha \beta переводить перекладання
iнтервалiв у перекладання iнтервалiв тодi й лише тодi, коли v\alpha > v\beta , а кроки \Pi \mathrm{r}\mathrm{e}
\alpha \beta та \Pi \mathrm{l}\mathrm{e}
\alpha \beta —
тодi й лише тодi, коли v\alpha < v\beta :
\Pi \mathrm{r}\mathrm{e}
\alpha \beta :
\Biggl[
. . . \gamma \alpha
. . . \beta
\Biggr]
,
\Biggl[
. . . \beta . . .
. . .
\Biggr]
\mapsto \rightarrow
\Biggl[
. . . \gamma
. . . \beta
\Biggr]
,
\Biggl[
. . . \beta \alpha . . .
. . .
\Biggr]
,
\Pi \mathrm{l}\mathrm{b}
\alpha \beta :
\Biggl[
\alpha . . .
\beta \gamma . . .
\Biggr]
,
\Biggl[
. . .
. . . \alpha . . .
\Biggr]
\mapsto \rightarrow
\Biggl[
\alpha . . .
\gamma . . .
\Biggr]
,
\Biggl[
. . .
. . . \beta \alpha . . .
\Biggr]
,
\Pi \mathrm{l}\mathrm{e}
\alpha \beta :
\Biggl[
\alpha \gamma . . .
\beta . . .
\Biggr]
,
\Biggl[
. . . \beta . . .
. . .
\Biggr]
\mapsto \rightarrow
\Biggl[
\gamma . . .
\beta . . .
\Biggr]
,
\Biggl[
. . . \alpha \beta . . .
. . .
\Biggr]
.
Кожен iз цих крокiв зменшує бiльшу з двох довжин v\alpha , v\beta на меншу i не змiнює всi iншi
довжини.
Зворотнi елементарнi кроки iндукцiї (\Pi \mathrm{r}\mathrm{b}
\alpha \beta )
- 1, (\Pi \mathrm{r}\mathrm{e}
\alpha \beta )
- 1, (\Pi \mathrm{l}\mathrm{b}
\alpha \beta )
- 1, (\Pi \mathrm{l}\mathrm{e}
\alpha \beta )
- 1 є застосовними
до схеми ПАI \sigma за умов \sigma (\beta \mathrm{e}) = \alpha \mathrm{e}, \sigma (\beta \mathrm{b}) = \alpha \mathrm{b}, \sigma (\alpha \mathrm{e}) = \beta \mathrm{e}, \sigma (\alpha \mathrm{b}) = \beta \mathrm{b} вiдповiдно (див.
твердження 3 з [1]). Необхiдними i достатнiми умовами непокрученостi схеми, одержаної зi
схеми перекладання iнтервалiв \sigma зворотними кроками iндукцiї (\Pi \mathrm{r}\mathrm{b}
\alpha \beta )
- 1, (\Pi \mathrm{r}\mathrm{e}
\alpha \beta )
- 1, (\Pi \mathrm{l}\mathrm{b}
\alpha \beta )
- 1,
(\Pi \mathrm{l}\mathrm{e}
\alpha \beta )
- 1, є наявнiсть елемента \gamma \in \scrA , для якого виконуються спiввiдношення \sigma (\alpha \mathrm{b}) = \gamma \mathrm{e},
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
458 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
\sigma - 1(\beta \mathrm{e}) = \gamma \mathrm{b}, \sigma - 1(\alpha \mathrm{b}) = \gamma \mathrm{e} i \sigma (\beta \mathrm{e}) = \gamma \mathrm{b} вiдповiдно. Оскiльки дiя крокiв (\Pi \mathrm{r}\mathrm{b}
\alpha \beta )
- 1 i (\Pi \mathrm{l}\mathrm{b}
\alpha \beta )
- 1
на дiйсну компоненту ПАI \bfv додає довжину v\beta до v\alpha , а дiя крокiв (\Pi \mathrm{r}\mathrm{e}
\alpha \beta )
- 1 i (\Pi \mathrm{l}\mathrm{e}
\alpha \beta )
- 1 —
довжину v\alpha до v\beta , то за умови додатностi вихiдного ПАI результуючий також є додатним: одна
з довжин лише збiльшується.
Твердження 3. Перекладання iнтервалiв, одержане з ротацiйного перекладання iнтерва-
лiв шляхом застосування до нього елементарного кроку iндукцiї , також є ротацiйним.
Доведення. Згiдно з твердженням 6 з [1], кроки iндукцiї не змiнюють повного покручення
схеми, отже, в даному випадку воно залишається нульовим. Згiдно з теоремою 1 з [1], пiд час
перетворення схеми ПАI пiд дiєю елементарного кроку iндукцiї дуальна до неї схема перетво-
рюється пiд дiєю зворотного кроку. А оскiльки дiя зворотного кроку iндукцiї на додатний ПАI
лише збiльшує одну з довжин на величину iншої, то дуальна схема залишається додатною.
Твердження доведено.
Аналогiчне твердження щодо зворотних крокiв iндукцiї є, взагалi кажучи, хибним, що
доводить наступний контрприклад.
Розглянемо схему \sigma =
\biggl\{ \biggl[
\gamma \alpha \delta
\delta \beta
\biggr]
,
\biggl[
\beta
\alpha \gamma
\biggr] \biggr\}
. Вона має нульове число покручення i є
додатною: наприклад, вектор довжин \bfv = (v\alpha , v\beta , v\gamma , v\delta ) = (1, 2, 1, 1) є дозволеним. Дуальна
до неї схема \sigma \ast =
\biggl\{ \biggl[
\alpha \beta
\gamma \beta \delta
\biggr]
,
\biggl[
\delta \gamma
\alpha
\biggr] \biggr\}
так само має нульове покручення i так само є додат-
ною: наприклад, вектор довжин \bfw = (w\alpha , w\beta , w\gamma , w\delta ) = (2, 1, 1, 1) є дозволеним. Отже, ПАI
(\sigma ,\bfv ) є ротацiйним перекладанням iнтервалiв. Зворотний елементарний крок iндукцiї (\Pi \mathrm{l}\mathrm{e}
\gamma \alpha )
- 1
є застосовним до нього, i одержана при цьому схема \sigma \prime =
\biggl\{ \biggl[
\alpha \delta
\delta \beta
\biggr]
,
\biggl[
\gamma \beta
\alpha \gamma
\biggr] \biggr\}
знову ж таки має
покручення нуль i є додатною: вектор довжин \bfv = (1, 2, 1, 1) перетворюється на \bfv \prime = (2, 2, 1, 1).
Вiдповiдно, одержаний ПАI (\sigma \prime ,\bfv \prime ) = (\Pi \mathrm{l}\mathrm{e}
\gamma \alpha )
- 1(\sigma ,\bfv ) є перекладанням iнтервалiв. Але це пере-
кладання не є ротацiйним: дуальна до \sigma \prime схема (\sigma \prime )\ast = \Pi \mathrm{l}\mathrm{e}
\alpha \gamma \sigma
\ast =
\biggl\{ \biggl[
\beta
\gamma \beta \delta
\biggr]
,
\biggl[
\delta \alpha \gamma
\alpha
\biggr] \biggr\}
хоча i має покручення нуль, але вочевидь не є додатною, бо дозволенi нею вектори довжин
\bfu = (u\alpha , u\beta , u\gamma , u\delta ) визначаються умовою u\gamma + u\delta = 0.
5.2. Операцiя злиття iнтервалiв. Якщо у перекладаннi iнтервалiв якiсь два сусiднi iн-
тервали зсуваються на однакову вiдстань, то їх природно злити в один: динамiчна система при
цьому не змiниться. Така ситуацiя має мiсце тодi, коли \sigma (\alpha \mathrm{b}) = \beta \mathrm{b}, \sigma (\beta \mathrm{e}) = \alpha \mathrm{e} для якихось
\alpha \not = \beta . Означимо операцiю злиття iнтервалiв \Sigma \alpha \beta , яка є застосовною до ПАI (\sigma ,\bfv ) за вище-
зазначеної умови на схему \sigma i дiє таким чином: з алфавiту \scrA вилучається символ \beta , елементи
\beta \mathrm{b} i \beta \mathrm{e} вилучаються з тих циклiв, до яких вони належали, а довжина v\alpha збiльшується на
довжину v\beta .
Формально \Sigma \alpha \beta (\sigma ,\bfv ) = (\sigma \prime ,\bfv \prime ), де \sigma \prime є перестановкою на зменшеному подвоєному алфавiтi
\=\scrA \prime = \scrA \prime \times \{ \mathrm{b}, \mathrm{e}\} , \scrA \prime = \scrA \setminus \{ \beta \} , яка задається такими спiввiдношеннями: у випадку \sigma (\beta \mathrm{b}) \not = \beta \mathrm{e}
маємо \sigma \prime (\alpha \mathrm{b}) = \sigma (\beta \mathrm{b}), \sigma \prime (\sigma - 1(\beta \mathrm{e})) = \alpha \mathrm{e} i \sigma \prime (\=\xi ) = \sigma (\=\xi ) для \=\xi \in \=\scrA \prime \setminus \{ \alpha \mathrm{b}, \sigma - 1(\beta \mathrm{e})\} , а у випадку
\sigma (\beta \mathrm{b}) = \beta \mathrm{e} маємо \sigma (\alpha \mathrm{b}) = \alpha \mathrm{e} i \sigma \prime (\=\xi ) = \sigma (\=\xi ) для \=\xi \in \=\scrA \prime \setminus \{ \alpha \mathrm{b}\} ; новий вектор довжин \bfv \prime \in \BbbR \scrA \prime
задається спiввiдношеннями v\prime \alpha = v\alpha + v\beta i v\prime \xi = v\xi для \xi \in \scrA \prime \setminus \{ \alpha \} .
Зауважимо, що для ротацiйної схеми \sigma випадок \sigma (\beta \mathrm{b}) = \beta \mathrm{e} є неможливим, тому що
з цього спiввiдношення випливає спiввiдношення \sigma \ast (\beta \mathrm{e}) = \beta \mathrm{e} для дуальної схеми \sigma \ast , яке
робить останню завiдомо не додатною: кожен дозволений схемою \sigma \ast вектор довжин \bfw мiстить
компоненту w\beta = 0.
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 459
Умова \sigma (\alpha \mathrm{b}) = \beta \mathrm{b}, \sigma (\beta \mathrm{e}) = \alpha \mathrm{e} застосовностi \Sigma \alpha \beta до \sigma є еквiвалентною умовi \sigma \ast (\alpha \mathrm{e}) =
\beta \mathrm{b}, \sigma \ast (\beta \mathrm{b}) = \alpha \mathrm{e} щодо дуальної схеми \sigma \ast . Це означає наявнiсть у складi \sigma \ast двохелементного
циклу
\biggl[
\beta
\alpha
\biggr]
. Застосування операцiї злиття \Sigma \alpha \beta до \sigma вилучає цей двохелементний цикл зi складу
\sigma \ast i замiнює \beta \mathrm{e} на \alpha \mathrm{e} у тому циклi \sigma \ast , до якого елемент \beta \mathrm{e} належав.
Твердження 4. Операцiя злиття iнтервалiв, застосована до ротацiйного перекладання
iнтервалiв, залишає його ротацiйним.
Доведення. З означення операцiї очевидно, що числа покручення циклiв не змiнюються,
лише один цикл в дуальнiй схемi повнiстю зникає, отже, повне покручення залишається нульо-
вим. Одна з довжин збiльшується на величину iншої, тож вектор довжин залишається додатним.
Для дуальної схеми до застосування операцiї iснував дозволений додатний вектор довжин \bfw iз
властивiстю w\alpha = w\beta , тому вектор \bfw \prime iз тими самими компонентами (лише з вилученою ком-
понентою w\beta ) вочевидь є додатним i дозволеним схемою, дуальною до одержаної в результатi
застосування операцiї \Sigma \alpha \beta .
Твердження доведено.
5.3. Iдея алгоритму перетворення ротацiйного перекладання iнтервалiв. Опишемо ал-
горитм дiй iз послiдовного перетворення довiльного незвiдного ротацiйного перекладання iн-
тервалiв, який зрештою приведе до побудови шуканого у частинi 2 теореми 1 вiдображення
першого повернення на колi. Нам буде зручно оперувати дуальними схемами. Iдея полягає в
тому, щоб, послiдовно застосовуючи елементарнi кроки iндукцiї до одного з циклiв у дуальнiй
схемi, довести його до двохелементного, пiсля чого злиттям вiдповiдних iнтервалiв виключити
з розгляду. Провiвши таку процедуру почергово щодо кожного з циклiв дуальної схеми, доки
їх є бiльше нiж один, ми зрештою отримаємо дуальну схему, яка складається лише з одного
циклу. На цьому алгоритм зупиниться, ми проаналiзуємо одержане перекладання iнтервалiв
(воно буде дуже спецiальним) i покажемо, як для нього побудувати поворот кола та об’єднання
дуг, для яких це перекладання буде вiдображенням першого повернення.
Важливим буде слiдкувати за тим, щоб кожне нове перетворення дуальної схеми залишало її
додатною (тобто не допустити ефекту, описаного у контрприкладi в кiнцi пiдпункту 5.1), тодi,
згiдно з твердженням 3, вона автоматично залишатиметься ротацiйною, а отже ротацiйним
залишатиметься i перетворюване перекладання iнтервалiв.
Нам знадобляться двi леми.
5.4. Лема про нероздiлюванiсть. Назвемо схему перекладання iнтервалiв \sigma роздiлюваною
(по циклу c0), якщо її алфавiт \scrA можна роздiлити на два непорожнi пiдалфавiти \scrA 1 i \scrA 2
(\scrA 1 \cup \scrA 2 = \scrA , \scrA 1 \not = \varnothing , \scrA 2 \not = \varnothing ) таким чином, що має мiсце властивiсть: один iз циклiв
c0 = (\=\xi , \sigma (\=\xi )), . . . , \sigma k(\=\xi )), \=\xi \in \=\scrA , k \geq 1, \sigma k+1(\=\xi ) = \=\xi , у складi \sigma = \{ c0, c1, . . . , cn\} , n \geq 0,
можна роздiлити на двi непорожнi дуги a1 = (\=\xi , \sigma (\=\xi ), . . . , \sigma i(\=\xi )) i a2 = (\sigma i+1(\=\xi ), . . . , \sigma k(\=\xi )),
0 \leq i < k, а решту циклiв — на двi групи \tau 1 = \{ c1, . . . , cj\} i \tau 2 = \{ cj+1, . . . , cn\} , 0 \leq j \leq n,
такi, що всi елементи дуги a1 та циклiв iз \tau 1 належать до \=\scrA 1 = \scrA 1\times \{ \mathrm{b}, \mathrm{e}\} , а всi елементи дуги
a2 та циклiв iз \tau 2 — до \=\scrA 2 = \scrA 2\times \{ \mathrm{b}, \mathrm{e}\} . У протилежному випадку назвемо схему перекладання
iнтервалiв нероздiлюваною.
Легко показати, що для перекладання iнтервалiв iз роздiлюваною схемою сума довжин
усiх початкових iнтервалiв у складi дуги a1 дорiвнює сумi довжин усiх кiнцевих iнтервалiв
у складi a1, i те ж саме правильно для iнтервалiв у складi дуги a2. Це випливає з того, що
зазначена властивiсть (сума довжин усiх початкових iнтервалiв iз певної сукупностi дорiвнює
сумi довжин усiх кiнцевих) за твердженням 1 має мiсце для кожного окремого циклу (тобто
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
460 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
окремого промiжку), а отже i для сукупностi всiх iнтервалiв, проiндексованих елементами
циклiв iз групи \tau 1, з одного боку, а також для сукупностi всiх iнтервалiв з iндексами з \=\scrA 1, з
iншого боку, i цi двi сукупностi iнтервалiв вiдрiзняються саме на сукупнiсть усiх iнтервалiв у
складi дуги a1.
Зокрема, з вищедоведеної властивостi випливає, що жодна з дуг a1 i a2 у роздiлюванiй
схемi перекладання iнтервалiв \sigma не може складатися лише з початкових або лише з кiнцевих
елементiв, бо iнакше сума вiдповiдних допустимих схемою довжин дорiвнювала б нулевi, а
отже схема не була б додатною. Оскiльки цикл c0 має нульове покручення, то з необхiднiстю
одна з цих дуг починається з кiнцевого елемента i закiнчується початковим, а iнша почина-
ється з початкового i закiнчується кiнцевим. Нехай для визначеностi першою є саме a1, а
другою — a2, тодi \=\xi = \alpha \mathrm{e}, \sigma i(\=\xi )) = \beta \mathrm{b}, \sigma i+1(\=\xi ) = \gamma \mathrm{b}, \sigma k(\=\xi ) = \delta \mathrm{e} для певних \alpha , \beta \in \scrA 1 i
\delta , \gamma \in \scrA 2.
Найбiльш наочно властивiсть роздiлюваностi схеми видно, якщо розглянути вiдповiдне пла-
ваюче перекладання iнтервалiв (\sigma ,\bfv ): вона означає, що промiжки цього перекладання можна
зафiксувати в таких позицiях, що кожен iз iнтервалiв одержаного закрiпленого перекладання
(\sigma ,\bfx ) лежить або цiлком на пiвпрямiй ( - \infty , 0), або цiлком на [0,+\infty ), i мiтки усiх iнтервалiв
першої групи належать до \scrA 1, а другої — до \scrA 2, причому рiвно для одного з промiжкiв (який
вiдповiдає циклу c0) нуль є внутрiшньою точкою, i x\alpha \mathrm{e} = x\gamma \mathrm{b} = 0 для тих \alpha i \gamma , якi визначенi
в попередньому абзацi. Фактично весь набiр iнтервалiв у (\sigma ,\bfx ) роздiлюється точкою нуль на
двi групи: всi iнтервали лiвiше вiд нуля мають iндекси з \=\scrA 1, а всi iнтервали правiше вiд нуля —
iндекси з \=\scrA 2.
Лема 1. Якщо схема перекладання iнтервалiв роздiлювана, то вона не може бути рота-
цiйною.
Доведення. Згiдно з описаними вище властивостями роздiлюваної схеми \sigma , набори еле-
ментiв \=\scrA 1 i \=\scrA 2 з’єднанi нею рiвно у двох мiсцях, а саме: iснують елементи \alpha , \beta \in \scrA 1 i
\delta , \gamma \in \scrA 2 такi, що \sigma (\beta \mathrm{b}) = \gamma \mathrm{b}, \sigma (\delta \mathrm{e}) = \alpha \mathrm{e}, а для всiх \=\xi \in \=\scrA 1\setminus \{ \beta \mathrm{b}\} i для всiх \=\eta \in \=\scrA 2\setminus \{ \delta \mathrm{e}\}
маємо \sigma (\=\xi ) \in \=\scrA 1 i \sigma (\=\eta ) \in \=\scrA 2. Вiдповiдна властивiсть має мiсце i для дуальної схеми \sigma \ast , а
саме: \sigma \ast (\beta \mathrm{e}) = \gamma \mathrm{b}, \sigma \ast (\delta \mathrm{b}) = \alpha \mathrm{e}, а для всiх \=\xi \in \=\scrA 1\setminus \{ \beta \mathrm{e}\} i для всiх \=\eta \in \=\scrA 2\setminus \{ \delta \mathrm{b}\} маємо
\sigma \ast (\=\xi ) \in \=\scrA 1 i \sigma \ast (\=\eta ) \in \=\scrA 2. Отже, один iз циклiв у складi \sigma \ast можна роздiлити на двi непорожнi
дуги a\prime 1 = (\alpha \mathrm{e}, . . . , \beta \mathrm{e}) та a\prime 2 = (\gamma \mathrm{b}, . . . , \delta \mathrm{b}), а решту циклiв — на двi групи \tau \prime 1 i \tau \prime 2 такi, що всi
елементи дуги a\prime 1 i циклiв iз \tau \prime 1 належать до \=\scrA 1, а всi елементи дуги a\prime 2 i циклiв iз \tau \prime 2 — до \=\scrA 2.
Нехай \bfw = (w\xi )\xi \in \scrA — дозволений схемою \sigma \ast вектор довжин. Сума довжин усiх початкових
iнтервалiв iз iндексами в якомусь одному циклi дорiвнює сумi довжин усiх кiнцевих iнтервалiв
iз iндексами в цьому циклi, це ж з очевиднiстю правильно i для групи циклiв. Отже, маємо спiв-
вiдношення
\sum
\xi : \xi \mathrm{b}\in \tau \prime 1
w\xi =
\sum
\xi : \xi \mathrm{e}\in \tau \prime 1
w\xi (трохи некоректне, але наочне позначення \xi \mathrm{b} \in \tau \prime 1
тут означає, що елемент \xi \mathrm{b} належить до одного з циклiв у складi групи \tau \prime 1, i аналогiчно для \xi \mathrm{e}).
Оскiльки
\sum
\xi : \xi \mathrm{b}\in \=\scrA 1
w\xi =
\sum
\xi \in \scrA 1
w\xi =
\sum
\xi : \xi \mathrm{e}\in \=\scrA 1
w\xi , а множина всiх елементiв циклiв з \tau \prime 1
вiдрiзняється вiд \=\scrA 1 в точностi на множину усiх елементiв дуги a\prime 1, то, вiднявши вiд останньої
рiвностi передостанню, отримаємо
\sum
\xi : \xi \mathrm{b}\in a\prime 1
w\xi =
\sum
\xi : \xi \mathrm{e}\in a\prime 1
w\xi .
Якщо припустити, що роздiлювана схема перекладання iнтервалiв \sigma є ротацiйною, то ду-
альна до неї схема \sigma \ast повинна бути додатною i мати нульове покручення. Але якщо всi цикли у
складi \sigma \ast мають нульове покручення, то визначена вище непорожня дуга a\prime 1 складається лише
з кiнцевих елементiв, а отже
\sum
\xi : \xi \mathrm{e}\in a\prime 1
w\xi = 0, i схема \sigma \ast не є додатною.
Лему доведено.
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 461
5.5. Лема про нерiвнi довжини. Для даної схеми ПАI \sigma скажемо, що довжини v\alpha i v\beta ,
\alpha , \beta \in \scrA , є рiвними з необхiднiстю, якщо для кожного дозволеного вектора довжин \bfv має мiсце
рiвнiсть v\alpha = v\beta . Зрозумiло, що всi спiввiдношення мiж довжинами визначаються рiвностя-
ми (3), але якщо схема досить складна, то рiвнiсть iз необхiднiстю певних двох довжин може
бути неочевидною.
Розглянемо ситуацiю, коли у якомусь перекладаннi iнтервалiв початковий I\alpha \mathrm{b} i кiнцевий
I\beta \mathrm{e} iнтервали прилягають обидва до лiвого або обидва до правого краю одного й того самого
промiжку J, тобто в дворядковому записi схема мiстить у собi цикл c0 вигляду
\biggl[
\alpha . . .
\beta . . .
\biggr]
або
вигляду
\biggl[
. . . \alpha
. . . \beta
\biggr]
, тобто \sigma (\beta \mathrm{e}) = \alpha \mathrm{b} або \sigma (\alpha \mathrm{b}) = \beta \mathrm{e} вiдповiдно, \alpha , \beta \in \scrA , i даний цикл не
є двохелементним. У загальному випадку довжини v\alpha i v\beta можуть при цьому бути рiвними з
необхiднiстю, але не у випадку ротацiйного перекладання, як показує така лема.
Лема 2. Якщо у схемi перекладання iнтервалiв \sigma для певних \alpha , \beta \in \scrA маємо \sigma (\beta \mathrm{e}) = \alpha \mathrm{b}
або \sigma (\alpha \mathrm{b}) = \beta \mathrm{e}, вiдповiдний цикл c0 не є двохелементним, а довжини v\alpha i v\beta є рiвними з
необхiднiстю, то ця схема не може бути ротацiйною.
Доведення. Обмежимося розглядом випадку \sigma (\beta \mathrm{e}) = \alpha \mathrm{b} (для випадку \sigma (\alpha \mathrm{b}) = \beta \mathrm{e} дове-
дення аналогiчне). Власне ми доведемо, що за перелiчених умов схема \sigma є роздiлюваною, тодi
з леми 1 випливатиме, що вона не може бути ротацiйною. Одразу зауважимо, що при \alpha = \beta
схема \sigma очевидно є роздiлюваною (по циклу c0, з пiдалфавiтами \scrA 1 = \{ \alpha \} , \scrA 2 = \scrA \setminus \{ \alpha \} ), тож
далi припускатимемо, що \alpha \not = \beta .
Нехай \bfv — дозволений схемою \sigma додатний вектор довжин. Якщо припустити iснування
(закiльцьованої) послiдовностi вiдмiнних вiд \alpha мiток \beta 1 = \beta , \beta 2, . . . , \beta k, \beta k+1 = \beta , k \geq 1,
таких, що \beta i+1\mathrm{e} \in c(\beta i\mathrm{b}) для всiх 1 \leq i \leq k, то одночасне збiльшення всiх довжин v\beta i
,
1 \leq i \leq k, на одне й те ж саме додатне число залишає правильними всi рiвностi (3), а
отже довжини v\alpha i v\beta не є рiвними з необхiднiстю. Оскiльки це суперечить умовi леми, то
закiльцьованої послiдовностi з указаною властивiстю не iснує.
Зберемо групу циклiв \tau 1 за таким алгоритмом. Спочатку включимо до неї цикл c1 = c(\beta \mathrm{b}),
а потiм додаватимемо всi цикли c(\gamma \mathrm{b}), де \gamma \not = \alpha , а елемент \gamma \mathrm{e} належить до якогось iз уже
доданих до групи \tau 1 циклiв. Фактично група \tau 1 складається з циклiв вигляду c(\beta k\mathrm{b}) для кожної
iснуючої скiнченної послiдовностi вiдмiнних вiд \alpha мiток \beta 1 = \beta , \beta 2, . . . , \beta k, k \geq 1, таких, що
\beta i+1\mathrm{e} \in c(\beta i\mathrm{b}) для всiх 1 \leq i < k. Цикл c0 не належить до групи \tau 1 згiдно з результатом
попереднього абзацу.
Розглянемо множину \scrA 0 \subset \scrA усiх мiток \gamma \not = \alpha таких, що \gamma \mathrm{e} \in \tau 1 (як i вище, такий не зовсiм
коректний запис позначає належнiсть даного елемента до якогось циклу з групи \tau 1). Згiдно з
побудовою маємо \gamma \mathrm{b} \in \tau 1 для всiх \gamma \in \scrA 0; оскiльки c0 не належить до групи \tau 1, то маємо
\beta \mathrm{e} \not \in \tau 1 i \alpha \mathrm{b} \not \in \tau 1. Якщо припустити, що \alpha \mathrm{e} \not \in \tau 1, то множиною мiток усiх кiнцевих елементiв
циклiв з групи \tau 1 є \scrA 0, тодi як множина мiток усiх їхнiх початкових елементiв включає в себе
множину \scrA 0 та мiстить (принаймнi) ще одну мiтку \beta \not \in \scrA 0, що суперечить твердженню 1 для
додатної схеми. Отже, \alpha \mathrm{e} \in \tau 1, i множиною мiток усiх кiнцевих елементiв циклiв з групи \tau 1
є \scrA 0 \cup \{ \alpha \} , тодi як множина мiток усiх їхнiх початкових елементiв включає в себе множину
\scrA 0 \cup \{ \beta \} , i насправдi в точностi є нею згiдно з твердженням 1 i рiвнiстю довжин v\alpha та v\beta .
Таким чином, i у випадку \alpha \not = \beta схема перекладання iнтервалiв \sigma є роздiлюваною (по
циклу c0, з пiдалфавiтами \scrA 1 = \scrA 0 \cup \{ \alpha , \beta \} , \scrA 2 = \scrA \setminus \scrA 1), а отже не є ротацiйною.
Лему доведено.
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
462 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
5.6. Реалiзацiя алгоритму перетворення ротацiйного перекладання iнтервалiв. Отже,
нехай дано незвiдне плаваюче ротацiйне перекладання iнтервалiв (\sigma ,\bfv ). Розглянемо дуальну
до \sigma ротацiйну схему перекладання iнтервалiв \sigma \ast . Якщо в нiй є двохелементнi цикли, то за-
стосуємо до (\sigma ,\bfv ) вiдповiднi операцiї злиття iнтервалiв, пiсля чого в дуальнiй схемi \sigma \ast не
залишиться двохелементних циклiв. Якщо циклiв у складi \sigma \ast бiльше нiж один, то виберемо
серед них один довiльний i будемо послiдовно застосовувати до нього елементарнi кроки iн-
дукцiї вигляду \Pi \mathrm{l}\mathrm{b}
\alpha \beta або \Pi \mathrm{l}\mathrm{e}
\alpha \beta , де \alpha i \beta — крайнi злiва мiтки у дворядковому записi цього циклу
c0 =
\biggl[
\alpha . . .
\beta . . .
\biggr]
, верхня i нижня вiдповiдно (тобто \sigma \ast (\beta \mathrm{e}) = \alpha \mathrm{b}), аж поки вiн не стане двох-
елементним. При цьому перекладання (\sigma ,\bfv ) перетворюватиметься пiд дiєю зворотних крокiв
(\Pi \mathrm{r}\mathrm{e}
\alpha \beta )
- 1 або (\Pi \mathrm{l}\mathrm{e}
\beta \alpha )
- 1 згiдно з теоремою 1 з [1]. Ми слiдкуватимемо за тим, щоб схема \sigma \ast
залишалася схемою перекладання iнтервалiв (тобто в цьому випадку залишалася додатною),
тодi згiдно з твердженням 3 вона залишатиметься ротацiйною i вiдповiдним чином перетворю-
ване перекладання iнтервалiв (\sigma ,\bfv ) теж залишатиметься ротацiйним. Опишемо, яким чином
ми кожного разу вибиратимемо, який саме з двох крокiв — \Pi \mathrm{l}\mathrm{b}
\alpha \beta або \Pi \mathrm{l}\mathrm{e}
\alpha \beta — буде застосовува-
тися до дуальної схеми \sigma \ast (зауважимо, що мiтки \alpha та \beta змiнюватимуться вiдповiдно до змiн
у перетворюваному циклi c0, ми не хочемо занадто ускладнювати систему позначень, тому
залишаємо позначення (\sigma ,\bfv ), \sigma \ast , c0, \alpha , \beta для об’єктiв, якi насправдi змiнюються протягом
дiї алгоритму). Одразу зазначимо, що \alpha \not = \beta , iнакше \sigma \ast не була б ротацiйною. Тепер можливi
чотири ситуацiї.
Ситуацiя 1: \alpha \mathrm{e} \not \in c0, \beta \mathrm{b} \not \in c0. Якщо це двохелементний цикл, то злиттям вiдповiдних
iнтервалiв у (\sigma ,\bfv ) позбуваємося його i переходимо до наступного. Якщо нi, то згiдно з лемою 2
iснує дозволений схемою \sigma \ast додатний вектор довжин \bfw такий, що w\alpha \not = w\beta . Якщо w\alpha > w\beta ,
то застосуємо до \sigma \ast крок \Pi \mathrm{l}\mathrm{b}
\alpha \beta , а якщо w\alpha < w\beta , то \Pi \mathrm{l}\mathrm{e}
\alpha \beta . Це збереже додатнiсть, а отже
i ротацiйнiсть схеми \sigma \ast , зменшивши при цьому кiлькiсть елементiв у циклi c0 : у першому
випадку елемент \beta \mathrm{e} буде перемiщено до того циклу, який мiстить \alpha \mathrm{e}, а в другому елемент \alpha \mathrm{b}
буде перемiщено до того циклу, який мiстить \beta \mathrm{b}.
Ситуацiя 2: \alpha \mathrm{e} \not \in c0, \beta \mathrm{b} \in c0. Розглянемо довiльний додатний вектор довжин \bfw , дозво-
лений схемою \sigma \ast . Оскiльки довжина w\beta входить рiвно в одну з рiвностей (3), записаних для
(\sigma \ast ,\bfw ), i входить у неї i злiва, i справа, то на цю довжину немає нiяких обмежень, тому її можна
замiнити на довiльне додатне число, менше за w\alpha (наприклад, покласти w\beta = w\alpha /2). Отже,
iснує додатний вектор довжин \bfw , дозволений схемою \sigma \ast , для якого w\alpha > w\beta . Застосуємо до
\sigma \ast крок \Pi \mathrm{l}\mathrm{b}
\alpha \beta , це збереже додатнiсть, а отже i ротацiйнiсть схеми \sigma \ast , перенiсши елемент \beta \mathrm{e} з
циклу c0 до того циклу, який мiстить \alpha \mathrm{e}.
Ситуацiя 3: \alpha \mathrm{e} \in c0, \beta \mathrm{b} \not \in c0. Ця ситуацiя є аналогiчною до ситуацiї 2, тiльки тепер
довiльно змiнювати можна довжину w\alpha у дозволеному схемою \sigma \ast додатному векторi довжин
\bfw . Зокрема, iснує такий вектор iз спiввiдношенням w\alpha < w\beta , тому застосування кроку \Pi \mathrm{l}\mathrm{e}
\alpha \beta
збереже додатнiсть, а отже i ротацiйнiсть схеми \sigma \ast , при перенесеннi елемента \alpha \mathrm{b} з її циклу c0
до того циклу, який мiстить \beta \mathrm{b}.
Ситуацiя 4: \alpha \mathrm{e} \in c0, \beta \mathrm{b} \in c0. Нехай лiвiше вiд \alpha у нижньому рядку дворядкового запису
циклу c0 знаходяться m \geq 1 мiток, а лiвiше вiд \beta у верхньому рядку — n \geq 1 мiток, тобто
c0 =
\biggl[
\alpha 1 \alpha 2 . . . \alpha n \beta . . .
\beta 1 \beta 2 . . . \beta m \alpha . . .
\biggr]
, \alpha 1 = \alpha , \beta 1 = \beta . Як i у ситуацiях 2 i 3, довжини w\alpha
i w\beta у додатному векторi довжин \bfw , дозволеному схемою \sigma \ast , можна вибирати довiльним
чином, i застосування як кроку \Pi \mathrm{l}\mathrm{b}
\alpha \beta , так i кроку \Pi \mathrm{l}\mathrm{e}
\alpha \beta зберiгатиме ротацiйнiсть схеми \sigma \ast . Але
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 463
кiлькiсть елементiв у циклi c0 при цьому не зменшиться, натомiсть при застосуваннi \Pi \mathrm{l}\mathrm{b}
\alpha \beta (\Pi \mathrm{l}\mathrm{e}
\alpha \beta )
мiтки, що стоять у нижньому рядку лiвiше вiд \alpha \mathrm{e} (у верхньому рядку лiвiше вiд \beta \mathrm{b}), циклiчно
переставляться:
\Pi \mathrm{l}\mathrm{b}
\alpha \beta 1
:
\Biggl[
\alpha . . . . . .
\beta 1 \beta 2 . . . \beta m \alpha . . .
\Biggr]
\mapsto \rightarrow
\Biggl[
\alpha . . . . . .
\beta 2 . . . \beta m \beta 1 \alpha . . .
\Biggr]
,
\Pi \mathrm{l}\mathrm{e}
\alpha 1\beta :
\Biggl[
\alpha 1 \alpha 2 . . . \alpha n \beta . . .
\beta . . . . . .
\Biggr]
\mapsto \rightarrow
\Biggl[
\alpha 2 . . . \alpha n \alpha 1 \beta . . .
\beta . . . . . .
\Biggr]
.
Отже, якщо серед мiток \beta i, 1 < i \leq m, є така, для якої \beta i\mathrm{b} \not \in c0, то, застосувавши по-
слiдовно кроки iндукцiї \Pi \mathrm{l}\mathrm{b}
\alpha \beta 1
, . . . ,\Pi \mathrm{l}\mathrm{b}
\alpha \beta i - 1
, перейдемо до ситуацiї 3; аналогiчно, якщо серед
мiток \alpha j , 1 < j \leq n, є така, для якої \alpha j\mathrm{e} \not \in c0, то, застосувавши послiдовно кроки iндук-
цiї \Pi \mathrm{l}\mathrm{e}
\alpha 1\beta
, . . . ,\Pi \mathrm{l}\mathrm{e}
\alpha j - 1\beta
, перейдемо до ситуацiї 2. В обох випадках наступним кроком кiлькiсть
елементiв циклу c0 буде зменшено. Припустимо тепер, що всi елементи \alpha 1\mathrm{e}, . . . , \alpha n\mathrm{e} та всi
елементи \beta 1\mathrm{b}, . . . , \beta m\mathrm{b} належать циклу c0. Множини \{ \alpha 2, . . . , \alpha n\} i \{ \beta 2, . . . , \beta m\} не можуть
мiж собою збiгатися, бо в цьому випадку схема \sigma \ast була б або роздiлюваною (по циклу c0) з пiд-
алфавiтами \scrA 1 = \{ \alpha 2, . . . , \alpha n, \alpha , \beta \} , \scrA 2 = \scrA \setminus \scrA 1, а отже не ротацiйною згiдно з лемою 1, або
ж звiдною (якщо в c0 немає елементiв, вiдмiнних вiд \scrA 1 \times \{ \mathrm{b}, \mathrm{e}\} ). Оскiльки схема \sigma \ast ротацiй-
на i незвiдна, то хоча б одна з множин \{ \beta 2, . . . , \beta m\} \setminus \{ \alpha 2, . . . , \alpha n\} i \{ \alpha 2, . . . , \alpha n\} \setminus \{ \beta 2, . . . , \beta m\}
є непорожньою. Якщо перша з них непорожня, тобто iснує \beta i \not \in \{ \alpha 2, . . . , \alpha n\} , 1 < i \leq m,
то, застосувавши послiдовно кроки \Pi \mathrm{l}\mathrm{b}
\alpha \beta 1
, . . . ,\Pi \mathrm{l}\mathrm{b}
\alpha \beta i - 1
, прийдемо до ситуацiї 4 зi збiльшеним n
(тепер це кiлькiсть мiток у верхньому рядку лiвiше вiд \beta i, а вона є бiльшою за n, оскiльки \beta i
знаходиться правiше вiд \beta ). Якщо множина \{ \beta 2, . . . , \beta m\} \setminus \{ \alpha 2, . . . , \alpha n\} порожня, то непорож-
ньою є множина \{ \alpha 2, . . . , \alpha n\} \setminus \{ \beta 2, . . . , \beta m\} , i ми аналогiчним чином прийдемо до ситуацiї 4,
але тепер зi збiльшеним m. Оскiльки n та m обмеженi, то такий процес не може тривати
нескiнченно, тому зрештою ми таки перейдемо до ситуацiй 2 або 3.
Пiдсумовуючи описаний алгоритм дiй щодо вибраного бiльш нiж двохелементного циклу
c0, ми в будь-якому випадку за скiнченну кiлькiсть крокiв iндукцiї одержимо з нього цикл,
що мiстить на один елемент менше. Отже, продовжуючи застосовувати цей алгоритм щодо
вибраного циклу, ми зрештою отримаємо з нього двохелементний цикл. Пiсля цього застосуємо
операцiю злиття вiдповiдних iнтервалiв у перекладаннi (\sigma ,\bfv ), i нова схема \sigma \ast мiститиме на
один цикл менше, нiж ранiше.
Продовжуючи вибирати цикли у складi \sigma \ast i застосовуючи до них описаний вище алгоритм,
ми позбуватимемося їх один за одним i зупинимося тодi, коли схема \sigma \ast являтиме собою один-
єдиний цикл. За нашою побудовою, одержане (шляхом послiдовного застосування до (\sigma ,\bfv )
вiдповiдних зворотних крокiв iндукцiї та операцiй злиття iнтервалiв) перекладання iнтервалiв
є ротацiйним, i з погляду динамiчних систем вихiдне перекладання є для нього вiдображенням
першого повернення на вiдповiднi промiжки.
5.7. Канонiчний вигляд ротацiйного перекладання iнтервалiв. Отже, ми прийшли до
ситуацiї, коли дуальна схема \sigma \ast складається з єдиного циклу. Особливiсть перекладання iн-
тервалiв iз такою схемою полягає в тому, що (пригадуючи класифiкацiю з пп. 4.2) серед усiх
країв є лише один типу L i лише один типу R, а всi решта мають типи MB чи ME. Вiдповiдно,
для перекладання (\sigma ,\bfv ) серед усiх країв є лише один типу MB i лише один типу ME, а всi
решта мають типи L чи R, тобто лише в одному мiсцi \sigma (\alpha \mathrm{b}) = \beta \mathrm{b} i лише в одному \sigma (\gamma \mathrm{e}) = \delta \mathrm{e},
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
464 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
\alpha , \beta , \gamma , \delta \in \scrA (причому серед цих чотирьох мiток можливими є лише рiвностi \alpha = \gamma чи \beta = \delta , а
будь-яка iнша рiвнiсть неможлива внаслiдок додатностi схем \sigma i \sigma \ast ), а в усiх iнших за кiнцевим
елементом слiдує початковий, а за початковим кiнцевий.
Можливi два випадки: якщо \alpha \mathrm{b} i \gamma \mathrm{e} належать двом рiзним циклам у складi перестановки
\sigma , то цi цикли мають вигляд
\biggl[
\alpha \beta
\kappa
\biggr]
i
\biggl[
\lambda
\delta \gamma
\biggr]
, \lambda , \kappa \in \scrA (рiвнiсть \lambda = \kappa можлива), а всi решта
є двохелементними; у протилежному випадку маємо один цикл
\biggl[
\alpha \beta
\delta \gamma
\biggr]
i всi решта знову ж
таки є двохелементними.
З огляду на спiввiдношення (3) легко переконатися, що додатнiсть схем \sigma i \sigma \ast забезпе-
чується лише тодi, коли множина всiх двохелементних циклiв у складi \sigma у першому випадку
роздiляється на три скiнченнi послiдовностi\Biggl[
\alpha i+1
\alpha i
\Biggr]
, 1 \leq i < m, де \alpha 1 = \alpha , \alpha m = \gamma , m \geq 1,
\Biggl[
\beta j+1
\beta j
\Biggr]
, 1 \leq j < n, де \beta 1 = \beta , \beta n = \delta , n \geq 1,
\Biggl[
\lambda k+1
\lambda k
\Biggr]
, 1 \leq k < s, де \lambda 1 = \lambda , \lambda s = \kappa , s \geq 1
(кожна з них може бути порожньою); у другому випадку наявнi лише першi двi послiдовностi.
Єдиний цикл у складi дуальної схеми \sigma \ast записується у першому випадку як\Biggl[
\beta 1 . . . \beta n \lambda 1 . . . \lambda s \alpha 1 . . . \alpha m
\alpha 1 . . . \alpha m \lambda 1 . . . \lambda s \beta 1 . . . \beta n
\Biggr]
,
а в другому як
\biggl[
\beta 1 . . . \beta n \alpha 1 . . . \alpha m
\alpha 1 . . . \alpha m \beta 1 . . . \beta n
\biggr]
.
З рiвностей (3) випливають, зокрема, спiввiдношення v\alpha = v\gamma , v\beta = v\delta в обох випадках
плюс додаткове спiввiдношення v\lambda = v\kappa = v\alpha + v\beta в першому.
Якщо має мiсце перший з описаних вище випадкiв
\biggl(
тобто єдиний цикл у складi \sigma \ast має
вигляд
\biggl[
\beta 1 . . . \beta n \lambda 1 . . . \lambda s \alpha 1 . . . \alpha m
\alpha 1 . . . \alpha m \lambda 1 . . . \lambda s \beta 1 . . . \beta n
\biggr]
iз s \geq 1
\biggr)
, то зведемо його до другого
випадку, послiдовно застосувавши до \sigma \ast кроки iндукцiї \Pi \mathrm{l}\mathrm{e}
\beta 1\alpha 1
, . . . ,\Pi \mathrm{l}\mathrm{e}
\beta n\alpha 1
. Як i у ситуацiї 4 з
попереднього пiдпункту, мiтки лiвiше вiд \alpha 1 у верхньому рядку циклiчно переставляться (при
цьому схема залишатиметься додатною, а отже ротацiйною внаслiдок вiдсутностi обмежень на
довжини), утворивши в кiнцi послiдовнiсть \lambda 1, . . . , \lambda s, \beta 1, . . . , \beta n — ту ж саму, яка знаходиться
у нижньому рядку правiше вiд \alpha m.
Таким чином, ми в усiх випадках зрештою приходимо до ситуацiї, коли ротацiйна схема \sigma
має канонiчний вигляд
\sigma \mathrm{c}\mathrm{a}\mathrm{n} =
\Biggl\{ \Biggl[
\alpha 1 \beta 1
\beta n \alpha m
\Biggr]
;
\Biggl[
\alpha i+1
\alpha i
\Biggr]
, 1 \leq i < m;
\Biggl[
\beta j+1
\beta j
\Biggr]
, 1 \leq j < n
\Biggr\}
(7)
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 465
для певного набору попарно рiзних мiток \alpha 1, . . . , \alpha m, \beta 1, . . . , \beta n i певних натуральних чисел m
та n. Разом iз дозволеним додатним вектором довжин \bfv = \bfv \mathrm{c}\mathrm{a}\mathrm{n} ротацiйна схема канонiчного
вигляду утворює ротацiйне перекладання iнтервалiв (\sigma \mathrm{c}\mathrm{a}\mathrm{n},\bfv \mathrm{c}\mathrm{a}\mathrm{n}) канонiчного вигляду. Компо-
ненти вектора довжин задовольняють спiввiдношення v\alpha 1 = . . . = v\alpha m i v\beta 1 = . . . = v\beta m ; ми
цi двi довжини позначимо просто v\alpha та v\beta вiдповiдно (не виключено, що вони також рiвнi мiж
собою).
У пiдсумку в останнiх двох пiдпунктах ми конструктивним чином довели таке твердження.
Твердження 5. Довiльне незвiдне ротацiйне перекладання iнтервалiв можна привести до
канонiчного вигляду послiдовним застосуванням скiнченної кiлькостi обернених елементар-
них крокiв iндукцiї та операцiй злиття iнтервалiв, причому на кожному кроцi цього процесу
перетворюваний ПАI залишатиметься незвiдним ротацiйним перекладанням iнтервалiв.
Зауваження 4. Як показує викладений алгоритм, фактично для приведення ротацiйного
перекладання до канонiчного вигляду достатньо обмежитися застосуванням обернених еле-
ментарних крокiв iндукцiї лише двох типiв, а саме, (\Pi \mathrm{l}\mathrm{e}
\alpha \beta )
- 1 i (\Pi \mathrm{r}\mathrm{e}
\alpha \beta )
- 1. Цiлком аналогiчно,
можна обмежитися застосуванням обернених елементарних крокiв iндукцiї лише iнших двох
типiв, а саме, (\Pi \mathrm{l}\mathrm{b}
\alpha \beta )
- 1 i (\Pi \mathrm{r}\mathrm{b}
\alpha \beta )
- 1, яким вiдповiдають елементарнi кроки iндукцiї \Pi \mathrm{r}\mathrm{e}
\alpha \beta i \Pi \mathrm{r}\mathrm{b}
\beta \alpha
вiдповiдно у застосуваннi до дуальної ротацiйної схеми (згiдно з теоремою 1 з [1]).
5.8. Побудова на колi. Для ротацiйного перекладання iнтервалiв (\sigma \mathrm{c}\mathrm{a}\mathrm{n},\bfv \mathrm{c}\mathrm{a}\mathrm{n}) канонiчного
вигляду (7), до якого ми привели вихiдне ротацiйне перекладання (\sigma ,\bfv ), вiзьмемо досить великi
натуральнi числа k1 та k2 i побудуємо поворот кола RL,M iз M = v\beta + k2v\alpha i L = v\alpha + k1M,
який розглядатимемо у проєкцiї на промiжок [ - v\alpha , k1M) вiдповiдно до (6) iз x0 = - v\alpha , тобто
як
RL,M : x \mapsto \rightarrow
\left\{ x+M, x \in [ - v\alpha , (k1 - 1)M),
x+M - L, x \in [(k1 - 1)M,k1M).
Вiдмiтимо на [ - v\alpha , k1M) точки ai = Ri
L,M (0), 0 \leq i < q, вiдрiзка траєкторiї довжини
q = 1 + k1 + k2k1 точки a0 = 0 пiд дiєю повороту RL,M . Неважко переконатися, що зазначенi
1+k1+k2k1 точок упорядкованi таким чином (злiва направо): ak1 = - v\alpha , a0 = 0, далi йде блок
iз k2+1 точок ak2k1+1 = v\beta , a(k2 - 1)k1+1 = v\beta +v\alpha , . . . , ak1+1 = v\beta +(k2 - 1)v\alpha , a1 = M, i далi
послiдовно ще k1 - 1 таких блокiв, зсунутих на 1 \leq j < k1 поворотiв RL,M , тобто блокiв iз k2+1
точок ak2k1+1+j = v\beta +jM, a(k2 - 1)k1+1+j = v\beta +v\alpha +jM, . . . , ak1+1+j = v\beta +(k2 - 1)v\alpha +jM,
a1+j = (1+ j)M, причому в останньому з них (при j = k1 - 1) остання точка a1+(k1 - 1) = k1M
є правим краєм промiжку [ - v\alpha , k1M) i в проєкцiї збiгається з його лiвим краєм ak1 = - v\alpha ,
який ми вже згадали. Також зазначимо, що aq = Rq
L,M (0) = v\beta - v\alpha .
З огляду на цей порядок i рiвностi ak1 = - v\alpha , a0 = 0, ak2k1+1 = v\beta легко бачити,
що точками ai, 0 \leq i < q, коло [ - v\alpha , k1M) розбивається на k1 дуг довжини v\beta , а саме,
дуги Ri
L,M [0, v\beta ), 0 \leq i < k1, та k2k1 + 1 дуг довжини v\alpha , а саме, дуги Ri
L,M [ - v\alpha , 0),
0 \leq i < k2k1 + 1. Жоднi двi з цих 1 + k1 + k2k1 дуг не мають спiльних точок i в об’єднаннi
дають усе коло. При цьому дуги Rk1
L,M [0, v\beta ) = [ak1 , aq) = [ - v\alpha , v\beta - v\alpha ) та Rk2k1+1
L,M [ - v\alpha , 0) =
[aq, ak2k1+1) = [v\beta - v\alpha , v\beta ) також не перетинаються i в об’єднаннi дають ту ж саму дугу
[ - v\alpha , v\beta ), яку дають в об’єднаннi дуги [0, v\beta ) та [ - v\alpha , 0).
Виходячи з цiєї конструкцiї, видiлимо на колi дугу [ - v\alpha , v\beta ), а також довiльнi m - 1
дуг з-помiж Ri
L,M [ - v\alpha , 0), 0 \leq i < k2k1 + 1, та довiльнi n - 1 дуг з-помiж Ri
L,M [0, v\beta ),
0 \leq i < k1, таким чином, щоб жоднi двi з видiлених дуг не дотикалися краями (це з оче-
виднiстю можливо, якщо k1 та k2 достатньо великi). Згiдно з побудовою, динамiчна система,
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
466 ОЛЕКСIЙ ТЕПЛIНСЬКИЙ
визначена вiдображенням першого повернення для повороту кола RL,M на видiлене об’єднання
n+m - 1 дуг, є iдентичною з динамiчною системою ротацiйного перекладання iнтервалiв ка-
нонiчного вигляду (\sigma \mathrm{c}\mathrm{a}\mathrm{n},\bfv \mathrm{c}\mathrm{a}\mathrm{n}). А оскiльки це перекладання канонiчного вигляду є одержаним
в результатi послiдовного застосування обернених крокiв iндукцiї та операцiй злиття iнтер-
валiв до вихiдного ротацiйного перекладання iнтервалiв (\sigma ,\bfv ), то динамiчна система остан-
нього, у свою чергу, визначається вiдображенням першого повернення на певне скiнченне
об’єднання пiдпромiжкiв фазового простору динамiчної системи (\sigma \mathrm{c}\mathrm{a}\mathrm{n},\bfv \mathrm{c}\mathrm{a}\mathrm{n}). Видiливши на
колi об’єднання дуг, яке вiдповiдає цьому об’єднанню пiдпромiжкiв, одержимо саме таке скiн-
ченне об’єднання дуг, вiдображення першого повернення на яке для повороту кола RL,M є
еквiвалентним до вихiдного незвiдного ротацiйного перекладання iнтервалiв (\sigma ,\bfx ) з точнiстю
до зсуву.
Частину 2 теореми 1 доведено.
6. Доведення третьої частини теореми. У третiй частинi теореми сформульовано крите-
рiй ротацiйностi схеми перекладання iнтервалiв у термiнах вiдображення першого повернення
на об’єднання дуг для iррацiонального повороту кола. Фактично її твердження майже випливає
з доведених нами перших двох частин теореми, а саме, з першої частини випливає, що в разi
iснування згаданого вiдображення першого повернення вiдповiдна до нього незвiдна схема ПАI
є ротацiйною, а з другої частини теореми випливає, що для незвiдної ротацiйної схеми iснує
вiдображення першого повернення з цiєю схемою. Єдине, що залишається довести, — це iсну-
вання для незвiдної ротацiйної схеми вiдповiдного вiдображення першого повернення саме для
iррацiонального повороту кола. Зараз ми це зробимо, для чого повернемося до алгоритму при-
ведення ротацiйного перекладання iнтервалiв до канонiчного вигляду, який ми застосовували
в попередньому пунктi.
Отже, нехай нам дано незвiдну ротацiйну схему перекладання iнтервалiв \sigma . Долучивши до
цiєї схеми довiльний дозволений нею додатний вектор довжин \bfv , отримаємо ротацiйне перекла-
дання (\sigma ,\bfv ). Приведемо його до канонiчного вигляду (\sigma \mathrm{c}\mathrm{a}\mathrm{n},\bfv \mathrm{c}\mathrm{a}\mathrm{n}) вiдповiдно до твердження 5.
У пiдпунктi 5.8 показано, що перекладання канонiчного вигляду з довжинами v\alpha , v\beta є вiдобра-
женням першого повернення для повороту кола RL,M iз M = v\beta +k2v\alpha , L = v\alpha +k1M з певни-
ми натуральними k1, k2. Число обертання цього повороту кола \rho = M/L = 1/(k1+1/(k2+\rho 0)),
де \rho 0 = v\beta /v\alpha , є рацiональним або iррацiональним в залежностi вiд рацiональностi або iрра-
цiональностi числа \rho 0. Отже, якщо довжини v\alpha i v\beta несумiрнi, то необхiдний iррацiональний
поворот кола вже побудовано.
Припустимо, що довжини v\alpha i v\beta є сумiрними, тобто \rho 0 = v\beta /v\alpha \in \BbbQ . У цьому випадку
просто змiнимо їх малим збуренням таким чином, щоб вони перестали бути сумiрними, напри-
клад, замiнивши довжину v\beta на v\prime \beta = v\beta + \varepsilon , де 0 < \varepsilon \ll 1, \varepsilon /v\beta \not \in \BbbQ . Тепер проведемо весь
алгоритм приведення до канонiчного вигляду у зворотному порядку. Перекладання (\sigma \mathrm{c}\mathrm{a}\mathrm{n},\bfv \mathrm{c}\mathrm{a}\mathrm{n})
було отримано з (\sigma ,\bfv ) застосуванням скiнченної кiлькостi зворотних крокiв iндукцiї та опе-
рацiй злиття iнтервалiв. Вiдповiдно, у зворотному порядку застосуємо послiдовно тi ж самi
прямi кроки iндукцiї та операцiї роздiлення iнтервалiв (на визначенi частини). Очевидно, що
кожна з цих операцiй є грубою в тому сенсi, що при її застосуваннi малi збурення дiйсних
компонент (довжин) перекладань залишаються малими, а отже i дискретнi компоненти (схе-
ми) перекладань на кожному кроцi алгоритму при малих збуреннях залишаються незмiнними.
Тому зi збуреного вказаним чином канонiчного перекладання (\sigma \mathrm{c}\mathrm{a}\mathrm{n},\bfv
\prime
\mathrm{c}\mathrm{a}\mathrm{n}) в результатi засто-
сування у зворотному порядку алгоритму приведення ми отримуємо збурене перекладання
(\sigma ,\bfv \prime ) iз тiєю ж самою заданою на початку схемою \sigma , i це збурене перекладання буде вiд-
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
РОТАЦIЙНI ПЕРЕКЛАДАННЯ IНТЕРВАЛIВ 467
ображенням першого повернення вже для iррацiонального повороту кола з числом обертання
\rho \prime = 1/(k1 + 1/(k2 + \rho \prime 0)), де \rho \prime 0 = (v\beta + \varepsilon )/v\alpha \not \in \BbbQ .
Частину 3 теореми 1 доведено.
Роботу частково профiнансовано Нацiональною академiєю наук України в рамках проєкту
„Математичне моделювання складних динамiчних систем та процесiв актуальних для безпеки
держави”, реєстрацiйний номер 0123U100853.
Автор заявляє про вiдсутнiсть конфлiкту iнтересiв.
Лiтература
1. О. Ю. Теплiнський, Перекладальнi ансамблi iнтервалiв, Укр. мат. журн., 75, № 2, 247 – 268 (2023).
2. M. Keane, Interval exchange transformations, Math. Z., 141, 25 – 31 (1975).
3. W. A. Veech, Interval exchange transformations, J. Anal. Math., 33, 222 – 272 (1978).
4. G. Rauzy, Échanges d’intervalles et transformations induites, Acta Arith., 34, 315 – 328 (1979).
5. M. S. Keane, G. Rauzy, Stricte ergodicité des échanges d’intervalles, Math. Z., 174, 203 – 212 (1980).
6. H. Masur, Interval exchange transformations and measured foliations, Ann. Math., 115, 169 – 200 (1982).
7. W. A. Veech, Gauss measures for transformations on the space of interval exchange maps, Ann. Math., 115, 201 – 242
(1982).
8. О. Ю. Теплiнський, Гiперболiчна пiдкова для дифеоморфiзмiв кола зi зламом, Нелiнiйнi коливання, 11, № 1,
112 – 127 (2008).
9. K. Khanin, A. Teplinsky, Renormalization horseshoe and rigidity for circle diffeomorphisms with breaks, Comm.
Math. Phys., 320, 347 – 377 (2013).
10. K. M. Khanin, E. B. Vul, Circle homeomorphisms with weak discontinuities, Adv. Soviet Math., vol. 3, Dyn. Sstems
and Statist. Mech., Amer. Math. Soc., Providence, RI (1991), p. 57 – 98.
11. K. Cunha, D. Smania, Renormalization for piecewise smooth homeomorphisms on the circle, Ann. Inst. H. Poincaré
Anal. Non Linéaire, 30, 441 – 462 (2013).
12. K. Cunha, D. Smania, Rigidity for piecewise smooth homeomorphisms on the circle, Adv. Math., 250, 193 – 226
(2014).
Одержано 30.08.23
ISSN 1027-3190. Укр. мат. журн., 2024, т. 76, № 3
|
| id | umjimathkievua-article-7779 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-03-24T03:33:47Z |
| publishDate | 2024 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/1e/f658806ca27baf01af234bf13a0c481e.pdf |
| spelling | umjimathkievua-article-77792024-06-19T00:35:20Z Rotational interval exchange transformations Ротаційні перекладання інтервалів Teplinsky, A. Теплінський, Олексій circle rotation interval exchange transformation interval rearrangement ensemble duality поворот кола, перекладання інтервалів, перекладальний ансамбль інтервалів, дуальність UDC 517.5 We show the equivalence of two possible definitions of a rotational interval exchange transformation: by the first definition, it is the first return map for a circle rotation onto a union of finitely many circle arcs and, by the second definition, it is an interval exchange with a scheme (in the sense of interval rearrangement ensembles) whose dual is also an interval exchange scheme. УДК 517.5 Показано еквівалентність двох можливих означень ротаційного перекладання інтервалів: згідно з одним, це ві\-дображення першого повернення для повороту кола на об'єднання скінченної кількості його дуг, а згідно з іншим, це перекладання інтервалів зі схемою (в сенсі перекладального ансамблю інтервалів), дуальна до якої схема також є схемою перекладання інтервалів. Institute of Mathematics, NAS of Ukraine 2024-03-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/7779 10.3842/umzh.v76i3.7779 Ukrains’kyi Matematychnyi Zhurnal; Vol. 76 No. 3 (2024); 447 - 467 Український математичний журнал; Том 76 № 3 (2024); 447 - 467 1027-3190 uk https://umj.imath.kiev.ua/index.php/umj/article/view/7779/9863 Copyright (c) 2024 Олексій Теплінський |
| spellingShingle | Teplinsky, A. Теплінський, Олексій Rotational interval exchange transformations |
| title | Rotational interval exchange transformations |
| title_alt | Ротаційні перекладання інтервалів |
| title_full | Rotational interval exchange transformations |
| title_fullStr | Rotational interval exchange transformations |
| title_full_unstemmed | Rotational interval exchange transformations |
| title_short | Rotational interval exchange transformations |
| title_sort | rotational interval exchange transformations |
| topic_facet | circle rotation interval exchange transformation interval rearrangement ensemble duality поворот кола перекладання інтервалів перекладальний ансамбль інтервалів дуальність |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/7779 |
| work_keys_str_mv | AT teplinskya rotationalintervalexchangetransformations AT teplínsʹkijoleksíj rotationalintervalexchangetransformations AT teplinskya rotacíjníperekladannâíntervalív AT teplínsʹkijoleksíj rotacíjníperekladannâíntervalív |