MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Jorge Vitório Pereira 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. – Jorge Vitório Pereira 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
up vote 12 down vote accepted

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.

share|cite|improve this answer
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 ]$


$[(-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$.

share|cite|improve this answer
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. – Jorge Vitório Pereira 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.

share|cite|improve this answer
Since my comments in David's answer became obsolete, I have deleted them. Thank you for your answer by the way. – Jorge Vitório Pereira 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.