Доказать евклидовость кольца (Винберг)

[movzx]

Доказать, что кольцо рациональных чисел вида $2^{-n}m\;(m \in \mathbb{Z}, n \in \mathbb{Z}_+)$ является евклидовым.

Для начала изменим представление чисел на $2^nm\;(m \in (\mathbb{Z}\setminus2\mathbb{Z}\cup \{0\}),n\in\mathbb{Z})$, то есть $m$ должен быть нечётным либо $0$. Проверим эквивалентность этих определений:
1. $x = 2^{-n}m$ (первая форма). Представим $m$ в форме $2^{n_1}m_1$, где $m_1$ — нечётное число либо $0$. Тогда $x=2^{n_1-n}m_1$ (вторая форма).
2. $x=2^nm$ (вторая форма). Если $n>0$, то $m_1=2^nm$. Тогда $x=2^0m_1$. Если $n\leq0$, то $n_1=-n$. Тогда $x=2^{-n_1}m$ (первая форма).

Далее определим норму: $N(2^nm)=|m|$. Свойства нормы:
1. $N(ab)\geq N(a)$, причём $N(ab)=N(a) \Leftrightarrow \exists b^{-1}$;
2. $\forall a, b\;(b\neq0)\; \exists q, r : (a=qb+r)\wedge(r=0\vee N(r)<N(b))$.

Проверка:
1. $N(ab)=N(a)N(b), N(1)=1$, следовательно норма обратимых элементов равна $1$. Отсюда следует свойство 1.
2. $a=2^{n_1}m_1, b=2^{n_2}m_2$. Примем $q=2^{n_1-n_2}\left[\frac {m_1} {m_2}\right]$. Тогда $r=a-qb=2^{n_1}\left(m_1-m_2\left[\frac{m_1}{m_2}\right]\right)=2^{n_1+l}m_l$. Очевидно, что $\left|\frac{m_1}{m_2}-\left[\frac{m_1}{m_2}\right]\right|<1$, следовательно $\left|m_l\right|\leq\left|m_1-m_2\left[\frac{m_1}{m_2}\right]\right|<\left|m_2\right|$, а это означает, что $N(r)<N(b)$. Если $\left|\frac{m_1}{m_2}-\left[\frac{m_1}{m_2}\right]\right|=0$, то $r=0$.

Кажется, всё. Нигде не ошибся? Можно ли было сделать проще?

[Slav-27]

Правильно. Концептуально проще, скорее всего, не получится. Но можно писать меньше буковок, и тогда, может быть, станет понятнее, что происходит. Следующий текст -- просто ваше же доказательство, но немного другими словами писанное.

movzx в сообщении #1151028 писал(а):

Доказать, что кольцо рациональных чисел вида $2^{-n}m\;(m \in \mathbb{Z}, n \in \mathbb{Z}_+)$ является евклидовым.

Это кольцо конечных двоичных дробей.

movzx в сообщении #1151028 писал(а):

Для начала изменим представление чисел на $2^nm\;(m \in (\mathbb{Z}\setminus2\mathbb{Z}\cup \{0\}),n\in\mathbb{Z})$

Возьмём двоичную дробь $a$, переставим там запятую так, чтобы она оказалась как раз справа от самой правой единицы. Запомним получившееся нечётное целое число $a'$ и количество разрядов, на которое сдвинули запятую -- $n_a$. Таким образом наше число представится в виде $a=a'\,2^{n_a}$. Нормой объявим $|a'|$.

1-е свойство очевидно. Проверим 2-е. Пусть надо делить $a$ на $b$. Поделим $a'$ на $b'$ как целые числа: $a'=b'q+r$, где $0\leqslant r<|b'|$ (и уж тем более $r' < |b'|$). Умножим это равенство на $2^{n_a}$: очевидно, получится искомое представление $a$. Действительно, у остатка просто сдвинется запятая, так что норма не изменится, так что и неравенство не нарушится.

[movzx]

