Prime subset sums

Efrat Bank‘s interesting number theory seminar here before break was about sums of arithmetic functions on short intervals in function fields.  As I was saying when I blogged about Hast and Matei’s paper, a short interval in F_q[t] means:  the set of monic degree-n polynomials P such that

deg(P-P_0) < h

for some monic degree-n P_0 and some small h.  Bank sets this up even more generally, defining an interval in the space V of global sections of a line bundle on an arbitrary curve over F_q.  In Bank’s case, by contrast with the number field case, an interval is an affine linear subspace of some ambient vector space of forms.  This leads one to wonder:  what’s special about these specific affine spaces?  What about general spaces?

And then one wonders:  well, what classical question over Z does this correspond to?  So here it is:  except I’m not sure this is a classical question, though it sort of seems like it must be.

Question:  Let c > 1 be a constant.  Let A be a set of integers with |A| = n and max(A) < c^n.  Let S be the (multi)set of sums of subsets of A, so |S| = 2^n.  What can we say about the number of primes in S?  (Update:  as Terry points out in comments, I need some kind of coprimality assumption; at the very least we should ask that there’s no prime factor common to everything in A.)

I’d like to say that S is kind of a “generalized interval” — if A is the first n powers of 2, it is literally an interval.  One can also ask about other arithmetic functions:  how big can the average of Mobius be over S, for instance?  Note that the condition on max(S) is important:   if you let S get as big as you want, you can make S have no primes or you can make S be half prime (thanks to Ben Green for pointing this out to me.)  The condition on max(S) can be thought of as analogous to requiring that an interval containing N has size at least some fixed power of N, a good idea if you want to average arithmetic functions.

Anyway:  is anything known about this?  I can’t figure out how to search for it.

Tagged , , ,

3 thoughts on “Prime subset sums

  1. Terence Tao says:

    Somewhat related: Maynard recently proved in that there are infinitely many primes that don’t have, say, 7, in their base 10 digit expansion. (The base 10 is important – the result is not currently known in base 11!). This set is vaguely like a subset sum, and the result was already quite nontrivial to prove, so my guess is not much can be said in the general case. Also there are some obvious local obstructions that can ensure that there are no primes whatsoever, e.g. if all the elements of A are multiples of 4.

  2. JSE says:

    Didn’t know about this Maynard result! It is indeed relevant: for instance, it sounds like it’s certainly out of reach to prove that there are infinitely many primes whose decimal digits are all 0 and 1, which means we can say nothing about the case where A = powers of 10, at least as far as lower bounds for the number of primes is concerned. Upper bounds seem easier at first glance: one can imagine showing that S is reasonably well distributed mod p for a lot of small primes, and that the primes are independent enough that you get a lot of divisibility by small primes among the elements of S.

  3. Vlad Matei says:

    If we take the Fibonacci numbers- every number can be written uniquely as a sum of distinct Fibonacci numbers, so you can generate all the primes up to that certain bound.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: