3
$\begingroup$

Consider the following equation with variable $n \in \mathbb{N}$:

$$\sum \limits_{i=1}^{k} \cos(n\theta_{i}) = 0.$$

Given $\theta_1,\dots,\theta_k$, I'd like to determine whether there exists $n \in \mathbb{N}$ such that the above equation holds.

For $k = 1$ a solution can be directly found in $O(1)$ time by taking the inverse cosine.

For $k = 2$ we can first factor it using the identity

$$\cos(A) + \cos(B) = 2\cos(\frac{A+B}{2})\cos(\frac{A-B}{2})$$

and then set both terms individually to $0$. The running time will be $O(1)$.

If all the $\theta_i$ are rational multiples of $\pi$ then the equation is periodic and solvable.

Are there general algorithms of solving for $k > 2$ and for values of $\theta_i$ for which $\cos(\theta_i)$ are algebraic numbers? If not, then are there any undecidability results like for roots of polynomials (as mentioned in the paper below)?

Undecidability in number theory. Bjorn Poonen, Notices of the American Math Society, March 2008.

I am considering all computation to be symbolic and exact. For example $\theta_1 = \cos^{-1}(1/3)$ is a possible input.

Improve this question
$\endgroup$
6
  • $\begingroup$ You have to define what solve means. Problem is decidable, polynomial roots are also decidable. As in polynomial root solving for higher polynomials we do not have representation in terms of elementary functions. There are roots, always (but some polynomials have only complex). If you cannot represent them in radical form it does not mean you cannot iteratively approximate them or present in terms of non-elementary functions. $\endgroup$ – Evil Aug 19 '15 at 15:00
  • $\begingroup$ I have added most of the required details. Do tell if any further are needed. $\endgroup$ – nikhil_vyas Aug 19 '15 at 20:26
  • $\begingroup$ Good stuff! So for $k=2$, your method allows us to reduce the problem to: given algebraic numbers $x_1,x_2$, determine whether $(\cos^{-1}(x_1) \pm \cos^{-1}(x_2))/\pi$ is rational or not. Is that decidable? How do we solve this in $O(1)$ time? Or did you have some alternate method in mind? I'm not immediately following what the algorithm is, after you set (say) $\cos((A+B)/2)=0$ (where $A=n\theta_1$, $B=n\theta_2$). Presumably we need to look for $n$ s.t. $n\theta$ is an integer multiple of $\pi$, where $\theta=(\theta_1+\theta_2)/2$ and $\theta_i = \cos^{-1}(x_i)$, but how can we do that? $\endgroup$ – D.W.♦ Aug 19 '15 at 22:34
  • $\begingroup$ Actually, I realized I have a more basic question. How do we solve it for $k=1$? Given $x_1$, we need to test whether there exists $n$ such that $n \theta_1 = n \cos^{-1}(x_1)$ is an integer multiple of $\pi$. This amounts to: given an algebraic number $x_1$, determine whether $\cos^{-1}(x_1)/\pi$ is a rational number. How do we do that? Are there known algorithms to solve that problem? Probably this just shows that I am not expert in this field. $\endgroup$ – D.W.♦ Aug 19 '15 at 22:41
  • $\begingroup$ I assume this undecidable part was for me. Diophantine equations and finding problems stated in paper are not algebraic or analytic root finding per se. It is as in title number theoretic. Polynomials in one variable with cosines are algebraic. Also asking TM to stop writing exact $\pi$ is unfair ;) I will check my notes and write down iff find something useful, as I did similar problem. Wow. Sorry, problem changed very much, you are not looking for real solutions :-/ $\endgroup$ – Evil Aug 19 '15 at 23:00

Your Answer

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

Browse other questions tagged or ask your own question.