It is known that finding 3 evenly spaced ones and 3SUM applied to (sorted) arrays with elements in the range $[0, \dots, N]$ can be solved in $\mathcal{O}(n + N \log N)$ time. Methods for solving either of the problems are based on convolution of polynomials (using the DFT).
Similarly, $k$-SUM with limited inputs can be solved in $\mathcal O(2^{\lfloor (k+1)/2 \rfloor} N k\log N)$ time due to an increase in DFT size (for a non-fourier approach of $k$-SUM, see this).
Now, I generalize the question "finding 3 evenly spaced ones" to finding arithmetic progressions, finding one of length $k$ (or verifying it exists) generally has time complexity $\mathcal O(n^2 k)$. But with input $< N$ and $k=3$ we get $\mathcal O(n + N \log N)$ as it can be reduced to 3SUM.
My question: Is there any known (or unknown) method to verify/find an arithmetic progression of any length $k>3$ in under quadratic time? You may use that the input is sorted, in a small range and does not contain any duplicates.
Any help would be much appreciated! I have spend a long time trying to figure this out without being able to think of a type of transform or method to enable this (or make it easier).