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!