<p>Suppose that <span class="math-container">$\varphi_1, \dots, \varphi_n$</span> are <span class="math-container">$n$</span> real numbers. Given <span class="math-container">$c \in [0,n]$</span>, we want to find the smallest <span class="math-container">$t &gt; 0$</span> such that:
<span class="math-container">$$
\left\vert \sum_{k=1}^{n}e^{i \varphi_k t}\right\vert \leq c
$$</span>
What is the computational complexity of this task? Note that for certain choices of <span class="math-container">$\varphi_k$</span> and <span class="math-container">$c$</span> such a <span class="math-container">$t$</span> might not exist (e.g. if most <span class="math-container">$\varphi_k$</span> are zero and <span class="math-container">$c=o(n)$</span>) or in general may be arbitrarily large. Intuitively, this should somehow be related to Diophantine properties of <span class="math-container">$\varphi_k$</span> and seems hard, but I was unable to find a reference.</p>

CC BY-SA 4.0
2024-11-19T11:24:15.433Z
Is $t$ an integer? If not, why should such a least $t$ exist, and how it is supposed to be represented in the output? Also, how do you represent the real numbers in the input? What is your computation model that it can deal with arbitrary reals, and how do you measure complexity in this model? If, as you say, $t$ may get arbitrarily large, perhaps the problem is not computable at all?
Emil Jeřábek
CC BY-SA 4.0
2024-11-19T11:47:33.813Z
Phi are given to some finite precision - the answer will of course depend on this precision. We may assume that t is an integer.
Marcin Kotowski
CC BY-SA 4.0
2024-11-19T12:36:50.517Z
If the input is just rational approximations of the $\varphi_k$ to some precision, then (1) the answer of the algorithm may be essentially unrelated to the answer for the unknown "true" $\varphi_k$ that the input is supposed to "approximate", and (2) the inputs are actually *rational* rather than real, hence I don't see how Diophantine approximation properties of the inputs would come into play, as these trivialize for rational numbers.
Emil Jeřábek
CC BY-SA 4.0
2024-11-19T13:30:38.433Z
Let me rephrase that: if the problem actually depends on the Diophantine properties of the $\varphi_k$, it is hopelessly non-continuous, and cannot be sensibly formulated unless you find a way of representing the $\varphi_k$ *exactly* rather than by approximations (e.g., by restricting them to a countable domain such as algebraic numbers, or by using a model of computation that can manipulate exact reals).
Emil Jeřábek
CC BY-SA 4.0
2024-11-19T13:56:45.797Z
Thanks for the comments. I'm perfectly happy to restrict to the case when phis are rational.
Marcin Kotowski
<cc.complexity-theory><time-complexity>
Computational complexity of a complex exponential sum
Marcin Kotowski
# Computational complexity of a complex exponential sum

(Asked by: username_0 on 2024-11-19)

Suppose that $\varphi\_1, \dots, \varphi\_n$ are $n$ real numbers. Given $c \in [0,n]$, we want to find the smallest $t > 0$ such that:
$$
\left\vert \sum\_{k=1}^{n}e^{i \varphi\_k t}\right\vert \leq c
$$
What is the computational complexity of this task? Note that for certain choices of $\varphi\_k$ and $c$ such a $t$ might not exist (e.g. if most $\varphi\_k$ are zero and $c=o(n)$) or in general may be arbitrarily large. Intuitively, this should somehow be related to Diophantine properties of $\varphi\_k$ and seems hard, but I was unable to find a reference.

**Tags:** cc.complexity-theory, time-complexity
> **Comments:**
> **username_1**: Is $t$ an integer? If not, why should such a least $t$ exist, and how it is supposed to be represented in the output? Also, how do you represent the real numbers in the input? What is your computation model that it can deal with arbitrary reals, and how do you measure complexity in this model? If, as you say, $t$ may get arbitrarily large, perhaps the problem is not computable at all?  
> **username_0**: Phi are given to some finite precision - the answer will of course depend on this precision. We may assume that t is an integer.  
> **username_1**: If the input is just rational approximations of the $\varphi_k$ to some precision, then (1) the answer of the algorithm may be essentially unrelated to the answer for the unknown "true" $\varphi_k$ that the input is supposed to "approximate", and (2) the inputs are actually *rational* rather than real, hence I don't see how Diophantine approximation properties of the inputs would come into play, as these trivialize for rational numbers.  
> **username_1**: Let me rephrase that: if the problem actually depends on the Diophantine properties of the $\varphi_k$, it is hopelessly non-continuous, and cannot be sensibly formulated unless you find a way of representing the $\varphi_k$ *exactly* rather than by approximations (e.g., by restricting them to a countable domain such as algebraic numbers, or by using a model of computation that can manipulate exact reals).  
> **username_0**: Thanks for the comments. I'm perfectly happy to restrict to the case when phis are rational.  

---

## 0 answers

