User ben green - MathOverflow

Answer by Ben Green for Philosophy behind Yitang Zhang's work on the Twin Primes Conjecture

2013-05-21T16:01:10Z

The preprint is now available.

http://annals.math.princeton.edu/wp-content/uploads/YitangZhang.pdf

Answer by Ben Green for Proof of the weak Goldbach Conjecture

2013-05-14T11:26:51Z

I think this blog post of Terry Tao, as well as the comments following it (including some from Helfgott) answer this question as completely as one could reasonably hope.

https://terrytao.wordpress.com/2012/05/20/heuristic-limitations-of-the-circle-method/

Additive Combinatorics - reference request

2013-04-19T08:43:27Z

Let $A$ be a finite set of integers with $|A \hat{+} A| \leq K|A|$, where the $\hat{+}$ denotes restricted sumset: the set of all $a_1 + a_2$ with $a_1, a_2 \in A$ and $a_1 \neq a_2$.

Claim: $|A + A| \leq (K + o(1))|A|$, where $o(1)$ denotes a quantity tending to 0 as $|A|$ tends to $\infty$.

Sketch proof: Let $A'$ be the set of all $a \in A$ for which $2a$ cannot be represented as $a_1 + a_2$ with $a_1, a_2 \in A$, $a_1 \neq a_2$. Note that $2A' = (A + A) \setminus (A \hat{+} A)$, so it suffices to show that $A'$ is small. But $A'$ has no 3-term arithmetic progressions. But by standard results (Freiman, Ruzsa...) a set $A'$ with no 3-term progressions has $|A' + A'| \gg |A'| \log^c |A'|$. Thus indeed $|A'| = o(|A|)$.

I know I've seen this argument in the literature, and my question is simply: where?

Answer by Ben Green for Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

2012-06-18T15:16:44Z

I think the answer to this is no. Suppose you can cover the cube with $m$ translates of the Hamming ball of radius $\frac{n}{2} - c\sqrt{n}$. Restrict this to a covering of the sets of size $k := \frac{n}{2} - \frac{1}{10} c \sqrt{n}$. This gives an $m$-colouring of these sets in a natural way. Now if two sets have the same colour then they intersect, and therefore we have an $m$-colouring of the Kneser graph $KG_{n,k}$. But Lovasz famously proved that the chormatic number of the Kneser graph is $n - 2k + 2 = \Omega(\sqrt{n})$.

I'm not sure whether one can use similar methods to get $\Omega(n)$, which is likely the sharp bound. Searching in the literature for "Borsuk graph" may yield results. With thanks to Benny Sudakov.

Answer by Ben Green for Nonlinear equations in integers

2012-05-22T14:15:20Z

Mark Sapir's point is of course valid. The equation $x^2 + y^2 = 2z^2$ is a different matter. There was a discussion of this previously on Math Overflow: see http://mathoverflow.net/questions/78949/

Answer by Ben Green for Perron, Fourier

2012-03-28T18:09:40Z

Harald,

My personal stance on this is that I like to try and avoid using Perron's formula in the "traditional" form. Instead, I like to see the Prime Number Theorem (say) as a statement about $\sum \Lambda(n) \phi(n)$, where $\phi$ is a $C^{\infty}_0$ cutoff function approximating the interval $[1,X]$. To relate this to $\zeta'/\zeta$, you need the Mellin inversion formula for $\phi$ on the vertical line $\Re s = \sigma$, and this really is precisely the same thing as the Fourier inversion formula for the function $e^{\sigma u}\phi(e^u)$. Since everything is a compactly supported smooth function, and in particular a Schwartz function, the analytic issues involved with inverting the Fourier transform are as mild as they can be.

My point of view on this is elaborated upon in in chapter 1 of this course http://www.dpmms.cam.ac.uk/~bjg23/ANT.html.

Answer by Ben Green for minimum number of subsets?

2012-02-03T16:03:17Z

If you want each $l$-tuple of elements to occur at least once then you can do this with $(1 + o(1))\binom{n}{l}/\binom{k}{l}$ sets, which is within $1 + o(1)$ of optimal by a simple counting argument. This is proven using something called the R\"odl Nibble. Most likely when $l = 2$, which is the situation you're interested in, there is a direct construction. The problem is perhaps more naturally formulated in terms of graphs: you're looking for a covering of all the edges of the complete graph $K_n$ by copies of $K_k$.

In terms of explicit constructions, this paper seems relevant. I'm led to understand that one of the authors takes a passing interest in Math Overflow; perhaps he will comment further.

MR1333298 (96e:05043) Gordon, Daniel M.(1-CCR); Patashnik, Oren(1-CCR); Kuperberg, Greg(1-CHI) New constructions for covering designs. (English summary) J. Combin. Des. 3 (1995), no. 4, 269–284.

In the spirit of current discussions on open access, a free version of the above:

http://front.math.ucdavis.edu/math/9502238

Answer by Ben Green for Is there a Plancherel Theorem for Gowers norms?

2011-12-12T00:01:46Z

There is indeed no known formula of this type. If one is found, it might well make the proof of the Inverse Conjectures much easier, maybe with better bounds. It's certainly very hard to see how anything useful can be said beyond the paper Terry mentions without a new proof of the inverse conjectures.

Answer by Ben Green for Arithmetic Progressions of Squares

2011-10-24T13:08:09Z

Probably not, but a proof is hopeless. Ruzsa and Gyarmati have a preprint in which they construct such a subset of size something like $N/\log \log N$.

Even the colouring version (that is, finite colour the squares, does one of the classes contain a 3-term progression) is open. A very closely-related question (Schur's theorem in the squares) is explicitly asked as Question 11 in this paper by Bergelson:

http://www.math.iupui.edu/~mmisiure/open/VB1.pdf

It is possible to show that a positive density subset of the squares contains a solution to $\frac{1}{4}(x_1 + x_2 + x_3 + x_4) = x_5$ by adapting the technique of arXiv:math/0302311. I'd have to admit this is slightly more than a back of an envelope calculation :-)

Answer by Ben Green for Infimums of exponential sums involving primes

2011-10-20T10:48:40Z

Timothy,

This is likely to be a pretty difficult question I think. For a random sequence of $\pm 1$s in place of the von Mangoldt function $\Lambda(n)$ the answer is a little surprising: the infimum is basically $1/\sqrt{x}$, a result of Konyagin and Schlag. This is available here:

www.math.uchicago.edu/~schlag/papers/POLTRAN.pdf

I say surprising because most people, if they were given 10 seconds to guess the answer, would probably go for $\sqrt{x}$ (I certainly would have).

I'm not sure there's any real reason to suppose that the answer for the deterministic function $\Lambda(n)$ will be much different, except perhaps in logarithmic factors.

I think you have precisely no chance of saying anything useful about the $\alpha_x$, but maybe someone will prove me wrong! I would be surprised if they were not close to equidistributed, though there may be some repulsion effects away from rationals with small denominator (where $S(\alpha)$ will be large).

EDIT: Thinking about it some more, it's not obvious to me even how one would show that $S(1/x) \neq 0$, though maybe this does follow from some kind of lower bound for linear forms in $\log p$. My point is that if there is deviation from the behaviour for a random sequence I would expect that one would see it near $\alpha = 0$ (and near other rationals with small denominator).

Answer by Ben Green for Cliques, Paley graphs and quadratic residues

2011-10-12T21:52:00Z

I'm certain that no "material" improvement to the upper bound has been obtained, and this seems to be a very hard open question. Some time ago Tom Sanders showed me an argument which improves the bound in the case $p = n^2 +1$ to $n - 1$. So far as I can tell he hasn't published this. Even if you regard the $-1$ as a "material improvement", it's a matter for conjecture whether his theorem even applies for infinitely many primes $p$.

The Graham-Ringrose estimates, which you mention, show that one cannot hope for $c(p) = O(\log p)$ for all $p$.

Answer by Ben Green for Roth's theorem and Behrend's lower bound

2011-05-07T17:40:53Z

Dear Yui,

It's only slightly more than a casual remark. Our inability to find a better example is certainly a big reason for believing that Behrend's bound is correct. Julia Wolf and I slightly rehashed the proof of Behrend's bound

http://arxiv.org/abs/0810.0732

When formulated this way, I think the construction looks both fairly natural and fairly unimprovable.

Also, there are beginning to be hints as to the correct behaviour coming from apparently similar equations such as $x_1 + x_2 + x_3 = 3x_4$. I think that Schoen and others, using work of Sanders, may have improved the bounds for this equation to $N \exp(-\log^c N)$, though I'm not certain about this.

Despite these remarks it is not known whether better bounds for Roth's theorem follow from any other more "natural" conjectures, such as the Polynomial Freiman-Ruzsa conjecture, so any suggestion that Behrend is sharp is somewhat tenuous. Some other people think differently, I believe - that it may not be sharp.

Historical question concerning Jordan's theorem

2010-05-02T19:04:53Z

I'm interested in Jordan's theorem which (after applying the unitary trick) states that any finite subgroup of $U_n(\mathbb{C})$ has an abelian subgroup of index $F(n)$, a function depending only on $n$ and not on the finite group.

The "standard" reference for this theorem is, I think, the book of Curtis and Reiner (Representation theory of finite groups and associative algebras, Chapter 36), and I think the argument there is due to Frobenius and Schur. But on Tao's blog

http://terrytao.wordpress.com/2010/02/18/a-proof-of-gromovs-theorem/

there's a slight variant on this argument which I personally find a little more natural.

Here's a very brief sketch. We work by induction on n. Let A be our finite subgroup of $U_n(\mathbb{C})$. Look at the intersection $A'$ of $A$ with a small ball about the identity; this must constitute a reasonable fraction of $A$. Divide into two cases. Case 1: everything in $A'$ is a multiple of $I_n$. Then we are done simply by looking at the subgroup of $A$ generated by $A'$. Case 2: there is an element $\gamma \in A'$ which is not a multiple of $I_n$. Take the nearest such element to $I_n$. Then one may argue that for any $x \in A'$ the commutator $[\gamma,x]$ is both nearer to $I_n$ than $\gamma$ and not a nontrivial multiple of $I_n$: hence it must equal $I_n$ and so $\gamma$ is centralised by the whole of $A'$. However the centraliser of an element such as $\gamma$ is a product of $U_{n_i}(\mathbb{C})$'s with $n_i < n$, and that means we can proceed by induction.

I asked Terry about this and he said someone had sketched the "choose an element closest to the identity" part of the argument and this had seemed the most natural way to conclude.

Anyway, I'd be interested in any comments people have on this or on proofs of Jordan's theorem in general (for example on Jordan's original proof). Can one find the above argument somewhere in the literature? Or was it passed over because it doesn't give especially good bounds on the index of the abelian subgroup?

Answer by Ben Green for Walsh Fourier Transform of the Möbius function

2011-03-10T15:34:20Z

An update to my earlier answer. I've written a proof of this "AC0 prime number conjecture" as a short paper, which can be found here.

http://www.dpmms.cam.ac.uk/~bjg23/papers/primes-boolean.pdf

I thought a bit about establishing a nontrivial bound on the Fourier-Walsh coefficients $\hat{\mu}(S)$ for all sets $S$. My paper does this when $|S| < cn^{1/2}/\log n$ (here $S \subseteq {1,\dots,n}$). On the GRH it works for $|S| = O(n/\log n)$. I remarked before that the extreme case $S = {1,\dots,n}$ follows from work of Mauduit and Rivat.

I still believe that there is hope of proving such a bound in general, but this does seem to be pretty tough. At the very least one has to combine the work of Mauduit and Rivat with the material in my note above, and neither of these (especially the former) is that easy.

Answer by Ben Green for Degree of commutativity of finite groups and subgroups

2011-03-10T10:04:44Z

Dear Eduardo,

I'm not entirely sure what your question is, but I'll take it as an excuse to point out some references on the degree of commutativity of a finite group $G$. I take a (very) lay interest in this because I often set to undergraduates the problem of proving that if $G$ is nonabelian then $d(G) \leq 5/8$.

A very comprehensive discussion of this is may be found in this 1979 paper of Rusin:

http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pjm/1102785075

There's also a 1983 article in Eureka (the magazine of the Cambridge student maths society) by Nigel Boston called "Nearly abelian groups", which (from memory) gives a fun exposition of the same thing. I've referred to this article before, so perhaps I'll take the opportunity to wander over to the library and scan it in, since this publication is not widely available outside Cambridge.

Secondly I'd like to draw attention to a paper of Peter Neumann called "Two combinatorial problems in group theory".

MR1005821 (90f:20036) Neumann, Peter M.(4-OXQ) Two combinatorial problems in group theory. Bull. London Math. Soc. 21 (1989), no. 5, 456–458.

I chanced across it quite by accident about 10 years ago. It proves the following very nice result: if $d(G) \geq \alpha$ then there are normal subgroups $K \leq H \lhd G$ with $[G : H] \leq C_1(\alpha)$, $|K| \leq C_2(\alpha)$, and $H/K$ abelian. Roughly, the only way you can have a positive proportion of elements commuting is if $G$ is virtually (small-by-abelian).

To answer your last question, I think the following paper may be relevant.

MR1764885 (2001i:20059) Lévai, L.; Pyber, L.(H-AOS) Profinite groups with many commuting pairs or involutions. (English summary) Arch. Math. (Basel) 75 (2000), no. 1, 1–7

Update: I visited the library and scanned the Eureka article. A PDF is available here: http://www.dpmms.cam.ac.uk/~bjg23/papers/boston.pdf

Answer by Ben Green for A learning roadmap for Additive combinatorics.

2010-11-21T08:58:24Z

Apart from Tao-Vu (which is a very useful resource) there aren't any obvious books from which to learn this subject at all comprehensively. The books Kevin recommends give an excellent survey of the state of the area in the late 1990s.

For more recent material, here are a few sets of course notes. Some of these are a bit more leisurely than Tao-Vu.

Jacques Verstraete: http://www.wix.com/annatar0/math262

Andrew Granville: http://www.dms.umontreal.ca/~andrew/Courses/MAT6640.H10.html

Ben Green: http://www.dpmms.cam.ac.uk/~bjg23/add-combinatorics.html

Terry Tao: http://www.math.ucla.edu/~tao/254a.1.03w/

For an overview of the content of Tao-Vu, you could consult my review of it in the Bulletin of the AMS:

http://www.ams.org/journals/bull/2009-46-03/S0273-0979-09-01231-2/home.html

Answer by Ben Green for Does Weyl's Inequality prove equidistribution?

2010-08-17T20:55:25Z

David,

At first sight I think you might be right about this. Personally, I try to avoid using Weyl's inequality in this form, but rather some statement of the following form: If $|S_N| \geq \epsilon N$, and if $\epsilon > N^{-c}$, then there is some $q \leq \epsilon^{-C}$ such that the fractional part of $q\theta$ is at most $\epsilon^{-C}/N^d$.

In other words: if the exponential sum is large then $\theta$ is very close to a rational with denominator $q$.

I sketch a proof of this ``log-free'' variant below. I don't think the inequality is typically stated in this way because so far as I'm aware it's more effort to prove, and because the form you stated is just fine for Waring's problem, where the factor of $(\log N)^C$ isn't very important. However, as you point out, it does seem to be important when talking about the equidistribution result (although normally one wouldn't involve quantitative estimates when talking about equidistribution results of the type you state).

Let me try to be a little more specific about how to prove this ``log free'' variant of Weyl's inequality that I've mentioned. Presumably there is a reference in the literature. However you can start from the presentation that I give on pages 59-60 of these notes

http://www.dpmms.cam.ac.uk/~bjg23/AddNumTheory/chap3.ps

At some point one obtains many $h_1, h_2, \dots, h_d$ for which $\Vert \theta h_1,\dots, h_d \Vert$ is small. At this point it is standard to invoke the divisor function estimate to show that there are in fact many $n$ for which $\Vert \theta n \Vert$ is small. However in doing this one loses an $N^{\epsilon}$ (it's worse than $\log^C N$ - are you sure you've quoted Gowers accurately?). To avoid losing it, let $S$ be the set of all $h_1\dots h_d$ mentioned above. Then $\Vert \theta (s_1 + s_2 + \dots + s_m) \Vert$ is small for all choices of $s_1,\dots, s_m \in S$, and one can argue* that for big enough $m$ this set of sums of $S$ is really big (i.e. there is no loss of $N^{\epsilon}$.)

*The key point is that for large enough $m$, the number of representations of any $n \in [X^d, 2X^d]$ as a sum of $m$ things of the form $h_1 \dots h_d$, $h_i \sim X$ is bounded by $C X^{d(m-1)}$. The usual proof would have $m = 1$, where this statement is actually false. The problem is, I think I'd need to use the Hardy-Littlewood method (which uses Weyl's inequality, but only the weaker form with the $N^{\epsilon}$) to prove this statement! Little surprise that you don't find this argument in textbooks then.

