# co.combinatorics – Number of \$k\$-progressions that share exactly \$m\$ elements with a fixed \$k\$-progression

Let $$A$$ be a subset of a an abelian group $$Z$$. (For the remainder of the question, one can think of $$A={1,ldots,n}$$ and $$Z = {bf Z}$$ if one likes, but feel free to post answers with different choices of $$A$$ and $$Z$$.) For a fixed arithmetic progression $$Psubseteq A$$ of length $$k$$ and $$0leq mleq k$$, we would like to know how many $$k$$-progressions share exactly $$m$$ elements with $$P$$. This will obviously depend on the “shape” of the progression $$P$$, so I’m interested in any statistics one could come up with (average, maximum, minimum, etc.). If $$A$$ depends on a parameter $$n$$ in some way (e.g., $$A = {1,ldots,n}$$, $$A={bf Z}/n{bf Z}$$), one could also take $$n$$ large and see what happens. Obviously, when $$m=k$$, the answer is $$1$$, and when $$m=0$$, this is the number of progressions in $$Asetminus P$$, which will not be awfully different from the number of progressions in $$A$$ when the size of $$A$$ is taken large relative to $$k$$.

This problem came up during an application of the second moment method, so we were only interested in asymptotics of the average. It also turned out that we could get away with a very loose upper bound, so a precise count ended up not being necessary. However, I think it’s a very interesting problem in itself!

Posted on Categories Articles