Impact
~136k
people reached
- 0 posts edited
- 0 helpful flags
- 96 votes cast
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)? |