Slav-27, спасибо. Такой подход всё упростил.

Slav-27 в сообщении #1151120 писал(а):

Поделим $a'$ на $b'$ как целые числа:

Ходил где-то рядом, но так и недодумался, а ведь так проще, прозрачнее.

Могут ли существовать ещё какие-то нормы?

[vpb]

В пункте 1 небольшая промашка. Что норма обратимого элемента всегда $1$, это ясно. Но Вам ведь на самом деле нужно
обратное: если элемент имеет норму $1$, то оно обратим. Я бы писал так. Заметим, что всегда $N(ab)=N(a)N(b)$.
Поэтому всегда $N(ab)\geq1$, так как $ N(b)\geq1$. Кроме того, если $N(ab)=N(a)$, то непременно $N(b)=1$. Но
элементы, имеющие норму $1$ --- это в точности элементы вида $\pm2^n$, т.е. это в точности обратимые элементы из
кольца. Значит, $b$ обратимо, чем свойство 1 и доказано.

От слов "очевидно" и "легко видеть, что" бывает много ошибок. Чаще, конечно, эти слова пишутся, когда вопрос действительно
простой, чтоб не тратить зря время читателя и свое. Но иногда это способ замаскировать (возможно, и от самого себя)
трудности.

Вариант текста, который Вам предлагает Slav-27, местами напоминает вождение руками в воздухе. Преподавателю в качестве
письменной работы я бы определенно сдавал Ваш исходный текст, с небольшими поправками.

Могут ли существовать еще какие-то нормы, относительно которых указанное кольцо евклидово, я не знаю. Мне ответ
неочевиден. Знаете, бывают задачи, над которыми надо 15 мин. думать, бывают многолетние, а бывают те, над которыми
надо размышлять несколько дней или недель. Зато решение (процесс, а не результат) такой задачи очень способствует
умственному развитию. На себе проверено. Может быть, вопрос про другие нормы такой. Не знаю точно. Я бы над ним на
Вашем месте некоторое время поломал голову.

[movzx]

vpb, на самом деле в первом пункте эту оговорку можно опустить, потому что она следует из свойств нормы:
1. $N(ab)\geq N(a)$;
2. $\forall a, b\;(b\neq0)\; \exists q, r : (a=qb+r)\wedge(r=0\vee N(r)<N(b))$.

($\Rightarrow$). Если $\nexists b^{-1}$, то $a$ не делится на $ab$. Разделим $a$ на $ab$ с остатком: $a=q(ab)+r$. Так как $r=a(1-qb)$, то $N(a)\leq N(r)<N(ab)$. Получаем: $\nexists b^{-1}\Rightarrow N(a)<N(ab)$, то есть $N(ab)=N(a)\Rightarrow \exists b^{-1}$.

($\Leftarrow$). Если $\exists b^{-1}$, то $N(abb^{-1})\geq N(ab)\geq N(a)$, следовательно $N(ab)=N(a)$.

Ценность данной оговорки, как мне видится, больше конструктивная, так как помогает быстрее понять, как должна выглядеть норма. В общем, спасибо. Замечания ваши учту, про другие нормы ещё подумаю.

Чтобы далеко не ходить, могу предложить такую функцию: $N(2^nm)=k|m|, k\in\mathbb{N}$. Заметим, что $N(ab)=\frac{N(a)N(b)}k$.

1. $N(b)\geq k$. Тогда $N(ab)=\frac{N(a)N(b)}k\geq N(a)$. Обратимые элементы имеют норму $k$ (опустим доказательство).

2. Берём $q$ и $r$ такие же, как для первой нормы, то есть $r=2^{n_1}\left(m_1-m_2\left[\frac{m_1}{m_2}\right]\right)=2^{n_1+l}m_l$. Аналогично: $\left|m_l\right|\leq\left|m_1-m_2\left[\frac{m_1}{m_2}\right]\right|<\left|m_2\right| \Rightarrow k\left|m_l\right|<k\left|m_2\right|$, то есть $N(r)<N(b)$.

