The Geometry of Cyclical Social Trends

Let $d:=\frac{1}{2}(e+f)$ be the midpoint of $ef$. The segment $Od$ lies on the perpendicular bisector of $ef$, so it is orthogonal to $ef$; hence to $ab$. Thus, $d\cdot(b-a)=0$. Since $d=\frac{1}{2}(2pc+(1-p)a+(1-p)b)$, the lemma follows from $(2pc+(1-p)(a+b))\cdot(b-a)=0$.

Pick two distinct $u,v\in W$. Applying Lemma 2.9 in the complex plane, we set: $a=\frac{1}{|C|}\sum_{h\in C}\omega^{\langle u,h\rangle}$; $b=\frac{1}{|C|}\sum_{h\in C}\omega^{\langle v,h\rangle}$; and $c=1$; thus $e=\lambda_{u}$ and $f=\lambda_{v}$, which implies that the segments $Oe$ and $Of$ are of the same length. Abusing notation by treating $a,b,c$ as both vectors and complex numbers, we have $(b-a)\cdot c=\Re(b-a)$; therefore,

1. 1.

   If $2\Re(b-a)+|a|^{2}-|b|^{2}=0$, then $|a|=|b|$, which in turn implies that $\Re(b-a)=0$; hence $a=\bar{b}$ and $\lambda_{u}=\bar{\lambda}_{v}$.

2. 2.

   If $2\Re(b-a)+|a|^{2}-|b|^{2}\neq 0$, then $p$ is unique: $p=p_{u,v}$.

By Lemma 2.3, $\lambda_{v}=p+\frac{1-p}{|C|}\sum_{h\in C}\omega^{\langle v,h\rangle}$. Fix nonzero $v\in V$. Because $n$ is prime and the vectors $h_{1},\ldots,h_{m}$ from $C$ form a basis over the field $\mathbb{Z}/n\mathbb{Z}$, the $m$-by-$m$ matrix whose $i$-th row is $h_{i}$ is nonsingular. This implies that, in the sum $\sum_{h\in C}\omega^{\langle v,h\rangle}$, the exponent sequence $(1,0,\ldots,0)$ appears for exactly one value $v\in V$ and the same is true of $(-1,0,\ldots,0)$. This holds true of any one-hot vector with a single $\pm 1$ at any place and $0$ elsewhere. This means that, for $2m$ values of $v$, the eigenvalue $\lambda_{v}$ is of the form $p+\frac{1-p}{m}(m-1+\omega)$ or its conjugate. Simple examination shows that these are precisely the subdominant eigenvalues.

Because $n$ is prime, the cyclotomic polynomial for $\omega$ is $\Phi(z)=z^{n-1}+z^{n-2}+\cdots+z+1$. It is the minimal polynomial for $\omega$, which is unique. Note that $\langle v,h\rangle=vh$, since $m=1$. Given $v\in V$, we define the polynomial $g_{v}(z)=\sum_{h\in C}z^{vh}$ in the quotient ring of rational polynomials $\mathbb{Q}[z]/(z^{n}-1)$. Sorting the summands by degree modulo $n$, we have $g_{v}(z)=\sum_{k=0}^{n-1}q_{v,k}z^{k}$, for nonnegative integers $q_{v,k}$, where $\sum_{k}q_{v,k}=|C|$. If $\lambda_{v}=\lambda_{u}$, for some $u\in V$, then, by Lemma 2.3, $g_{v}(\omega)=g_{u}(\omega)$; hence $\Phi$ divides $g_{v}-g_{u}$. Because the latter is of degree at most $n-1$, it is either identically zero or equal to $\Phi$ up to a rational factor $r\neq 0$. In the second case,

This implies that $q_{v,k}-q_{u,k}=r\neq 0$, for all $0\leq k<n$, which contradicts the fact that $\sum_{k}q_{v,k}=\sum_{k}q_{u,k}=|C|$; therefore, $g_{v}=g_{u}$.

1. 1.

   If $v=0$, then $g_{v}(z)=|C|$; hence $g_{u}(z)=|C|$ and $u=0$, ie, $v=u$.

2. 2.

   If $v\neq 0$, then let $S_{v}=\{\omega^{vh}\,|\,h\in C\}$. Because $\mathbb{Z}/n\mathbb{Z}$ is a field, the $|C|$ roots of unity in $S_{v}$ are distinct; hence $q_{v,k}\in\{0,1\}$. It follows that $S_{v}=S_{u}$ and $|S_{v}|=|S_{u}|=|C|$; therefore, for some permutation $\sigma$ of order $|C|$, we have $vh=u\sigma(h)$, for all $h\in C$. Summing up both sides over $h\in C$ gives us $v\sum_{h\in C}h=u\sum_{h\in C}h\pmod{n}$; hence $v=u$, since $\sum_{h\in C}h\neq 0\pmod{n}$.

