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
8
-
$\begingroup$ Just to clarify: do you mean that for each such $k$ there exists an $S$ of cardinality $k$, etc? $\endgroup$– Yemon ChoiCommented Jul 4, 2015 at 21:48
-
$\begingroup$ Something is fishy: if we just take any pair of "almost opposite" roots of unity, the absolute value of their sum is of order $1/n$, so you can easily get constant instead of $\sqrt n$ for large $n$. $\endgroup$– fedjaCommented Jul 4, 2015 at 22:49
-
$\begingroup$ @fedja sum of squares of all $n-1$ absolute values we are interested in equals $nk-k^2$, how may they all be uniformly bounded? $\endgroup$– Fedor PetrovCommented Jul 4, 2015 at 23:20
-
$\begingroup$ The set S is fixed. For each z we construct the sum g which depends on z and S. If n were prime we could use some symmetry, but g has to be bounded even for n not prime and arbitrary z. $\endgroup$– The Masked AvengerCommented Jul 4, 2015 at 23:46
-
3$\begingroup$ One possibility is to try to do something similar to Spencer's "Six standard deviations suffice" (note that the full sum is 0, so you can restate it in terms of "mean zero" coefficients, say $\pm 1$ for half-size sets), but that will give only about $6n$, not $n/2$... $\endgroup$– fedjaCommented Jul 5, 2015 at 11:45
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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).
-
$\begingroup$ To Seva: This shows me that you understand my question. As to the answer, it seems elusive. $\endgroup$– GregCommented Jul 6, 2015 at 17:56
-
$\begingroup$ To Seva: Thanks for your observations. It is important NOT TO QUALIFY AS AN ANSWER the observations you make on the problem. The question is now registered to have an answer, when in fact it does not. A technical, yet annoying issue. $\endgroup$– GregCommented Aug 26, 2015 at 21:16
-
$\begingroup$ @Greg: I have reworked the answer, so comments made earlier seem irrelevant now. You can just delete them if you agree. $\endgroup$– SevaCommented Aug 27, 2015 at 15:52