# Products of primitive roots of the unity

Let $m>2$ be an integer and $k=\varphi(m)$ be the number of $m$-th primitive roots of the unity. Let $\Phi = \{ \xi_1, \ldots, \xi_{k/2}\}$ be a set of $k/2$ pairwise distinct primitive $m$-th roots of the unity such that $\Phi \cap \overline{\Phi} = \emptyset$, where $\overline\Phi = \{ \overline \xi_1, \ldots, \overline\xi_{k/2}\}$ is the set of complex conjugate primitive roots.

Question 1. Does there exist an integer $N$, independent of $m$ and $\Phi$, such that $1$ belongs to $\Phi^N$, the set of products of $N$ non-necessarily distinct elements in $\Phi$ ?

The real question behind this concerns automorphisms of complex Abelian varieties and symmetric differentials. Let $A$ be a complex Abelian variety, and $\varphi : A \to A$ be an automorphism of finite order.

Question 2. Does there exist an integer $N$, independent of $A$ and $\varphi$, such that there exists a non-zero holomorphic section $\omega \in Sym^N \Omega^1_A$ satisfying $\varphi^* \omega = \omega$ ?

Update (07/05/2013) : If $m$ is prime then we can take $N=3$ is Question 1 above. Indeed, the product of any two elements in $\Phi$ is still a primitive root of the unity. If we denote the set of all these products by $\Phi^2$ then it must intersect $\overline \Phi$. Otherwise $\Phi^2 \subset\Phi$ and, inductively, we deduce that $\Phi^m\subset\Phi$. Thus $1 \in \Phi$ contradicting the choice of $\Phi$.

In general $N=3$ does not work. If we take $m=6$ then $\varphi(6)=2$ and for $\Phi=\{\xi_6\}$ we need to take $N=6$. If we take $m=12$ then $\varphi(12)=4$ and for $\Phi=\{\xi_{12}, \xi_{12}^7 \}$ we also need to take $N=6$.

Concerning Question 2 for the particular case $A=Jac(C)$ is the jacobian of a curve and $\varphi$ is induced by an automorphism of $C$ then I know that $N = 2^2 \times 3 \times 5$ suffices. Indeed, there always exists $N\le 6$ that works for a given pair $(A=Jac(C),\varphi)$ with $\varphi$ induced by an automorphism of $C$.The argument in this cases consists in looking at the quotient orbifold and orbifold symmetric differentials on it.

-
I think you want $\phi$ to be an automorphism of finite order. – Damian Rössler Jul 4 '13 at 16:09
@Damian Rössler: Thank you. – jvp Jul 4 '13 at 16:26
Just curious: why do you need this kind of result ? Do you want to apply the fixed point formula to $\phi$ ? – Damian Rössler Jul 5 '13 at 20:20
This kind of result gives information on the canonical ring of a certain class of foliations on projective surfaces. If true, it would considerably simplify a work in progress about the possibility effectively integrating certain classes of polynomial differential equations. – jvp Jul 5 '13 at 21:29
It is false in general that the product of two primitive $m$th roots of unity is again a primitive $m$th root of unity. Indeed, if $m$ is even, then such a product is never a primitive $m$th root of unity, as it has order at most $m/2$. – Greg Martin Jul 8 '13 at 3:51

Theorem If $m$ is relatively prime to $30$, then $N=3$ works.

I'll use additive notation. The cyclic group of order $n$ is denoted $C(n)$, the generators of this cyclic group are denoted $U(n)$.

Lemma Let $p \geq 7$ be prime and let $X$, $Y$ and $Z$ be subsets of $C(p)$ of size at least $(p-1)/2$. Then $0 \in X+Y+Z$.

Proof By the Cauchy-Davenport theorem (thanks quid!), we have $|X+Y+Z| \geq \min(3 (p-1)/2 -2,p)$, which equals $p$ once $p \geq 7$. $\square$

We now prove the Theorem by induction on $m$; the case $m=1$ is vacuously true. Let $p$ be a prime dividing $m$ and let $\pi$ be the projection map $C(m) \to C(m/p)$. Let $A \subset U(m)$ so that $U(m)$ is the disjoint union of $A$ and $-A$. We want to show that $0 \in A+A+A$.

