Impact
~130k
people reached
- 0 posts edited
- 0 helpful flags
- 96 votes cast
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)? |
Jun
18 |
comment |
Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?
I agree it should probably be linear in n, but this might be rather hard to prove. Benny Sudakov was telling me that it is known (but difficult) that Hamming Balls of radius 1 cover with efficiency 1 + o(1), but this is an open problem for balls of radius 2. He may known about your question too; I'll ask him this afternoon. |
May
22 |
comment |
Nonlinear equations in integers
In fact there is no set of size $o(N)$ which misses all triples $(3k, 4k, 5k)$ by the following type of argument: consider such triples with $|k - N/10| < N/100$ (say). These are all disjoint. Therefore any set consisting of $98\%$ of ${1,..,N}$ contains a pythagorian triple. Computation of the exact density might be tricky. |
May
22 |
comment |
Nonlinear equations in integers
One of the references here, I bet: algo.inria.fr/csolve/triple |
May
22 |
comment |
Nonlinear equations in integers
I'm pretty sure, actually, that all sets of $99\%$ of $[1,...,N]$ contain a triple $(3k, 4k, 5k)$. I'm also pretty sure I can find a reference for this fact given a minute or two. |