Actually, I'd be very interested to see a decent reference for all this.

Answer by Ben Green for Are all primes in a PAP-3?

2010-08-02T20:25:10Z

This question is extremely close to this one

http://mathoverflow.net/questions/2214/covering-the-primes-by-3-term-aps

though not exactly the same.

For much the same reasons as described in the answer given there, the answer to your question is almost certainly yes, but a proof is beyond current technology, exactly as you suggest. I'm not aware that the problem has a specific name.

To show that 3 belongs to a 3PAP is of course trivial: it belongs to 3,5,7 or 3,7,11. Showing that there are infinitely many such 3PAPs is, as you point out, a problem of the same level as difficulty as the Sophie Germain primes conjecture or the twin primes conjecture.

For a general p, I find it extremely unlikely that you could show that there is a k > 0 such that p + k, p + 2k are both prime without showing that there are infinitely many. Proving this for even one value of p would be a huge advance.

I think you could show that almost all primes p do have this property using the Hardy-Littlewood circle method.

Answer by Ben Green for Algebraic geometry used "externally" (in problems without obvious algebraic structure).

2010-06-25T18:07:57Z

A really nice example is the (unpublished) work of Larsen and Pink on the "rough" classification of subgroups of $\mbox{GL}_n(k)$. Here's a link: http://www.math.ethz.ch/~pink/ftp/LP5.pdf

