How to prove that $0$ sum could be reached

Question

I have $n$ random points $u_1, u_2, \ldots, u_n$ on the unit circle. Points are uniformly distributed.

I want to think about the points as associated angles $\theta_1, \theta_2, \ldots, \theta_n$ that are uniformly picked in $(-\pi, \pi]$.

Suppose, we rotate the circle, thus $\theta_i$ is a function of the angle $\theta$ of the new axis in the original frame.

For example, if $\theta_1 = \dfrac{\pi}{2}$ and we rotate the circle $\dfrac{\pi}{6}$ in the positive direction, then $\theta_1\left(\dfrac{\pi}{6}\right) = \dfrac{2}{3}\pi$.

Angles are adjusted to always stay in $(-\pi, \pi]$ range. See the animation below

Denote $S_{\theta} \triangleq \theta_1(\theta) + \theta_2(\theta) + \ldots + \theta_n(\theta)$.

Does there exist a rotation $\theta$ such that $S_{\theta} = 0$ ?

My gut feeling, is that yes. But I do not see a direction to prove the claim.

What I have done, is that rotating a circle clock-wise creates $S_{\theta}$ monotonically decreasing, except, when a point "crosses a negative X axis", at that point $2\pi$ are added.

But I don't see why $S_{\theta}$ changes the sign. It could stay negative or positive always.

Answer 1

Yes, such a value exists.

First, let's understand how any of the $\theta_i(\theta)$ functions looks like. Let's choose the direction of rotation such that $\theta_i(\theta)$ increases, unless it encounters the discontinuity jumping between $-\pi$ and $\pi$. In that case, $\theta_i(\theta)$ is just a linear function, increasing with slope $1$. If it reaches the value $\pi$, it will jump to $-\pi$ and continue from there linearly with slope 1 until again the value reaches $\pi$, which happens at an increment of $\theta$ of exactly $2\pi$.

So it's easy to see understand that $\theta_i(\theta)$ is $2\pi$-periodic (rotating the circle by $\theta+2\pi$ leaves the new axis in exactly the same position as rotating it by $\theta$). For a starting value of e.g. $\theta_i(0)=\frac{\pi}3$, the function looks like this:

The key insight now is that, no matter the starting value of $\theta_i(0)$, the Rieman integral of $\theta_i(\theta)$ over $[0,2\pi]$ is always zero. One can do this by hand calculation, but an easier way to see this is to realize that because the function is $2\pi$-periodic, the integral doesn't change when one moves the integration interval around, as long as the length stays at $2\pi$.

In this case, we can choose the interval to be $[-\theta_i(0),2\pi-\theta_i(0)]$, which means the function will always look like this in this interval, starting from $0$ up to $\pi$, the jumping down to $-\pi$ and climb back up to $0$.

The integral over the positive part of the function cancels the integral over the negative part exactly.

We are almost done now!