For $b \in U(m/p)$, we have $|\pi^{-1}(b) \cap A|+|\pi^{-1}(-b) \cap A| = p-1$ or $p$; the first case occurs when $GCD(p,m/p)=1$ and the second case occurs otherwise. Choose a subset $B$ of $U(m/p)$ so that $U(m/p)$ is the disjoint union of $B$ and $-B$ and, for each $b \in B$, we have $|\pi^{-1}(b) \cap A| \geq (p-1)/2$.

Inductively, we can find $b_1$, $b_2$ and $b_3$ in $B$ (not necessarily distinct) so that $b_1+b_2+b_3=0$. Choose lifts $c_i$ of the $b_i$ to $C(m)$ so that $c_1+c_2+c_3=0$. Let $X_i$ be $(\pi^{-1}(b_i) \cap A) - c_i$ for $i=1$, $2$, $3$. Use the Lemma to find $x_1$, $x_2$, $x_3$ with $x_i \in X_i$ and $x_1+x_2+x_3=0$. Then $c_i+x_i \in \pi^{-1}(b_i) \cap A \subseteq A$ and $\sum (c_i+x_i) = 0$. $\square$

As noted in comments below, $12$ always works. Indeed, if we want to have a single $N$ for all $\Phi$, then $12$ is the best possible because $m=12$, $\Phi = \{1,7 \}$ forces $6|N$ and $m=12$, $\Phi = \{ 1,5 \}$ forces $4 | N$. However, it seems to me that a better statement (which I will now prove) is that, for any $\Phi$, either $N=4$ or $N=6$ works.

Once our inductive claim is that either $4$ or $6$ works, the prime $5$ behaves like any other prime, so we may reduce to numbers of the form $2^a 3^b$. Also, if $9 | m$ and the claim holds for $m/3$, then it holds for $m$, as we get to replace the bound $(p-1)/2$ by $p/2$. So we are reduced to $m$ of the form $2^a$ or $2^a \times 3$.

gcousin has already done $2^a$. For $m=2^a \times 3$, consider the map $\pi: C(2^a \times 3) \to C(2^a)$. If all of the fibers of this map have size $0$ or $2$, then we may reduce to the case of $2^a$ as above, since then we have subsets of $C(3)$ of size $2$ in the lemma.

Suppose, then, that there is some $x \in U(2^a)$ such $\pi^{-1}(x) \cap A$ and $\pi^{-1}(-x) \cap A$ nonzero; let $a$ and $a'$ occupy these sets. Then $a+a'$ is $3$-torsion, so $N=6$ works.

-
Nice argument. In case you are interest in this, I think the proof of the lemma could be shortened by invoking the Theorem of Chauchy-Davenport (twice): for subsets $A,B$ of prime-cyclic group one has $|A+B| \ge \min \{|A|+|B| - 1, p\}$; so in fact $X+Y +Z$ is the full group. – quid Jul 10 '13 at 19:05
I also think that $N=12$ works. Induction as in David Speyer's argument shows that $N=4$ works for $3\nmid m$, and another induction shows that $N=12$ works for $3\mid m$. For this we need the Lemma (or Cauchy-Davenport) for $4$ summands. A very small trick is needed for the case $m=2^a.3$, namely we take $3$ copies of the $4$ summands that work for $m/3=2^a$. – GH from MO Jul 11 '13 at 0:03
@David: Very nice. It is perhaps worth noting that the argument you present for $m=2^a\times 3$ can be adapted for $m=2^a$ as well. – GH from MO Jul 11 '13 at 0:20

Partial Result:

For $m=p^l$, $p\neq 2$ prime, we can prove $1\in\Phi^N$ for $N=3$; independently of the choice of $\Phi$.

For $p=2$, we have the similar result with $N=4$.

We formulate the proofs in the language of $\mathbb Z/m\mathbb Z$. Via exponential, $m$-th roots of unity correspond to the elements of $\mathbb Z/m\mathbb Z$, and primitive $m$-th roots correspond to the invertibles in $\mathbb Z/m\mathbb Z$.

Proof for $p\neq 2$ :

Let $\Phi$ be a part of $(\mathbb Z/m\mathbb Z)^*$ such that $(\mathbb Z/m\mathbb Z)^*=\Phi\sqcup (-\Phi)$.

