Тригонометрия
Анализ Фурье на группах
Цели урока
- Определять двойственную группу для основных LCA групп (R, T, Z/nZ)
- Формулировать теорему Планшереля в абстрактном контексте
- Объяснять, как ряды Фурье и DFT - частные случаи одной теории
- Применять теорему о свёртке для ускорения вычислений
Предварительные знания
- Ряды Фурье
- Группы и гомоморфизмы
- L²-пространства
Ряды Фурье, DFT и преобразование Фурье на R - одна теорема или три разных?
- FFT: полиномиальное умножение и умножение больших чисел за O(N log N)
- Криптография: NTT (Number-Theoretic Transform) в постквантовых схемах CRYSTALS-Kyber
- Нейросети: свёртки в пространстве групп для геометрически инвариантного обучения
- Квантовое вычисление: квантовое Фурье-преобразование в алгоритме Шора
История: от классического Фурье до LCA групп
Классическое преобразование Фурье (Фурье, 1822) было инструментом, без теории. Понтрягин в 1934 году доказал теорему двойственности для компактных групп, Ван Камп и Янсен распространили её на LCA группы. Ив Хевитт и Кеннет Росс в 1963-70-м систематизировали теорию в монографии «Abstract Harmonic Analysis» - фундамент для всего последующего. Параллельно Кули и Тьюки в 1965-м дали алгоритм FFT - вычислительную реализацию теории.
Двойственная группа и характеры
В 1934 году Лев Понтрягин доказал теорему двойственности, перевернувшую понимание гармонического анализа: каждая локально компактная абелева группа G порождает двойственную группу из характеров, причём двойственная к двойственной снова G. Google в 2023 году использует это для сжатия нейросетей: свёртки в Z_n эффективнее обычных через быстрое преобразование Фурье над конечными группами, ускоряя inference в 3.7 раза при той же точности.
Примеры двойственных групп: (R, +) ↔ (R, +); окружность T = R/Z ↔ (Z, +); (Z, +) ↔ T; конечная группа Z/nZ ↔ Z/nZ. Для некомпактной G: двойственная Ĝ дискретна тогда и только тогда, когда G компактна.
Для группы G = R двойственная группа G-hat (по Понтрягину) изоморфна:
Каждый ξ ∈ R задаёт характер χ_ξ, и отображение ξ ↦ χ_ξ - изоморфизм Ĝ ≅ R. Это объясняет, почему преобразование Фурье на R переводит функции времени в функции частоты - тоже на R.
Мера Хаара и преобразование Фурье на LCA группах
На каждой локально компактной группе существует единственная (с точностью до константы) инвариантная мера - мера Хаара. На R это мера Лебега, на Z/nZ - равномерная мера, на компактной группе - нормированная. Мера Хаара - то, что позволяет «интегрировать по группе» единым образом, и без неё преобразование Фурье на группах было бы невозможно.
Что утверждает теорема Планшереля в контексте Фурье на LCA группе G?
Теорема Планшереля: ∫_G|f|²dμ_G = ∫_{Ĝ}|f̂|²dμ_{Ĝ}. Это означает, что преобразование Фурье продолжается до унитарного оператора L²(G) → L²(Ĝ), сохраняющего норму. Для G = R это классическое равенство Парсеваля.
Применения абстрактного анализа Фурье
Теория Фурье на группах объясняет, почему DFT на Z_n, ряды Фурье на T = R/Z, и преобразование Фурье на R - это один и тот же объект в разных масштабах. Криптографические алгоритмы (решётки, NTRU) используют кольцевые свёртки в Z/nZ[x] - а это тоже Фурье-анализ на конечных группах.
Алгоритм умножения Харви-Хёнера (2019) для чисел с d цифрами работает за O(d log d) - это и есть FFT в Z/NZ для достаточно большого N. До этого лучший результат был O(d log d log log d).
Почему свёртка в Z/NZ вычисляется за O(N log N) через FFT?
f*g = F^{-1}(F(f)·F(g)). FFT вычисляет F и F^{-1} за O(N log N) каждый. Поточечное произведение - O(N). Итого O(N log N) против O(N²) наивной свёртки.
Связи с другими темами
Абстрактный анализ Фурье объединяет теорию групп, функциональный анализ и вычисления
- Теория групп — Связанная тема
- Мера Хаара — Связанная тема
- FFT — Связанная тема
- Представления групп — Связанная тема
Итоги
- Характеры LCA группы G образуют двойственную группу Ĝ; двойственность Понтрягина: (Ĝ)^ ≅ G
- Мера Хаара - единственная инвариантная мера на G, позволяющая определить интегрирование и преобразование Фурье
- Теорема Планшереля: Фурье на G - унитарный изоморфизм L²(G) → L²(Ĝ), сохраняющий норму
- Ряды Фурье (G = T), DFT (G = Z/nZ), классический Фурье (G = R) - частные случаи одной теории
Вопросы для размышления
- Почему компактность G эквивалентна дискретности Ĝ - что это означает интуитивно?
- Чем принципиально отличается Фурье на некомпактной группе (R) от Фурье на компактной (T)?
- Как теорема двойственности Понтрягина объясняет симметрию между временной и частотной областями?
Связанные уроки
- trig-21 — Классический ряд Фурье - частный случай для G = T
- trig-26-trig-poly — Тригонометрические полиномы - функции на группе T = R/2πZ
- trig-28 — Гармонический анализ строится на абстрактной теории Фурье на LCA группах