Глава 2. Уолш–Адамар: преобразование без трансцендентностей

Где стоит глава

Центр Части VII

Предыдущая глава построила абстрактную теорию: ортонормированная система, коэффициенты Фурье, проекция, Бессель, Парсеваль, наилучшее приближение — и завершилась обещанием предъявить конкретную рациональную систему, на которой вся эта геометрия работает без единой трансцендентности. Настоящая глава это обещание выполняет. Её героиня — преобразование Уолша–Адамара: ортогональное $\pm 1$-преобразование над булевым кубом $Z_2^n$, которое играет для конечного гармонического анализа ту же роль, что преобразование Фурье — для непрерывного, но не требует ни синусов, ни косинусов, ни комплексной экспоненты.

Это центральная глава Части VII, и выбор её предмета не случаен. Классический гармонический анализ строится на характерах окружности — функциях $e^{2\pi ikx}$, которые сразу вводят и трансцендентные значения, и мнимую единицу, и завершённый бесконечный спектр. ToS спрашивает: что в гармоническом анализе остаётся чисто рациональным, конечным и доказуемым без аксиом? Ответ: целый параллельный мир, если заменить группу окружности на булев куб $Z_2^n$. Его характеры — функции Уолша — принимают лишь значения $\pm 1$, их ортогональность есть точное тождество над ℚ, а сохранение энергии — конечная сумма. Трансцендентная тригонометрия и комплексный DFT остаются честной границей и разбираются в Главе 7.3; здесь — рациональное ядро.

Что эта глава утверждает — и что нет

Доказано здесь следующее, и всё — без единой аксиомы.¹ Матрица Адамара $H_{2^k}$ строится рекурсией Сильвестра из значений $\pm 1$; её строки попарно ортогональны с квадратом нормы $N=2^k$, то есть $H_N^{\mathsf{T}}{H}_N=N\cdot I$, и это доказано для всех $2^k$. Функции Уолша — характеры группы $(Z_2^n,\oplus )$: значение на сумме (по модулю 2) аргументов есть произведение значений. Преобразование сохраняет энергию, $\text{norm}{Hf}^2=N\text{norm}{f}^2$ (дискретное равенство Планшереля), и обратимо с точностью до масштаба, $H(Hf)=Nf$. Наконец, нормированный случай $N=2$, если вынести $1/\sqrt{2}$ в абстрактный параметр $s$ с соотношением $s^2\cdot 2=1$, — это в точности квантовый вентиль Адамара.

Чего глава не утверждает. Буквальная ортонормированность $\text{inner}{e}_i{e}_j={\delta }_{ij}$ требует множителя $1/\sqrt{N}$, рационального лишь когда $N$ — точный квадрат (для $N=2^k$ — лишь при чётном $k$); поэтому нормировка вводится абстрактным параметром, а не вычисляется. Комплексный DFT (корни единицы $e^{2\pi ik/N}$, мнимая единица $i$) и непрерывная тригонометрия — честная P4-граница (Глава 7.3). И <<частота>> здесь — не вещественное число, а характер конечной группы; упорядочение строк по числу знакоперемен (секвентность) — перестановка, не меняющая ортогональности.

E/R/R-каркас главы

Каркас системы в порождающем порядке Rules $\to$ Roles $\to$ Elements; полный разбор — в § «Разбор в порождающем порядке». Глава вводит систему преобразования Уолша–Адамара.

Rules (Правила, $\leftrightarrow$ L5). Рекурсия Сильвестра $H_{2N}=\left[\begin{array}{cc}{H}_N& H_N\\ H_N& -H_N\end{array}\right]$; ортогональность $H_N^{\mathsf{T}}{H}_N=N\cdot I$; характерное свойство ${\mathrm{w}}_i(a\oplus b)={\mathrm{w}}_i(a){\mathrm{w}}_i(b)$; сохранение энергии $\text{norm}{Hf}^2=N\text{norm}{f}^2$.

Roles (Роли, $\leftrightarrow$ L4). Строка ${\mathrm{w}}_i$ — роль-характер (частота как характер группы); $H$ — роль-преобразование; $\oplus$ — роль-операция группы $Z_2^n$; нормировка $1/\sqrt{N}$ — роль-предел.

Elements (Элементы, $\leftrightarrow$ L1$+$P4). Рациональные значения $\pm 1$ матрицы, индексы $i,j<2^k$, амплитуды $f_j\in Q$, конечные суммы; завершённый спектр и трансцендентные значения — вне элементов (P4).

