\documentclass[12pt]{article} %\documentclass{article} %\usepackage{russian} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{textcomp} %\documentstyle[12pt]{article} %\input amssym.def \setcounter{secnumdepth}{0} \font\aaa=cmsy10 at 10pt \renewcommand{\S}{{\aaa\char120\ }} \renewcommand{\phi}{\varphi} \newcommand{\be}{\begin{equation}} \newcommand{\ee}{\end{equation}} \newcommand{\ba}{\begin{eqnarray}} \newcommand{\ea}{\end{eqnarray}} \newcommand{\ban}{\begin{eqnarray*}} \newcommand{\ean}{\end{eqnarray*}} \newcommand{\too}{\mathop{\longrightarrow}} \newcommand{\nul}{{\bf0}} \newcommand{\cupm}{\mathop{\cup}} \newcommand{\capm}{\mathop{\cap}} \renewcommand{\t}{{\Bbb T}} \newcommand{\td}{{\Bbb T}^d} \newcommand{\rd}{{\Bbb R}^d} \newcommand{\zdd}{{\Bbb Z}^{d-1}} \newcommand{\zddp}{{\Bbb Z}^{d-1}_+} \newcommand{\rdd}{{\Bbb R}^{d-1}} \newcommand{\zd}{{\Bbb Z}^{d}} \newcommand{\tdd}{{\Bbb T}^{d-1}} \newcommand{\ld}{L(\td)} \renewcommand{\r}{{\Bbb R}} \newcommand{\z} {{\Bbb Z}} \newcommand{\n} {{\Bbb N}} \newcommand{\calt}{{\cal T}} \newcommand{\call}{{\cal L}} \newcommand{\cons}{{C\,}} \newcommand{\ddd}{,\dots,} \renewcommand{\lll}{\left(} \newcommand{\rrr}{\right)} \newcommand{\ex}[1]{e^{2\pi i{#1}}} \newcommand{\exm}[1]{e^{-2\pi i{#1}}} \newcommand{\sml}[3]{\sum\limits_{{#1}={#2}}^{#3}} \newtheorem{theo}{Theorem} \newtheorem{lem}[theo]{Lemma} \newtheorem {prop} [theo] {Proposition} \newtheorem {coro} [theo] {Corollary} \newtheorem {defi} [theo] {Definition} \begin {document} \centerline{\Large\bf{Decompositions of Trigonometric Polynomials} } \centerline{\Large\bf {Related to Multivariate Subdivision Schemes}} \bigskip \centerline{Nira Dyn and M. Skopina \footnote {The paper is supported by RFBR, project N 06-01-00457}} \bigskip \subsection{1.Introduction} In this paper we study decompositions of multivariate trigonometric polynomials, satisfying a set of constraints known as Strung-Fix conditions of order $m$, multiplied by a factor of the form $1-exp(q(x))$, with $q(x)$ a multilinear polynomial with integer coefficients. The decomposition is a representation of such a polynomial as a sum of trigonometric polynomials, satisfying the Strung-Fix conditions of order $m-1$, multiplied by factors of the above form. This type of decompositions is of interest in the analysis of convergence and smoothness of multivariate subdivision schemes. The algebraic approach to the analysis of such schemes is investigated in~\cite{0} relative to the expansion matrix $2I$, and in~\cite{12}, \cite{11}, relative to general expansion matrices. The analogous decompositions for multivariate algebraic polynomials are based on the rich structure of ideals of multivariate polynomials. The trigonometric decompositions are based on the rather simple idea of the representation of a trigonometric polynomial in terms of its unique polyphase trigonometric polynomials relative to an expansion matrix\cite{2}. The outline of the papers is as follows: in Section 2 we introduce our notation, and bring basic results related to polyphase representations of trigonometric polynomials. In Section 3 properties of trigonometric polynomials satisfying the Strang-Fix conditions of order $m=0$ relative to a general expansion matrix are derived, in terms of its polyphase trigonometric polynomials. These results are used in Section 4 to prove the decomposition for the case $m=0$. An algorithm for the computation of the decomposition for $m=0$ is presented, and the decomposition is used to derive that for the case $m=1$. An example of this case is also presented, with all the computational details. The general case $m>1$, which is much more complicated is investigated in Section 5, and an algorithm for this case is given. In the last section it is proved that trigonometric polynomials satisfying the Strang-Fix conditions of order $m$ are determined by the value at the origin of the derivatives of their polyphase trigonometric polynomials. This result provides a tool for the construction of such polynomials. The application to the smoothness analysis of multivariate subdivision schemes will be done elsewhere. \subsection {2. Notation and preliminary information} Let $ \n $ be the set of positive integers, $ \rd $ denotes the $d $-dimensional Euclidean space, $x = (x_1\ddd x_d) $, $y = (y_1\ddd y_d) $ are its elements (vectors), $ (x, y) = x_1y_1 +\dots+x_dy_d $, $ |x | =\sqrt {(x, x)} $, ${\bf e}_j=(0\ddd1\ddd0)$ is the $j$-th unit vector in $\rd$, \ $ \nul = (0\ddd0) \in \rd $; $ \zd $ is the integer lattice in $ \rd $. For $x,y\in\rd$, we write $x>y$ if $x_j>y_j$, $j=1\ddd d$; $ \zd_+ = \{x\in Z^d:\ x\ge\nul \} $. If $\alpha, \beta\in\zd_+$, $a,b\in\rd$, we set $\alpha!=\prod\limits_{j=1}^d\alpha_j!$, $\lll\alpha\atop\beta\rrr= \frac{\alpha!}{\beta!(\alpha-\beta)!}$, $a^b=\prod\limits_{j=1}^d{a_j}^{b_j}$, $[\alpha]=\sml j1d \alpha_j$, $D^\alpha f=\frac{\partial^{[\alpha]}f} {\partial^{\alpha_1}x_1\dots\partial^{\alpha_d}x_d}$; $\delta_{ab}$ denotes Kronecker delta; $z:=(z_1\ddd z_d)$, where $z_k:=\ex{x_k}$. Let $ M $ be a non-degenerate $ d \times d $ integer matrix whose eigenvalues are bigger than 1 in module, $M^* $ is the conjugate matrix to $M $, $I_d$ denotes the unit $ d \times d$ matrix. We say that numbers $k, n\in \zd $ are congruent modulo~ $M $ (write $k\equiv ~ n ~ \pmod {M} $) if $k-n=M\ell $, $ \ell\in\zd $. The integer lattice $ \zd $ is splitted into cosets with respect to the introduced relation of congruence. The number of cosets is equal to $ | \det M | $ (see, e.g., \cite [p. 107] {73}). Let us take an arbitrary representative from each coset, call them digits and denote the set of digits by $D (M) $. Throughout the paper we consider that such a matrix $M$ is fixed, $m=|\det M|$, $D (M) =\{s_0\ddd s_{m-1}\}$, $D (M^*) =\{s^*_0\ddd s^*_{m-1}\}$, $s_0=s^*_0=\nul$, $r_k=M^{-1}s_k$, $k=0\ddd m-1$. %$R (M) =\{r_0\ddd r_{m-1}\}$. % $r^*_k=M^{-1}s^*_k$,$R^* (M) =\{r^*_0\ddd r^*_{m-1}\}$. \noindent {\bf Proposition A} {\em The matrix $\left\{\frac1{\sqrt m}\,\ex{(r_k, s_l^*)}\right\}_{k,l=0}^{m-1}$ is unitary. In particular,} \be \frac1{\sqrt m}\sum\limits_{k=0}^{m-1}\ex{(r_k, s_l^*)}=\delta_{0l}. \label{a} \ee A proof of this statement can be found, e.g., in~\cite{1}. We will consider $1$-periodic trigonometric polynomials in $d$ variables $$ t(x)=\sum\limits_{n\in\zd}\widehat t(n)\ex{(n,x)}. $$ For any trigonometric polynomial $t$, there exists a unique set of trigonometric polynomials $\tau_{\nu}$, $\nu=0\ddd m-1$, (polyphase functions of $t$) so that \be t(x)=\sml \nu0{m-1}\ex{(s_\nu,x)}\tau_{\nu}(M^*x). \label{1} \ee It is clear that $$ \tau_{\nu}(x)=\sum\limits_{n\in\zd}\widehat t(Mn+s_\nu)\ex{(n,x)}. $$ For any $n\in\z_+$, denote by $SF^n$ the set of trigonometric polynomials $t$ such that $D^\beta t({M^*}^{-1}x)|_{x=s}=0$ for all $s\in D(M^*)$, $s\ne\nul$, and for all $\beta\in\zd_+$, $[\beta]\le n$. Such a notation is reasonable because the refinable function corresponding to a polynomial $t\in SF^n$ satisfies Strang-Fix condition of order~$n$. It will be convenient for us to define $SF^{-1}$ as the set of all trigonometric polynomials. \subsection {3. Auxiliary results} \begin{prop} A trigonometric polynomial $t$ belongs to $SF^0$ if and only if \be \tau_\nu(\nul)=\frac{t(\nul)}{m},\ \ \ \nu=0\ddd m-1, \label{01} \ee where $\tau_{0}\ddd\tau_{m-1}$ are the polyphase functions of $t$. \label{p1} \end{prop} {\bf Proof.} Let $s\in D(M^*)$, using~(\ref{1}) we have $$ t({M^*}^{-1}s)=\sml \nu 0{m-1}\ex{(r_\nu,s)}\tau_{\nu}(s)= \sml \nu 0{m-1}\ex{(r_\nu,s)}\tau_{\nu}(\nul). $$ So, the relation $t\in SF^0$ can be rewritten as $$ \sml \nu 0{m-1}\ex{(r_\nu,s_l^*)}\tau_{\nu}(\nul)=t(\nul)\delta_{\nul l}, \ \ \ l=0\ddd m-1. $$ Consider these equalities as a linear system with unknowns $\tau_0(\nul)\ddd\tau_{m-1}(\nul)$. Due to Proposition A, the system has a unique solution given by~(\ref{01}). $\Diamond$ \begin{lem} Let $t$ be a trigonometric polynomial, $t(\nul)=0$, then $$ t(x)=\sml k1d t_k(x)(1-\ex{(x,{\bf e}_k)}), $$ where $t_k$, $k=1\ddd d$, are trigonometric polynomials. \label{l1} \end{lem} {\bf Proof.} There exists $N\in\zd$ such that $t(x)\ex{(N,x)}=p(z)$, where $p$ is an algebraic polynomial. It is clear that $P(1\ddd1)=0$. By Taylor formula it follows that $$ p(z)=\sml k1d p_k(z)(1-z_k). $$ where $p_k$, $k=1\ddd d$, are algebraic polynomials. It remains to set $t_k(x):=p_k(z)\exm{(N,x)}. \Diamond$ \begin{lem} Let $t, \tilde t\in SF^0$, $t(\nul)=\tilde t(\nul)$, then $$ t(x)-\tilde t(x)=\sml k1d t_k(x)\lll 1-\ex{(M^*x,{\bf e}_k)}\rrr, $$ where $t_k$, $k=1\ddd d$, are trigonometric polynomials. \label{l2} \end{lem} {\bf Proof.} Using~(\ref{1}) for $t, \tilde t$, we have \be t (x)-\tilde t(x)=\sml \nu 0{m-1}\ex{(s_\nu,x)}(\tau_{\nu}(M^*x)-\tilde \tau_{\nu}(M^*x)). \label{2} \ee Due to Proposition~\ref{p1}, $\tau_{\nu}(\nul)-\tilde \tau_{\nu}(\nul)=0$, $\nu=1\ddd m-1$. Hence, by Lemma~\ref{l1}, \be \tau_{\nu}(y)-\tilde \tau_{\nu}(y)=\sml l1d \tau_{\nu k}(y)\lll 1-\ex{(y,{\bf e}_k)}\rrr, \label{3} \ee where $\tau_{\nu k}$, $k=1\ddd d$, are trigonometric polynomials. It remains to set $y=M^*x$ and combine~(\ref{3}) with~(\ref{2}). $\Diamond$ \begin{lem} Let $t\in SF^0$, $r\in\zd$, $\tilde t:=\ex{(r,\cdot)}t$, then $\tilde t\in SF^0$. \label{l3} \end{lem} {\bf Proof.} By~(\ref{1}), $$ \tilde t(x)=\ex{(r,x)}\sml \nu0{m-1}\ex{(s_\nu,x)}\tau_{\nu}(M^*x)= \sml \nu0{m-1}\ex{(s_\nu+r,x)}\tau_{\nu}(M^*x). $$ It is clear that $s_\nu+r=s_{l_\nu}+Mn_\nu$, $n_\nu\in\zd$, $\{l_0\ddd l_{m-1}\}=\{0\ddd m-1\}$. So, $$ \tilde \tau_{l_\nu}(x)=\sml \nu0{m-1}\ex{(s_{l_\nu},x)}\ex{(n_\nu,M^*x)}\tau_{\nu}(M^*x), $$ and the trigonometric polynomial $\tilde \tau_{l_\nu}(x):=\ex{(n_\nu,x)}\tau_\nu(x)$ is the $l_\nu$-th polyphase function of $\tilde t$. If $s\in D(M^*)$, $s\ne\nul$, due to Proposition~\ref{p1}, $$ \tilde \tau_{l_\nu}(s)=\ex{(n_\nu,s)}\tau_\nu(s)=\tau_\nu(s)=\tau_\nu(\nul)= \frac{t(\nul)}{m}=\frac{\tilde t(\nul)}{m}. $$ Again by Proposition~\ref{p1}, it follow that $\tilde t\in SF^0$. $\Diamond$ \begin{lem} Let $n\in\zd$, $ 1-\ex{(M^{-1}n,{\bf e}_j)}=0$ for each $j=1\ddd d$. Then $n\equiv\nul\pmod M$. \label{l4} \end{lem} {\bf Proof.} Since $\ex n=1$ if and only if $n\in\z$, we have $(M^{-1}n)_j=(M^{-1}n,{\bf e}_j)\in\z$ for each $j=1\ddd d$. Hence, $M^{-1}n=l\in\zd$, i.e. $n=Ml$.~$\Diamond$ \subsection {4. Decomposition of masks} \begin{prop} Let $t\in SF^0$, $k=1\ddd d$, then \be (1-\ex{(x,{\bf e}_k)})t(x)=\sml j1d t_{jk}(x)(1-\ex{(M^*x,{\bf e}_j)}), \label{001} \ee where $t_{jk}$, $j=1\ddd d$, are trigonometric polynomials. Inversely, if~(\ref{001}) holds for a trigonometric polynomial $t$, then $t\in SF^0$. \label{p2} \end{prop} {\bf Proof.} If $t\in SF^0$, then~(\ref{001}) follows immediately form Lemmas~\ref{l2} and~\ref{l3}. Now let $t$ be an arbitrary trigonometric polynomial such that~(\ref{001}) holds, $s\in D(M^*)$, $s\ne\nul$. It follows from~(\ref{001}) that $$ t({M^*}^{-1}s)\lll 1-\ex{({M^*}^{-1}s,{\bf e}_k))}\rrr= \\ \sml j1d t_{jk}({M^*}^{-1}s)(1-\ex{(s,{\bf e}_j)})=0. $$ Taking into account Lemma~\ref{l4}, we obtain $t({M^*}^{-1}s)$, which was to be proved.~$\Diamond$ Analyzing the proofs of Lemmas~\ref{l2} and \ref{l3} it is not difficult to describe an algorithm for finding polynomials $t_{jk}$, $j,k=1\ddd d$, in decomposition~(\ref{001}). We will consider that the polyphase functions $\tau_\nu$ of $t$ are given, and the algorithm derives the polyphase functions $\tau_{jk\nu}$ of each polynomial $t_{jk}$. \vspace{.5cm} \noindent {\bf ALGORITHM 1} {\bf Input:} \ \ \ \ \ $\{\widehat\tau_\nu(l), \ l\in\zd, \ \nu=0\ddd m-1\}$. {\bf Output:} \ \ $\{\widehat\tau_{jk\nu}(l), \ l\in\zd,\ \nu=0\ddd m-1, \ j,k=1\ddd d\}$. {\bf Step 0.} \ \ For each $\nu=0\ddd m-1$ find the sets $$\Omega_\nu:=\{l\in\zd:\ \widehat\tau_\nu(l)\ne0\}.$$ {\bf For each }$k=1\ddd d$ {\bf do} \hspace{.1cm} {\bf For each} $\nu=0\ddd m-1$ {\bf do} \begin{quote} {\bf Step 1.} Compute $M^{-1}({\bf e}_k-s_\nu+s_n)=:l_n$ for all $n=0\ddd m-1$ and denote by $n^*$ the unique $n$ such that $l_n\in\zd$. \end{quote} \begin{quote} {\bf Step 2.} Find the set $\tilde\Omega_{k\nu}:=\{l=r+l_{n^*}, r\in \Omega_{n^*}\}$, and for each $l\in \tilde\Omega_{k\nu}$ put $\widehat{\tilde\tau}_\nu(l):={\widehat\tau}_{n^*}(l-l_{n^*})$, $$ p_{k\nu}(z):=\sum\limits_{l\in\Omega_\nu\cup{\tilde\Omega}_{k\nu}} ({\widehat\tau}_\nu(l)-\widehat{\tilde\tau}_\nu(l))z^l. $$ \end{quote} \begin{quote} {\bf Step 3.} Put \ban &&\tau_{1k\nu}(x)=\frac1{1-z_1}\lll p_{k\nu}(z)-p_{k\nu}(1,z_2\ddd z_d) \rrr, \\ &&\tau_{2k\nu}(x)=\frac1{1-z_2}\lll p_{k\nu}(1,z_2,z_3\ddd z_d) -p_{k\nu}(1,1,z_3\ddd z_d)\rrr, \\ &&\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \ldots\ldots \\ &&\tau_{dk\nu}(x)=\frac1{1-z_d}\lll p_{k\nu}(1,1\ddd 1,z_d) -p_{k\nu}(1,1\ddd 1,1)\rrr.\Diamond \ean \end{quote} \begin{theo} If $t\in SF^1$, then in any decomposition~(\ref{001}) the trigonometric polynomials $t_{jk}$, $j,k=1\ddd d$, belong to $SF^0$. \label{t1i} \end{theo} {\bf Proof.} %First we note that decomposition~(\ref{001}) exists because $SF^{(1)}\subset SF^{(0)}$. Let $l=1\ddd d$, $s\in D(M^*)$, $s\ne\nul$. Since $t\in SF^{(1)}$, \be \frac{\partial}{\partial x_l}\lll \lll 1-\ex{({M^*}^{-1}x,{\bf e}_k))}\rrr t({M^*}^{-1}x)\rrr\Bigg|_{x=s}=0, \ \ \ k=1\ddd d. \label{28} \ee On the other hand, it follows from~(\ref{001}) that for each $k=1\ddd d$ we have \ban \frac{\partial}{\partial x_l}\lll\lll 1-\ex{({M^*}^{-1}x,{\bf e}_k))}\rrr t({M^*}^{-1}x)\rrr\Bigg|_{x=s}= \hspace{3cm} \\ \frac{\partial}{\partial x_l}\lll\sml j1d t_{jk}({M^*}^{-1}x)(1-\ex{x_j})\rrr\Bigg|_{x=s}= \\ \sml j1d t_{jk}({M^*}^{-1}s)\frac{\partial}{\partial x_l}(1-\ex{x_j})\Bigg|_{x=s}= -2\pi i\,t_{lk}({M^*}^{-1}s). \ean So, we proved that $t_{lk}({M^*}^{-1}s)=0$ for all $s\in D(M^*)$, $s\ne\nul$, which means $t_{lk}\in SF^{(0)}$.~$\Diamond$ {\bf Example.\ \ \ } Let $ M=\left(\begin{array}{rr} 0 & 2 \\ 2 & -1 \end{array} \right), $ %the set $D(M)$ consists of $$ s_0=\left(\begin{array}{r} 0 \\ 0\end{array} \right), s_1=\left(\begin{array}{r} 1 \\ 0\end{array} \right), s_2=\left(\begin{array}{r} 0 \\ 1\end{array} \right), s_3=\left(\begin{array}{r} 1\\ 1 \end{array} \right). $$ Define the polyphase functions of a polynomial $t$ by \ban \tau_0(x)&=&\frac1{16}(4+4z_1+4z_2+4z_1z_2), \\ \tau_1(x)&=&\frac1{16}(5+4z_1+z_1^{-1}+2z_2+3z_2^{-1}+z_1z_2), \\ \tau_2(x)&=&\frac1{16}(4+z_1+2z_1^{-1}+5z_2+z_2^{-1}+3z_1z_2), \\ \tau_3(x)&=&\frac1{16}(5+z_1+4z_1^{-1}+z_2+3z_2^{-1}+z_1z_2+z_1^{-1}z_2). \ean It is not difficult to see that $t\in SF^0$. Using Algorithm 1, we find $$ \begin{array}{ll} \tau_{110}(x)=\frac1{16}(-1+2z_2+z_1z_2+2z_2^2+z_1z_2^2), & \tau_{210}(x)=\frac1{16}(5+3z_2), \\ \\ \tau_{111}(x)=\frac1{16}(z_1^{-1}+3z_2), & \tau_{211}(x)=\frac1{16}(5+3z_2^{-1}), \\ \\ \tau_{112}(x)=\frac1{16}(-1+2z_1^{-1}+z_2+z_2^2-z_1^{-1}z_2), & \tau_{212}(x)=\frac1{16}(5+3z_2+z_2^{-1}), \\ \\ \tau_{113}(x)=\frac1{16}(2z_1^{-1}+2z_2+z_1^{-1}z_2), & \tau_{213}(x)=\frac1{16}(5+2z_2^{-1}), \\ \\ \tau_{120}(x)=\frac1{16}(1+z_1+4z_2+z_2^{-1}+3z_1z_2), & \tau_{220}(x)=\frac1{16}z_2^{-1}, \\ \\ \tau_{121}(x)=\frac1{16}(2+z_1+z_1^{-1}+z_2+3z_2^{-1}+z_1z_2), & \tau_{221}(x)=0, \\ \\ \tau_{122}(x)=\frac1{16}(3+z_2+2z_1^{-1}), & \tau_{222}(x)=\frac1{16}z_2^{-1}, \\ \\ \tau_{123}(x)=\frac1{16}(3+3z_1^{-1}+z_1^{-1}z_2), & \tau_{223}(x)=0. \end{array} $$ Due to Theorem 2 of \cite{10}, to prove that the subdivision scheme $S_t$ is convergent, it sufficient to check that the norm the matrix subdivision operator $S_T$ from $\ell_\infty^2$ to $\ell_\infty^2$ is strictly less than 1, and that $M$ has a self-similar tile, i.e. there exists a set $E\subset\r^2$ such that $ME=\cupm\limits_{s\in D(M)}(E+s)$, $\cupm\limits_{l\in\z^2}(E+l)=\r^2$, $\mbox{mes} E=1$. The first requirement is fulfilled because $$ \|S_T\|_{\ell_\infty^2\to\ell_\infty^2}\le\max\limits_{(\nu,k)} (\|\tau_{1k\nu}\|_{\ell_1}+\|\tau_{2k\nu}\|_{\ell_1})\le\frac{15}{16} $$ (here we identify a trigonometric polynomial with its sequence of Fourier coefficients). Set $$ E=\left\{x\in\r^2:\ \ x=\sml k1\infty M^{-k}x_k,\ x_k\in D(M)\right\}. $$ To show that $E$ provides a self-similar tile it suffices to check (see, e.g., \cite{73}) that the function $$ m_0(x)=\frac14(1+\ex{x_1}+\ex{x_2}+\ex{(x_1+x_2)}) $$ is such that $m_0({M^*}^{-k}x)$ does not vanish on $\left[-1/2,1/2\right]^2$ for all $k\in\n$. Since $$ |m_0({M^*}^{-1}x)|^2=\lll1+\cos2\pi\lll\frac{x_1}4+\frac{x_2}2\rrr\rrr \lll1+\cos2\pi\frac{x_1}2\rrr, $$ we see that all zeros of this function are on the lines $\frac{x_1}4+\frac{x_2}2=\pm\frac12+l$, $\frac{x_1}2=\pm\frac12+l$, $l\in\z$, and it is clear that the cube $\left[-1/2,1/2\right]^2$ does not intersect with these lines. It remains to note that $\|{M^*}^{-1}x\|_\infty\le\frac34\|x\|_\infty$, and so ${M^*}^{-1}\left[-1/2,1/2\right]^2\subset\left[-1/2,1/2\right]^2$. Proposition \ref{p2} and Theorem~\ref{t1i} state that for $n=0,1$ condition $t\in SF^n$ implies $t_{jk}\in SF^{n-1}$. This fact can not be extended to the case $n>1$. If $t\in SF^2$, there exist decompositions~(\ref{001}) whose elements are not in $SF^1$. Nevertheless, it will be shown that decomposition of $t\in SF^n$ can be fixed up to provide $t_{jk}\in SF^{n-1}$. \begin{theo} Let $n\in\z_+$. A trigonometric polynomial $t$ belongs to $SF^n$ if and only if there exists a decomposition~(\ref{001}) with $t_{jk}\in SF^{n-1}$, $j,k=1\ddd d$. \label{t1} \end{theo} {\bf Proof.} Set \ban a(x)=t({M^*}^{-1}x), &&a_{jk}(x)=t_{jk}({M^*}^{-1}x), \\ b_k(x)=1-\ex{{(M^*}^{-1}x,{\bf e}_k)}, &&c_k(x)=1-\ex{(x,{\bf e}_k)}. \ean In these notation, (\ref{001}) can be rewritten as \be b_k(x)a(x)=\sml j1d a_{jk}(x)c_j(x). \label{4} \ee Note the following trivial properties of $c_j$: \ba &&c_j(l)=0 \ \forall l\in\zd, \label{5} \\ &&D^\delta c_j\equiv0\ \forall \delta\ne r{\bf e}_j, r\in\n, \delta\ne \nul, \label{6} \\ &&\frac{\partial c_j}{\partial x_j}(l)\ne0\ \forall l\in\zd. \label{7} \ea We will prove the theorem by induction on $n$. We have a base for $n=0$ due to Proposition~\ref{p2}. Let us prove the inductive step: $n\to n+1$. Assume that each polynomial $t_{jk}$ belongs to $SF^{n}$, i.e. $D^\beta a_{jk}(s^*_l)=0$, $l=1\ddd m-1$, for all $\beta\in\zd_+$, $[\beta]\le n$. Let $\alpha\in\zd$, $[\alpha]=n+1$, $s\in D(M^*)$, $s\ne\nul$. It follows from~(\ref4) and Leibniz formula that $$ \sum\limits_{\nul\le\beta\le\alpha} \lll\alpha\atop\beta\rrr D^{\alpha-\beta}b_k(s) D^\beta a(s)=D^\alpha a_{jk}(s)c_j(s). $$ By the inductive hypotheses, $D^\beta a(s)=0$ whenever $\beta<\alpha$. Hence, taking into account~(\ref5), we have $$ b_k(s)D^\alpha a(s)=c_j(s)D^\alpha a_{jk}(s)=0. $$ Due to Lemma~\ref{l4}, $b_k(s)\ne0$ for at least one $k=1\ddd d$. It follows that $D^\alpha a(s)=0$. Now we assume that $t\in SF^{n+1}$, i.e. $D^\alpha a(s^*_\nu)=0$, $\nu=1\ddd m-1$, for all $\alpha\in\zd_+$, $[\alpha]\le n+1$. Due to the inductive hypotheses, there exist polynomials $t_{jk}\in SF^{n-1}$ satisfying~(\ref{001}), i.e. $D^\delta a_{jk}(s^*_\nu)=0$, $\nu=1\ddd m-1$, for all $\delta\in\zd_+$, $[\delta]\le n-1$. We will construct new trigonometric polynomials satisfying~(\ref{001}) and belonging to $SF^{n}$. Note that for $n=0$ any trigonometric polynomials $t_{jk}$ satisfying~(\ref{001}) belong to $SF^{0}$, due to Theorem~\ref{t1i}. Let us prove the following statement. If $D^\delta a_{jk}(s^*_\nu)=0$, $\nu=1\ddd m-1$, for all $\delta\in\zd_+$, $[\delta]\le n$ and for all $j=1\ddd l-1$ ($l=1\ddd d$), then there exist polynomials $\tilde t_{jk}$, $j,k=1\ddd d$, such that $\sml j1d \tilde a_{jk}c_j=\sml j1d a_{jk}c_j$, where $ \tilde a_{jk}(x)= \tilde t_{jk}({M^*}^{-1}x)$, and $D^\delta \tilde a_{jk}(s^*_\nu)=0$, $\nu=1\ddd m-1$, $k=1\ddd d$, for all $\delta\in\zd_+$, $[\delta]\le n$, and for all $j=1\ddd l$. Let $s\in D(M^*), s\ne\nul$, $\beta\in \z_+^d$, $[\beta]=n$, $\sml i{l+1}d\beta_i=0$. Set $\alpha=\beta+{\bf e}_l$ and note that $[\alpha]=n+1$. It follows from~(\ref4) that \be D^\alpha\lll \sml j1d a_{jk}(x)c_j(x)\rrr\Bigg|_{x=s}= D^\alpha(b_k(x)a(x))|_{x=s}=0. \label8 \ee On the other hand, due to~(\ref5), (\ref6) and the assumption of the statement, we have \ban D^\alpha\lll \sml j1d a_{jk}(x)c_j(x)\rrr\Bigg|_{x=s}= \sml j1lD^{\alpha-{\bf e}_j} a_{jk}(s)\frac{\partial c_j}{\partial x_j}(s)= D^{\beta} a_{lk}(s)\frac{\partial c_l}{\partial x_l}(s). \ean Combining this with~(\ref7) and (\ref8), we get $D^\beta a_{lk}(s) =0$. %whenever $[\beta]=n$, $\beta_{l+1}=\dots=\beta_d=0$. Note that the statement is proved already for $l=d$ (in this case $\tilde t_{jk}=t_{jk}$, $j,k=1\ddd d$). Next let $j=l+1\ddd d$, $\beta\in \z_+^d$, $[\beta]=n$, $\sml i{l+1}d\beta_i>0$. Define the functions $$ q_{\beta j}(x)=\frac1{-2\pi i}g_{n-1, \beta-{\bf e}_j}(x)\sml\nu1{m-1}h_\nu(x)D^\beta a_{lk}(s^*_\nu), $$ where $g_{N \delta}$ is a trigonometric polynomial such that $D^\gamma g_{N \delta}(\nul)=0$ for all $\gamma\in \z_+^d$, $[\gamma]\le N$, $\gamma\ne\delta$ and $D^\delta g_{N \delta}(\nul)=1$; $$ h_\nu(x)=\frac1m\sml\mu0{m-1}\ex{(x-s_\nu^*, {M}^{-1}s_\mu)}. $$ Since, by Proposition A, $h_\nu(s^*_\mu)=\delta_{\mu\nu}$, due to (\ref5), (\ref6) and Leibniz formula, it is not difficult to see that for each $\nu=1\ddd m-1$ we have \ba &&D^\beta(c_j(x)q_{\beta j}(x))\Big|_{x=s_\nu^*}=D^\beta a_{lk}(s^*_\nu); \label{25} \\ &&D^\delta(c_j(x)q_{\beta j}(x))\Big|_{x=s_\nu^*}=0\ \ \ \forall \delta\in \z_+^d,\ [\delta]\le n,\ \delta\ne\beta; \label{26} \\ &&D^\delta(c_i(x)q_{\beta j}(x))\Big|_{x=s_\nu^*}=0\ \ \ \forall \delta\in \z_+^d,\ [\delta]\le n-1, \forall i=1\ddd d. \label{27} \ea Set \ban \tilde a_{lk}(x)&:=&a_{lk}(x)-\sml j{l+1}d \sum\limits_{[\beta]=n, \ \beta_j>0\atop\beta_{l+1}=\dots=\beta_{j-1}=0} c_j(x)q_{\beta j}(x), \\ \tilde a_{jk}(x)&:=&a_{jk}(x)+ \sum\limits_{[\beta]=n, \ \beta_j>0\atop\beta_{l+1}=\dots=\beta_{j-1}=0} c_l(x)q_{\beta j}(x),\ \ \ j=l+1\ddd d. \ean Because of construction, $\sml jld \tilde a_{jk}c_j=\sml jld a_{jk}c_j$, and, taking into account~(\ref{25}), (\ref{26}), for each $\nu=1\ddd m-1$ we have $D^\beta \tilde a_{lk}(s^*_\nu)=0$ whenever $[\beta]=n$, $\sml i{l+1}d\beta_i>0$; $D^\beta \tilde a_{lk}(s^*_\nu)=D^\beta a_{lk}(s^*_\nu)=0$ whenever $[\beta]=n$, $\sml i{l+1}d\beta_i=0$. At last, due to~(\ref{27}), $D^\delta \tilde a_{jk}(s^*_\nu)=0$, $j=l\ddd d$ for all $\delta\in\zd_+$, $[\delta]\le n-1$. To complete the proof of the statement it remains to put $\tilde t_{jk}=\tilde a_{jk}(M^*x)$ for $j=l\ddd d$ and $\tilde t_{jk}=t_{jk}$ for $j=1\ddd l-1$. So, we described one step for improvement of decomposition~(\ref{001}). Starting with $l=1$, after $(d-1)$ steps we will obtain required polynomials.~$\Diamond$ Analyzing the proof of Theorem~\ref{t1} it is not difficult to describe an algorithm for finding polynomials $t_{jk}\in SF^{n-1}$, $j,k=1\ddd d$, in decomposition~(\ref{001}). To realize this algorithm we will need functions $g_{N\delta}$. Explicit recursive formulas for these functions are presented in~\cite{2}. \vspace{.5cm} \noindent {\bf ALGORITHM 2} {\bf Input:} \ \ \ \ \ $ %\mbox{A trigonometric polynomial}\ t\in SF^{N}$, $N>1$. {\bf Output:} \ \ $ %\mbox{Trigonometric polynomials}\ t_{jk}\in SF^{N-1}, j,k=1\ddd d$. %, satisfying~(\ref{001}). {\bf Step 1.} \ \ Using Algorithm 1, find $t_{jk}$, $j,k=1\ddd d$, satisfying~(\ref{001}). {\bf Step 2.} \ \ For $n=1\ddd N-1$ do \hspace{2.2cm} Set $t_{jk}^{(0)}:=t_{jk}$, $j,k=1\ddd d$; \hspace{2.5cm} For each $l=1\ddd d-1$ do \hspace{2.8cm} For each $k=1\ddd d$ do $ \ \ \ \ \ a_{lk}(x)=t^{(l-1)}_{lk}({M^*}^{-1}x); $ $$ \ \ \ \ t^{(l)}_{lk}(x):=t^{(l-1)}_{lk}(x)-\sml j{l+1}d \lll1-\ex{(M^*x,{\bf e}_j)}\rrr\sum\limits_{[\beta]=n, \ \beta_j>0\atop\beta_{l+1}=\dots=\beta_{j-1}=0} q_{\beta j}(M^*x); $$ \hspace{3.1cm} For each $j=1\ddd l$ do $$ \hspace{-8cm} t^{(l)}_{jk}(x):=t^{(l-1)}_{jk}(x); $$ \hspace{3.1cm} For each $j=l+1\ddd d$ do $$ t^{(l)}_{jk}(x):=t^{(l-1)}_{jk}(x)+ \lll1-\ex{(M^*x,{\bf e}_l)}\rrr\sum\limits_{[\beta]=n, \ \beta_j>0\atop\beta_{l+1}=\dots=\beta_{j-1}=0} q_{\beta j}(M^*x).\Diamond $$ In the case $d=2$, Step 2 of Algorithm 2 does not look so frightening, it is reduced to the following. For $n=1\ddd N-1$ do Set $l=1$, $t_{jk}^{(0)}:=t_{jk}$, $j,k=1,2$; For each $k=1,2$ do \ban a_{1k}(x)&=&t^{(0)}_{1k}({M^*}^{-1}x); \\ t_{1k}(x)&:=&t^{(0)}_{1k}(x)- \lll1-\ex{(M^*x,{\bf e}_2)}\rrr\sum\limits_{[\beta]=n, \ \beta_2>0} q_{\beta j}(M^*x); \\ t_{2k}(x)&:=&t^{(0)}_{2k}(x)+ \lll1-\ex{(M^*x,{\bf e}_1)}\rrr\sum\limits_{[\beta]=n, \ \beta_2>0} q_{\beta j}(M^*x). \ean In particular, for $d=2$, $N=2$, Step 2 may be realized as follows. Set $t_{jk}^{(0)}:=t_{jk}$, $j,k=1,2$; For each $k=1,2$ do \ban t_{1k}(x):=t^{(0)}_{lk}(x)+ \frac1{2\pi i}\lll1-\ex{(M^*x)_2}\rrr \sml\nu1{m-1} h_\nu(M^*x)\frac{\partial}{\partial x_2} t^{(0)}_{1k}({M^*}^{-1}u)\Big|_{u=s^*_\nu}; \\ t_{2k}(x):=t^{(0)}_{2k}(x)-\frac1{2\pi i} \lll1-\ex{(M^*x)_1}\rrr \sml\nu1{m-1} h_\nu(M^*x)\frac{\partial}{\partial x_2} t^{(0)}_{1k}({M^*}^{-1}u)\Big|_{u=s^*_\nu}. \ean For each $n\in\n$ we introduce the set $$ \Gamma^n:=\{k\in\r^n:\ \ k_l=1\ddd d,\ l=1\ddd n\}. $$ \begin{theo} Let $n, n_0\in\n$, $n\le n_0$, $t\in SF^{n_0-1}$, $k\in\Gamma^n$, then there exist trigonometric polynomials $t_{jk}\in SF^{n_0-n-1}$, $j\in \Gamma^n$, such that \ba \prod\limits_{l=1}^n\lll 1-\ex{(x,{\bf e}_{k_l})}\rrr t(x)&=& \sml {j_1}1d \ldots \sml {j_n}1d t_{jk}(x)\prod\limits_{l=1}^n\lll 1-\ex{(M^*x,{\bf e}_{j_l})}\rrr, \label{13} \\ t_{jk}(\nul)&=&\prod\limits_{l=1}^n({M^*}^{-1})_{j_lk_l}\,t(\nul). \label{14} \ea \label{t2} \end{theo} {\bf Proof.} We will proof by induction on $n$. Base: $n=1$. Let $k\in\Gamma^1$. Due to Proposition~\ref{p2} and Theorem~\ref{t1}, there exist trigonometric polynomials $t_{jk}\in SF^{n_0-2}$, $j\in \Gamma^1$, such that~(\ref{001}) holds. Rewrite identity~(\ref{001}) as follows $$ (1-\ex{(x,M^{-1}{\bf e}_k)})t({M^*}^{-1}x)=\sml j1d t_{jk}({M^*}^{-1}x)(1-\ex{(x,{\bf e}_j)}), $$ Differentiating by $x_l$, we have \ban -2\pi i\,(M^{-1}{\bf e}_k,{\bf e}_l)\ex{(x,M^{-1}{\bf e}_k)}) t({M^*}^{-1}x)+ (1-\ex{(x,M^{-1}{\bf e}_k)})\frac{\partial}{\partial x_l}t({M^*}^{-1}x)= \\ \sml j1d \frac{\partial}{\partial x_l}t_{jk}({M^*}^{-1}x)(1-\ex{(x,{\bf e}_j)})- 2\pi i\, t_{jk}({M^*}^{-1}x)\,\ex{(x,{\bf e}_j)}. \ean Substituting $x=\nul$, we obtain $$ -2\pi i\,(M^{-1}{\bf e}_k,{\bf e}_l) t(\nul)= -2\pi i\,t_{jk}(\nul). $$ To prove the base it remains to note that $$ (M^{-1}{\bf e}_k,{\bf e}_l)=({M^*}^{-1}{\bf e}_l,{\bf e}_k)=({M^*}^{-1})_{kl}. $$ Inductive step: $n-1\to n$. Let $1