Of course, this assumes that $\vartheta\neq\emptyset$. Fix $v\in V$ and let $\beta_{v}=\sum_{w\in C}\big{(}\omega^{\langle v,w\rangle}-\omega^{-\langle v,w\rangle}\bigr{)}$; further, assume that $\beta_{v}$ is nonzero, hence imaginary. We have $\beta_{v}\,\psi_{u}^{v}=g_{u}^{\top}\psi^{v}$, where $g_{u}$ is a vector in $\{-1,0,1\}^{N}$. It follows that $\beta_{v}\,\psi^{v}=A\psi^{v}$, for an $N$-by-$N$ matrix $A$ whose nonzero elements are $\pm 1$ and whose rows are given by $g_{u}^{\top}$. Thus, $\beta_{v}$ is an imaginary eigenvalue of $A$; hence a complex root of the characteristic polynomial $\det(A-\gamma\mathbb{I})$. Let $r\geq 1$ be the rank of $A$ and let $\gamma_{1},\ldots,\gamma_{r}$ be its nonzero eigenvalues. Expansion of the determinant gives us a sum of monomials of the form $b_{i}\gamma^{l_{i}}$, for $1\leq i\leq 2^{N}N!$, where $b_{i}\in\{-1,0,1\}$. The subset of them given by $l_{i}=N-r$ add up to the product of the nonzero eigenvalues (times $\pm\gamma^{N-r}$); hence $\prod_{i=1}^{r}|\gamma_{i}|\geq 1$. Label $\gamma_{1}$ the nonzero eigenvalue of smallest modulus. The sum of the squared moduli of the eigenvalues of a matrix is at most the square of its Frobenius norm; hence no eigenvalue of $A$ can have a modulus larger than $\sqrt{2N|C|}$ and, therefore

Since $h\in W$, it follows from (6) that $0<\lambda=|\lambda_{h}|<1$. Thus,

With $\lambda_{h}$ assumed to be nonreal, Lemma 2.3 implies that so is $\beta_{h}$; hence $\beta_{h}\neq 0$. Applying (14) completes the proof.

We must have $|\vartheta|=1$. Let $\lambda_{h}$ be (an) eigenvalue corresponding to the unique angle in $\vartheta$; recall that $0<\theta_{h}<n/2$. As we replace $p$ by $p^{\prime}>p$, we use the prime sign with all relevant quantities post-substitution. Thus, the subdominant eigenvalue for $p^{\prime}$ associated with $\vartheta^{\prime}$ is denoted by $\lambda_{v}^{\prime}$; again, we assume that $|\vartheta^{\prime}|=1$. Note that $v$ might not necessarily be equal to $h$; hence the case analysis:

• •

  $v=h$: Using the same notation for complex numbers and the points in the plane they represent (Fig. 5), we see that $\lambda_{h}^{\prime}$ lies in (the relative interior of) the segment $1\lambda_{h}$; hence $\theta_{h}^{\prime}<\theta_{h}$.

• •

  $v\neq h$: We prove that, as illustrated in Fig. 5, all three conditions $|\lambda_{h}|>|\lambda_{v}|$, $|\lambda_{h}^{\prime}|<|\lambda_{v}^{\prime}|$, and $\theta_{h}<\theta_{v}^{\prime}\leq n/2$, cannot hold at the same time, which will establish the theorem. If we increase $q$ continuously from $p$ to $p^{\prime}$, $\theta_{h}(q)$ decreases continuously. (We use the argument $q$ to denote the fact that $\theta_{h}$ corresponds to the eigenvalue defined with $p$ replaced by $q$.) Since, at the end of that motion, $|\lambda_{h}(q)|<|\lambda_{v}(q)|$, by continuity we have $p_{o}<p^{\prime}$, where $p_{o}=\min\{q>p\,:\,|\lambda_{h}(q)|=|\lambda_{v}(q)|\}$. To simplify the notation, we repurpose the use of the prime superscript to refer to $p_{o}$ (eg, $p^{\prime}=p_{o}$). So, we now have $|\lambda_{h}^{\prime}|=|\lambda_{v}^{\prime}|$ and $\theta_{h}<\theta_{v}^{\prime}<\theta_{v}\leq n/2$. It follows that (i) the point $\lambda_{v}$ lies in the pie slice of radius $|\lambda_{h}|$ running counterclockwise from $\lambda_{h}$ to $-|\lambda_{h}|$ on the real axis. Also, because $|\lambda_{h}^{\prime}|=|\lambda_{v}^{\prime}|$ and $|\lambda_{h}|>|\lambda_{v}|$, setting $c=1$ as before in Lemma 2.9 shows that (ii) $\Re(\lambda_{v})>\Re(\lambda_{h})$.⁴⁴4The keen-eyed observer will notice that in the lemma we must plug in $(p_{o}-p)/(1-p)$ instead of $p$. Putting (i, ii) together shows that $\theta_{h}\geq n/4$ (as shown in Fig. 5). Consequently, the slope of the segment $\lambda_{h}\lambda_{v}$ is negative. Since that segment is parallel to $\lambda_{h}^{\prime}\lambda_{v}^{\prime}$, the perpendicular bisector of the latter has positive slope. Since that bisector is above $\lambda_{v}^{\prime}$ and $\Im(\lambda_{v}^{\prime})\geq 0$, this implies that $0$ and $\lambda_{h}^{\prime}$ are on opposite sides of that bisector; hence $|\lambda_{v}^{\prime}|<|\lambda_{h}^{\prime}|$, which is a contradiction.