Since $S(\theta)$ (I'll use that instead of $S_\theta$ to stress the function character) equals $\sum_{i=1}^n \theta_i(\theta)$, we get

$$ \int_0^{2\pi}S(\theta) = \int_0^{2\pi}\sum_{i=1}^n \theta_i(\theta) = \sum_{i=1}^n\int_0^{2\pi}\theta_i(\theta) = 0.$$

In order for $S(\theta)$'s integral to be $0$, there must be positive and negative function values (if all were $0$, we would be done already). So there exist $x_1, x_2$ with $S(x_1) < 0, S(x_2) > 0$. Since $S(\theta)$ is of course also $2\pi$-periodic, we can assume $x_1 < x_2$.

$S(\theta)$ is the sum of piecewise increasing functions, so $S(\theta)$ is as well. $S(x_1)$ is negative, from here $S(\theta)$ increases (linearly, so continuosly) until it reaches a point of discontinuity, where it jumps down by $2\pi$. So if it reached function value $0$ during the linear increase, we found what we were looking for. If not, it was still negative when the jump happened, so it is still negative after the jump down, when the function will again start to rise.

But we know that the function will reach a positve value at point $x_2$, so at some point in a linerly rising part of $S(\theta)$ it will have to obtain the value $0$, which concludes the proof.

Answer 2

How about using $\theta=\frac{-(\theta_1+\theta_2+\cdots+\theta_n)}{n}$?

Then $$\begin{array}{rcl} \theta_1(\theta)+\cdots+\theta_n(\theta)&=&(\theta_1+\theta)+\cdots+(\theta_n+\theta)\\ &=&(\theta_1+\cdots+\theta_n)+(n\theta) \\ &=& (\theta_1+\cdots+\theta_n)+n \left(-\frac{\theta_1+\cdots \theta_n }{n} \right)\\ &=&0 \end{array} $$

Answer 3

Since the sum of the shifted angles differs from the sum of the original angles by $n\theta$ plus some multiple of $2\pi$, the problem can only be solved by taking $\theta=\theta(k)=-\frac{\theta_1+\cdots +\theta_n}n+\frac{2k\pi}n$ for suitable $k\in\Bbb Z$. This also means that we may assume wlog. that the angles are "normalized" to begin with, i.e., $$\tag1\theta_1+\cdots+\theta_n\in2\pi\Bbb Z$$ and $$\tag2\theta_1\le\theta_2\le\ldots\le \theta_n. $$ If for each interval $(\frac {2j-n}n\pi,\frac{2(j+1)-n}n\pi]$, $0\le j<n$, we know the number $N_j$ of angles $\theta_i$ are in that interval, then this already determines $\sum\theta_i$ up to an interval $(\alpha,\alpha+2\pi]$, and so by $(1)$ determines it completely. Hence for any $n$-tuple $\mathbf N=(N_0, \ldots, N_{n-1})$ of non-negative integers $N_j$ with $\sum N_j=n$, we can let $$ F(\mathbf N)=\frac1{2\pi}\sum_{i=1}^n\theta_i$$ where $\sum\theta_i$ is a multiple of $2\pi$ and exactly $N_j$ of the $\theta_i$ are in $(\frac {2j-n}n\pi,\frac{2(j+1)-1}n\pi]$; by the remark above, this is well-defined. If we define the rotation of such a tuple, $$\operatorname{rot}(N_0,\ldots, N_{n-1}):=(N_1,\ldots, N_{n-1},N_0),$$ then our goal is to find, for each valid $\mathbf N$, some $k\in\Bbb Z$ with $F(\operatorname{rot}^k\mathbf N)=0$.

Note that by the condition on the $\theta_i$, $$ \tag3\sum_{j=0}^{n-1}(\tfrac jn-\tfrac12)N_j<F(\mathbf N)\le 1+ \sum_{j=0}^{n-1}(\tfrac jn-\tfrac12)N_j$$ so that $$ F(\mathbf N)=\left\lfloor1+\sum_{j=0}^{n-1}(\tfrac jn-\tfrac12)N_j\right\rfloor.$$ It follows that $$\tag4 F(\operatorname{rot}\mathbf N)=F(\mathbf N)-1+N_0\ge F(\mathbf N)-1.$$

If we sum over all rotations of a period, i.e., with $$G(\mathbf N):=\sum_{k=0}^{n-1}F(\operatorname{rot}^k\mathbf N),$$we find from $(3)$ that $$ \sum_{j=0}^{n-1}(\tfrac jn-\tfrac12)\sum_{k=0}^{n-1}N_k<G(\mathbf N)\le n+\sum_{j=0}^{n-1}(\tfrac jn-\tfrac12)\sum_{k=0}^{n-1}N_k,$$ i.e., $$ -\frac n2<G(\mathbf N)\le \frac n2.$$ Therefore it is neither possible that all $F(\operatorname{rot}^k\mathbf N)$ of a period are positive nor that all are negative. As Hence there must exist some $k\in\Bbb N$ with $F(\operatorname{rot}^k\mathbf N)\ge 0$ and $F(\operatorname{rot}^{k+1}\mathbf N)\le 0$. Using $(4)$, we conclude that one of $F(\operatorname{rot}^k\mathbf N)$, $F(\operatorname{rot}^{k+1}\mathbf N)$ must be $=0$. $\square$