Uniformly small sums of roots of unity I have considerable numerical evidence that
for all $0\leq k\leq{{n-1}\over 2}$ ($n$ odd) there exists a subset $
S_k$ of {1,2,...,n} of cardinality $k$
such that the modulus square of $g(z)=\sum_{j\in S_k}z^j$ is less than
$n/2$ for ALL $n^{th}$ roots of unity $z\neq 1.$ [By the way, I am not 
assuming that $n$ is prime.] Am I having a run of bad 
days, or is this a bummer to prove?
Greg
 A: This is a reworked version of my original answer, which now solves the problem for infinitely many pairs $(n,k)$ ( but certainly not all pairs).
Let $G:={\mathbb Z}/n{\mathbb Z}$. You want to show that for every $1<k<n/2$, there is a subset $S\subset G$ of size $|S|=k$ such that the indicator function $1_S$ has all its non-trivial Fourier coefficients $\hat1_S(\chi)$ smaller than $\sqrt{n/2}$ in absolute value. 
Denoting by $r_S(g)$ the number of representations of $g$ in the form $g=s'-s''$ with $s',s''\in S$, we have the easily-verified identity
  $$ |\hat 1_S(\chi)|^2 = \sum_{g\in G} r_S(g)\chi(g),\quad \chi\in\hat G. \tag{$\ast$} $$
Suppose now that $S$ is a $(n,k,\lambda)$-difference set in $G$; that is, a $k$-element subset of $G$ such that $r_S(g)=\lambda$ for each non-zero element $g\in G$. A simple double counting shows that a necessary condition for an $(n,k,\lambda)$-difference set in $G$ to exist is that $k(k-1)=\lambda(n-1)$. Consequently, it follows from ($\ast$) that for such a set $S$ and any non-principal character $\chi$, we have
  $$ |\hat1_S(\chi)|^2 = k-\lambda \le \frac{k(k-1)}{2\lambda} = \frac{n-1}2, $$
as wanted.
This answers your question in the situation where the group $G={\mathbb Z}/n{\mathbb Z}$ admits an $(n,k,\lambda)$-difference set, for an appropriate value for $\lambda$. Such difference set are known to exist for infinitely many pairs $(n,k)$, just google for "cyclic difference sets" (here "cyclic" indicates that we are interested in difference subsets of cyclic groups).
