Теоретико-числовое дискретное преобразование Фурье

Теоре́тико-числово́е дискре́тное преобразова́ние Фурье́, преобразование вектора из ${\displaystyle n}$ элементов ${\displaystyle x=(x_{0},x_{1},x_{2},\ldots ,x_{n-1})}$ поля или ассоциативного коммутативного кольца с единицей ${\displaystyle R}$ (далее кольцо с единицей) в другой вектор ${\displaystyle y=(y_{0},y_{1},y_{2},\ldots ,y_{n-1})}$ из ${\displaystyle n}$ элементов того же поля или кольца по формуле ${\displaystyle (1),}$ которая зависит от выбора параметра ${\displaystyle w_{n}}$ – первообразного корня из единицы степени ${\displaystyle n}$ в ${\displaystyle R}$

${\displaystyle {\text{ДПФ}}_{R,n,w_{n}}:y_{i}=\sum _{j=0}^{n-1}{w_{n}}^{ij}x_{j},\quad i=0,1,\dots ,n-1}$ (1).

Определение первообразного корня ${\displaystyle w_{n}}$ из ${\displaystyle 1}$ степени ${\displaystyle n}$ для теоретико-числового ${\displaystyle {\text{ДПФ}}_{R,n,w_{n}}}$ над полем или кольцом с единицей ${\displaystyle R}$ подобрано так, чтобы обобщался вывод формул для обратного дискретного преобразования Фурье над полем комплексных чисел. А именно, налагаемое в случае поля комплексных чисел условие:

для любого ${\displaystyle k=1,2,\ldots ,n-1}$ число ${\displaystyle (1-w^{k})}$ не равно ${\displaystyle 0,}$

в общем случае заменяется на условие:

для любого ${\displaystyle k=1,2,\ldots ,n-1}$ число ${\displaystyle (1-w^{k})}$ не является делителем нуля в ${\displaystyle R,\quad (2)}$

и добавляется условие:

сумма ${\displaystyle n}$ единиц в ${\displaystyle R}$ обратима.${\displaystyle \quad (3)}$

Явная формула преобразования, обратного к теоретико-числовому дискретному преобразованию Фурье, выводится следующим образом. Если ${\displaystyle R}$ – коммутативное ассоциативное кольцо с единицей, ${\displaystyle w}$ – первообразный корень из ${\displaystyle 1}$ степени ${\displaystyle n,}$ т. е. выполнены условия ${\displaystyle (2)}$ и ${\displaystyle (3),}$ то прямым вычислением, аналогичным вычислению для случая комплексных чисел, можно проверить, что произведение матриц преобразований ${\displaystyle {\text{ДПФ}}_{R,n,w}}$ и ${\displaystyle {\text{ДПФ}}_{R,n,{\bar {w}}},}$ где ${\displaystyle {\bar {w}}=w^{n-1}}$ – элемент ${\displaystyle R,}$ обратный ${\displaystyle w,}$ является диагональной матрицей, в которой каждый диагональный элемент равен сумме ${\displaystyle n}$ единиц кольца ${\displaystyle R}$. Поэтому обратное преобразование принимает вид ${\displaystyle {\hat {n}}\,{\text{ДПФ}}_{R,n,{\bar {w}}},}$ где ${\displaystyle {\hat {n}}}$ – элемент, обратный сумме ${\displaystyle n}$ единиц в ${\displaystyle R,}$ существующий в силу ${\displaystyle (3)}$.

Для данного кольца с единицей или поля ${\displaystyle R}$ первообразный корень из ${\displaystyle 1}$ степени ${\displaystyle n}$ существует не для всякого ${\displaystyle n}$.

Примеры:

а) Легко проверить, что для поля вычетов по модулю ${\displaystyle 5,}$ вычет ${\displaystyle 2}$ является первообразным корнем из ${\displaystyle 1}$ степени ${\displaystyle 4,}$ но не существует кубического первообразного корня из ${\displaystyle 1}$.

б) В факторкольце ${\displaystyle R=\mathbb {Z} /8\mathbb {Z} }$ вычетов по модулю ${\displaystyle 8}$ вычет ${\displaystyle 3}$ является корнем квадратным из ${\displaystyle 1,}$ но не является первообразным корнем степени ${\displaystyle 2}$ по следующим причинам:

• нарушено условие ${\displaystyle (2),}$ ибо ${\displaystyle 1-3}$ является делителем нуля в ${\displaystyle R}$;
• нарушено условие ${\displaystyle (3),}$ ибо сумма ${\displaystyle 1+1}$ не обратима в ${\displaystyle R}$.

Далее, для квадратного корня из ${\displaystyle 1}$ ${\displaystyle w=3}$ в кольце ${\displaystyle R}$ сумма степеней этого корня ${\displaystyle 1+w}$ равна вычету ${\displaystyle 4,}$ отличному от нуля в ${\displaystyle R}$. Поскольку эта сумма равна недиагональному элементу произведения матриц преобразований ${\displaystyle {\text{ДПФ}}_{R,2,w}}$ и ${\displaystyle {\text{ДПФ}}_{R,2,{\bar {w}}},}$ где ${\displaystyle {\bar {w}}=w,}$ это произведение оказывается недиагональной матрицей.

в) Для поля вычетов по простому модулю ${\displaystyle p=998244353=7\cdot 17\cdot 2^{23}+1}$ вычет ${\displaystyle 31}$ является первообразным корнем из ${\displaystyle 1}$ степени ${\displaystyle 2^{23}}$.