We may suppose $2\in \Phi$. Consider $E=\{2n\in 2\mathbb N \vert n\wedge p=1\mbox{ and } 0<2n<p^l\}$. We denote $u_+ \in E$ the successor of $u\in E$ for the natural order on $E$.

If $E\subset \Phi$ then $p^l-1=-1\in \Phi$ and $2+(-1)+(-1)=0\mbox{ mod }m$ is a zero sum of three terms in $\Phi$ (admissible sum in the sequel).

If $E\not \subset \Phi$ then there exists $u\in E\cap \Phi$ such that $u_+\notin \Phi$ (We have fixed $2\in \Phi$). We consider $u_0$ the smallest such $u$. If $u^0=2$ then $-4\in \Phi$ and $2+2-4=0$ is an admissible sum. If $u^0\neq 2$, then $4\in \Phi$ and $u^0-u^0_+=-2$ or $-4$ and is a sum of two terms in $\Phi$. Adding $4$ or $2$ to this latter sum we obtain an admissible sum.

Adaptation for $p=2$: we can suppose $1\in \Phi$, set $E$ to be the set of odd numbers in $[0,2^n]$. If $E\not \subset\Phi$ we have $u-u_+=-2$ and $1+1+u-u_+=0\mbox{ mod }m$ has four terms in $\Phi$. If $E\subset\Phi$ then $-1=2^l-1\in \Phi$ and $1\in \Phi$, this is a contradiction.

Actually, JVP firstly transmitted another proof for p=2 : Let $\Phi^N$ denote the set of sums of $N$ terms in $\Phi$. We may suppose $1\in \Phi$.

If $\Phi^3\subset \Phi$ then for any $u\in \Phi$ we have $u+2=u+1+1$ is in $\Phi$, thus every odd is in $\Phi$ and $2^l-1=-1\in \Phi$ which contradicts $1\in \Phi$.

Thus $\Phi^3 \not \subset \Phi$ and there exist $a,b,c\in \Phi$ such that $a+b+c=d\in -\Phi$ (for d is odd and not in $\Phi$). Hence $a+b+c-d=0$ is a sum of four terms in $\Phi$.

If we allow to bound by $k$ the number of distinct prime factors, I can give a bound of $N(m)$ by $2^{k-1}\cdot 3$ if $m$ is odd and $2^{k-1}\cdot 4$ if m is even. I don't know if it is better than the one obtained in the interesting answer of quid.

Proof : By recurrence, combine Lemma $1$ below and the bound for $N(p^l)$.

Lemma 1 :

If $m=uv$ where $u,v$ are coprimes then, if $(\mathbb Z/m \mathbb Z)^*=\Phi_m \sqcup -\Phi_m$, up to interversion of $u$ and $v$, we can find a partition $(\mathbb Z/u \mathbb Z)^*=\Phi_u \sqcup -\Phi_u$ such that the natural injection $\mathbb Z/u\mathbb Z\rightarrow > \mathbb Z/m \mathbb Z$ induces a map $\{2n\vert n\in\Phi_u\}\rightarrow \Phi_m^2$, in particular

$$N(m)\leq 2 Max(N(u),N(v)).$$

Corrected Proof of Lemma 1:

Use Chinese Remainder Theorem and factor $\mathbb Z/m\mathbb Z=\mathbb Z/u\mathbb Z \times \mathbb Z/v\mathbb Z$.

For $a\in (\mathbb Z/u \mathbb Z)^*$ define property

$P(a)$: There exists $b\in(\mathbb Z/v \mathbb Z)^*$ such that $(a,b),(a,-b)\in \Phi_m$.

$P(a)$ implies $(2a,0)\in\Phi_m^2$. So if for every $a$ we have $P(a)$ or $P(-a)$ we can conclude.

If there exists $a_0$ such that [non $P(a_0)$ and non $P(-a_0)$] holds then for every $b\in \mathbb Z/v\mathbb Z$

$[(a_0,b) \not \in \Phi_m\mbox{ xor }(a_0,-b) \not \in \Phi_m ]$

and

$[(-a_0,b) \not \in \Phi_m\mbox{ xor }(-a_0,-b) \not \in \Phi_m ]$.

