2

Let $p$ be a prime. Consider a sequence $S$ of $p$ binary numbers $x_n \in \{ 0, 1 \}$, i.e. $S = \{x_1, x_2, \cdots, x_p\}$, where the number of zeroes in $S$ is neither $0$ nor $p$. Then the conjecture is: for all such sequences, all discrete fourier transformation (DFT) components $\hat S_k$ of $S$ are nonzero. That is, show that, $\forall k = 1\cdots p$, one obtains $\hat S_k = \sum_{n=1}^p x_n \exp (2 \pi i \frac{ n k }{p}) \ne 0$.

A way to the solution might be the visualization that a vectorial sum of $p$ evenly distributed spokes in a wheel (the unit circle) is performed, where only those spokes with $x_n = 1$ are existent, and where every $k$th spoke (modulo $p)$ is counted, and the vector sum will not disappear.

It is clear that the conjecture only holds if $p$ is prime. Since if it weren't, write $p= q \cdot r$, and consider a sequence $S^q$ where every $q$th entry is $x_n = 1$ and all others are $0$. The DFT components $\hat S^q_k$ of $S^q$ will then be $$\hat S^q_k = \sum_{n=1}^p x_n \exp (2 \pi i\frac{ n k }{q r}) = \sum_{n=1}^r \exp (2 \pi i \frac{ n q k }{q r}) = \sum_{n=1}^r \exp (2 \pi i \frac{ n k }{r}) = 0.$$

Greg Martin
  • 78,820
Andreas
  • 15,175
  • 1
    This may be using a sledgehammer to crack a nut, but "On Vanishing sums of roots of unity" by Lam and Leung gives your desired result as a special case of their main result. – Andreas Lenz Sep 25 '23 at 17:24

1 Answers1

5

This DFT $\hat S_k$ equals $f(\zeta_k)$, where $f(t) = x_p + \sum_{n=1}^{p-1} x_n t^n$ is a polynomial with integer coefficients and $\zeta_k = \exp(2\pi i k/p)$ is a primitive $p$th root of unity (since $p$ is prime). The only way $f(\zeta_k)$ could equal $0$ is if $f(t)$ is a multiple of the minimal polynomial of $\zeta_k$, which is $1+t+t^2+\cdots+t^{p-1}$. There are only two cases where this happens, namely $x_1=\cdots=x_p=0$ and $x_1=\cdots=x_p=1$; this finishes the proof.

(Proof that $\zeta_k$ is a primitive $p$th root of unity: it is a $p$th root of unity since $\zeta_k^p = \exp(2\pi i k/p)^p = \exp(2\pi i k p/p) = \exp(2\pi i k) = 1$, but for any $1\le m\le p-1$ we have $\zeta_k^m = \exp(2\pi i k/p)^m = \exp(2\pi i k m/p) \ne 1$ since $km$ is not a multiple of $p$.)

Greg Martin
  • 78,820
  • Thanks Greg. I was just wondering whether this needs another step. You write: "$\zeta_k = \exp(2\pi i k/p)$ is a primitive $p$th root of unity". For this to hold for all $k$, one needs to show that $p$ must be prime (or is that obvious by other means?). For if $p$ were not prime, then for some $k$, a minimal polynomial of $\zeta_k$ with smaller degree than $p-1$ could be constructed, and then the rest of the proof would not hold. – Andreas Sep 26 '23 at 09:47
  • don't you yourself say $p$ is prime in your question? – kodlu Sep 26 '23 at 15:00
  • @kodlu Yes the question states that $p$ is prime. The statement which needs to be proven is: "For $p$ prime, and for all $k$, $\zeta_k = \exp(2\pi i k/p)$ is a primitive $p$th root of unity." It is already clear that this does not hold if $p$ is not prime. However, that doesn't prove the positive statement that it holds if $p$ is prime. – Andreas Sep 27 '23 at 07:41
  • Dear Greg, to complete the question: Do you have a proof for the statement: " For $p$ prime, and for all $k$, $\zeta_k = \exp(2\pi i k/p)$ is a primitive $p$th root of unity." ? – Andreas Oct 04 '23 at 08:34
  • I encourage you to review the definition of "primitive $p$th root of unity" and verify it directly by calculating the powers of $\zeta_k$. – Greg Martin Oct 04 '23 at 15:32
  • There is a little bit more to do than just calculating the powers. I found a proof here: https://math.stackexchange.com/a/101123/317854 – Andreas Oct 05 '23 at 10:49