Тождество Эрмита

То́ждество Эрми́та — тождество в элементарной теории чисел, описывающее свойство целой части числа.

Для любого вещественного числа $x$ и целого $m\geqslant 1$ имеет место равенство:

\lfloor mx\rfloor =\lfloor x\rfloor +\left\lfloor x+{\frac {1}{m}}\right\rfloor +\ldots +\left\lfloor x+{\frac {m-1}{m}}\right\rfloor

(тождество Эрмита); здесь $\lfloor \cdot \rfloor$ обозначает целую часть («пол»).

«Это до некоторой степени удивительный результат, ибо функция пол является целочисленной аппроксимацией вещественнозначной величины — тем не менее, отдельное приближение слева равняется сумме их целой компании справа. Если считать, что $\lfloor x\rfloor$ — это, грубо говоря, $x-{\frac {1}{2}}$ в среднем, то левая часть, грубо говоря, равна примерно $mx-{\frac {1}{2}}$ , в то время как правая часть — это приблизительно $\left(x-{\frac {1}{2}}\right)+\left(x-{\frac {1}{2}}-{\frac {1}{m}}\right)+\ldots +\left(x-{\frac {1}{2}}+{\frac {m-1}{m}}\right)=mx-{\frac {1}{2}}$ . Но сумма всех этих грубых приближений оказывается величиной точной!»
— Р. Грэм, Д. Кнут, О. Паташник^[1].

Частным случаем тождества Эрмита является следующая формула разложения целого числа $n$ (получаемая заменой $x$ на ${\frac {n}{m}}$ ):

n=\left\lfloor {\frac {n}{m}}\right\rfloor +\left\lfloor {\frac {n+1}{m}}\right\rfloor +\ldots +\left\lfloor {\frac {n+m-1}{m}}\right\rfloor .\quad \quad \quad (*)

В своей оригинальной работе (1885)^[2] для доказательства указанного тождества Ш. Эрмит использовал аппарат производящих функций. В дальнейшем были опубликованы многочисленные более простые доказательства, некоторые из которых приведены ниже.

Доказательство Штерна

Следующее элементарное доказательство принадлежит М. А. Штерну (1886)^[3]. Существует (однозначно определённое) целое $k,\quad 0\leqslant k<m$ , для которого выполнено двойное неравенство:

\lfloor x\rfloor +{\frac {k}{m}}\leqslant x<\lfloor x\rfloor +{\frac {k+1}{m}}.\quad \quad \quad \quad (**)

Умножая все части этого неравенства на $m$ , получим

m\lfloor x\rfloor +k\leqslant mx<m\lfloor x\rfloor +k+1,

откуда

\lfloor mx\rfloor =m\lfloor x\rfloor +k

.

Из $(**)$ также получим оценки:

x+{\frac {m-k-1}{m}}<\lfloor x\rfloor +{\frac {k+1}{m}}+{\frac {m-k-1}{m}}=\lfloor x\rfloor +1

и

\lfloor x\rfloor +1=\lfloor x\rfloor +{\frac {k}{m}}+{\frac {m-k}{m}}\leqslant x+{\frac {m-k}{m}},

то есть:

x+{\frac {m-k-1}{m}}<\lfloor x\rfloor +1\leqslant x+{\frac {m-k}{m}}.

Отсюда сразу следует, что каждое из слагаемых

\lfloor x\rfloor ,\left\lfloor x+{\frac {1}{m}}\right\rfloor ,\ldots ,\left\lfloor x+{\frac {m-k-1}{m}}\right\rfloor

равно $\lfloor x\rfloor$ , а каждое из слагаемых

\left\lfloor x+{\frac {m-k}{m}}\right\rfloor ,\left\lfloor x+{\frac {m-k+1}{m}}\right\rfloor ,\ldots ,\left\lfloor x+{\frac {m-1}{m}}\right\rfloor

равно $\lfloor x\rfloor +1$ . Поэтому сумма всех этих слагаемых равна

(m-k)\lfloor x\rfloor +k(\lfloor x\rfloor +1)=m\lfloor x\rfloor +k=\lfloor mx\rfloor .

Доказательство Пойа и Сегё

Из равенства $\lfloor y+l\rfloor =\lfloor y\rfloor +l$ , верного для произвольных $x\in \mathbb {R} ,\ l\in \mathbb {Z}$ , следует, что для доказательства тождества Эрмита достаточно рассмотреть случай $0\leqslant x<1$ . Пусть (в этом предположении) целое $k$ выбрано так, что

x+{\frac {k-1}{m}}<1\leqslant x+{\frac {k}{m}}.\quad \quad \quad (***)