Moreover, if $(a_0,b)\in \Phi_m$ then $-(a_0,-b)\in \Phi_m$ and $(0,2b)\in\Phi_m^2$. Similarly $(a_0,-b)\in \Phi_m$ yields $(0,-2b)\in\Phi_m^2$ and we see there exists a partition $\Phi_v$ of $(\mathbb Z/v \mathbb Z)^*$ such that $\{(0,2b)\vert b \in \Phi_v\}\subset \Phi_m^2$.

-
Hi gcousin (and welcome here)! You surely don't need to be on MathOverflow to answer jvp's questions ;) – Loïc Teyssier Jul 8 '13 at 16:45
Hi Loïc. Indeed, the question was motivated by a work in progress with gcousin and another colleague. Since this is still not a definitive answer, I suggested to gcousin to post it here. Perhaps others can build on it to give a final answer. – jvp Jul 8 '13 at 17:02
@quid: It is impressive ! As $m/\varphi(m)\leq (3/2)^{k-1}\cdot 2$ for $m$ even and $m/\varphi(m)\leq (3/2)^{k}$ for $m$ odd your general arguments give better result that mi ad hoc computation. – gcousin Jul 9 '13 at 1:29
I am glad you like the argument, if something else comes to mind I will update my answer. – quid Jul 9 '13 at 12:41
To avoid confusion for later readers: the comment of gcousin refers to an earlier version of my answer, which contained an error; the current version of it is is corrected but not optimized regarding quantive aspects (as it became obsolete before). – quid Jul 11 '13 at 0:18

This is not a full answer, it only shows the following (using the notation of the question):

For every $c>0$ there exist an $N$ depending only on $c$ such that $1 \in \Phi^N$ for each $\Phi$ and $m$ with $\varphi(m)/m>c$.

Unfortuantely, there is of course no positive lower bound on $\varphi(m)/m$ valid for all $m$, the worst case being about $e^{-\gamma}(\log \log m)^{-1}$.

But, on the postive side in this way one has, for example, a value of $N$ depending only on (an upper bound on) the number of distinct prime divisors of $m$.

The above result is a direct application of a result of Klopsch and Lev 'Generating abelian groups by addition only' (Theorem 2.9). [I used additive terminology below as done in the other answer.]

Recalling only the most relevant part for the purpose at hand it says:

Let $G$ be a finitie abelian group, and suppose that $\rho \ge 4$. Then $$s_{\rho}^+ (G) \le \frac{2}{\rho + 1} |G|$$

I do not recall the formal definition of $s_{\rho}^+ (G)$ (see Section 2.2 of the paper) but it is defined in such a way as to assert that for every generating set $A$ of $G$ of size larger than $s_{\rho}^+ (G)$ every element of $G$ is the sum of less than $\rho$ elements of $A$ (repetitions allowed).

To put this in line with the current problem it follows in particular that $0$ is the sum of exactly $\rho!$ elements of $A$. [This is inefficient. I just wanted a quick fix. Asymptotics seem not relevant anymore also see other argument.]

So, changing back to th notation of the question, given a $c>0$ one gets for all $m$ such that $\phi(m)/m > c$ that $$1 \in \Phi^N \text{ for } N = \lceil 4/c \rceil !$$

Added: Here is a more specfic approach. Recall Chowla's generalization of Cauchy-Davenport's theorem.

For $A,B \subset \mathbb{Z}/m \mathbb{Z}$ such that $0 \in A$ and all other elements of $A$ have order $m$ one has $$|A + B| \ge \min \{|A|+ |B| -1, m \}$$

Applying this with $A =\Phi \cup \{0\}$ and $B =\Phi$, and repeatedly to compute $A+A+\dots + A + B$. One gets that $0$ is the nonemty sum of at most $\lceil 2m/\varphi(m) \rceil$ many elements of $\Phi$ and thus exactly of the lcm of $2, \dots , \lceil 2m/\varphi(m) \rceil$ many.

-
Since my comments in David's answer became obsolete, I have deleted them. Thank you for your answer by the way. – jvp Jul 11 '13 at 0:25
@jvp: You are welcome! I also deleted my obsolete comments on David Speyer's answer. – quid Jul 11 '13 at 0:35