Матрица Адамара: рекурсия Сильвестра

Удвоение вместо колебания

Тригонометрическая гармоника задаётся колебанием: $\cos$ и $\sin$ пробегают непрерывный диапазон значений. Функция Уолша задаётся удвоением знаковой таблицы. Базовый блок — единичная матрица $H_1=[1]$. Каждый следующий уровень получается рекурсией Сильвестра:

$$H_{2N}=\left(\begin{array}{cc}{H}_N& H_N\\ H_N& -H_N\end{array}\right),$$

так что

$$H_2=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),H_4=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 1& -1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\end{array}\right).$$

Каждый элемент — $+1$ или $-1$, то есть чисто рациональное число; никакого предельного перехода, никаких трансцендентных значений.² Знак элемента $(i,j)$ определяется старшими битами индексов $i$ и $j$: верхне-левый, верхне-правый и нижне-левый блоки повторяют $H_N$, а нижне-правый берётся с минусом — ровно это и кодирует рекурсивная формула.

Строки как функции Уолша

$i$-я строка матрицы — это функция Уолша ${\mathrm{w}}_i$: она сопоставляет столбцу $j$ знак $H_{ij}\in \{\pm 1\}$. Это дискретный аналог $i$-й гармоники: чем <<выше частота>>, тем чаще функция меняет знак вдоль строки. Аналогия с тригонометрией здесь буквальна по структуре и расходится лишь в носителе: вместо непрерывного отрезка — конечное множество из $N=2^k$ точек, вместо вещественных значений колебания — знаки $\pm 1$.

Гармоника Уолша — это не колебание, а знаковый узор, построенный удвоением. <<Частота>> измеряется числом знакоперемен, а не вещественным аргументом синуса; весь спектр конечен и рационален.

Оговорим один технический нюанс. Рекурсия Сильвестра нумерует строки в так называемом естественном (адамаровом) порядке, который не совпадает с упорядочением по возрастанию числа знакоперемен (секвентности) — истинным аналогом возрастания частоты. Переход к секвентному порядку есть перестановка строк; она не меняет ни ортогональности, ни сохранения энергии, поэтому всё доказанное ниже от выбора порядка не зависит.

Ортогональность: $H_N^{\mathsf{T}}{H}_N=N\cdot I$

Точное тождество вместо интеграла

Сердце всякого гармонического анализа — ортогональность базисных функций. В тригонометрии она выражается интегралами $\int \sin (mx)\sin (nx)dx=0$ при $m\ne n$ — а это уже трансцендентный объект: интеграл от произведения трансцендентных функций. У Уолша та же ортогональность есть конечная сумма произведений знаков:

