INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A18

A REMARK ON THE CHEBOTAREV THEOREM ABOUT ROOTS OF UNITY

F. Pakovich^{1}

Department of Mathematics, Ben Gurion University, P.O.B. 653, Beer-Sheva 84105, Israel

                          pakovich@math.bgu.ac.il

Received: 2/21/07, Accepted: 4/8/07, Published: 4/12/07

Abstract

Let Ω be a matrix with entries a_{i,j} = ω^{ij}, 1 ≤ i, j ≤ n, where ω = e^{2π\sqrt{−1}/n}, n ∈ ℕ. The Chebotarev theorem states that if n is a prime then any minor of Ω is non-zero. In this note we provide an analogue of this statement for composite n.

Let Ω be a matrix with entries a_{i,j} = ω^{ij}, 1 ≤ i, j ≤ n, where ω = e^{2π\sqrt{−1}/n}, n ∈ ℕ. The Chebotarev theorem states that if n is a prime then any minor of Ω is non-zero. Chebotarev’s proof of this theorem and the references to other proofs can be found in [2]. Yet other proofs can be found in recent papers [1] and [3].

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) ≤ 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 D_{n,r,l}(z) = z^{l}(1 + z^{r} + z^{2r} + ⋯ + z^{( \frac{n}{r} −1)r}), where r|n, 0 ≤ l ≤ 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.

Theorem. Let n be a composite number and P (z) be a non-zero complex polynomial, deg P (z) ≤ n − 1. Suppose that P (z) has exactly k different roots which are n-roots of unity. Then the inequality

w(P) ≥ \frac{n}{n − k}  (∗)

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}(ω^{j}z) for some j, 0 ≤ j ≤ n − 1, and r, l as above.

Proof. Let P (z) = p_{0} + p_{1}z + ... + p_{n−1}z^{n−1} and let C = (\begin{matrix}p_{0} & p_{1} & ... & p_{n−1} \\ p_{n−1} & p_{0} & ... & p_{n−2} \\ ... & ... & ... & ... \\ p_{1} & p_{2} & ... & p_{0} \end{matrix}) be the

1Research supported by the ISF, Grant No. 979/05

circulant matrix generated by the coefficients of P (z). We will denote the row vectors of C by t⃗_{j}, 0 ≤ j ≤ n − 1. Set r = 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

f⃗_{i} = ((ω^{i})^{0}, (ω^{i})^{1}, ..., (ω^{i})^{(n−1)}), 0 ≤ i ≤ n − 1,

and the corresponding eigenvalues are P (ω^{i}), 0 ≤ i ≤ n − 1. Furthermore, the vectors f⃗_{i}, 0 ≤ i ≤ n − 1, form a basis of ℂ^{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)r ≥ n.  (∗∗)

This inequality essentially is a particular case of Theorem B in [1] and can be established easily as follows ([1]). Let V be a vector space generated by the vectors t⃗_{j}, 0 ≤ j ≤ n−1, and R ⊆ {t⃗_{0}, t⃗_{1}, ..., t⃗_{n−1}} consisting of r vectors which generate V. Clearly, for any i, 1 ≤ i ≤ n, there exists a vector v⃗ ∈ 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 v⃗ ∈ ℂ^{n} denote by supp{v⃗} the set consisting of numbers i, 1 ≤ i ≤ n, for which the i^{th} coordinate of v⃗ is non-zero. Observe now that the equality in (**) is attained only if for any two vectors v⃗_{1}, v⃗_{2} ∈ R we have supp{v⃗_{1}} ∩ supp{v⃗_{2}} = ∅. This implies easily that supp{t⃗_{0}} consists of numbers all congruent modulo r to the same number l, 0 ≤ l ≤ r−1. Therefore, P (z) = z^{l}Q(z^{r}) for some polynomial Q(z) = q_{0} + q_{1}z + ... + q_{(n/r)−1}z^{(n/r)−1} and number l, 0 ≤ l ≤ r − 1.

Furthermore, since the vectors t⃗_{0}, t⃗_{r}, t⃗_{2r}, ..., 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 q⃗ = {q_{0}, q_{1}, ..., q_{(n/r)−1}} is orthogonal to (n/r) − 1 vectors from the collection

g⃗_{j} = ((ν^{j})^{0}, (ν^{j})^{1}, ..., (ν^{j})^{(n/r)−1}), 0 ≤ j ≤ (n/r) − 1,

where ν = ω^{r}. Since g⃗_{j}, 0 ≤ j ≤ (n/r) − 1, are linearly independent this implies that there exists α ∈ ℂ such that q⃗ = αg⃗_{j} for some 0 ≤ j ≤ (n/r) − 1. □

References

[1] D. Goldstein, R. Guralnick, I. Isaacs, Inequalities for finite group permutation modules, Trans. Am. Math. Soc. 357, No.10, 4017-4042 (2005)

[2] P. Stevenhagen, H. Lenstra, Chebotarev and his density theorem, Math. Intell. 18, No.2, 26-37 (1996)

[3] T. Tao, An uncertainty principle for cyclic groups of prime order, Math. Res. Lett. 12, No.1, 121-127