I have found reference to this problem. It is known as "the Rédei-de Bruijn-Schönberg theorem", which is proved in the following papers:

  • N. G. de Bruijn: On the factorization of cyclic groups, Indag. Math.15(1953), 370-377.
  • L. Rédei: Ein Beitrag zum Problem der Faktorisation von Abelschen Gruppen, ActaMath. Acad. Sci. Hungar.1(1950), 197-207.
  • I. J. Schoenberg: A note on the cyclotomic polynomial, Mathematika11(1964), 131-136.

End of update.

The background of this question is something about cyclotomic fields, but the statement doesn't involve any algebraic number theory. I just get puzzled by this (might be stupid) little question...

Let $n>1$ be an integer, and consider the vector space $\mathbb{C}^n$.

A vector $v=(v_1, \cdots, v_n) \in \mathbb{C}^n$ is called

  • periodic, if there is a proper divisor $d$ of $n$, such that $v_i = v_{i + d}$ for all $i$;
  • integral, if every $v_i$ is an integer.

Question: if an integral vector can be written as a finite sum of periodic vectors, then is it true that it can always be written as a finite sum of integral period vectors?

It should be clear that the field $\mathbb{C}$ could be replaced with any field of characteristic zero (e.g. $\mathbb{Q}$).

I would guess that the claim is true, but cannot convince myself with a proof...

So far I can only prove the case when $n$ has at most $2$ different prime factors, which doesn't help much in the general case.

I've also tried to adopt a point of view from cyclotomic fields, or representation theory, or doing some Fourier transform - but again I'm not intelligent enough to morph the question to something known...

Therefore I add all the possibly relevant tags.

EDIT: I add here a proof when $n = pq$ is the product of $2$ different primes. The more general case $n = p^r q^s$ is morally the same.

Since $n = pq$, every periodic vector $a$ either satisfies $a_i = a_{i + p}$ for all $i$, or satisfies $a_i = a_{i + q}$ for all $i$.

Hence any finite sum of periodic vectors can be written as $a + b$, where $a_i = a_{i + p}$ and $b_i = b_{i + q}$.

Now suppose that $v = a + b$ is such a sum, which is integral. This means that $a_i + b_i = 0\mod\mathbb{Z}$, which then gives: $$a_i = -b_i = -b_{i + q} = a_{i + q} \mod \mathbb{Z}.$$ Together with $a_i = a_{i + p}$, we conclude that all $a_i$ are equal $\mod\mathbb{Z}$, hence all $b_i$ also, and we can adjust them with a constant vector so as to make them both integral.

This trick doesn't work for more than $2$ prime factors, though...

  • $\begingroup$ My guess is that, if true, you should be able to prove it by characterizing sums of period vectors. If false, there is probably a counterexample involving roots of unity summing to 0 in different ways. $\endgroup$ – Kimball Sep 20 '19 at 8:24
  • $\begingroup$ Yes, it is closely related to summing roots of unities to $0$. But I still haven't solved it... $\endgroup$ – WhatsUp Sep 20 '19 at 14:33
  • $\begingroup$ viewing the vector space as the group algebra (or probably rather algebra of functions so we get contravariance) Z[Z/n], isn't the periodicity condition equivalent to saying that the multiplicity of any primitive character is zero? this should just be the fact that the characters are an integral basis for the class functions. $\endgroup$ – xir Sep 20 '19 at 15:12
  • $\begingroup$ @xir Yes, this is one of my equivalent interpretations, except that I only know how to work with $\mathbb{C}[\mathbb{Z}/n]$. Passing to $\mathbb{Q}[\mathbb{Z}/n]$ is not difficult, but I don't know how to deal with the possible denominators... $\endgroup$ – WhatsUp Sep 20 '19 at 17:10
  • $\begingroup$ Pie-in-the-sky suggestion: call $n$ a WhatsUp dimension if the statement holds for $n$. Primes are trivially WhatsUp dimensions (since periodic = constant then). You've proved that products of two primes are WhatsUp dimensions. Is it possible that your proof can be adapted to show that if $m$ and $n$ are relatively prime WhatsUp dimensions, then $mn$ is also a Whatsup dimension? If so then the result follows for all $n>1$ by factorization into prime powers. $\endgroup$ – Greg Martin Sep 20 '19 at 20:26

