At most how many $k$-APs in $[n]$ contains a fixed number?

104 Views Asked by At

A non-trivial $k$-term arithmetic progression ($k$-AP) in $[n]=\{1,2,\dots, n\}$ is a set $\{a_1,a_2,\dots,a_k\}$ of $k$ numbers in $[n]$ so that $a_{i+1}-a_i=d>0$ for all $1\le i\le k-1$. Here we can assume $k\ge 3$ is an integer.

I am wondering how good can we have an upper bound on the number of $k$-APs in $[n]$ that contain a given number $a$? Is $n$ a bound?

The current bound I can get is $kn/(k-1)$: there are at most $k$ places to put $a$ in a $k$-AP, and the common difference is at most $n/(k-1)$.

1

There are 1 best solutions below

0
On

Let us concentrate on $3$ term progressions. A similar technique will work for longer ones and I do not know whether a $4$ term progression also counts as two $3$ term progressions.

If $a$ is the first element, we need the difference $d$ to have $1 \le d \le \frac {n-a}2$ so there are $\lfloor \frac {n-a}2 \rfloor$ of them. If $a$ is the second element we need $1 \le d \le \min(a-1,n-a)$. Finally if $a$ is the third element we need $1 \le d \le \frac {a-1}2$ so there are $\lfloor \frac {a-1}2 \rfloor$ of them. The total is just the sum of these $$\left\lfloor \frac {n-a}2 \right\rfloor + \min(a-1,n-a)+\left\lfloor \frac {a-1}2 \right\rfloor$$