Значит, это норма.

[vpb]

movzx, я вижу, Вы довольно сообразительны.

То, что $N(ab)>N(a)$, если $b$ не обратимо, действительно, общее свойство нормы. Я про это забыл (на самом деле, и не знал).

Предложенную Вами конструкцию можно обобщить. Для $a=2^nm$, где $n\in{\mathbb Z}$, а $m$ --- нечетное, положим
$N_1(a)=(|m|+1)/2$. Далее, если $f:{\mathbb N}\longrightarrow{\mathbb N}$ --- любая строго
возрастающая функция, то определим $N(a)=f(N_1(a))$, а также $N(0)=0$. Легко видеть, что $N$ --- норма. Задача
теперь может быть уточнена так: существуют ли нормы, отличные от норм такого вида (т.е., вида $f(N_1(a))$)?

Slav-27, я, наверное, был не очень прав насчет Вашего текста. Я обратил внимание на недостатки, не отметив очевидных
достоинств. Ваш текст ясен и лаконичен, не загружен излишними формулами. Я так не умею. Я хотел лишь отметить, что
местами у Вас лаконичность перетекает, по моему, в недостаточную ясность (впрочем, как известно, наши недостатки ---
продолжение наших достоинств). vpb.

[movzx]

vpb, спасибо. Что-то такое и хотелось сделать, но уже не было времени обдумать.

vpb в сообщении #1151801 писал(а):

$N(0)=0$

Это лишнее: норма есть функция вида $N:A\setminus\{0\}\to\mathbb{Z}_+$.

vpb в сообщении #1151801 писал(а):

существуют ли нормы, отличные от норм такого вида (т.е., вида $f(N_1(a))$)?

Интересный вопрос. Как мне видится, ответ будет положительным. Попробую показать на несложном примере. Для начала определим $N_0(2^nm)=|m|$, далее зафиксируем произвольное простое число $p>3$. Определим функцию

$$N(2^nm)=\begin{cases}N_0(2^nm),&\text{если $m\neq p$;}\\ \left[\frac{p}2\right]_{ev}+1,&\text{если $m=p$,}\end{cases}$$

где $[x]_{ev}$ — округление к ближайшему чётному. Таким образом норма останется прежней везде, кроме одной точки, являющейся простым числом (в этой точке значение «просядет» и будет равным минимальному нечётному большему половины $p$: например для $11$ будет $7$, для $13$ — $7$, для $17$ — $9$). Покажем, что определённая функция есть норма, предварительно заметив, что $N(2^np)<N_0(2^np)$, ибо

$$\left[\frac{p}2\right]_{ev}+1<\frac{p}2+2<\frac{p}2+\frac{p}2=p,$$

так как $p>3$, а значит, $p>4$ и $\frac{p}2>2$. В общем, $N(a)\leq N_0(a)$.

1. $N(ab)=N_0(ab)\geq N_0(a)\geq N(a)$. Таким образом, первое свойство доказано.

2. Будем делить $a=2^{n_1}m_1$ на $b=2^{n_2}m_2$. Если $m_2\neq p$, то производим деление по тому же принципу, что и для нормы $N_0$. Таким образом мы получим пару чисел $q, r:(a=qb+r)\wedge(r=0\vee N(r)\leq N_0(r)<N_0(b)=N(b))$. Если $m_2=p$, то, произведя деление «обычным» способом (как для $N_0$), мы получим три возможных исхода:
1) $r = 0$ — в этом случае оставим $q$ и $r$;
2) $r=2^{n_r}m_r:|m_r|<\frac{p}2\Rightarrow|m_r|<\frac{p}2<\left[\frac{p}2\right]_{ev}+1\Rightarrow N(r)<N(b)$, следовательно $q$ и $r$ подходят;
3) $|m_r|>\frac{p}2$ — в этом случае возьмём

$$q'=2^{n_1-n_2}\left\lceil\frac{m_1}{m_2}\right\rceil,$$