A beautiful question! Though I don't have the time or the space to fill in all the details, I think one can answer the question in the following way. The answer is yes.

We can reformulate the question as follows: let $I \subset \mathbb{Z}[x]$ be the ideal generated by the polynomials $$ \frac{x^n-1}{x^d-1}, \quad d \mid n, \quad d \neq n. $$ We claim that $I$ is $\mathbb{Z}$-saturated, that is, within $\mathbb{Q}[x]$, $$ \mathbb{Q} I \cap \mathbb{Z}[x] = I. $$ (Attach to each polynomial $f \in \mathbb{Q}[x]$ the sequence given by the coefficients of $f$ mod $x^n - 1$. The passage from $\mathbb{C}$ to $\mathbb{Q}$ is effected by some easy linear algebra.)

We claim, indeed, that $$ I = J := (\Phi_n) $$ is the ideal generated by the $n$th cyclotomic polynomial. Note that $J$ is visibly $\mathbb{Z}$-saturated.

  1. Clearly $$ (x^n-1) \subseteq I \subseteq J. $$
  2. Also, $\mathbb{Q}I = \mathbb{Q}J$, because the only common roots of the generators of $I$ are at the primitive $n$th roots of unity and are all simple. (This step uses the Nullstellensatz, which, since we have just one variable, isn't all that deep.)
  3. So if $I \neq J$, the discrepancy can be found locally, that is, there is a prime $p$ such that the images $\bar{I}, \bar{J}$ of $I$ and $J$ in $\mathbb{F}_p[x]$ are unequal. (Pass to the finite-dimensional $\mathbb{Q}$-vector space $\mathbb{Q}[x]/(x^n-1)$. The images $L_I$, $L_J$ are $\mathbb{Z}$-lattices with the same $\mathbb{Q}$-span; if they are unequal, pick $p | [L_J : L_I]$.)
  4. If $p \nmid n$, we are done by the Nullstellensatz again, because the $n$th roots of unity remain distinct in $\bar{\mathbb{F}}_p$.

  5. Now $p \mid n$. Let $$ \bar K = \left\{\frac{f}{\Phi_n(x)} : f \in \bar I \right\}. $$ We wish to prove that $\bar K$ is the unit ideal, that is, that the polynomials in $\bar K$ have no common roots. Suppose there is a common root $\lambda \in \bar{\mathbb{F}}_p$. Then $\lambda^n = 1$, since $x^n - 1 \in \bar I$. Let $\lambda$ be a primitive $r$th root of unity; note that $r \mid n$ and $p \nmid r$, so $r \mid n'$, where $n = p^k n'$ with $p \nmid n'$. We get a contradiction as follows:

    • If $r \neq n'$, then the element $$ \frac{x^n - 1}{\Phi_n(x) (x^{p^k r} - 1)} = \prod_{d|n,\, d\nmid p^k r,\, d \neq n} \Phi_d \in \bar K $$ has no root at $\lambda$ (because the factors $\Phi_r, \Phi_{pr}, \ldots, \Phi_{p^k r}$ have all been eliminated).
    • If $r = n'$, then the element $$ \frac{x^n - 1}{\Phi_n(x) (x^{n/p} - 1)} = \prod_{d|n,\, p^k \parallel d,\, d \neq n} \Phi_d \in \bar K $$ likewise has no root at $\lambda$.
  • $\begingroup$ Evan, thanks a lot for your answer. However, I have to apologize that I haven't updated the question since long time - because I forgot it... In fact, I myself obtained a proof of this result, and afterwards found it being proved in other places, e.g. arxiv.org/pdf/math/9511209.pdf Theorem 2.2. In that paper, it's cited as "the Rédei-de Bruijn-Schönberg theorem", which seems to date back to the 1950's. Sorry for not updating these informations... $\endgroup$ – WhatsUp Dec 30 '19 at 22:50
  • $\begingroup$ Wow! That's fine. $\endgroup$ – Evan O'Dorney Jan 1 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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