In one sentence, the idea is to study these subgroups by looking at their "effective Zariski closures", whereupon techniques of algebraic geometry may be brought to bear on the problem.

Answer by Ben Green for covering a square with unit squares

2010-06-25T16:44:55Z

This reference is certainly pertinent, being the second Google hit for "covering a square with squares" (after your question). Just reading it now...

http://www.uccs.edu/~faculty/asoifer/docs/untitled.pdf

UPDATE: so far as I can tell from looking at this article, the author regards your question as an unsolved problem. There is a further article by him and Karabash, apparently in (his) journal Geombinatorics, vol. 18, which I cannot access online and which has not been reviewed on MathSciNet.

Least collaborative mathematician

2010-06-21T13:05:28Z

The recent question about the most prolific collaboration interested me. How about this question in the opposite direction, then: can anyone beat, amongst contemporary mathematicians, the example of Christopher Hooley, who has written 91 papers and has yet to coauthor a single one (at least if one discounts an obituary written in 1986)?

Answer by Ben Green for How does one use the Poisson summation formula?

2010-06-20T17:49:50Z

The existing answers list some important situations where Poisson Summation plays a role, the application to proving the functional equation of $\theta$ and hence of $\zeta$ being my personal favourite. My best answer to Tim's question as he actually asked it might be: why not have it in mind to try using it whenever you have a discrete sum that you are having trouble estimating, especially if you fancy your chances of understanding the Fourier transform of the summands. You'll end up with a different sum and it might be a lot easier to understand, and you might even be able to approximate your first sum by an integral (the term $\hat{f}(0)$ in the Poisson summation formula).

