24
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ I think you want $\phi$ to be an automorphism of finite order. $\endgroup$ Jul 4, 2013 at 16:09
  • $\begingroup$ Just curious: why do you need this kind of result ? Do you want to apply the fixed point formula to $\phi$ ? $\endgroup$ Jul 5, 2013 at 20:20
  • $\begingroup$ 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. $\endgroup$ Jul 5, 2013 at 21:29
  • 1
    $\begingroup$ 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$. $\endgroup$ Jul 8, 2013 at 3:51
  • $\begingroup$ ah, I see. When $m$ is prime, it's ok. $\endgroup$ Jul 8, 2013 at 7:00

3 Answers 3

12
+500
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – user9072
    Jul 10, 2013 at 19:05
  • $\begingroup$ 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$. $\endgroup$
    – GH from MO
    Jul 11, 2013 at 0:03
  • 1
    $\begingroup$ @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. $\endgroup$
    – GH from MO
    Jul 11, 2013 at 0:20
8
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Hi gcousin (and welcome here)! You surely don't need to be on MathOverflow to answer jvp's questions ;) $\endgroup$ Jul 8, 2013 at 16:45
  • $\begingroup$ 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. $\endgroup$ Jul 8, 2013 at 17:02
  • $\begingroup$ @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. $\endgroup$
    – gcousin
    Jul 9, 2013 at 1:29
  • $\begingroup$ I am glad you like the argument, if something else comes to mind I will update my answer. $\endgroup$
    – user9072
    Jul 9, 2013 at 12:41
  • 1
    $\begingroup$ @LSpice, It is a preprint for a long time, you may find its last version on the arxiv at arxiv.org/abs/1604.05276. $\endgroup$
    – gcousin
    Jul 29, 2019 at 19:46
8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Since my comments in David's answer became obsolete, I have deleted them. Thank you for your answer by the way. $\endgroup$ Jul 11, 2013 at 0:25
  • $\begingroup$ @jvp: You are welcome! I also deleted my obsolete comments on David Speyer's answer. $\endgroup$
    – user9072
    Jul 11, 2013 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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