Отсюда последовательно получаем:

mx+(k-1)<m\leqslant mx+k,

k-1<m-mx\leqslant k,

-k\leqslant mx-m<-k+1,

то есть $-k=\lfloor mx-m\rfloor =\lfloor mx\rfloor -m$ и тогда $\lfloor mx\rfloor =m-k$ .

Из $(***)$ также сразу следует, что каждое из слагаемых

\lfloor x\rfloor ,\left\lfloor x+{\frac {1}{m}}\right\rfloor ,\ldots ,\left\lfloor x+{\frac {k-1}{m}}\right\rfloor

равно $0$ , а каждое из оставшихся слагаемых

\left\lfloor x+{\frac {k}{m}}\right\rfloor ,\left\lfloor x+{\frac {k+1}{m}}\right\rfloor ,\ldots ,\left\lfloor x+{\frac {m-1}{m}}\right\rfloor

равно $1$ . Таким образом, обе части доказываемого равенства равны $m-k$ .

Это доказательство было опубликовано Д. Пойа и Г. Сегё в первом издании их знаменитого сборника задач и теорем из анализа (1925)^[4].

Доказательство Мацуоки

Следующее короткое доказательство, основанное на функциональном тождестве, принадлежит Ёсио Мацуоке (1964)^[5]. Рассмотрим (для фиксированного $m$ ) вещественную функцию:

f(x)=\lfloor mx\rfloor -\lfloor x\rfloor -\left\lfloor x+{\frac {1}{m}}\right\rfloor -\ldots -\left\lfloor x+{\frac {m-1}{m}}\right\rfloor .

Тождество Эрмита будет установлено, если будет доказано, что эта функция тождественно равна нулю. Для любого $x\in \mathbb {R}$ имеем:

f\left(x+{\frac {1}{m}}\right)=\lfloor mx+1\rfloor -\left\lfloor x+{\frac {1}{m}}\right\rfloor -\left\lfloor x+{\frac {2}{m}}\right\rfloor -\ldots -\left\lfloor x+{\frac {m-1}{m}}\right\rfloor -\lfloor x+1\rfloor =f(x)

(поскольку $\lfloor mx+1\rfloor =\lfloor mx\rfloor$ и $\lfloor x+1\rfloor =\lfloor x\rfloor$ ). Вместе с тем, очевидно, $f(x)=0$ при $0\leqslant x<{\frac {1}{m}}$ . Поэтому $f(x)=0$ для всех $x\in \mathbb {R}$ .

Доказательство с помощью формулы разложения целого числа

Формулу разложения $(*)$ легко доказать без применения тождества Эрмита — например, индукцией по $n$ (формула верна для $n=0$ , и, если она верна для $n\in \mathbb {Z}$ , то верна и для $n\pm 1$ ), либо (что, по существу, то же самое) методом, аналогичным методу Мацуоки, описанным выше: рассмотреть, при фиксированном $m$ , функцию, определённую для всех $n\in \mathbb {Z}$ равенством:

\varphi (n)=n-\left\lfloor {\frac {n}{m}}\right\rfloor +\left\lfloor {\frac {n+1}{m}}\right\rfloor +\ldots +\left\lfloor {\frac {n+m-1}{m}}\right\rfloor ,

и заметить, что $\varphi (0)=0$ и $\varphi (n+1)=\varphi (n)$ для всех $n\in \mathbb {Z}$ , откуда заключить, что $\varphi (n)\equiv 0$ .

Далее, тождество Эрмита можно вывести из формулы $(*)$ , если в ней положить $n=\lfloor mx\rfloor$ и воспользоваться равенством^[1]:

\left\lfloor {\frac {\lfloor y\rfloor +k}{m}}\right\rfloor =\left\lfloor {\frac {y+k}{m}}\right\rfloor ,

верным для произвольных $y\in \mathbb {R}$ и $k,m\in \mathbb {Z}$ , $m\geqslant 0$ .

Быстрое вычисление сумм

Пример. Найти $\left\lfloor x\right\rfloor +\left\lfloor x+{\tfrac {1}{3}}\right\rfloor +\left\lfloor x+{\tfrac {2}{3}}\right\rfloor$ .

По тождеству Эрмита (при (n=3)) : $\lfloor 3x\rfloor$ .

Вместо трёх выражений считаем одно.

Теория чисел (оценки и делимость)

Пример. Нужно оценить сумму $\sum _{k=0}^{n-1}\left\lfloor {\frac {a+k}{n}}\right\rfloor$ .

Тождество Эрмита даёт $=\left\lfloor {\frac {na}{n}}\right\rfloor =\lfloor a\rfloor$ .