To explain a little more with an example, there's a whole theory concerned with the estimation of exponential sums $\sum_{n \leq N} e^{2\pi i \phi(n)}$. There are two processes called A and B that can be used to turn a sum like this into something you might be better positioned to understand. Process A is basically Weyl/van der Corput differencing (Cauchy-Schwarz) and process B is essentially Poisson summation. It's not a very straightforward task to put together a theory of how these processes interact, and how they may best be combined to estimate your sum, and in fact this is in general something of an art. The 10 lectures book by Montgomery contains a nice exposition, and there's a whole LMS lecture note volume by Graham and Kolesnik if you want more details.

I want to share a perhaps slightly obscure paper of Roberts and Sargos (Three-dimensional exponential sums with monomials, Journal fur die reine und angewandte Mathematik (Crelle) 591), in which they use Poisson Summation in the form of Process B mentioned above arbitrarily many times to establish the following rather simple-to-state result: the number of quadruples $x_1,x_2,x_3,x_4$ in $[X, 2X)$ with

$$|1/x_1 + 1/x_2 - 1/x_3 - 1/x_4| \leq 1/X^3$$

is $X^{2 + o(1)}$. In other words, the quantities $1/a + 1/b$ tend to avoid one another to pretty much the same extent as random numbers of the same size. Very very roughly speaking (I don't really understand the argument in depth) the proof involves looking at exponential sums $\sum_x e^{2\pi i m/x}$, and it is these that are transformed repeatedly using Poisson summation followed by other modifications (it being reasonably pointless to try and apply Poisson sum twice in succession).

Answer by Ben Green for Intervals with large numbers of primes

2010-05-26T17:20:48Z

For fixed $k$ this is definitely hopeless, since it would imply that for some $b$ there are infinitely many primes $p$ such that $p + b$ is prime, and this is a well-known open problem that seems out of reach of the latest techniques for finding small gaps between primes (see this survey article of Soundararajan for example: http://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01142-6/S0273-0979-06-01142-6.pdf)

For similar reasons this will also be hopeless if $k$ is too small depending on $n$.

If $k$ is huge compared with $n$ then the existence of many such pairs would follow immediately from the prime number theorem if only one knew that $a_k \leq (1 + o(1))\pi(k)$. However, I do not believe this is known and in fact I'm nigh-on certain that nothing better than $a_k \leq 2\pi(k)$ is known. This is a result of Montgomery and Vaughan; the slightly weaker bound of $a_k \leq (2 + o(1))\pi(k)$ follows rather easily from the Selberg upper bound sieve. Incidentally, the presence of the factor $2$ here reflects something called the parity problem in sieve theory: breaking it, even by a tiny amount, is generally very problematic.

In the previous discussion referenced above, the result of Hensley and Richards was mentioned. This is an example to show that it is \emph{not} true that $a_k \leq \pi(k)$. As you hint in the question, one might then conjecture that there is $n$ such that ${n+1,\dots, n+k}$ contains $a_k > \pi(k)$ primes, in which case one would have a violation of the triangle inequality $\pi(x+y) \leq \pi(x) + \pi(y)$. Such a conjecture would follow from the Hardy-Littlewood $k$-tuple conjecture which is, of course, hopelessly out of reach.

Answer by Ben Green for Given n k-element subsets of n, is there a small subset A of n which intersects them all?

2010-05-17T23:19:26Z

I believe, reading the abstract, that the paper "Transversal numbers of uniform hypergraphs", Graphs and Combinatorics 6, no. 1, 1990 by Noga Alon answers your question in the affirmative, for some definition of ``your question''. Namely, the worst case is that $A$ has to have size about $2\log k/k$ times $n$, and this multiplier tends to zero as $k$ tends to infinity.

Here's a free copy of the paper.

http://www.cs.tau.ac.il/~nogaa/PDFS/Publications/Transversal%20numbers%20of%20uniform%20hypergraphs.pdf

I'm certainly no expert on these matters and my advice would be to look at this and related literature on transversals of hypergraphs. Your collection $C$ of sets is the same thing as a $k$-uniform hypergraph, and the property that you want from $A$ is equivalent to it being a transversal.

Reading Alon's paper a little more I see that what you want is the easier direction of his argument (which gives a tight dependence on $k$). The basic idea is to choose your transversal randomly by picking elements of ${1,\dots,n}$ with an appropriate probability $p$. That way, with high probability, you'll hit most of the sets from your collection $C$, and then you just add in one extra element of $A$ for each un-hit set from $C$.

Reading a little further still, I see that the upper bound is probabilistic as well: that is, to make a collection $C$ which is ``bad'', the best plan is to choose sets in $C$ at random from amongst all $k$-element subsets of ${1,\dots,n}$.

There's probably literature on your ``almost transveral'' question, but I'll leave someone else to find it. My guess is that random does best in both directions there too.

Answer by Ben Green for Random projection and finite fields

2010-05-04T14:24:50Z

Suppose the vectors are $e_1,\dots,e_n$. The kernel of projection onto a random subspace of dimension $n+r$ is a random subspace of dimension $n-r$, so you want the probability that such a subspace has trivial intersection with the span of $e_1,\dots, e_n$. Now just count the number of choices for a basis $v_1,\dots, v_{n-r}$ of such a space: $2^{2n} - 2^n$ for the first vector, then $2^{2n} - 2^{n+1}$ for the second, and so on. This is to be compared with $2^{2n} - 1$ choices for the first vector if one doesn't have an restriction, $2^{2n}-2$ for the second and so on.

So the probability of this happening is the ratio of these two quantities, which you need to find a good approximation for; a very brief back-of-an-envelope calculation suggested it's about $1 - c2^{-r}$, at least if $r$ is largeish. For your specific needs, then, $d - n$ should be about $C\log n$.

Translation of Goldbach's 1742 letter to Euler

2010-05-03T15:57:38Z

This ought to be a simple one to answer. Does anyone know of, or can anyone provide, an accurate English translation of the marginal remarks in Goldbach's letter to Euler

http://upload.wikimedia.org/wikipedia/commons/1/18/Letter_Goldbaxh-Euler.jpg

in which a statement equivalent to the Goldbach conjecture is first stated?

Answer by Ben Green for explicit big linearly independent sets

2010-05-01T21:29:17Z

It would be a great surprise to me were there a linear relation between the numbers $\pi^x$, as $x$ ranges over reals all of whose digits in base $3$ are $0$ or $1$.... I guess there must be an example for which one can actually prove something :-)

Answer by Ben Green for Wanted: A constructive version of a theorem of Furstenberg and Weiss

2010-04-29T00:29:42Z

Dear RJS,

I think Tim Gowers is right - the problem seems too hard. Reasonably good bounds are known on (for example) the least $n \geq 1$ for which $\Vert n^2 \sqrt{2} \Vert \leq \epsilon$; one can find such an $n$ with $n \leq \epsilon^{-7/4 + o(1)}$. This is a result of Zaharescu [Zaharescu, A; Small values of $n^2\alpha\pmod 1$. Invent. Math. 121 (1995), no. 2, 379--388.] Zaharescu in fact obtains this result for any $\theta$ in place of $\sqrt{2}$. From a cursory glance at the paper I see that he uses the continued fraction expansion for $\theta$ and so it may be that one can slightly improve his bound in the particular case of $\sqrt{2}$.

It is an old conjecture of Heilbronn that the right bound here should be $\epsilon^{-1 + o(1)}$. I don't know off the top of my head whether any more precise conjectures have been made based on sensible heuristics either for this or for your original problem.

To get an explicit upper bound for your problem one can proceed quite straightforwardly using arguments due to Weyl. I don't think this is the right place to describe an argument in detail: there are several variants, and I first learnt this from a Tim Gowers course at Cambridge. See Theorem 3.10 of these notes:

http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/notes-acnt.pdf

If you really had to show that 627 is the answer to your specific problem, probably the best bet would be to inspect all the quadratics $n^2\sqrt{2} + \theta n + \theta'$ for $\theta,\theta'$ in some rather dense finite subset of $[0,1]^2$ and show using a computer that each takes (mod 1) a value less than 0.009999 for some $n \leq 627$. Painful!

The argument of Furstenberg and Weiss uses ergodic theory and so will not directly lead to an effective bound.

There are quite detailed conjectures about the fractional parts of $n^2\sqrt{2}$ (and other similar sequences) due to Rudnick, Sarnak and Zaharescu, essentially encoding the fact that this sequence of fractional parts is expected to behave like a Poisson process. I don't think those conjectures are likely to be helpful in your context since, taken too literally, they would seem to suggest that there are arbitrarily long intervals without a number such that $\Vert n^2 \sqrt{2} \Vert < 0.01$ - contrary to Furstenberg-Weiss.

Nonetheless let me point out a recent paper of Heath-Brown which is very interesting in connection with these matters:

http://arxiv.org/pdf/0904.0714v1.

One more point perhaps worthy of mention: sequences with bounded gaps are usually known as syndetic.

Answer by Ben Green for Are There Primes of Every Hamming Weight?

2010-04-27T16:01:07Z

Fedja is absolutely right: this has been proven, for sufficiently large $n$, by Drmota, Mauduit and Rivat.

Although it looks at first sight as though this question is as hopeless as any other famous open problem on primes, it is easy to explain why this is not the case. Of the numbers between $1$ and $N := 2^{2n}$, the proportion whose digit sum is precisely $n$ is a constant over $\sqrt{\log N}$. These numbers are therefore quite "dense", and there is a technique in prime number theory called the method of bilinear sums (or the method of Type I/II sums) which in principle allow one to seriously think about finding primes in such a set. This is what Drmota, Mauduit and Rivat do.

I do not believe that their method has currently been pushed as far as (for example) showing that there are infinitely many primes with no 0 when written in base 1000000.

Let me also remark that they depend in a really weird way on some specific properties of these digit representation functions, in particular concerning the sum of the absolute values of their Fourier coefficients, which is surprisingly small. That is, it is not the case that they treat these Hamming sets as though they were "typical" sets of density $1/\sqrt{\log N}$.

I think one might also mention a celebrated paper of Friedlander and Iwaniec, http://arxiv.org/abs/math/9811185. In this work they prove that there are infinitely many primes of the form $x^2 + y^4$. This sequence has density just $c/N^{1/4}$ in the numbers up to $N$, so the analysis necessary to make the bilinear forms method work is really tough. Slightly later, Heath-Brown adapted their ideas to handle $x^3 + 2y^3$. Maybe that's in some sense the sparsest explicit sequence in which infinitely many primes are known (except of course for silly sequences like $s_n$ equals the first prime bigger than $2^{2^n}$).

Finally, let me add the following: proving that, for some fixed $n$, there are infinitely many primes which are the sum of $n$ powers of two - this is almost certainly an open problem of the same kind of difficulty as Mersenne primes and so on.

Answer by Ben Green for What are some examples of colorful language in serious mathematics papers?

2010-04-23T13:39:44Z

The reader who makes it to the later chapters of M. N. Huxley's Area, Lattice Points and Exponential sums is rewarded with the following gem:

"If mathematics were an orchestra, the exponentials would be the violins. The $\rho(t)$ would be the flutes; they are introduced by the exponentials. The Poisson summation formula would be the tuba: powerful, but ridiculous when used too much"

Comment by Ben Green

2013-05-21T16:19:15Z

I'll denote any points I get from this observation (which I stole from someone else anyway) to a good cause. An additional point to be made, now the preprint is available, is that the Bombieri-Fouvry-Friedlander-Iwaniec type results on level of distribution depend on an estimate for sums of Kloosterman sums that requires (via a lemma of Bombieri and Birch) Deligne's work on the Weil Conjectures. It seems to me (though I'm certainly not an expert) that these estimates are not accessible by the more elementary methods such as Dwork/Stepanov.

Comment by Ben Green

2013-05-20T09:45:34Z

Mark - we added our comments at the same time. I was referring to the table on page 12 of GPY, whereas you were referring to the one on p9. I guess the one on page 9 tells you what you can get using just the basic GPY method, and the one on page 12 uses more complicated weights. I guess Zhang elaborates on the basic GPY method. Maybe his method can be combined with the more complicated GPY method which leads to the numerics on page 12; it seems likely that this will be one place any would-be 70000000-reducers will look first.

Comment by Ben Green

2013-05-20T09:39:24Z

It's interesting to speculate on how much the 70000000 will be reduced. In this regard, the table on page 12 of Goldston-Pintz-Yildirim is relevant. If one had level of distribution 4/7 with no strings attached, it seems one might get gaps of size 500 or so. To get gaps under 100 without some completely new idea one would have to go out to level of distribution nearly 2/3, i.e. double the improvement of BFI. I'd wager that getting down to 10000 or so is going to prove pretty difficult.

Comment by Ben Green

2013-04-19T16:02:17Z

I finally dug out the reference myself using a MathSciNet search. MR1931192 (2003f:11016) Reviewed Schoen, Tomasz(PL-POZN) The cardinality of restricted sumsets. (English summary) J. Number Theory 96 (2002), no. 1, 48–54.

Comment by Ben Green

2013-04-19T11:30:34Z

Thanks Seva - but I'm sure I've seen this exact argument somewhere. I guess not in one of your papers then?

Comment by Ben Green

2013-04-09T11:15:03Z

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}?

Comment by Ben Green

2013-03-26T18:27:20Z

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,

Comment by Ben Green

2013-03-11T10:13:39Z

This is nicely done.

Comment by Ben Green

2013-03-08T18:26:31Z

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?

Comment by Ben Green

2013-03-08T17:47:52Z

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.

Comment by Ben Green

2013-03-08T07:35:52Z

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

Comment by Ben Green

2013-03-07T22:08:53Z

I should add, though, that I have to prepare an undergraduate lecture now - so I'll try and write down the details tomorrow.

Comment by Ben Green

2013-03-07T22:08:26Z

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

Comment by Ben Green

2013-03-06T21:35:09Z

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.

Comment by Ben Green

2012-10-19T12:22:51Z

Harald: I think his name is Gonzalo Fiz-Pontiveros.