\documentclass[12pt]{article} \usepackage{amssymb,amsmath,latexsym} \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \makeatletter %% this should really go into a style file! \renewcommand\section{\@startsection {section}{1}{\z@}% % {-3.5ex \@plus -1ex \@minus -.2ex}% % here is your vskip of 30pt: {-30pt \@plus -1ex \@minus -.2ex}% {2.3ex \@plus.2ex}% {\normalfont\normalsize\bfseries}} \renewcommand\subsection{\@startsection{subsection}{2}{\z@}% {-3.25ex\@plus -1ex \@minus -.2ex}% {1.5ex \@plus .2ex}% {\normalfont\normalsize\bfseries}} % add a point after section numbers: \renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad} \makeatother \begin{document} \vspace*{-50pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A18} \vskip 22pt \thispagestyle{empty} \begin{center} \uppercase{\bf A remark on the Chebotarev theorem \\about roots of unity} \vskip 20pt {\bf F. Pakovich\footnote{Research supported by the ISF, Grant No. 979/05}}\\ {\smallit Department of Mathematics, Ben Gurion University, P.O.B. 653, Beer-Sheva 84105, Israel}\\ {\tt pakovich@math.bgu.ac.il}\\ \end{center} \vskip 20pt \centerline{\smallit Received: 2/21/07, Accepted: 4/8/07, Published: 4/12/07} \vskip 20pt \centerline{\bf Abstract} \noindent Let $\Omega$ be a matrix with entries $a_{i,j}=\omega^{ij},$ $1\leq i,j \leq n,$ where $\omega=e^{2\pi \sqrt{-1}/n},$ $n\in \mathbb N.$ The Chebotarev theorem states that if $n$ is a prime then any minor of $\Omega$ is non-zero. In this note we provide an analogue of this statement for composite $n.$ \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A18\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt % \def\d{{\rm d}} \def\D{{\rm D}} \def\I{{\rm I}} \def\C{{\mathbb C}} \def\N{{\mathbb N}} \def\P{{\mathbb P}} \def\Z{{\mathbb Z}} \def\d{{\rm d\,}} \def\deg{{\rm deg\,}} \def\Det{{\rm Det}}\def\dim{{\rm dim\,}} \def\Ker{{\rm Ker\,}} \def\Gal{{\rm Gal\,}} \def\St{{\rm St\,}} \def\Sym{{\rm Sym\,}} \def\Mon{{\rm Mon\,}} Let $\Omega$ be a matrix with entries $a_{i,j}=\omega^{ij},$ $1\leq i,j \leq n,$ where $\omega=e^{2\pi \sqrt{-1}/n},$ $n\in \mathbb N.$ The Chebotarev theorem states that if $n$ is a prime then any minor of $\Omega$ is non-zero. Chebotarev's proof of this theorem and the references to other proofs can be found in \cite{l}. Yet other proofs can be found in recent papers \cite{g} and \cite{t}. For a complex polynomial $P(z)$ denote by $w(P)$ the number of non-zero coefficients of $P(z).$ It is easy to see that the Chebotarev theorem is equivalent to the following statement: if a non-zero polynomial $P(z),$ $\deg P(z) \leq n-1,$ has $k$ different roots which are $n$-roots of unity then $w(P)> k$ whenever $n$ is a prime. A natural question is: How small can $w(P)$ be if $n$ is a composite number ? The example %of the polynomial $D_{n,r,l}(z)=z^l(1+z^r+z^{2r}+ \cdots + z^{(\frac{n}{r}-1)r}),$ where $r\vert n$, $0\leq l \leq r-1,$ shows that $w(P)$ could be as small as $n/(n-k).$ In this note we show that actually it is the ``worst'' possible case. \noindent{\bf Theorem.} {\it Let $n$ be a composite number and $P(z)$ be a non-zero complex polynomial, $\deg P(z) \leq n-1.$ Suppose that $P(z)$ has exactly $k$ different roots which are $n$-roots of unity. Then the inequality $$ w(P)\geq \frac{n}{n-k}\eqno(*)$$ holds. Furthermore, the equality attains if and only if $P(z)$ up to a multiplication by a complex number coincides with $D_{n,r,l}(\omega^j z)$ %$$P(z)=\alpha z^l(1+(\nu^j)z^r+ (\nu^j)^{2}z^{2r}+ ... + (\nu^j)^{(\frac{n}{r}-1)}z^{(\frac{n}{r}-1)r}),$$ for some $j,$ $0\leq j \leq n-1,$ and $r,l$ as above. } \noindent{\it Proof.} Let $P(z)=p_{0}+p_{1}z+...+p_{n-1}z^{n-1}$ and let $\displaystyle C=\begin{pmatrix}p_0 & p_1 & ... & p_{n-1}\\ p_{n-1} & p_0 & ...& p_{n-2}\\ ... & ... & ... & ...\\ p_1& p_2 & ... & p_0\end{pmatrix}$ be the circulant matrix generated by the coefficients of $P(z).$ We will denote the row vectors of $C$ by $\vec{t_j},$ $0\leq j \leq n-1$. Set $r={\rm rk}\, C.$ The key observation is that the number $k$ is equal to the number $n-r$. To establish it notice that eigenvectors of $C$ are $$\vec{f_i}=((\omega^i)^0,(\omega^i)^1,...,(\omega^i)^{(n-1)}),\ \ \ \ \ 0\leq i \leq n-1,$$ and the corresponding eigenvalues are $P(\omega^{i}),$ $0\leq i \leq n-1.$ Furthermore, the vectors $\vec{f_i},$ $0\leq i \leq n-1,$ form a basis of $\mathbb C^n$. The matrix $C$ is diagonal with respect to this basis and therefore $k=n-r$. It follows that in order to prove inequality (*) it is enough to establish the inequality $$w(P)\hskip 0.05cm r\geq n. \eqno(**)$$ This inequality essentially is a particular case of Theorem B in \cite{g} and can be established easily as follows (\cite{g}). Let $V$ be a vector space generated by the vectors $\vec{t}_j,$ $0\leq j \leq n-1$, and $R \subseteq \{\vec{t}_0, \vec{t}_1, ... , \vec{t}_{n-1}\}$ consisting of $r$ vectors which generate $V.$ Clearly, for any $i,$ $1\leq i \leq n,$ there exists a vector $\vec{v}\in V$ for which its $i$-th coordinate is distinct from zero. Since each vector from $R$ has exactly $w(P)$ non zero coordinates it follows that (**) holds. For a vector $\vec{v}\in \mathbb C^n$ denote by ${\rm supp}\{\vec{v}\}$ the set consisting of numbers $i,$ $1\leq i \leq n,$ for which the $i^{\mathrm{th}}$ coordinate of $\vec{v}$ is non-zero. Observe now that the equality in (**) is attained only if for any two vectors $\vec{v}_1,\vec{v}_2\in R$ we have ${\rm supp}\{\vec{v}_1\}\,\cap\,{\rm supp}\{\vec{v}_2\}=\emptyset$. This implies easily that ${\rm supp}\{\vec{t}_0\}$ consists of numbers all congruent modulo $r$ to the same number $l,$ $0\leq l \leq r-1.$ Therefore, $P(z)=z^lQ(z^r)$ for some polynomial $Q(z)=q_{0}+q_{1}z+...+q_{(n/r)-1}z^{(n/r)-1}$ and number $l,$ $0\leq l \leq r-1.$ Furthermore, since the vectors $\vec{t}_0,\vec{t}_r,\vec{t}_{2r}, ... , \vec{t}_{(n/r)-1}$ have equal supports the equality in (**) implies that any two of them are proportional. Therefore, the rank of the circulant matrix $W$ generated by the coefficients of $Q(z)$ equals 1. This implies that the vector $\vec{q}=\{q_{0},q_{1},...,q_{(n/r)-1}\}$ is orthogonal to $(n/r)-1$ vectors from the collection $$\vec{g_j}=((\nu^j)^0,(\nu^j)^1,...,(\nu^j)^{(n/r)-1}),\ \ \ \ 0\leq j \leq (n/r)-1,$$ where $\nu=\omega^r.$ Since $\vec{g}_j,$ $0\leq j \leq (n/r)-1,$ are linearly independent this implies that there exists $\alpha\in \mathbb C$ such that $\vec{q}=\alpha \vec{g}_j$ for some $0\leq j \leq (n/r)-1.$ \hfill $\Box$ \bibliographystyle{amsplain} \begin{thebibliography}{10} \footnotesize %\parskip=0pt \vspace*{-10pt} \bibitem {g} D. Goldstein, R. Guralnick, I. Isaacs, \textit{ Inequalities for finite group permutation modules}, Trans. Am. Math. Soc. 357, No.10, 4017-4042 (2005) \bibitem {l} P. Stevenhagen, H. Lenstra, \textit{ Chebotarev and his density theorem,} Math. Intell. 18, No.2, 26-37 (1996) \bibitem {t} T. Tao, \textit{ An uncertainty principle for cyclic groups of prime order}, Math. Res. Lett. 12, No.1, 121-127 (2005). \end{thebibliography} \end{document}