MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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-Schwartz 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-Schwartz 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-Schwartz 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-Schwartz 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 bouns 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.

share|cite|improve this question
Regarding the side question on the name: I do not think there is really a standard name "sets with distinct subset sums" perhaps, see But then also minor variations of this seem used, as it is in some sense more a description than a name; I think also "unique-sum sets" is used sometimes. – quid Mar 6 '13 at 18:56
Joel, this is a nice question. I haven't thought about it yet, but the first thing that comes to my mind (especially in connection with your second condition) is the paper of Mauduit and Rivat on binary digits of primes. They have to estimate the L^1 norm of the exponential sum of some Riesz products quite similar to yours, and they do beat the trivial Cauchy-Schwarz bound by an expontial factor. – Ben Green Mar 6 '13 at 21:35
I chatted with Tom Sanders about this today in Oxford, and I think we can more-or-less solve it, at least the second case. The key idea is to write |1 + e(t)| as 2^{1/2} (1 + cos(2 pi t))^{1/2}, then use the inequality (1 + x)^{1/2} \leq 1 + x/2 - cx^2, valid for some $c > 0 (in fact for c = 3/2 - 2^{1/2}). Now expand everything out, and you get a bound for your integral of 2^{n/2}(1 - c/4)^n if S is "good": has no relations with coefficients <= 2. A bit of fiddling should give exactly what you want, with your weaker assumption on S; in the powers of two case you can split S into two good sets – Ben Green Mar 7 '13 at 22:08
Also, heuristically I think we expect $\|f\|_1^{1/n}$ to look like $4/\pi = 1.273...$ which is the average of $2\left|\cos x\right|$. It's probably not too hard to prove that this is what happens for random $S$ (which are almost always subsum-distinct, and indeed almost always have no relations with small coefficients). – Noam D. Elkies Mar 8 '13 at 16:30
And yes, I first tried to bound $\left|\cos x\right|$ above by a linear combination of just $1$ and $\cos^2x$ to get a bound on $\|f\|_1$ valid for any subsum-distinct set. Unfortunately (and annoyingly) the best linear upper bound is $2^{-3/2}(1+2\cos^2(x))$ which gives only an alternative proof that $\|f\|_1<2^{n/2}$. Even worse, for each $\alpha\in(0,2)$ the best linear upper bound on $\left|\cos^\alpha x\right|$ yields only an alternative proof that $\|f\|_\alpha<2^{n/2}$ (where an exponential improvement for any one $\alpha \in (0,2)$ would have given the desired result for $\alpha=1$). – Noam D. Elkies Mar 8 '13 at 17:12
up vote 9 down vote accepted

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 :).

share|cite|improve this answer
This is nicely done. – Ben Green Mar 11 '13 at 10:13
Dear Fedja, I understand the major part of your proof and it is beautiful. I have a problem with one detail, when you write " 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." Let us call E this exceptional set.I understand that you get an upper bound of the integral of the product by $e^{-c|S|}$ on the complement of E, but what about the integral on E? The obvious upper bound for the integral is $\mu(E) 2^|S|= e^{(\log 2 - c)| |S|}$ since the product itself is bounded by 2^|S|. So you need... – Joël Mar 11 '13 at 17:08
... $c>\log 2$ to conclude, or what am I missing? Now this $c$ is the $b$ in your proof below, and it doesn't seem obvious you can take it large enough? – Joël Mar 11 '13 at 17:10
Dear Fedja, I would like to use your argument for a lemma in a paper I am writing. Do you authorize me to do so ? If so, I'd like to to attribute the argument to you and to thank you, but I don't know your real name. I can name you as "Fedja" if you prefer, but otherwise could you please send me your name by email ? (my email is easy to find on my webpage, which is linked from my MO profile page). Thanks. – Joël May 7 '13 at 14:46
Dear Joel, First, no authorization is required to use any of my posts in any way you find appropriate. The goal of communication is to share the information, not to establish property rights. Second, attributing the argument to me would be ridiculous, because it is, probably much older than I. Whom to attribute it to then? I don't really know. Something like that can be found in Zygmund's "Trigonometric series", something else in various papers on Salem sets. It is one of the tricks I picked somewhere on my way, but when and where I can no longer tell. Just cite MO and stop at that. :) – fedja May 25 '13 at 1:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.