Andy's Math/CS page

Wednesday, May 20, 2009

Additive combinatorics: a request for information

Given a subset A of the integers mod N, we can ask, how many 4-element `patterns' appear in A? A pattern is an equivalence class of size-4 subsets of A, where two 4-sets S, S' are considered the same pattern if S = S' + j (mod N) for some j.

Clearly the number of patterns is at most |A|-choose-4; but it can be much less: if A is a consecutive block, or more generally an arithmetic progression, the number of patterns is on the order of |A|^3.

So my question is: if the number of patterns is `much less' then |A|^4, what nice structure do we necessarily find in A?

I believe that similar questions for 2-patterns have satisfactory answers: then the hypothesis is just that the difference-set (A - A) is small. In this case I believe A is 'close' to a (generalized) arithmetic progression, although actually I'm having trouble finding the relevant theorem here too (most references focus on sumsets (A + A), for which Frieman's Theorem applies).

Thanks in advance for any pointers!

Labels:

3 Comments:

  • Ask it in mathoverflow, surely somebody (*ahem-ahem* Terry Tao) will help you.

    By Anonymous Anonymous, at 1:14 PM  

  • This is very good, it took me a while to fully understand it, but I did it, very good.

    By Anonymous pharmacy escrow, at 11:55 AM  

  • Hey! Coach Factory Online simply wanted to say your website is one of the nicely laid out, most inspirational I have come across in quite a while.

    By Anonymous Coach Factory Online, at 2:27 AM  

Post a Comment

<< Home