I am looking for an upper bound $R=R\_{n,\varepsilon}$ such that for given $\varepsilon>0$ and real numbers $\alpha\_1, \dotsc, \alpha\_n$ in, say, $[1,2]$, there is $x\in [1,R]$ such that
$$
\frac 1n\sum\_{k-1}^n\cos(\alpha\_k x)\geq 1-\varepsilon
$$


Dirichlet's principle states that $x$ can be (an integer) smaller than $\varepsilon^{-n}$.


We are actually interested in the case where the $\alpha\_i$ are iid, say, uniform over $[1,2]$, so pathological cases of badly approximable $n$-tuples can be ignored, and a result holding with high probability would be great.


The main problem is that $n$ goes to infinity, our feeling is that we could get something in $\varepsilon^{-n/2}$, using Fubini's theorem, but it is not clear.



When does a random trigonometric sum approximate $1$?
$\newcommand\ep\varepsilon\newcommand\al\alpha$Let $X\_k:=\cos(\alpha\_kx)$. Then $X\_1,X\_2,\dots$ are iid random variables such that $P(X\_1<1)=1$ and hence $\mu:=EX\_1<1$, so that $\mu<1-\varepsilon$ if $\varepsilon\in(0,1-\mu)$. So, by the law of large numbers, with high probability we get the inequality
$$
\frac 1n\sum\_{k=1}^n\cos(\alpha\_k x)<1-\varepsilon, 
$$
opposite to your desired one, for all large enough $n$.


So, your idea of randomizing the $\alpha\_k$'s to exclude "pathological cases" is not working.




---


On the other hand, we can get the upper bound $2\pi\lceil(2\pi^2/\ep)^{n/2}\rceil$ on $x$ even without randomization. Indeed, by the [simultaneous version of Dirichlet's approximation theorem](https://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem#Simultaneous_version), for any real $\al\_1,\dots,\al\_n$ and any natural $N$ there exist integers $p\_1,\dots,p\_n,q$ such that $1\le q\le N$ and $|2p\_i\pi-2q\pi\al\_i|\le2\pi/N^{1/n}$ for all $i\in[n]:=\{1,\dots,n\}$. So, letting $x:=2q\pi$ and using the inequality $\cos(2p\pi)-\cos(2p\pi+t)\le t^2/2$ for integral $p$ and real $t$, we have
$$1-\cos(\al\_k x)=\cos(2p\_k\pi)-\cos(2q\pi\al\_i)
\le2\pi^2/N^{2/n}\le\ep$$
for all $k\in[n]$ if $N=\lceil(2\pi^2/\ep)^{n/2}\rceil$.


Therefore and because $1\le x=2q\pi\le2\pi N$, we get the upper bound $2\pi\lceil(2\pi^2/\ep)^{n/2}\rceil$, of the desired form, on the smallest number $x\ge1$ such that
$$
\frac 1n\sum\_{k-1}^n\cos(\al\_k x)\ge1-\ep.
$$