$$r'=a-q'b=2^{n_1}\left(m_1-m_2\left\lceil\frac{m_1}{m_2}\right\rceil\right)=2^{n_{r'}}m_{r'}.$$

$\lceil x\rceil$ — округление «вверх» (к большему по модулю: $\lceil-2,5\rceil=-3$). Для начала стоит прояснить ситуацию. Например $p=11, N(p)=7$. Можно поделить $31$ на $11$ двумя способами: $2\cdot11+9$ либо $3\cdot11-2$. Первый способ, очевидно, не подходит, поэтому мы заменяем его вторым. Покажем, что $m_r$ и $m_{r'}$ разных знаков, приняв, что $m_2>0$ (случай, когда $m_2<0$ будет аналогичен, но с противоположными знаками):

$$\frac{m_1}{m_2}>0\Rightarrow\left[\frac{m_1}{m_2}\right]<\frac{m_1}{m_2}<\left\lceil\frac{m_1}{m_2}\right\rceil\Rightarrow m_2\left[\frac{m_1}{m_2}\right]-m_1<0<m_2\left\lceil\frac{m_1}{m_2}\right\rceil-m_1;$$

$$\frac{m_1}{m_2}<0\Rightarrow\left[\frac{m_1}{m_2}\right]>\frac{m_1}{m_2}>\left\lceil\frac{m_1}{m_2}\right\rceil\Rightarrow m_2\left[\frac{m_1}{m_2}\right]-m_1>0>m_2\left\lceil\frac{m_1}{m_2}\right\rceil-m_1.$$

Далее, заметив, что $|a|+|b|=|a-b|$, если $ab<0$:

$$\frac{p}2+|m_{r'}|<|m_r|+|m_{r'}|=|m_r-m_{r'}|=\left|m_1-m_2\left[\frac{m_1}{m_2}\right]-m_1+m_2\left\lceil\frac{m_1}{m_2}\right\rceil\right|=|m_2|=p,$$

ибо $|\lceil x\rceil-[x]|=1$, если $x\neq[x]$ (в этом случае $r'=r=0$). В итоге: $|m_{r'}|<\frac{p}2<\left[\frac{p}2\right]_{ev}+1\Rightarrow N(r')<N(b)$. Таким образом мы получили подходящую пару $q', r'$.

Результат: $N$ — норма. Надеюсь, нигде не ошибся.

(Оффтоп)

Фух!

Думаю, что можно придумать ещё изощрённее примеры: функция, которая будет «проседать» во всех простых числах, а если число составное, то будет равна максимуму норм этих чисел с прибавлением единицы. Возможно, она тоже будет нормой, но проверять не очень хочется.

[vpb]

movzx,
я вижу, Вы потратили много сил. Построенная Вами функция действительно является нормой. Однако, она
имеет вид, указанный в моем предыдущем сообщении (т.е. $f(N_1(a))$); присмотритесь внимательнее. Я думаю,
что задача не очень простая, но и не чересчур сложная (сам я не знаю как ее решать).

[movzx]

vpb, сомневаюсь, что моя норма имеет такой вид, хотя бы потому, что любая норма вашего вида не умеет различать числа разных знаков: у всех чисел вида $a=2^{n_a}m$ и $b=2^{n_b}(-m)$ при фиксированном $m$ будет одинаковая норма из-за модуля в $N_1$. Для моей нормы, к примеру, при $p=11$ это не так: $N(11)=7$, а $N(-11)=11$. Ну и плюс $N(9)=9$, поэтому мою норму не получится представить в вашем виде ($N_1$ переведёт $11$ и $-11$ в $6$, поэтому, какую бы функцию $f$ мы ни взяли, у нас не получится отличить $11$ от $-11$).

(Оффтоп)

vpb в сообщении #1153703 писал(а):

я вижу, Вы потратили много сил

Набирал целый вечер, но зато потренировался с $\TeX$'ом. Много нового узнал. Лишним не будет.

[vpb]

movzx, Вы неправы. Это очень просто. Если Вы не сообразите сами, я через пару дней напишу более подробно
(сейчас не пишу, хотя это всего три слова, чтобы Вы сами подумали). vpb.

[movzx]

vpb, давайте по порядку.
0. Возьмём норму $N$, которая строится по моему принципу при $p=11$.
1. Нужно доказать или опровергнуть, что $N=f\circ N_1$, где $N_1(2^nm)=(|m|+1)/2$, $f\colon \mathbb{N}\to\mathbb{N}$ — строго возрастающая функция.
2. $N(11)=7, N(-11)=11$.
3. Предположим, что подходящая функция $f$ существует. Тогда: $N(11)=f(N_1(11))=f(6), N(-11)=f(N_1(-11))=f(6)$.
4. $f(6)=7$, так как $N(11)=7$, но в то же время $N(-11)=11$, поэтому $f(6)=11$.
5. Стало быть, не существует подходящей функции $f$ (во всяком случае однозначной).
На каком шаге я совершил ошибку? Все свои мысли на этот счёт я изложил, поэтому уже с трудом понимаю, что не так в моих рассуждениях (видимо, взгляд «замылился» либо изначально я вас неправильно понял).

[vpb]

В евклидовом кольце, если два элемента отличаются умножением на обратимый элемент (например, противоположны),
их нормы равны.

[movzx]

vpb, именно, а значит, моя функция вовсе и не норма.

movzx в сообщении #1153141 писал(а):

1. $N(ab)=N_0(ab)$

Здесь я ошибся, ибо $N((-1)\cdot(-11))=N(11)<N(-11)$.

Ну что же. Попробуем исправить ситуацию. Зафиксируем простое число $p>3$ и определим функцию

$$N(2^nm)=\begin{cases}|m|,&\text{если $|m|\neq p$;}\\ \left[\frac{p}2\right]_{ev}+1,&\text{если $|m|=p$.}\end{cases}$$

Теперь первое свойство будет выполняться, ибо $N(ab)=N_0(ab)$ при любых $a, b$ (и обратимых, и необратимых).
В доказательстве второго свойства нужно проставить модули: «Если $|m_2|\neq p$, то производим деление по тому же принципу, что и для нормы $N_0$. <…> Если $|m_2|=p$, то, произведя деление «обычным» способом (как для $N_0$), мы получим три возможных исхода». В доказательстве разности знаков $m_r$ и $m_{r'}$ оговорка о $m_2<0$ была сделана (зачем-то), поэтому остальное остаётся в силе.

Теперь покажем, что норма $N\neq f\circ N_1$, где $N_1=(|m|+1)/2$, $f\colon\mathbb{N}\to\mathbb{N}$ — строго возрастающая функция. Рассмотрим частный случай при $p=11$:
$N(9)=f(N_1(9))=f(5)=9$;
$N(11)=f(N_1(11))=f(6)=7$.
Значит, $f$ убывает от $5$ до $6$.

В общем случае:
$N(p-2)=f(N_1(p-2))=f((p-1)/2)=p-2$;
$N(p)=f(N_1(p))=f((p+1)/2)=[p/2]_{ev}+1$.

Если $p>7$, $[p/2]_{ev}+3\leq p/2+3,5<p$ (откуда следует, что $[p/2]_{ev}+1<p-2$). Если $p=5$ или $p=7$, то $[p/2]_{ev}+1=p-2$. Окончательно: $f((p-1)/2)\geq f((p+1)/2)$, то есть $f$ — функция либо неубывающая (при $p=5$ или $p=7$), либо убывающая от $(p-1)/2$ до $(p+1)/2$.

Теперь, надеюсь, всё верно? Хотел сразу проставить модули, но отказался, решив, что так будет проще (да уж).

[vpb]

movzx, да, теперь все верно. (а я, стало быть, ошибся). Я Вам еще кое-что хочу написать по этому поводу, но сегодня не могу.