Ben Green
Reputation
3,773
Next privilege 5,000 Rep.
Approve tag wiki edits
 Apr 19 asked Additive Combinatorics - reference request Apr 9 comment Minimal size of subsets $A,B$ in a finite group $G$ such that $AB=G$ Is this exactly "coupon collecting analysis"? For each choice of B = {b_1,..,b_k} you can try and estimate the probability that AB is all of G, if A is chosen randomly. But then you have to sum over a large selection of B's, and the triangle inequality may be too crude. In fact, I posed as an open problem (Barbados workshop, March 2012) the question of deciding whether the log N should really be there. Can Z/NZ be covered by O(N^{1/2}) translates of a random set A of size N^{1/2}? Apr 8 awarded Good Answer Mar 26 comment Riemann Z function, bounds on number of non-trivial zeros along horizontal lines, rather than vertical ones I think that from standard asymptotics on the number of zeros of height up to T you get a bound of O(log T). Apparently even on RH is is only known that the multiplicity of 1/2 + iT as a zero is O(log T/log log T). So I guess you shouldn't expect too much better than this O(log T) bound, Mar 11 comment On the $L^1$-norm of certain exponential sums. This is nicely done. Mar 8 comment On the $L^1$-norm of certain exponential sums. Yep, this issue (of whether a 1-dissociated set, or "subsum-distinct" set) has a positive density 2-dissociated subset seems a little unclear. It seems closely related to work of Pisier and Bourgain from the late 80's on Sidon sets. In particular I wonder whether Pisier's arithmetic characterisation of Sidon sets works with 2-dissociated in place of dissociated. Perhaps the proposer could comment on whether he needs the full generality? Mar 8 comment On the $L^1$-norm of certain exponential sums. Noam, Very nice! To do the splitting, I was planning to use Holder: $\int |fg| \leq (\int |f|)^{1/3}(\int |g|)^{1/3}(\int |f g|^2)^{1/3}$. You have the trivial bound on each factor (note that fg is the FT of the set of subset sums of S), so you only need to win in one factor, say the first one. So actually, I think all you need is that any subsum-distinct set has a 2-dissociated subset of positive density. That's clear in the case of powers of 2 (just thin out every other power of two) but actually not so obvious in general. I'm looking at some literature on that right now. Mar 8 comment The polynomial Freiman-Ruzsa conjecture for the special case when $f$ is a bijection It seems unlikely to me that the bijection assumption would help. If f is an arbitrary function then, provided f is not "really far" from a bijection I'd expect that some modification f'(x) = f(x) + eps(x) with eps varying in a small set would make f' pretty close to a bijection (perhaps use Hall's marriage theorem or something). PFR for f and for f' are basically the same problem. Being a bijection is not a property that is useful in connection with several of the existing techniques in the area, particularly Fourier analysis (cf. the work of Sanders). Mar 7 comment On the $L^1$-norm of certain exponential sums. I should add, though, that I have to prepare an undergraduate lecture now - so I'll try and write down the details tomorrow. Mar 7 comment On the $L^1$-norm of certain exponential sums. 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 Mar 6 comment On the$L^1$-norm of certain exponential sums. 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. Jan 22 awarded Good Answer Dec 16 awarded Popular Question Oct 19 comment Showing non-expansion for$x\rightarrow x+1, x\rightarrow 2x.$Harald: I think his name is Gonzalo Fiz-Pontiveros. Sep 24 comment Möbius Randomness of the Rudin-Shapiro Sequence Terry is right. To get more than$o(n)$cancellation one would need to show that more general bilinear sums involving the Rudin-Shapiro sequence are small, not a tempting task, but probably fairly necessary. I note that it would also be enough to show that a weird variant of the Gowers$U^3$-norm of$\mu$is small -- not the usual Gowers norm$U^3[N]$, but the norm$U^3[F_2^n]$in which M\"obius is considered as a function on the binary cube via its binary digits. Not a very natural thing to try and compute. Sep 16 comment There exists B subset A, |B| = log n, A \cap 2*B = \emptyset A masters student from Lyon, Jehanne Dousse, recently improved [SSV] to log n logloglog n or thereabouts, by replacing the use of Szemeredi's theorem by a density increment argument generalising that of Roth, allowing one to locate inside a dense set A some elements x_1,...,x_k, all of whose midpoints also lie in A. The key is that these configurations can still be detected by Gowers' U2-norm. I have no clue what the correct bound is.... Jul 28 comment Growth rate of the infinity norm of Discrete Fourier Transform of +1,-1 vectors The answer is basically$\sqrt{n}$for large$n$.When$n$is prime, an example should be given by the Legendre symbol$f_i = (i | n)\$. Jun 18 awarded Enlightened Jun 18 awarded Nice Answer Jun 18 answered Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?