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!
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: general math
3 Comments:
Ask it in mathoverflow, surely somebody (*ahem-ahem* Terry Tao) will help you.
By 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 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 Coach Factory Online, at 2:27 AM
Post a Comment
<< Home