I am stuck with an elementary-looking problem, which does not belong to my usual field of research so I eventually decided to ask it on MO.
Let $S$ be a finite set of integers. For $P$ a subset of $S$, I note
$$s_P = \sum_{s \in P} s$$
the sum of elements in $P$.
I assume that $S$ satisfies the following property
$$ (*) \ \ \ \ \ \ \forall P,Q \subset S, \ \ \ s_P=s_Q \Longrightarrow P=Q$$
In other words, $(*)$ means that the set $R=$ {$ s_P,\ P \subset S$} has
maximal cardinality:
$$ (*) \ \ \ \ \ \ |R| = 2^ {|S|}$$
(Is there a name for the property $(*)$? additively free maybe?)
Now for $x \in [0,1]$ a real number, I consider the exponential sum
$$f(x) = \prod_{s \in S} (1+e^{2 i \pi s x}) = \sum_{r \in R} e^{2 i \pi r x}.$$
(Seen as a function of $e^{2i \pi x}$ on the unit circle of $\mathbb C$, $f$ is the Fourier
transform $\widehat{\chi_R}$ of the chatacteristic function $\chi_R$ of $R \subset \mathbb Z$.) I am interested in upper bounds for the $L^1$ norm of $f$,
$$||f||_1 = \int _{x=0}^1 |f(x)| dx.$$
A very simple application of Cauchy-Schwarz gives
$$||f||_1 < \sqrt{|R|} = \sqrt{2}^{|S|}$$
My question is:
When $|S|$ goes to $\infty$, can we prove an asymptotically better upper bound for $||f||_1$ than the Cauchy-Schwarz estimate above?
For example, is there a positive real
$\alpha < \sqrt{2}$ such that $||f||_1 < \alpha^{|S|}$ for all $S$ satisfying $(*)$ ? (Edit: same question for sets $S$ satisfying the stronger property $(*2)$ below).
Example: when $S=${$ 1,2,4,\dots,2^{n-1}$}, then $|S|=n$ and $R=${$0,1,2,3,\dots,2^n-1$}, so $S$ satisfies $(*)$, then $f(x)$ is essentially (up to multiplication by a complex of modulus 1)
the Dirichlet kernel $D_{2^{n-1}}(x)$ and a famous result (of Dirichlet?) says that $$||f||_1 \sim \log (2^{n-1}) \sim n = |S|,$$ so in this case we get a much better bound than the Cauchy-Schwarz bound, and which is essentially optimal by the Littlewood conjecture (now a theorem, saying that $||\widehat{\chi_R}||_1 >> \log |R|$).
Edit: This suggests to restrain ourselves at first to sets $S$ satisfying the stronger property
$(*2) \ \ \ $ every element of $S$ is a power of $2$.
Non-Example: removed as pointless after Noam's comment; replaced with this Remark:
Without the hypothesis $(*)$, (for $f$ defined as a product over $S$ as above, or as a sum over $R$ if $R$ is interpreted as a multiset),
the Cauchy-Schwarz bound $||f||_1 \leq \sqrt{2}^{|S|}$ does not hold any more, and one can not in general improve on the trivial bound $||f||_1 \leq 2^{|S|}$ as shown in Noam's comment
below.
But in general I am stuck. I thought that the product expression of $f(s)$ might help,
but I was not able to use it in a clever way.
Numerical evidence is not very conclusive but does not seem to point toward a polynomial bounds in $|S|$. Any advice, reference, intuition, conjecture, solution (proof or disproof) welcome. I am not even sure that my tags are right, please feel free to modify them. PS: my motivation comes form Galois representations.
Best Answer
As Noam correctly mentioned, the upper bound has to be exponential. However, the exponent can, indeed, be improved.
One (fairly cheap) trick is to look at $|f(x)|^2=2^{|S|}\prod_S(1+\cos 2\pi sx)$. If we can show that the product is bounded from above by $e^{-c|S|}$ outside a set of measure $e^{-c|S|}$, we can get away with Cauchy-Schwarz. Now, $\log(1+y)\le y-cy^2$ for $y\in[-1,1]$ with some $c>0$. Since $2\cos^2 y=1+\cos 2y$, we see that the square term will give us a fixed linear in $|S|$ push down, so it remains to show that for every $a>0$, the set of $x$ for which $\left|\sum_{s\in S} \cos 2\pi sx \right|$ is at least $a|S|$ has exponentially small measure (we'll need to use that twice: once for $x$ and once for $2x$).
This is actually pretty easy if we recall the reverse inequality $\log(1+x)\ge x-Cx^2$ for $x\in[-\frac 12,\frac 12]$, say. Note that the unique representation as a sum property implies that $$ \int_0^1 \prod(1+t\cos 2\pi sx)\,dx=1 $$ for every $t\in\mathbb R$. Assuming that $\sum_{s\in S} \cos 2\pi sx>a|S|$ on a set $E$, choose $t\in(0,\frac 12)$ so small that $b=at-Ct^2>0$. Then, clearly, the product is at least $e^{b|S|}$ on $E$ and the desired exponential bound on the measure of $E$ follows at once. The other set where $\sum_{s\in S} \cos 2\pi sx<-a|S|$ is treated the same way using small negative $t$.
This all is extremely crude, of course. However, it answers the original question in the affirmative, so I'll stop here :).