Это используется в доказательствах делимости и при работе с остатками.

Упрощение сложных сумм

Пример: $\sum _{k=0}^{4}\left\lfloor 2.3+{\frac {k}{5}}\right\rfloor$ .

По Эрмиту: $=\lfloor 5\cdot 2.3\rfloor =\lfloor 11.5\rfloor =11$ .

Без формулы пришлось бы считать 5 значений отдельно.

Олимпиадные задачи

Типичная задача:

Найти $\sum _{k=1}^{n}\left\lfloor {\frac {k}{m}}\right\rfloor$ .

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

Анализ равномерного распределения

Тождество Эрмита показывает, что числа вида $x,x+{\tfrac {1}{n}},x+{\tfrac {2}{n}},\dots$ распределяются равномерно по единичному отрезку.

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

↑ ¹ ² Конкретная математика, 1998, с. 108.
↑ Hermite Ch. Sur quelques conséquences arithmétiques des formules de la théorie des fonctions elliptiques (Extrait du Bulletin de l’Acad. Sci. St. Pétersb. T. 29) (фр.) // Acta Math. — 1885. — Vol. 5. — P. 297–330..
↑ Stern M. A. Sur un théorème de M. Hermite relatif à la fonction E(x) (фр.) // Acta Math. — 1886. — Vol. 8. — P. 93–96..
↑ Pólya G., Szegö G. Aufgaben und Lehrsätze aus der Analysis (нем.). — Berlin, Heidelberg: Springer-Verlag. — Bd. II: Functiontheorie, Nullstellen, Polynome, Determinanten, Zahlentheorie. — S. 118, 324. — (Die Grundlehren der mathematischen Wissenschaften in Enzeldarstellungen; Bd. XX).; см. также русский перевод 3-го немецкого издания (1964): Полиа Г., Сеге Г. Задачи и теоремы из анализа. Ч. 2: Теория функций (специальная часть). Распределение нулей. Полиномы. Определители. Теория чисел. (рус.) / Пер. с нем. Д. А. Райкова. — 3-е изд. — М.: Наука, 1978. — С. 131, 346. — 431 с.
↑ Matsuoka Y. On a Proof of Hermite's Identity (англ.) // The American Mathematical Monthly. — 1964. — Vol. 71, iss. 10. — P. 1115. — doi:10.2307/2311413 . — JSTOR 2311413..

Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика. Основание информатики. — М.: «Мир», 1998. — С. 106—108. — 703 с. — ISBN 5-03-001793-3.
Семёнов И. Л. Антье и мантисса. Сборник задач с решениями (рус.) / Под ред. Е. В. Хорошиловой. — М.: ИПМ им. М. В. Келдыша, 2015. — С. 52—53, 217—218. — 432 с. — ISBN 978-5-98354-014-9.

[_37d8212be265a6e3-1] ¹ ² Конкретная математика, 1998, с. 108.

[2] Hermite Ch. Sur quelques conséquences arithmétiques des formules de la théorie des fonctions elliptiques (Extrait du Bulletin de l’Acad. Sci. St. Pétersb. T. 29) (фр.) // Acta Math. — 1885. — Vol. 5. — P. 297–330..

[3] Stern M. A. Sur un théorème de M. Hermite relatif à la fonction E(x) (фр.) // Acta Math. — 1886. — Vol. 8. — P. 93–96..

[4] Pólya G., Szegö G. Aufgaben und Lehrsätze aus der Analysis (нем.). — Berlin, Heidelberg: Springer-Verlag. — Bd. II: Functiontheorie, Nullstellen, Polynome, Determinanten, Zahlentheorie. — S. 118, 324. — (Die Grundlehren der mathematischen Wissenschaften in Enzeldarstellungen; Bd. XX).; см. также русский перевод 3-го немецкого издания (1964): Полиа Г., Сеге Г. Задачи и теоремы из анализа. Ч. 2: Теория функций (специальная часть). Распределение нулей. Полиномы. Определители. Теория чисел. (рус.) / Пер. с нем. Д. А. Райкова. — 3-е изд. — М.: Наука, 1978. — С. 131, 346. — 431 с.

[5] Matsuoka Y. On a Proof of Hermite's Identity (англ.) // The American Mathematical Monthly. — 1964. — Vol. 71, iss. 10. — P. 1115. — doi:10.2307/2311413 . — JSTOR 2311413..

[1]

[2]

[3]

[4]

[5]

Тождество Эрмита

Формулировка

Доказательства

Доказательство Штерна

Доказательство Пойа и Сегё

Доказательство Мацуоки

Доказательство с помощью формулы разложения целого числа

Применение

Примечания

Литература

Категории