$$\sum _{j<N}{H}_{ij}{H}_{i^{\prime }j}=\{\begin{array}{ll}N,& i=i^{\prime },\\ 0,& i\ne i^{\prime },\end{array}$$

то есть $H_N^{\mathsf{T}}{H}_N=N\cdot I$. Разные строки ортогональны, а каждая имеет квадрат нормы $N$. И это доказано для всех $N=2^k$ — индукцией по рекурсивной структуре Сильвестра, как точное тождество над ℚ, без единой аксиомы.³

Ортогональность Уолша — не интеграл, который надо <<взять>>, а конечная сумма $\pm 1$, которая вычисляется. Там, где тригонометрия опирается на анализ трансцендентных функций, Уолш опирается на сложение целых чисел.

Именно это и делает Уолша–Адамара точкой опоры рациональной гармонии: ортогональная система, на которой буквально выполняется вся абстрактная теория Главы 7.1 (коэффициенты, проекция, Бессель, Парсеваль), причём каждая её предпосылка — $\text{inner}{e}_i{e}_j=N{\delta }_{ij}$ — не постулат, а доказанное равенство.

Функции Уолша как характеры булева куба

Что такое гармонический анализ на самом деле

За всем гармоническим анализом стоит одна идея: разложить функцию по характерам группы — гомоморфизмам группы в мультипликативную группу значений. Для окружности характеры суть $x\mapsto e^{2\pi ikx}$, и ключевое их свойство — превращение сложения аргументов в произведение значений: $e^{2\pi ik(x+y)}=e^{2\pi ikx}{e}^{2\pi iky}$. Именно это свойство стоит за теоремой о свёртке, за сохранением энергии, за всей алгеброй Фурье.

Функции Уолша обладают ровно тем же свойством — но для другой группы и с рациональными значениями. Группа здесь — булев куб $(Z_2^n,\oplus )$ с операцией побитового сложения по модулю 2 (XOR), а значения характеров — $\pm 1$. Доказано:

$${\mathrm{w}}_i(a\oplus b)={\mathrm{w}}_i(a){\mathrm{w}}_i(b)(i,a,b<2^k),$$

то есть каждая функция Уолша ${\mathrm{w}}_i$ — гомоморфизм $(Z_2^n,\oplus )\to (\{\pm 1\},\cdot )$, характер булева куба.⁴

Функция Уолша — это характер булева куба: она переводит групповую операцию $\oplus$ в умножение. <<Частота>> $i$ — не число, а метка характера. Гармонический анализ Уолша — это анализ Фурье на $Z_2^n$, где трансцендентную окружность заменил рациональный куб.

Почему это и есть <<настоящий Фурье>>

Отсюда видно, в каком точном смысле Уолш — не <<упрощённая имитация>> Фурье, а его полноправный собрат. Структура одна и та же: ортогональный базис характеров абелевой группы — а после нормировки $1/\sqrt{N}$ он становится ортонормированным; в Уолш-слое сама ортогональная структура рациональна, нормировка же вынесена как отдельная граница. Меняется лишь группа: вместо окружности $\mathbb{T}$ (или $Z_N$ с корнями единицы) — булев куб $Z_2^n$. Окружность тянет за собой трансцендентность и комплексность; куб остаётся в ℚ. Всё, что в анализе Фурье держится на характерном свойстве — сохранение энергии и теорема о свёртке. Энергию мы уже сохранили; теорема о свёртке $H(f\ast g)=(Hf)\cdot (Hg)$ опирается на тот же характер и доказана для всех $2^k$ — через переиндексацию конечной суммы под XOR-биекцией — а разворачивается в Главе 7.5.⁵

Сохранение энергии и вентиль Адамара

Дискретное равенство Планшереля

Из ортогональности следует сохранение энергии. Преобразование Уолша функции $f$ — вектор её коэффициентов $(Hf{)}_i={\sum }_{j<N}{H}_{ij}{f}_j$. Тогда

$$\text{norm}{Hf}^2=N\text{norm}{f}^2,$$

дискретный аналог равенства Планшереля: энергия спектра равна энергии сигнала с множителем $N$.⁶ Преобразование к тому же обратимо: применённое дважды, оно лишь перемасштабирует сигнал,

$$H(Hf)=Nf,$$

так что обратное преобразование есть $H^{-1}=\frac{1}{N}H$ — снова без всякой трансцендентности.⁷ Переход к нормированной системе делит обе части на $N$ и возвращает Парсеваль Главы 7.1 в форме ${\sum }_i{c}_i^2=\text{norm}{f}^2$ — но множитель $1/\sqrt{N}$, делающий $H/\sqrt{N}$ изометрией, рационален лишь при чётном $k$ и в общем случае остаётся роль-пределом.

Вентиль Адамара: мост в квантовые вычисления

Случай $N=2$ имеет собственное имя. Матрица $H_2=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$, нормированная множителем $1/\sqrt{2}$, — это квантовый вентиль Адамара, элементарный кирпич квантовых вычислений (он создаёт суперпозицию в алгоритмах Гровера, Дойча–Йожи и др.). Две его определяющие черты доказаны как рациональные факты, с единственной трансцендентностью — нормировкой — вынесенной в абстрактный параметр.

Во-первых, вентиль есть инволюция: $H^2=I$, применённый дважды он возвращает исходное состояние.⁸ Во-вторых, он создаёт равную суперпозицию: из базисного состояния $|0⟩$ он делает вектор с равными амплитудами $1/\sqrt{2}$ на обоих исходах.⁹

Сохранение энергии — точный рациональный факт ($\text{norm}{Hf}^2=N\text{norm}{f}^2$); квантовый вентиль Адамара — это нормированное преобразование Уолша на двух точках. Единственная трансцендентность — нормировка $1/\sqrt{N}$ — отделена и помечена; структура вентиля (инволюция, суперпозиция) рациональна.

E/R/R-разбор: преобразование как характеры группы

Постановка

Разберём построенную систему — преобразование Уолша–Адамара — в терминах E/R/R. Оговорка об уровне: <<система Уолша>> здесь — содержательная интерпретация конкретной матрицы $H_{2^k}$ и её действия, а не объект, объявленный в коде как System. Разбор есть онтологическое осмысление структуры главы и чтение авторских E/R/R-шапок опорных файлов,¹⁰ а не приписывание коду новых формальных утверждений.

Ведём разбор в порождающем порядке Rules $\to$ Roles $\to$ Elements (эпистемически глава шла обратно — от наблюдаемой матрицы к её групповому смыслу).

Разбор в порождающем порядке

Rules (Правила, $\leftrightarrow$ L5). В основании — порождающее правило матрицы: рекурсия Сильвестра, удваивающая знаковую таблицу. Над ним — правила, которые эту таблицу удерживают: ортогональность $H_N^{\mathsf{T}}{H}_N=N\cdot I$, характерное свойство ${\mathrm{w}}_i(a\oplus b)={\mathrm{w}}_i(a){\mathrm{w}}_i(b)$ (гомоморфизм в $\{\pm 1\}$) и сохранение энергии $\text{norm}{Hf}^2=N\text{norm}{f}^2$. Универсальный слой — законы L1–L5; конкретный слой — именно рекурсия Сильвестра и групповая операция $\oplus$.

Roles (Роли, $\leftrightarrow$ L4). Правила задают роли. Строка ${\mathrm{w}}_i$ — роль-характер: место, которое <<частота>> $i$ занимает как гомоморфизм группы. Само $H$ — роль-преобразование (снятие всех координат разом). Операция $\oplus$ — роль групповой структуры на множестве индексов. А нормировка $1/\sqrt{N}$ — роль-предел: то, что превращает ортогональную систему в ортонормированную; при квадратных $N$ она рациональна, в общем же случае не актуализируется над ℚ.

Elements (Элементы, $\leftrightarrow$ L1$+$P4). Роли подбирают носителей, и носители конечны и рациональны: значения $\pm 1$ элементов матрицы, индексы $i,j<2^k$, амплитуды $f_j\in Q$, конечные суммы ${\sum }_{j<N}$. Под P4 ни один элемент не есть завершённая бесконечность и ни одно значение не трансцендентно: актуальны лишь конечная матрица и конечные суммы; завершённый спектр и значение $1/\sqrt{N}$ для нечётного $k$ не актуализируются.

Компонент	Что фиксирует	E/R/R
рекурсия Сильвестра; $H^{\mathsf{T}}H=N\cdot I$; ${\mathrm{w}}_i(a\oplus b)={\mathrm{w}}_i(a){\mathrm{w}}_i(b)$; $\text{norm}{Hf}^2=N\text{norm}{f}^2$	КАК построено и сохраняется преобразование	Rules ($L5$)
характер ${\mathrm{w}}_i$; преобразование $H$; операция $\oplus$; нормировка $1/\sqrt{N}$	ЗАЧЕМ значимы носители: места в системе	Roles ($L4$)
значения $\pm 1$; индексы $i,j<2^k$; $f_j\in Q$; конечные суммы ${\sum }_{j<N}$	ЧТО есть на каждой стадии (конечно, рационально, P4)	Elements ($L1$, P4)

Проверка сформированности и что даёт разбор

{ Система сформирована корректно: каждый компонент попадает ровно в одну E/R/R-категорию, и нет самоотнесения (P1). Существенно, чего здесь нет: система не берёт своим элементом ни завершённый бесконечный спектр, ни трансцендентное значение. <<Частота>> не есть вещественное число-элемент — это роль-характер конечной группы; группа $(Z_2^n,\oplus )$ конечна, её характеров ровно $N$, и все они предъявлены как строки конкретной матрицы.}

Что даёт разбор. Он вскрывает, почему Уолш есть подлинный гармонический анализ, а не его суррогат: функция Уолша — это Роль (характер группы), преобразование — это Правило (рекурсия плюс ортогональность плюс сохранение энергии), а $\pm 1$-значения и амплитуды — Элементы (конечные, рациональные). Трансцендентность входит в классический Фурье не через идею гармонического анализа, а через выбор группы — окружности. Заменив окружность булевым кубом, мы получаем ту же идею в чисто рациональном исполнении. Брать же <<частоту>> за вещественное число или спектр за завершённый бесконечный объект — ставить роль-предел на место Элемента, то же смешение категорий, что вело Части II и IV.

Следующая глава очерчивает границу с другой стороны: что происходит, когда группой всё же берут окружность — непрерывную тригонометрию и комплексный DFT с корнями единицы. Там видно, что именно становится трансцендентным и почему ToS держит это как честную P4-границу, а рациональным ядром гармонического анализа оставляет Уолша–Адамара.

---

---

Часть: Часть VII. Гармонический анализ · Том: «Математика»

Навигация: ← Глава 1. Ортонормированные системы и коэффициенты Фурье · Глава 3. Тригонометрия и комплексный DFT: где граница →

Footnotes

1. Опорный файл — ProcessWalshHadamard.v (каталог src/process/ Rocq-репозитория ToS, 12 доказанных утверждений, 0 Admitted, 0 аксиом), дополненный ProcessFourierON.v (5 утверждений), ProcessWalshCharacter.v (7 утверждений) и ProcessHadamardGate.v (5 утверждений). Имена лемм — в сносках ниже. ↩

2. В коде матрица задана рекурсивно: had k i j возвращает элемент $(i,j)$ матрицы $H_{2^k}$ как значение из $\{+1,-1\}$ (ProcessWalshHadamard.v); размер $N=2^k$ — pow2 k. Знаковая природа закреплена леммой had_sq: каждый элемент в квадрате равен $1$. ↩

3. Центральная теорема hadamard_orthogonal в ProcessWalshHadamard.v: ${\sum }_{j<2^k}{H}_{ij}{H}_{i^{\prime }j}=2^k{\delta }_{i{i}^{\prime }}$, доказано индукцией по $k$. Диагональный случай ($i=i^{\prime }$) — walsh_norm: каждая строка имеет квадрат нормы $N$. Конкретные $N=2,4$ — hadamard_2_orthogonal, hadamard_4_orthogonal. Все — 0 аксиом. ↩

4. Теорема had_character в ProcessWalshCharacter.v: $‘had‘ki(a\oplus b)=‘had‘kia\cdot ‘had‘kib$, доказано индукцией по $k$ с разбором битовой структуры Nat.lxor (XOR). 0 аксиом. XOR здесь — операция группы $Z_2^n$. ↩

5. Общая свёртка — walsh_convolution в ProcessWalshConvolutionGeneral.v: $H(f\ast g)=(Hf)\cdot (Hg)$ для всех $2^k$, через характер (had_character) и лемму xor_perm_q_sum (инвариантность q_sum под XOR-биекцией, доказанная блочной рекурсией Сильвестра). 0 аксиом. ↩

6. Теорема parseval_walsh в ProcessFourierON.v: $\text{inner}Hf{Hf}_N=N\text{inner}f{f}_N$, выведено из самосопряжённости преобразования (матрица Уолша симметрична — had_symmetric) и тождества $H^2=N\cdot I$. 0 аксиом. ↩

7. walsh_HH в ProcessFourierON.v: $H(Hf)=Nf$ (обращение Фурье с точностью до $1/N$); следует из $H_N^{\mathsf{T}}{H}_N=N\cdot I$ и симметрии $H$. ↩

8. hgate_involution в ProcessHadamardGate.v: для нормированного вентиля $‘hgate‘(‘hgate‘f)=f$. Нормировка $1/\sqrt{2}$ введена абстрактным параметром $s$ с соотношением $s^2\cdot 2=1$; тождество $H(Hf)=2f$ (частный случай $N=2$) тогда даёт $s^2\cdot 2\cdot f=f$. Сами элементы $H_2$ — из $\{\pm 1\}$ (hadamard_2x2). ↩

9. hgate_superposition: $‘hgate‘e_0=(s,s)$ — равные амплитуды на двух координатах. Это и есть переход от определённого состояния к суперпозиции, выполняемый вентилем Адамара. ↩

10. Шапки дают разметку прямо: ProcessWalshHadamard.v — Elements: $\pm 1$-матрица, размер $2^k$; Rules: рекурсия Сильвестра, $H^{\mathsf{T}}H=N\cdot I$. ProcessWalshCharacter.v — Rules: ${\mathrm{w}}_i(a\oplus b)={\mathrm{w}}_i(a){\mathrm{w}}_i(b)$; Roles: ${\mathrm{w}}_i$ — характер $(Z_2^n,\oplus )\to \{\pm 1\}$. ProcessFourierON.v — Rules: $\text{norm}{Hf}^2=N\text{norm}{f}^2$. ↩